Abstract
We present a multi-parent hybrid genetic–tabu algorithm (denoted by GTA) for the Unconstrained Binary Quadratic Programming (UBQP) problem, by incorporating tabu search into the framework of genetic algorithm. In this paper, we propose a new multi-parent combination operator for generating offspring solutions. A pool updating strategy based on a quality-and-distance criterion is used to manage the population. Experimental comparisons with leading methods for the UBQP problem on 25 large public instances demonstrate the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
McBride, R.D., Yormark, J.S.: An implicit enumeration algorithm for quadratic integer programming. Management Science 26, 282–296 (1980)
Krarup, J., Pruzan, A.: Computer aided layout design. Mathematical Programming Study 9, 75–94 (1978)
Gallo, G., Hammer, P., Simeone, B.: Quadratic knapsack problems. Mathematical Programming 12, 132–149 (1980)
Alidaee, B., Kochenberger, G.A., Ahmadian, A.: 0-1 quadratic programming approach for the optimal solution of two scheduling problems. International Journal of Systems Science 25, 401–408 (1994)
Chardaire, P., Sutter, A.: A decomposition method for quadratic zero-one programming. Management Science 41(4), 704–712 (1994)
Phillips, A.T., Rosen, J.B.: A quadratic assignment formulation of the molecular conformation problem. Journal of Global Optimization 4, 229–241 (1994)
Pardalos, P., Rodgers, G.P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45, 131–144 (1990)
Kochenberger, G.A., Glover, F., Alidaee, B., Rego, C.: A unified modeling and solution framework for combinatorial optimization problems. OR Spectrum 26, 237–250 (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Boros, E., Hammer, P.L., Sun, R., Tavares, G.: A max-flow approach to improved lower bounds for quadratic 0-1 minimization. Discrete Optimization 5(2), 501–529 (2008)
Boros, E., Hammer, P.L., Tavares, G.: Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO). Journal of Heuristics 13, 99–132 (2007)
Alkhamis, T.M., Hasan, M., Ahmed, M.A.: Simulated annealing for the unconstrained binary quadratic pseudo-boolean function. European Journal of Operational Research 108, 641–652 (1998)
Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. In: Working Paper, The Management School, Imperial College, London, England (1998)
Katayama, K., Narihisa, H.: Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem. European Journal of Operational Research 134, 103–119 (2001)
Glover, F., Kochenberger, G.A., Alidaee, B.: Adaptive memory tabu search for binary quadratic programs. Management Science 44, 336–345 (1998)
Palubeckis, G.: Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Annals of Operations Research 131, 259–282 (2004)
Palubeckis, G.: Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17(2), 279–296 (2006)
Glover, F., Lü, Z., Hao, J.K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR (2010); doi: 10.1007/s10288-009-0115-y
Merz, P., Freisleben, B.: Genetic algorithms for binary quadratic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), pp. 417–424. Morgan Kaufmann, San Francisco (1999)
Lodi, A., Allemand, K., Liebling, T.M.: An evolutionary heuristic for quadratic 0-1 programming. European Journal of Operational Research 119(3), 662–670 (1999)
Katayama, K., Tani, M., Narihisa, H.: Solving large binary quadratic programming problems by an effective genetic local search algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000), pp. 643–650. Morgan Kaufmann, San Francisco (2000)
Borgulya, I.: An evolutionary algorithm for the binary quadratic problems. Advances in Soft Computing 2, 3–16 (2005)
Amini, M., Alidaee, B., Kochenberger, G.A.: A scatter search approach to unconstrained quadratic binary programs. In: New Methods in Optimization, pp. 317–330. McGraw-Hill, New York (1999)
Merz, P., Katayama, K.: Memetic algorithms for the unconstrained binary quadratic programming problem. BioSystems 78, 99–118 (2004)
Moscato, P.: Memetic algorithms: a short introduction. In: New Ideas in Optimization, pp. 219–234. Mcgraw-Hill Ltd., Maidenhead (1999)
Hoos, H., Stützle, T.: Stochastic Local Search Foundations and Applications. Morgan Kaufmann / Elsevier (2004)
Glover, F., Hao, J.K.: Efficient evaluations for solving large 0-1 unconstrained quadratic optimization problems. To appear in International Journal of Metaheuristics 1(1) (2009)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Boston (1997)
Syswerda, G.: Uniform crossover in genetic algorithms. In: Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2–9 (1989)
Lü, Z., Hao, J.K.: A memetic algorithm for graph coloring. European Journal of Operational Research 203(1), 241–250 (2010)
Beasley, J.E.: Obtaining test problems via internet. Journal of Global Optimization 8, 429–433 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lü, Z., Hao, JK., Glover, F. (2010). A Study of Memetic Search with Multi-parent Combination for UBQP. In: Cowling, P., Merz, P. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2010. Lecture Notes in Computer Science, vol 6022. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12139-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-12139-5_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12138-8
Online ISBN: 978-3-642-12139-5
eBook Packages: Computer ScienceComputer Science (R0)