×

Analytical and numerical comparisons of biogeography-based optimization and genetic algorithms. (English) Zbl 1216.68252

Summary: We show that biogeography-based optimization (BBO) is a generalization of a genetic algorithm with global uniform recombination (GA/GUR). Based on the common features of BBO and GA/GUR, we use a previously-derived BBO Markov model to obtain a GA/GUR Markov model. One BBO characteristic which makes it distinctive from GA/GUR is its migration mechanism, which affects selection pressure (i.e., the probability of retaining certain features in the population from one generation to the next). We compare the BBO and GA/GUR algorithms using results from analytical Markov models and continuous optimization benchmark problems. We show that the unique selection pressure provided by BBO generally results in better optimization results for a set of standard benchmark problems. We also present comparisons between BBO and GA/GUR for combinatorial optimization problems, include the traveling salesman, the graph coloring, and the bin packing problems.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

Genocop; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Ackley, D., A connectionist machine for genetic hillclimbing, (1987), Kluwer Academic Publishers
[2] Back, T., Evolutionary algorithms in theory and practice, (1996), Oxford University Press · Zbl 0877.68060
[3] Back, T.; Hammel, U.; Schwefel, H., Evolutionary computation: comments on the history and current state, IEEE transactions on evolutionary computation, 1, 3-17, (1997)
[4] Beaulieu, N., On the generalized multinomial distribution, optimal multinomial detectors, and generalized weighted partical decision detectors, IEEE transactions on communications, 39, 193-194, (1991)
[5] M. Bhattacharya, Expensive optimization, uncertain environment: an EA-based solution, in: Genetic and Evolutionary Computation Conference, 2007, pp. 2407-2414.
[6] Bremermann, H.; Rogson, M.; Salaff, S., Global properties of evolution processes, (), 3-41
[7] Cai, Z.; Wang, Y., A multiobjective optimization-baed evoluationary algorithm for constrained optimization, IEEE transactions on evolutionary computation, 10, 658-675, (2006)
[8] Clerc, M.; Kennedy, J., The particle swarm – explosion, stability, and convergence in a multidimensional complex space, IEEE transactions on evolutionary computation, 6, 58-73, (2002)
[9] Davis, T.; Principe, J., A simulated annealing like convergence theory for the simple genetic algorithms, (), 174-181
[10] Davis, T.; Principe, J., A Markov chain framework for the simple genetic algorithm, Evolutionary computation, 1, 269-288, (1993)
[11] Dembski, W.; Marks, R., Conservation of information in search: measuring the cost of success, IEEE transactions on systems, man, and cybernetics – part A: systems and humans, 39, 1051-1061, (2009)
[12] Eiben, A., Multiparent recombination in evolutionary computing, (), 175-192
[13] Eiben, A., Multiparent recombination, (), 289-302
[14] A. Eiben, C. Schippers, Multi-parent’s niche: n-ary crossovers on NK-landscapes, in: Proceedings of the 4th Conference on Parallel Problem Solving from Nature, 1996, pp. 319-328.
[15] Eiben, A.; Back, T., Empirical investigation of multiparent recombination operators in evolution strategies, Evolutionary computation, 5, 347-365, (1998)
[16] M. Ergezer, D. Simon, D. Du, Oppositional biogeography-based optimization, in: IEEE Conference on Systems, Man, and Cybernetics, San Antonio, Texas, 2009, pp. 1035-1040.
[17] Falkenauer, A., A hybrid grouping genetic algorithm, Journal of heuristics, 2, 5-30, (1996)
[18] W. Gong, Z. Cai, C. Ling, DE/BBO: a hybrid differential evolution with biogeography-based optimization for global numerical optimization, Soft Computing, in press. doi:10.1007/s00500-010-0591-1.
[19] Grinstead, C.; Snell, J., Introduction to probability, (1997), American Mathematical Society · Zbl 0914.60004
[20] Ho, Y.; Pepyne, D., Simple explanation of the no-free-lunch theorem and its implications, Journal of optimization theory and applications, 155, 549570, (2002) · Zbl 1031.91018
[21] F. Hoffmeister, T. Back, Genetic algorithms and evolution strategies: Similarities and differences, in: Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, 1991, pp. 455-469.
[22] Jin, Y., A comprehensive survey of fitness approximation in evolutionary computation, Soft computing, 9, 3-12, (2005)
[23] A. Khanafer, One dimensional bin packing. <http://ali.khanafer.free.fr/index.php?n=Main.Benchmarks>.
[24] H. Kundra, A. Kaur, V. Panchal, An integrated approach to biogeography based optimization with case based reasoning for retrieving groundwater possibility, in: 8th Annual Asian Conference and Exhibition on Geospatial Information, Technology and Applications, August 2009.
[25] Leighton, F., A graph coloring algorithm for large scheduling problems, Journal of research of the national bureau of standards, 84, 489-505, (1979) · Zbl 0437.68021
[26] Loh, K.; Golden, B.; Wasil, E., Solving the one-dimensional bin packing problem with a weight annealing heuristic, Computers and operations research, 35, 2283-2291, (2008) · Zbl 1177.90347
[27] Lomolino, M.; Riddle, B.; Brown, J., Biogeography, (2009), Sinauer Associates
[28] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical programming, 34, 111-124, (1986) · Zbl 0581.90061
[29] R. Lung, D. Dumitrescu, A new evolutionary model for detecting multiple optima, in: Genetic and Evolutionary Computation Conference, 2007, pp. 1296-1303.
[30] H. Ma, S. Ni, M. Sun, Equilibrium species counts and migration model tradeoffs for biogeography-based optimization, in: IEEE Conference on Decision and Control, 2009, pp. 3306-3310.
[31] Matula, D.; Marble, G.; Isaacson, J., Graph coloring algorithms, (), 109-122
[32] Michalewicz, Z., Genetic algorithms+data structures=evolution programs, (1998), Springer
[33] Mo, H.; Xu, L., Biogeography migration algorithm for traveling salesman problem, (), 405-414
[34] K. Moreland, The needles-in-haystack problem, in: International Conference on Machine Learning and Data Mining in Pattern Recognition, 2009, pp. 516-524.
[35] Nix, A.; Vose, M., Modeling genetic algorithms with Markov chains, Annals of mathematics and artificial intelligence, 5, 79-88, (1992) · Zbl 1034.68534
[36] Panchal, V.; Singh, P.; Kaur, N.; Kundra, H., Biogeography based satellite image classification, International journal of computer science and information security, 6, 269-274, (2009)
[37] Price, K.; Storn, R., Differential evolution, Dr. dobb’s journal, 22, 18-20, (1997), 22, 24, 78
[38] R. Rarick, D. Simon, F. Villaseca, B. Vyakaranam, Biogeography-based optimization and the solution of the power flow problem, in: IEEE Conference on Systems, Man, and Cybernetics, 2009, pp. 1029-1034.
[39] Ratle, A., Accelerating the convergence of evolutionary algorithms by fitness landscape approximation, (), 87-96
[40] G. Reinelt, TSPLIB, August 2008. <http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95>.
[41] Reeves, C.; Rowe, J., Genetic algorithms: principles and perspectives, (2003), Kluwer
[42] Roy, P.; Ghoshal, S.; Thakur, S., Biogeography-based optimization for economic load dispatch problems, Electric power components and systems, 38, 166-181, (2010)
[43] Savsani, V.; Rao, R.; Vakharia, D., Discrete optimisation of a gear train using biogeography based optimisation technique, International journal of design engineering, 2, 205-223, (2009)
[44] A. Scholl, R. Klein, Bin packing, September 1, 2003. <http://www.wiwi.uni-jena.de/Entscheidung/binpp/bin3dat.htm>.
[45] Simon, D., Biogeography-based optimization, IEEE transactions on evolutionary computation, 12, 702-713, (2008)
[46] D. Simon, M. Ergezer, D. Du, Population distributions in biogeography-based optimization algorithms with elitism, in: IEEE Conference on Systems, Man, and Cybernetics, 2009, pp. 1017-1022.
[47] D. Simon, A probabilistic analysis of a simplified biogeography-based optimization algorithm, Evolutionary Computation, in press. Available at <http://academic.csuohio.edu/simond/bbo/simplified>.
[48] D. Simon, M. Ergezer, D. Du, and R. Rarick, Markov Models for Biogeography-Based Optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B. Available at <http://embeddedlab.csuohio.edu/BBO>. · Zbl 1216.68252
[49] Storn, R., System design by constraint adaptation and differential evolution, IEEE transactions on evolutionary computation, 3, 22-34, (1999)
[50] Suzuki, J., A Markov chain analysis on simple genetic algorithms, IEEE transactions on systems, man and cybernetics, part B, 25, 655-659, (1995)
[51] Suzuki, J., A further result on the Markov chain model of genetic algorithms and its application to a simulated annealing-like strategy, IEEE transactions on systems, man, and cybernetics, part B, 28, 95-102, (1998)
[52] Tao, G.; Michalewicz, Z., Inver-over operator for the TSP, (), 803-812
[53] Torregosa, R.; Kanok-Nukulchai, W., Weight optimization of steel frames using genetic algorithm, Advances in structural engineering, 5, 99-111, (2002)
[54] M. Trick, Graph coloring instances. <http://mat.gsia.cmu.edu/COLOR/instances.html>.
[55] F. Vavak, T. Fogarty, Comparison of steady state and generational genetic algorithms for use in nonstationary environments, in: IEEE International Conference on Evolutionary Computation, 1996, pp. 192-195.
[56] S. Venkatraman, G. Yen, A simple elitist genetic algorithm for constrained optimization, in: IEEE Congress on Evolutionary Computation, 2004, pp. 288-295.
[57] Whittaker, R., Island biogeography, (1998), Oxford University Press
[58] Yao, X.; Liu, Y.; Lin, G., Evolutionary programming made faster, IEEE transactions on evolutionary computation, 3, 82-102, (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.