Algorithmus um Objekte auf einer Flaeche mit gleichem Abstand anzuordnen..?

[sirbender]

Hallo,

ich suche einen Algorithmus (z.B. Genetischer Algorithmus) mit dem ich z.B. fuer eine gegebene rechteckige Flaeche und einer Anzahl von Objekten die Positionen der Objekte errechnen sodass die Objekte moeglichst den gleichen Abstand haben bzw. einen moeglichst grossen Abstand haben. D.h. es soll "bestraft" werden, wenn sich zwei Objekte nahe kommen.

Ein konkretes Beispiel: Rechteck mit 400x200. 5 Objekte sind optimal angeordnet wenn 4 Objekte in den Ecken zum liegen kommen und ein Objekt im Zentrum. Also:
0,0
400,0
400,200
0,200
200,100 (Zentrum)

Eine andere Loesung die allerdings als schlechter bewertet werden sollte ist z.B.:
0,0
400,0
400,200
0,200
200,0 (Aenderung)

Liegt das Objekt bei 200,100 (Zentrum) hat man 4 Abstaende zu jedem Objekt in der Ecke mit einem Abstand von Diagonale/2 = 223,60.

Liegt das Objekt bei 200,0 hat man 2 Abstaende von 200. Diese zwei Abstaende von 200 sollten uenguenstiger sein als 4 Abstaende mit 223,60. Ehrlich gesagt sollte schon ein Abstand von 200 unguenstiger sein als 4 Abstaende von 223,60.

Ich bin mir ziemlich sicher, dass es da gute Algorithmen gibt die getestet sind fuer das Problem. Auch wohl Genetische Algorithmen. Ich finde allerdings nichts mit Google (vielleicht such ich auch falsch). Ich habe das Problem schon implementiert mit Genetischen Algorithmen aber so richtig kann ich nicht alle simplen Faelle (geringe Anzahl von Objekten) von optimalen Anordnungen finden. Jetzt wuerde ich meine Implementierung gerne mit einer ausgereiften Loesung vergleichen.

 

[Joose]

Hm ... laut deiner Beschreibung sollen die Objekte möglichst den gleichen Abstand haben. Den gleichen Abstand zu was? Einfach nur zueinander?
Dann ist dein Beispiel nicht gerade gut gewählt: Zur Mitte haben die Ecke zwar den gleichen Abstand, die Ecken zueinander haben aber einen sehr großen bzw. sehr kleinen Abstand.

Bis zu 3 Objekte kannst du im gleichen Abstand zueinander positionieren. Bei mehr als 3 Objekten ist das nicht mehr möglich.
Hier wäre die optimalste Variante (wahrscheinlich) immer nach dem gleichen Schema: eine symmetrische Figur mit X Ecken. Wobei die Ecken alle im gleichen Abstand zu einander sind und die Anzahl der Anzahl der Objekte entspricht, -1 (der Mittelpunkt der Figur).

 

[sirbender]

Danke fuer die Antwort. Genau es geht um den Abstand der Objekte zueinander. Und es ist klar, dass man bei einer gegebenen Flaeche und Anzahl von Objekten nie eine Loesung finden kann, die fuer alle Objekte zueinander den gleichen Abstand findet. Es soll auch nicht die Form der Flaeche optimiert werden, sodass eine Loesung gefunden wird wo alle Objekte den gleichen Abstand zueinander haben.

Vielmehr geht es darum fuer eine gegebene Flaeche (z.B. Rechteck) und Anzahl von Objekten eine Loesung findet bei der sehr nahe Abstaende von Objekten zueinander vermieden werden. Um mal ein konkretes Beispiel zu nennen: Es ist besser 10 Abstaende von 5 Meter zu haben anstatt 9 Abstaende mit 6 Metern und 1 Abstand mit 4 Metern. Diese 4 Meter sollten wegoptimiert werden. Ganz grosse Abstaende sind komplett unwichtig. Das wichtige ist, dass einzelne kleine Abstaende vermieden werden.

Das wichtigste ist jedoch wie ich das optimiere. Was ich oben beschrieben habe ist, wie das Ergebnis aussehen soll. Also bei einem Genetic Algorithm wie die Fitness Function sein soll.
Was fehlt ist wie das Chromosom kodiert wird, wie Crossover und Mutation ablaufen soll. Bzw. wenn man keine Genetischen Algorithmen verwendet, wie die Optimierung an sich ablaufen soll. Das verstehe ich nicht ganz.

 

[mrBrown]

Das wichtigste ist jedoch wie ich das optimiere. Was ich oben beschrieben habe ist, wie das Ergebnis aussehen soll. Also bei einem Genetic Algorithm wie die Fitness Function sein soll.
Was fehlt ist wie das Chromosom kodiert wird, wie Crossover und Mutation ablaufen soll. Bzw. wenn man keine Genetischen Algorithmen verwendet, wie die Optimierung an sich ablaufen soll. Das verstehe ich nicht ganz.

