直觉模糊小生境的自适应遗传算法求解旅行商问题

doi:10.11896/j.issn.1002-137X.2016.12.008

摘要/Abstract

摘要： 提出一种基于直觉模糊距离测度的小生境技术,结合模糊控制的自适应遗传算法求解旅行商问题。运用个体在遗传算法迭代寻优中的适应度值,通过直觉模糊集的距离测度确定个体之间的相似性,使用共享函数和惩罚函数对适应度低的个体进行惩罚和淘汰,维护了种群个体的多样性；建立模糊推理系统,以自适应调节遗传算法迭代中的交叉率和变异率,使遗传算法能在局部寻优和全局寻优之间达到平衡,弥补遗传算法易早熟收敛和后期寻优能力差的缺陷；通过求解TSPLIB中的多组实例并进行对比,结果表明所提算法的收敛速度、优化精度、效率均具有明显优势。

关键词: 直觉模糊集,小生境,遗传算法,自适应,偏差率

Abstract: An improved niche algorithm based on distance measure of intuitionistic fuzzy and self-adaptive fuzzy genetic algorithm was proposed.Utilizing the distance measure of intuitionistic fuzzy set and the individual fitness in genetic algorithm optimizing procedure which is used to measure the similarity of individual,the one with low fitness is eliminated by the share function and penalty function,which can enhance the diversity of population.Furthermore,a fuzzy control system is established to adjust the crossover and mutation rate adaptively,and the algorithm can get balance between local search and global search capability,which can avoid the premature convergence and poor searching efficiency in the later period.Simulation results of series TSPLB instances show that the proposed method has many advantages on the convergence speed,optimal precision and efficiency.

Key words: Intuitionistic fuzzy set,Niche,Genetic algorithm,Self-adaptive,Deviation rate

梅海涛,王毅,华继学. 直觉模糊小生境的自适应遗传算法求解旅行商问题[J]. 计算机科学, 2016, 43(12): 46-49. https://doi.org/10.11896/j.issn.1002-137X.2016.12.008

MEI Hai-tao, WANG Yi and HUA Ji-xue. Self-adaptive Genetic Algorithm Based on Intuitionistic Fuzzy Niche for Solving Traveling Salesman Problem[J]. Computer Science, 2016, 43(12): 46-49. https://doi.org/10.11896/j.issn.1002-137X.2016.12.008

参考文献

