欢迎来到天天文库
浏览记录
ID:20448508
大小:288.64 KB
页数:7页
时间:2018-10-11
《matlab作业—遗传算法与优化问题》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、遗传算法与优化问题一、问题背景与实验目的遗传算法(GeneticAlgorithm—GA),是模拟达尔文的遗传选择和A然淘汰的生物进化过程的计算模型,它是由美国Michigan人7:的J.Holland教授于1975年首先提出的。遗传算法作为一种新的全局优化搜索算法,以其简肀通川、鲁棒性强、适于丼行处理及应用范围广等妯著特点,奠定了它作为21世纪关键智能计算之一的地位。1.遗传算法的基本原理遗传算法的基本思想正足基于校仿生物界遗传学的遗传过程。它把问题的参数川基因代表,把问题的解用染色体代表(在汁算机甩用二进制码表
2、示),从而得到一个由具柯不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争,适者冇敁好的机会生存和产生后代。后代随机化地继飧Y父代的最好特征,并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到闷题最优的解。值得注意的一点足,现在的遗传算法是受卞物进化论7:说的启发提出的,这种学说对我们用计算机解决复杂问题很有用,而它本身是否完全正确并不熏要(目侃生物界对此学说尚冇争议)。(1)遗传算法屮的生物遗传学概念山于遗传算法是山进化论和遗传学
3、机理而产牛.的直接搜索优化方注•,故而在这个算法中耍用到各种进化和遗传学的概念。首先给出遗传学概念、遗传算法概念和相应的数学概念三者之M的对戍关系。这些概念如卜、1个体——要处理的基本对象、结构,也就是可行解。2群体——个体的集合,被选定的一•组可行解。3染色体——个体的表现形式,可行解的编码。4基因——染色体屮的元素编码屮的元素。5基因位——某一基因在染色体屮的位置元素在编码屮的位H。6适应值——个体对于环境的适应程度,或在环境压力下的生存能力,可行解所对应的适应函数值。7种群——被选定的一组染色体或个体根据入选
4、概率定出的一组可行解。8选择——从群体中选择优胜的个体,淘汰劣质个体的操作保留或复制适应值大的可行解,去掉小的可行解。9交叉组染色体上对应基因段的交换,根据交叉原则产生的一组新解。io交叉概率——染色体对应基因段交换的概率(可能性大小),闭区间io,u上的一个值,一般为0.65〜0.90。11变异——染色体水平上基因变化编码的某些元素被改变。12变异概率——染色体上难因变化的概率(可能性大小),开区间(O,l)P、j的一个值,一般为0.001〜0.01。13进化——诂者生存个体进行优胜劣汰的进化,一代乂一代地优化目
5、标函数取到最大值,最优的可行解。(2)遗传算法的步骤遗传算法计算优化的操作过程就如同牛物学上生物遗传进化的过程,主要奋三个基本操作(或称为算子):选择(Selection)、交叉(Crossover)、变异(Mutation)。遗传算法基本步骤主要是:先把M题的解表示成“染色体”,在算法中也就是以二进制编码的串,在执行遗传算法之前,给出一群“染色体”,也就是假没的可行解。然后,把这些假设的可行解置于问题的“环境”屮,并按适者生存的原则,从屮选择出较适应环境的“染色体”进行fi制,冉通过交叉、变异过程产生更适应环境的
6、新一代“染色体”群。经过这样的一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是M题的最优解。下而给出遗传算法的具体步骤,流程阁参见閔h第一少:选择编码策略,把参数集合(可行解集介)转换染色体结构空间;第二步:定义适应函数,便于计算适应值;第三步:确定遗传策略,也括选择群体大小,选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数;第四步:随机产生初始化群体;第艽步:计算群体屮的个体或染色体解码后的适应位:第六步:按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体;第七步:判断群体
7、性能是否满足某一指标、或者是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步.阁1一个遗传算法的其体步骤遗传算法冇很多种具体的不同实现过程,以上介绍的是标准遗传算法的主要步骤,此算法会一直运行直到找到满足条件的最优解为止.1.遗传算法的实际应用例子:设f(xl,x2)=21.5+xl*sin(4pxl)+x2*sin(20px2),求maxf(xl,x2)。其中-3.0<=xl<=12.1,4.1<=x2<=5.8o注:这是一个非常简单的二元函数求极值的问题,相信大家都会做。在此我们要研究的
8、不是M题木:G,而是借此来说明如何通过遗传算法分析和解决M题。在此将细化地给出遗传算法的整个过程。(1)编码和产生初始群体首先第一少要确定编码的策略,也就是说如何把xl和x2在各fc
9、的区叫内的数用汁算机语言表示出来。编码就足表现型到基因型的映射,编码吋要注意以下三个原则:a完备性:问题空间中所有点(潜在解)都能成为GA编码空间中的点(染色体位中)的表现型;
此文档下载收益归作者所有