A multi-objective particle swarm optimizer based on decomposition

ABSTRACT

The simplicity and success of particle swarm optimization (PSO) algorithms, has motivated researchers to extend the use of these techniques to the multi-objective optimization field. This paper presents a multi-objective particle swarm optimization (MOPSO) algorithm based on a decomposition approach, which is intended for solving continuous and unconstrained multi-objective optimization problems (MOPs). The proposed decomposition-based multi-objective particle swarm optimizer (dMOPSO), updates the position of each particle using a set of solutions considered as the global best according to the decomposition approach. dMOPSO is mainly characterized by the use of a memory reinitialization process which aims to provide diversity to the swarm. Our proposed approach is compared with respect to two decomposition-based multi-objective evolutionary algorithms (MOEAs) which are representative of the state-of-the-art in the area. Our results indicate that our proposed approach is competitive and it outperforms the two MOEAs with respect to which it was compared in most of the test problems adopted.

References

1. M. Clerc. Confinements and Biases in Particle Swarm Optimisation, 2006.
2. I. Das. Nonlinear Multicriteria Optimization and Robust Optimality. PhD thesis, Rice University, Houston, Texas, 1997.
3. I. Das and J. E. Dennis. Normal-boundary intersection: a new method for generating Pareto optimal points in multicriteria optimization problems. SIAM Journal on Optimization, 8(3):631--657, 1998.
4. L. N. de Castro and J. Timmis. Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002.
5. K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Test Problems for Evolutionary Multiobjective Optimization. In A. Abraham, L. Jain, and R. Goldberg, editors, Evolutionary Multiobjective Optimization. Theoretical Advances and Applications, pages 105--145. Springer, USA, 2005.
6. R. C. Eberhart, J. Kennedy, and Y. Shi. Swarm Intelligence. Morgan Kaufmann, 1st edition, April 2001.
7. M. Ehrgott. Multicriteria Optimization. Springer, Berlin, 2nd edition edition, June 2005.
8. C. M. Fonseca and P. J. Fleming. Multiobjective Genetic Algorithms Made Easy: Selection, Sharing, and Mating Restriction. In Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, pages 42--52, Sheffield, UK, September 1995. IEE.
9. F. Glover, M. Laguna, and R. Martín. Fundamentals of scatter search and path relinking. Control and Cybernetics, 39:653--684, 2000.
10. J. Kennedy. Bare bones particle swarms. In Swarm Intelligence Symposium, 2003. SIS '03. Proceedings of the 2003 IEEE, pages 80--87, April 2003.
11. J. Kennedy and R. C. Eberhart. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, pages 1942--1948, 1995.
12. J. Knowles and D. Corne. Properties of an Adaptive Archiving Algorithm for Storing Nondominated Vectors. IEEE Transactions on Evolutionary Computation, 7(2):100--116, April 2003.
13. M. Laumanns, L. Thiele, E. Zitzler, and K. Deb. Archiving with Guaranteed Convergence and Diversity in Multi-Objective Optimization. In W. L. et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'2002), pages 439--447, San Francisco, California, July 2002. Morgan Kaufmann Publishers.
14. K. Miettinen. Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston, Massachuisetts, 1999.
15. N. A. Moubayed, A. Petrovski, and J. A. W. McCall. A novel smart multi-objective particle swarm optimisation using decomposition. In PPSN (2), pages 1--10, 2010.
16. W. Peng and Q. Zhang. A decomposition-based multi-objective particle swarm optimization algorithm for continuous optimization problems. In IEEE International Conference on Granular Computing, 2008. GrC 2008, pages 534 --537, 2008.
17. M. Reyes Sierra and C. A. Coello Coello. Improving PSO-Based Multi-objective Optimization Using Crowding, Mutation and ε-Dominance. In C. A. Coello Coello, A. Hernández Aguirre, and E. Zitzler, editors, Evolutionary Multi-Criterion Optimization. Third International Conference, EMO 2005, pages 505--519, Guanajuato, México, March 2005. Springer. Lecture Notes in Computer Science Vol. 3410.
18. M. Reyes-Sierra and C. A. Coello Coello. Multi-Objective Particle Swarm Optimizers: A Survey of the State-of-the-Art. International Journal of Computational Intelligence Research, 2(3):287--308, 2006.
19. J. R. Schott. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1995.
20. P. Vincke. Multicriteria Decision-Aid. John Wiley & Sons, New York, 1992.
21. Q. Zhang and H. Li. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712--731, December 2007.
22. Q. Zhang, W. Liu, and H. Li. The Performance of a New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances. In 2009 IEEE Congress on Evolutionary Computation (CEC'2009), pages 203--208, Trondheim, Norway, May 2009. IEEE Press.
23. E. Zitzler, K. Deb, and L. Thiele. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2):173--195, Summer 2000.
24. E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In K. Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou, and T. Fogarty, editors, EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pages 95--100, Athens, Greece, 2002.
25. E. Zitzler and L. Thiele. Multiobjective Optimization Using Evolutionary Algorithms--A Comparative Study. In A. E. Eiben, editor, Parallel Problem Solving from Nature V, pages 292--301, Amsterdam, September 1998. Springer-Verlag.
26. E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. da Fonseca. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation, 7(2):117--132, April 2003.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming