Full Text:   <1560>

Summary:  <784>

CLC number: TP273

On-line Access: 2013-11-06

Received: 2013-07-09

Revision Accepted: 2013-10-03

Crosschecked: 2013-10-15

Cited: 9

Clicked: 3242

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2013 Vol.14 No.11 P.815-821

http://doi.org/10.1631/jzus.C1300184


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


Author(s):  Eneko Osaba, Enrique Onieva, Roberto Carballedo, Fernando Diaz, Asier Perallos, Xiao Zhang

Affiliation(s):  Deusto Institute of Technology (DeustoTech), University of Deusto, Bilbao 48007, Spain

Corresponding email(s):   e.osaba@deusto.es, enrique.onieva@deusto.es, roberto.carballedo@deusto.es, fernando.diaz@deusto.es, perallos@deusto.es, xiao.zhang@deusto.es

Key Words:  Island model, Adaptive algorithm, Combinatorial optimization, Vehicle routing problems, Intelligent transportation systems


Share this article to: More |Next 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[J]. Journal of Zhejiang University Science C, 2013, 14(11): 815-821.

@article{title="A multi-crossover and adaptive island based population algorithm for solving routing problems",
author="Eneko Osaba, Enrique Onieva, Roberto Carballedo, Fernando Diaz, Asier Perallos, Xiao Zhang",
journal="Journal of Zhejiang University Science C",
volume="14",
number="11",
pages="815-821",
year="2013",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1300184"
}

%0 Journal Article
%T A multi-crossover and adaptive island based population algorithm for solving routing problems
%A Eneko Osaba
%A Enrique Onieva
%A Roberto Carballedo
%A Fernando Diaz
%A Asier Perallos
%A Xiao Zhang
%J Journal of Zhejiang University SCIENCE C
%V 14
%N 11
%P 815-821
%@ 1869-1951
%D 2013
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1300184

TY - JOUR
T1 - A multi-crossover and adaptive island based population algorithm for solving routing problems
A1 - Eneko Osaba
A1 - Enrique Onieva
A1 - Roberto Carballedo
A1 - Fernando Diaz
A1 - Asier Perallos
A1 - Xiao Zhang
J0 - Journal of Zhejiang University Science C
VL - 14
IS - 11
SP - 815
EP - 821
%@ 1869-1951
Y1 - 2013
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1300184


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Anbuudayasankar, S., Ganesh, K., Lenny Koh, S.C., Ducq, Y., 2012. Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Syst. Appl., 39(3):2296-2305.

[2]Bae, J., Rathinam, S., 2012. Approximation algorithms for multiple terminal, Hamiltonian path problems. Optim. Lett., 6(1):69-85.

[3]Cantú-Paz, E., 1998. A survey of parallel genetic algorithms. Calcul. Parall. Res. Syst. Rep., 10(2):141-171.

[4]Davis, L., 1985. Applying Adaptive Algorithms to Epistatic Domains. Proc. Int. Joint Conf. on Artificial Intelligence, p.161-163.

[5]de Jong, K., 1975. Analysis of the Behavior of a Class of Genetic Adaptive Systems. MS Thesis, University of Michigan, Michigan, USA.

[6]Goldberg, D., 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, Boston, USA.

[7]Golden, B., Baker, E., Alfaro, J., Schaffer, J., 1985. The Vehicle Routing Problem with Backhauling: Two Approaches. Proc. 21st Annual Meeting of SETIMS, p.90-92.

[8]Holland, J.H., 1975. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Michigan, USA.

[9]Laporte, G., 1992. The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res., 59(3):345-358.

[10]Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I., Dizdarevic, S., 1999. Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif. Intell. Rev., 13(2):129-170.

[11]Lawler, E., Lenstra, J., Kan, A., Shmoys, D., 1985. The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization, Volume 3. Wiley, New York, USA.

[12]Lin, S., 1965. Computer solutions of the traveling salesman problem. Bell Syst. Techn. J., 44(10):2245-2269.

[13]Martínez-Torres, M., 2012. A genetic search of patterns of behaviour in OSS communities. Expert Syst. Appl., 39(18):13182-13192.

[14]Mattos Ribeiro, G., Laporte, G., 2012. An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res., 39(3):728-735.

[15]Moon, I., Lee, J.H., Seong, J., 2012. Vehicle routing problem with time windows considering overtime and outsourcing vehicles. Expert Syst. Appl., 39(18):13202-13213.

[16]Mukherjee, S., Ganguly, S., Das, S., 2012. A strategy adaptive genetic algorithm for solving the travelling salesman problem. LNCS, 7677:778-784.

[17]Ngueveu, S., Prins, C., Wolfler Calvo, R., 2010. An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res., 37(11):1877-1885.

[18]Niu, B., Zhu, Y., He, X., Wu, H., 2007. MCPSO: a multi-swarm cooperative particle swarm optimizer. Appl. Math. Comput., 185(2):1050-1062.

[19]Osaba, E., Carballedo, R., Diaz, F., Perallos, A., 2013. Analysis of the Suitability of Using Blind Crossover Operators in Genetic Algorithms for Solving Routing Problems. Proc. 8th Int. Symp. on Applied Computational Intelligence and Informatics, p.17-23.

[20]Ray, S., Bandyopadhyay, S., Pal, S., 2004. New Operators of Genetic Algorithms for Traveling Salesman Problem. Proc. 17th Int. Conf. on Pattern Recognition, p.497-500.

[21]Reinelt, G., 1991. TSPLIB: a traveling salesman problem library. ORSA J. Comput., 3(4):376-384.

[22]Sarin, S.C., Sherali, H.D., Yao, L., 2011. New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem. Optim. Lett., 5(2):259-272.

[23]Schaffer, J.D., Morishima, A., 1987. An Adaptive Crossover Distribution Mechanism for Genetic Algorithms. Proc. 2nd Int. Conf. on Genetic Algorithms and Their Application, p.36-40.

[24]Spears, W.M., 1995. Adapting Crossover in Evolutionary Algorithms. Proc. Conf. on Evolutionary Programming, p.367-384.

[25]Syswerda, G., 1991. Schedule Optimization Using Genetic Algorithms. In: Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, USA, p.332-349.

[26]Tsai, P.W., Pan, J.S., Liao, B.Y., Chu, S.C., 2009. Enhanced artificial bee colony optimization. Int. J. Innov. Comput. Inf. Control, 5(12):5081-5092.

[27]Wang, L., Tang, D.B., 2011. An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem. Expert Syst. Appl., 38(6):7243-7250.

[28]Whitley, D., Rana, S., Heckendorn, R.B., 1999. The island model genetic algorithm: on separability, population size and convergence. J. Comput. Inf. Technol., 7:33-48.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE