Q&A
前提
遺伝的プログラミングGPで選択を行う際にルーレット選択を行いたいです。
添付しているソースコードのpopulation変数には、1000個の個体(数式)が格納されています。
populationに格納されているそれぞれの個体はTreeクラスによって作られたインスタンスで、tree.fitnessという変数を持ちます。tree.fitnessは各個体の適応度を表しています。
コード中のmain関数でselectという関数を用いて、選択という操作を行っています。
このコードは見た感じトーナメント選択という手法をとっています。
トーナメント選択とは、populationの中からランダムにM個(指定した分)選び、その中でtree.fitnessが最も小さいものを新たにpopulationに格納、といった操作を行っています。
この部分をルーレット選択で実装したいのですが、うまくできず困っています。
ルーレット選択はpopulationに格納されている各個体の適応度tree.fitnessに注目し、
個体i(population[i])の選ばれる確率 = 個体iの適応度 / 全個体の適応度の和
とし、各個体が選択される確率を与えます。その後、与えられた確率に応じて個体を選択し、新たにpopulationに格納、という手順をとります。
実現したいこと
コード中のトーナメント選択をルーレット選択に変えて実装したい。
コードの補足説明
〇main関数
N: 個体数(population)に格納される数
M: トーナメント選択数
initial_population: 初期個体(数式。Treeインスタンス)をランダムに1000個生成し、populationに格納。
各個体はfitnessという変数をもっており、適応度を表す。
実際に今回使う関数はこれくらいだと思うので、ほかの部分は無視していただいて結構です。
わからない箇所あれば補足いたします。
よろしくお願いいたします。
補足情報(FW/ツールのバージョンなど)
該当のソースコード
Python
1import operator 2import math 3import random 4import numpy as np 5from copy import deepcopy 6import matplotlib.pyplot as plt 7 8 9class Tree(list): 10 def __init__(self,content): 11 list.__init__(self,content) 12 self.fitness = None 13 @property 14 def height(self): 15 stack = [0] 16 max_depth = 0 17 for elem in self: 18 depth = stack.pop() 19 max_depth = max(max_depth, depth) 20 stack.extend([depth+1] * elem[2]) 21 return max_depth 22 def searchSubtree(self, begin): 23 end = begin + 1 24 total = self[begin][2] 25 while total > 0: 26 total += self[end][2] - 1 27 end += 1 28 return slice(begin, end) 29 def __str__(self): 30 start = 0 31 str_arr = [""] 32 for node in self: 33 for i in range(len(str_arr)): 34 if str_arr[i] == "": 35 name,func,arity = node 36 if arity != 0: 37 tmp_arr = [name,"(",""] 38 for x in range(arity-1): 39 tmp_arr += [",",""] 40 tmp_arr.append(")") 41 str_arr = str_arr[:i] + tmp_arr + str_arr[i+1:] 42 else: 43 str_arr = str_arr[:i] + [name] + str_arr[i+1:] 44 break 45 return "".join(str_arr) 46 47def makePrimeNumbers(len_numbers): 48 primes = [2, 3] 49 n = 5 50 while len(primes) < len_numbers: 51 isprime = True 52 for i in range(1, len(primes)): 53 if primes[i] ** 2 > n: 54 break 55 if n % primes[i] == 0: 56 isprime = False 57 break 58 if isprime: 59 primes.append(n) 60 n += 2 61 return primes 62 63def protectedDiv(left, right): 64 with np.errstate(divide='ignore',invalid='ignore'): 65 y = np.divide(left, right) 66 if isinstance(y, np.ndarray): 67 y[np.isinf(y)] = 1 68 y[np.isnan(y)] = 1 69 elif np.isinf(y) or np.isnan(y): 70 y = 1 71 return y 72 73def protectedPower(left,right): 74 with np.errstate(over='ignore',invalid='ignore'): 75 y = np.power(left, right) 76 if isinstance(y, np.ndarray): 77 y[np.isinf(y)] = 1 78 y[np.isnan(y)] = 1 79 elif np.isinf(y) or np.isnan(y): 80 y = 1 81 return y 82 83def makeNodeSet(): 84 nodeSet = [] 85 leafSet = [] 86 nodeSet.append(("add",np.add,2)) 87 nodeSet.append(("sub",np.subtract,2)) 88 nodeSet.append(("mul",np.multiply,2)) 89 nodeSet.append(("div",protectedDiv,2)) 90 #nodeSet.append(("pow",np.power,2)) 91 nodeSet.append(("sin",np.sin,1)) 92 nodeSet.append(("cos",np.cos,1)) 93 nodeSet.append(("tan",np.tan,1)) 94 # nodeSet.append(("log",np.log,1)) 95 # nodeSet.append(("exp",np.exp,1)) 96 # nodeSet.append(("sqrt",np.sqrt,1)) 97 98 leafSet.append(("-1",1,0)) 99 leafSet.append(("0",0,0)) 100 leafSet.append(("1",1,0)) 101 leafSet.append(("0.5",0.5,0)) 102 leafSet.append(("0.1",0.1,0)) 103 leafSet.append(("pi",np.pi,0)) 104 leafSet.append(("e",np.e,0)) 105 leafSet.append(("x",None,0)) 106 107 return nodeSet,leafSet 108 109def randomTreeMake(nodeSet,leafSet,_min,_max): 110 height = random.randint(_min,_max) 111 items = [] 112 stack = [0] 113 while len(stack) != 0: 114 depth = stack.pop() 115 if depth == height: 116 node = random.choice(leafSet) 117 else: 118 node = random.choice(nodeSet) 119 stack.extend([depth+1]*node[2]) 120 items.append(node) 121 tree = Tree(items) 122 return tree 123 124def get_y(tree,nodeSet,leafSet,x): 125 stack = [] 126 for node in tree[::-1]: 127 name,func,arity = node 128 if name == "x": 129 output = x 130 else: 131 if arity == 0: 132 output = func*np.ones(x.shape[0]) 133 if arity == 1: 134 output = func(stack.pop()) 135 if arity == 2: 136 output = func(stack.pop(),stack.pop()) 137 stack.append(output) 138 return stack.pop() 139 140def mate(tree1,tree2,limit,limMode): 141 save1 = deepcopy(tree1) 142 save2 = deepcopy(tree2) 143 while True: 144 index1 = random.randint(1,len(tree1)-1) 145 index2 = random.randint(1,len(tree2)-1) 146 slice1 = tree1.searchSubtree(index1) 147 slice2 = tree2.searchSubtree(index2) 148 tree1[slice1],tree2[slice2] = tree2[slice2],tree1[slice1] 149 if limMode == "LENGTH": 150 if len(tree1) <= limit and len(tree2) <= limit: 151 return tree1,tree2 152 elif limMode == "HEIGHT": 153 if tree1.height <= limit and tree2.height <= limit: 154 return tree1,tree2 155 else: 156 return tree1,tree2 157 tree1,tree2 = deepcopy(save1),deepcopy(save2) 158 159def mutate(tree,NodeSet,leafSet,limit,limMode): 160 save = deepcopy(tree) 161 while True: 162 index = random.randrange(len(tree)) 163 slice_ = tree.searchSubtree(index) 164 tree[slice_] = randomTreeMake(NodeSet,leafSet,1,2) 165 if limMode == "LENGTH": 166 if len(tree) <= limit: 167 return tree 168 elif limMode == "HEIGHT": 169 if tree.height <= limit: 170 return tree 171 else: 172 return tree 173 tree = deepcopy(save) 174 175def initial_population(N,nodeSet,leafSet,_min,_max): 176 population = [] 177 for n in range(N): 178 tree = randomTreeMake(nodeSet,leafSet,_min,_max) 179 population.append(tree) 180 return population 181 182def evaluate(population,nodeSet,leafSet,x,y): 183 for tree in population: 184 if tree.fitness == None: 185 _y = get_y(tree,nodeSet,leafSet,x) 186 fitness = np.sum(np.abs(_y - y)) 187 tree.fitness = fitness 188 189def select(population,M): 190 new_population = [] 191 for i in range(len(population)): 192 sub_population = random.sample(population,M) 193 best = min(sub_population,key=lambda tree:tree.fitness) 194 new_population.append(deepcopy(best)) 195 return new_population 196 197def crossover(population,Pcx): 198 random.shuffle(population) 199 for i in range(int(len(population)/2)): 200 if random.random() < Pcx: 201 childA = population[2*i] 202 childB = population[2*i+1] 203 childA,childB = mate(childA,childB,17,"HEIGHT") 204 population[2*i] = deepcopy(childA) 205 population[2*i+1] = deepcopy(childB) 206 population[2*i].fitness = None 207 population[2*i+1].fitness = None 208 return population 209 210def mutation(population,Pmut,nodeSet,leafSet): 211 random.shuffle(population) 212 for i in range(len(population)): 213 if random.random() < Pmut: 214 child = population[i] 215 child = mutate(child,nodeSet,leafSet,17,"HEIGHT") 216 population[i] = deepcopy(child) 217 population[i].fitness = None 218 219 return population 220 221def printLog(population,g): 222 key=lambda tree:tree.fitness 223 worst = max(population,key=key) 224 best = min(population,key=key) 225 ave = sum([tree.fitness for tree in population])/len(population) 226 key=lambda tree:len(tree) 227 max_node = len(max(population,key=key)) 228 min_node = len(min(population,key=key)) 229 ave_node = sum([len(tree) for tree in population])/len(population) 230 print("===========",g,"genelation===========") 231 print("worst fitness : ",worst.fitness," max nodes : ",max_node) 232 print("ave fitness : ",ave ," ave nodes : ",ave_node) 233 print("best fitness : ",best.fitness, " min nodes : ",min_node) 234 235def makeGraph(tree,x,y,nodeSet,leafSet): 236 _y = get_y(tree,nodeSet,leafSet,x) 237 plt.plot(x,y,label="true prime number") 238 plt.plot(x,_y,label="gp prime number") 239 plt.legend(loc="upper left") 240 plt.savefig("test.pdf") 241 242def main(): 243 N = 1000 244 M = 7 245 maxG = 500 246 Pcx = 0.5 247 Pmut = 0.1 248 nodeSet,leafSet = makeNodeSet() 249 x = np.array(range(1,10)) 250 y = np.array(makePrimeNumbers(x.shape[0])) 251 252 population = initial_population(N,nodeSet,leafSet,1,2) 253 g = 0 254 while True: 255 evaluate(population,nodeSet,leafSet,x,y) 256 printLog(population,g) 257 if g == maxG: 258 break 259 population = select(population,M) # 変更したい部分 260 population = crossover(population,Pcx) 261 population = mutation(population,Pmut,nodeSet,leafSet) 262 g+=1 263 best = min(population,key=lambda tree:tree.fitness) 264 print(best) 265 makeGraph(best,x,y,nodeSet,leafSet) 266 267main() 268
回答1件
あなたの回答
tips
プレビュー
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。
2022/11/25 11:35
2022/11/25 13:04
退会済みユーザー
2022/11/25 13:10
退会済みユーザー
2022/11/25 13:49 編集
退会済みユーザー
2022/11/27 08:18 編集
2022/11/29 06:43