MODIFICATION OF FIREWORKS METHOD FOR MULTIOBJECTIVE OPTIMIZATION BASED ON NON-DOMINATED SORTING

The article suggests a modification for numerical fireworks method of the single-objective optimization for solving the problem of multiobjective optimization. The method is metaheuristic. It does not guarantee finding the exact solution, but can give a good approximate result. Multiobjective optimization problem is considered with numerical criteria of equal importance. A possible solution to the problem is a vector of real numbers. Each component of the vector of a possible solution belongs to a certain segment. The optimal solution of the problem is considered a Pareto optimal solution. Because the set of Pareto optimal solutions can be infinite; we consider a method for finding an approximation consisting of a finite number of Pareto optimal solutions. The modification is based on the procedure of non-dominated sorting. It is the main procedure for solutions search. Non-dominated sorting is the ranking of decisions based on the values of the numerical vector obtained using the criteria. Solutions are divided into disjoint subsets. The first subset is the Pareto optimal solutions, the second subset is the Pareto optimal solutions if the first subset is not taken into account, and the last subset is the Pareto optimal solutions if the rest subsets are not taken into account. After such a partition, the decision is made to create new solutions. The method was tested on well-known bi-objective optimization problems: ZDT2, LZ01. Structure of the location of Pareto optimal solutions differs for the problems. LZ01 have complex structure of Pareto optimal solutions. In conclusion, the question of future research and the issue of modifying the method for problems with general constraints are discussed.

multiobjective optimization, metaheuristic algorithms, non-dominated sorting, Pareto efficiency, Pareto optimality, decision making

1. Arias-Montano, A., Coello Coello, A.C. and Mezura-Montes, E. (2012). Multiobjective evolutionary algorithms in aeronautical and aerospace engineering. IEEE Transactions on Evolutionary Computation, vol. 16, iss. 5, pp. 662–694. DOI: 10.1109/TEVC.2011.2169968

2. Multi-objective optimization. Techniques and applications in chemical engineering (2017). Ed. G.P. Rangaiah. 2nd еd. World Scientific, 588 p. DOI: 10.1142/10240

3. Berezkin, V.E., Lotov, A.V. and Lotova, E.A. (2014). Study of hybrid methods for approximating the Edgeworth-Pareto hull in nonlinear multicriteria optimization problems. Computational mathematics and mathematical physics, vol. 54, no. 6, pp. 919–930. DOI: 10.7868/S0044466914060039

4. Podinovskij, V.V. and Nogin, V.D. (1982). Pareto-optimalnyye resheniya mnogokriterialnkyh zadach [Pareto optimal solutions of multiobjective problems]. Moscow: Nauka, 256 p. (in Russian)

5. Tan, Y. and Zhu, Y. (2010). Fireworks algorithm for optimization. In: Tan Y., Shi Y., Tan K.C. (eds.). Advances in Swarm Intelligence. First International Conference, ICSI 2010, Beijing, China, June 12–15, 2010, Proceedings, Part I. ICSI 2010. Lecture Notes in Computer Science, vol. 6145. Berlin, Heidelberg: Springer, pp. 355–364. DOI: 10.1007/978-3-642-13495-1_44

6. Handbook of Metaheuristics (2003). Ed. F. Glover and G.A. Kochenberger. New-York; Boston; Moscow: Kluwer Academic Publishers, 557 p.

7. Panteleev, A.V. and Krychkov, A.U. (2017). Metaheuristic optimization methods for parameters estimation of dynamical systems. Civil Aviation High Technologies, vol. 20, no. 2, pp. 37–45. DOI: 10.26467/2079-0619-2017-20-2-37-45 (in Russian)

8. Fortin F.-A., Grenier S. and Parizeau M. (2013). Generalizing the improved run-time complexity algorithm for non-dominated sorting. GECCO '13. Proceedings of the 15th annual conference on Genetic and evolutionary computation. Amsterdam, The Netherlands – July 06–10, 2013, pp. 615–622. DOI: 10.1145/2463372.2463454

9. Buzdalov, M. and Shalyto, A. (2014). A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. Parallel Problem Solving from Nature – PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13–17, 2014. Proceedings. Cham: Springer International Publishing, pp. 528–537. DOI: 10.1007/978-3-319-10762-2_52

10. Zitzler, E. and Thiele, L. (1998). Multiobjective optimization using evolutionary algorithms – a comparative case study. Parallel Problem Solving from Nature – PPSN V. 5th International Conference Amsterdam, The Netherlands September 27–30, 1998, pp. 292–301. DOI: 10.1007/BFb0056872

11. Zitzler, E., Deb, K. and Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: empirical results. Evolutionary Computation, vol. 8, no. 2, pp. 173–195. DOI: 10.1162/106365600568202

12. Li, H. and Zhang, Q. (2009). Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation, vol. 13, iss. 2, April, pp. 284–302. DOI: 10.1109/TEVC.2008.925798

13. Amuso, V.J. and Enslin, J. (2007). The Strength Pareto Evolutionary Algorithm 2 (SPEA2) applied to simultaneous multi-mission waveform design. 2007 International waveform diversity and design conference, Pisa, pp. 407–417. DOI: 10.1109/WDDC.2007.4339452

14. Jain, H. and Deb, K. (2014). An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach. Part II: Handling constraints and extending to an adaptive approach. IEEE Transactions on evolutionary computation, vol. 18, iss. 4, Aug., pp. 602–622. DOI: 10.1109/TEVC.2013.2281534