Please wait a minute...
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
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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 wordsIsland model      Adaptive algorithm      Combinatorial optimization      Vehicle routing problems      Intelligent transportation systems     
Received: 09 July 2013      Published: 06 November 2013
CLC:  TP273  
Cite this article:

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.

URL:

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


A multi-crossover and adaptive island based population algorithm for solving routing problems

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 
[1] Erfan Shaghaghi, Mohammad Reza Jabbarpour, Rafidah Md Noor, Hwasoo Yeo, Jason J. Jung. Adaptive green traffic signal controlling using vehicular communication[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 373-393.