Wenn du's einfach haben willst, kodierst du das nicht noch mal extra als "Genotyp", sondern arbeitest mit den Daten die du hast, also zB eine Liste der Objekte.

Mutation wäre dann, Objekte zufällig verschieben, Rekombination zwei Listen vermischen (uU aufpassen auf duplizierte Objekte), und Selektion der kleinste Abstand zweier Objekte zueinander.

Wenn man die Funktionen vernünftig trennt, kann man später einzelne Sachen austauschen, zB mit unterschiedlicher Kodierung für Geno- und Phänotyp

 

[sirbender]

Was du beschreibst habe ich so alles schon ausprobiert. Auch sehr viel konkreter und mit vielen unterschiedlichen Settings. Also nur minimal verschieben beim Mutieren oder sehr viel, usw.

Leider ist das Ergebnis nicht so optimal wie ich es mir wuensche. Vor allem bei kleinen Anzahlen von Objekten faellt es einem als Mensch schnell auf, dass das nicht die optimale Loesung ist und man "sieht" schnell eine bessere.

Was ich suche ist eine wirklich durchdachte und funktionierende Loesung bzw. ein Ansatz der sehr konkret ist und der einem sagt, warum es auf diese oder jene Art zu einem sehr guten Resultat fuehrt.

 

[mrBrown]

Was du beschreibst habe ich so alles schon ausprobiert. Auch sehr viel konkreter und mit vielen unterschiedlichen Settings. Also nur minimal verschieben beim Mutieren oder sehr viel, usw.

Leider ist das Ergebnis nicht so optimal wie ich es mir wuensche. Vor allem bei kleinen Anzahlen von Objekten faellt es einem als Mensch schnell auf, dass das nicht die optimale Loesung ist und man "sieht" schnell eine bessere.

Was ich suche ist eine wirklich durchdachte und funktionierende Loesung bzw. ein Ansatz der sehr konkret ist und der einem sagt, warum es auf diese oder jene Art zu einem sehr guten Resultat fuehrt.

Mit evolutionären/gentischen Algorithmen findest du auch nicht immer das globale Optimum.
Das klingt ein bisschen so, als ob der ein einem lokalem Optimum festsaß, im Glücksfall kommt man da mit Rekombination raus, uU aber auch gar nicht, je nachdem wie man das implementiert hat.

Ich kenne auch keine existierende Lösung dafür, vllt willst du ja mal posten, was du gemacht hast, dann könnte man mal nach Fehlen und Verbesserungen gucken

 

[DrZoidberg]

Wie viele Objekte sind das maximal?

 

[sirbender]

Naja...von 1 bis sagen wir 100.

 

[JCODA]

Was würdest du von einer Art "Ladungssimulation" halten? Jedes Objekt hat eine positive Ladung und somit stoßen sie sich ab. Das dürfte sich leicht implementieren lassen, ich versuch mich mal daran.

 

[JCODA]

Mhhh, schade. Ich dachte ich kann ein altes Spiel umschreiben, sodass das schnell geht, allerdings habe ich diie Schwierigkeit mit den "Rand" falsch eingeschätzt. Anbei das "falsche" Programm.

 

[DrZoidberg]

Eine Ladungssimulation könnte tatsächlich funktionieren. Man müsste die Simulation halt nur auf einer Kugeloberfläche ablaufen lassen, so dass man keinen Rand hat. Am Ende friert man die Objekte ein und "schneidet" dann ein rechteckiges Stück aus dieser Oberfläche aus.

 

[JCODA]

Eine Ladungssimulation könnte tatsächlich funktionieren. Man müsste die Simulation halt nur auf einer Kugeloberfläche ablaufen lassen, so dass man keinen Rand hat. Am Ende friert man die Objekte ein und "schneidet" dann ein rechteckiges Stück aus dieser Oberfläche aus.

Ja, ich hab auch zunächst an einen Torus gedacht, aber hab mich ein bisschen mit der Abstandsberechnung vertan. Vielleicht schreib programmier ich heute Abend 'was dazu.

 

[DrZoidberg]

Ich habe jetzt gemerkt, dass es auch mit einem normalen flachen Koordinatensystem geht. Ich hab da mal was geschrieben. Wenn ein "Teilchen" den Rand erreicht taucht es auf der gegenüberliegenden Seite wieder auf. Abstossende Kräfte verhalten sich nach dem selben Prinzip, d.h. wenn sich z.B. ein Teilchen in der unteren rechten Ecke befindet stösst es ein anderes Teilchen in der linken oberen Ecke ab.
https://jsfiddle.net/q6txo0n7/
Teilchen können einfach mit der Maus platziert werden. Auf der Konsole(F12) wird die Geschwindigkeit der Simulation ausgegeben.

 

