Journal of Shandong University(Engineering Science) ›› 2018, Vol. 48 ›› Issue (6): 19-26.doi: 10.6040/j.issn.1672-3961.0.2018.203

• Machine Learning & Data Mining • Previous Articles     Next Articles

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

15

PDF (PC)

506

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

CLC Number: 

  • TP311

Fig.1

Program flow chart"

Fig.2

Initial path"

Fig.3

Optimized path"

Table 1

The contrastive data between optimized paths, path lengths and the generations"

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

Fig.4

Optimization process"

Fig.5

The contrast of optimization process"

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] CHEN Jiajie, WANG Jinfeng. Method for solving Choquet integral model based on ant colony algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 81-87.
[2] WANG Fei, XU Jian, LI Wei, WANG Xinhao, SHI Xiaohan. Rolling optimal dispatch method of wind power based on distributed energy storage system [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(6): 89-94.
[3] LIU Debao, WU Yaohua, GUO Yaoyang, WANG Yanyan. Item assignment optimization of automatic picking system based on hybrid picking strategy [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(6): 36-44.
[4] DONG Hongbin, ZHANG Guangjiang, PANG Jinwei, HAN Qilong. A clustering ensemble algorithm based on co-evolution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 1-9.
[5] LIANG Xingjian, ZHAN Zhihui. Improved genetic algorithm based on the dual-mode mutation strategy [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 1-7.
[6] SUN Peng, CHENG Shi-qing*, XIE Jing-si, ZHANG Hai-rui. CV-GA-SVM model for predicting the ash fusion point of a mixed biomass [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 108-111.
[7] YANG Qinmin, LIU Hailin*. Dynamic channel allocation modeling and algorithm in cellular networks
based on a genetic algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(2): 85-90.
[8] LIU Bin, ZHANG Ren-jin. NURBS curve approximation based on annealing genetic algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(5): 96-100.
[9] YANG Ai-min1, ZHOU Yong-mei1, DENG He2, ZHOU Jian-feng3. Method of feature generation and selection for network traffic classification [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(5): 1-7.
[10] WANG Yan-yan, WU Yao-hua, SUN Guo-hua, YU Hong-peng. Research on  picking  order  batching  policy  of  a  distribution  center [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(2): 43-46.
[11] GONG Dunwei, SUN Xiaoyan, REN Jie. Interactive genetic algorithms with tournament evaluation and evolutionary knowledge extraction [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 1-7.
[12] WANG Jian, ZHANG Shan. voltage  regulation research of an improved genetic algorithm considering infeasidering infeasibility degree [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(6): 21-24.
[13] LI Jie ，LIU Hong. A method of fractal artistic pattern generation based on a genetic algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(6): 33-36.
[14] ZHANG Jian,WU Yao-hua,LIU Pei,WANG Yan-yan . Hybrid hub-and-spoke network planning of road express freight [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(5): 6-9 .
[15] BEI Guang-xia,LOU Pei-huang,WANG Xiao-yong,ZHU Heng-yun,DU Hui . Cylindricity error evaluation based on genetic algorithms [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(2): 33-36 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] CHENG Daizhan, LI Zhiqiang. A survey on linearization of nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 26 -36 .
[2] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[3] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[4] HU Tian-liang,LI Peng,ZHANG Cheng-rui,ZUO Yi . Design of a QEP decode counter based on VHDL[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 10 -13 .
[5] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 104 -107 .
[6] CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[7] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 131 -136 .
[8] LI Shijin, WANG Shengte, HUANG Leping. Change detection with remote sensing images based on forward-backward heterogenicity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 1 -9 .
[9] WANG Ru-gui,CAI Gan-wei . Sub-harmonic resonance analysis of 2-DOF controllable plane linkage mechanism electromechanical coupling system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 58 -63 .
[10] XUE Cheng-qian,DONG Jian-wen,MENG Xian-feng,CHANG Hong,CAO Ning,CHEN Hua-ying,LI Mu-sen . The effect of C／C+HA bonerepairing material to the physiological and biochemical response of the crossed Boer Goat[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 73 -76 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd