Bibliothek für NP-harte Zuordnung gesucht.

[Anja-Schaefer]

Hallo,

ich habe ein Problem, weiss aber nicht genau, wie ich es exakt einordnen kann. Ich habe durch mein Nebenfach ein wenig in die Themen Programmierung/Informatik reingeschnuppert, bin aber alles andere als ein Experte.

Zum Problem: Ich möchte ein Programm entwickeln, dass eine Menge von Personen optimal zu Kursgruppen zuordnet. Dort sollen sie gemeinsam lernen. Nehmen wir an, es sind ca. 200 Anmeldungen. Nun gibt es einige Randbedingungen:

- Die Personen haben einen gewissen Kenntnisstand. Die Gruppen sollen alle möglichst homogen sein, dh alle Teilnehmer einen ähnlichen Kenntnisstand haben.
- Die Gruppen kommen zu unterschiedlichen Terminen zusammen. Hier sollen die Teilnehmer Präferenzen nennen.
- Einige Teilnehmer kennen sich schon vorher und möchten gerne gemeinsam in eine Gruppe. Dies soll nach Möglichkeit berücksichtigt werden.

Meine schwachen Erinnerungen sagen mir, dass das jetzt irgendwas mit Constraints, NP-Hart, Optimierung oder irgendwas ähnlichem zu tun haben müsste.

Kann mir jemand sagen, in welcher Richtung ich hier weitersuchen sollte? Es macht ja sicher keinen Sinn, hier eine Lösung komplett von vorne zu programmieren. Da gibt es doch bestimmt Bibliotheken.

Kann mir jemand da ein paar Stichworte oder Bibliotheken nennen, nach denen ich suchen kann?

Freue mich über jeden Hinweis!

 

[Anja-Schaefer]

Niemand eine Idee?

 

[Tomate_Salat]

Optimierung ist immer gut, Constraints haben etwas mit Datenbanken zu tun.

Hast du bereits einen Ansatz? Soll das ganze später ein GUI haben? Wieviel hast du schon in Java programmiert?

 

[SlaterB]

ne GUI? was ist das denn für eine Frage, es geht hier um ein extrem komplexes Problem,
zu dem man eine Zauberlösung wie Dijkstra bei Graphen braucht, nur weitaus größer, da interessiert das drumherum doch nicht,

Ansatz kann man auch fast vergessen, entweder was für Wochen zu modellieren (allein die Eingabe/ Gewichung/ Einbindung der noch völlig unklaren Faktoren 'Präferenzen') oder es gibt ein größeres fertiges Tool dafür,
danach ist gefragt

 

[FlorianP]

Zuerst brauchst du wohl eine Art "Kostenfunktion" die das ganze nach "gut" und "schlecht" bewertet. Davon hängt dann vieles ab, wohl auch ob es (effizient) exakt lösbar ist oder ob du dich mit einer Näherungslösung zufrieden geben musst.

Wenn z.B. deine Kostenfunktion den Kenntnisstand extrem hoch bewertet, wirds wohl ziemlich einfach, die Teilnehmer nach Kenntnisstand sortieren und dann die Gruppen auswählen und am Rand bei ähnlichem Kenntnisstand den Rest (wie Sympathie) berücksichtigen. Wenn alle Faktoren gleich wichtig sind, wirds wohl eher schwer werden eine exakte Lösung (in vernünftiger Zeit) zu bekommen, dann wird's wohl NP-hart.

 

[fastjack]

@Tomate_Salat Gerade bei NP hast Du Constraints Die sind aber nicht mit denselbigen in Datenbanken zu verwechseln.

Eine Bibliothek in Java, die grundlegende Algorithmen oder so für NP anbietet ist mir nicht bekannt, nur viele Java-Lösungen für konkrete Probleme. Aber die gibt es bei google massig.

 

[Dow Jones]

Kann mir jemand da ein paar Stichworte oder Bibliotheken nennen, nach denen ich suchen kann?

Hmm, das schon, aber die Anwendung der gängigen Methoden um solche Optimierungsprobleme zu bearbeiten (z.B. Integer Linear Programming oder Simulated Annealing) ist nicht so ganz trivial.

Wie FlorianP schon schrieb wirst du kaum darum herum kommen dein gewünschtes Optimierungsziel in Form von mathematischen Formeln zu formulieren, und das kann durchaus recht aufwendig werden. Zumal wenn die Anforderungen an die Lösung nur umgangssprachlich und vage vorgegeben sind ("soll", "nach Möglichkeit" etc).

Ich würde vorschlagen du nimmst dir mal einen Nachmittag Zeit um das Problem mathematisch zu formulieren. Dazu stellst du Formeln auf mit denen sich die Güte einer konkreten Verteilung der Personen auf Kursgruppen berechnen lässt (in der Literatur oftmals als Fitnessfunktion bezeichnet). Dabei sollte man ruhig kleinschrittig vorgehen, das hilft sehr die Übersicht zu behalten.

Fangen wir einfach mal an Formeln für die verschiedenen Kriterien aufzustellen, die wir für die Berechnung der Güte einer Lösung benötigen. Als erstes nehmen wir uns das Kriterium "homogener Kentnisstand der Teilnehmer" vor. Mathematisch formuliert könnte das so aussehen:

