Laufzeitanalyse EA < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi!
Ich beschäftige mich momentan mit Evolutionären Algorithmen und versuche gerade die Laufzeitanalysen nachzuvollziehen.
Hierbei wird bisher immer nach einem ähnlichen Schema vorgegangen:
- Finde Maximum/Minimum der Fitnessfunktion
- Untersuche inwiefern sich das Individum ändern muss, um näher zum Maximum zu kommen
- Berechne die W'keit [mm] s_i [/mm] für den Wechsel von einem Zustand zum "nächst besseren" (im Bezug auf die Fitness-Funktion) Zustand
Die erwartete Laufzeit lässt sich dann immer über (Vorrausgesetzt man wird während einer Mutation nicht schlechter):
[mm] E(T)\le\summe_{i=1}^{n-1}*s_i^{-1} [/mm] abschätzen.
Nun ist klar, dass ich im worst case n-1 mal von einem Zustand zum Nächsten wechseln muss, daher die Summation von i=1 bis n-1. Aber wieso nehme ich jetzt gerade den Kehrwert von [mm] s_i? [/mm]
Ich habe mir bestimmt schon 5 verschiedene Folien/Skripte angeschaut, aber niergends wird erklärt, warum man das gerade so abschätzt.
Hat jemand von euch eine Idee?
Gruß
Pille
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 31.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
