Asgar - Fr 29.04.05 13:23
Titel: Mutations Algorythmus

---

Hallo erstmal.
Ich arbeite seit kurzem an einem Programm das Stundenpläne für eine Schule erstellen soll. Diese Stundenpläne sollen zufällig erstellt und dann nach verschiedenen Kriterie bewertet werden. Die besten Stundenpläne wählt das Programm aus. Die Stundenpläne die erstellt werden sollen nur ein wenig von den vorigen abweichen. In verschiedenen Diplomarbeiten über das Thema wude dafür immer eine mutation durchgeführt. Ich weis allerdings nicht wie ein solcher Mutationsalgorythmus aussieht und funktioniert. Hoffe mir kann hier irgendwer ein paar Tips dazu geben.

zemy - Mo 02.05.05 20:30

---

Wenn sie nur ein Wenig abweichen sollen, ändere doch nur einfach

Tausche eine Zufällige Stunde eines zufälligen Tages mit einer anderen zufälligen Stunde eines anderen Tages. Haste genau eine Änderung. Obs dafür ne andere, elegantere Möglichkeit gibt: keine Ahnung, so würde ichs machen.

delfiphan - Mo 02.05.05 20:39

---

Bei so evolutionären Algorithmen spielt es nicht mal eine sooo grosse Rolle, wie die Mutation aussieht.
Das Permutieren zweier Stunden ist wahrscheinlich eine gute Methode. Andere Möglichkeiten wären z.B. Cross-Over - wenn du zwei Stundenpläne aus dem Genpool nimmst und diese miteinander kreuzst, indem du zufällige Tage von einem und die übrigen Tage vom anderen Stundenplan nimmst.

Asgar - Di 03.05.05 10:42

---

Aber wie vertausche ich die Stunden zufällig? Gibts dafür irgend einen Befehl?
Hab die Stunden in nem 2 Dimensionalen Array. (Stunden[Klasse,Unterrichtsstunden]:=Fach)
Hab keine Ahnung wie ich da was vertauschen soll, bin noch Anfänger, wäre also nett wenn ihr mir ein Paar tips geben könntet.

sourcehunter - Do 05.05.05 12:49

---

Guck doch mal in der Delphi-Hilfe nach random und randomize.

Asgar - Mo 09.05.05 13:22

---

Glaub kaum das das damit geht, egal hab ein Beispiel in einem anderen Thread gefunden.
Trozdem danke für die Ratschläge.

delfiphan - Mo 09.05.05 13:31

---

Asgar hat folgendes geschrieben:

Glaub kaum das das damit geht, egal hab ein Beispiel in einem anderen Thread gefunden.

:?: Das wird tatsächlich häufig so gemacht - das hab ich nicht erfunden oder zusammengereimt.
Von Verladen von Containern bei Schiffen bis zur Erstellung von Fahrplänen werden solche Algorithmen eingesetzt. Kurz, bei np-vollständigen Problemen sind die meist geeignet, da eine gute Alternative meist sehr komplex oder sogar unmöglich ist zu finden. Ob tatsächlich das "Cross-Over" (wie oben erwähnt) stattfindet, das hängt stark vom Problem ab. Es gibt viele "Rekombinations"- und Mutationsarten; aber Evolutionäre Algorithmen werden sehr wohl bei solchen Problemen eingesetzt.

Könntest du vollständigkeihtshalber noch den Link zum anderen Thread posten? Danke.

Asgar - Mo 09.05.05 13:33

---

das mit dem nicht funktionieren war auch nicht auf deinen Post bezogen sondern auf das randomize.
Das mit der Mutation war ja das beispiel was ich nehme, da war in einem thread ein link zu einem programm namens Wandering Travveler, und da es open source ist kann ich das gut gebrauchen.

zemy - Di 10.05.05 19:25

---

ach, TSP [http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden]? Ist vieleicht ganz gut, um die Problematik zu verstehen, aber der Source wird wohl kaum auf dein Problem anwendbar sein. Schau dir das TSP [http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden] nochmal bei Wiki an und folge ein paar Links, Wenn dus nicht ausarten lässt, ist es auch nicht zu schwierig.

MfG Zemy