遗传算法求解函数优化问题的比较

遗传算法求解函数优化问题的比较

多极值点函数具有多个极值，对此问题，传统的优化技术很容易陷入局部最优解，求得全局优化解的概率不高，可靠性低；为此，建立尽可能大概率的求解全局优化解算法是求解函数优化的一个重要问题。

遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传制）演化而来的随机搜索和优化方法，是当今影响最广泛的进化计算方法之一，是进化计算理论体系的中心。遗传算法借鉴了物种进化的思想，将欲求解问题编码，把可行解表示成字符串形式。初始化随机产生一个种群，用合理的评价函数对种群进行评估，在此基础上进行选择、交叉及变异等遗传操作。选择算子根据父代中个体适值大小进行选择或淘汰，它保证了算法的最优搜索方向。交叉算子模拟基因重组及随机信息交换，产生更好个体，使其在可行域内有效搜索。变异算子模拟基因突变，保证了遗传算法的全局搜索能力。遗传算法的搜索能力主要由选择算子及交叉算子赋存，变异算子尽可能保证算法达到全局最优，避免陷入局部最优。

遗传算法中的各个模块如下所示 1、编码

将数据进行二进制编码，其规则如下：设某一参数的取值范围为（L,U），使用长度为k的二进制编码表示该参数，则它共有2k种不同的编码。该参数编码时代对应关系为

00000000000000=0->L 00000000000001=1->L+Δ 00000000000010=2->L+2Δ 00000000000011=3->L+3Δ ……

11111111111111=2k-1->U

2、解码

解码的目的是为了将不直观的二进制数据串还成十进制。是编码过程的逆过程。 3、初始种群

随机产生k位的0、1排列，将该排列数来表示一个染色体，每个染色体代表一个初始值。初始种群就是随机产生数量为群体规模的染色体。 4、选择

这里选择轮盘赌方法，轮盘赌选择又称适应度比例选择方法，是最常见也是最为著名的选择方法，由Holland 教授提出。基本原理是根据个体适应值的比例来确定个体的选择概率，是一个随机采样的过程。为了防止当前群体的最优个体在下一代发生丢失，导致遗传算法不能收敛到全局最优解，引入了精英选择策略。 5、杂交

假设个体A和B被选择进行杂交。首先在个体中随机选择一个交配区域，如随机产生一个1到k的数，在个体A、B在该随机数后的染

色体进行交换。如

交换前

A：00000111|110000 B：01100000|001111

交换后

A：00000111|001111 B：01100000|110000

6、变异

为了避免在算法迭代后期出现种群过早收敛，对于二进制的基因码组成的个体种群，实行基因码的小概率翻转，对于二进制编码即0变成1，而1变成0。例如个体01100000001111的第2个位发生变异，则个体变为00100000001111. 7、个体适应度评估

遗传算法利用个体的适应度函数搜索基本不利于外部信息的因素，在算法设计时，适应度函数决定系统是否能寻找到系统最优解。由目标函数变换而成的适应度函数在设计时应考虑一下几个因素：适应度函数是否能反映解的优劣，该函数是否是单值的和非负的，只有满足以上因素才能设计出合理的算法。对于函数优化问题，适应度可取为函数值。 8、复制

将子代复制为父代。

遗传算法的步骤如下所示：

begin t<-0

初始化P(t) 评价P(t)

while(终止条件不满足) do begin

杂交P(t)以产生C(t) 变异C(t) 评价C(t)

从P(t)和C(t)中选择P(t+1) t<-t+1 end end

函数y=x.*sin(10*pi*x)+2的图像如下图所示：