用Python從零開始實現(xiàn)簡單遺傳算法
遺傳算法是一種隨機全局優(yōu)化算法。連同人工神經(jīng)網(wǎng)絡，它可能是最流行和廣為人知的生物學啟發(fā)算法之一。該算法是一種進化算法，它通過自然選擇，具有二進制表示形式和基于遺傳重組和遺傳突變的簡單算子，來執(zhí)行受進化生物學理論啟發(fā)的優(yōu)化過程。
在本教程中，您將發(fā)現(xiàn)遺傳算法優(yōu)化算法。完成本教程后，您將知道：
- 遺傳算法是一種受進化啟發(fā)的隨機優(yōu)化算法。
- 如何在Python中從頭開始實現(xiàn)遺傳算法。
- 如何將遺傳算法應用于連續(xù)目標函數(shù)。
教程概述
本教程分為四個部分。他們是：
- 遺傳算法
- 從零開始的遺傳算法
- OneMax的遺傳算法
- 連續(xù)函數(shù)優(yōu)化的遺傳算法
遺傳算法
遺傳算法是一種隨機全局搜索優(yōu)化算法。它受到自然選擇進化生物學理論的啟發(fā)。具體來說，是將對遺傳學的理解與理論相結合的新綜合方法。
該算法使用遺傳表示（位串），適應度（功能評估），基因重組（位串交叉）和突變（翻轉位）的類似物。該算法的工作原理是首先創(chuàng)建固定大小的隨機位串。重復算法的主循環(huán)固定次數(shù)的迭代，或者直到在給定迭代次數(shù)的最佳解決方案中看不到進一步的改善為止。該算法的一次迭代就像是進化的一代。
首先，使用目標函數(shù)評估總體位串（候選解決方案）。每個候選解決方案的目標函數(shù)評估被視為解決方案的適用性，可以將其最小化或最大化。然后，根據(jù)他們的健康狀況選擇父母。給定的候選解決方案可以用作父級零次或多次。一種簡單有效的選擇方法包括從總體中隨機抽取k個候選者，并從適應性最好的組中選擇成員。這就是所謂的錦標賽選擇，其中k是一個超參數(shù)，并設置為諸如3的值。這種簡單的方法模擬了成本更高的適應度成比例的選擇方案。
父母被用作生成下一代候選點的基礎，并且人口中的每個職位都需要一個父母。
然后將父母配對，并用來創(chuàng)建兩個孩子。使用交叉算子執(zhí)行重組。這涉及在位串上選擇一個隨機的分割點，然后創(chuàng)建一個子對象，該子對象的位從第一個父級到分割點直至從第二個父級到字符串的末尾。然后，為第二個孩子倒轉此過程。
例如，兩個父母：
parent1 = 00000
parent2 = 11111
可能會導致兩個交叉孩子：
子1 = 00011
孩童2 = 11100
這稱為單點交叉，并且操作員還有許多其他變體。
交叉概率是對每對父母概率應用的，這意味著在某些情況下，父母的副本將作為孩子而不是重組算子。交叉由設置為較大值（例如80％或90％）的超參數(shù)控制。變異涉及在已創(chuàng)建的子候選解決方案中翻轉位。通常，將突變率設置為1 / L，其中L是位串的長度。
例如，如果問題使用具有20位的位串，則良好的默認突變率將是（1/20）= 0.05或5％的概率。
這定義了簡單的遺傳算法過程。這是一個很大的研究領域，并且對該算法進行了許多擴展。
現(xiàn)在我們已經(jīng)熟悉了簡單的遺傳算法過程，下面讓我們看一下如何從頭開始實現(xiàn)它。
從零開始的遺傳算法
在本節(jié)中，我們將開發(fā)遺傳算法的實現(xiàn)。第一步是創(chuàng)建隨機位串。我們可以使用布爾值True和False，字符串值“ 0”和“1”，或者整數(shù)值0和1。在這種情況下，我們將使用整數(shù)值。我們可以使用randint（）函數(shù)生成一個范圍內(nèi)的整數(shù)值數(shù)組，并且可以將范圍指定為從0開始且小于2的值，例如 0或1。為了簡化起見，我們還將候選解決方案表示為列表而不是NumPy數(shù)組。可以如下創(chuàng)建初始的隨機位串填充，其中“n_pop”是控制填充大小的超參數(shù)，“n_bits”是定義單個候選解決方案中位數(shù)的超參數(shù)：
# initial population of random bitstring
pop = [randint(0, 2, n_bits).tolist() for _ in range(n_pop)]接下來，我們可以枚舉固定數(shù)量的算法迭代，在這種情況下，該迭代由名為“ n_iter”的超參數(shù)控制。
...
# enumerate generations
for gen in range(n_iter):
...算法迭代的第一步是評估所有候選解。
我們將使用一個名為Objective（）的函數(shù)作為通用目標函數(shù)，并對其進行調(diào)用以獲取適合度得分，我們將其最小化。
# evaluate all candidates in the population
scores = [objective(c) for c in pop]然后，我們可以選擇將用于創(chuàng)建子代的父代。
錦標賽選擇過程可以實現(xiàn)為一種函數(shù)，該函數(shù)可以獲取總體并返回一個選定的父級。使用默認參數(shù)將k值固定為3，但是您可以根據(jù)需要嘗試使用不同的值。
# 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 (e.g. perform a tournament)
if scores[ix] < scores[selection_ix]:
selection_ix = ix
return pop[selection_ix]然后，我們可以為總體中的每個位置調(diào)用一次此函數(shù)，以創(chuàng)建父母列表。
# select parents
selected = [selection(pop, scores) for _ in range(n_pop)]然后，我們可以創(chuàng)建下一代。
這首先需要執(zhí)行交叉的功能。此功能將占用兩個父級和交叉率。交叉率是一個超參數(shù)，它確定是否執(zhí)行交叉，如果不進行交叉，則將父級復制到下一代。這是一個概率，通常具有接近1.0的較大值。
下面的crossover（）函數(shù)使用范圍為[0,1]的隨機數(shù)來實現(xiàn)交叉以確定是否執(zhí)行了交叉，然后如果要進行交叉則選擇有效的分割點。
# 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]我們還需要執(zhí)行突變的功能。該過程簡單地以“ r_mut”超參數(shù)控制的低概率翻轉位。
# 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]然后，我們可以遍歷父級列表并創(chuàng)建要用作下一代的子級列表，根據(jù)需要調(diào)用交叉和變異函數(shù)。
# 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（）的函數(shù)中，該函數(shù)采用目標函數(shù)的名稱和搜索的超參數(shù)，并返回在搜索過程中找到的最佳解決方案。
# 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]現(xiàn)在，我們已經(jīng)開發(fā)了遺傳算法的實現(xiàn)，讓我們探討如何將其應用于目標函數(shù)。
OneMax的遺傳算法
在本節(jié)中，我們將遺傳算法應用于基于二進制字符串的優(yōu)化問題。該問題稱為OneMax，并根據(jù)字符串中的1的個數(shù)評估二進制字符串。例如，長度為20位的位串對于全1的字符串的得分為20。假設我們已經(jīng)實現(xiàn)了遺傳算法以最小化目標函數(shù)，則可以在此評估中添加負號，以便大的正值變?yōu)榇蟮呢撝?。下面的onemax（）函數(shù)實現(xiàn)了此功能，并將整數(shù)值的位串作為輸入，并返回值的負和。
# objective function
def onemax(x):
return -sum(x)接下來，我們可以配置搜索。
搜索將運行100次迭代，我們將在候選解決方案中使用20位，這意味著最佳適應度為-20.0。
人口總數(shù)將為100，我們將使用90％的交叉率和5％的突變率。經(jīng)過一番嘗試和錯誤后，才選擇此配置。
# 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)然后可以調(diào)用搜索并報告最佳結果。
# 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目標函數(shù)的完整示例。
# 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 (e.g. 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))運行示例將報告沿途發(fā)現(xiàn)的最佳結果，然后在搜索結束時給出最終的最佳解決方案，我們希望這是最佳解決方案。
注意：由于算法或評估程序的隨機性，或者數(shù)值精度的差異，您的結果可能會有所不同。考慮運行該示例幾次并比較平均結果。
在這種情況下，我們可以看到搜索在大約八代之后找到了最佳解決方案。
>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連續(xù)函數(shù)優(yōu)化的遺傳算法
優(yōu)化OneMax功能不是很有趣。我們更可能希望優(yōu)化連續(xù)函數(shù)。例如，我們可以定義x ^ 2最小化函數(shù)，該函數(shù)接受輸入變量并在f（0，0）= 0.0時具有最優(yōu)值。
# 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”超參數(shù)作為目標函數(shù)每個輸入變量的位數(shù)，并將其設置為16位。
# bits per variable
n_bits = 16這意味著在給定兩個輸入變量的情況下，我們的實際位字符串將具有（16 * 2）= 32位。
# mutation rate
r_mut = 1.0 / (float(n_bits) * len(bounds))接下來，我們需要確保初始填充會創(chuàng)建足夠大的隨機位串。
# initial population of random bitstring
pop = [randint(0, 2, n_bits*len(bounds)).tolist() for _ in range(n_pop)]最后，在使用目標函數(shù)評估每個位串之前，我們需要將這些位串解碼為數(shù)字。
我們可以通過首先將每個子字符串解碼為整數(shù)，然后將整數(shù)縮放到所需范圍來實現(xiàn)此目的。這將提供一個范圍內(nèi)的值向量，然后可將其提供給目標函數(shù)進行評估。
下面的decode（）函數(shù)以函數(shù)的界限，每個變量的位數(shù)和一個位串作為輸入來實現(xiàn)此目的，并返回已解碼實數(shù)值的列表。
# 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然后，我們可以在算法循環(huán)的開始處調(diào)用它來解碼總體，然后評估總體的解碼版本。
# 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]結合在一起，下面列出了用于連續(xù)函數(shù)優(yōu)化的遺傳算法的完整示例。
# 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 (e.g. 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))運行示例將報告最佳解碼結果以及運行結束時的最佳解碼解決方案。
注意：由于算法或評估程序的隨機性，或者數(shù)值精度的差異，您的結果可能會有所不同?？紤]運行該示例幾次并比較平均結果。
在這種情況下，我們可以看到該算法發(fā)現(xiàn)了一個非常接近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
