完成模拟退火遗传算法.doc

袆膀蒈蒆螂腿膈蚂蚈膈芀蒄羆芇莃蚀袂芆蒅蒃螈芅膅蚈蚄袂莇蒁蚀袁葿螇罿袀腿蕿袅衿芁螅螁袈莄薈蚇袇蒆莀羅羇膆薆袁羆芈荿螇羅蒀薄螃羄膀蒇虿羃节蚃羈羂莄蒅袄羁蒇蚁螀羁膆蒄蚆肀艿虿薂聿莁蒂袁肈肁蚇袇肇芃薀螃肆莅螆虿肅蒈薈羇肅膇莁袃肄芀薇蝿膃莂莀蚅膂肂薅薁膁芄莈羀膀莆蚃袆膀蒈蒆螂腿膈蚂蚈膈芀蒄羆芇莃蚀袂芆蒅蒃螈芅膅蚈蚄袂莇蒁蚀袁葿螇罿袀腿蕿袅衿芁螅螁袈莄薈蚇袇蒆莀羅羇膆薆袁羆芈荿螇羅蒀薄螃羄膀蒇虿羃节蚃羈羂莄蒅袄羁蒇蚁螀羁膆蒄蚆肀艿虿薂聿莁蒂袁肈肁蚇袇肇芃薀螃肆莅螆虿肅蒈薈羇肅膇莁袃肄芀薇蝿膃莂莀蚅膂肂薅薁膁芄莈羀膀莆蚃袆膀蒈蒆螂腿膈蚂蚈膈芀蒄羆芇莃蚀袂芆蒅蒃螈芅膅蚈蚄袂莇蒁蚀袁葿螇罿袀腿蕿袅衿芁螅螁袈莄薈蚇袇蒆莀羅羇膆薆袁羆芈荿螇羅蒀薄螃羄膀蒇虿羃节蚃羈羂莄蒅袄羁蒇蚁螀羁膆蒄蚆肀艿虿薂聿莁蒂袁肈肁蚇袇肇芃薀螃肆莅螆虿肅蒈薈羇肅膇莁袃肄芀薇蝿膃莂莀蚅膂肂薅薁膁芄莈羀膀莆蚃袆膀蒈蒆螂腿膈蚂蚈膈芀蒄羆芇莃 完成“模拟退火遗传算法”，试验结果良好作者：佚名 文章来源：本站原创 点击数： 797 更新时间：2004-5-15研究背景：遗传算法在运行早期个体差异较大，当采用经典的轮盘赌方式选择，后代产生个数与父个体适应度大小成正比，因此在早期容易使个别好的个体的后代充斥整个种群，造成早熟；在遗传算法后期，适应度趋向一致，优秀的个体在产生后代时，优势不明显，从而使整个种群进化停滞不前。由我前面测试过的预选择算法看出，算法很快就收敛。因此对适应度适当地拉伸是必要的。引进模拟退火算法，在温度高时（遗传算法前期），适应度相近的个体产生的后代概率相近；而当温度不断下降后，拉伸作用加强，使适应度相近的个体适应度差异放大，从而使得优秀的个体优势更明显。模拟退火算法简介：经过一个晚上研究模拟退火算法解决TSP代码，我总结一下模拟退火算法的基?本思想。模拟退火算法的核心思想与热力学的原理颇为相似，本质在于对物质缓慢地制冷以争取充足的时间，让大量原子在丧失可动性之前进行重新分布。从算法的结构上看出，大致分为以下几个步骤：1、构造数学模型2、定义目标函数（在遗传算法中可定义为适应度函数）3、确定控制参数（温度、能量）4、计算代价（假设进行某种操作之后所付出的代价）5、预测这种代价，看看是否需要对被分析的对象重新构造（在遗传算法里面就是要?看看是否需要进行交叉操作）6、改变温度7、重复试验具体实现c语言代码：1、定义关键变量：doublescale_fitness;/*适应度拉伸值*/doubletemperature;/*染色体所在温度*/structindividual*cospop;/*代价种群*/doubleT;/*当前温度*/doubleT0;/*初始温度*/doubleTFACTOR;/*温度下降系数*/doublede;/*代价值*/intans;/*判断是否需要交叉*/intnumT;/*试验的温度数*/intcurT;/*当前温度试验数*/2、定义关键函数：voidscalefitness();/*拉伸适应度函数*/doublesumofscalefitness();/*拉伸适应度值求和*/intmetrop(double,double);/*Metroplis算法*/3、关键函数实现：/将原本的适应度值fi拉伸为：exp(fi/T)/sumof(exp(fi/T)voidscalefitness()intj=0;sumofscale_fitness=sumofscalefitness();for(j=0;jpopsize;j+)oldpopj.scale_fitness=exp(oldpopj.fitness)/T)/sumofscale_fitness;/若代价0，重构概率为exp(-de/t)intmetrop(doublep_de,doublep_T)if(p_de0)return(1);elseif(flip(exp(-1)*p_de/p_T)return(1);elsereturn(0);/计算代价de=cospopj.fitness-fmin(oldpopmate1.fitness,oldpopmate2.fitness);/预测ans=metrop(de,T);/经过试探性的交叉之后以及由预测判断完毕，可以确定是否真的需要重构（交叉）if(ans)/*需要重构*/newpopj.fitness=cospopj.fitness;newpopj.temperature=T;newpopj.varible=cospopj.varible;for(k=0;kchromsize;k+)newpopj.chromk=cospopj.chromk;else/*不需要重构*/newpopj.fitness=oldpopmate1.fitness;newpopj.scale_fitness=oldpopmate1.scale_fitness;newpopj.temperature=T;newpopj.varible=oldpopmate1.varible;for(k=0;kchromsize;k+)newpopj.chromk=oldpopmate1.chromk;试验结果：由于模拟退火算法需要慢慢地调整结构，在试验中一共尝试100次温度变化，每一种温度下繁衍200代，初始化温度为1度。温度每次下降10。最后在第68代获得了自我开始研究遗传算法优化解以来的最优解：3.850373。曾经在自适应算法中在第38代获得了3.850274，但无论怎样改变交叉率和变异率都未突破这个瓶颈。采用模拟退火算法得到的最优解比以往我研究过的5种遗传算法解要理想得多。俗?话说“慢工出细活”，我想用在这里最合适不过了。虽然基本遗传算法收敛比模拟退火慢在第96代方找出最优解3.850274，但能获得3.850373这个优解是很难达到了，除非采用大规模的种群结构或生成代数吧。关于模拟退火遗传算法还在继续优化中，下一步将会更改一些具体的参数，看看参数对试验结果会有什么影响。文章录入：邀月共饮责任编辑：邀月共饮 上一篇文章： 五子棋算法 下一篇文章： C+的BP算法源程序【字体：小 大】【发表评论】【告诉好友】【打印此文】【关闭窗口】 袈肀蒄蚃蚁肆蒃蒃羆羂肀薅蝿袈聿蚇羄膇肈莇螇肃肇葿羃罿膆薂螆袅膅蚄薈膃膅莄螄腿膄薆薇肅膃蚈袂羁膂莈蚅袇膁蒀袀膆膀薂蚃肂艿蚅衿羈艿莄蚂袄芈蒇袇螀芇虿蚀腿芆荿羅肅芅蒁螈羁芄薃羄袆芃蚆螆膅莃莅蕿肁莂蒈螅羇莁薀薈羃莀荿螃衿荿蒂蚆膈莈薄袁肄莇蚆蚄羀莇莆袀袆蒆蒈蚂膄蒅薁袈肀蒄蚃蚁肆蒃蒃羆羂肀薅蝿袈聿蚇羄膇肈莇螇肃肇葿羃罿膆薂螆袅膅蚄薈膃膅莄螄腿膄薆薇肅膃蚈袂羁膂莈蚅袇膁蒀袀膆膀薂蚃肂艿蚅衿羈艿莄蚂袄芈蒇袇螀芇虿蚀腿芆荿羅肅芅蒁螈羁芄薃羄袆芃蚆螆膅莃莅蕿肁莂蒈螅羇莁薀薈羃莀荿螃衿荿蒂蚆膈莈薄袁肄莇蚆蚄羀莇莆袀袆