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

doi:10.6040/j.issn.1672-3961.0.2018.203

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

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

公冶小燕¹(),林培光^2,^3,*(),任威隆⁴

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 GONGYE¹(),Peiguang LIN^2,^3,*(),Weilong REN⁴

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)

摘要/Abstract

摘要：

将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

公冶小燕,林培光,任威隆. 基于Grefenstette编码和2-opt优化的遗传算法[J]. 山东大学学报 (工学版), 2018, 48(6): 19-26.

Xiaoyan GONGYE,Peiguang LIN,Weilong REN. Genetic algorithm based on Grefenstette coding and 2-opt optimized[J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 19-26.

图/表 6

图1

图2

图3

表1

图4

图5

参考文献 21

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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

世代数	路径值	路径
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

[1]	陈嘉杰,王金凤. 基于蚁群算法求解Choquet模糊积分模型[J]. 山东大学学报(工学版), 2018, 48(3): 81-87.
[2]	王飞,徐健,李伟,汪新浩,施啸寒. 基于分布式储能系统的风储滚动优化调度方法[J]. 山东大学学报(工学版), 2017, 47(6): 89-94.
[3]	王常顺,肖海荣. 基于自抗扰控制的水面无人艇路径跟踪控制器[J]. 山东大学学报(工学版), 2016, 46(4): 54-59.
[4]	刘德宝, 吴耀华, 郭耀阳, 王艳艳. 基于串并行混合拣选策略的自动拣选系统品项分配优化[J]. 山东大学学报(工学版), 2015, 45(6): 36-44.
[5]	董红斌, 张广江, 逄锦伟, 韩启龙. 一种基于协同进化方法的聚类集成算法[J]. 山东大学学报(工学版), 2015, 45(2): 1-9.
[6]	梁兴建, 詹志辉. 基于双模式变异策略的改进遗传算法[J]. 山东大学学报(工学版), 2014, 44(6): 1-7.
[7]	孙鹏,程世庆*,谢敬思,张海瑞. 预测混合生物质灰熔点的CV-GA-SVM模型[J]. 山东大学学报(工学版), 2012, 42(2): 108-111.
[8]	杨钦民,刘海林*. 基于遗传算法的蜂窝网络动态信道分配建模及算法实现[J]. 山东大学学报(工学版), 2011, 41(2): 85-90.
[9]	刘彬,张仁津. 基于退火遗传算法的NURBS曲线逼近[J]. 山东大学学报(工学版), 2010, 40(5): 96-100.
[10]	阳爱民1,周咏梅1,邓河2,周剑峰3. 一种网络流量分类特征的产生及选择方法[J]. 山东大学学报(工学版), 2010, 40(5): 1-7.
[11]	王艳艳,吴耀华,孙国华,于洪鹏. 配送中心分拣订单合批策略的研究[J]. 山东大学学报(工学版), 2010, 40(2): 43-46.
[12]	杜乾蔚何彬王玉玲游智. 基于遗传算法的含金属混合炸药配方设计[J]. 山东大学学报(工学版), 2009, 39(5): 149-152.
[13]	巩敦卫,孙晓燕,任洁. 基于联赛评价和知识提取的交互式遗传算法 [J]. 山东大学学报(工学版), 2009, 39(2): 1-7.
[14]	王剑张善. 考虑不可行度的改进遗传算法在电压无功调整中的研究[J]. 山东大学学报(工学版), 2008, 38(6): 21-24.
[15]	李杰刘弘. 基于遗传算法的分形艺术图案生成方法[J]. 山东大学学报(工学版), 2008, 38(6): 33-36.

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

Genetic algorithm based on Grefenstette coding and 2-opt optimized

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 21

相关文章 15

多维度评价

本文评价

推荐阅读 10