| 3.4本文算法整体流程
本算法采用文 中的擂台法（arena’s principle，AP）来作为选择评价算子，对于交叉算子和变异算子都采用文献 中所定义的方法。算法采用擂台法来得到Pareto解，该算法也是构造Pareto解或非支配解的快速算法 ，也是遗传算法的适应度评价方法。本算法也采用新的效率很高的检验Pruefer数的可行性准则，对于m个工厂n个仓库的运输问题，只要满足下列条件之一则该Prüfer数就是可行的 ：
(1) Pruefer数(P)中出现的工厂节点的总个数等于n-1
(2) Pruefer余数(CP)中出现的仓库节点总个数等于m-1
令P（t）是当前t代时的抗体种群，C（t）是当前t代产生的抗体，PSet（t）是当前t代为止产生的Pareto解集。
新算法流程如下：
Begin
 ;
随机初始化可行的P（t）;
根据构造生成树T算法 、运输量的变异算法和AP算法从P（t）得PSet（t）;
While 终止条件不满足 do
Begin
重组P（t）得C（t）;
根据构造生成树T算法、运输量的变异算法和AP算法从P（t）和C（t）更新PSet（t）;
基于浓度选择的群体更新，从P（t）和C（t）中选择出P（t+1）;
 ;
end
end
最终得到的PSet（t）便是Pareto边界PF。
4 算例及结论
本文算法采用Visual Studio 2005(C#语言)实现，硬件环境为PC (Pentium IV 3.0 GHz C内存:2G).
4.1 算例一
现有8家工厂、9家仓库，工厂的供应量为：a = (10, 8, 12, 16, 21, 15, 7, 9)，和需求量为：b = (9, 7, 15, 10, 13, 16, 7, 10, 11)。算例拥有两个成本矩阵，如下：
算法中的参数设置：pop_size=50，max_gen=10000，run=5。
上图是上面相同参数下三种算法的结果比较。”圆点”代表st-GA，即基于Pruefer树的遗传算法，该算法是采用贪婪法的运输分配方案。”矩形点”代表Fuzzy-GA，是在st-GA的基础上采用fuzzy规则来对运输量进行模糊分配。”菱形点”代表本文 Lam-GA算法结果，得到了更好的结果。如：(207,207)。而且明显看出取得了很好的Pareto前沿面。
4.2 算例二
算例二的规模较大，设有18家工厂，19家仓库，工厂供应量为a=(27, 38, 35, 24, 12, 29, 37, 42, 56, 36, 42, 40, 60, 22, 19, 38, 66, 48)，仓库的需求量为b=(42, 30, 37, 19, 36, 46, 45, 37, 24, 46, 38, 23, 29, 45, 62, 18, 30, 28, 36)。该算例的成本矩阵如下：
 
算法中的参数设置：pop_size=120,max_gen=5000,run=5次。
 上图和前面算例一样。”圆点”代表st-GA，即基于Pruefer树的遗传算法，该算法是采用贪婪法运
输分配方案。”矩形点”代表Fuzzy-GA，是在st-GA的基础上采用fuzzy规则来对运输量进行模糊分配。”菱形点”代表本文Lam-GA算法结果。从图可以明显看出，对于大规模算例，本文中的算法取得了很好的Pareto前沿面和Pareto解。
本文提出的新的Lam-GA算法，采用了新的可行性判断方法，具有更快的收敛速度和更强的收敛性，在保持供应平衡的基础上对运输量进行局部变异，提高了解的精度。通过加入免疫思想中抗体浓度控制，使得Pareto解的分布性更加均匀。
References (参考文献)
[1] Zou Shurong and Zhong Hongwei, Fuzzy-GA and Multi-Objective Transportation ptimization, IEEE International Conference cis-ram .270-273，9，2008
[2] Michalewicz. Z, Genetic Algorithm + Data Structure = Evolution Programs,3rd. edition, Springer-Verlag, New York, 1996
[3] Michalewicz. Z, G. A. Vignaux and M. Hobbs, A non-standard genetic algorithm for the nonlinear transportation problems, ORSA Journal of computing, vol. 3, no.4, 307-316, 1991
[4] Gen,M. and Y. Li,Spanning tree-based genetic algorithm for bicriteria fixed charge transportation problem, in proceeding of the Congress on Evolutionary Computation, PP.2265-2271 Washington, DC,1999
[5] Gen,M. and R. Cheng, Genetic Algorithm and Engineering Optimization, J Wiley&Sons, Inc, 20004
[6] 多目标进化算法及其应用[M] 郑金华 科学出版社 2007
[7] 自然计算、机器学习与图像理解前沿[M] 焦李成 公茂果等 西安电子科技出版社 2008
[8]Feng Zhongtian and Zou Shurong , Improvement of the Algorithm to Determine the Feasibility of the Prüfer Number, IEEE International Conference on Natural Computation(2009)
[9] J. Jang, C. Sun and E. Mizutani, Neuro-Fuzzy and Soft Computation, Prentice Hall, 1997
[10] Das Indraned etal, A Closer look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems, Structural Optimization, 14(1),63-69, 1997
[11] 人工免疫系统[M] 莫宏伟 左兴权 科学出版社 2009
[12] 免疫进化理论与应用[M] 杨孔雨 社会科学文献出版社 2008
2/2 首页 上一页 1 2 |
