Python人工智慧——遺傳演算法

本章詳細討論人工智慧中的遺傳演算法。

什麼是遺傳演算法？

遺傳演算法 (GA) 是一種基於自然選擇和遺傳學概念的搜尋演算法。遺傳演算法是進化計算這個更大計算分支的子集。

遺傳演算法由約翰·霍蘭德和他在密歇根大學的學生和同事們開發，其中最著名的是大衛·E·戈德堡。此後，它已在各種最佳化問題上進行了嘗試，並取得了高度成功。

在遺傳演算法中，我們有一組給定問題的可能解決方案。然後，這些解決方案會經歷重組和變異（就像在自然遺傳學中一樣），產生新的後代，並且該過程會針對各個世代重複進行。每個個體（或候選解決方案）都被分配一個適應度值（基於其目標函式值），並且適應度更高的個體具有更高的交配機率，從而產生更適應的個體。這與達爾文的適者生存理論相符。

因此，它會隨著世代的推移不斷進化出更好的個體或解決方案，直到達到停止條件。

遺傳演算法本質上是足夠隨機的，但它們比隨機區域性搜尋（我們只嘗試隨機解決方案，並跟蹤到目前為止最好的解決方案）的效能要好得多，因為它們也利用了歷史資訊。

如何將遺傳演算法用於最佳化問題？

最佳化是使設計、情況、資源和系統儘可能有效的行為。下圖顯示了最佳化過程：

用於最佳化過程的遺傳演算法機制階段

以下是將遺傳演算法機制用於問題最佳化時的一系列步驟。

步驟 1 — 隨機生成初始種群。
步驟 2 — 選擇具有最佳適應度值的初始解。
步驟 3 — 使用變異和交叉運算元重組選擇的解。
步驟 4 — 將後代插入種群。
步驟 5 — 現在，如果滿足停止條件，則返回具有最佳適應度值的解。否則，轉到步驟 2。

安裝必要的包

為了使用 Python 中的遺傳演算法解決問題，我們將使用一個名為DEAP的強大的遺傳演算法包。這是一個新穎的進化計算框架庫，用於快速原型設計和測試想法。我們可以在命令提示符下使用以下命令安裝此包：

pip install deap

如果您使用的是anaconda環境，則可以使用以下命令安裝 deap：

conda install -c conda-forge deap

使用遺傳演算法實現解決方案

本節將解釋如何使用遺傳演算法實現解決方案。

生成位模式

以下示例演示如何基於One Max問題生成包含 15 個 1 的位字串。

匯入必要的包，如下所示：

import random
from deap import base, creator, tools

定義評估函式。這是建立遺傳演算法的第一步。

def eval_func(individual):
   target_sum = 15
   return len(individual) - abs(sum(individual) - target_sum),

現在，使用正確的引數建立工具箱：

def create_toolbox(num_bits):
   creator.create("FitnessMax", base.Fitness, weights=(1.0,))
   creator.create("Individual", list, fitness=creator.FitnessMax)

初始化工具箱

   toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
   toolbox.attr_bool, num_bits)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

註冊評估運算元：

toolbox.register("evaluate", eval_func)

現在，註冊交叉運算元：

toolbox.register("mate", tools.cxTwoPoint)

註冊變異運算元：

toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)

定義用於育種的運算元：

toolbox.register("select", tools.selTournament, tournsize = 3)
return toolbox
if __name__ == "__main__":
   num_bits = 45
   toolbox = create_toolbox(num_bits)
   random.seed(7)
   population = toolbox.population(n = 500)
   probab_crossing, probab_mutating = 0.5, 0.2
   num_generations = 10
   print('\nEvolution process starts')

評估整個種群：

fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
   ind.fitness.values = fit
print('\nEvaluated', len(population), 'individuals')

建立並迭代各代：

for g in range(num_generations):
   print("\n- Generation", g)

選擇下一代個體：

offspring = toolbox.select(population, len(population))

現在，克隆選定的個體：

offspring = list(map(toolbox.clone, offspring))

對後代應用交叉和變異：

for child1, child2 in zip(offspring[::2], offspring[1::2]):
   if random.random() < probab_crossing:
   toolbox.mate(child1, child2)

刪除子代的適應度值

del child1.fitness.values
del child2.fitness.values

現在，應用變異：

for mutant in offspring:
   if random.random() < probab_mutating:
   toolbox.mutate(mutant)
   del mutant.fitness.values