[1] Son M,Ko S,Koo J.Genetic Algorithm to Optimize the Design of Main Combustor and Gas Generator in Liquid Rocket Engines[J].Journal of Thermal Science,2014,23(3):259-268
[2] Wang Ping,Wu Guang-qiang.Multidisciplinary Design Optimization of Vehicle Instrument Panel Based on Multi-objective Genetic Algorithm[J].Chinese Journal of Mechanical Engineering,2013,26(2):304-312
[3] Lou Xiong-wei,Huang De-cai,Fang Lu-ming,et al.Forest FireIdentification Method Based on Improved Genetic Algorithm and SVM[J].Computer Science,2014,41(8):316-321 (in Chinese) 楼雄伟,黄德才,方陆明,等.基于改进遗传算法和SVM的森林火灾视频目标鉴定[J].计算机科学,2014,41(8):316-321
[4] Li Y,Liu G,Lao S Y.A genetic algorithm for community detection in complex networks[J].Journal of Central South University,2013(20):1269-1276
[5] Zhao L Y,Xu Y,Xu L B,et al.A novel immune genetic algorithm based on quasi secondary response[J].Journal of Beijing Institute of Technology,2011,20(1):4-13
[6] Wang G M,Wang X J,Wan Z P,et al.An adaptive genetic algorithm for solving bilevel linear programming problem[J].Applied Mathematics and Mechanics,2007,28(12):1605-1612
[7] Tian L L,Zhao N,Zhong W,et al.Placement Optimization of Wind Farm Based on Niche Genetic Algorithm[J].Journal of Nanjing University of Aeronautics & Astronautics,2011,43(5):650-654(in Chinese) 田琳琳,赵宁,钟伟,等.基于小生境遗传算法的风电场布局优化[J].南京航空航天大学学报,2011,43(5):650-654
[8] Wang Y,Liu S Y,Zhang W,et al.Intuitionistic fuzzy similarity measures reasoning method based on inclusion degrees[J].Journal of Systems Engineering and Electronics,2014,36(3):494-500(in Chinese) 王毅,刘三阳,张文,等.基于包含度的直觉模糊相似度量推理方法[J].系统工程与电子技术,2014,36(3):494-500
[9] Liu J W,Lin Z Z,Wen F S,et al.Consistency Analysis and Optimization of Black-start Group Decision-making Based on Intuitionistic Fuzzy Distance[J].Automation of Electric Power Systems,2012,36(10):1-6(in Chinese) 刘伟佳,林振智,文福栓,等.基于直觉模糊距离的黑启动群体决策一致性分析与优化[J].电力系统自动化,2012,36(10):1-6
[10] Lu S,Lei Y J,Kong W W,et al.Image registration algorithm based on intuitionistic fuzzy distance[J].Control and Decision,2011,26(11):1670-1674(in Chinese) 鲁珊,雷英杰,孔韦韦,等.基于直觉模糊距离的图像配准算法[J].控制与决策,2011,26(11):1670-1674
[11] Zhang S Q,Han L G,Liu C C,et al.Inverting reservoir parameters in a two-phase fractured medium with a niche genetic algorithm[J].Applied Geophysics,2012,9(4):440-450
[12] Goldberg D E.Genetic algorithms in search,optimization andmachine leaning[M].New York:Addison- Wesley Publishing Company,Inc,1989
[13] Yang Ning,Wang Qian.Negative Selection Algorithm Based on Niche Strategy[J].Computer Science,2011,38(10A):181-184(in Chinese) 杨宁,王茜.一种基于小生境策略的阴性选择算法[J].计算机科学,2011,38(10A):181-184
[14] Zhu Yu,Han Chang-pei.Improved Genetic Algorithm with Adaptive Convergence Populations[J].Computer Science,2012,39(10):214-217(in Chinese) 朱钰,韩昌配.一种种群自适应收敛的快速遗传算法[J].计算机科学,2012,39(10):214-217
[15] Gu D Q,Liu G F,Yuan J,et al.New algorithm for solving TSP based on dots and lines loop optimization[J].Journal of PLA University of Science and Technology,2010,11(4):423-427(in Chinese) 顾大权,刘高飞,袁珏,等.基于点线回路优化求解TSP的一个新算法[J].解放军理工大学学报,2010,11(4):423-427
[16] Feng X,Ma M Y,Yu H Q.Lake-Energy Optimization Algo-rithm for Travelling Salesman Problem[J].Journal of Computer Research and Development,2013,50(9):2015-2027(in Chinese) 冯翔,马美怡,虞慧群.TSP湖水能量优化算法[J].计算机研究与发展,2013,50(9):2015-2027
[17] Zhou Y Q,Huang Z X.Artificial glowworm swarm optimization algorithm for TSP[J].Control and Decision,2012,27(12):1816-1821(in Chinese) 周永权,黄正新.求解TSP的人工萤火虫群优化算法[J].控制与决策,2012,27(12):1816-1821
[18] Zhou Y Q,Huang Z X,Liu H X.Discrete Glowworm Swarm Optimization Algorithm for TSP Problem[J].Acta Electronic Sinica,2012,40(6):1164-1170(in Chinese) 周永权,黄正新,刘洪霞.求解TSP问题的离散型萤火虫群优化算法[J].电子学报,2012,40(6):1164-1170
[19] Rao W Z,Jin C,Huang T Y.Hybrid algorithm of the nearest neighbor and insertion for the traveling salesman problem[J].Systems Engineering-Theory & Practice,2011,31(8):1419-1428(in Chinese) 饶卫振,金淳,黄英艺.求解TSP问题的最近邻域与插入混合算法[J].系统工程理论与实践,2011,31(8):1419-1428

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed