Multi-Case Multi-Objective Simulated Annealing (MC-MOSA): New Approach to Adapt Simulated Annealing to Multi-objective Optimization

Authors: Abdelfatteh Haidine, Ralf Lehnert

Abstract:

In this paper a new approach is proposed for the adaptation of the simulated annealing search in the field of the Multi-Objective Optimization (MOO). This new approach is called Multi-Case Multi-Objective Simulated Annealing (MC-MOSA). It uses some basics of a well-known recent Multi-Objective Simulated Annealing proposed by Ulungu et al., which is referred in the literature as U-MOSA. However, some drawbacks of this algorithm have been found, and are substituted by other ones, especially in the acceptance decision criterion. The MC-MOSA has shown better performance than the U-MOSA in the numerical experiments. This performance is further improved by some other subvariants of the MC-MOSA, such as Fast-annealing MC-MOSA, Re-annealing MCMOSA and the Two-Stage annealing MC-MOSA.

Keywords: Simulated annealing, multi-objective optimization, acceptance decision criteria, re-annealing, two-stage annealing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331259

References:

[1] E. Zitzler, "Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications," PhD Thesis at the Swiss Federal Institute of Technology Zurich, Zurich, Switzerland, November 1999
[2] J. D. Knowles, "Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization," PhD Thesis at the Department of Computer Science, The University of Reading, Reading, UK, January, 2002
[3] P. Serafini, "Simulated Annealing for Multiobjective Optimization Problems," in Proc. of the 10th International Conference on Multiple Criteria Decision Making, Taipei Taiwan, pp. 87-96, 1992.
[4] E. L. Ulungu, J. Teghem, P. H. Fortemps and D. Tuyttens, "MOSA Method: A Tool for Solving Multiobjective Combinatorial Optimization Problems," Journal of Multicriteria Decision Analysis, Vol. 8, pp. 221- 236, 1999
[5] P. Czyzak and A. Jaszkiewicz, "Pareto Simulated Annealing - a Metaheuristic for Multiple-Objective Combinatorial Optimization," Journal of Multi-Criteria Decision Analysis, Vol. 7, No. 1, pp. 34-47, 1998
[6] A. Jaszkiewicz, M. Hapke and P. Kominek, "Performance of Multiple Objective Evolutionary Algorithms on a Distribution System Design Problem - Computational Experiment," in Proc. of the First International Conference Evolutionary Multi-Criterion Optimization (EMO 2001), Zurich, Switzerland, March 7-9, 2001,
[7] M. P. Hansen, "Tabu Search for Multiobjective Optimization: MOTS," Technical Report Presented in Proc. of 13th International Conference on MCDM, Technical University of Denmark, 1997.
[8] V. Barichard, "Approches Hybrides pour les Problmes Multiobjectifs," PhD Thesis at the Ecole Doctorale d-Angers, University of Angers, Angers, France, November, 2003
[9] J. D. Schaffer, "Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Genetic Algorithms and Their Applications," in Proc. of the First International Conference on Genetic Algorithms, pp. 93-100, 1985.
[10] C. M. Fonseca and P. J. Fleming, "Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization," in Proc. of the Fifth International Conference on Genetic Algorithms, pp. 416-423, San Mateo, USA, 1993.
[11] J. Horn, N. Nafpliotis and D. E. Goldberg, "A Niched Pareto Genetic Algorithm for Multiobjective Optimization," in Proc. of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Piscataway USA, pp. 82-87, 1994
[12] N. Srivivas and K. Deb, "Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms," Evolutionary Computation, Vol. 2, No. 3, pp. 221-248, 1995
[13] K. Deb, A. Pratap, S. Agrawal and T. Meyarivan, "A Fast and Elitist Multiobjective Genetic Algorithm for Multi-Objective Optimization: NSGA-II," IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, April 2002.
[14] E. Zitzler and L. Thiele, "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach," IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271, 1999
[15] E. Zitzler, N. Laumanns and L. Thiele, "SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization," in Proc. of Conf. on Evolutionary Methods for Design, Optimization, and Control, Barcelona, Spain, pages 95-100, 2002
[16] E. Zitzler, M. Laumanns and S. Bleuler, "A Tutorial on Evolutionary Multiobjective Optimization," in Metaheuristics for Multiobjective Optimization, pages 3-38, Springer-Verlag, Berlin, Germany, 2004
[17] H. Ishibuchi and T. Murata, "Multi-objective genetic local search algorithm," in Proc. of 3rd IEEE International Conference on Evolutionary Computation (ICEC-96), pp. 119-124, IEEE, 1996.
[18] A. Jaszkiewicz, "Genetic Local Search for Multiple Objective Combinatorial Optimization," European Journal of Operational Research, 137(1), pp. 50-71, 2002.
[19] H. Ishibuchi, T. Yoshida and T. Murata, "Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling," IEEE Transactions on Evolutionary Computation, Vol. 7, Issue 2, pp. 204- 223, April 2003
[20] A. Jaszkiewicz, "Multiple Objective Metaheuristic Algorithms for Combinatorial Optimization," Habilitation Thesis 360, Poznan University of Technology, Poznan, Poland, 2001
[21] C. Gil, R. Banos, M. G. Montoya and J. Gomez, "Performance of Simulated Annealing, Tabu Search, and Evolutionary Algorithms for Multi-objective Network Partitioning," Algorithmic Operations Research, Vol.1 (2006) pp.55-64.
[22] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, pp. 671-680, 1983
[23] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller, "Equation of State Calculation by Fast Computing Machines," Journal of Chemical Physics, vol. 21, pp. 1087-1092, 1953
[24] I. H. Osman, "Heuristics for the Generalized Assignment Problem: Simulated Annealing and Tabu Search Approaches," OR Spektrum, Vol 17, pp. 211-225, 1995
[25] S. Martello and P. Toth, "Knapsack Problem: Algorithms and Computer Implementations, John Wiley & Sons, 1990
[26] A. Jaszkiewicz, "Multiple Objective MetaHeuristics Library in C++ MOMHLib++," Free Source Code Library, Institute of Computing Science, Poznan University of Technology, Poznan, Poland, 2001.