如何用Python從零開始實現(xiàn)簡單遺傳算法

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

遺傳算法是一種隨機全局優(yōu)化算法。連同人工神經(jīng)網(wǎng)絡(luò)，它可能是最流行和廣為人知的生物學(xué)啟發(fā)算法之一。該算法是一種進(jìn)化算法，它通過自然選擇，具有二進(jìn)制表示形式和基于遺傳重組和遺傳突變的簡單算子，來執(zhí)行受進(jìn)化生物學(xué)理論啟發(fā)的優(yōu)化過程。

遺傳算法

遺傳算法是一種隨機全局搜索優(yōu)化算法。它受到自然選擇進(jìn)化生物學(xué)理論的啟發(fā)。具體來說，是將對遺傳學(xué)的理解與理論相結(jié)合的新綜合方法。

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

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

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

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

例如，兩個父母：

parent1 = 00000

parent2 = 11111

可能會導(dǎo)致兩個交叉孩子：

子1 = 00011

孩童2 = 11100

這稱為單點交叉，并且操作員還有許多其他變體。

交叉概率是對每對父母概率應(yīng)用的，這意味著在某些情況下，父母的副本將作為孩子而不是重組算子。交叉由設(shè)置為較大值（例如80％或90％）的超參數(shù)控制。變異涉及在已創(chuàng)建的子候選解決方案中翻轉(zhuǎn)位。通常，將突變率設(shè)置為1 / L，其中L是位串的長度。

例如，如果問題使用具有20位的位串，則良好的默認(rèn)突變率將是（1/20）= 0.05或5％的概率。

這定義了簡單的遺傳算法過程。這是一個很大的研究領(lǐng)域，并且對該算法進(jìn)行了許多擴展。

現(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ù)作為通用目標(biāo)函數(shù)，并對其進(jìn)行調(diào)用以獲取適合度得分，我們將其最小化。

# evaluate all candidates in the population  scores = [objective(c) for c in pop]

然后，我們可以選擇將用于創(chuàng)建子代的父代。

錦標(biāo)賽選擇過程可以實現(xiàn)為一種函數(shù)，該函數(shù)可以獲取總體并返回一個選定的父級。使用默認(rèn)參數(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í)行交叉，如果不進(jìn)行交叉，則將父級復(fù)制到下一代。這是一個概率，通常具有接近1.0的較大值。

下面的crossover（）函數(shù)使用范圍為[0,1]的隨機數(shù)來實現(xiàn)交叉以確定是否執(zhí)行了交叉，然后如果要進(jìn)行交叉則選擇有效的分割點。

# 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ù)控制的低概率翻轉(zhuǎn)位。

# 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)

我們可以將所有這些結(jié)合到一個名為generic_algorithm（）的函數(shù)中，該函數(shù)采用目標(biāo)函數(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)，讓我們探討如何將其應(yīng)用于目標(biāo)函數(shù)。

OneMax的遺傳算法

在本節(jié)中，我們將遺傳算法應(yīng)用于基于二進(jìn)制字符串的優(yōu)化問題。該問題稱為OneMax，并根據(jù)字符串中的1的個數(shù)評估二進(jìn)制字符串。例如，長度為20位的位串對于全1的字符串的得分為20。假設(shè)我們已經(jīng)實現(xiàn)了遺傳算法以最小化目標(biāo)函數(shù)，則可以在此評估中添加負(fù)號，以便大的正值變?yōu)榇蟮呢?fù)值。下面的onemax（）函數(shù)實現(xiàn)了此功能，并將整數(shù)值的位串作為輸入，并返回值的負(fù)和。

# objective function  def onemax(x):   return -sum(x)

接下來，我們可以配置搜索。

搜索將運行100次迭代，我們將在候選解決方案中使用20位，這意味著最佳適應(yīng)度為-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)用搜索并報告最佳結(jié)果。

# 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))

結(jié)合在一起，下面列出了將遺傳算法應(yīng)用于OneMax目標(biāo)函數(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)的最佳結(jié)果，然后在搜索結(jié)束時給出最終的最佳解決方案，我們希望這是最佳解決方案。

注意：由于算法或評估程序的隨機性，或者數(shù)值精度的差異，您的結(jié)果可能會有所不同?？紤]運行該示例幾次并比較平均結(jié)果。

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

>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ù)作為目標(biāo)函數(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)]

最后，在使用目標(biāo)函數(shù)評估每個位串之前，我們需要將這些位串解碼為數(shù)字。

我們可以通過首先將每個子字符串解碼為整數(shù)，然后將整數(shù)縮放到所需范圍來實現(xiàn)此目的。這將提供一個范圍內(nèi)的值向量，然后可將其提供給目標(biāo)函數(shù)進(jìn)行評估。

下面的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]

結(jié)合在一起，下面列出了用于連續(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))

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

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

在這種情況下，我們可以看到該算法發(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

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