nach oben

Soft Computing

Erschienen in:

20.05.2019 | Methodologies and Application

Analysis of semi-asynchronous multi-objective evolutionary algorithm with different asynchronies

verfasst von: Tomohiro Harada, Keiki Takadama

Erschienen in: Soft Computing | Ausgabe 4/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper proposes a novel master–slave parallel evolutionary algorithm (EA) approach with different asynchrony and provides its detailed analyses on multi-objective optimization problems. We express the proposed EA with different asynchrony as a semi-asynchronous EA. A semi-asynchronous EA generates new solutions whenever evaluations of the predefined number of solutions complete, unlike a conventional synchronous EA waits for evaluations of all solutions to generate the next population. To establish a semi-asynchronous EA, this paper introduces an asynchrony parameter that is used to decide how many solutions are waited to generate new solutions. We conduct an experiment to verify the effectiveness of the proposed semi-asynchronous EA on benchmark problems with the several variances of the evaluation time. In the experiment, we apply a semi-asynchronous EA to NSGA-II and NSGA-III, which are well-known multi-objective EAs. The semi-asynchronous NSGA-IIs and the semi-asynchronous NSGA-IIIs with different asynchronies are compared on multi-objective optimization benchmark problems. The experimental result reveals that semi-asynchronous approaches with an appropriate asynchrony have possibility to outperform the asynchronous and the synchronous ones. Additionally, detailed analysis reveals that an appropriate asynchrony may vary not only depends on a target problem but also depends on the degree of the evolution process.

Vorheriger Artikel A new framework for reliable control placement in software-defined networks based on multi-criteria clustering approach

Nächster Artikel A multi-start ILS–RVND algorithm with adaptive solution acceptance for the CVRP

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

\(\lceil x\rceil \) indicates the ceiling function that maps a real number x to the smallest next integer.

Akay B (2013) Synchronous and asynchronous Pareto-based multi-objective artificial bee colony algorithms. J Glob Optim 57(2):415–445. https://doi.org/10.1007/s10898-012-9993-1 MathSciNetCrossRefMATH

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

Carlisle A, Dozier G (2001) An off-the-shelf PSO. In: Particle swarm optimization workshop. Technology IUPUI, Indianapolis, IN, pp 1–6

Chang JF, Chu SC, Roddick JF, Pan JS (2005) A parallel particle swarm optimization algorithm with communication strategies. J Inf Sci Eng 21(4):809–818

Chipperfield A, Fleming P (1996) Parallel genetic algorithm. In: Zomaya AY (ed) Parallel and distributed computing handbook. McGraw-Hill, pp 1118–1143

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

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

Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints. IEEE Trans Evolut Comput 18(4):577–601. https://doi.org/10.1109/TEVC.2013.2281535 CrossRef

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. https://doi.org/10.1109/4235.996017 CrossRef

Depolli M, Trobec R, Filipic B (2013) Asynchronous master–slave parallelization of differential evolution for multi-objective optimization. Evol Comput 21(2):261–291CrossRef

Durillo JJ, Nebro AJ, Luna F, Alba E (2008) A study of master–slave approaches to parallelize nsga-ii. In: 2008 IEEE international symposium on parallel and distributed processing, pp 1–8. https://doi.org/10.1109/IPDPS.2008.4536375

Durillo JJ, Zhang Q, Nebro AJ, Alba E (2011) Distribution of computational effort in parallel MOEA/D. In: Coello CAC (ed) Learning and intelligent optimization, vol 6683. Lecture notes in computer science. Springer, Berlin, pp 488–502. https://doi.org/10.1007/978-3-642-25566-3_38 CrossRef

Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning, 1st edn. Addison-Wesley Longman Publishing Co., Inc, BostonMATH

Gong YJ, Chen WN, Zhan ZH, Zhang J, Li Y, Zhang Q, Li JJ (2015) Distributed evolutionary algorithms and their models: a survey of the state-of-the-art. Appl Soft Comput 34:286–300. https://doi.org/10.1016/j.asoc.2015.04.061 CrossRef

