Rucksackproblem und genetischer Algorithmus

[Saheeda]

Hallo,

ich habe zum besseren Verständnis einen genetischen Algorithmus zunächst stark vereinfacht umgesetzt.
Meine Population besteht nur aus Strings, welche wiederum aus 0 und 1 bestehen.

Jeder dieser Strings hat die Länge 8 und ich bin davon ausgegangen, dass wenn mindestens 7 dieser 8 Stellen den Wert 1 haben, der String hinreichend genau optimiert wurde.
Anhand der Anzahl der 1 in jedem String berechne ich die Fitness. "00011111" => Fitness von 0.625, dabei ist es egal, ich welcher Reihenfolge sie auftauchen, es geht mir hier nur um die Anzahl.

Mein Algorithmus geht rekursiv durch eine Liste von Strings und rekombiniert, selektiert und mutiert diese, bis >=90% der Population hinreichend genau optimiert sind.


Jetzt wollte ich das Prinzip auf das Rucksack-Problem anwenden und stelle fest, dass ich keine Ahnung habe, wie ich die Fitness berechnen soll.
Die Gesamtfitness darf nicht über 1 liegen und hängt von der Anzahl der Items, der Gesamtkapazität, dem Gewicht und der Nützlichkeit jedes Items ab, soweit bin ich, aber ich habe keine Idee, wie ich die vier (bzw. fünf) Werte in eine vernünftige Formel kriege.

 

[BuckRogers]

Hi,
spontan gesagt würde ich folgendermaßen Vorgehen:
(ich habe mich in der Uni auch mal mit genetischem Algorithmus befasst und da was programmiert)
Ausschlaggebend ist die Gesamtkapazität des Rucksacks. Anscheinend hat jedes Item das gleiche Volumen aber unterschiedliches Gewicht und Nützlichkeit, nehme ich an. Also hat der Rucksack eine Beschränkung von Volumen und Gewicht. Das würde ich bei jeder Generation berechnen und dann die Population dementsprechend ausdünnen. Die Fitness würde ich anhand der erreichten maximalen Kapazität des Rucksacks bestimmen. Ob das maximale Volumen bei geringstem Gewicht zu erreichen ist? Also Fitness Faktor 1 wäre dann erreicht wenn der Rucksack mit Items gefüllt ist, die das geringste Gewicht haben und die höchste Nützlichkeit.
Sagen wir mal beispielsweise der Rucksack kann 10 Items fassen mit einem maximalen Gewicht von 10 Kg. Der höchste Nützlichkeitswert liegt auch bei 10 sagen wir. Das Gewicht müsste invers dargestellt werden. Das geringste Gewicht hat den höchsten Wert, sagen wir 10.
Also haben wir im Idealfall 10 Items * 10 Gewicht * 10 Nützlichkeit = 1000/1000 = 1 Fitness.
Du müsstest die Ausdehnung der Werte eines jeden Faktors in eine anständige Skala bringen, am besten so dass du damit rechnen kannt und im Idealfall den Wert 1 bekommst.

 

[Saheeda]

Hallo,

ich habe zwischenzeitlich für mich einen Weg gefunden, wobei ich nicht weiß, ob der so ideal ist:

Ich berechne zunächst für alle Items im Rucksack das Gesamtgewicht, ist dieses höher, als die Gesamtkapazität des Rucksacks, so setze ich die Fitness auf 0. Andernfalls ist sie die Summe der Kosten/Nützlichkeiten aller Items.

Beim 0-1-Algorithmus war die Abbruchbedingung, dass die Fitness eines gewissen Teils der Population über 7/8 liegt.
Jetzt terminiert er, wenn sich innerhalb der letzten 25 Generationen die durchschnittliche Fitness nicht verbessert hat.

Ich habe damit auch verschiedene Testläufe gemacht, und es scheint so zu funktionieren (bzw. ich habe noch keinen Testfall gefunden, der in eine Endlosschleife läuft).

 

[BuckRogers]

Hi,

