Reference point based archived many objective simulated annealing. (English) Zbl 1443.90309

Summary: Recent research in optimization theory focuses on developing algorithms for the many objective optimization problems. These problems require careful attention to efficiently handle the increasing number of objectives and also to address the various challenges associated with these types of problems. The present study introduces a new unconstrained many-objective optimization algorithm called reference point based many objective simulated annealing algorithm (RSA). The algorithm is an amalgamation of several new modules including a reference point based clustering technique to control the size of the archive which stores the solutions, a novel mutation strategy termed as mutation-switching and a new acceptance probability function. Unlike the existing simulated annealing based multiobjective optimization techniques, the current work explores the use of archive-to-archive transition rather than point-to-point transition. The performance of RSA is validated and compared with many other state-of-the-art algorithms on a number of unconstrained benchmark problems of DTLZ and WFG test suites with up to 15 objectives. The experimental results show that RSA outperforms AMOSA, NSGA-III, MOEA/D-PBI and \(\theta\)-DEA in terms of two well-known performance metrics, namely inverse generational distance (IGD) and hyper-volume (HV), for a majority of the test cases considered . It has also been shown that RSA usually requires fewer number of function evaluations compared to other algorithms for equal or better performance and might thus be more useful for MaOO problems which are expensive in terms of computational time. To illustrate some real-life applications of RSA, in a part of the paper, we have developed a multiobjective clustering technique utilizing RSA as the underlying optimization mechanism which is then used for segmenting satellite images.Obtained results prove the efficacy of RSA in solving the segmentation task.


90C29 Multi-objective and goal programming
Full Text: DOI


[1] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, vol. 16 (2001), John Wiley & Sons · Zbl 0970.90091
[2] Coello, C. A.C.; Van Veldhuizen, D. A.; Lamont, G. B., Evolutionary Algorithms for Solving Multi-Objective Problems, vol. 242 (2002), Springer · Zbl 1130.90002
[3] Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evol Comput, 1, 1, 32-49 (2011)
[4] Lücken, C.; Barán, B.; Brizuela, C., A survey on multi-objective evolutionary algorithms for many-objective problems, Comput. Optim. Appl., 58, 3, 707-756 (2014) · Zbl 1334.90219
[5] Li, B.; Li, J.; Tang, K.; Yao, X., Many-objective evolutionary algorithms: a survey, ACM Comput. Surv., 48, 1, 13:1-13:35 (2015)
[6] Fleming, P. J.; Purshouse, R. C.; Lygoe, R. J., Many-Objective Optimization: An Engineering Design Perspective, 14-32 (2005), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg · Zbl 1109.68596
[7] Herrero, J. G.; Berlanga, A.; López, J. M.M., Effective evolutionary algorithms for many-specifications attainment: application to air traffic control tracking filters, Trans. Evol. Comp, 13, 1, 151-168 (2009)
[8] Lygoe, R. J.; Cary, M.; Fleming, P. J., A Real-World Application of a Many-Objective Optimisation Complexity Reduction Process, 641-655 (2013), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[10] Sayyad, A. S.; Menzies, T.; Ammar, H., On the value of user preferences in search-based software engineering: A case study in software product lines, Proceedings of the 2013 International Conference on Software Engineering. Proceedings of the 2013 International Conference on Software Engineering, ICSE ’13, 492-501 (2013), IEEE Press: IEEE Press Piscataway, NJ, USA
[11] Sülflow, A.; Drechsler, N.; Drechsler, R., Robust Multi-Objective Optimization in High Dimensional Spaces, 715-726 (2007), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[12] Yuan, Y.; Xu, H., Multiobjective flexible job shop scheduling using memetic algorithms, IEEE Trans. Autom. Sci. Eng., 12, 1, 336-353 (2015)
[13] Chikumbo, O.; Goodman, E.; Deb, K., Approximating a multi-dimensional pareto front for a land use management problem: a modified MOEA with an epigenetic silencing metaphor, 2012 IEEE Congress on Evolutionary Computation, 1-9 (2012)
[14] Bandyopadhyay, S.; Saha, S.; Maulik, U.; Deb, K., A simulated annealing-based multiobjective optimization algorithm: AMOSA, IEEE Trans. Evolution. Comput., 12, 3, 269-283 (2008)
[15] Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, Lect. Notes Comput. Sci., 1917, 849-858 (2000)
[16] Knowles, J.; Corne, D., The pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimisation, Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, vol. 1 (1999), IEEE
[17] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evolution. Comput., 11, 6, 712-731 (2007)
[18] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints, Evolution. Comput. IEEE Trans., 18, 4, 577-601 (2014)
[19] Yuan, Y.; Xu, H.; Wang, B.; Yao, X., A new dominance relation-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evolution. Comput., 20, 1, 16-37 (2016)
[20] Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evol Comput, 19, 1, 45-76 (2011)
[21] Yang, S.; Li, M.; Liu, X.; Zheng, J., A grid-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evolution. Comput., 17, 5, 721-736 (2013)
[22] Bader, J.; Brockhoff, D.; Welten, S.; Zitzler, E., On Using Populations of Sets in Multiobjective Optimization, 140-154 (2009), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[23] Das, I.; Dennis, J. E., Normal-boundary intersection: a new method for generating the pareto surface in nonlinear multicriteria optimization problems, SIAM J. Opt., 8, 3, 631-657 (1998) · Zbl 0911.90287
[24] Wang, H.; Yao, X., Corner sort for pareto-based many-objective optimization, IEEE Trans. Cybernetics, 44, 1, 92-102 (2014)
[25] Asafuddoula, M.; Ray, T.; Sarker, R. A., A decomposition-based evolutionary algorithm for many objective optimization, IEEE Trans. Evolution. Comput., 19, 3, 445-460 (2015)
[26] Deb, K.; Agrawal, R. B., Simulated binary crossover for continuous search space, Complex Syst., 9, 1-34 (1994)
[27] Sengupta, R.; Pal, M.; Saha, S.; Bandyopadhyay, S., Population dynamics indicators for evolutionary many-objective optimization, Progress in Intelligent Computing Techniques: Theory, Practice, and Applications, 1-10 (2017), Springer
[28] Qiu, X.; Xu, J. X.; Tan, K. C.; Abbass, H. A., Adaptive cross-generation differential evolution operators for multiobjective optimization, IEEE Trans. Evol. Comput., 20, 2, 232-244 (2016)
[29] Suman, B.; Kumar, P., A survey of simulated annealing as a tool for single and multiobjective optimization, J. Oper. Res. Soc., 57, 18, 1143-1160 (2006) · Zbl 1121.90065
[30] Smith, K. I.; Everson, R. M.; Fieldsend, J. E., Dominance measures for multi-objective simulated annealing, Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2004, 19-23 June 2004, Portland, OR, USA, 23-30 (2004)
[31] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multiobjective optimization, Evolution. Multiobject. Opt., 105-145 (2005) · Zbl 1078.90567
[32] Huband, S.; Hingston, P.; Barone, L.; While, R. L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evolution. Comput., 10, 5, 477-506 (2006)
[33] Ishibuchi, H.; Setoguchi, Y.; Masuda, H.; Nojima, Y., Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes, IEEE Trans. Evolution. Comput., 21, 2, 169-190 (2017)
[34] Gómez, R. H.; Coello, C. A.C., MOMBI: A new metaheuristic for many-objective optimization based on the R2 indicator, Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2013, Cancun, Mexico, June 20-23, 2013, 2488-2495 (2013)
[36] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Hypervolume-based multiobjective optimization: theoretical foundations and practical implications, Theor. Comput. Sci., 425, 75-103 (2012) · Zbl 1242.90205
[37] He, Z.; Yen, G. G., Visualization and performance metric in many-objective optimization, IEEE Trans. Evolution. Comput., 20, 3, 386-402 (2016)
[38] Peng, W.; Zhang, Q., A decomposition-based multi-objective particle swarm optimization algorithm for continuous optimization problems, The 2008 IEEE International Conference on Granular Computing, GrC 2008, Hangzhou, China, 26-28 August 2008, 534-537 (2008)
[39] Bader, J.; Zitzler, E., A Hypervolume-Based Optimizer for High-Dimensional Objective Spaces, 35-54 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[40] Lpez-Ibez, M.; Dubois-Lacoste, J.; Cceres, L. P.; Birattari, M.; Sttzle, T., The irace package: iterated racing for automatic algorithm configuration, Oper. Res. Perspect., 3, Supplement C, 43-58 (2016)
[41] Hutter, F.; Stützle, T.; Leyton-Brown, K.; Hoos, H. H., ParamILS: an automatic algorithm configuration framework, CoRR, abs/1401.3492 (2014) · Zbl 1192.68831
[42] Saha, S.; Bandyopadhyay, S., Unsupervised pixel classification in satellite imagery using a new multiobjective symmetry based clustering approach, TENCON 2008 - 2008 IEEE Region 10 Conference, 1-6 (2008)
[43] Bandyopadhyay, S.; Saha, S., Gaps: a clustering method using a new point symmetry-based distance measure, Pattern Recognit., 40, 12, 3430-3451 (2007) · Zbl 1122.68486
[44] Maulik, U.; Bandyopadhyay, S., Performance evaluation of some clustering algorithms and validity indices, IEEE Trans. Pattern Anal. Mach. Intell., 24, 12, 1650-1654 (2002)
[45] Shah, R. A.; Reed, P. M.; Simpson, T. W., Many-Objective Evolutionary Optimisation and Visual Analytics for Product Family Design, 137-159 (2011), Springer London: Springer London London
[46] Fang, H.; Rais-Rohani, M.; Liu, Z.; Horstemeyer, M. F., A comparative study of metamodeling methods for multiobjective crashworthiness optimization, Comput. Struct., 83, 25, 2121-2136 (2005)
[47] Pierro, F.d.; Khu, S.-T.; Savi, D.; Berardi, L., Efficient multi-objective optimal design of water distribution networks on a budget of simulations using hybrid algorithms, Environ. Modell. Softw., 24, 2, 202-213 (2009)
[48] Tesch, M.; Schneider, J.; Choset, H., Expensive multiobjective optimization for robotics, 2013 IEEE International Conference on Robotics and Automation, 973-980 (2013)
[49] Nourani, Y.; Andresen, B., A comparison of simulated annealing cooling strategies, J. Phys. A Math. Gen., 31, 41, 8373 (1998) · Zbl 0962.82068
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.