Harada T, Takadama K (2013) Asynchronous evaluation based genetic programming: comparison of asynchronous and synchronous evaluation and its analysis. In: Krawiec K, Moraglio A, Hu T, Etaner-Uyar A, Hu B (eds) Genetic programming, vol 7831. Lecture notes in computer science. Springer, Berlin, pp 241–252. https://doi.org/10.1007/978-3-642-37207-0_21 CrossRef

Harada T, Takadama K (2014) Asynchronously evolving solutions with excessively different evaluation time by reference-based evaluation. In: GECCO ’14: proceedings of the 2014 conference on genetic and evolutionary computation. ACM, Vancouver, BC, Canada, pp 911–918. https://doi.org/10.1145/2576768.2598330

Harada T, Takadama K (2017a) Performance comparison of parallel asynchronous multi-objective evolutionary algorithm with different asynchrony. In: 2017 IEEE congress on evolutionary computation (CEC), pp 1215–1222. https://doi.org/10.1109/CEC.2017.7969444

Harada T, Takadama K (2017b) A study of self-adaptive semi-asynchronous evolutionary algorithm on multi-objective optimization problem. In: Proceedings of the genetic and evolutionary computation conference companion, GECCO ’17. ACM, New York, NY, USA, pp 1812–1819. https://doi.org/10.1145/3067695.3084221

Holm S (1979) A simple sequentially rejective multiple test procedure. Scand J Stat 6(2):65–70MathSciNetMATH

Huband S, Barone L, While L, Hingston P (2005) A scalable multi-objective test problem toolkit. Springer, Berlin, pp 280–295. https://doi.org/10.1007/978-3-540-31880-4_20 CrossRefMATH

Jain H, 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 Trans Evol Comput 18(4):602–622. https://doi.org/10.1109/TEVC.2013.2281534 CrossRef

Koh BI, George AD, Haftka RT, Fregly BJ (2006) Parallel asynchronous particle swarm optimization. Int J Numer Methods Eng 67(4):578–595. https://doi.org/10.1002/nme.1646 CrossRefMATH

Koza J (1992) Genetic programming on the programming of computers by means of natural selection. MIT Press, CambridgeMATH

Kruskal WH, Wallis WA (1952) Use of ranks in one-criterion variance analysis. J Am Stat Assoc 47(260):583–621. https://doi.org/10.2307/2280779 CrossRefMATH

Lewis A, Mostaghim S, Scriven I (2009) Asynchronous multi-objective optimisation in unreliable distributed environments. In: Lewis A, Mostaghim S, Randall M (eds) Biologically-inspired optimisation methods, studies in computational intelligence, vol 210. Springer, Berlin, pp 51–78. https://doi.org/10.1007/978-3-642-01262-4_3 CrossRef

Luna F, Zavala GR, Nebro AJ, Durillo JJ, Coello CAC (2016) Distributed multi-objective metaheuristics for real-world structural optimization problems. Comput J 59(6):777–792. https://doi.org/10.1093/comjnl/bxu082 CrossRef

Maxwell III SR (1994) Experiments with a coroutine model for genetic programming. In: Proceedings of the 1994 IEEE world congress on computational intelligence, vol 1. IEEE Press, Orlando, Florida, USA, pp 413–417a. https://doi.org/10.1109/ICEC.1994.349915.http://ieeexplore.ieee.org/iel2/1125/8059/00349915.pdf?isNumber=8059. Accessed 19 May 2019

Milani A, Santucci V (2010) Asynchronous differential evolution. In: Proceedings of the 2010 IEEE congress on evolutionary computation (CEC 2010), pp 1–7 . https://doi.org/10.1109/CEC.2010.5586107

Nebro AJ, Durillo JJ, Vergne M (2015) Redesigning the jmetal multi-objective optimization framework. In: Proceedings of the companion publication of the 2015 annual conference on genetic and evolutionary computation, GECCO Companion ’15. ACM, New York, NY, USA, pp 1093–1100. https://doi.org/10.1145/2739482.2768462

