您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报 (工学版) ›› 2018, Vol. 48 ›› Issue (6): 19-26.doi: 10.6040/j.issn.1672-3961.0.2018.203

• 机器学习与数据挖掘 • 上一篇    下一篇

基于Grefenstette编码和2-opt优化的遗传算法

公冶小燕1(),林培光2,3,*(),任威隆4   

  1. 1. 曲阜师范大学软件学院, 山东 曲阜 273165
    2. 山东财经大学计算机科学与技术学院, 山东 济南 250014
    3. 山东大学软件学院, 山东 济南 250101
    4. 肯特州立大学计算机学院, 美国 肯特 44240
  • 收稿日期:2018-05-31 出版日期:2018-12-20 发布日期:2018-12-26
  • 通讯作者: 林培光 E-mail:yigongsd@163.com;linpg@sdufe.edu.cn
  • 作者简介:公冶小燕(1990—)，女，山东济宁人，硕士研究生，主要研究方向信息检索.E-mail:yigongsd@163.com
  • 基金资助:
    教育部人文社会科学研究项目(15YJAZH042);山东省本科高校教学改革研究重点项目(2015Z058)

Genetic algorithm based on Grefenstette coding and 2-opt optimized

Xiaoyan GONGYE1(),Peiguang LIN2,3,*(),Weilong REN4   

  1. 1. School of Software Engineering, Qufu Normal University, Qufu 273165, Shandong, China
    2. School of Computer Science and Technology, Shandong University of Finance and Economics, Jinan 250014, Shandong, China
    3. School of Software, Shandong University, Jinan 250101, Shandong, China
    4. School of Computer Science, Kent State University, Kent 44240, Ohio, USA
  • Received:2018-05-31 Online:2018-12-20 Published:2018-12-26
  • Contact: Peiguang LIN E-mail:yigongsd@163.com;linpg@sdufe.edu.cn
  • Supported by:
    教育部人文社会科学研究项目(15YJAZH042);山东省本科高校教学改革研究重点项目(2015Z058)

RichHTML

21

PDF (PC)

1343

摘要：

将Grefenstette编码和2-opt优化算法共同运用到遗传算法中，采用一定数目的城市坐标对路径搜索进行求解。仿真试验取得良好的效果，初始路径接近最优路径，且经过122次迭代后快速得到最优路径。证明本研究提出的搜索空间路径方案实现了遗传算法可以快速收敛到最优解，同时保持较强的搜索能力，实现全局最优，又可以防止陷入局部最优。

关键词: 遗传算法, 空间路径搜索, Grefenstette编码, 2-opt, 全局最优

Abstract:

Grefenstette coding and 2-opt were applied simultaneously into genetic algorithm to obtain the space searching path, using a certain number of city coordinates. The synthetic experimentation achieved good result: the optimal path could be approximately represented by initial path, and could be accurately achieved via 122 iterations. And this result demonstrated that the proposed solution of search space path enabled genetic algorithm quickly converge to the optimal solution, maintained a strong search capability, achieved global optimization, and prevented local optimum.

Key words: genetic algorithm, space path searching, Grefenstette coding, 2-opt, global optimization

中图分类号: 

  • TP311

图1

程序流程图"

图2

初始化路径"

图3

最优化路径"

表1

对比数据最优路径、路径长度及世代数"