also einige Eckdaten verstehe ich nicht ganz. Vielleicht kannst du mir da sin ein paar Zeilen erklären?
Die Population besteht aus den Rucksäcken? Gibt es ein Populationsmaximum?
Die Items haben nur 2 Faktoren? Gewicht und Nützlichkeit?
Du berechnest eine Fitness pro Individuum und darus die Gesamtfitness?

Grüße

 

[Saheeda]

Hallo,

natürlich.

Bei mir gibt es einen Pool von Items, jeder Rucksack besitzt als "Genotyp" ein Array, welches angibt, welche Elemente des Pools in ihm enthalten sind.
Z.B.: Pool: "Sonnenbrille, Kompass, Wecker, Bücher, Laptop"
Rucksack1 hat den Genotypen 00011 => Bücher, Laptop sind eingepackt
Rucksack2 hat den Genotypen 11010 => Sonnebrille, Kompass, Bücher sind eingepackt.
etc.

Die Population besteht aus verschiedenen Wertekombinationen dieser Items, also ja, aus verschiedenen Rucksäcken.
In jeder Generation verdoppelt sich die Population zunächst und anschließend werden die 50% mit der höchsten Fitness in die nächste Generation übernommen. Auf diese Art habe ich eine konstante Populationsgröße.

Jedes Item hat zwei Faktoren: Gewicht und Nützlichkeit. Beide Werte haben keine Grenzen, bei der Nützlichkeit sind niedriger Werte irrelevant, hohe Werte sehr nützlich.

Jeder Rucksack hat eine Fitness, die sich aus der Summe aller Nützlichkeiten seiner Items berechnet.

In "isOptimized" berechne ich die durchschnittliche Fitness einer gesamten Generation. Die Annahme dahinter ist, dass wenn sich die gesamte Population irgendwann nicht mehr verbessert, ist diese hinreichend genau optimiert.

Die Klasse:

public class GeneticSolver<T extends Evolvable<T>> { 

    /**  Breeds the given parents until fitness can't be improved.  */
    public boolean resolve(final List<T> entities) throws InstantiationException, IllegalAccessException {

        List<T> nextGeneration = new ArrayList<>(entities);

        while (!this.isOptimized(nextGeneration)) {
            this.numberOfCurrentGeneration++;

            this.mutation(nextGeneration);

            List<T> allChildren = this.recombine(nextGeneration);

            nextGeneration = this.selectFittest(allChildren, allChildren.size() / 2);
        }

        System.out.println("\n======== Results ===========");
        System.out.println("Number of Generations: " + this.numberOfCurrentGeneration);
        System.out.println("Number of Entities: " + entities.size());
        return true;

    }

    /** Finds out, if population can be assumed as 'perfect' by comparing whole population's fitness with
     * previous generations.  */
    private boolean isOptimized(final List<T> currentGeneration) {

        if (currentGeneration.size() == 0) {
            return false;
        }

        double currentGenerationAverageFitness = 0;
        for (T b : currentGeneration) {
            currentGenerationAverageFitness += b.getFitness();
        }
        currentGenerationAverageFitness /= currentGeneration.size();

        if (currentGenerationAverageFitness > this.highestAverageFitness) {
            this.highestAverageFitness = currentGenerationAverageFitness;
            this.generationWithHighestFitness = this.numberOfCurrentGeneration;
        }

        final int differenceToBestGeneration = 25;
        if (this.numberOfCurrentGeneration - differenceToBestGeneration > this.generationWithHighestFitness) {
            return true;
        }

        return false;
    }

    /** Selects 50% of population with highest fittest.  */
    public List<T> selectFittest(final List<T> currentGeneration, final int maxPopulation) {
        List<T> nextGeneration = new ArrayList<>(currentGeneration);

        for (T p : nextGeneration) {
            p.getFitness();
        }

        Collections.sort(nextGeneration);
        List<T> sublist = nextGeneration.subList(0, maxPopulation);
        return sublist;
    }

}

Wenn Interesse besteht, kann ich auch die restlichen Klassen (Tests und ein paar Test-Entitäten) mit hochladen.

 

