遗传算法优化函数.doc

《遗传算法优化函数.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法优化函数05372128梁少华05级计算机B班1引言遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。霍兰德（Holland）于1975年在他的著作《AdaptationinNaturalandArtificialSystems》首次提出遗传算法，并主要由他和他的学生发展起来的。生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过

2、个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。　　遗传算法自从1975年提出以来，在国际上已经形成了一个比较活跃的研究领域，已召开了多次比较重要的国际会议和创办了很多相关的国际刊物。遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等.函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的

3、函数优化问题，用其他优化方法较难求解，用遗传算法可以方便地得到较好的结果。2问题求解3初始化假设种群大小为100.确定染色体由两部分基因组成:前半部分为x1的值,后半部分为x2的值.然后随机产生由100个染色体组成的群体.4计算适应函数值利用适应值函数:计算出每一个染色体的适应值Vi.5选择求出群体的总适应值F,然后用单个染色体的适应值Vi除以总适应值F得到每个染色体的选择概率Pi.进而求得每个染色体的累积概率Ci.最后用转轮盘方法选择群体后代:用计算机产生一个的随机数，如果它介于Ci和Ci+1的累积概率之间，就选择Ci+1复制到下一代。6交叉接着对新的染色体进行交叉操作。值得注意的是，在

4、一代中并不是所有的个体都需要参与交叉配对，相反地算法往往只选择其中的一部分进行遗传学上的改变。决定染色体进行交叉与否的概率称为交叉概率。设，我们分别为100个染色体产生对应的100个的随机数，如果随机数小于0.6，则选择该染色体进行交叉.将选中的染色体两两配对，并交换染色体的前半部分基因(即x1的值,这与交换后半部分x2的值是完全等效的).7变异对这一种群执行变异操作。具体方法是为每个染色体的每一部分基因产生一个的随机数，如果这个数小于变异概率，则对应基因发生变异(即重新随机产生x1或x2的值)。在本例中，设置变异概率pm=0.001。8循环至此，我们已经完成了遗传算法中的一代，初始种群通

5、过选择，交叉和变异算子的作用产生了下一代的种群。我们再计算一次种群中所有染色体的适应值,继续根据此适应值进行选择、交叉和变异，可以产生第三代种群。遗传算法不断循环这一过程,在第1000代得到的最好染色体值为38.232717679.9具体程序实现.前提：程序假充种群大小为100，进化代数为1000，交叉率为0.5，变异率为0.001。编码：每个染色体的编码用一个含有两个元素的数组表示，数组的第一个元素为x1，第二个元素为x2.初始化：从文件中读取x1和x2的取值范围，并在此取值范围内随机产生每一个染色体的编码以及进行相关的初始化.种群保存在数组population中，population的

6、最后一个元素始终保存着适应值最大的染色体。为了保证程序在每次运行时都有不同的初始化群体，符合自然现象，加入代码srand((unsigned)time(NULL))，因为时间每次运行都不相同，所以产生的随机数也不同.计算：计算出每一个染色体的适应值population[i].fitness=21.5+x[1]*sin(4*PI*x[1])+x[2]*sin(20*PI*x[2]);.然后找出适应值最大的染色体，并保存在数组population的最后一个元素中,并用前一代的最大适应值染色体替换当代适应值最差的染色体.选择：按照轮盘方法选择种群的新后代.交叉：以Pc=0.5为交叉率，分别为10

7、0个染色体产生对应的100个的随机数，如果随机数小于0.5，则选择该染色体进行交叉.将选中的染色体两两配对，并交换染色体的前半部分基因(即x1的值,这与交换后半部分x2的值是完全等效的).如果选择的染色体为偶数则直接交叉，如果为奇数，则掉弃最后一个选择的染色体.变异：以Pm=0.001为每个染色体数组的每一个元素产生一个的随机数，如果这个数小于变异概率，则对应元素发生变异(即重新随机产生x1或x2的值)。输出：输出当代的