nach oben

Neural Computing and Applications

Erschienen in:

01.11.2012 | ICIC2010

Hypervolume-based multi-objective local search

verfasst von: Matthieu Basseur, Rong-Qiang Zeng, Jin-Kao Hao

Erschienen in: Neural Computing and Applications | Ausgabe 8/2012

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a multi-objective local search, where the selection is realized according to the hypervolume contribution of solutions. The HBMOLS algorithm proposed is inspired from the IBEA algorithm, an indicator-based multi-objective evolutionary algorithm proposed by Zitzler and Künzli in 2004, where the optimization goal is defined in terms of a binary indicator defining the selection operator. In this paper, we use the indicator optimization principle, and we apply it to an iterated local search algorithm, using hypervolume contribution indicator as selection mechanism. The methodology proposed here has been defined in order to be easily adaptable and to be as parameter-independent as possible. We carry out a range of experiments on the multi-objective flow shop problem and the multi-objective quadratic assignment problem, using the hypervolume contribution selection as well as two different binary indicators which were initially proposed in the IBEA algorithm. Experimental results indicate that the HBMOLS algorithm is highly effective in comparison with the algorithms based on binary indicators.

Vorheriger Artikel Dynamic transition embedding for image feature extraction and recognition

Nächster Artikel Path management method using partially connected neural network in large-scale heterogeneous sensor network

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

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

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

We assume throughout the paper that all the objective functions are normalized.

If a neighbor does not exist, its objective value is replaced by the objective value of the reference point Z _ref.

http://www.tik.ee.ethz.ch/pisa/assessment.html.

http://www.seas.upenn.edu/qaplib/inst.html.

Arroyo J, Armentano V (2005) Genetic local search for multi-objective flowshop scheduling problems. Eur J Oper Res 167(3):717–738MathSciNetMATHCrossRef

Bader J, Deb K, Zitzler E (2008) Faster hypervolume-based search using monte carlo sampling. In: Conference on multiple criteria decision making (MCDM 2008). Springer, New York, pp 313–326

Basseur M, Burke EK (2007) Indicator-based multiobjective local search. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2007). Singapore, September, pp 3100–3107

Basseur M, Seynhaeve F, Talbi E-G (2002) Design of multi-objective evolutionary algorithms: application to the flow-shop scheduling problem. In: Congress on evolutionary computation, vol 2. Honolulu, USA, pp 1151–1156

Beume N (2009) S-metric calculation by considering dominated hypervolume as klee’s measure problem. Evol Comput 17(4):477–492CrossRef

Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181:1653–1669MATHCrossRef

Bradstreet L, While L, Barone L (2008) A fast incremental hypervolume algorithm. IEEE Trans Evol Comput 12(6):714–723CrossRef

Bringmann K, Friedrich T (2008) Approximating the volume of unions and intersections of high-dimensional geometric objects. In: ISAAC’08: proceedings of the 19th international symposium on algorithms and computation, Berlin, Heidelberg. Springer, pp 436–447

Bringmann K, Friedrich T (2009) Don’t be greedy when calculating hypervolume contributions. In: FOGA’09: proceedings of the tenth ACM SIGEVO workshop on foundations of genetic algorithms. New York, NY, USA, ACM, pp 103–112

10.

Coello Coello CA, Lamont GB, Van Veldhuizen DA (2006) Evolutionary algorithms for solving multi-objective problems (genetic and evolutionary computation). Springer, New York, Inc., Secaucus, NJ, USA

11.

Day O, Lamont B (2005) Multiobjective quadratic assignment problem solved by an explicit building block search algorithm—momga-iia. In: EvoCOP, volume 3448 of lecture notes in computer science. Springer, New York, pp 91–100

12.

Dhaenens C, Lemesre J, Talbi E (2010) K-ppm: A new exact method to solve multiobjective combinatorial optimization problems. Eur J Oper Res 1:45–53MathSciNetCrossRef

13.

Du J, Leung JY-T (1990) Minimizing total tardiness on one machine is NP-hard. Math Oper Res 15:483–495MathSciNetMATHCrossRef

14.

Figueira J, Liefooghe A, Talbi E-G, Wierzbicki A (2010) A parallel multiple reference point approach for multi-objective optimization. Eur J Oper Res 205(2):390–400MathSciNetMATHCrossRef

15.

Knowles JD, Corne DW (2000) Approximating the nondominated front using the pareto archived evolution strategy. Evol Comput 8(2):149–172CrossRef

16.

Knowles JD, Thiele L, Zitzler E (2005) A tutorial on the performance assessment of stochastive multiobjective optimizers. Technical report TIK-Report No. 214, Computer Engineering and Networks Laboratory, ETH Zurich, July

17.

Landa-Silva D, Burke EK, Petrovic S (2004) Metaheuristic for multiobjective optimisation, chapter an introduction to multiobjective metaheuristics for scheduling and timetabling. Springer, New York, pp 91–129

18.

Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343–362MathSciNetCrossRef

19.

Liefooghe A, Mesmoudi S, Humeau J, Jourdan L, Talbi E-G (2009) Designing, implementing and analyzing effective heuristics. In: Engineering stochastic local search algorithms, volume 5752 of lecture notes in computer science. Springer, New York, pp 120–124

20.

Nagar A, Haddock J, Heragu S (1995) Multiple and bicriteria scheduling: a litterature survey. Eur J Oper Res 81:88–104MATHCrossRef

21.

Paquete L, Stuetzle T (2006) A study of local search algorithms for the biobjective QAP with correlated flow matrices. Eur J Oper Res 169(3):943–959MATHCrossRef

22.

Pardalos P, Rendl F, Wolkowicz H (1994) The quadratic assignment problem: a survey and recent developments. In: Proceedings of the DIMACS workshop on quadratic assignment problems, volume 16 of DIMACS series in discrete mathematics and theoretical computer science, pp 1–42

23.

Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555–565MathSciNetMATHCrossRef

24.

Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285MATHCrossRef

25.

Zhang Q, Li H (2006) A multiobjective evolutionary algorithm based on decomposition. Technical report TIK-report CSM-450, Department of Computer Science, University of Essex

26.

Zitzler E, Künzli S (2004) Indicator-based selection in multiobjective search. In 8th international conference on parallel problem solving from nature (PPSN VIII), pp 832–842, Birmingham, UK, September

27.

Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. Evol Comput 3:257–271CrossRef

28.

Zitzler E, Thiele L, Laumanns M, Foneseca CM, Grunert da Fonseca V (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117–132CrossRef

Titel: Hypervolume-based multi-objective local search
verfasst von: Matthieu Basseur
Rong-Qiang Zeng
Jin-Kao Hao
Publikationsdatum: 01.11.2012
Verlag: Springer-Verlag
Erschienen in: Neural Computing and Applications / Ausgabe 8/2012
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI: https://doi.org/10.1007/s00521-011-0588-4

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"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 8/2012

Testability transformation based on equivalence of target statements

Sparse data-dependent kernel principal component analysis based on least squares support vector machine for feature extraction and recognition

Efficient support vector data descriptions for novelty detection

A novel approach to accelerate the convergence speed of a stochastic multi-agent system using recurrent neural nets

Path management method using partially connected neural network in large-scale heterogeneous sensor network

Local directional derivative pattern for rotation invariant texture classification