欢迎浏览我公司网站!!
行业资讯
优化算法2--遗传算法(原理)
时间: 2024-05-13浏览次数:
?遗传算法是一种随机全局优化算法。它的灵感来自通过自然选择的生物进化理论。具体来说,是将对遗传学的理解与理论结合起来的新的综合。与人工神经网络一样,它是最受欢迎和最广为人知的生物启发算法之一。该算法是一种进化算法,以?遗传重组?和?遗传突变?为基础,利用?二元表示?和简单?算子?的自然选择,根据生物进化理论(适者生存)进行优化。该算法使用类似的遗传表示(位串)、适应度(函数计算)、

?遗传算法是一种随机全局优化算法。它的灵感来自通过自然选择的生物进化理论。具体来说,是将对遗传学的理解与理论结合起来的新的综合。

与人工神经网络一样,它是最受欢迎和最广为人知的生物启发算法之一。

该算法是一种进化算法,以?遗传重组?和?遗传突变?为基础,利用?二元表示?和简单?算子?的自然选择,根据生物进化理论(适者生存)进行优化。

该算法使用类似的遗传表示(位串)、适应度(函数计算)、遗传重组(位串的交叉)和变异(翻转位)。

该算法首先创建一个固定大小的随机位串的总体。算法的主循环重复固定次数的迭代,或者直到在给定次数的迭代中,在最佳解决方案中看不到进一步的改进。

算法的一次迭代就像进化的一代

  • 首先,使用目标函数计算位串(候选解)的填充。将每个候选解的目标函数评价作为解的适应度,可最小化或最大化。

  • 然后,根据适应度选择父母。一个给定的候选解决方案可能被用作零次或多次父解决方案。

一种简单有效的?选择方法?是从种群中?随机?抽取个?候选者,并从适应度最好的群体中选择成员。这称为?竞赛选择,其中是一个?超参数,并设置为一个值,例如3。这个简单的方法模拟了一个更昂贵的适合度比例选择方案。

在竞赛选择中,每个亲本都是种群中随机选择的条染色体中最适合的。

父母是产生?下一代?候选点数的基础,群体中的每个位置都需要一对父母。

然后让父母成双成对地生两个孩子。重组使用交叉操作符进行。这包括在位串上选择一个?随机的分裂点,然后创建一个子串,其中包含从第一个父节点到分裂点的位,以及从第二个父节点到字符串末尾的分裂点的位。然后,这个过程对第二个子节点进行反转。

具体流程会在下面介绍。

基本?术语

  1. 种群(population):它是给定问题的所有可能(编码)解决方案的子集。GA的种群与人类的种群类似。

  2. 染色体(Chromosomes):一个染色体就是解决这个问题的一个解

  3. 基因(Gene):基因是染色体的一个位置元素

  4. 等位基因(Allele):一个基因为一个特定的染色体所取的

  5. 基因型(Genotype):基因型是计算空间中的总体。在计算空间中,解以一种易于理解和使用计算系统操作的方式表示。

  6. 表现型(Phenotype):表现型是现实世界解决方案空间中的群体,在这个空间中,解决方案以现实世界情景中的方式表示。

  7. 解码和编码(Decoding and Encoding):对于简单的问题,表型和基因型空间是相同的。然而,在大多数情况下,表型和基因型空间是不同的。解码是从基因型到表现型空间的转化过程,编码是从表现型到基因型空间的转化过程。译码速度要快,因为遗传算法在计算适应度值时要反复进行译码

  8. 适应度函数(Fitness Function):简单定义的适应度函数是以解为输入,以解的适用性为输出的函数。在某些情况下,适应度函数和目标函数可能是相同的,而在另一些情况下,适应度函数和目标函数可能根据问题的不同而不同。

  9. 基因算子(Genetic Operators):改变后代的基因组成。这包括交叉、变异、选择等。

自然选择的过程是从群体中选择最适合的个体开始的。它们产生的后代继承了父母的特征,并将遗传给下一代。如果父母有更好的健康状况,他们的后代就会比父母更好,有更好的生存机会。这个过程不断迭代,最终会找到最适合的个体

这个概念可以应用于搜索问题。我们考虑一个问题的一组解,并从中选择一组最好的解。

遗传算法流程如下图所示:

? ? ? ? ? ? ? ? ? ? ?

?

1 种群初始化

这个过程从一组被称为种群的个体开始。每个个体是想要解决的问题的一个解决方案。个体的特征是一组称为基因的参数(变量)。基因被连接成一串,形成染色体(解决方案)。

在遗传算法中,个体的一组基因是用一串字母表示的(位串)。通常使用二进制值(1和0组成的字符串)。染色体中的编码基因:

?

2 适应度函数?

适应度函数决定了个体的适合度(个体与其他个体竞争的能力)。它给每个个体一个适合度评分。一个个体被选择繁殖的概率是基于它的适合度分数。

3 选择?

选择阶段的想法是选择最适合的个体,让他们把自己的基因传给下一代。

两对个体(父母)被选择基于他们的适合度得分。适应度高的个体被选择繁殖的机会更大。

4 交叉

交叉是遗传算法中最重要的阶段。对于每一对要交配的父母来说,交叉点是从基因中随机选择的。

例如,考虑交叉点为3,如下所示:

? ? ? ? ? ? ?

?

这被称为单点交叉,还有许多其他的算子变体。

后代是通过父母之间的基因交换而产生的,直到达到交叉点。

? ? ? ? ? ? ? ? ? ? ?

?新的后代被添加到种群中。

? ? ? ? ? ? ? ? ? ? ? ? ?

?

交叉被概率地应用于每一对父代,这意味着在某些情况下,父代的副本被作为子代,而不是重组操作符。交叉由设置为较大值的超参数控制,例如80%或90%。

交叉是遗传算法的显著特征。它涉及到将父母双方的部分混合和匹配来形成孩子。如何进行混合和匹配取决于个体的表现。

5 变异

在某些新形成的后代中,他们的一些基因可能会以低随机概率发生突变。突变涉及到在创建的孩子候选解决方案中翻转比特。通常情况下,变化率设置为1/L,其中L为位串的长度。

? ? ? ? ? ? ? ? ? ? ?

?

突变的发生是为了保持种群内的多样性,防止过早收敛。

6 终止

如果种群已经收敛(没有产生与上一代显著不同的后代),则算法终止。可以说,遗传算法已经为我们的问题提供了一套解决方案。

种群数量是固定的。随着新一代的形成,最不适合的个体会死亡,为新一代提供空间。

这个阶段的顺序重复的,以在每一代中产生比上一代更好的个体。

优点:

  1. 与传统方法相比,速度更快,效率更高。

  2. 具有很好的并行能力。

  3. 可同时优化连续和离散函数以及多目标问题。

  4. 提供一个好的解决方案列表,而不仅仅是一个单一的解决方案。

  5. 总能找到问题的答案,随着时间的推移会变得更好。

  6. 当搜索空间很大且涉及大量参数时非常有用。

缺点:

  1. 算法并不适用于所有的问题,特别是那些简单的、可以得到导数信息的问题。

  2. 适应度值是反复计算的,这对于某些问题可能是计算昂贵的。

  3. 由于是随机的,所以不能保证解的最优性或质量。

  4. 如果执行不当,遗传算法可能无法收敛到最优解

参考:

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm

?


Copyright © 2002-2022 盛煌-盛煌娱乐-盛煌全球注册认证站 版权所有

粤IP*******

平台注册入口