AI与Python - 遗传算法

本章详细讨论了AI的遗传算法.

什么是遗传算法？

遗传算法(GA)是基于搜索的算法关于自然选择和遗传学的概念. GA是一个更大的计算分支的子集，称为进化计算.

GAs由John Holland及其密歇根大学的学生和同事开发，最着名的是David E. Goldberg .从那以后，它已经尝试了各种优化问题并取得了很大的成功.

在GA中，我们有一组可能的解决方案来解决给定的问题.然后这些溶液经历重组和突变(如在天然遗传学中)，产生新的儿童，并且该过程重复多代.为每个个体(或候选解决方案)分配适合度值(基于其目标函数值)，并且使得更健康的个体具有更高的交配和产生钳工个体的机会.这符合达尔文的最适合生存的理论.

因此，它保持不断发展更好的个人或解决方案代代相传直到它达到停止标准.

遗传算法本质上是充分随机的，但它们比随机局部搜索表现更好(我们只是尝试随机解决方案，跟踪最好的因此因为他们也利用历史信息.

如何使用GA进行优化问题？

优化是一种设计，情况的动作，资源和系统，尽可能有效.下面的框图显示了优化过程 :

用于优化过程的GA机制的阶段

以下是用于优化问题的GA机制的一系列步骤.

• 步骤1 : 随机生成初始人口.

• 步骤2 : 选择具有最佳适合度值的初始解决方案.

• 步骤3 : 使用突变和交叉算子重新组合选定的解决方案.

• 步骤4 : 将后代插入人群中.

• 步骤5 : 现在，如果满足停止条件，则返回具有最佳适合度值的解决方案.否则转到第2步.

安装必要的软件包

使用遗传来解决问题在Python中的算法，我们将使用功能强大的GA包 DEAP .它是一个新的进化计算框架库，用于快速原型设计和思想测试.我们可以在命令提示符下使用以下命令安装此软件包 :

pip install deap

如果您使用 anaconda 环境，则可以使用以下命令安装deap :

conda install -c conda-forge deap

使用遗传算法实现解决方案

本节介绍使用遗传算法实现解决方案.

生成位模式

以下示例说明如何生成包含15个位的位串，基于 One Max 问题.

导入必要的包，如下所示 :

import randomfrom 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 toolboxif __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 = fitprint('\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.valuesdel 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 = fitprint('Evaluated', len(invalid_ind), 'individuals')

现在，用下一代个体和减号替换人口;

population[:] = offspring

打印当前世代的统计数据 :

fits = [ind.fitness.values[0] for ind in population]length = len(population)mean = sum(fits) / lengthsum2 = sum(x*x for x in fits)std = abs(sum2 / length - mean**2)**0.5print('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 startsEvaluated 500 individuals- Generation 0Evaluated 295 individualsMin = 32.0 , Max = 45.0Average = 40.29 , Standard deviation = 2.61- Generation 1Evaluated 292 individualsMin = 34.0 , Max = 45.0Average = 42.35 , Standard deviation = 1.91- Generation 2Evaluated 277 individualsMin = 37.0 , Max = 45.0Average = 43.39 , Standard deviation = 1.46… … … …- Generation 9Evaluated 299 individualsMin = 40.0 , Max = 45.0Average = 44.12 , Standard deviation = 1.11- Evolution endsBest 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 operatorimport mathimport randomimport numpy as npfrom deap import algorithms, base, creator, tools, gpdef division_operator(numerator, denominator):   if denominator == 0:      return 1   return numerator / denominatordef 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 toolboxif __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代之后给出输出为min，max，std(标准偏差).