|
|
摘 要：自从霍兰德于1915年在他的著作《Adaption im Natural and artificial Systems》中首次提出遗传算法以来，经过了近30年的研究，现在已经发展到了一个比较成熟的阶段，并且在实际中得到了很好的应用。为了更好的了解遗传算法，本文通过最简单的一个手工计算实例来还原遗传算法的全过程。
【关键词】：遗传算法 生物进化 染色体 种群
自然界的生物进化是按“适者生存，优胜劣汰”规律进行的，而遗传算法就是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性，这是一种全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定。
遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串(称为染色体)，即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。
遗传算法主要步骤：
（1）编码：由于遗传算法不能直接处理解空间的数据，必须通过编码将它们表示成遗传空间的基因型串结构数据。
（2）选择初始种群 ：随机产生N个初始串结构数据，每个串结构数据称为一个个体，也称为染色体，N个个体体构成了一个种群。
（3）选择适应度函数：遗传算法在搜索过程中一般不需要其他外部信息或知识，仅用适应度函数来评价个体的适应度。
（4）选择：利用选择概率再随机的选择个体和复制数量。选择算子的设计可依据达尔文适者生存的进化论原则，选择概率大的被选中的机会较多。
（5）杂交：对被选中的个体进行随机配对并随机的选择基因交换位，交换基因后产生新的个体，全体新个体构成新的（下一代）种群。
（ ）变异：变异操作是按位进行求反，对二二进制编码的个体而言，就是对随机选中的某位进行求反运算，即“0”变“1”，“1”变大“0”。
（1）一代种群 通过遗传，即选择、杂交和变异产生下一代种群 。新种群又可重复上述的选择、杂交和变异的遗传过程。
为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。
求下述二元函数的最大值：
Max f(x1,x2)= x12+ x22
S,t,x1∈{1,2,3,4,5, ,1}
x2∈{1,2,3,4,5, ,1}
(1) 个体编码
遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数来表示。因 x1, x2 为 0 ~ 1之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的 位无符号二进制数就形成了个体的基因型，表示一个可行解。例如，基因型 X＝101110 所对应的表现型是：x＝[5， ]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。
(2) 初始群体的产生
群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。
如：011101，101011，011100，111001
(3) 适应度汁算
目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接用目标函数值作为个体的适应度。
(4) 选择运算
我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：
1.先计算出群体中所有个体的适应度的总和? fi( i=1.2,…,M )；
2.fi其次计算出每个个体的相对适应度的大小 fi /，它即为每个个体被遗传到下一代群体中的概率，
3.每个概率值组成一个区域，全部概率值之和为1；
4.最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。
(5） 交叉运算
我们采用单点交叉的方法，其具体操作过程是：
1.先对群体进行随机配对；
2.其次随机设置交叉点位置；
3.最后再相互交换配对染色体之间的部分基因。
由此可以看出，其中新产生的个体111101、111011的适应度较原来两个个体的适应度都要高。
( )? 变异运算
我们采用基本位变异的方法来进行变异运算，其具体操作过程是：
1.首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；
2.然后依照某一概率将变异点的原有基因值取反。
对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。
从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体111111。
总的来说，遗传算法一般应用于在一个问题的解集中查找最优解情况，如是一个问题有多个答案，但是想查找一个最优答案的话，那么使用遗传算法可以达到更快更好的效果。目前，遗传算法已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
参考文献：
[1]李敏强，寇纪淞，林丹，李全书，《遗传算法的基本理论与应用》，科学出版社，200 .
[2]玄光男，程润伟，《遗传算法与工程优化》，清华大学出版社，2003.
[3]张琛，詹志辉，《遗传算法选择策略比较》，计算机工程与设计，2009 第23期.
作者简介：
朱小宝，男 工作单位：南昌航空大学飞行器工程学院，研究生学历，软件工程专业毕业， 目前讲师职称。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
转载注明来源:http://www.ybaotk.com |
上一篇：高职公共计算机课程改革探析下一篇：关于信息环境下如何做好机关档案工作的几点思考
|
发表于 2020-5-29 00:03:46
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
QQ登录
