遗传算法优化问题求解

2023-06-28 理论教育版权反馈

【摘要】：遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。遗传算法之所以具备强大的搜索能力，是因为包罗了选择、杂交和变异三种基本操作算子，同时这三种操作算子也是模拟自然生物圈中自然存在的有性繁殖、杂交和变异等现象的核心载体。同样，遗传算法中起核心作用的是遗传操作的交叉算子。通过交叉，遗传算法的搜索能力得以飞跃提高。图11-1遗传算法流程图

遗传算法（genetic algorithm，GA）最早是由美国的John Holland于20世纪70年代提出，该算法是根据大自然中生物体进化规律而设计提出的。作为一种启发式算法，遗传算法不需要所求解问题的解空间连续可微分，该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。该算法在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

遗传算法之所以具备强大的搜索能力，是因为包罗了选择、杂交和变异三种基本操作算子，同时这三种操作算子也是模拟自然生物圈中自然存在的有性繁殖、杂交和变异等现象的核心载体。遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的，这种随机化操作是高效有向和传统的随机无向搜索方法是有区别的。

（1）选择

从群体中选择优胜个体、淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproduction operator）。选择的目的是把优化的个体（或解）直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。

（2）交叉

在自然界生物进化过程中起核心作用的是生物遗传基因的重组（加上变异）。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

（3）变异

变异算法的基本内容是对群体中的个体串的某些基因座上的基因值作变动。遗传算法引入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力，当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏；二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象，此时收敛概率应取较大值。

变异算法的运算过程（图11-1）大体如下：

①将待解决问题的约束与优化目标等参数编码到染色体中，形成问题参数与染色体的对应关系，构成染色体编码空间；

②根据问题的参数设定恰当的适应度函数；

③设置进化过程中的相关操作算子，主要有交叉算子、变异算子、选择算子等；

④根据问题确定合适的遗传算法参数，包含种群规模、交叉概率、变异概率等参数；

⑤生成初始种群P（0）；

⑥对种群P（0）中的所有个体进行适应度函数值计算；

⑦判断种群是否满足算法终止条件，若满足条件则输出该种群中适应度值最高的个体；如果不满足算法终止条件，则继续后续的操作过程；

⑧对种群P（0）进行选择、交叉、变异运算，产生新的种群P（1）；

⑨重复步骤⑥、⑦、⑧产生种群P（t），直至满足算法终止条件。

pagenumber_ebook=268,pagenumber_book=252