世代数 路径值 路径
1 39.685 72 S G I H L Q T O J R K A N D C B F M P E
2 38.188 44 Q F A I O E H D N K B C L J P S G R M T
3 36.764 80 S G I H L Q T M F B C D N A K R J O E P
18 35.446 51 I B D L N A H M T Q F C K O E P R G S J
28 35.409 76 I E P T M L D C F Q B A N K H J R G S O
31 35.395 14 I E P T M L B Q F C D K N A H J O S R G
32 34.779 50 I E P T M L B Q F C D K N A H J G R S O
37 34.759 24 O E S D B R G P M T F Q I L K N A C H J
38 33.057 02 O E S D B R G P M T F Q I L C A N K H J
39 32.790 86 O E S D B J H K N A C L I Q F T M P G R
40 31.822 38 D P G S I H J O R E M T F Q B C L A K N
41 31.092 50 D P G S I H J O R E M T F Q B C L A N K
42 30.726 71 D P G S I H J O R E M T F Q B L C A N K
43 30.423 27 D P G S I B Q F T M E R O J H L C A N K
44 30.074 63 D P G S I B Q F T M E R O J H K N A C L
45 29.451 71 D P G S J O R E M T F Q B I H K N A C L
111 27.818 50 G E M T F Q L C B I D K A N H J O S R P
112 27.472 46 G E M T F Q L C B I D K N A H J O S R P
113 27.105 11 G E M T F Q L C B I D A N K H J O S R P
120 26.280 11 Q I B L C A N K D H J O S R E P G M T F
121 24.919 26 Q I B L C A N K D H J O S R G P E M T F
122 24.522 23 Q I B L C A N K D H J O S G R P E M T F

图4

最优化过程"

图5

最优化过程的对比"