[BuckRogers]

Hi,

danke. Werd mir das mal in Ruhe ansehen wenn ich Zeit habe neben der Arbeit. Mich interessiert das Thema genetischer Algorithmus einfach irgendwie ein wenig.

Wie funktioniert eigentlich recombine? Wird das unwillkürlich Männlein und Weiblein gekreuzt?
Also ich finde den Ansatz schon sehr ausgereift und erweiterbar ist es auch.
Mit selectFittest() besteht ein ziemlich starker Einfluss auf die Population. Zwar ist das zweckdienlich aber nicht natürlich ^^
Was ist eigentlich das Ziel dieser Berechnung?

Grüße

 

[Saheeda]

Hi,

ich finde das Thema auch unglaublich spannend, warum auch immer ^^

Beim Rekombinieren werden zufällig zwei Entitäten aus der Liste ausgewählt.
Anschließend wird das Genom Stelle für Stelle durchgegangen und ebenfalls wieder zufällig entweder die entsprechende Stelle von der Mutter oder vom Vater übernommen.
Die vielen zufällig generierten Sachen machen das Testen etwas schwierig, sodass auch die benötigten Zeiten nicht wirklich vorhersagbar sind.

Du hast natürlich Recht, dass es etwas übertrieben/radikal ist, jedes Mal die komplette Population zu halbieren. Ein realistischeres/zyklischeres Verhalten wäre aber eine sehr spannende Sache. Man könnte das natürlich auch als Räuber-Beute-Beziehung implementieren und im nächsten Schritt wechselnde Umweltfaktoren mit einbeziehen....
Ich glaube, ich hab mein nächstes Projekt gefunden ^^


Das ist eine Übungsaufgabe im Rahmen der Ausbildung und hat zum Zweck, was über Algorithmen zu lernen.
^^

 

[BuckRogers]

Nabend,

ja das ist super finde ich. Deine Implementierung des Algorithmus ist soweit ziemlich gut. Ich muss sagen dass du da weiter gekommen bist als ich mit meiner Aufgabe damals in der Uni. Ich sollte den genetischen Algorithmus als Suche nach der idealen Produktionskette "ausprobieren" und habe mich eher an der GUI und des Ablaufes des Algorithmus aufgehalten, anstatt eine Methodik zur Ermittlung der fittesten Individuuen zu entwickeln. Der Rucksack war sozusagen eine Produktionsschiene und die Items waren die Aufträge auf dieser Produktionsstrecke. Als Anforderung an die Suche konnte man Parameter übergeben: Anzahl Produktionsstrecken, Anzahl der Aufträge, maximale Population, maximale Generation etc. Gesucht werden sollte nach dem optimalen Ablauf. Kürzeste Gesamtzeit der Produktion für alle Strecken. Ich bin kläglich daran gescheitert. Der Professor hat mir trotzdem eine 1 gegeben. Er meinte ich hätte ohnehin mehr gemacht als erwartet wurde. hahaha... der ganze Stress umsonst.
(Das nur am Rande)

Nun zu dir ^^
Wieso gibt es keine obere Grenze für die Attribute der Items(Gewicht, Nützlichkeit)? Wäre es nicht einfacher die Fitness zu berechnen wenn man da Grenzvorgaben hätte? Ich weiß ja, dass das nur einer Interpretation ist und man das irgendwie adaptieren könnte. Bezüglich des Gewichts der Items gibt es einen Idealwert, zwar nie zu erreichen, der wäre ja 0,0 Kg. Eventuell kann man da ja mit Grenzwerten herangehen? Wieso gibt es keinen Idealwert für die Nützlichkeit? oO
Sind deine "Rucksäcke/Items" eigentlich Objekte? Doofe Frage... müssten sie ja sein, sonst kann man schwer mit Attributen arbeiten. Du redest immer von den "01" Strings und den deine ZIP habe ich noch nicht reingeschaut. ^^

