質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

与えられた確率に応じて個体を選択するルーレット選択を実装したい。

AI_engineer
AI_engineer

総合スコア14

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

1回答

0グッド

0クリップ

494閲覧

投稿2022/11/25 10:48

前提

遺伝的プログラミング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

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答1

0

ベストアンサー

重み付き乱数を使用してみてはいかがでしょうか。
https://docs.python.org/ja/3.10/library/random.html#random.choices
random.choices()関数の引数 weights に各要素の重みを指定することで、相対的な重みに基づいて要素が選ばれます。

py

1sub_population = random.choices(population, weights=(p.fitness for p in population), k=M)

fitnessが小さいものを優先するのであれば下記のようになるかと

py

1sub_population = random.choices(population, weights=(1/p.fitness for p in population), k=M)

追記

M個を重複なしで、かつfitness に応じて優先的に選出したい(fitness大ならば選出確率大)という場合、
random.sample の重み付き版である numpy.random.choice(replace=false, p=重みリスト)を使ってみてはいかがでしょうか。
(非復元重み付きランダムサンプリング)

python

1def select(population,M): 2 new_population = [] 3 # probeの総和を1にするためにfitnessの合計値を求めておく 4 s = sum(u.fitness for u in population) 5 # fitnessから求めた population各個体の選出確率のリスト(重みリスト) 6 prob = [p.fitness/s for p in population] 7 for i in range(len(population)): 8 sub_population = np.random.choice(population,size=M,replace=False,p=prob) 9 best = min(sub_population,key=lambda tree:tree.fitness) 10 new_population.append(deepcopy(best)) 11 return new_population

numpyを使わない場合は下記のような形で。

python

1def select(population,M): 2 new_population = [] 3 for i in range(len(population)): 4 sub_population = [] 5 # 選出用populationのインデックスとfitnessのペアを格納したプール 6 pool = [[idx, p.fitness] for idx,p in enumerate(population)] 7 8 # M個選出するためにM回繰り返す 9 for _ in range(M): 10 # 現在のプールの重みリスト 11 w = [p[1] for p in pool] 12 # 重み付き確率に応じて選出プールから1個選出する 13 selected = random.choices(pool, weights=w, k=1)[0] 14 sub_population.append(population[selected[0]]) 15 # 選出された個体の重みをゼロにして選出対象外とする 16 selected[1]=0 17 18 best = min(sub_population,key=lambda tree:tree.fitness) 19 new_population.append(deepcopy(best)) 20 return new_population 21

※いずれにしても計算は重くなります。

投稿2022/11/25 11:08

編集2022/11/26 01:06
qnoir

総合スコア7889

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

AI_engineer

2022/11/25 11:35

ご回答ありがとうございます。 URL見ましたが、いまいち理解できませんでした... ルーレット選択では、 (個体の選ばれる確率)= (個体の適応度)/ (全個体の適応度の和) で表されます。 相対的な重みに基づいてとありますが、この重み付き乱数でも上式と同じ確率で選択されるのでしょうか。
AI_engineer

2022/11/25 13:04

書いていただいたコードを試してみましたが、sub_populationに選ばられる個体が毎回同じになってしまいます...
qnoir

2022/11/25 13:10

はい。 たとえば下記のコードの結果をみていただければ適応度とみなした「重み」配列の確率で選択されていることが お分かりいただけるかと思います。 import random numbers = list(range(0,10)) #背番号0~9 w = [1, 3, 5, 7, 9, 9, 7, 5, 3, 1] # index0~9:各背番号0~9に応じた重み (=適応度に相当) samples = random.choices(numbers, k = 10000, weights = w) print([samples.count(i) for i in numbers])
qnoir

2022/11/25 13:49 編集

>sub_populationに選ばられる個体が毎回同じになってしまいます... そもそももともとのコードでは、設定されるfitness が、世代を経るごとに大幅な偏りが出るつくりになっているためではないでしょうか。 「全体個体のfitness総和に対する、各個体のfitnessに応じて選出されるようにする」というのが要件と伺っておりますので、仮にfitness が突出して**大きい**個体が存在する場合、サンプリングの過程でその個体が優先的に選ばれるのは当然です。 現状の**select関数内で**計算毎に使用される、各個体のfitnessが、どのような値であるか、確認されましたでしょうか? (場合によっては、質問者さんが想定しない値になっている可能性があるかもしれませんが) (もしかしてfitnessが小さい方を優先的に選ぶ、という要件がありましたでしょうか・であれば回答に追記した形のように逆数にしてみてください。) (fitnessに応じた確率での選出は無視して)1回あたりのサンプリングではとりあえずM個重複なしで選出したい、というのであれば、コードはまた別の形になります。ただしこれは非復元重み付きサンプリングになりますので必ずしも直感的に期待される分布にはなりません。
qnoir

2022/11/27 08:18 編集

重複なしで選出する場合のコードを追記しました。
AI_engineer

2022/11/29 06:43

ご回答ありがとうございます。 コードを見直してみると適合度が小さいものほどよいっぽいですね。 コードの方も勉強になりました。 ありがとうございました。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。