[sirbender]

Mhhh, schade. Ich dachte ich kann ein altes Spiel umschreiben, sodass das schnell geht, allerdings habe ich diie Schwierigkeit mit den "Rand" falsch eingeschätzt. Anbei das "falsche" Programm.

Ganz interessant nur fuehrt es dann zu eher falschen Ergebnissen wie im angehaengten Screenshot gezeigt. Die Kugel, die sich nicht in der Ecke befindet sollte im Zentrum der Flaeche sein. Komischerweise schafft die Animation es nicht mal die Kugel zwischen den beiden Kugeln in den unteren Ecken zu zentrieren. Ohne den Code gesehen zu haben scheint mit das Verhalten trotzdem seltsam, da die linke untere Kugel die Kugel rechts daneben stark abstossen sollte.

 

[sirbender]

Ich habe jetzt gemerkt, dass es auch mit einem normalen flachen Koordinatensystem geht. Ich hab da mal was geschrieben. Wenn ein "Teilchen" den Rand erreicht taucht es auf der gegenüberliegenden Seite wieder auf. Abstossende Kräfte verhalten sich nach dem selben Prinzip, d.h. wenn sich z.B. ein Teilchen in der unteren rechten Ecke befindet stösst es ein anderes Teilchen in der linken oberen Ecke ab.
https://jsfiddle.net/q6txo0n7/
Teilchen können einfach mit der Maus platziert werden. Auf der Konsole(F12) wird die Geschwindigkeit der Simulation ausgegeben.

Schaut intressant aus. Das Verhalten stoert aber ein bischen:

"Abstossende Kräfte verhalten sich nach dem selben Prinzip, d.h. wenn sich z.B. ein Teilchen in der unteren rechten Ecke befindet stösst es ein anderes Teilchen in der linken oberen Ecke ab."

Diese Art der Abstossung von Objekten in rechter unterer und linker oberer Ecke sollte nicht sein. Kannst du das Verhalten einfach abstellen?

 

[DrZoidberg]

Wenn ich das abstelle, dann verhält sich mein Programm genau so wie das von JCODE. Die meisten Teilchen sammeln sich dann am Rand und in den Ecken, da sie dort von nichts mehr rausgedrückt werden.

 

[mrBrown]

Wenn ich das abstelle, dann verhält sich mein Programm genau so wie das von JCODE. Die meisten Teilchen sammeln sich dann am Rand und in den Ecken, da sie dort von nichts mehr rausgedrückt werden.

Ohne es jetzt ausprobiert zu haben, wie ist's wenn man den Teilchen etwas Zufallsbewegung gibt? Sobald die wieder ein Stückchen vom Rand weg sind, müssten die Richtung Mitte gedruckt werden, sind die einmal in "optimaler" Anordnung, müssten die dann dahin wieder zurückgedrückt werden

 

[Blender3D]

Nur ein Gedanke.

Wenn ich das abstelle, dann verhält sich mein Programm genau so wie das von JCODE. Die meisten Teilchen sammeln sich dann am Rand und in den Ecken, da sie dort von nichts mehr rausgedrückt werden.

Wie wäre es damit? Kugel ist 5 Einheiten vom linken Rand entfernt. Kraftvektor der Kugel ist 10 Einheiten lang. Vom rechten Rand wirkt durch den linken Rand ein Kraftvektor der Kugel von 5 Einheiten durch.
Dadurch würden sich die Kugeln, wie im Zentrum der Fläche verhalten.

 

[mrBrown]

Nur ein Gedanke.

Wie wäre es damit? Kugel ist 5 Einheiten vom linken Rand entfernt. Kraftvektor der Kugel ist 10 Einheiten lang. Vom rechten Rand wirkt durch den linken Rand ein Kraftvektor der Kugel von 5 Einheiten durch.
Dadurch würden sich die Kugeln, wie im Zentrum der Fläche verhalten.

Wurd vorher schon vorgeschlagen bzw umgesetzt, ist aber unerwünscht gewesen 😉

 

[DrZoidberg]

Gut, ich habe da noch weitere Funktionen hinzugefügt. Man kann auf die Teilchen jetzt zufällige Kraftvektoren wirken lassen. Und man kann sich aussuchen, ob Kraftvektoren und Teilchen in der Lage sind vom rechten Rand zum linken zu "springen" bzw. vom oberen zum unteren und umgekehrt.
https://jsfiddle.net/oh3fhuq1/

 

[JCODA]

@sirbender was wäre eine "Optimale" Verteilung in einem 500x500 Feld mit 10 Objekten?