Wenn du möchtest kann ich dir meinen GenAlgo code aus der Uni geben, auch wenn es dir nicht wirklich helfen würde denke ich, da du viel weiter mit der Berechnung bist als ich es war.

 

[Saheeda]

a)
Das "Problem" bei der Berechnung der Fitness mit Grenzwerten ist: Was ist perfekt?

Beim einfachen 0-1-Beispiel kann ich sagen, ein String, der nur noch aus 1 besteht, ist perfekt. Aber was ist beim Rucksack? Mir fällt keine Möglichkeit ein, irgendeinen Muster-Rucksack vorzugeben, bei dem ich sagen könnte "Wenn irgendeine Entität der Population 80% diesen Wertes erreicht ist, ist sie gut genug". Denn wenn ich einen Musterrucksack "einfach so" definieren könnte, bräuchte ich keinen Algorithmus.

b)
Da alle Entitäten mit demselben Pool arbeiten, ist die Fitness ja eh nur ein relativer Wert. Wie gut ist die aktuelle Entität im Vergleich zu allen anderen?
Dabei ist es ja ziemlich egal, ob ich mich im Prozent- oder Tausenderbereich bewege.


zu den Objekte:
Der Rucksack ist ein Objekt. Der Pool besteht aus Objekten(Items). Aber der Genotyp besteht nur aus 0 und 1 (Typ schwankt, am Anfang habe ich mit Strings gearbeitet, später bin ich auf byte[] umgeschwenkt.)
Ich persönlich fand es einfacher, einen Wert innerhalb eines Strings/Arrays zu ändern, als Objekte hin und her zu schieben.

Zum einen kosten mich Objekte deutlich mehr Speicherplatz/Rechenzeit. Bei 10 Entitäten mag das noch keine Rolle spielen, aber wenn ich immer wieder hunderte oder tausende von Entitäten (und deren Itemlisten) durchiteriere, neu verknüpfe, erzeuge und lösche, wird das glaube ich irgendwann teuer.

Zum anderen müsste ich bei Objekten ständig aufpassen, dass keines aus Versehen doppelt im Rucksack landet oder dass es dem Pool verfügbarer Items wieder hinzugefügt wird, wenn eine Kombination nicht funktioniert.
Dopplungen könnte man mit einer HashMap/HashSet vermeiden, klar. Aber ständig aufpassen, dass mir nirgendwo was verloren geht? Meehh, bin ich zu faul für.

Deswegen habe ich den Pool abstrahiert. Jedes Item im Pool hat eine feste Stelle im Genotyp und die ist entweder 0 oder 1.
Item rausnehmen? Bitflip zu 0. Item einfügen? Bitflip zu 1.



Ich hätte ehrlich gesagt nicht gedacht, dass der Algorithmus so gut ist, bis Montag hatte ich von dem Begriff des genetischen Algorithmus' noch nie was gehört ^^
Aber mich würde dein Entwurf sehr interessieren.


EDIT:
Bei der Ausgabe der Ergebnisse müsste ich dann logischerweise wieder von meinen 0-1-Array auf den Pool gehen und mir jedes Item an korrespondierender Stelle ausgeben lassen. Den Teil habe ich mir geschenkt.

 

[BuckRogers]

Hey thanks for the code,

ich hab mal n maven projekt draus gemacht. JUnit war einfach zu importieren. Hamcrest auch. Die Matcher Klasse ist die von dir? Die Abhängigkeit fehlt mir oder du hast sie mir nicht gegeben . Ich kann keine Diamonds verwennden weil ich kein Java 8 drauf habe. hahahaha ;(

UPDATE:
Problemchen gelöst. Hamcrest-all funktioniert. Typen gebe ich einfach mit.
Die rekursive Methode resolve(List){...}: Variable currentGeneration gibt es nicht lokal oder global?
NAja egal. Ich gehe erstmal pennen.

:gaen:

UPDATE:
habe einfach entities Parameter verwendet als currentGeneration. Tests laufen soweit. Toll. Jetzt aber geh ich pennen. N8 :meld: