Keywords
metaheuristics
tabu search
scatter search
nonlinear optimization
Objetivos múltiples
metaheurísticas
búsqueda tabú
búsqueda dispersa
optimización no lineal
How to Cite
Abstract
This paper introduces two variants of a multiple criteria scatter search to deal with nonlinear continuous and combinatorial problems, applying a tabu search approach as a diversification generator method. Frequency memory and another escape mechanism are used to diversify the search. A Pareto relation is applied in order to designate a subset of the best generated solutions to be reference solutions. A choice function called Kramer Choice is used to divide the reference solution in two subsets. Euclidean and Hamming distances are used as measures of dissimilarity in order to find diverse solutions to complement the subsets of high quality current Pareto solutions to be combined. Linear combination and path relinking are used as a combination methods. The performance of these approaches are evaluated on several test problems taken from the literature.
References
Balas, E. “Machine sequencing via disjunctive graphs: an implicit enumeration algorithm”, Ops.Res 17 (6): 927–1136.
Beausoleil, R.P. (2001) “Multiple criteria scatter search”, MIC’2001-4th Metaheuristics International Conference. Porto, Portugal.
Beausoleil, R.P. (2002) “A tabu search approach for weighted tardiness with sequence-dependent setups in one-machine problem”, Revista de Matemática: Teoŕıa y Aplicaciones 9(1): 35–46.
Beausoleil, R. (2004) “Bounded Variables Nonlinear Multiple Criteria Optimization using Scatter Search”, Revista de Matemática: Teoŕıa y Aplicaciones 11 (1): 17–40.
Coello, C.A.; Toscano P.G. (2001) “A micro-genetic algorithm for multiobjective optimization”, In: E. Zitzler, K. Deb, L. Thiele, C.A. Coello & D. Corne (Eds.), First International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Sciences No.1993, Springer-Verlag: 216–140
Deb, K.; Agrawal, S.; Pratab, A.; Mayariban, T. (2000) “A fast elitist non-sorting genetic algorithms for multi-objective optimization”, NSGA-II, KanGal, report 200001, Indian Institute of Technology, Kanpur, India.
Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E. (2001) “Scalable test problems for evolutionary multi-objective optimization”, TIK-Tecnical Report (112).
Laarhoven P.J.; Aarts E.H.; Lenstra J.K. (1998) “Job shop scheduling by simulated anneling”, Report OS, Centre for Mathématiques, Ecole Polytechnique Fédérale de Lausanne.
Glover, F. (1998) “A template for scatter search and path relinking in artificial evolution”, Lecture Notes in Computer Science (1363): 13–54. J.-K,Hao, E.Lutton, E.Ronald, M.Schoenauer and D.Snyers (Eds), Springer.
Glover, F. (1994) “Tabu search for nonlinear and parametric optimization (with links to genetic algorithms)”, Discrete Applied Mathematics (40): 231–255.
Glover, F.; Laguna M. (1993) “Modern Heuristic Techniques for Combinatorial Problems”, Halsted Press, John Wiley & Sons, Inc.: 70–147.
Glover, F.; Laguna, M.; Mart́ı, R. “Scatter Search Tutorial for a class of non-linear optimization problem on bounded variables”.
Makarov, I.M.; Vinogradskaia, T.M.; Rubinski, A.A; Sokolov, V.B. (1982) Choice Theory and Decision Making. Nauka, Moscu.
Rubin, P.A.; Ragatz, G.L. (1995) “Scheduling in a sequence dependent setup environment with genetic search”, Computers and Operation Research (22): 85–99.
Pratyush, S.; Jian-Bo, Y. (1998) Multiple criteria decision support in engineering design, Springer-Verlag.
Schaffer, J.D. (1985) “Multiple objective optimization with vector evaluated genetic algorithms”, Unpublished doctoral dissertation, Vanderbilt University.
Knowles, J.; Corne, D. (1999) The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multiobjective Optimization. University of Reading, UK.
Schott, J.R. (1995) Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master’s thesis, Departament of Aeronautics, Massachusetts Institute of Technology, Cambrige, Massachusetts.
Schaffer, J.D. (1985) “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms”, In: Genetic Algorithms and their Applications, Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum, Hillsdale, New Jersey: 93–100
Van, V.; Lamont, G.B. (1998) “Evolutionary computation and convergence to a Pareto front”, In: J.R. Koza (Ed.), Late Breaking Papers at the Genetic Programming 1998 Conference, Stanford University, CA: 221–228
Zitzler, E.; Kalyanmoy, D.; Thiele, L. TIK-Report, No.70, December 22, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland.
Zitzler, E.; Laumanns, M.; Thiele, L. (2001) “SPEA2: Improving the strength Pareto evolutionary algorithm”, Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich.