nach oben

Soft Computing

Erschienen in:

07.09.2015 | Methodologies and Application

Many-objective optimization based on information separation and neighbor punishment selection

verfasst von: Ruimin Shen, Jinhua Zheng, Miqing Li, Juan Zou

Erschienen in: Soft Computing | Ausgabe 5/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Many-objective optimization refers to optimizing a multi-objective optimization problem (MOP) where the number of objectives is more than 3. Most classical evolutionary multi-objective optimization (EMO) algorithms use the Pareto dominance relation to guide the search, which usually perform poorly in the many-objective optimization scenario. This paper proposes an EMO algorithm based on information separation and neighbor punishment selection (ISNPS) to deal with many-objective optimization problems. ISNPS separates individual’s behavior in the population into convergence information and distribution information by rotating the original coordinates in the objective space. Specifically, the proposed algorithm employs one coordinate to reflect individual’s convergence and the remaining \(m-1\) coordinates to reflect individual’s distribution, where m is the number of objectives in a given MOP. In addition, a neighborhood punishment strategy is developed to prevent individuals from being crowded. From a series of experiments on 42 test instances with 3–10 objectives, ISNPS has been found to be very competitive against six representative algorithms in the EMO area.

Vorheriger Artikel Iterative numerical method for fuzzy Volterra linear integral equations in two dimensions

Nächster Artikel Decision making with the generalized intuitionistic fuzzy power interaction averaging operators

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Here the binary tournament selection (Miller and Goldberg 1995) is used as the mating selection.

For MOEA/D, we adopt the original C++ code, which can be obtained at http://dces.essex.ac.uk/staff/zhang/webofmoead.htm.

For NSGA-III, the C++ implemention (version 1.1) from professor Chiang is used in our study, which can be downloaded at web.ntnu.edu.tw/ tcchiang/publications/nsga3cpp/nsga3cpp.htm.

For \(\epsilon \)-MOEA, we adopt the C implemention from KanGAL, which can be downloaded at www.iitk.ac.in/kangal/index.shtml.

For MSOPS, the original MATLAB code is adopted, which can be found at .

For IBEA, the Java implementation in jMetal (Durillo et al. 2010; Durillo and Nebro 2011) project (version 4.5) is utilized, which can be downloaded at .

As suggested by Gómez and Coello Coello (2013), the Monte Carlo simulation is utilized to accelerate the calculation of hypervolume contribution of SMS-EMOA.

Adra SF, Fleming PJ (2009) A diversity management operator for evolutionary many-objective optimisation. In: Evolutionary multi-criterion optimization, pp. 81–94. Springer, Nantes, France. doi:10.1007/978-3-642-01020-0_11

Aguirre HE, Tanaka K (2007) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res 181(3):1670–1690. doi:10.1016/j.ejor.2006.08.004 CrossRefMATH

Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45–76. doi:10.1162/EVCO_a_00009

Bentley PJ, Wakefield JP (1997) Finding acceptable Pareto-optimal solutions using multiobjective genetic algorithms. Soft Comput Eng Des Manuf 5:231–240

Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181(3):1653–1669. doi:10.1016/j.ejor.2006.08.008 CrossRefMATH

Bosman PA, Thierens D (2003) The balance between proximity and diversity in multi-objective evolutionary algorithms. IEEE Trans Evol Comput 7(2):174–188. doi:10.1109/TEVC.2003.810761 CrossRef

Cheney W, Kincaid DR (2010) Linear algebra: theory and applications, 2nd edn. Jones & Bartlett Publishers. ISBN 1449613527, 9781449613525

Coello CA, Lamont GB (2004) Applications of multi-objective evolutionary algorithms. World Scientific Publisher, SingaporeCrossRefMATH

Corne DW, Knowles JD (2007) Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Genetic and evolutionary computation conference, pp. 773–780. London, England, UK. doi:10.1145/1276958.1277115

Das I, Dennis JE (1998) Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim 8(3):631–657. doi:10.1137/S1052623496307510 MathSciNetCrossRefMATH

Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley-interscience series in systems and optimization, 1st edn. Wiley, Chichester, New York

Deb K, Agrawal RB (1994) Simulated binary crossover for continuous search space. Complex Syst 9(2):115–148MathSciNetMATH

Deb K, Goyal M (1996) A combined genetic adaptive search (GeneAS) for engineering design. Comput Sci Inform 26(4):30–45

Deb K, Jain H (2004) An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part I: solving problems with box constraints. IEEE Trans Evol Comput 18(4):577–601. doi:10.1109/TEVC.2013.2281535 CrossRef

Deb K, Jain S (2002) Running performance metrics for evolutionary multi-objective optimization. Tech. Rep. Kangal Report No. 2002004, Indian Institute of Technology

Deb K, Kumar A (1995) Real-coded genetic algorithms with simulated binary crossover: studies on multimodal and multiobjective problems. Complex Syst 9(6):431–454

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197. doi:10.1109/4235.996017 CrossRef

Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multi-objective optimization. In: Evolutionary multiobjective optimization, advanced information and knowledge processing, pp. 105–145. Springer, Berlin. doi:10.1007/1-84628-137-7_6