1 HOLLAND J H . Adaptation in nature and artificial systems[M]. Cambridge, USA: MIT Press, 1992: 6- 9.
2 GHARIB A , BENHRA J , CHAOUQI M . A performance comparison of PSO and GA applied to TSP[J]. International Journal of Computer Applications, 2015, 130 (15): 34- 39.
doi: 10.5120/ijca2015907188
3 赵红, 李滢, 肖文洁, 等. 实数与二进制编码GA种群多样性统一数学模型[J]. 计算机工程与科学, 2016, 38 (6): 1177- 1182.
doi: 10.3969/j.issn.1007-130X.2016.06.017
ZHAO Hong , LI Ying , XIAO Wenjie , et al. A unified mathematical model of population diversity for real and binary coded GA[J]. Computer Engineering and Science, 2016, 38 (6): 1177- 1182.
doi: 10.3969/j.issn.1007-130X.2016.06.017
4 朱华桂. 基于持续运营机会约束的竞争设施点选址研究:一种有效的实数编码遗传求解算法[J]. 中国管理科学, 2016, 24 (12): 158- 165.
ZHU Huagui . Research on competitive facility location under the operation-sustainable chance constraint: an efficient real coded genetic algorithm[J]. Chinese Journal of Management Science, 2016, 24 (12): 158- 165.
5 解庆, 赵小强. 遗传算法编码策略研究[J]. 甘肃科技, 2013, 29 (2): 13- 16.
doi: 10.3969/j.issn.1000-0952.2013.02.005
XIE Qin , ZHAO Xiaoqiang . Research on coding strategy of genetic algorithm[J]. Gansu Science and Technology, 2013, 29 (2): 13- 16.
doi: 10.3969/j.issn.1000-0952.2013.02.005
6 WANG Guirong , LI Qiqiang , WANG Luhao . An improved cross entropy algorithm for steelmaking-continuous casting production scheduling with complicated technological routes[J]. Journal of Central South University, 2015, 22 (8): 2998- 3007.
doi: 10.1007/s11771-015-2836-8
7 GREFENSTETTE J J . Optimization of control parameters for genetic algorithms[J]. Systems Man & Cybernetics IEEE Transactions on, 1986, 16 (1): 122- 128.
8 DE J. An analysis of the behavior of a class of genetic adaptive systems[D]. Ann Arbor, USA: University of Michigan, 1975.
9 GOLDBERG D E . Genetic algorithms in search, optimization and machine learning[M]. Melbourne, Australia: Addison-Wesley Publishing Company, 1989: 2104- 2116.
10 DAVIS L D . Handbook of genetic algorithms[M]. New York, USA: Van Nostrand reinhold, 1991.
11 KOZA J R . Genetic programming: on the programming of computers by means of natural selection[M]. Cambridge, USA: MIT Press, 1992.
12 赵越, 徐鑫, 赵焱, 等. 自适应记忆遗传算法研究[J]. 计算机技术与发展, 2014, 24 (2): 63- 66.
ZHAO Yue , XU Xin , ZHAO Yan , et al. Research on adaptive memory genetic algorithm[J]. Computer Technology and Development, 2014, 24 (2): 63- 66.
13 GREFENSTETTE J J, GOPAL R, ROSMAITA B J, et al. Genetic algorithms for the traveling salesman problem[C]// GREFENSTETTE J J. the 1st International Conference on Genetic Algorithms. Pittsburgh, USA: Carnegie-Mellon University, 1985: 160-168.
14 弭宝福.遗传算法进化策略的改进研究[D].哈尔滨:东北农业大学, 2014: 4-6.
MI Baofu. The improvement research on evolution strategy of genetic algorithm[D]. Harbin: Northeast Agricultural University, 2014: 4-6.
15 刘鲭洁, 陈桂明, 刘小方. 基于矩阵编码的遗传算法研究[J]. 计算机工程, 2011, 37 (13): 160- 162.
doi: 10.3969/j.issn.1000-3428.2011.13.051
LIU Qingjie , CHEN Guiming , LIU Xiaofang . Research on genetic algorithm based on matrix coding[J]. Computer Engineering, 2011, 37 (13): 160- 162.
doi: 10.3969/j.issn.1000-3428.2011.13.051
16 CROSS G A . A method for solving traveling salesman problems[J]. Operations Research, 1958, 6 (6): 791- 812.
doi: 10.1287/opre.6.6.791
17 谭巍. 高速公路收费口的设置[J]. 山东理工大学学报(自然科学版), 2012, 26 (5): 96- 99.
doi: 10.3969/j.issn.1672-6197.2012.05.024
TAN Wei . Highway toll gate settings[J]. Journal of Shandong University of Technology(Natural Science Edition), 2012, 26 (5): 96- 99.
doi: 10.3969/j.issn.1672-6197.2012.05.024
18 FENG Kai , LU Jiangang , CHEN Jianshui . Nonlinear model predictive control based on support vector machine and genetic algorithm[J]. Chinese Journal of Chemical Engineering, 2015, 24 (12): 2048- 2052.
19 GOLDBERG D E . Alleles, loci and the traveling salesman problem[J]. Proc.intl Conf.on Genetic Algorithms & Their Applications, 1985, 12 (92): 154- 159.
20 ENGLERT M , RÖGLIN H , VÖCKING B . Worst case and probabilistic analysis of the 2-opt algorithm for the TSP: extended abstract[J]. Algorithmica, 2014, 68 (1): 190- 264.
doi: 10.1007/s00453-013-9801-4
21 任昊南.用遗传算法求解TSP问题[D].济南:山东大学, 2008: 47.
REN Haonan. Search on genetic algorithm for solving traveling salesman problem[D]. Jinan: Shandong University, 2008: 47.
[1] 邵孟伟,袁世飞,周宏志,王乃华. 基于BP神经网络和遗传算法的翅片管结构优化[J]. 山东大学学报 (工学版), 2025, 55(6): 76-82.
[2] 孙尚渠,张恭禄,蒋志斌,李朝阳. 盾构滚刀磨损的影响因素敏感性分析及预测[J]. 山东大学学报 (工学版), 2025, 55(1): 86-96.
[3] 陈吟枫,肖晋宇,侯金鸣,江涵,赵小令,施啸寒. 基于精细化运行模拟的源-网-储协同短期扩展规划[J]. 山东大学学报 (工学版), 2024, 54(6): 156-166.
[4] 李二超, 张智钊. 在线动态订单需求车辆路径规划[J]. 山东大学学报 (工学版), 2024, 54(5): 62-73.
[5] 赵姣,杨倩倩,胡大伟,胡卉,李洋. 基于排队模型的电动物流车充电站选址和运输路径问题[J]. 山东大学学报 (工学版), 2024, 54(2): 47-59.
[6] 孙东磊,杨思,韩学山,叶平峰,王宪,刘蕊. 高比例风电接入下计及时段间耦合旋转备用响应风险的动态经济调度方法[J]. 山东大学学报 (工学版), 2022, 52(5): 111-122.
[7] 孙东磊, 鉴庆之, 李智琦, 韩学山, 王明强, 陈博, 付一木. 源网协调的电力系统均匀性规划[J]. 山东大学学报 (工学版), 2022, 52(5): 92-101.
[8] 宋修广,张营超,庄培芝,杨鹤,张海凤,王娟. 基于遗传算法的道路安定极限优化求解方法[J]. 山东大学学报 (工学版), 2021, 51(5): 1-7.
[9] 郭蓉蓉,张汝华,马信辉,郭森垚. 近交叉口路中式快速公交站点选址优化[J]. 山东大学学报 (工学版), 2021, 51(3): 61-67.
[10] 周恺卿,李航程,莫礼平. 基于全局最优的自适应和声搜索算法[J]. 山东大学学报 (工学版), 2021, 51(2): 47-56.
[11] 顾雪平, 杨超, 梁海平, 王元博, 李少岩. 异步电网并行协调恢复策略的优化制定方法[J]. 山东大学学报 (工学版), 2019, 49(5): 9-16.
[12] 孙润稼,朱海南,刘玉田. 基于偏好多目标优化和遗传算法的输电网架重构[J]. 山东大学学报 (工学版), 2019, 49(5): 17-23.
[13] 陈嘉杰,王金凤. 基于蚁群算法求解Choquet模糊积分模型[J]. 山东大学学报(工学版), 2018, 48(3): 81-87.
[14] 王飞,徐健,李伟,汪新浩,施啸寒. 基于分布式储能系统的风储滚动优化调度方法[J]. 山东大学学报(工学版), 2017, 47(6): 89-94.
[15] 王常顺,肖海荣. 基于自抗扰控制的水面无人艇路径跟踪控制器[J]. 山东大学学报(工学版), 2016, 46(4): 54-59.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 王素玉,艾兴,赵军,李作丽,刘增文 . 高速立铣3Cr2Mo模具钢切削力建模及预测[J]. 山东大学学报(工学版), 2006, 36(1): 1 -5 .
[2] 张永花,王安玲,刘福平 . 低频非均匀电磁波在导电界面的反射相角[J]. 山东大学学报(工学版), 2006, 36(2): 22 -25 .
[3] 李 侃 . 嵌入式相贯线焊接控制系统开发与实现[J]. 山东大学学报(工学版), 2008, 38(4): 37 -41 .
[4] 施来顺,万忠义 . 新型甜菜碱型沥青乳化剂的合成与性能测试[J]. 山东大学学报(工学版), 2008, 38(4): 112 -115 .
[5] 孔祥臻,刘延俊,王勇,赵秀华 . 气动比例阀的死区补偿与仿真[J]. 山东大学学报(工学版), 2006, 36(1): 99 -102 .
[6] 来翔 . 用胞映射方法讨论一类MKdV方程[J]. 山东大学学报(工学版), 2006, 36(1): 87 -92 .
[7] 余嘉元1 , 田金亭1 , 朱强忠2 . 计算智能在心理学中的应用[J]. 山东大学学报(工学版), 2009, 39(1): 1 -5 .
[8] 陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[9] 李可,刘常春,李同磊 . 一种改进的最大互信息医学图像配准算法[J]. 山东大学学报(工学版), 2006, 36(2): 107 -110 .
[10] 季涛,高旭,孙同景,薛永端,徐丙垠 . 铁路10 kV自闭/贯通线路故障行波特征分析[J]. 山东大学学报(工学版), 2006, 36(2): 111 -116 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发