《基于Java实现的遗传算法》笔记（7 / 7）：个人总结

待我称王封你为后i 2022-09-16 04:52 33阅读 0赞

### 文章目录 ###

*  为何采用遗传算法
 *  哪些问题适合用遗传算法解决
 *  遗传算法基本术语
 *  一般遗传算法的过程
 *  基本遗传算法的伪代码

# 为何采用遗传算法 #

遗传算法是机器学习的子集。在实践中，遗传算法通常不是用来解决单一的、特定问题的最好算法。对任何一个问题，几乎总有更好的、更有针对性的解决方案！那么何必麻烦呢？

**遗传算法**是一个极好的多用途工具，可以应用于许多不同类型的问题。这是**瑞士军刀**与合适的螺丝刀之间的差异。如果任务是拧紧300颗螺丝，你会跳起来找螺丝刀。但如果任务是拧几颗螺丝、割开一些布、在皮革上打一个孔，然后打开一瓶冰苏打水奖励自己的努力工作，那么瑞士军刀是更好的选择。

此外，遗传算法是整体研究机器学习的不错入门。如果机器学习是一座冰山，遗传算法就是尖端的一部分。遗传算法有趣、令人兴奋且充满创新。遗传算法的模型基于自然生物过程，建立了计算世界和自然世界之间的连接。编写第一个遗传算法，观看从混乱和随机中出现的惊人结果，让人叹为观止。

机器学习冰山顶端的其他研究领域也同样令人兴奋，但它们往往关注的问题更狭窄，更难以理解。遗传算法则不然，它很容易理解，是有趣的实现，它们引入了所有机器学习技术都会使用的许多概念。

# 哪些问题适合用遗传算法解决 #

下面是一个问题特征列表，这类问题是采用遗传算法的良好候选者：

*  如果问题足够困难，难以写代码来解决；
 *  如果人不知道如何解决这个问题；
 *  如果问题是不断变化的；
 *  如果搜索每个可能解是不可行的；
 *  如果可以接受“足够好”的解。

# 遗传算法基本术语 #

遗传算法建立在生物进化的概念上的。

*  种群：这就是一个候选解（个体）集合，可以有变异和交叉这样的遗传操作应用于它们。
 *  候选解（个体）：给定问题的一个可能的解。
 *  基因：组成染色体的不可分割的构建块。经典的基因包含0或1。
 *  染色体：染色体是一串基因。染色体定义了一个特定的候选解（个体）。用二进制编码一个典型的染色体可能包含“01101011”这样的内容。
 *  变异：一个过程，其中候选解中的基因被随机改变，以创建新的性状。
 *  交叉：其中染色体被组合以创建新的候选解决方案的方法。这有时称为重组。
 *  选择：这是选择的候选解，繁殖下一代解的技术。
 *  适应度：一个评分，衡量候选解适合给定问题的程度。

# 一般遗传算法的过程 #

![在这里插入图片描述][e28150de09364818b2af13f70380b167.png_pic_center]

1.  遗传算法开始，初始化**候选解**（个体）的种群。这通常是随机提供整个搜索空间的均匀覆盖。涉及参数有种群规模。
2.  接下来，通过为种群中的每个个体分配一个适应度值，对种群进行评估。在这个阶段，常常要注意当前最优解，以及种群的平均适应度。
3.  评估后，根据终止条件集，该算法决定它是否应该终止搜索。通常这是因为该算法已达到指定的世代数量，或已经找到适当的解。
    
    1.  如果终止条件最终满足，算法会跳出循环，通常向用户返回最后的搜索结果。
    2.  一些典型的终止条件是：
        
         *  到达世代的最大数目;
         *  超过分配给它的时间;
         *  发现一个满足所需条件的解;
         *  该算法已经达到了一个稳定阶段。
4.  如果终止条件不满足，种群经过一个选择阶段，基于适应度评分，从种群中选择个体。适应度越高，个体就更有机会被选择。选择目的为下一步“交叉和变异”作准备。选择方法有：
    
     *  轮盘赌选择（也称为适应度比例选择）。个体的适应度越高，在轮盘上占据的空间就越多，也就是选中的概率越大。（参考第2章）
     *  锦标赛选择。随机从种群中选择一些个体，进入锦标赛。以通过比较这些个体的适应度值来竞争，然后选择适应度最高的个体作为亲代。（参考第3章）
5.  下一阶段对选择的个体应用交叉和变异。这个阶段为下一代创建新个体。如果是种群中的精英（种群中适应度最靠前的一小部分个体），直接跳过进入下一代。涉及参数有交叉率、变异率。交叉和变异后，确保仍然得到一个有效解（合格的个体）。
    
    1.  交叉方法有：
        
         *  均匀交叉（uniform crossover）。后代的每个基因都有50%的机会来自第一个亲代或其第二个亲代。（参考第2章）
         *  单点交叉。随机选择基因组中的一个位置，确定哪些基因来自于哪个亲代。交叉位置之前的遗传信息来自于亲代1，之后的遗传信息来自于亲代2。（参考第3章）
         *  排序交叉。在这种交叉方法中，第一个亲代染色体的一个子集被选中。然后该子集被添加到后代染色体的相同位置。下一步是将第二个亲代的遗传信息添加到后代的染色体中。通常从所选子集的结束位置开始，然后包括亲代2的每个基因，只要后代染色体中还没有该基因。（参考第4章）
6.  此时新种群返回到评估步骤（步骤2），过程重新开始。我们称这种循环的每一圈为一个世代。

# 基本遗传算法的伪代码 #

generation = 0;
    population[generation] = initializePopulation(populationSize);
    evaluatePopulation(population[generation]);
    while isTerminationConditionMet() == false do
        parents = selectParents(population[generation]);
        population[generation+1] = crossover(parents);
        population[generation+1] = mutate(population[generation+1]);
        evaluatePopulation(population[generation]);
        generation++;
    End loop;

[e28150de09364818b2af13f70380b167.png_pic_center]: /images/20220828/83ccf283f29f40f2b8342fd6708b1a6b.png