Drechsler N, Drechsler R, Becker B (2001) Multi-objective optimisation based on relation favour. In: Evolutionary multi-criterion optimization, pp. 154–166. Springer, Berlin. doi:10.1007/3-540-44719-9_11

Durillo JJ, Nebro AJ (2011) jMetal: a java framework for multi-objective optimization. Adv Eng Softw 42:760–771. doi:10.1016/j.advengsoft.2011.05.014 CrossRef

Durillo JJ, Nebro AJ, Alba E (2010) The jMetal framework for multi-objective optimization: design and architecture. In: IEEE congress on evolutionary computation, pp. 4138–4325. Barcelona, Spain. doi:10.1109/CEC.2010.5586354

Farina M, Amato P (2002) On the optimal solution definition for many-criteria optimization problems. In: Proceedings of the NAFIPS-FLINT international conference, pp. 233–238. IEEE Serv Center. doi:10.1109/NAFIPS.2002.1018061

Farina M, Amato P (2004) A fuzzy definition of “optimality” for many-criteria optimization problems. IEEE Trans Syst Man Cybern Part A: Syst Hum 34(3):315–326. doi:10.1109/TSMCA.2004.824873 CrossRef

Glaser RE (1983) Levene’s robust test of homogeneity of variances. Encycl Stat Sci 4:608–610

Gómez RH, Coello CA (2013) MOMBI: a new metaheuristic for many-objective optimization based on the R2 indicator. In: IEEE congress on evolutionary computation, pp. 2488–2495. Cancun. doi:10.1109/CEC.2013.6557868

Huband S, Hingston P, Barone L, While L (2006) A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans Evol Comput 10(5):477–506. doi:10.1109/TEVC.2005.861417 CrossRefMATH

Hughes EJ (2003) Multiple single objective Pareto sampling. In: IEEE congress on evolutionary computation, vol. 4, pp. 2678–2684. IEEE, Canberra, Australia. doi:10.1109/CEC.2003.1299427

Hughes EJ (2005) Evolutionary many-objective optimisation: many once or one many? In: IEEE congress on evolutionary computation, vol. 1, pp. 222–227. IEEE Press. doi:10.1109/CEC.2005.1554688

Ikeda K, Kita H (2001) Failure of Pareto-based MOEAs: does non-dominated really mean near to optimal? IEEE Congr Evol Comput 2:957–962. doi:10.1109/CEC.2001.934293

Inselberg A (1985) The plane with parallel coordinates. Vis Comput 1(4):69–91. doi:10.1007/BF01898350 MathSciNetCrossRefMATH

Inselberg A, Dimsdale B (1990) Parallel coordinates: a tool for visualizing multi-dimensional geometry. In: IEEE conference on visualization, pp. 361–378. IEEE Computer Society Press. doi:10.1109/VISUAL.1990.146402

Ishibuchi H, Sakane Y, Tsukamoto N, Nojima Y (2009) Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 1820–1825. San Antonio, USA. doi:10.1109/ICSMC.2009.5346628

Ishibuchi H, Tsukamoto N, Hitotsuyanagi Y, Nojima Y (2008) Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. In: Annual conference on genetic and evolutionary computation, pp. 649–656. ACM, New York, USA. doi:10.1145/1389095.1389225

Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: A short review. In: IEEE congress on evolutionary computation, pp. 2424–2431. doi:10.1109/CEC.2008.4631121

Jaimes AL, Quintero LVS, Coello CA (2009) Ranking methods in many-objective evolutionary algorithms. In: Nature-inspired algorithms for optimisation, pp. 413–434. Springer, Berlin

Knowles JD, Corne DW (2007) Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In: Evolutionary multi-criterion optimization, pp. 757–771. Springer, Berlin. doi:10.1007/978-3-540-70928-2_57

Köppen M, Yoshida K (2007) Substitute distance assignments in NSGA-II for handling many-objective optimization problems. In: Evolutionary multi-criterion optimization, pp. 727–741. doi:10.1007/978-3-540-70928-2_55

Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10(3):263–282. doi:10.1162/106365602760234108 CrossRef

Li M, Yang S, Liu X (2014) Diversity comparison of Pareto front approximations in many-objective optimization. IEEE Trans Cybern 44(12):2568–2584. doi:10.1109/TCYB.2014.2310651

Li M, Yang S, Liu X (2014) Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Trans Evol Comput 18(3):348–365. doi:10.1109/TEVC.2013.2262178 CrossRef

Li M, Yang S, Liu X, Shen R (2013) A comparative study on evolutionary algorithms for many-objective optimization. In: Evolutionary multi-criterion optimization, lecture notes in computer science, pp. 261–275. Sheffield, UK. doi:10.1007/978-3-642-37140-0_22

Li M, Zheng J, Li K, Yuan Q, Shen R (2010) Enhancing diversity for average ranking method in evolutionary many-objective optimization. In: Parallel problem solving from nature, pp. 647–656. Springer, Berlin. doi:10.1007/978-3-642-15844-5_65

