|
遺伝的アルゴリズムはランダムなグローバル最適化アルゴリズムです。人工ニューラル ネットワークと並んで、これはおそらく最も人気があり、よく知られている生物学にヒントを得たアルゴリズムの 1 つです。このアルゴリズムは、遺伝子組み換えと遺伝子突然変異に基づくバイナリ表現と単純な演算子を使用して、自然選択による進化生物学理論にヒントを得た最適化プロセスを実行する進化アルゴリズムです。 このチュートリアルでは、遺伝的アルゴリズムの最適化アルゴリズムについて説明します。このチュートリアルを完了すると、次のことが分かります。 - 遺伝的アルゴリズムは、進化にヒントを得た確率的最適化アルゴリズムです。
- Python で遺伝的アルゴリズムをゼロから実装する方法。
- 遺伝的アルゴリズムを連続目的関数に適用する方法。
チュートリアルの概要 このチュートリアルは 4 つのパートに分かれています。彼らです： - 遺伝的アルゴリズム
- ゼロからの遺伝的アルゴリズム
- OneMaxの遺伝的アルゴリズム
- 連続関数最適化のための遺伝的アルゴリズム
遺伝的アルゴリズム 遺伝的アルゴリズムは、ランダムなグローバル検索最適化アルゴリズムです。これは、自然選択による進化という生物学理論に触発されたものです。具体的には、遺伝学の理解と理論を組み合わせた新しい統合アプローチです。 このアルゴリズムは、遺伝的表現 (ビット文字列)、適応度 (機能評価)、遺伝的組み換え (ビット文字列の交差)、および突然変異 (ビットの反転) の類似物を使用します。このアルゴリズムは、まず固定サイズのランダムなビット文字列を作成することによって機能します。アルゴリズムのメイン ループは、固定された反復回数だけ、または指定された反復回数で最適なソリューションにさらなる改善が見られなくなるまで繰り返されます。アルゴリズムの 1 回の反復は、進化の世代のようなものです。 まず、目的関数を使用して全体のビット文字列（候補解）を評価します。各候補ソリューションの目的関数評価は、ソリューションの適合性として考慮され、最小化または最大化できます。次に、健康状態に基づいて親が選択されます。特定の候補ソリューションは、親として 0 回以上使用できます。シンプルで効果的な選択方法は、集団から k 人の候補者をランダムにサンプリングし、最も適応度の高いグループのメンバーを選択することです。これはトーナメント選択と呼ばれ、k はハイパーパラメータであり、3 などの値に設定されます。この単純なアプローチは、コストが適応度に比例する選択シナリオをシミュレートします。 親は、候補サイトの次の世代を生成するための基礎として使用され、集団内の各位置には親が必要です。 次に、親をペアにして 2 人の子供を作成します。組み換えはクロスオーバー演算子を使用して実行されます。これには、ビット文字列上のランダムな分割ポイントを選択し、最初の親から分割ポイントまでのビットと、2 番目の親から文字列の末尾までのビットを使用して子オブジェクトを作成することが含まれます。次に、2 番目の子に対して同じ手順を逆に実行します。 たとえば、2 人の親の場合: 親1 = 00000 親2 = 11111 2 つの交差子が発生する可能性があります: サブ1 = 00011 子供2 = 11100 これはシングルポイントクロスオーバーと呼ばれ、この演算子には他にも多くのバリエーションがあります。 交差確率は各親のペアに確率的に適用されます。つまり、場合によっては、親のコピーが組み換え演算子の代わりに子として使用されます。クロスオーバーは、80% や 90% などの大きな値に設定されたハイパーパラメータによって制御されます。突然変異では、作成された子候補ソリューション内のビットを反転します。通常、突然変異率は 1/L に設定されます。ここで、L はビット文字列の長さです。 たとえば、問題で 20 ビットのビット文字列が使用される場合、適切なデフォルトの突然変異率は (1/20) = 0.05、つまり 5% の確率になります。 これは単純な遺伝的アルゴリズムのプロセスを定義します。これは広範囲にわたる研究分野であり、アルゴリズムには多くの拡張があります。 シンプルな遺伝的アルゴリズムのプロセスについて理解できたので、これをゼロから実装する方法を見てみましょう。 ゼロからの遺伝的アルゴリズム このセクションでは、遺伝的アルゴリズムの実装を開発します。最初のステップは、ランダムなビット文字列を作成することです。ブール値のTrueとFalse、文字列値の「0」と「1」、または整数値の0と1を使用できます。この場合は整数値を使用します。 randint() 関数を使用すると、範囲内の整数値の配列を生成することができ、範囲は 0 から始まり 2 未満の値、たとえば 0 や 1 のように指定できます。また、簡潔にするために、候補ソリューションを NumPy 配列ではなくリストとして表します。初期のランダム ビット文字列集団は次のように作成できます。ここで、「n_pop」は集団のサイズを制御するハイパーパラメータであり、「n_bits」は単一の候補ソリューションの中央値を定義するハイパーパラメータです。 # initial population of random bitstring pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)] 次に、アルゴリズムの反復回数を固定値で列挙します。この場合、反復回数は「n_iter」というハイパーパラメータによって制御されます。 ... # enumerate generations for gen in range(n_iter): ... アルゴリズムの反復の最初のステップは、すべての候補ソリューションを評価することです。 汎用目的関数として Objective() という関数を使用し、それを呼び出して適合スコアを取得し、それを最小化します。 # evaluate all candidates in the population scores = [objective(c) for c in pop] 次に、子を作成するために使用する親を選択できます。 トーナメント選択プロセスは、集団を受け取り、選択された親を返す関数として実装できます。デフォルトのパラメータを使用すると、k 値は 3 に固定されますが、必要に応じて異なる値を試すことができます。 # tournament selection def selection(pop, scores, k=3): # first random selection selection_ix = randint(len(pop)) for ix in randint(0, len(pop), k-1): # check if better (eg perform a tournament) if scores[ix] < scores[selection_ix]: selection_ix = ix return pop[selection_ix] 次に、集団内の各位置に対してこの関数を 1 回呼び出して、親のリストを作成します。 # select parents selected = [selection(pop, scores) for _ in range(n_pop)] そうすれば、次の世代を創ることができるのです。 まず、クロスオーバー関数を実行する必要があります。この関数は、2 つの親と交差率を受け取ります。交差率は、交差が実行されるかどうかを決定し、実行されない場合は親が次の世代にコピーされるハイパーパラメータです。これは確率であり、通常は 1.0 に近い大きな値になります。 以下の crossover() 関数は、[0,1] の範囲の乱数を使用してクロスオーバーを実行するかどうかを決定し、クロスオーバーを実行する場合は有効な分割ポイントを選択してクロスオーバーを実装します。 # crossover two parents to create two children def crossover(p1, p2, r_cross): # children are copies of parents by default c1, c2 = p1.copy(), p2.copy() # check for recombination if rand() < r_cross: # select crossover point that is not on the end of the string pt = randint(1, len(p1)-2) # perform crossover c1 = p1[:pt] + p2[pt:] c2 = p2[:pt] + p1[pt:] return [c1, c2] 突然変異を実行する関数も必要です。このプロセスは、単に「r_mut」ハイパーパラメータによって制御される低い確率でビットを反転するだけです。 # mutation operator def mutation(bitstring, r_mut): for i in range(len(bitstring)): # check for a mutation if rand() < r_mut: # flip the bit bitstring[i] = 1 - bitstring[i] 次に、親のリストを反復処理し、必要に応じて交差関数と突然変異関数を呼び出して、次の世代として使用する子のリストを作成します。 # create the next generation children = list() for i in range(0, n_pop, 2): # get selected parents in pairs p1, p2 = selected[i], selected[i+1] # crossover and mutation for c in crossover(p1, p2, r_cross): # mutation mutation(c, r_mut) # store for next generation children.append(c) これらすべてを generic_algorithm() という関数に組み合わせることができます。この関数は、目的関数の名前と検索するハイパーパラメータを受け取り、検索中に見つかった最適なソリューションを返します。 # genetic algorithm def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut): # initial population of random bitstring pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)] # keep track of best solution best, best_eval = 0, objective(pop[0]) # enumerate generations for gen in range(n_iter): # evaluate all candidates in the population scores = [objective(c) for c in pop] # check for new best solution for i in range(n_pop): if scores[i] < best_eval: best, best_eval = pop[i], scores[i] print(">%d, new best f(%s) = %.3f" % (gen, pop[i], scores[i])) # select parents selected = [selection(pop, scores) for _ in range(n_pop)] # create the next generation children = list() for i in range(0, n_pop, 2): # get selected parents in pairs p1, p2 = selected[i], selected[i+1] # crossover and mutation for c in crossover(p1, p2, r_cross): # mutation mutation(c, r_mut) # store for next generation children.append(c) # replace population pop = children return [best, best_eval] 遺伝的アルゴリズムの実装を開発したので、それを目的関数に適用する方法を検討してみましょう。 OneMaxの遺伝的アルゴリズム このセクションでは、バイナリ文字列ベースの最適化問題に遺伝的アルゴリズムを適用します。この問題は OneMax と呼ばれ、文字列内の 1 の数に基づいてバイナリ文字列を評価します。たとえば、長さが 20 ビットのビット文字列の場合、すべて 1 の文字列のスコアは 20 になります。目的関数を最小化する遺伝的アルゴリズムを実装したと仮定すると、大きな正の値が大きな負の値になるように、この評価に負の符号を追加することができます。以下の onemax() 関数はこの機能を実装し、整数値のビット文字列を入力として受け取り、値の負の合計を返します。 # objective function def onemax(x): return -sum(x) 次に、検索を設定します。 検索は 100 回反復され、候補ソリューションの中から 20 の位置を使用します。つまり、最適な適合度は -20.0 になります。 個体数は 100 で、交差率は 90%、突然変異率は 5% を使用します。この構成は、試行錯誤の末に選択されました。 # define the total iterations n_iter = 100 # bits n_bits = 20 # define the population size n_pop = 100 # crossover rate r_cross = 0.9 # mutation rate r_mut = 1.0 / float(n_bits) その後、検索を呼び出して、最良の結果を報告できます。 # perform the genetic algorithm search best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut) print('Done!') print('f(%s) = %f' % (best, score)) これらすべてをまとめると、遺伝的アルゴリズムを OneMax 目的関数に適用する完全な例が以下にリストされます。 # genetic algorithm search of the one max optimization problem from numpy.random import randint from numpy.random import rand # objective function def onemax(x): return -sum(x) # tournament selection def selection(pop, scores, k=3): # first random selection selection_ix = randint(len(pop)) for ix in randint(0, len(pop), k-1): # check if better (eg perform a tournament) if scores[ix] < scores[selection_ix]: selection_ix = ix return pop[selection_ix] # crossover two parents to create two children def crossover(p1, p2, r_cross): # children are copies of parents by default c1, c2 = p1.copy(), p2.copy() # check for recombination if rand() < r_cross: # select crossover point that is not on the end of the string pt = randint(1, len(p1)-2) # perform crossover c1 = p1[:pt] + p2[pt:] c2 = p2[:pt] + p1[pt:] return [c1, c2] # mutation operator def mutation(bitstring, r_mut): for i in range(len(bitstring)): # check for a mutation if rand() < r_mut: # flip the bit bitstring[i] = 1 - bitstring[i] # genetic algorithm def genetic_algorithm(objective, n_bits, n_iter, n_pop, r_cross, r_mut): # initial population of random bitstring pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)] # keep track of best solution best, best_eval = 0, objective(pop[0]) # enumerate generations for gen in range(n_iter): # evaluate all candidates in the population scores = [objective(c) for c in pop] # check for new best solution for i in range(n_pop): if scores[i] < best_eval: best, best_eval = pop[i], scores[i] print(">%d, new best f(%s) = %.3f" % (gen, pop[i], scores[i])) # select parents selected = [selection(pop, scores) for _ in range(n_pop)] # create the next generation children = list() for i in range(0, n_pop, 2): # get selected parents in pairs p1, p2 = selected[i], selected[i+1] # crossover and mutation for c in crossover(p1, p2, r_cross): # mutation mutation(c, r_mut) # store for next generation children.append(c) # replace population pop = children return [best, best_eval] # define the total iterations n_iter = 100 # bits n_bits = 20 # define the population size n_pop = 100 # crossover rate r_cross = 0.9 # mutation rate r_mut = 1.0 / float(n_bits) # perform the genetic algorithm search best, score = genetic_algorithm(onemax, n_bits, n_iter, n_pop, r_cross, r_mut) print('Done!') print('f(%s) = %f' % (best, score)) 例を実行すると、途中で見つかった最良の結果が報告され、検索の最後に最終的な最良のソリューションが提供されます。これが最適なソリューションであることが期待されます。 注意: アルゴリズムや評価手順の確率的特性、または数値精度の違いにより、結果が異なる場合があります。例を複数回実行し、平均結果を比較することを検討してください。 この場合、検索によって約 8 世代後に最適なソリューションが見つかったことがわかります。 >0, new best f([1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]) = -14.000 >0, new best f([1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0]) = -15.000 >1, new best f([1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1]) = -16.000 >2, new best f([0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]) = -17.000 >2, new best f([1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -19.000 >8, new best f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -20.000 Done! f([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) = -20.000000 連続関数最適化のための遺伝的アルゴリズム OneMax 関数を最適化するのはあまり楽しいことではありません。連続関数を最適化したい場合が多くなります。たとえば、入力変数を受け取り、f(0, 0) = 0.0 で最適値を持つ x^2 最小化関数を定義できます。 # objective function def objective(x): return x[0]**2.0 + x[1]**2.0 遺伝的アルゴリズムを使用してこの関数を最小化できます。まず、各入力変数の境界を定義する必要があります。 # define range for input bounds = [[-5.0, 5.0], [-5.0, 5.0]] 目的関数の入力変数あたりのビット数として「n_bits」ハイパーパラメータを使用し、これを 16 ビットに設定します。 # bits per variable n_bits = 16 つまり、2 つの入力変数が与えられた場合、実際のビット文字列は (16 * 2) = 32 ビットになります。 # mutation rate r_mut = 1.0 / (float(n_bits) * len(bounds)) 次に、初期のパディングによって十分に大きなランダム ビット文字列が作成されることを確認する必要があります。 # initial population of random bitstring pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)] 最後に、目的関数で評価する前に、各ビット文字列を数値にデコードする必要があります。 まず各部分文字列を整数にデコードし、次にその整数を目的の範囲にスケーリングすることでこれを実行できます。これにより、範囲内の値のベクトルが提供され、それを評価のために目的関数に入力することができます。 以下の decode() 関数は、関数の境界、変数ごとのビット数、およびビット文字列を入力として受け取り、デコードされた実数値のリストを返します。 # decode bitstring to numbers def decode(bounds, n_bits, bitstring): decoded = list() largest = 2**n_bits for i in range(len(bounds)): # extract the substring start, end = i * n_bits, (i * n_bits)+n_bits substring = bitstring[start:end] # convert bitstring to a string of chars chars = ''.join([str(s) for s in substring]) # convert string to integer intinteger = int(chars, 2) # scale integer to desired range value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0]) # store decoded.append(value) return decoded 次に、アルゴリズムのループの先頭でこれを呼び出して、集団をデコードし、集団のデコードされたバージョンを評価できます。 # decode population decoded = [decode(bounds, n_bits, p) for p in pop] # evaluate all candidates in the population scores = [objective(d) for d in decoded] これらすべてをまとめると、連続関数の最適化のための遺伝的アルゴリズムの完全な例がここに示されます。 # genetic algorithm search for continuous function optimization from numpy.random import randint from numpy.random import rand # objective function def objective(x): return x[0]**2.0 + x[1]**2.0 # decode bitstring to numbers def decode(bounds, n_bits, bitstring): decoded = list() largest = 2**n_bits for i in range(len(bounds)): # extract the substring start, end = i * n_bits, (i * n_bits)+n_bits substring = bitstring[start:end] # convert bitstring to a string of chars chars = ''.join([str(s) for s in substring]) # convert string to integer intinteger = int(chars, 2) # scale integer to desired range value = bounds[i][0] + (integer/largest) * (bounds[i][1] - bounds[i][0]) # store decoded.append(value) return decoded # tournament selection def selection(pop, scores, k=3): # first random selection selection_ix = randint(len(pop)) for ix in randint(0, len(pop), k-1): # check if better (eg perform a tournament) if scores[ix] < scores[selection_ix]: selection_ix = ix return pop[selection_ix] # crossover two parents to create two children def crossover(p1, p2, r_cross): # children are copies of parents by default c1, c2 = p1.copy(), p2.copy() # check for recombination if rand() < r_cross: # select crossover point that is not on the end of the string pt = randint(1, len(p1)-2) # perform crossover c1 = p1[:pt] + p2[pt:] c2 = p2[:pt] + p1[pt:] return [c1, c2] # mutation operator def mutation(bitstring, r_mut): for i in range(len(bitstring)): # check for a mutation if rand() < r_mut: # flip the bit bitstring[i] = 1 - bitstring[i] # genetic algorithm def genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut): # initial population of random bitstring pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)] # keep track of best solution best, best_eval = 0, objective(pop[0]) # enumerate generations for gen in range(n_iter): # decode population decoded = [decode(bounds, n_bits, p) for p in pop] # evaluate all candidates in the population scores = [objective(d) for d in decoded] # check for new best solution for i in range(n_pop): if scores[i] < best_eval: best, best_eval = pop[i], scores[i] print(">%d, new best f(%s) = %f" % (gen, decoded[i], scores[i])) # select parents selected = [selection(pop, scores) for _ in range(n_pop)] # create the next generation children = list() for i in range(0, n_pop, 2): # get selected parents in pairs p1, p2 = selected[i], selected[i+1] # crossover and mutation for c in crossover(p1, p2, r_cross): # mutation mutation(c, r_mut) # store for next generation children.append(c) # replace population pop = children return [best, best_eval] # define range for input bounds = [[-5.0, 5.0], [-5.0, 5.0]] # define the total iterations n_iter = 100 # bits per variable n_bits = 16 # define the population size n_pop = 100 # crossover rate r_cross = 0.9 # mutation rate r_mut = 1.0 / (float(n_bits) * len(bounds)) # perform the genetic algorithm search best, score = genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut) print('Done!') decodedecoded = decode(bounds, n_bits, best) print('f(%s) = %f' % (decoded, score)) この例を実行すると、実行終了時に最良のデコード結果と最良のデコード ソリューションが報告されます。 注意: アルゴリズムや評価手順の確率的特性、または数値精度の違いにより、結果が異なる場合があります。例を複数回実行し、平均結果を比較することを検討してください。 この場合、アルゴリズムが f(0.0, 0.0) = 0.0 に非常に近い入力を見つけたことがわかります。 >0, new best f([-0.785064697265625, -0.807647705078125]) = 1.268621 >0, new best f([0.385894775390625, 0.342864990234375]) = 0.266471 >1, new best f([-0.342559814453125, -0.1068115234375]) = 0.128756 >2, new best f([-0.038909912109375, 0.30242919921875]) = 0.092977 >2, new best f([0.145721435546875, 0.1849365234375]) = 0.055436 >3, new best f([0.14404296875, -0.029754638671875]) = 0.021634 >5, new best f([0.066680908203125, 0.096435546875]) = 0.013746 >5, new best f([-0.036468505859375, -0.10711669921875]) = 0.012804 >6, new best f([-0.038909912109375, -0.099639892578125]) = 0.011442 >7, new best f([-0.033111572265625, 0.09674072265625]) = 0.010455 >7, new best f([-0.036468505859375, 0.05584716796875]) = 0.004449 >10, new best f([0.058746337890625, 0.008087158203125]) = 0.003517 >10, new best f([-0.031585693359375, 0.008087158203125]) = 0.001063 >12, new best f([0.022125244140625, 0.008087158203125]) = 0.000555 >13, new best f([0.022125244140625, 0.00701904296875]) = 0.000539 >13, new best f([-0.013885498046875, 0.008087158203125]) = 0.000258 >16, new best f([-0.011444091796875, 0.00518798828125]) = 0.000158 >17, new best f([-0.0115966796875, 0.00091552734375]) = 0.000135 >17, new best f([-0.004730224609375, 0.00335693359375]) = 0.000034 >20, new best f([-0.004425048828125, 0.00274658203125]) = 0.000027 >21, new best f([-0.002288818359375, 0.00091552734375]) = 0.000006 >22, new best f([-0.001983642578125, 0.00091552734375]) = 0.000005 >22, new best f([-0.001983642578125, 0.0006103515625]) = 0.000004 >24, new best f([-0.001373291015625, 0.001068115234375]) = 0.000003 >25, new best f([-0.001373291015625, 0.00091552734375]) = 0.000003 >26, new best f([-0.001373291015625, 0.0006103515625]) = 0.000002 >27, new best f([-0.001068115234375, 0.0006103515625]) = 0.000002 >29, new best f([-0.000152587890625, 0.00091552734375]) = 0.000001 >33, new best f([-0.0006103515625, 0.0]) = 0.000000 >34, new best f([-0.000152587890625, 0.00030517578125]) = 0.000000 >43, new best f([-0.00030517578125, 0.0]) = 0.000000 >60, new best f([-0.000152587890625, 0.000152587890625]) = 0.000000 >65, new best f([-0.000152587890625, 0.0]) = 0.000000 Done! f([-0.000152587890625, 0.0]) = 0.000000 |
