Artificial Intelligence With Python 简明教程
AI with Python – Genetic Algorithms
本章详细讨论了人工智能的遗传算法。
What are Genetic Algorithms?
遗传算法 (GA) 是基于自然选择和遗传学概念的基于搜索的算法。GA 是计算的一个更大分支的子集，称为进化计算。
GA 由 John Holland 及密歇根大学的学生和同事（最著名的是 David E. Goldberg）开发的，此后已在各种优化问题上进行尝试，并获得了高度成功。
在 GA 中，针对给定的问题有一组可能的解决方案。然后，这些解决方案经过重新组合和变异（就像自然遗传中一样），产生新的子代，并且该过程会重复进行多代。每个个体（或候选解决方案）被分配一个适应度值（基于其目标函数值），并且适应度较高的个体更有可能配对并产生子个体。这与达尔文的进化论相符。
因此，它会在多代中保留适应度更好的个体或解决方案，直到达到停止条件。
遗传算法在本质上是足够随机的，但它们的性能比随机局部搜索（我们只尝试随机解决方案，跟踪到目前为止的最佳解决方案）好得多，因为它们也利用了历史信息。
Installing Necessary Packages
为了使用 Python 中的遗传算法解决问题，我们将使用一个名为 deap 的强大 GA 软件包。它是一个新颖进化计算框架的库，用于快速原型制作和测试创意。我们可以借助命令提示符上的以下命令安装此软件包 -
pip install deap如果您使用的是 iPython 环境，则可以使用以下命令安装 deap -
conda install -c conda-forge deapImplementing Solutions using Genetic Algorithms
本节将向您解释使用遗传算法实现解决方案的方法。
Generating bit patterns
以下示例向您展示如何生成一个位字符串，该字符串将基于 0-1 背包问题包含 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: 15Symbol Regression Problem
它是遗传规划中最著名的问题之一。所有符号回归问题都使用任意数据分布，并尝试用符号公式拟合最准确的数据。通常，像均方根误差 (RMSE) 这样的度量用于衡量个体的适应度。这是一个经典的回归器问题，我们这里使用方程式 5x3-6x2+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) 作为输出。