·94- 智能系统学报 第4卷 表2SGA、GGA和UGA的实验结果比较 问题的特点，结合局部搜索技术，提出了新的解决图 Table 2 Experien tal result of SGA,GGA and UGA 二划分问题的混合遗传算法，克服了佳点集遗传算 问题 算法Nc 0 法中佳点选取不带随机性的缺点，实例仿真得出的 SGA 60 6312293 51.31 结果表明了新算法的有效性和先进性.今后的工作 Queen5 5 GGA 60 60681.85 11.48 是进步分析该方法的深层次的数学基础以及该方法 RGA 60 6000000 1.40 在组合优化问题中的有效性和先进性， SGA 83 9401 590 149.72 David GGA 82 91.08 477 6263 参考文献： RGA 82 87.88 3.26 2396 [1]KANG S J,MOON B R.A hybrid genetic algorithm or SGA 14 35.20 994 13819 multiway graph partitoning [C]//Proc Genetic Evolu- Miles250 GGA 18 47.14 13.57 6534 tionary Computation Conf(GECCO-2000).San Francisco, RGA 4 1030 420 2089 USA:Morgan Kaufann,2000:159-166 SGA 49551568218115619 [2 ]HENDR CKSON B,KOLDA T G Graph partitioning mod- Queen10 10 GGA 50051564 292 47.90 els for parallel computing[J]Parallel Compute,2000,26 RGA 49549500000 376 (12):1519-1534 SGA1188127920420917473 [3张铃，张钱.遗传算法机理的研究[J]软件学报， Queen1313GGA1232013642047.0712579 2000,11(7):945-952 RGA10921092301.711874 ZHANG Ling,ZHANG Ba Research on the mechanis of SGA193020663057.4417608 genetic algorithms[J].Joumal of Sofware,2000,11(7): Queen1515GGA2148226480324412358 945-952 RGA168016853011741537 [4]张铃，张钱.佳点集遗传算法[J]计算机学报， 2001,24(9):917-922 ZHANG L ing ZHANG Ba Good point set based genetic 其中：SGA为简单遗传算法；GGA为佳点集遗 algorithm [J ]Chinese Joumal of Computers,2001,24 传算法；RGA为基于随机化均匀设计的混合遗传算 (9):917-922 法.算法参数为：群体规模为100交叉和变异概率： [5华罗庚，王元.数论在近似分析中的应用M]北京 P。=09,Pm=005:最大迭代代数为200算法中惩 科学出版社，1978 [6]SOPER A J,WALSHAW C,CROSS M.A combined evolu- 罚系数： tionary search and multilevel optm ization approach o graph r=1.)I max(1.)n. partitioning[J]Joumal of Gbbal Opti ization,2000,29 (2):225-241 n为顶点个数；当(max|y,l,|2)-n/2)≤5时 [7正兆军，张润楚.均匀设计抽样的偏差[J]数学物理 u=0,否则u=1为避免遗传算法的随机性，对每个 学报，1997,17(2)：207-217 标准算例在同一台机器上进行连续100次计算，记 WANG Zhaojun,ZHANG Runchu Descrpency of unifm 录如下结果： desingn sampling[J].Acta Mathematica Scientia,1997,17 (2):207-217. 1)100次运行中求得的最好解记为Ne)和 [8 ]WALSHAW C.The graph partitioning archive EB/OL ] 100次运行所得解的平均值记为Ve;2)100次运 [2008-04-15 ]http:/staftweb ans gre ac uk/~wc06/ 行求得解的标准差记为·；3)100次运行中每次 partition/. 收敛时代数的平均值记为N) 作者简介 由表2可以得出：随机化均匀设计混合遗传算 周本达，男，1974生，副教授.主要 法每次得到的解均好于简单遗传算法和佳点集遗传 研究方向为遗传算法、多Agent系统.发 表学术论文10余篇 算法：而且在解的平均值、平均收敛代数、标准差等 指标上均好于简单和佳点集遗传算法.由此说明随 机化均匀设计混合遗传算法在搜索能力、收敛速度 以及避免早熟等各项指标上均好于简单遗传算法和 佳点集遗传算法， 陈明华，男，1954生，教授，主要研 6结束语 究方向为遗传算法、统计建模中的大样 本理论 文章以遗传算法的理想浓度模型”为基础，充 分分析其运行机理，利用统计抽样的理论和方法对 算法中的交叉操作进行了重新设计.分析图二划分 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net表 2 SGA、GGA和 UGA的实验结果比较 Table 2 Exper im en ta l result of SGA, GGA and UGA 问题 算法 Nbest Vavg σ Navg SGA 60 63. 12 2. 93 51. 31 Queen5_5 GGA 60 60. 68 1. 85 11. 48 RGA 60 60. 00 0. 00 1. 40 SGA 83 94. 01 5. 90 149. 72 David GGA 82 91. 08 4. 77 62. 63 RGA 82 87. 88 3. 26 23. 96 SGA 14 35. 20 9. 94 138. 19 M iles250 GGA 18 47. 14 13. 57 65. 34 RGA 4 10. 30 4. 20 20. 89 SGA 495 515. 68 21. 81 156. 19 Queen10_10 GGA 500 515. 64 2. 92 47. 90 RGA 495 495. 00 0. 00 3. 76 SGA 1 188 1 279. 20 42. 09 174. 73 Queen13_13 GGA 12 320 1 364. 20 47. 07 125. 79 RGA 1 092 1 092. 30 1. 71 18. 74 SGA 1 930 2 066. 30 57. 44 176. 08 Queen15_15 GGA 2 148 2 264. 80 32. 44 123. 58 RGA 1 680 1 685. 30 11. 74 15. 37 其中 : SGA 为简单遗传算法 ; GGA 为佳点集遗 传算法 ; RGA为基于随机化均匀设计的混合遗传算 法. 算法参数为 :群体规模为 100;交叉和变异概率 : Pc = 0. 9, Pm = 0. 05;最大迭代代数为 200. 算法中惩 罚系数 : r = 1 - ( 1 2 ) | max( | V1 | , | V2 | ) - n /2 | , n为顶点个数; 当 (max | V1 | , | V2 | ) - n /2 ) ≤5时 u = 0,否则 u = 1. 为避免遗传算法的随机性 ,对每个 标准算例在同一台机器上进行连续 100次计算 ,记 录如下结果 : 1) 100次运行中求得的最好解 (记为 Nbest )和 100次运行所得解的平均值 (记为 Vavg ) ; 2) 100次运 行求得解的标准差 (记为 σ ) ; 3) 100次运行中每次 收敛时代数的平均值 (记为 Navg ). 由表 2可以得出 :随机化均匀设计混合遗传算 法每次得到的解均好于简单遗传算法和佳点集遗传 算法;而且在解的平均值、平均收敛代数、标准差等 指标上均好于简单和佳点集遗传算法. 由此说明随 机化均匀设计混合遗传算法在搜索能力、收敛速度 以及避免早熟等各项指标上均好于简单遗传算法和 佳点集遗传算法. 6 结束语 文章以遗传算法的“理想浓度模型 ”为基础 ,充 分分析其运行机理 ,利用统计抽样的理论和方法对 算法中的交叉操作进行了重新设计. 分析图二划分 问题的特点 ,结合局部搜索技术 ,提出了新的解决图 二划分问题的混合遗传算法 ,克服了佳点集遗传算 法中佳点选取不带随机性的缺点 ,实例仿真得出的 结果表明了新算法的有效性和先进性. 今后的工作 是进步分析该方法的深层次的数学基础以及该方法 在组合优化问题中的有效性和先进性. 参考文献 : [ 1 ] KANG S J, MOON B R. A hybrid genetic algorithm for multi2way graph partitioning [ C ] / /Proc Genetic & Evolu2 tionary Computation Conf ( GECCO22000). San Francisco, USA: Morgan Kaufmann, 2000: 1592166. [ 2 ]HENDR ICKSON B, KOLDA T G. Graph partitioning mod2 els for parallel computing[J ]. Parallel Compute, 2000, 26 (12) : 151921534. [ 3 ]张 铃 ,张 钹. 遗传算法机理的研究 [J ]. 软件学报 , 2000, 11 (7) : 9452952. ZHANG Ling, ZHANG Bo. Research on the mechanism of genetic algorithms[J ]. Journal of Software, 2000, 11 (7) : 9452952. [ 4 ]张 铃 ,张 钹. 佳点集遗传算法 [ J ]. 计算机学报 , 2001, 24 (9) : 9172922. ZHANG L ing, ZHANG Bo. Good point set based genetic algorithm [ J ]. Chinese Journal of Computers, 2001, 24 (9) : 9172922. [ 5 ]华罗庚 , 王 元. 数论在近似分析中的应用 [M ]. 北京 : 科学出版社 , 1978. [ 6 ] SOPER A J, WALSHAW C, CROSSM. A combined evolu2 tionary search and multilevel op timization app roach to graph partitioning[J ]. Journal of Global Op tim ization, 2000, 29 (2) : 2252241. [ 7 ]王兆军 , 张润楚. 均匀设计抽样的偏差 [J ]. 数学物理 学报 , 1997, 17 (2) : 2072217. WANG Zhaojun, ZHANG Runchu. Descripency of uniform desingn samp ling[J ]. Acta Mathematica Scientia, 1997, 17 (2) : 2072217. [ 8 ]WALSHAW C. The graph partitioning archive [ EB /OL ]. [ 2008204215 ]. http: / /staffweb. cms. gre. ac. uk /～wc06 / partition /. 作者简介 : 周本达 ,男 , 1974生 ,副教授. 主要 研究方向为遗传算法、多 Agent系统. 发 表学术论文 10余篇. 陈明华 ,男 , 1954生 ,教授 ,主要研 究方向为遗传算法、统计建模中的大样 本理论. ·94· 智 能 系 统 学 报 第 4卷