Li M, Zheng J, Shen R, Li K, Yuan Q (2010) A grid-based fitness strategy for evolutionary many-objective optimization. In: Genetic and evolutionary computation conference, pp. 463–470. ACM. doi:10.1145/1830483.1830570

Miller BL, Goldberg DE (1995) Genetic algorithms, tournament selection, and the effects of noise. Complex Syst 9:193–212MathSciNet

Miller RGJ (1981) Simultaneous statistical inference, 2nd edn. Springer, New YorkCrossRefMATH

Mostaghim S, Schmeck H (2008) Distance based ranking in many-objective particle swarm optimization.In: Parallel problem solving from nature, pp. 753–762. Springer, Berlin. doi:10.1007/978-3-540-87700-4_75

Phan DH, Suzuki J (2013) R2-IBEA: R2 indicator based evolutionary algorithm for multiobjective optimization. In: IEEE congress on evolutionary computation, pp. 1836–1845. IEEE, Cancun, Mexico. doi:10.1109/CEC.2013.6557783

Phan DH, Suzuki J, Hayashi I (2011) BIBEA: boosted indicator based evolutionary algorithm for multiobjective optimization. In: Asia pacific symposium of intelligent and evolutionary systems. Yokosuka, Japan

di Pierro F (2006) Many-objective evolutionary algorithms and applications to water resources engineering. Ph.d. thesis, school of engineering, computer science and mathematics, University of Exeter, UK

di Pierro F, Khu ST, Savić DA (2007) An investigation on preference order ranking scheme for multiobjective evolutionary optimization. IEEE Trans Evol Comput 11(1):17–45. doi:10.1109/TEVC.2006.876362 CrossRef

Purshouse RC, Fleming PJ (2003) Evolutionary many-objective optimization: an exploratory analysis. IEEE Congr Evol Comput 3:2066–2073. doi:10.1109/CEC.2003.1299927

Purshouse RC, Fleming PJ (2007) On the evolutionary optimization of many conflicting objectives. IEEE Trans Evol Comput 11(6):770–784. doi:10.1109/TEVC.2007.910138 CrossRef

Rice J (1995) Mathematical statistics and data analysis. Duxbury Press

Rudolph G, Trautmann H, Sengupta S, Schütze O (2013) Evenly spaced Pareto front approximations for tricriteria problems based on triangulation. In: Evolutionary multi-criterion optimization, pp. 443–458. Springer, Sheffield, UK. doi:10.1007/978-3-642-37140-0_34

Sato H, Aguirre HE, Tanaka K (2007) Controlling dominance area of solutions and its impact on the performance of MOEAs. In: Evolutionary multi-criterion optimization, pp. 5–20. Springer, Berlin. doi:10.1007/978-3-540-70928-2_5

Tamhane AC (1977) Multiple comparisons in model I one-way ANOVA with unequal variances. Commun Stat 6(1):15–32. doi:10.1080/03610927708827466

Veldhuizen DAV, Lamont GB (1998) Evolutionary computation and convergence to a Pareto front. In: Late breaking papers at the genetic programming 1998 conference, pp. 221–228. Stanford University Bookstore, University of Wisconsin, Madison, Wisconsin, USA

Wagner T, Beume N, Naujoks B (2007) Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Evolutionary multi-criterion optimization, pp. 742–756. Springer, Berlin. doi:10.1007/978-3-540-70928-2_56

Wegman EJ (1990) Hyperdimensional data analysis using parallel coordinates. J Am Stat Assoc 85:664–675CrossRef

Yang S, Li M, Liu X, Zheng J (2013) A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 17(5):721–736. doi:10.1109/TEVC.2012.2227145 CrossRef

Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731. doi:10.1109/TEVC.2007.892759 MathSciNetCrossRef

Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.d. thesis, Eidgenössische Technische Hochschule Zürich. Swiss Federal Institute of Technology

Zitzler E, Künzli S (2004 Indicator-based selection in multiobjective search. In: Parallel problem solving from nature, pp. 832–842. Springer, Berlin. doi:10.1007/978-3-540-30217-9_84

Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. Evolutionary methods for design., optimisation, and controlCIMNE, Barcelona, Spain, pp 95–100

Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Parallel problem solving from nature, pp. 292–301. Springer, Berlin. doi:10.1007/BFb0056872

Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271. doi:10.1109/4235.797969 CrossRef

Titel: Many-objective optimization based on information separation and neighbor punishment selection
verfasst von: Ruimin Shen
Jinhua Zheng
Miqing Li
Juan Zou
Publikationsdatum: 07.09.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 5/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-015-1842-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 5/2017

Topology optimization of compliant structures and mechanisms using constructive solid geometry for 2-d and 3-d applications

Image quality assessment based on multiscale fuzzy gradient similarity deviation

Evaluation of research proposals for grant funding using interval-valued intuitionistic fuzzy sets

Iterative numerical method for fuzzy Volterra linear integral equations in two dimensions

Searching the Web for illegal content: the anatomy of a semantic search engine

Design and theoretical analysis of virtual machine placement algorithm based on peak workload characteristics