Decomposition-based evolutionary algorithm with automatic estimation to handle many-objective optimization problem. (English) Zbl 1475.90141
Summary: In many-objective optimization problems (MaOPs), the decomposition-based algorithms are widely used since they have promising performances in maintaining the diversity of solutions. However, few studies have been reported on how to utilize relationships between subproblems to promote global convergence. To fill this gap, we develop an automatic estimation mechanism based on the modified Ant Colony Algorithm to assist the co-evolution between subproblems, where two species of ants are designed. The working-ants execute local exploitation by recording the information of subproblems. The command-ants control global exploration by adjusting co-evolution between working-ants. Moreover, the automatic estimation mechanism is expanded into three modes to verify the more efficient one, and they are embedded separately in the decomposition-based algorithm to construct the combined algorithms. The proposed algorithms are compared with five state-of-the-art algorithms on multiple test suites. The experimental results show that the proposed algorithms perform comparably or better than all referenced algorithms. Given the better performance of the proposed algorithms, it is evident that the hybrid mechanism may be a potential manner to handle MaOPs.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C29 | Multi-objective and goal programming |
Keywords:
many-objective optimization; automatic estimation; subproblem relationship; decomposition-based algorithmReferences:
| [1] | K. Deb, Multi-objective optimization, in: Search methodologies, Springer, 2014, pp. 403-449. |
| [2] | J. Garcia, A. Berlanga, J.M.M. LÓpez, Effective evolutionary algorithms for many-specifications attainment: Application to air traffic control tracking filters, IEEE Transactions on Evolutionary Computation 13 (1) (2009) 151-168. |
| [3] | Tahmasebi, S.; Moradi, P.; Ghodsi, S.; Abdollahpouri, A., An ideal point based many-objective optimization for community detection of complex networks, Information Sciences, 502, 125-145 (2019) · Zbl 1453.90153 |
| [4] | J. Zhou, L. Gao, X. Yao, C. Zhang, F.T. Chan, Y. Lin, Evolutionary many-objective assembly of cloud services via angle and adversarial direction driven search, Information Sciences 513 (2020) 143-167. doi:10.1016/j.ins.2019.10.054. |
| [5] | Vamvakas, P.; Tsiropoulou, E. E.; Papavassiliou, S., Dynamic provider selection & power resource management in competitive wireless communication markets, Mobile Networks and Applications, 23, 1, 86-99 (2018) |
| [6] | M.R. Musku, A.T. Chronopoulos, D.C. Popescu, Joint rate and power control using game theory, in: CCNC 2006. 2006 3rd IEEE Consumer Communications and Networking Conference, 2006, vol. 2, IEEE, 2006, pp. 1258-1262. |
| [7] | Goodman, D. J.; Mandayam, N. B., Power control for wireless data, IEEE Personal Communications, 7, 2, 48-54 (2000) |
| [8] | E.E. Tsiropoulou, G.K. Katsinis, S. Papavassiliou, Utility-based power control via convex pricing for the uplink in CDMA wireless networks, in: 2010 European Wireless Conference (EW), IEEE, 2010. doi:10.1109/ew.2010.5483417. |
| [9] | Purshouse, R. C.; Fleming, P. J., On the evolutionary optimization of many conflicting objectives, IEEE Transactions on Evolutionary Computation, 11, 6, 770-784 (2007) |
| [10] | Li, M.; Yang, S.; Liu, X., Shift-based density estimation for pareto-based algorithms in many-objective optimization, IEEE Transactions on Evolutionary Computation, 18, 3, 348-365 (2014) |
| [11] | Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints, IEEE Transactions on Evolutionary Computation, 18, 4, 577-601 (2014) |
| [12] | Adra, S. F.; Fleming, P. J., Diversity management in evolutionary many-objective optimization, IEEE Transactions on Evolutionary Computation, 15, 2, 183-195 (2011) |
| [13] | M. Črepinšek, S.-H. Liu, M. Mernik, Exploration and exploitation in evolutionary algorithms: A survey, ACM Computing Surveys (CSUR) 45 (3) (2013) 35. · Zbl 1293.68251 |
| [14] | Farina, M.; Amato, P., On the optimal solution definition for many-criteria optimization problems, in, (Proceedings of the NAFIPS-FLINT international conference (2002)), 233-238 |
| [15] | Zou, X.; Chen, Y.; Liu, M.; Kang, L., A new evolutionary algorithm for solving many-objective optimization problems, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38, 5, 1402-1412 (2008) |
| [16] | Kollat, J. B.; Reed, P. M., Comparing state-of-the-art evolutionary multi-objective algorithms for long-term groundwater monitoring design, Advances in Water Resources, 29, 6, 792-807 (2006) |
| [17] | Cai, D.; Yuping, W., A new uniform evolutionary algorithm based on decomposition and cdas for many-objective optimization, Knowledge-Based Systems, 85, 131-142 (2015) |
| [18] | Zhang, Q.; Li, H., Moea/d: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11, 6, 712-731 (2007) |
| [19] | Bader, J.; Zitzler, E., Hype: An algorithm for fast hypervolume-based many-objective optimization, Evolutionary Computation, 19, 1, 45-76 (2011) |
| [20] | While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, IEEE Transactions on Evolutionary Computation, 16, 1, 86-95 (2012) |
| [21] | Rostami, S.; Neri, F., Covariance matrix adaptation pareto archived evolution strategy with hypervolume-sorted adaptive grid algorithm, Integrated Computer-Aided Engineering, 23, 4, 313-329 (2016) |
| [22] | Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (International Conference on Parallel Problem Solving from Nature (2004), Springer), 832-842 |
| [23] | Rudolph, G.; Schütze, O.; Grimme, C.; Trautmann, H., An aspiration set emoa based on averaged hausdorff distances, (International Conference on Learning and Intelligent Optimization (2014), Springer), 153-156 |
| [24] | Tian, Y.; Cheng, R.; Zhang, X.; Cheng, F.; Jin, Y., An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility, IEEE Transactions on Evolutionary Computation, 22, 4, 609-622 (2018) |
| [25] | J. Luo, X. Huang, Y. Yang, X. Li, J. Feng, A many-objective particle swarm optimizer based on indicator and direction vectors for many-objective optimization, Information Sciences 514 (2020) 166-202. doi:10.1016/j.ins.2019.11.047. · Zbl 1457.90146 |
| [26] | Pamulapati, T.; Mallipeddi, R.; Suganthan, P. N., \( I_{\operatorname{SDE}}^+\) an indicator for multi and many-objective optimization, IEEE Transactions on Evolutionary Computation, 23, 2, 346-352 (2019) |
| [27] | A. Díaz-Manríquez, G. Toscano-Pulido, C.A.C. Coello, R. Landa-Becerra, A ranking method based on the r2 indicator for many-objective optimization, in: 2013 IEEE Congress on Evolutionary Computation, IEEE, 2013, pp. 1523-1530. |
| [28] | Liu, Y.; Qin, H.; Zhang, Z.; Yao, L.; Wang, C.; Mo, L.; Ouyang, S.; Li, J., A region search evolutionary algorithm for many-objective optimization, Information Sciences, 488, 19-40 (2019) · Zbl 1451.90145 |
| [29] | Zhao, H.; Zhang, C., An online-learning-based evolutionary many-objective algorithm, Information Sciences, 509, 1-21 (2020) · Zbl 1456.90153 |
| [30] | Xiang, Y.; Zhou, Y.; Tang, L.; Chen, Z., A decomposition-based many-objective artificial bee colony algorithm, IEEE Transactions on Cybernetics, 49, 1, 287-300 (2017) |
| [31] | Ishibuchi, H.; Setoguchi, Y.; Masuda, H.; Nojima, Y., Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes, IEEE Transactions on Evolutionary Computation, 21, 2, 169-190 (2016) |
| [32] | Zhou, A.; Zhang, Q., Are all the subproblems equally important? Resource allocation in decomposition based multiobjective evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 20, 1, 52-64 (2016) |
| [33] | Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, man, and cybernetics, Part B: Cybernetics, 26, 1, 29-41 (1996) |
| [34] | Gambardella, L. M.; Taillard, D.; Dorigo, M., Ant colonies for the quadratic assignment problem, Journal of the Operational Research Society, 50, 2, 167-176 (1999) · Zbl 1054.90621 |
| [35] | M.G. Ippolito, E.R. Sanseverino, F. Vuinovich, Multiobjective ant colony search algorithm optimal electrical distribution system planning, in: Congress on Evolutionary Computation, 2004. |
| [36] | Hui, L.; Landa-Silva, D.; Gandibleux, X., Evolutionary multi-objective optimization algorithms with probabilistic representation based on pheromone trails, Evolutionary Computation (2010) |
| [37] | Chen, L.; Liu, H.-L.; Tan, K. C.; Cheung, Y.-M.; Wang, Y., Evolutionary many-objective algorithm using decomposition-based dominance relationship, IEEE Transactions on Cybernetics, 49, 12, 4129-4139 (2019) |
| [38] | Dorigo, M.; Birattari, M., Ant Colony Optimization (2010), Springer |
| [39] | Sun, Y.; Yen, G. G.; Yi, Z., Igd indicator-based evolutionary algorithm for many-objective optimization problems, IEEE Transactions on Evolutionary Computation, 23, 2, 173-187 (2018) |
| [40] | Xiang, Y.; Zhou, Y.; Li, M.; Chen, Z., A vector angle-based evolutionary algorithm for unconstrained many-objective optimization, IEEE Transactions on Evolutionary Computation, 21, 1, 131-152 (2017) |
| [41] | K. Deb, L. Thiele, M. Laumanns, E. Zitzler, Scalable Test Problems for Evolutionary Multiobjective Optimization, 2001. · Zbl 1078.90567 |
| [42] | Huband, S.; Barone, L.; While, L.; Hingston, P., A scalable multi-objective test problem toolkit, Lecture Notes in Computer Science, 3410, 280-295 (2005) · Zbl 1109.68603 |
| [43] | Li, H.; Deb, K.; Zhang, Q.; Suganthan, P.; Chen, L., Comparison between moea/d and nsga-iii on a set of novel many and multi-objective benchmark problems with challenging difficulties, Swarm and Evolutionary Computation, 46, 104-117 (2019) |
| [44] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002) |
| [45] | H. Ishibuchi, H. Masuda, Y. Tanigaki, Y. Nojima, Difficulties in specifying reference points to calculate the inverted generational distance for many-objective optimization problems, in: 2014 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making (MCDM), IEEE, 2014, pp. 170-177. |
| [46] | Wang, H.; Jin, Y.; Yao, X., Diversity assessment in many-objective optimization, IEEE Transactions on Cybernetics, 47, 6, 1510-1522 (2017) |
| [47] | Li, K.; Deb, K.; Zhang, Q.; Kwong, S., An evolutionary many-objective optimization algorithm based on dominance and decomposition, IEEE Transactions on Evolutionary Computation, 19, 5, 694-716 (2014) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
