Full Text

Abstract

Evolutionary algorithms have been used to solve multi-objective optimization problems of two or three objectives giving results that both converge to the optimal front and are diverse along that front. However, once the number of objectives rises to four and above, the Pareto dominance concept that most of these algorithms are based on loses selection pressure, recombination operations are ineffective as individuals in populations are not close in the problem space and the evaluation of performance measures such as hyper-volume becomes computationally expensive. To overcome the loss in selection pressure, recent evolutionary algorithms adopt a number of techniques which include modifying the dominance relation to increase selection pressure as done with €-dominance, α-dominance and dominance area control, using a secondary selection mechanism such as the shift-based density estimator, grid-based fitness metric or knee-point driven analysis to filter individuals and decomposing the so-called many objective problems into sub-problems to simultaneously solve. The controlling dominance area of solutions, CDAS technique has been found to be effective in generating solutions that converge to the optimal front but leads to a loss in the diversity of the generated solutions. In this paper, we propose an extension to the speed-constrained particle swarm optimizer that uses a relaxed form of dominance, CDAS and the shift-based density estimator as secondary selection mechanism to increase diversity of solutions obtained. Also, the particles in the swarm will have an archive of personal bests from which the selection will be done using the weighted sum approach. Finally, the performance of the algorithm will be compared with state of the art algorithms such as NSGA-III and MOEA/DD using the DTLZ benchmark functions.

References

1. Maltese, J., Ombuki-Berman, B. M., & Engelbrecht, A. P. (2016). A Scalability Study of Many-Objective Optimization Algorithms. IEEE.

2. Sato, H., Aguirre, H. E., & Tanaka, K. (2007). Controlling Dominance Area of Solutions and Its Impact on the Performance of MOEAs. In H. Sato, H. E. Aguirre, & K. Tanaka, Evolutionary Multi-Criterion Optimization (pp. 5-20). Berlin Heidelberg: Springer.

3. Hiroyuki, S., Aguirre, H. E., & Tanaka, K. (2010). Self-Controlling Dominance Area of Solutions in Evolutionary Many-Objective Optimization. In K. Deb, A. Bhattacharya, N. Chakraborti, P. Chakroborty, S. Das, J. Dutta, . . . K. C. Tan, Simulated Evolution and Learning (pp. 455-465). Berlin Heidelberg: Springer.

4. de Carvalho, A. B., &Pozo, A. (2012). Measuring the Convergence and Diversity of CDAS Multi-Objective Particle Swarm Optimization Algorithms: A Study of Many-Objective Problems. International Conference on Hybrid Artificial Intelligence Systems (pp. 43–51). Brazil: Neuro-Computing

5. He, Z., Yen, G. G., & Zhang, J. (2014). Fuzzy-Based Pareto Optimality for Many-Objective Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 269 - 285.

6. Farina, M., & Amato, P. (2004). A Fuzzy Definition of \"Optimality\" for Many-Criteria Optimization Problems. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 315 - 326.

7. di Pierro, F., Khu, S.-T., & Savic, D. A. (2007). A Investigation on Preference Order Ranking Scheme for Multiobjective Evolutionary Optimization. IEEE Transactions on Evolutionary Computation, 17-45.

8. Qiuzhen, L., Liu, S., Zhu, Q., Tang, C., Song, R., Chen, J., Zhang, J. (2016). Particle Swarm Optimization with a Balanceable Fitness Estimation for Many-objective Optimization Problems. IEEE Transactions on Evolutionary Computation, 1-1.

9. Zhang, X., Tian, Y., &Jin, Y. (2014). A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 761 - 776.

10. Li, M., Zheng, J., Shen, R., Li, K., & Yuan, Q. (2010). A Grid-Based Fitness Strategy for Evolutionary Many-Objective Optimization. Proceedings of the 12th annual conference on Genetic and evolutionary computation (pp. 463-470). Oregon: ACM.

11. Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000). A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. Lecture Notes in Computer Science (pp. 849-858). Paris: Springer.

12. Köppen, M., & Yoshida, K. (2007). Substitute Distance Assignments in NSGA-II for Handling Many-objective Optimization Problems. In M. Köppen, & K. Yoshida, Evolutionary Multi-Criterion Optimization (pp. 727-741). Berlin Heidelberg: Springer.

13. Zitzler, E., & Künzli, S. (2004). Indicator-Based Selection in Multiobjective Search. In X. Yao, E. K. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervós, J. A. Bullinaria, H.P. Schwefel, Parallel Problem Solving from Nature - PPSN VIII (pp. 832-842). Berlin Heidelberg: Springer.

14. Bader, J., & Zitzler, E. (2011). HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. Evolutionary Computation, 45-76.

15. Li, B., Tang, K., Li, J., & Yao, X. (2016). Stochastic Ranking Algorithm for Many-Objective Optimization Based on Multiple Indicators. IEEE Transactions on Evolutionary Computation, 924-938

16. Zhang, Q., & Li, H. (2007). MOEA/D: A Multi objective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 712 - 731.

17. Deb, K., & Jain, H. (2014). An Evolutionary Many Objective Optimization Algorithm Using Reference Point-Based Non-Dominated Sorting Approach. IEEE Transactions on Evolutionary Computation, 577-601.

18. Jain, H., & Deb, K. (2014). An Evolutionary Many-Objective Optimization Algorithm using Reference-Point Based Non-Dominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach. IEEE Transactions on Evolutionary Computation, 602-622.

19. Li, K., Deb, K., Qingfu, Z., & Kwong, S. (2014). An Evolutionary Many-Objective Optimization Algorithm Based on Dominance and Decomposition. IEEE Transactions on Evolutionary Computation (pp. 694 - 716). IEEE.

20. Yuan, Y., Xu, H., Wang, B., & Yao, X. (2016). A New Dominance Relation-Based Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 16-37.

21. Britto, A., & Pozo, A. (2012). I-MOPSO: A Suitable PSO Algorithm for Many-Objective Optimization. Brazilian Symposium on Neural Networks (pp. 166-171). IEEE.

22. Padhye, N., Branke, J., & Mostaghim, S. (2009). Empirical comparison of MOPSO methods - Guide selection and diversity preservation. Evolutionary Computation (pp. 2516-2523). IEEE.

23. Li, K., Deb, K., Qingfu, Z., & Kwong, S. (2014). An Evolutionary Many-Objective Optimization Algorithm Based on Dominance and Decomposition. IEEE Transactions on Evolutionary Computation (pp. 694 - 716). IEEE.

24. Li, M., Yang, S., & Liu, X. (2013). Shift-Based Density Estimation for Pareto-Based Algorithms in Many-Objective Optimization. IEEE Transactions on Evolutionary Computation (pp. 348 - 365). IEEE.

Keywords

Particle SwarmOptimizer, Many-Objective, CDAS, SDE, Intelligence.