遗传算法

遗传算法详细操作教程

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

什么是遗传算法？

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

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

在GAs中，我们为给定问题提供了一系列可能的解决方案。这些解决方案然后经历重组和突变(如在自然遗传学中)，产生新的儿童，并且该过程在各代重复。每个个体(或候选解决方案)都被分配一个适应值(基于其目标函数值)，并且适合者个体被赋予更高的配偶并产生更适合个体的机会。这符合达尔文适者生存理论。

因此，它不断发展更好的个人或解决方案，直到达到停止标准。

遗传算法在本质上具有充分的随机性，但它们比随机局部搜索(我们只是尝试随机解决方案，追踪迄今为止最好的)的性能好得多，因为它们也在利用历史信息。

如何使用遗传算法优化问题？

优化是使设计，状况，资源和系统尽可能有效。以下框图显示了优化过程 -

遗传算法_https://bianchenghao6.com_【人工智能教程】_第1张

GA机制优化过程的阶段

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

第1步 - 随机生成初始群体。
第2步 - 选择具有最佳适应值的初始解决方案。
第3步 - 使用变异和交叉算子重组选定的解决方案。
第4步 - 将后代插入群体。
第5步 - 现在，如果停止条件得到满足，则返回具有最佳适应值的解。否则，请转到第2步。

安装必要的软件包

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

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
pip install deap

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

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
conda install -c conda-forge deap

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

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

生成位模式

以下示例显示了如何根据One Max问题生成一个包含15个字符串的位串。

如下所示导入必要的软件包 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
import random
 from deap import base, creator, tools

定义评估函数。这是创建遗传算法的第一步。

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
def eval_func(individual):
    target_sum = 15
    return len(individual) - abs(sum(individual) - target_sum)

现在，使用正确的参数创建工具箱 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
def create_toolbox(num_bits):
    creator.create("FitnessMax", base.Fitness, weights=(1.0,))
    creator.create("Individual", list, fitness=creator.FitnessMax)

初始化工具箱

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
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)

注册计算操作符 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
toolbox.register("evaluate", eval_func)

现在，注册交叉运算符 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
toolbox.register("mate", tools.cxTwoPoint)

注册一个可变运算符 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)

定义育种操作符 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
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')

评估整个人口 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
fitnesses = list(map(toolbox.evaluate, population))
 for ind, fit in zip(population, fitnesses):
    ind.fitness.values = fit
 print('\nEvaluated', len(population), 'individuals')

经过几代人的创建和迭代 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
for g in range(num_generations):
    print("\n- Generation", g)

选择下一代个人 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
offspring = toolbox.select(population, len(population))

现在，克隆选定的个人 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
offspring = list(map(toolbox.clone, offspring))

对后代应用交叉和变异 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
for child1, child2 in zip(offspring[::2], offspring[1::2]):
    if random.random() < probab_crossing:
    toolbox.mate(child1, child2)

删除孩子的适应值

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
del child1.fitness.values
 del child2.fitness.values

现在，应用突变 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
for mutant in offspring:
    if random.random() < probab_mutating:
    toolbox.mutate(mutant)
    del mutant.fitness.values

评估与无效的健身个体 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
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')

现在，用下一代个体替代人口 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
population[:] = offspring

打印当代人的统计数据 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
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")

打印最终输出 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
 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(均方根误差)这样的度量用于度量个体的适应度。这是一个经典的回归问题，这里我们使用方程:5x3-6x2 + 8x = 1。我们需要按照上述示例中的所有步骤进行操作，但主要部分是创建基元集，因为它们是个人的构建基块，因此可以开始评估。这里将使用经典的基元集。

以下Python代码详细解释了这一点 -

 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-26
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代后的输出为min，max，std(标准偏差)。

计算机视觉

AI强化学习