遗传算法基本原理及其C、VC源程序 [转]

来源：互联网   发布日期：2011-08-29 21:34:44   浏览：14677次  

一：简介

　　遗传算法起源于上个世纪60年代，那时的研究大多将注意力放在对自然系统的模拟之上。1975年美国的Holland教授与其同事、学生研究形成了一个完整的理论和方法，由Holland教授提出的遗传算法现在一般称之为基本遗传算法(Simple Genetic Algorithm)，经过其后的40多年的发展，遗传算法已经形成一个庞大的体系，在人工智能、模式识别、组合优化、智能控制等领域得到广泛的应用。

　　遗传算法的特点是采用简单的编码技术来表示各种复杂的结构，通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。算法从一组随机产生的初始群体开始搜索过程，以适应度函数为依据，采用基于适应值比例的选择策略在当前种群中选择个体，通过杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。

二：算法原理

　　遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自适应全局概率搜索算法。在解决具体问题时先大致确定问题的潜在解的一个集合，这个集合就是算法的初始种群。种群由计算机生成（一般是随机生成）的一定数目的个体组成，个体就是潜在解的计算机编码，那么我们最后要求的解就由这些初始生成的个体进化而来。每个个体具有其自的特征（携带不同基因），我们根据这些个体的不同的特征来确定其存活到下一代的可能性高低，按照优胜劣汰的法则，我们由父代来产生子代，如此来繁衍。当然在具体的进化过程中为了保持种群多样性防止过早收敛，还要在其中使个体以一定小概率发生变异。这样在最后满足收敛条件后的种群最优个体就是问题的近似最优解。

　　遗传算法的实现过程主要包括编码、产生群体、计算适应度、复制、交换、变异等操作。概括地讲，遗传算法求解组合优化问题的具体步骤可描述如下：

　　(1) 根据具体问题，选择编码方式，随机产生初始群体，个体数目一定，每个个体表示为染色体的基因编码；
　　(2) 选择合适的适应度函数，计算并评价群体中各个体的适应度；
　　(3) 选择(selection)：根据各个个体的适应度，按照一定的规则或方法，从当前群体中选择出一些优良的个体遗传到下一代群体。
　　(4) 交叉(crossover)：将选择过后的群体内的各个个体随机搭配成对，对每一对个体，以一定概率(交叉概率)交换它们中的部分基因。
　　(5) 变异(mutation)：对交叉过后的群体中的每一个个体，以某个概率(称为变异概率)改变某一个或某一些基因位上的基因值为其他的等位基因。
　　(6) 终止条件判断。若满足终止条件，则以进化过程中得到的具有最大适应度的个体作为最优解输出，终止运算；否则，迭代执行(2) - (5)步。

　　适应度是评价群体中染色体个体好坏的标准，是算法进化的驱动力，是自然选择的唯一依据，改变种群结构的操作皆通过适应度函数来控制。在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，被遗传到下一代的概率就越大；相反，被遗传到下一代的概率就越小。在进化过程中，遗传算法除适应度外不再需要其它信息，也不需要适应度函数满足连续可微，唯一要求是针对输入可计算出能加以比较的结果。

三：基本遗传算法函数优化及其源程序

　　由于函数优化问题比较简单，而且也能比较好的反映算法的本身效能，所以普遍地被用于算法测试。我们用如下的算法来做测试：

　　f(x) =x sin( 10 pi x ) + 2.0

　　函数图像如下：

　　上图为函数在区间［-2.0,3.0］的曲线，可以看到函数在［-1,2.0］内有多处极值。

　　编制基本遗传算法(SGA)程序求解上述函数在区域[-1.0,2.0]的全局最大值。我们采用二进制编码，随机产生初始种群，适应度函数取函数体本身。取种群大小为50，染色体长度为22(精度为6位小数)，交叉概率为0.6，变异概率为0.02，迭代100代。独立运行5次，绘制种群最大适应度(函数最优解)平均曲线值如下图：

　　由图可以看出遗传算法可以有效地跳出局部最优值且收敛速度较快，程序运行30代左右即可得到最大值3.850274，与实际最大值相差不大，可以作为问题的全局最优解。

四：程序源代码及相关下载

　　C语言程序在Dev-Cpp下编译通过，不过里面函数大部分都是自己写的，在VC下面应当也可以编译通过，VC版的程序在WinXP+VC 6.0下编译通过，不过程序包中都已经包含有编译好的可执行文件。程序运行后会在本目录下生成一个名为SGAReport.txt的文件，这是算法运行过程中每一代的信息。

　　SkyDrive下载：

　　http://cid-ade735cf80ea4224.skydrive.live.com/browse.aspx/SGA

　　另外一个空间用的是千脑的网盘，所以不能直接右击下载，你需要单击打开另处一个下载页才能下载，不过测试了下，速度应当还不错。

　　http://www.qiannao.com/space/list/6lines/上传分享/SGA/.page

赞助本站