Ich habe diese Frage früher im Stackoverflow gepostet, wo sie als Off-Topic geschlossen wurde. Ich hoffe es überlebt hier.
In unserer Kletterhalle müssen die Routen von Zeit zu Zeit neu eingestellt werden. Es gelten folgende Regeln:
- Wir haben Klettergriffe mit verschiedenen Farben in unterschiedlichen Mengen. - Wenn eine Route in einem Sektor festgelegt ist, darf in diesem Sektor oder in den nahe gelegenen Sektoren keine andere Route mit derselben Farbe festgelegt werden, um Verwirrung zu vermeiden.
- Einige Farbkombinationen müssen in einem Sektor vermieden werden, z. B. Weiß / Grau oder Rot / Rosa.
- Das Ziel ist es, vier Routen in jedem Sektor zu haben. Weniger ist in Ordnung, wenn vier gegen die oben genannten Regeln verstoßen würden.
Ich habe inzwischen zwei verschiedene Ansätze ausprobiert. Das erste war Simuliertes Tempern, bei dem ich die Wand mit einem zufälligen Farbmuster (aber mit einem bestimmten Farbgewicht) initialisierte und für jede Farbkombination eine Schlechtigkeit berechnete . Diese Schlechtigkeit wurde auch für Kombinationen zwischen einem Sektor und seinen Nachbarn berechnet. In jeder Iteration wurde eine zufällig ausgewählte Route aus dem schlechtesten Sektor gegen eine Route aus einem zufällig ausgewählten anderen Sektor ausgetauscht. Dies zeigte eine Art Konvergenz, aber das Ergebnis war nicht verwendbar (dh der resultierende Zustand enthielt Sektoren mit Doppel- oder Dreifachfarben).
Ich näherte mich dann dem Problem von der gegenüberliegenden Seite und begann mit einer leeren Wand. Diesmal hatte jede Farbe eine Konzentration, die von einem Sektor zu den benachbarten Sektoren abfiel. Die Konzentration ähnlicher Farben wurde ebenfalls erhöht, dh ein roter Weg erhöhte die Konzentration von Orange in einem Sektor und in der Nähe. Eine gewichtete zufällige Farbquelle (der Eimer) gab mir die nächste Farbe für die Wand, die in dem Sektor mit der niedrigsten Konzentration dieser Farbe platziert wurde. Wenn eine Konzentration über einem bestimmten Schwellenwert lag, wurde die Farbe nicht hinzugefügt (sondern wieder in den Eimer gegeben). Dies war ein Teilerfolg, da der Ergebnisstatus keine Doppelfarben enthielt - einige Sektoren waren jedoch leer oder enthielten nur eine Farbe.
Also: Was könnte angesichts der oben genannten Regeln ein geeigneter Algorithmus zur Lösung dieses Problems sein? Gerne füge ich bei Bedarf weitere Informationen hinzu.
Bearbeiten 1 - Weitere Informationen:
- Mein Testfall hat 15 Sektoren,
- Jeder Sektor sollte 4 Routen enthalten
- Das echte Fitnessstudio besteht aus 3 Gebäuden mit durchschnittlich jeweils 50 Sektoren
- Einige Sektoren sind um Säulen angeordnet, andere sind durch Dächer verbunden
- Wir haben ungefähr 10 verschiedene Haltefarben
- Die Höhe der Sektoren variiert zwischen 6 (Anfängerabschnitt) und 20 Metern (13 vertikal + 7 Dach), sodass sie unterschiedliche Mengen an Laderäumen verbrauchen. Der Durchschnitt liegt jedoch bei etwa 12 und dies kann als konstant angesehen werden.
- Es gibt eine begrenzte Menge jeder Farbe, die Mengen sind nicht gleich
- Einige Farben sind einfacher, andere schwieriger (dh wir können eine gelbe Route für jede Schwierigkeit erstellen, während die Erstellung einer sehr einfachen orangefarbenen Route für Kinder fast unmöglich ist.)
- Einige Sektoren sind "einfacher", daher sollten einfache Farben dorthin gehen (dies ist optional, unsere Routensetzer können die Dinge in einem weiten Bereich schwieriger oder einfacher machen).
- Wir können mit Sicherheit sagen, welche Farben in einem Sektor oder in benachbarten Sektoren gut zusammenpassen und welche Kombinationen nicht. Es gibt einige Überraschungen wie Weiß und Schwarz (schlechte Kombination): Beide werden grau, während Gummi (Schuhe) oder Kreide (Hände) darauf verbleiben.
- Einige Haltefarben sind Kombinationen wie Violett / Weiß (in einem Streifenmuster).
Edit 2: Einige Fragen zu genetischen Algorithmen
Ich habe jetzt ParadisEO heruntergeladen und kompiliert und sogar meine IDE (ich verwende Code :: Blocks) zum Kompilieren des QuickStart-Beispiels erhalten. ParadisEO bietet genetische Algorithmen mit einem einzigen Ziel sowie einem GA mit mehreren Zielen. GertVdE schlug vor, die Fitness jedes Sektors zu berechnen und die Summe der Fitness aller Sektoren als ein einziges Ziel zu maximieren. Könnte ich auch die Fitness jedes Sektors mit einer GA mit mehreren Zielen maximieren? Das wären rund 50 Ziele.
Außerdem habe ich Probleme mit der Definition einer sinnvollen Crossover-Funktion. Da die maximale Menge jeder Farbe festgelegt ist, kann das Überqueren zu illegalen Zuständen führen. Wenn ich mehr als die zuvor angegebene maximale Menge zulasse, konvergiert das Gesamtmuster möglicherweise zu einer Wiederholung von weniger "störenden" Kombinationen, bei denen die störenden Farben weggeworfen wurden. Andererseits kann ich auch überschüssige Farben wegwerfen, bis das Maximum erreicht ist, wodurch die Crossover-Funktion nicht konservativ wird.
(Ich bin völlig neu in genetischen Algorithmen)
quelle
Antworten:
Ich würde das oben genannte Problem mit einem genetischen Algorithmus lösen. Sie codieren jede Lösung als einen Vektor von ganzen Zahlen:
Anschließend definieren Sie eine Fitnessfunktion als gewichtete Summe des minimalen Farbunterschieds in jedem Sektor und der Anzahl der Routen in einem Sektor (der Anzahl der Nullen im Vektor). Sie können das Paradiseo- Framework oder Inspyred für die Implementierung genetischer Algorithmen verwenden.
quelle
Hier ist ein kurzer Überblick über meine aktuelle Implementierung. Ich werde versuchen, mich an die Konzepte zu halten und nicht auf Sprachdetails einzugehen. Ich habe das ParadisEO Framework verwendet , eine C ++ - Vorlagenbibliothek für genetische Algorithmen, und hier und da etwas Auftrieb hinzugefügt.
Klettern halten Farben
Die Haltefarben werden in einer XML-Datei als Paar aus Farbname und Menge gespeichert. Die in einer Datei gefundenen Beträge werden addiert und normalisiert. Auf diese Weise kann ein Betrag entweder als Gesamtzahl der Routen ausgedrückt werden, die mit dieser Farbe festgelegt werden können, oder als Prozentsatz. Jeder Farbe wird eine ID zugewiesen, beginnend mit 1. Null ist für eine "leere" Route reserviert.
Farbkombinationsstrafen
Einige Farben passen in einem Sektor oder in benachbarten Sektoren nicht gut zusammen. Jede nicht so gute Farbkombination wird durch die beiden Farbnamen (wie in der vorherigen XML-Datei, siehe oben) und eine willkürliche "Schlechtigkeit" beschrieben. Intern werden die Badness-Werte in einer Matrix gespeichert, die durch Farb-IDs indiziert ist.
Die Wand
Die Wand ist eine Klasse, die von der Genomrepräsentationsklasse von ParadisEO abgeleitet ist, damit ParadisEO sie manipulieren und bewerten kann, aber einige weitere Funktionen hinzugefügt werden. Jedes Gen repräsentiert eine Routenfarbe nach ID (einschließlich Null oder leer). Sektoren werden durch ein Paar von Indizes zu den Genen dargestellt, so dass jeder Sektor einen Anfang und ein Ende hat. Ich habe zuerst Iteratoren für die Gene verwendet, aber das Wall-Objekt muss kopierkonstruierbar sein, was Iteratoren ohne zusätzliche Arbeit ungültig machen würde. Derzeit haben alle Sektoren 4 Routen, die jedoch in Zukunft konfiguriert werden können.
Die Wand hat auch einen Farbeimer. Dieser Bucket enthält einen Zähler für jede Farbe, der wie in der XML-Farbdatei beschrieben verteilt wird. Die Farbanzahl summiert sich zur Gesamtzahl der Routen in der Wand. Eine Farbe kann aus dem Eimer entnommen werden, wodurch der Zähler verringert wird, und sie kann auch zurückgesetzt werden, wodurch der Zähler vergrößert wird.
Eine Farbe kann einem Sektor nur hinzugefügt werden, wenn der Sektor diese Farbe noch nicht enthält (der Sektor muss beim Hinzufügen der Farbe "legal" bleiben).
Bewertungsoperator
Der Bewertungsoperator fasst alle Badness-Werte in einem Sektor unter Verwendung der oben beschriebenen Badness-Matrix zusammen. Der Wert jedes Sektors wird im Fitnessvektor gespeichert (der auch Teil der Wall-Klasse ist). Dies ist also eine GA mit mehreren Zielen. Ich könnte das ändern, wenn es notwendig wird.
Zweipunkt-Frequenzweiche
Der Crossover-Operator nimmt zwei Eltern, erstellt eine Kopie von jedem (den Nachkommen) und führt dann eine Zweipunkt-Crossover durch, indem er ganze Sektoren neu kombiniert . Dies hat den Vorteil, dass Sektoren legal bleiben (keine doppelten Farben). Der Nachteil jeder Überkreuzungsoperation (für dieses Problem) besteht darin, dass die resultierenden Nachkommen überschüssige Farben enthalten können, wenn die Farben in den Eltern gruppiert wurden. Eine Reparaturfunktion wurde hinzugefügt, die überschüssige Routen (Farbe Null) zufällig entfernt. Die Nachkommen haben daher weniger Wege als die Eltern der Reparatur die Nachkommen gewechselt haben.
Mutation 1: Route hinzufügen
Die potenzielle Abnahme der Routen bei den Nachkommen wird von einem Operator "Route hinzufügen" berücksichtigt. Es nimmt eine Farbe aus dem Eimer der Mauer und fügt sie irgendwo hinzu. Wenn dies keine legale Operation ist, tut es nichts (manchmal gibt es keinen legalen Platz für eine verbleibende Farbe).
Mutation 2: Zufälliger Austausch
Zwei zufällige Routen von zwei zufälligen Sektoren werden vertauscht. Dieses Swap-Paar wird generiert, bis die resultierenden Sektoren legal sind, und dann wird der Swap ausgeführt.
Mutation 3: Verschiebung
Eine Anzahl von Sektoren wird um eine Stelle nach links verschoben.
Ich habe jetzt keine Zeit mehr, kann aber später weitere Informationen hinzufügen. Insbesondere die Auswertung ist so einfach wie sie ist, und die Komponenten wurden als Beweis für das Konzept programmiert. Die GA optimiert zwar die Mauer in gewissem Maße, aber die Ergebnisse sind nicht für den tatsächlichen Gebrauch bereit. Ich bin mir sicher, dass sich dies verbessern wird, wenn ich mit den Routensetzern gesprochen habe und weitere Regeln für die Bewertung verfügbar sind. Bilder werden auch kommen, wenn sie verfügbar sind.
quelle