Obayashi S, Jeong S, Shimoyama K, Chiba K, Morino H (2010) Multi-objective design exploration and its applications. Int J Aeronaut Space Sci 4(4) . https://doi.org/10.5139/IJASS.2010.11.4.247 CrossRef

Robič T, Filipič B (2005) DEMO: differential evolution for multiobjective optimization. Springer, Berlin, pp 520–533. https://doi.org/10.1007/978-3-540-31880-4_36 CrossRefMATH

Santander-Jiménez S, Vega-Rodríguez MA (2016a) Asynchronous non-generational model to parallelize metaheuristics: a bioinformatics case study. IEEE Trans Parallel Distrib Syst 28(7):1825–1838. https://doi.org/10.1109/TPDS.2016.2645764 CrossRef

Santander-Jiménez S, Vega-Rodríguez MA (2016b) Performance evaluation of dominance-based and indicator-based multiobjective approaches for phylogenetic inference. Inf Sci 330(C):293–314. https://doi.org/10.1016/j.ins.2015.10.021 CrossRef

Scott EO, De Jong KA (2015a) Evaluation-time bias in asynchronous evolutionary algorithms. In: Proceedings of the companion publication of the 2015 annual conference on genetic and evolutionary computation, GECCO Companion ’15. ACM, New York, NY, USA, pp 1209–1212. https://doi.org/10.1145/2739482.2768482

Scott EO, De Jong KA (2015b) Understanding simple asynchronous evolutionary algorithms. In: Proceedings of the 2015 ACM conference on foundations of genetic algorithms XIII, FOGA ’15. ACM, New York, NY, USA, pp 85–98. https://doi.org/10.1145/2725494.2725509

Tasoulis DK, Pavlidis NG, Plagianakos VP, Vrahatis MN (2004) Parallel differential evolution. In: Proceedings of the 2004 congress on evolutionary computation (IEEE Cat. No.04TH8753), vol 2, pp 2023–2029. https://doi.org/10.1109/CEC.2004.1331145

Wessing S, Rudolph G, Menges DA (2016) Comparing asynchronous and synchronous parallelization of the SMS-EMOA. Springer, Cham, pp 558–567. https://doi.org/10.1007/978-3-319-45823-6_52 CrossRef

Wilcoxon F (1945) Individual comparisons by ranking methods. Biom Bull 1(6):80–83CrossRef

Zhabitskaya E, Zhabitsky M (2013) Asynchronous differential evolution with restart. In: Dimov I, Farag I, Vulkov L (eds) Numerical analysis and its applications, vol 8236. Lecture notes in computer science. Springer, Berlin, pp 555–561. https://doi.org/10.1007/978-3-642-41515-9_64 CrossRef

Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. Springer, Berlin, pp 291–301. https://doi.org/10.1007/BFb0056872 CrossRef

Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: empirical results. Evol Comput 8(2):173–195CrossRef

Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. TIK report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland

Zăvoianu AC, Lughofer E, Koppelstätter W, Weidenholzer G, Amrhein W, Klement EP (2015) Performance comparison of generational and steady-state asynchronous multi-objective evolutionary algorithms for computationally-intensive problems. Knowl Based Syst 87(C):47–60. https://doi.org/10.1016/j.knosys.2015.05.029 CrossRef

Titel: Analysis of semi-asynchronous multi-objective evolutionary algorithm with different asynchronies
verfasst von: Tomohiro Harada
Keiki Takadama
Publikationsdatum: 20.05.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 4/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-019-04071-7

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 4/2020

A distributionally robust optimization model for designing humanitarian relief network with resource reallocation

A novel uncertain bimatrix game with Hurwicz criterion

Sustainability efficiency evaluation of seaports in China: an uncertain data envelopment analysis approach

Incentive contracts of knowledge investment for cooperative innovation in project-based supply chain with double moral hazard

Estimation of dynamic mixed double factors model in high-dimensional panel data

A transportation planning problem with transfer costs in uncertain environment