nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.02.2014

A study of search algorithms’ optimization speed

verfasst von: Andrea Valsecchi, Leonardo Vanneschi, Giancarlo Mauri

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Search algorithms are often compared by the optimization speed achieved on some sets of cost functions. Here some properties of algorithms’ optimization speed are introduced and discussed. In particular, we show that determining whether a set of cost functions F admits a search algorithm having given optimization speed is an NP-complete problem. Further, we derive an explicit formula to calculate the best achievable optimization speed when F is closed under permutation. Finally, we show that the optimization speed achieved by some well-know optimization techniques can be much worse than the best theoretical value, at least on some sets of optimization benchmarks.

Vorheriger Artikel Signed Roman domination in graphs

Nächster Artikel Sharp bounds of the Zagreb indices of k-trees

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

Aarts E, Korst J (1989) Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. Wiley, New York MATH

Altenberg L (1997) Nk fitness landscapes. In: Back T, et al. (eds) Handbook of evolutionary computation. IOP Publishing Ltd and Oxford University Press, Bristol, pp B2.7:5–B2.7:10

Deb K, Goldberg DE (1993) Analyzing deception in trap functions. In: Whitley D (ed) Foundations of genetic algorithms, vol 2. Morgan Kaufmann, San Mateo, pp 93–108

English TM (2004) On the structure of sequential search: beyond “no free lunch”. In: Gottlieb J, Raidl GR (eds) EvoCOP. Lecture notes in computer science, vol 3004. Springer, Berlin, pp 95–103

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

Häggström O (2006) Intelligent design and the nfl theorems. Biol Philos 22(2):217–230 CrossRef

Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is NP-complete. Inf Process Lett 5(1):15–17 CrossRefMATHMathSciNet

Igel C, Toussaint M (2004) A no-free-lunch theorem for non-uniform distributions of target functions. J Math Model Algorithms 3(4):313–322 CrossRefMATHMathSciNet

Jackson K, Kreinin A, Zhang W (2009) Randomization in the first hitting time problem. Stat Probab Lett 79(23):2422–2428. doi:10.1016/j.spl.2009.08.016 CrossRefMATHMathSciNet

Radcliffe N, Surry PD (1995) Fundamental limitations on search algorithms: evolutionary computing in perspective. Lecture notes in computer science, vol 1000. Springer, Berlin, pp 275–291

Rowe JE, Vose MD, Wright AH (2009) Reinterpreting no free lunch. Evol Comput 17:117–129. DOI http://dx.doi.org/10.1162/evco.2009.17.1.117. URL http://dx.doi.org/10.1162/evco.2009.17.1.117 CrossRef

Schumacher C, Vose MD, Whitley LD (2001) The no free lunch and problem description length. In: Spector L, Goodman ED, Wu A, Langdon WB, Voigt HM, Gen M, Sen S, Dorigo M, Pezeshk S, Garzon MH, Burke E (eds) Proceedings of the genetic and evolutionary computation conference (GECCO-2001). Morgan Kaufmann, San Francisco, pp 565–570. URL cite-seer.ist.psu.edu/schumacher01no.html

Valsecchi A, Vanneschi L (2008) A study of some implications of the no free lunch theorem. In: Gi- acobini M, et al. (eds) International workshop on theoretical aspects in artificial evolution, EvoTheory 2008. Proceedings of applications of evolutionary computing, EvoWorkshops 2008. Lecture notes in computer science, vol 4974. Springer, Berlin, pp 633–642

Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82. URL citeseer.ist.psu.edu/wolpert96no.html CrossRef

Titel: A study of search algorithms’ optimization speed
verfasst von: Andrea Valsecchi
Leonardo Vanneschi
Giancarlo Mauri
Publikationsdatum: 01.02.2014
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9514-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 2/2014

Improvements to MCS algorithm for the maximum clique problem

Total and paired domination numbers of toroidal meshes

Boundary graph classes for some maximum induced subgraph problems

An improved distributed data aggregation scheduling in wireless sensor networks

The adjacent vertex distinguishing total coloring of planar graphs

On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube

Premium Partner