开发研究与设计技术
本栏目责任编辑：谢媛媛
遗传算法求解函数极值的应用
周丽
１，２
，张智顺
３
（１．湖南农业大学理学院信息科学系，湖南长沙４１０１２８；２．湖南师范大学数学与计算机科学学院，湖南长沙４１００８１；
３．贵州大学电子科学与信息技术学院，贵州贵阳５５０００３）摘要：通过用遗传算法求高等数学中的函数极值问题，说明了遗传算法对连续、可导等条件的放宽，同时，也体现了遗传算法在求解高等数学中函数极值的良好应用。
关键词：遗传算法；编码；选择；杂交；变异中图分类号：ＴＰ１８
文献标识码：Ａ
文章编号：１００９－３０４４（２００７）２１－４０８０２－０２
ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅＡｐｐｌｉｃａｔｉｏｎＦｕｎｃｔｉｏｎＥｘｔｒｅｍｕｍ
ＺＨＯＵＬｉ１，２，ＺＨＡＮＧＺｈｉ－ｓｈｕｎ３
（１．Ｈｕ＇ｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，Ｃｈａｎｇｓｈａ４１０１２８，Ｃｈｉｎａ；２．Ｈｕ＇ｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＣｈａｎｇＳｈａ４１００８１；
３．ＧｕｉｚｈｏｕＵｎｉｖｅｒｓｉｔｙｏｆＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅ，Ｇｕｉｙａｎｇ５５０００３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｂｙｕｓｉｎｇｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｆｏｒｈｉｇｈｅｒｍａｔｈｅｍａｔｉｃｓｏｆｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ，ｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｏｃｏｎｔｉｎｕｏｕｓ，ｄｅｒｉｖａｔｉｖｅａｎｄｏｔｈｅｒｃｏｎｄｉｔｉｏｎｓｒｅｌａｘｅｄ．ｉｔａｌｓｏｄｅｍｏｎｓｔｒａｔｅｄｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｔｈｅＨｉｇｈｅｒＭａｔｈｅｍａｔｉｃｓｆｕｎｃｔｉｏｎｅｘｔｒｅｍｕｍｇｏｏｄａｐｐｌｉｃａｔｉｏｎ．
ｋｅｙｗｏｒｄｓ：ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ；Ｃｏｄｉｎｇ；Ｃｈｏｉｃｅ；Ｈｙｂｒｉｄ；Ｖａｒｉａｔｉｏｎ
遗传算法（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ，简称ＧＡ）是根据自然
现象而提出来的一种随机搜界的“物竞天择，适者生存”索算法，是霍兰德（Ｈｏｌｌａｎｄ）于１９７５年在他的著作
中首次提出来《ＡｄａｐｔｉｏｎｉｎＮａｔｕｒａｌａｎｄａｒｔｉｆｉｃｉａｌＳｙｓｔｅｍｓ》
的。此算法将优化问题看作是自然界中生物的进化过程，通过模拟大自然中生物进化过程中的遗传规律，来达到寻优的目的。
根据达尔文的进化论，在生物进化的过程中，生物的发展进化主要有３个原因，即遗传、变异、和选择。遗传是指子代总是和亲代相似，变异却是指那些不相似的现象，选择是指具有精选的能力，它决定生物进化的方向，适者生存，不适者淘汰。
下面我们用一个实例来说明遗传算法的选择、杂交、变异的三个生物进化过程。
设函数ｆ（Ｘ）＝１８Ｘ－Ｘ＾２其中Ｘ为［０，１５］间的整数，求
此函数的最大值。
如果此问题用数学知识求解，很容易，如果把此函数看作是［０，１５］的连续函数的话，
此函数的图象就是一条开口向下的抛物线，对称轴为
如果是不连续，又不可导呢？那样，我数，十分容易解出。
们就可以用遗传达算法来解决，为了方便演示遗传算法的如果编码、作出适应函数、选择初始种群、选择、杂交、变异等过程，为方便起见，我现在还是以上面那个函数为例：
现在我们用遗传算法来解答：
１遗传编码
由于Ｘ的定义域是［０，１５］的整数，１５＜２＾４，所以可以用四位的二进制来表示此问题。如：００００表示Ｘ＝０，１１１１表示
Ｘ＝１５，其中０，１为基因，而此四位的二进制串就是染色体。
２做出适应函数
这里因为是求ｆ（Ｘ）的最大值，所以可以直接用ｆ（Ｘ）作为适应函数。
３选择初始种群
假设群体的规模Ｎ＝４，交配概率Ｐ＝１００％，变异概率Ｐ＝１％，且设初始群体为：１１１０、１００１、０１０１、００１１，则第为代群体的总体情况由下表１可知：
表１第０代情况表
Ｘ＝－ｂ／２ａ＝９，因此，最大值在Ｘ＝９处。
当然，也可以用求导的方法，先可出此函数的导数，再令导数为Ｏ，确定函数的极值点，但如果用求导的方法，须要求此函数可导。当然，这里因为是给出的初等函
收稿日期：２００７－０８－２０
作者简介：周丽（１９８０－），女，湖南郴州人，硕士研究生，研究方向为数理统计；张智顺（１９８０－），男，湖南郴州人，硕士研究生，研究方向为信息系统的研究与开发。
８０２
电脑知识与技术
本栏目责任编辑：谢媛媛
从上表中可知：最大适应值为８０，最小适应值为４５，平均值为５９．２５，适应值总和为２３７。
开发研究与设计技术
表３第０代变异情况表
４选择
根据生物进化论，适应度越强的，适应值越大，选择概率越大，越可能被选上，期望次数也越大，而选择概率越小的就越有可能被淘汰，所以表１的群体经选择后，染色体
１１１０被选择一次，染色体１０００被选择两次，染色体０１００被选择一次，而染色体００１１却被淘汰了。因此，得到第０代的种群为：１１１０、１０００、１０００、０１００
这样就可以得到新群体（第１代群体）。第１代群体为：在此群体下的选择情况如表４所示：
１１００、１０１０、１００１、０１００。
表４第１代情况表
５杂交
由于假定了交配概率是１００％，所以种群中所有的染色体都参与杂交。假定种群中的染色体是按顺序两两配对杂交。可得下表２：
表２第０代种群的交配情况表
从上表中可知：最大适应值为８１，最小适应值为５６，平均值为５９．２５，适应值总和为２８９。
此时，刚好是问题的适应函数的最大值，对应染色体为
１００１，故得到最优解为
Ｘ＝（１００１）的二进制为９。所以函数的最大值为８１。
经过交配后，新群体为：１１００、１０１０、１０００、０１００，其中最大的适应值仍为８０，没有发生变化，但平均适应值为７２，适应值总和为２８８。与第０代相比，最大适应值没有提高，平均适应值由６１．５提高到了７２，适应值总和由２３７提高到了
上述的交配到何时才能停止呢？一般可以通过规定的最大代数来定义，在达到了指定的进化代后，算法停止。或是如果经过连续进化后，得到的最优解没有任何变化，此时也可以停止交配。
通过上例求函数的极大值问题，说明了遗传算法是一种很好的方法，它可以不需要适应函数的连续性，可导性。放宽了高等数学中求极值时的条件。同时，经过编码后，只可见，遗传算法，在高数求解需做适应值的计算，操作简单。极值问题中发挥了良好的作用。
２８８。
我们可以发现，上面的群体：１１００、１０１０、１０００、０１００，不管怎么杂交都无法得到最后最后一位基因为１。因此，已经不可能通过交配达到最优解了。这种过早的陷入局部最优解的早熟现象。
６变异
扩大群体的规模可以防止早熟现象的发生，因此遗传算法一般要求具有一定的群体规模。变异也可以提高群体的多样性，从而为防止出现早熟起到一定的作用。比如：我们在表２所示的子代中染色体１０００的第四位基因发生变
异，变成为１００１，如表３所示：
（上接第８０１页）
参考文献：
［１］马少平，朱小燕．人工智能［Ｍ］．清华大学出版社，２００４．［２］曹承志．智能技术［Ｍ］．清华大学出版社，２００４．
［３］蔡自兴，徐光佑．人工智能及其应用［Ｍ］．清华大学出版社，２００４．
［４］朱福喜，杜友福．人工智能引论［Ｍ］．武汉大学出版社，２００６．
６结束语
本文给出了Ｔｉｍｅｒ控件的几种用法，起抛砖引玉的作用。Ｔｉｍｅｒ控件的作用还有待进一步挖掘。
Ｃａｓｅ４，５，６
Ｐ１．Ｐｉｃｔｕｒｅ＝ＬｏａｄＰｉｃｔｕｒｅ（＂绿灯．ｉｃｏ＂）ｆｂＴｈｅｎＴｉｍｅｒ２．Ｅｎａｂｌｅｄ＝ｂＥｎｄＳｅｌｅｃｔ
（１０）设置Ｔｉｍｅｒ２的Ｔｉｍｅｒ事件代码如下：
Ｉｆ（ａ＜４）Ａｎｄ（Ｐ２．Ｌｅｆｔ＞Ｐ１．ＬｅｆｔＡｎｄＰ２．Ｌｅｆｔ＜Ｐ１．Ｌｅｆｔ＋Ｐ１．Ｗｉｄｔｈ）ＯｒＰ２．Ｌｅｆｔ＜＝１００Ｔｈｅｎ
Ｔｉｍｅｒ２．Ｅｎａｂｌｅｄ＝ＦａｌｓｅＥｌｓｅ
Ｐ２．ＭｏｖｅＰ２．Ｌｅｆｔ－１０，Ｐ２．Ｔｏｐ，Ｐ２．Ｗｉｄｔｈ，Ｐ２．ＨｅｉｇｈｔＥｎｄＩｆ
运行程序即可完成信号灯指挥交通的功能。
参考文献：
［１］刘瑞新，文成林，汪远征．ＶｉｓｕａｌＦｏｘＰｒｏ程序设计教程［Ｍ］．机械工业出版社，２００４．８６－８９．
［２］龚沛曾，陆尉民，杨志强．ＶｉｓｕａｌＢａｓｉｃ程序设计简明教程［Ｍ］．高等教育出版社，２００１．１５４－１５６．
［３］张毅，王晓强，等．ＶｉｓｕａｌＢａｓｉｃ应用技巧与常见问题你问我答［Ｍ］．北京机械工业出版社，２００３．２０６－２１０．
［４］申石磊，张东生．ＶｉｓｕａｌＢａｓｉｃ程序设计［Ｍ］．中国科学技术出版社，２００７．３１－３２．
８０３
开发研究与设计技术
本栏目责任编辑：谢媛媛
遗传算法求解函数极值的应用
周丽
１，２
，张智顺
３
（１．湖南农业大学理学院信息科学系，湖南长沙４１０１２８；２．湖南师范大学数学与计算机科学学院，湖南长沙４１００８１；
３．贵州大学电子科学与信息技术学院，贵州贵阳５５０００３）摘要：通过用遗传算法求高等数学中的函数极值问题，说明了遗传算法对连续、可导等条件的放宽，同时，也体现了遗传算法在求解高等数学中函数极值的良好应用。
关键词：遗传算法；编码；选择；杂交；变异中图分类号：ＴＰ１８
文献标识码：Ａ
文章编号：１００９－３０４４（２００７）２１－４０８０２－０２
ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅＡｐｐｌｉｃａｔｉｏｎＦｕｎｃｔｉｏｎＥｘｔｒｅｍｕｍ
ＺＨＯＵＬｉ１，２，ＺＨＡＮＧＺｈｉ－ｓｈｕｎ３
（１．Ｈｕ＇ｎａｎＡｇｒｉｃｕｌｔｕｒａｌＵｎｉｖｅｒｓｉｔｙＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ，Ｃｈａｎｇｓｈａ４１０１２８，Ｃｈｉｎａ；２．Ｈｕ＇ｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＣｈａｎｇＳｈａ４１００８１；
３．ＧｕｉｚｈｏｕＵｎｉｖｅｒｓｉｔｙｏｆＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅ，Ｇｕｉｙａｎｇ５５０００３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｂｙｕｓｉｎｇｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｆｏｒｈｉｇｈｅｒｍａｔｈｅｍａｔｉｃｓｏｆｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ，ｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｏｃｏｎｔｉｎｕｏｕｓ，ｄｅｒｉｖａｔｉｖｅａｎｄｏｔｈｅｒｃｏｎｄｉｔｉｏｎｓｒｅｌａｘｅｄ．ｉｔａｌｓｏｄｅｍｏｎｓｔｒａｔｅｄｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｔｈｅＨｉｇｈｅｒＭａｔｈｅｍａｔｉｃｓｆｕｎｃｔｉｏｎｅｘｔｒｅｍｕｍｇｏｏｄａｐｐｌｉｃａｔｉｏｎ．
ｋｅｙｗｏｒｄｓ：ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ；Ｃｏｄｉｎｇ；Ｃｈｏｉｃｅ；Ｈｙｂｒｉｄ；Ｖａｒｉａｔｉｏｎ
遗传算法（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ，简称ＧＡ）是根据自然
现象而提出来的一种随机搜界的“物竞天择，适者生存”索算法，是霍兰德（Ｈｏｌｌａｎｄ）于１９７５年在他的著作
中首次提出来《ＡｄａｐｔｉｏｎｉｎＮａｔｕｒａｌａｎｄａｒｔｉｆｉｃｉａｌＳｙｓｔｅｍｓ》
的。此算法将优化问题看作是自然界中生物的进化过程，通过模拟大自然中生物进化过程中的遗传规律，来达到寻优的目的。
根据达尔文的进化论，在生物进化的过程中，生物的发展进化主要有３个原因，即遗传、变异、和选择。遗传是指子代总是和亲代相似，变异却是指那些不相似的现象，选择是指具有精选的能力，它决定生物进化的方向，适者生存，不适者淘汰。
下面我们用一个实例来说明遗传算法的选择、杂交、变异的三个生物进化过程。
设函数ｆ（Ｘ）＝１８Ｘ－Ｘ＾２其中Ｘ为［０，１５］间的整数，求
此函数的最大值。
如果此问题用数学知识求解，很容易，如果把此函数看作是［０，１５］的连续函数的话，
此函数的图象就是一条开口向下的抛物线，对称轴为
如果是不连续，又不可导呢？那样，我数，十分容易解出。
们就可以用遗传达算法来解决，为了方便演示遗传算法的如果编码、作出适应函数、选择初始种群、选择、杂交、变异等过程，为方便起见，我现在还是以上面那个函数为例：
现在我们用遗传算法来解答：
１遗传编码
由于Ｘ的定义域是［０，１５］的整数，１５＜２＾４，所以可以用四位的二进制来表示此问题。如：００００表示Ｘ＝０，１１１１表示
Ｘ＝１５，其中０，１为基因，而此四位的二进制串就是染色体。
２做出适应函数
这里因为是求ｆ（Ｘ）的最大值，所以可以直接用ｆ（Ｘ）作为适应函数。
３选择初始种群
假设群体的规模Ｎ＝４，交配概率Ｐ＝１００％，变异概率Ｐ＝１％，且设初始群体为：１１１０、１００１、０１０１、００１１，则第为代群体的总体情况由下表１可知：
表１第０代情况表
Ｘ＝－ｂ／２ａ＝９，因此，最大值在Ｘ＝９处。
当然，也可以用求导的方法，先可出此函数的导数，再令导数为Ｏ，确定函数的极值点，但如果用求导的方法，须要求此函数可导。当然，这里因为是给出的初等函
收稿日期：２００７－０８－２０
作者简介：周丽（１９８０－），女，湖南郴州人，硕士研究生，研究方向为数理统计；张智顺（１９８０－），男，湖南郴州人，硕士研究生，研究方向为信息系统的研究与开发。
８０２
电脑知识与技术
本栏目责任编辑：谢媛媛
从上表中可知：最大适应值为８０，最小适应值为４５，平均值为５９．２５，适应值总和为２３７。
开发研究与设计技术
表３第０代变异情况表
４选择
根据生物进化论，适应度越强的，适应值越大，选择概率越大，越可能被选上，期望次数也越大，而选择概率越小的就越有可能被淘汰，所以表１的群体经选择后，染色体
１１１０被选择一次，染色体１０００被选择两次，染色体０１００被选择一次，而染色体００１１却被淘汰了。因此，得到第０代的种群为：１１１０、１０００、１０００、０１００
这样就可以得到新群体（第１代群体）。第１代群体为：在此群体下的选择情况如表４所示：
１１００、１０１０、１００１、０１００。
表４第１代情况表
５杂交
由于假定了交配概率是１００％，所以种群中所有的染色体都参与杂交。假定种群中的染色体是按顺序两两配对杂交。可得下表２：
表２第０代种群的交配情况表
从上表中可知：最大适应值为８１，最小适应值为５６，平均值为５９．２５，适应值总和为２８９。
此时，刚好是问题的适应函数的最大值，对应染色体为
１００１，故得到最优解为
Ｘ＝（１００１）的二进制为９。所以函数的最大值为８１。
经过交配后，新群体为：１１００、１０１０、１０００、０１００，其中最大的适应值仍为８０，没有发生变化，但平均适应值为７２，适应值总和为２８８。与第０代相比，最大适应值没有提高，平均适应值由６１．５提高到了７２，适应值总和由２３７提高到了
上述的交配到何时才能停止呢？一般可以通过规定的最大代数来定义，在达到了指定的进化代后，算法停止。或是如果经过连续进化后，得到的最优解没有任何变化，此时也可以停止交配。
通过上例求函数的极大值问题，说明了遗传算法是一种很好的方法，它可以不需要适应函数的连续性，可导性。放宽了高等数学中求极值时的条件。同时，经过编码后，只可见，遗传算法，在高数求解需做适应值的计算，操作简单。极值问题中发挥了良好的作用。
２８８。
我们可以发现，上面的群体：１１００、１０１０、１０００、０１００，不管怎么杂交都无法得到最后最后一位基因为１。因此，已经不可能通过交配达到最优解了。这种过早的陷入局部最优解的早熟现象。
６变异
扩大群体的规模可以防止早熟现象的发生，因此遗传算法一般要求具有一定的群体规模。变异也可以提高群体的多样性，从而为防止出现早熟起到一定的作用。比如：我们在表２所示的子代中染色体１０００的第四位基因发生变
异，变成为１００１，如表３所示：
（上接第８０１页）
参考文献：
［１］马少平，朱小燕．人工智能［Ｍ］．清华大学出版社，２００４．［２］曹承志．智能技术［Ｍ］．清华大学出版社，２００４．
［３］蔡自兴，徐光佑．人工智能及其应用［Ｍ］．清华大学出版社，２００４．
［４］朱福喜，杜友福．人工智能引论［Ｍ］．武汉大学出版社，２００６．
６结束语
本文给出了Ｔｉｍｅｒ控件的几种用法，起抛砖引玉的作用。Ｔｉｍｅｒ控件的作用还有待进一步挖掘。
Ｃａｓｅ４，５，６
Ｐ１．Ｐｉｃｔｕｒｅ＝ＬｏａｄＰｉｃｔｕｒｅ（＂绿灯．ｉｃｏ＂）ｆｂＴｈｅｎＴｉｍｅｒ２．Ｅｎａｂｌｅｄ＝ｂＥｎｄＳｅｌｅｃｔ
（１０）设置Ｔｉｍｅｒ２的Ｔｉｍｅｒ事件代码如下：
Ｉｆ（ａ＜４）Ａｎｄ（Ｐ２．Ｌｅｆｔ＞Ｐ１．ＬｅｆｔＡｎｄＰ２．Ｌｅｆｔ＜Ｐ１．Ｌｅｆｔ＋Ｐ１．Ｗｉｄｔｈ）ＯｒＰ２．Ｌｅｆｔ＜＝１００Ｔｈｅｎ
Ｔｉｍｅｒ２．Ｅｎａｂｌｅｄ＝ＦａｌｓｅＥｌｓｅ
Ｐ２．ＭｏｖｅＰ２．Ｌｅｆｔ－１０，Ｐ２．Ｔｏｐ，Ｐ２．Ｗｉｄｔｈ，Ｐ２．ＨｅｉｇｈｔＥｎｄＩｆ
运行程序即可完成信号灯指挥交通的功能。
参考文献：
［１］刘瑞新，文成林，汪远征．ＶｉｓｕａｌＦｏｘＰｒｏ程序设计教程［Ｍ］．机械工业出版社，２００４．８６－８９．
［２］龚沛曾，陆尉民，杨志强．ＶｉｓｕａｌＢａｓｉｃ程序设计简明教程［Ｍ］．高等教育出版社，２００１．１５４－１５６．
［３］张毅，王晓强，等．ＶｉｓｕａｌＢａｓｉｃ应用技巧与常见问题你问我答［Ｍ］．北京机械工业出版社，２００３．２０６－２１０．
［４］申石磊，张东生．ＶｉｓｕａｌＢａｓｉｃ程序设计［Ｍ］．中国科学技术出版社，２００７．３１－３２．
８０３