一、实验题目
求解线性约束优化问题的遗传算法
将物品由7个起运站运到7个目的地;已知由i站运到j地的单位运费是,表示i站的供应量,表示j地的需求量,表示从i站到j地的运量。 (i, j =1,2,…,7)
约束条件:
目标函数为:
罚函数为:
其中,k=1,P=1/14,f为第t代群体的平均适应度,T为最大运行代数,为约束的违反度。
费用参数表如下:
使用策略:通用遗传算法模型、精英保存策略、轮盘赌法策略选择个体交叉和变异,对上述例子进行了算法的测试,种群个体大小为40,迭代10000次,得到比较稳定的结果。每次运行的结果是得到一个相对稳定的、代价小的目标值。实验结果:在当前条件下,在初始种群的40个个体,经过10000次迭代得到最低运费为1279,并且程序多次运行结果都稳定在1300左右。
二、实验环境
操作系统:Microsoft Windows XP Professional
软件:Microsoft Visual C++ 6.0
三、实验设计原理
1. 实验内容分析
本实验采用遗传算法求解带约束条件的函数优化问题。
2. 遗传算法的思想
生物的进化是以集团为主体的。与此相对应,遗传算法的运算对象是由M个个体所组成的集合,称为群体。与生物一代一代的自然进化过程相类似,遗传算法的运算过程也是一个反复迭代过程,第t代群体极为P(t),进过一代遗传和进化后,得到第t+1代群体,他们也是由多个个体组成的集合,记做P(t+1)。这个群体不断地经过遗传和进化操作,并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代,这样最终在群体中将会得到一个优良的个体X,它所对应的表现性X将达到或接近于问题的最优解。
3. 算法实现步骤
①产生初始种群:产生初始种群的方法通常有两种:一种是完全随机的方法产生的,适合于对问题的解无任何先验知识的情况;另一种是将某些先验知识转变为必须满足的一组要求,然后在满足这些要求的解中再随机地选择样本,t=0,随机产生n个个体形成一个初始群体P(t),该群体代表优化问题的一些可能解的集合;
②适应度评价函数:按编码规则,将群体P(t)中的每一个个体的基因码所对应的自变量取值代入目标函数,算出其函数值,i=1,2,…,n,越大,表示该个体有较高的适应度,更适合于f所定义的生存环境,适应度为群体进化提供了依据;
③选择:按一定概率从群体P(t)中选出m个个体,作为双亲用于繁殖后代,产生新的个体加入下一个群体P(t+1)中;
④交叉(重组):对于选中的用于繁殖的每一个个体,选择一种交叉方法,产生新的个体;
⑤变异:以一定的概率从群体P(t+1)中随机选择若干个个体,对于选中的个体,进行变异;
⑥对产生新一代的群体返回步骤③再进行评价,交叉、变异如此循环往复,使群体中个体的适应度和平均适应度不断提高,直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高,则迭代过程收敛,算法结束。
4. 算法流程图
5. 实验调试与结果分析(问题的发现、分析、解决方案与创新)
1) 程序结果如下图:
2) 收敛效果如下图:
四、实验小结及附录
通过本次实验,我了解了演化计算的基本思想,并能够运用演化计算的思想解决函数最优值问题,能够编写相应的程序。实验过程中遇到很多问题,但是进过认真分析,最终能解决问题。