Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2013, Vol. 14 Issue (11): 815-821    DOI: 10.1631/jzus.C1300184
    
A multi-crossover and adaptive island based population algorithm for solving routing problems
Eneko Osaba, Enrique Onieva, Roberto Carballedo, Fernando Diaz, Asier Perallos, Xiao Zhang
Deusto Institute of Technology (DeustoTech), University of Deusto, Bilbao 48007, Spain
A multi-crossover and adaptive island based population algorithm for solving routing problems
Eneko Osaba, Enrique Onieva, Roberto Carballedo, Fernando Diaz, Asier Perallos, Xiao Zhang
Deusto Institute of Technology (DeustoTech), University of Deusto, Bilbao 48007, Spain
 全文: PDF 
摘要： We propose a multi-crossover and adaptive island based population algorithm (MAIPA). This technique divides the entire population into subpopulations, or demes, each with a different crossover function, which can be switched according to the efficiency. In addition, MAIPA reverses the philosophy of conventional genetic algorithms. It gives priority to the autonomous improvement of the individuals (at the mutation phase), and introduces dynamism in the crossover probability. Each subpopulation begins with a very low value of crossover probability, and then varies with the change of the current generation number and the search performance on recent generations. This mechanism helps prevent premature convergence. In this research, the effectiveness of this technique is tested using three well-known routing problems, i.e., the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), and vehicle routing problem with backhauls (VRPB). MAIPA proves to be better than a traditional island based genetic algorithm for all these three problems.
关键词： Island model;  Adaptive algorithm;  Combinatorial optimization;  Vehicle routing problems;  Intelligent transportation systems    
Abstract: We propose a multi-crossover and adaptive island based population algorithm (MAIPA). This technique divides the entire population into subpopulations, or demes, each with a different crossover function, which can be switched according to the efficiency. In addition, MAIPA reverses the philosophy of conventional genetic algorithms. It gives priority to the autonomous improvement of the individuals (at the mutation phase), and introduces dynamism in the crossover probability. Each subpopulation begins with a very low value of crossover probability, and then varies with the change of the current generation number and the search performance on recent generations. This mechanism helps prevent premature convergence. In this research, the effectiveness of this technique is tested using three well-known routing problems, i.e., the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), and vehicle routing problem with backhauls (VRPB). MAIPA proves to be better than a traditional island based genetic algorithm for all these three problems.
Key words: Island model    Adaptive algorithm    Combinatorial optimization    Vehicle routing problems    Intelligent transportation systems
收稿日期: 2013-07-09 出版日期: 2013-11-06
CLC:  TP273  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Eneko Osaba
Enrique Onieva
Roberto Carballedo
Fernando Diaz
Asier Perallos
Xiao Zhang

引用本文:

Eneko Osaba, Enrique Onieva, Roberto Carballedo, Fernando Diaz, Asier Perallos, Xiao Zhang. A multi-crossover and adaptive island based population algorithm for solving routing problems. Front. Inform. Technol. Electron. Eng., 2013, 14(11): 815-821.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1300184    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2013/V14/I11/815

[1] Guo-liang Tao, Ce Shang, De-yuan Meng, Chao-chao Zhou. 含参数初值整定和自适应鲁棒方法的3-RPS气动并联平台位姿控制[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 303-316.
[2] Guo-liang Tao, Ce Shang, De-yuan Meng, Chao-chao Zhou. 含参数初值整定和自适应鲁棒方法的3-RPS气动并联平台位姿控制[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 303-316.
[3] Xiao-yu ZHANG. 一类非仿射离散非线性系统的直接自适应模糊滑模控制[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(12): 1331-1343.
[4] Yong-chun Xie, Huang Huang, Yong Hu, Guo-qi Zhang. 先进控制方法在航天器上的应用：进展、挑战和未来发展[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 841-861.
[5] Guo-jiang Shen, Yong-yao Yang. 一种城市主干道信号动态协调控制方法及其应用[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 907-918.
[6] Kyong-il Kim, Hsin Guan, Bo Wang, Rui Guo, Fan Liang. 铰接车辆的主动转向控制策略研究[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(6): 576-586.
[7] Jin-yi Liu, Jing-quan Tan, En-rong Mao, Zheng-he Song, Zhong-xiang Zhu. 基于比例控制的农业机械自动转向系统研究[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(5): 458-464.
[8] Chang-bin Yu, Yin-qiu Wang, Jin-liang Shao. 基于线性二次最优化的多智能体编队控制[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(2): 96-109.
[9] Mei-qin Liu, Hai-yang Chen, Sen-lin Zhang. 一类时变时滞非线性系统的H∞参考跟踪控制设计[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(9): 759-768.
[10] Gurmanik Kaur, Ajat Shatru Arora, Vijender Kumar Jain. 基于体位特征使用混杂模型预测血压对于无支撑后背的反应[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(6): 474-485.
[11] Salvador Ibarra-Martínez, José A. Castán-Rocha, Julio Laria-Menchaca. 使用理性行为人优化城区交通控制[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(12): 1123-1137.
[12] Wajdi S. Aboud, Sallehuddin Mohamed Haris, Yuzita Yaacob. Advances in the control of mechatronic suspension systems[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(10): 848-860.
[13] Peng-fei Qian, Guo-liang Tao, De-yuan Meng, Hao Liu. 用于气动系统的一种改进型直接自适应鲁棒运动跟踪控制器[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(10): 878-891.
[14] Farnaz Sabahi, M.-R. Akbarzadeh-T. 一种分析扩展模糊逻辑的架构[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(7): 584-591.
[15] Hua Zhang, Lu-ping Xu, Yang-he Shen, Rong Jiao, Jing-rong Sun. X射线脉冲星的一种新型最大似然相位估计方法[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(6): 458-469.