nach oben

Journal of Combinatorial Optimization

Erschienen in:

26.02.2018

Quantile and mean value measures of search process complexity

verfasst von: Jaromír Kukal, Matej Mojzeš

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Performance measures of metaheuristic algorithms assess the quality of a search process by statistically analysing its performance. Such criteria serve two purposes: they provide the verdict on which algorithm is better for what task, and they help applying an algorithm on a given task in the most effective way. The latter goal may be achieved by an appropriate restart strategy of the search process. Furthermore, these criteria are traditionally based on analysis of the search step mean value. Our aim is to elaborate the mean value analysis as well, but via a novel and more general quantile-based analytic approach, which can be used to define new measures. We prove and demonstrate this purpose on three quantile-based performance measures.

Vorheriger Artikel A continuous characterization of the maximum vertex-weighted clique in hypergraphs

Nächster Artikel On the lower bounds of random Max 3 and 4-SAT

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

Nur mit Berechtigung zugänglich

Auger A, Hansen N (2005) Performance evaluation of an advanced local search evolutionary algorithm. In: The 2005 IEEE congress on evolutionary computation, 2005, vol 2, pp 1777–1784. IEEE, 2005

Barrero DF, Muñoz P, Camacho D, R-Moreno MD (2015) On the statistical distribution of the expected run-time in population-based search algorithms. Soft Comput 19(10):2717–2734. ISSN 1433-7479. https://doi.org/10.1007/s00500-015-1672-y

Burkard RE, Karisch SE, Rendl F (1997) Qaplib-a quadratic assignment problem library. J Glob Optim 10(4):391–403MathSciNetCrossRefMATH

Cerny V (1985) Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Optim Theory Appl 45(1):41–51MathSciNetCrossRefMATH

Chen H, Zhu Y, Hu K, He X (2010) Hierarchical swarm model: a new approach to optimization. Discrete Dyn Nat Soc 2010

Feoktistov V (2006) Differential evolution—in search of solutions. Springer, New YorkMATH

Gendreau M, Potvin J-Y (2010) Handbook of metaheuristics, vol 2. Springer, New YorkCrossRefMATH

Golberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading

Hansen N, Auger A, Finck S, Ros R (2010) Real-parameter black-box optimization benchmarking 2010: experimental setup

Hilbert D (1933) Ein beitrag zur theorie des legendreschen polynoms. In: Algebra Invariantentheorie Geometrie, pp 367–370. Springer, Berlin

Hoos H, Stützle T (1998) Evaluating las vegas algorithms: pitfalls and remedies. In: Proceedings of the fourteenth conference on uncertainty in artificial intelligence, pp 238–245. Morgan Kaufmann Publishers Inc., Los Altos

Kharroubi F, He J, Tang J, Chen M, Chen L (2015) Evaluation performance of genetic algorithm and tabu search algorithm for solving the max-rwa problem in all-optical networks. J Comb Optim, 30(4):1042–1061. ISSN 1573-2886. https://doi.org/10.1007/s10878-013-9676-y

Neocleous C, Schizas C (2002) Artificial neural network learning: a comparative review. In: Vouros GA, Panayiotopoulos T (eds) Methods and applications of artificial intelligence. Springer, Berlin, pp 300–313CrossRef

Senthilkumar P, Shahabudeen P (2006) Ga based heuristic for the open job shop scheduling problem. Int J Adv Manuf Technol 30(3–4):297–301CrossRef

Snyman J (2005) Practical mathematical optimization: an introduction to basic optimization theory and classical and new gradient-based algorithms, vol 97. Springer, New YorkMATH

Stützle T, Hoos H (2004) Stochastic local search: foundations and applications. Elsevier, AmsterdamMATH

Valsecchi A, Vanneschi L, Mauri G (2014) A study of search algorithms’ optimization speed. J Comb Optim, 27(2):256–270. ISSN 1382-6905. https://doi.org/10.1007/s10878-012-9514-7

Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82CrossRef

Yang X-S, Deb S (2009) Cuckoo search via lévy flights. In: Nature & biologically inspired computing, 2009. World Congress on NaBIC 2009, pp 210–214. IEEE, 2009

Titel: Quantile and mean value measures of search process complexity
verfasst von: Jaromír Kukal
Matej Mojzeš
Publikationsdatum: 26.02.2018
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0251-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+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2018

Channel assignment problem and n-fold t-separated -labeling of graphs

Dynamic work hour optimization for casual workers

On the lower bounds of random Max 3 and 4-SAT

A local search approximation algorithm for a squared metric k-facility location problem

FPT-algorithms for some problems related to integer programming

The number of edges, spectral radius and Hamilton-connectedness of graphs