wissensdifferenz_zweier_personen (p1, p2) = wissensstand (p1) - wissensstand (p2)
quadratische_wissensdifferenz_zweier_personen (p1, p2) = wissensdifferenz_zweier_personen (p1, p2) ^ 2

Es bietet sich an die Wissensdifferenz zu quadrieren, denn
1) müssen wir dann das Vorzeichen der Ergebnisses nicht weiter berücksichtigen. nach der quadrierung es ist immer positiv
2) große Wissensdifferenzen werden "verstärkt". wenn wir später die Summe aller (quadratischen) Wissensdifferenzen der Teilnehmer in einer Kursgruppe bilden, dann ist eine große Wissensdifferenz schwerwiegender als 10 kleine Wissensdifferenzen.

Weiter geht's:

kursgruppe_von_person ( p ) = ...
ist_person_in_gruppe ( g, p ) = 0 ^ ( g - kursgruppe_von_person (p) )
sind_personen_in_gruppe ( g, p1, p2 ) = ist_person_in_gruppe (g, p1) * ist_person_in_gruppe (g, p2)

Die Funktion kursgruppe_von_person ( p ) soll für eine Person p die Nummer seiner Kursgruppe liefern. Diese ist aber leider unbekannt (denn genau das wollen wir ja schlußendlich ermitteln, in welche Gruppe wir eine Person einordnen sollen). Dazu schreibe ich weiter unten etwas.
Die Funktion is_person_in_gruppe(g, p) sieht vielleicht ersteinmal merkwürdig aus, aber hier machen wir uns eine mathematische "Obskurität" zunutze:
0^0 = 1,
0^irgendwas anderes = 0
Unsere Funktion liefert genau dann den Wert 1 wenn Person p in Gruppe Nummer g ist. In allen anderen Fällen liefert sie den Wert 0.
Ähnlich auch die nächste Funktion: sind_personen_in_gruppe(g, p1, p2) liefert genau dann 1 wenn p1 und p2 in Gruppe g sind. sonst ist das Ergebnis 0.

Die bisherigen Formeln können wir nun nutzen um die Wissensschwankung ein einer Gruppe zu berechnen:

wissensschwankung_in_gruppe ( g ) = 
   [Summe von x=1 bis x=anzahl_von_angemeldeten_personen] 
      [Summe von y=(x+1) bis y=anzahl_von_angemeldeten_personen]  
         sind_personen_in_gruppe (g, x, y) * quadratische_wissensdifferenz_zweier_personen (x, y)

Durch die doppelte Summe werden alle Personenpaare gebildet und jeweils deren Wissensdifferenz berechnet. Die Wissensdifferenz zweier Personen werden dabei entweder mit 1 (wenn beide Personen in der gleichen Gruppe sind) oder mit 0 (wenn sie in unterschiedlichen Gruppen sind) multipliziert. wissensschwankung_in_gruppe ( g ) berechnet also die Summe der quadratischen wissensschwankungen aller personen, die in Gruppe g sind. Das ist ein Wert, für den gilt: Je kleiner, desto besser.


Auf diese Weise kann man das gesamte Problem in Form von mathematischen Formeln bringen. Was dann noch übrig bleibt sind die Parameter. Dabei gibt es zum einen Konstanten (wie z.B. der Wissensstand von Person x), die muss man halt kennen und irgendwo angeben. Zum anderen gibt es Variablen, die man nicht kennt sondern erfahren möchte (z.B. die Kursgruppe von Person x). Und dazu kann man nun einen sogenannten ILP-Solver verwenden. Das kann man sich vorstellen wie ein Programm, das alle Möglichkeiten ausprobiert Personen in Kursgruppen einzuordnen, und dann am Ende eine Lösung ausgibt.

Damit das funktioniert muss man diesem ILP-Solver natürlich die ganzen Formeln und Konstanten übergeben. Und zusätzlich auch noch Bedingungen, die man erfüllt haben möchte:

1 <= anzahl_von_gruppen <= 10
quadratische_wissensschwankung_in_den_gruppen : MINIMIZE

Damit würde der ILP-Solver nach einer Lösung suchen, bei der es zwischen 1 und 10 Kursgruppen gibt, und bei der die die minimalste Wissensschwankung in den Gruppen auftritt.

Das ganze Verfahren macht auf den ersten Blick zwar einen aufwändigen Eindruck, aber wenn man erstmal verstanden hat wie das System funktioniert, dann kann man damit schon zurechtkommen.


PS: Freie ILP-Solver gibt es genug, Links finden sich in der Wikipedia. Empfehlen kann ich aber keinen, da ich bisher auch nur einmal mit so einem Teil gearbeitet habe
PPS: Nur der Vollständigkeit halber - die ILP-Solver probieren natürlich nicht wirklich alle Möglichkeiten aus, die arbeiten schon etwas pfiffiger. Sonst dürfte man wahrscheinlich 20 Jahre auf die Lösung warten...

 

[Landei]

Na ja, ich würde "Kosten" zuordnenen (z.B. für Wissensunterschiede, Auseinanderreißen von Bekannten, zu große oder zu kleine Gruppen) und dann einen genetischen Algorithmus auf das Dingens loslassen. Dazu finden sich auch Bibliotheken (JGAP: Java Genetic Algorithms Package nach kurzem googeln). Soweit ich weiß kann man über eine geschickte Konstenzuordnung recht gute Ergebnisse erzielen.