評估具有無效適應度的個體：

invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
   ind.fitness.values = fit
print('Evaluated', len(invalid_ind), 'individuals')

現在，用下一代個體替換種群：

population[:] = offspring

列印當前世代的統計資料：

fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print('Min =', min(fits), ', Max =', max(fits))
print('Average =', round(mean, 2), ', Standard deviation =',
round(std, 2))
print("\n- Evolution ends")

列印最終輸出：

   best_ind = tools.selBest(population, 1)[0]
   print('\nBest individual:\n', best_ind)
   print('\nNumber of ones:', sum(best_ind))
Following would be the output:
Evolution process starts
Evaluated 500 individuals
- Generation 0
Evaluated 295 individuals
Min = 32.0 , Max = 45.0
Average = 40.29 , Standard deviation = 2.61
- Generation 1
Evaluated 292 individuals
Min = 34.0 , Max = 45.0
Average = 42.35 , Standard deviation = 1.91
- Generation 2
Evaluated 277 individuals
Min = 37.0 , Max = 45.0
Average = 43.39 , Standard deviation = 1.46
… … … …
- Generation 9
Evaluated 299 individuals
Min = 40.0 , Max = 45.0
Average = 44.12 , Standard deviation = 1.11
- Evolution ends
Best individual:
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 
 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0,
 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Number of ones: 15

符號迴歸問題

這是遺傳程式設計中最著名的難題之一。所有符號迴歸問題都使用任意資料分佈，並嘗試使用符號公式擬合最準確的資料。通常，使用均方根誤差 (RMSE) 等度量來衡量個體的適應度。這是一個經典的迴歸問題，這裡我們使用方程5x³-6x²+8x=1。我們需要按照上述示例中的所有步驟進行操作，但主要部分是建立基本集，因為它們是各個體的構建塊，因此評估可以開始。這裡我們將使用經典的基本集。

以下 Python 程式碼詳細解釋了這一點：

import operator
import math
import random
import numpy as np
from deap import algorithms, base, creator, tools, gp
def division_operator(numerator, denominator):
   if denominator == 0:
      return 1
   return numerator / denominator
def eval_func(individual, points):
   func = toolbox.compile(expr=individual)
   return math.fsum(mse) / len(points),
def create_toolbox():
   pset = gp.PrimitiveSet("MAIN", 1)
   pset.addPrimitive(operator.add, 2)
   pset.addPrimitive(operator.sub, 2)
   pset.addPrimitive(operator.mul, 2)
   pset.addPrimitive(division_operator, 2)
   pset.addPrimitive(operator.neg, 1)
   pset.addPrimitive(math.cos, 1)
   pset.addPrimitive(math.sin, 1)
   pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
   pset.renameArguments(ARG0 = 'x')
   creator.create("FitnessMin", base.Fitness, weights = (-1.0,))
   creator.create("Individual",gp.PrimitiveTree,fitness=creator.FitnessMin)
   toolbox = base.Toolbox()
   toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
   toolbox.expr)
   toolbox.register("population",tools.initRepeat,list, toolbox.individual)
   toolbox.register("compile", gp.compile, pset = pset)
   toolbox.register("evaluate", eval_func, points = [x/10. for x in range(-10,10)])
   toolbox.register("select", tools.selTournament, tournsize = 3)
   toolbox.register("mate", gp.cxOnePoint)
   toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
   toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset)
   toolbox.decorate("mate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   toolbox.decorate("mutate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   return toolbox
if __name__ == "__main__":
   random.seed(7)
   toolbox = create_toolbox()
   population = toolbox.population(n = 450)
   hall_of_fame = tools.HallOfFame(1)
   stats_fit = tools.Statistics(lambda x: x.fitness.values)
   stats_size = tools.Statistics(len)
   mstats = tools.MultiStatistics(fitness=stats_fit, size = stats_size)
   mstats.register("avg", np.mean)
   mstats.register("std", np.std)
   mstats.register("min", np.min)
   mstats.register("max", np.max)
   probab_crossover = 0.4
   probab_mutate = 0.2
   number_gen = 10
   population, log = algorithms.eaSimple(population, toolbox,
      probab_crossover, probab_mutate, number_gen,
      stats = mstats, halloffame = hall_of_fame, verbose = True)

請注意，所有基本步驟與生成位模式時使用的步驟相同。此程式將在 10 代後為我們提供最小值、最大值和標準差 (std) 輸出。

列印頁面