|
Journal of Zhejiang University SCIENCE C
ISSN 1869-1951(Print), 1869-196x(Online), Monthly
2013 Vol.14 No.11 P.815-821
A multi-crossover and adaptive island based population algorithm for solving routing problems
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
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/jzus.C1300184
CLC number:
TP273
Download Full Text:
Downloaded:
3214
Download summary:
<Click Here>Downloaded:
2575Clicked:
8796
Cited:
9
On-line Access:
2024-08-27
Received:
2023-10-17
Revision Accepted:
2024-05-08
Crosschecked:
2013-10-15