一、介绍
遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法。它于1962年被提出, 直到1989年才最终形成基本框架[1]。它从初始种群出发, 采用“优胜劣汰, 适者生存”的自然法则选择个体, 并通过杂交、变异来产生新一代种群, 如此逐代进化, 直到满足目标为止[2]。
二、遗传算法的基本过程
(一) 基本过程
遗传算法的主要内容和基本步骤如下: (1) 选择编码策略。 (2) 定义遗传策略。 (3) 令t=0, 随机选择N个染色体初始化种群P (0) 。 (4) 定义适应度函数f (f>0) 。 (5) 计算P (t) 中每个染色体的适应度。 (6) t=t+1。 (7) 运用选择算子, 从P (t-1) 中得到P (t) 。 (8) 对P (t) 中的每个染色体, 按概率Pc参与交叉。 (9) 对染色体中的基因, 以概率Pm参与变异运算。 (10) 判断群体性能是否满足终止标准, 如不满足, 则返回5) 。
(二) 编码与解码
常用的遗传编码算法有二进制编码、格雷编码、实数编码和字符编码等[2]。对于函数优化问题, 一般采用两种编码方式。 (1) 二进制编码:将原问题结构变换为染色体的位串结构, 稳定性高。 (2) 实数编码:将每个体的染色体都用某一范围的一个实数来表示, 容易理解且不需要解码的过程。
(三) 适应度函数
适应度函数是一个对个体的适应性进行度量的函数。适应度函数值越大, 说明解的质量越高。常用的适应度函数有原始适应度函数和标准适应度函数[2]。
(四) 基本遗传操作
遗传算法中基本遗传操作包括选择、交叉和变异三种。
选择操作是在种群中选择优秀的个体, 并成为一对父母, 然后将它们的基因传递到下一代, 直到下一代个体数量达到种群数量上限。常用的选择策略有比例选择、排序选择和竞技选择[2]。交叉操作是按照某种方式对选择的父母根据交叉概率进行交配重组, 从而形成新的个体。通常采用单点交叉法, 即随机选择k位为交叉点, 单点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉。变异操作是对选中的个体的染色体中某些基因按照变异概率进行变动, 然后形成新的个体, 通常采用单点变异法。
三、函数最大值实验及结果分析
(一) 目标函数
我们将求解函数f (x) =x+10sin (6x) +12cos (x) 在区间[0, 10]的最大值。
(二) 定义各种策略及实验结果
首先, 我们设定求解的精度为小数点后4位, 然后将x的解空间划分为 (10) * (1e+4) =100000个等分。65536=2^16<100000<2^17=131072, 所以需要17位二进制数来表示这些解, 即这里染色体串的长度位17。其次, 使用f (x) 来表示该问题的适应度函数, 适应度函数值越大, 则解的质量越高。最后就是定义遗传策略, 这里我们设定交叉概率为0.6, 变异概率为0.05, 最大迭代次数为200。
测试结果如图1:
最优个体:00001011011100101;最优适应度:28.1421;最优个体对应自变量值:6.5394;达到最优结果需要的迭代次数:从21次到一百多次不等迭代次数与平均适应度关系曲线 (横轴:迭代次数, 纵轴:平均适应度) 。
(三) 结果分析
上述实验结果显示, 当迭代次数达到近21次左右时, 平均适应度会迅速上升并达到一个较为稳定的区域。然后, 随着迭代次数的进一步增加发现, 平均适应度会在这个稳定的区域上下波动但跨度不大, 并渐渐的保持在了一个水平值上。这时, 曲线达到了最优适应度, 也就是该种群基本达到了最佳适应水平。
(四) 改进方法
首先, 我们知道在种群刚开始迭代的时候因为需要增强种群的多样性, 所以变异概率通常会高一点, 当渐渐接达到了最优迭代次数时, 就需要稳定的发展下去, 这个时候的变异概率通常会很低, 所以我们可以对变异的概率进行动态确定, 这里可以使用类似于正态分布函数来表示变异概率随着迭代次数增加的变化趋势。
四、总结
在介绍了遗传算法的理论知识的基础上, 本文主要介绍了在函数最优解方面的应用并进行了简单的实验。遗传算法具有良好的全局搜索能力, 克服了传统算法容易陷入局部最优的缺点;但遗传算法也有一些不足的地方, 比如运行效率不高、编程实现的步骤较为复杂、局部搜索能力差而且容易早熟收敛, 对于这一点可以动态确定变异的概率或者改进选择的方式来优化。目前而言, 遗传算法并不是最完美的, 这些都是将来需要进一步研究的问题。
摘要：遗传算法遵守着物竞天择、适者生存的原则, 是人工智能领域中用于解决最优化的一种启发式搜索算法, 是进化算法的一种。发展至今已经得到了广泛的应用, 特别是在生产调度、神经网络、函数优化、模式识别等领域, 遗传算法都发挥了很大的作用。本文主要是通过实现函数优化方面的例子来体现遗传算法的实用价值以及从遗传算法的变异概率方面尝试了改进。
关键词：人工智能,遗传算法,函数优化
参考文献
[1] AlexYu.简单遗传算法MATLAB实现[M].
[2] 王万森.人工智能原理及其应用 (第三版) [M].电子工业出版社, 2014.
[3] (美) 米歇尔 (Mitchell, T.M.) 着, 曾华军等译.机器学习[M].机械工业出版社, 2008.
[4] 周志华.机器学习[M].清华大学出版社, 2016.