概述
遗传算法(Genetic Algorithm, GA)是一种基于自然选择和遗传学原理的优化算法,广泛应用于搜索和优化问题。其基本原理可以总结如下:
1、编码(Encoding):
将解决方案表示为染色体(Chromosomes),通常是字符串或数组。每个染色体包含若干基因(Genes),基因可以是二进制位、实数或其他适合问题的表示方法。
2、初始种群(Initial Population):
随机生成一定数量的染色体作为初始种群。种群规模通常对算法性能有显著影响。
3、适应度函数(Fitness Function):
为每个染色体定义一个适应度函数,用于衡量其在解决问题上的优劣。适应度函数的设计直接影响算法的效果。
4、选择(Selection):
根据适应度值选择染色体进行繁殖,适应度高的染色体有更大概率被选中。常用的选择方法包括轮盘赌选择(Roulette Wheel Selection)、锦标赛选择(Tournament Selection)等。
5、交叉(Crossover):
通过交叉操作将两个染色体(父代)组合生成新的染色体(子代)。常用的交叉方法包括单点交叉(Single-point Crossover)、两点交叉(Two-point Crossover)和均匀交叉(Uniform Crossover)等。
6、变异(Mutation):
以一定概率对染色体中的基因进行随机修改,以引入多样性并防止算法陷入局部最优解。变异操作有单点变异(Single-point Mutation)、多点变异(Multi-point Mutation)等。
7、进化(Evolution):
经过选择、交叉和变异操作后,生成新一代种群。新一代种群将替代旧种群,并重复上述过程直到满足终止条件,如达到最大迭代次数或找到满意的解。
8、终止条件(Termination Condition):
算法通常在满足某些条件时终止,如达到预定的迭代次数、适应度值达到某个阈值或种群中个体的多样性不足。
遗传算法通过模拟自然选择和遗传机制,能够有效地在大搜索空间中找到近似最优解,特别适用于复杂的、非线性、多峰值优化问题。
算法基本流程
![](https://i-blog.csdnimg.cn/direct/61bfa4d81142481b8a8dabc32166f976.png)
遗传算法中的精英主义(elitism)
为什么要选择精英主义策略?
尽管遗传算法群体的平均适应度通常随着世代的增加而增加,但在任何时候都有可能失去当代的最佳个体。这是由于选择、交叉和变异运算符在创建下一代的过程中改变了个体。在许多情况下,丢失是暂时的,因为这些个体(或更好的个体)将在下一代中重新引入种群。但是,如果要保证最优秀的个体总是能进入下一代,则可以选用精英主义策略。
方法
这意味着,在我们使用通过选择、交叉和突变创建的后代填充种群之前,将前n个个体(n是预定义参数)复制到下一代。复制后的的精英个体仍然有资格参加选择过程,因此仍可以用作新个体的亲本。
结果
Elitism策略有时会对算法的性能产生重大的积极影响,因为它避免了重新发现遗传过程中丢失的良好解决方案所需的潜在时间浪费。
小生境与共享
什么是小生境与共享?
由于遗传算法的趋势是找到全局最大值,因此一段时间后大多数个体集中在最高峰附近。在图2中通过使用×标记的位置表示这一点,×代表了当前代的个体。
![](https://i-blog.csdnimg.cn/direct/89931efea9794ec9b3f8e8801c5a09a0.png)
但是有时,除了全局最大值外,我们还希望找到其他部分(或全部)峰值。为此,可以将每个峰视为小生境,以与其高度成比例的方式提供资源。
然后,找到一种在占用资源的个体之间共享(或分配)这些资源的方法,理想情况下,这将促使物种进行相应的分配,最高峰会吸引最多的人,因为它提供的奖励最多,而其他峰由于提供较少的奖励而相应减少物种数量(如图3所示)。
![](https://i-blog.csdnimg.cn/direct/e7dc6eb29b6a431db2711407c7d50b7e.png)
参考:
超详细的遗传算法(Genetic Algorithm)解析 - upstreamL - 博客园 (cnblogs.com)