Original geschrieben von Clawg
Genetische Algorithmen sind nicht dasselbe wie Evolutionäre Algorithmen
Stimmt, sie sind eine Teilmenge der EA. Aber schön dass du gepostet hast.
@Sas:
Dienstplanerstellung ist interessant. Die große Schwierigkeit bei unserem Algorithmus ist Verteilung auf mehrere Agenten, sprich alles komplett dezentral zu halten.
Es gibt auch pseudodezentrale Heuristiken(z.b. Lova Tomas SASP) die recht gute Ergebnisse bringen, allerdings immer nur auf ein spezielles Zielkriterium bezogen, wir versuchen ein für alle Agenten "faires" Ergebnis zu bekommen.
Fairness zu definieren ist schon eine Kunst
.
Zum Thema nochmals: Die Individuuen sind im Prinzip pupskleine int Arrays (120 max groß). Die Ints sind unqiue im Array und auch durchnummeriert von 1-120, als Referenz auf ein Objekt (Job).
Jeder Job hat Ressourcen (bei uns bisher max 4, was aber rein historisch gewachsen ist) eine Dauer, Vorgänger und Nachfolger (Job 1 vor 2&5, dann 3&9 etc...). Es geht nun darum diesen Netzplan (=Schedule=int Array pro agent), so anzuordnen dass die 4 Ressourcen (z.b. alle 4 global genutzt = werden von allen agenten gleichzeitig genutzt) möglichst effizient genutzt werden und die Einzeldauer der Netzpläne eine möglichst geringe absolute Abweichung zum kritischen ihrem kritischen Pfad hat (als ein weiteres zielkriterium).
Rekombination = Erzeugung eines Gesamtschedules
Mutation = gültiges switchen von Jobs innerhalb eines agenten-netzplans
Selektion = z.b. via Wahrscheinlichkeiten (siehe Fink et al 2007 afaik), Wahlverfahren der Agenten, Akkzeptanzraten etc.
Richtig Zeitintensiv ist die Rekombination und natürlich auch krass Speicherintensiv wenn man davon ausgeht dass wir populationsgrößten von 50-100 oder wie auch immer haben und es auch lokale ressourcen gibt.
Des Weiteren ist für das SA von Fink natürlich auch die Nährungsverfahren zum bestimmen gewisser Temperaturwerte rechenintensiv wie sau.
Hoffe konnte dir ein wenig das problem erklären. Falls du genaueres wissen möchtest: 55529167, diskutiere gerne drüber
Grüße
Eeth
