Platzierungsoptimierung [Optimierungsalgorithmus]

18.12.2009, 17:02	Wolfson	Auf diesen Beitrag antworten »
Platzierungsoptimierung [Optimierungsalgorithmus] Hallo, ich stecke grad ein bissl in einer Problematik fest, die zu lange wäre um Sie hier komplett zu erklären. Drum bediene ich mich eines Vergleichs, der eine ziemlich genaue Abbildung meines Problems darstellt. Ich habe ein Schachbrett mit n Feldern und so viele Figuren, dass jedes Feld mit einer Figur besetzt ist. Es gibt unterschiedliche Figuren die Beziehungen untereinander haben. Damit meine ich Konfliktpotential, so hat z.B. eine Dame mit einem König ein höheres Konfliktpotential als mit einer weiteren Dame. Es gibt also 2 Maße (Faktoren für Konflikte): Konfliktpotential = $\begin{eqnarray} dk_{ij} \end{eqnarray}$ Die unterschiedlichen Werte für das Konfliktpotential zwischen 2 Arten von Figuren $\begin{eqnarray} f_{i} \end{eqnarray}$ und $\begin{eqnarray} f_{j} \end{eqnarray}$ sind festgelegt und nicht veränderlich Abstand = $\begin{eqnarray} de_{ij} \end{eqnarray}$ damit ist der Abstand gemeint, den jeweils 2 Figuren $\begin{eqnarray} f_{i} \end{eqnarray}$ und $\begin{eqnarray} f_{j} \end{eqnarray}$ auf dem Schachbrett zueinander haben (Euklid'sche Distanz) Das Ziel ist es die Platzierung der Figuren so vorzunehmen, dass minimale Konflikte auftreten. Es gibt die oben genannten 2 Faktoren die das beeinflussen. d_e: Um so näher 2 Figuren zueinander stehen, umso wahrscheinlicher haben Sie einen Konflikt. d_k: Um so höher das Konfliktpotential zwischen den 2 Figuren umso größer der Konflikt. Am Besten ist es daher sämtliche Figuren so weit wie möglich voneinander entfernt aufzustellen, aber jedes Feld muss mit einer Figur besetzt sein. Jede Figur hat mit jeder der anderen einen "Konfliktwert" $\begin{eqnarray} \frac{1}{de_{ij} \cdot dk_{ij}} \end{eqnarray}$ . Aufsummiert erhält man dann den Konfliktwert den eine Figur mit Allen anderen hat: $\begin{eqnarray} \sum_{j=1}^{n} \frac{1}{de_{ij} \cdot dk_{ij}} \end{eqnarray}$ . Die kompletten Konflikte der Platzierung sind also mit Hilfe einer weiteren Summe über alle Figuren und ihre jeweiligen Konfliktwerte beschrieben: $\begin{eqnarray} \sum_{i=1}^{n}\sum_{j=1}^{n} \frac{1}{de_{ij} \cdot dk_{ij}} \end{eqnarray}$ Diese Funktion gilt es zu minimieren! Da aber nur ein "Pool" von Feldern zur Verfügung steht stellt sich mir die Frage wie man das anstellen kann. Hat jemand von Euch einen Hinweis für mich? Ich wäre sehr dankbar für jeden Tipp!!!
18.12.2009, 17:18	wisili	Auf diesen Beitrag antworten »
RE: Platzierungsoptimierung [Optimierungsalgorithmus] Ich gratuliere für die sehr präzise und verständliche Problemdarstellung, habe aber noch keine klare Lösungsstrategie. Ich befürchte, dass es auf eine algorithmische hinausläuft, die allerdings Gefahr läuft, exponentiellen Aufwand aufzuweisen (mir kommt das Problem des Handlungsreisenden in den Sinn).
18.12.2009, 19:07	Mazze	Auf diesen Beitrag antworten »
Ich denke auch das man hier um Optimierungsalgorithmen wie Breitensuche /Backtracking /Branch and Bound oder heuristische Verfahren nicht drum rum kommt. Allerdings ist der Zustandsraum gigantisch. Mir fällt keine Heuristik so schnell ein, sonst würde ich Dir den A* Algorithmus (gesprochen : A-stern Algorithmus) empfehlen. Was eventuel ginge ist die Funktion $\begin{eqnarray} dk_{ij} \end{eqnarray}$ auch als differenzierbare Funktion zu betrachten (geeignet interpolieren). Dann kann man vielleicht mit einem Gradientenabstieg eine gute Näherungslösung finden (die dann an das nächste Feld angepasst werden muss). Alles in allem aber gehöriger Formaler aufwand.
18.12.2009, 20:40	Abakus	Auf diesen Beitrag antworten »
Hallo! Wenn du eine möglichst konfliktarme Stellung suchst und Figuren beliebig platzieren kannst, eignet sich ein Genetischer Algorithmus. Eine Bewertungsfunktion hast du ja. Grüße Abakus

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »