如何用Python從零開始實現簡單遺傳算法

今天就跟大家聊聊有關如何用Python從零開始實現簡單遺傳算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

遺傳算法是一種隨機全局優化算法。連同人工神經網絡，它可能是最流行和廣為人知的生物學啟發算法之一。該算法是一種進化算法，它通過自然選擇，具有二進制表示形式和基于遺傳重組和遺傳突變的簡單算子，來執行受進化生物學理論啟發的優化過程。

遺傳算法

遺傳算法是一種隨機全局搜索優化算法。它受到自然選擇進化生物學理論的啟發。具體來說，是將對遺傳學的理解與理論相結合的新綜合方法。

該算法使用遺傳表示（位串），適應度（功能評估），基因重組（位串交叉）和突變（翻轉位）的類似物。該算法的工作原理是首先創建固定大小的隨機位串。重復算法的主循環固定次數的迭代，或者直到在給定迭代次數的最佳解決方案中看不到進一步的改善為止。該算法的一次迭代就像是進化的一代。

首先，使用目標函數評估總體位串（候選解決方案）。每個候選解決方案的目標函數評估被視為解決方案的適用性，可以將其最小化或最大化。然后，根據他們的健康狀況選擇父母。給定的候選解決方案可以用作父級零次或多次。一種簡單有效的選擇方法包括從總體中隨機抽取k個候選者，并從適應性最好的組中選擇成員。這就是所謂的錦標賽選擇，其中k是一個超參數，并設置為諸如3的值。這種簡單的方法模擬了成本更高的適應度成比例的選擇方案。

父母被用作生成下一代候選點的基礎，并且人口中的每個職位都需要一個父母。

然后將父母配對，并用來創建兩個孩子。使用交叉算子執行重組。這涉及在位串上選擇一個隨機的分割點，然后創建一個子對象，該子對象的位從第一個父級到分割點直至從第二個父級到字符串的末尾。然后，為第二個孩子倒轉此過程。

例如，兩個父母：

parent1 = 00000

parent2 = 11111

可能會導致兩個交叉孩子：

子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 (e.g. perform a tournament)   if scores[ix] < scores[selection_ix]:   selection_ix = ix   return pop[selection_ix]

然后，我們可以為總體中的每個位置調用一次此函數，以創建父母列表。

# select parents  selected = [selection(pop, scores) for _ in range(n_pop)]

然后，我們可以創建下一代。

這首先需要執行交叉的功能。此功能將占用兩個父級和交叉率。交叉率是一個超參數，它確定是否執行交叉，如果不進行交叉，則將父級復制到下一代。這是一個概率，通常具有接近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 (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))

運行示例將報告沿途發現的最佳結果，然后在搜索結束時給出最終的最佳解決方案，我們希望這是最佳解決方案。

注意：由于算法或評估程序的隨機性，或者數值精度的差異，您的結果可能會有所不同。考慮運行該示例幾次并比較平均結果。

在這種情況下，我們可以看到搜索在大約八代之后找到了最佳解決方案。

>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功能不是很有趣。我們更可能希望優化連續函數。例如，我們可以定義x ^ 2最小化函數，該函數接受輸入變量并在f（0，0）= 0.0時具有最優值。

# 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

這意味著在給定兩個輸入變量的情況下，我們的實際位字符串將具有（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 (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))

運行示例將報告最佳解碼結果以及運行結束時的最佳解碼解決方案。

注意：由于算法或評估程序的隨機性，或者數值精度的差異，您的結果可能會有所不同。考慮運行該示例幾次并比較平均結果。

在這種情況下，我們可以看到該算法發現了一個非常接近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

看完上述內容，你們對如何用Python從零開始實現簡單遺傳算法有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。