Multi-Case Multi-Objective Simulated Annealing (MC-MOSA): New Approach to Adapt Simulated Annealing to Multi-objective Optimization
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:53064", author = "Abdelfatteh Haidine and Ralf Lehnert", title = "Multi-Case Multi-Objective Simulated Annealing (MC-MOSA): New Approach to Adapt Simulated Annealing to Multi-objective Optimization", 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.", volume = "2", number = "12", pages = "4061-9", }
