repräsentative Teilmenge / Teilbestand gesucht (Optimierungsproblem) |
| 09.03.2012, 08:38 | Auf diesen Beitrag antworten » | ||||||
| paludi06 | repräsentative Teilmenge / Teilbestand gesucht (Optimierungsproblem) Hallo zusammen, ich mache gerade ein Praktikum und soll nun einen Algorithmus für ein Problem finden. Dazu brauche ich eure Hilfe. Ich habe mich schon etwas eingelesen in bekannte Probleme, doch je mehr ich mich mit Algorithmen beschäftige, desto eher denke ich, dass ich kaum eine Chance habe das Problem alleine zu lösen bzw. ob es überhaupt in polynomieller Laufzeit gelöst werden kann. Es geht um folgendes Problem: Gegeben ist: N Vektoren die n-dimensional sind und ein Ergebnisvektor z = (z_1,...,z_n) der ebenfalls n-dimensional ist. Der i-te Eintrag von z ist die Summe über den i-ten Eintrag aller N Vektoren, i = 1, ..., n Gesucht ist: Eine Teilmenge der N Vektoren, die aus N/10 Vektoren besteht die folgendes erfüllt: Wenn man über den i-ten Eintrag all dieser N/10 Vektoren addiert, soll man möglichst nahe bei (z_i)/10 liegen. Unmathematisch ausgedrückt: Gegeben ist Bestand der Größe N (Anzahl der Zeilen), welcher n verschiedene Ausprägungen hat (Anzahl der Spalten). Über diese n Ausprägungen wird nun über alle N Zeilen addiert (liefert Ergebnisvektor z). Gesucht ist nun: 1/10 Teilbestand der möglichst genau 1/10 des Wertes jeder Ausprägung trifft, also ein repräsentativer Bestand. Der Algorithmus muss keines falls die optimale Lösung finden, sondern als Abbruchkriterium kann man die Bedingung einbauen, dass die Werte in einem bestimmten Intervall liegen. Meine Ideen bisher: Eine meiner Ideen war z.B., die Abstände die möglich klein werden sollen, in eine Summe zu schreiben und die Beträge (oder Quadrate) zu minimieren. Dabei lief mir die "kleinste Quadrate Methode" über den Weg, allerdings ist diese Methode irgendwie für eine andere Problemstellung als meine. Eine andere Idee war, mein Problem als "Rucksackproblem" aufzufassen, indem ich die Anzahl meiner Vektoren als "Gewicht" auffasse (jeder Vektor hat also Gewicht von 1) und versuche einen Rucksack mit maximal Gewicht N/10 zu füllen. Dabei soll der zu maximierende Nutzen bei mir folgendes sein: Die zu minimierenden Abstände werden wieder in eine Summe geschrieben und davor ein Minuszeichen gesetzt und das soll dann maximiert werden. Problem ist allerdings, dass ich nicht jedem einzelnen Vektor sinnvoll einen Nutzen zuordnen kann. Außerdem hab ich noch was von heuristischen und genetischen Algorithmen gelesen, die bei einer sehr großen Datenmenge, bei der es nichts besseres gibt als alle Möglichkeiten durchzuprobieren, ganz gut sein sollen. Allerdings habe ich keinen Algorithmus zu meinem Problem finden können. Hat jemand von euch eine Idee wie man da geschickt vorgeht? Erinnert euch das an ein ähnliches Problem, zudem man was im Internet / Literatur findet? Ich wäre für jedes Stichwort unter dem ich was im Internet / Literatur finde, dass ähnlich zu meinem Problem ist, dankbar. Viele Grüße, paludi06 |
||||||
|
|
|||||||
| 11.03.2012, 13:13 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Hallo, Ich denke dein Problem ist ein n-dimensionales Subset Sum Problem. In dem Verlinkten Wiki-Artikel ist auch ein Ansatz (Branch and Bound) beschrieben. Über das Uni-Netz kann man oft auch Papers abrufen: http://www.springerlink.com/content/p3511w638h45616u/ . Vlt hilft dir das weiter. Naiv würde ich einfach probieren den Zielvektor zu erstellen und den mittleren quadratischen Abstand zum Zielvektor zu minimieren. Eine Heuristik dazu fällt mir nicht ein (muss aber nichts heißen). Man könnte aber versuchen parallel eine Teilmengen Aufzusummieren auf ein Minimum zu testen. Vlt lässt sich auch sowas wie Simulated Annealing durchführen. Hoffe ich konnte dir wenigstens ein paar Ideen liefern. VG, Karlito |
||||||
| 12.03.2012, 08:27 | Auf diesen Beitrag antworten » | ||||||
| paludi06 |
Verstehe leider nicht, was du damit genau meinst, vielleicht könntest du diesen Gedanken nochmal etwas ausführen.
|
||||||
| 13.03.2012, 17:10 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Hallo, was ich genau meine ist, einfach parallel Teilmengen zu erstellen (meinetwegen 20 - 100) und die dann mit den Operationen "Hinzufügen eines zufättigen Elements", "Entfernen eines zufälligen Elements", "Tausch eines Zufälligen Elements" zu bearbeiten. Also ein rein stochastisches Verfahren. Dazu könnte man sich noch spitzfindigkeiten Einfallen lassen wie, dass man die Wahrscheinlichkeiten für die Operationen danach gewichtet, wie der mittlere Fehler gerade ist. Oder halt, dass man die Elemente danach auswählt, wie groß die gesamtsumme über den Vektor im Bezug auf den noch verbleibenden Fehler ist, so etwas wie Simulated Annealing, so dann am Anfang Vektoren mit großem "Gewicht" genommen werden und am Ende immer kleiner werdend... Ich denke das mit den Gewichten ist auch relativ einfach umzusetzen. Parallel deswegen, weil man aus den Varianten, die stochastisch entstehen, die beste Wählen kann. Dabei gibt es sicher eine Obergrenze, bis zu welcher Anzahl gleichzeitiger Prozesse das Vernünftig ist. Mit moderner Hardware (Grafikkarte o. Fusion-Kernen) macht das bestimmt auch ne Menge Spaß 
VG, Karlito |
||||||
| Anzeige | |||||||
|
|
|||||||
| 15.03.2012, 07:28 | Auf diesen Beitrag antworten » | ||||||
| paludi06 | Hallo Karlito, vielen Dank für deine ausführliche Erklärung! Ich werd nun mal mein Glück damit versuchen
|
||||||
| 23.03.2012, 11:54 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Hi, falls du das hier noch liest, schreib mal bitte, wie deine Erfahrungen waren und was schlussendlich zum Ziel geführt hat. VG, Karlito |
||||||
| 26.03.2012, 07:30 | Auf diesen Beitrag antworten » | ||||||
| paludi06 | Hallo Karlito, also ich hab es zunächst mal so gemacht, wie du es vorgeschlagen hast, dass ich den Zielvektor erstellt habe und den mittleren quadratischen Abstand minimiert habe. Das hab ich dann mit dem simpelsten Algorithmus den ich gefunden habe versucht hinzubekommen: 1. Starte mit zufälligen Teilbestand 2. Lasse 2 Schleifen laufen; eine über die Vektoren im Teilbestand und eine über die Vektoren außerhalb. Wenn es besser ist einen Vektor zu tauschen, dann tausche. Zusätzlich hab ich noch ein Abbruchkriterium drin, damit er nicht ewig sucht. Dadurch, dass die Daten sich recht angenehm untereinander verhalten, findet er bisher recht zügig gute Ergebnisse (auch bei großen Beständen). Vielen Dank nochmal für deine Hilfe! Gruß paludi06 |
||||||
| 26.03.2012, 11:43 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Hallo, Danke für die Rückmeldung und schön dass es geholfen hat. VG, Karlito |
||||||
|
|
