Implementierung des genetischen Algorithmus

Der Algorithmus

Hier noch einmal der Algorithmus, der zum näherungsweisen Lösen des Rucksackproblems benutzt werden soll.

ALGORITHMUS loesung mit genetischem Algorithmus 
    erzeuge eine initiale Population
    SOLANGE das Abbruchkriterium nicht erfüllt ist:
        lege eine neue Population an
        SOLANGE die Populationsgröße nicht erreicht ist:
            wähle durch Selektion 2 Individuen aus
            erzeuge 2 neue Individuen durch Kreuzung der Individuen
            verändere die Gensequenz der neuen Individuen durch Mutation
            nimm die neuen Individuen in die neue Population auf
        ersetze die alte durch die neue Population
    bestimme das Individuum mit maximaler Fitness

Eine Implementierung

Die im Algorithmus vorkommenden Aktionen lassen sich gut mit Hilfe von Funktionen modellieren und realisieren.

Aufgabe 1

Ergänze die Funktionsdefinitionen.

# Rucksackproblem

gegenstaende = [(3.5, 375), (2.5, 300), (2.0, 100), (3.0, 225), (1.0, 50),
                (1.75, 125), (0.75, 75), (3.0, 275), (2.5, 150), (2.25, 50)]
grenzgewichtRucksack = 15.0

# Funktionen zur Erzeugung einer Lösung

anzahlIndividuen = 50
mutationswahrscheinlichkeit = 0.05

from random import *

def erzeugeIndividuum():
    # ...
    return individuum

def erzeugePopulation():
    # ...
    return population
        
def fitness(individuum):
    # ...
    return wert

def kreuzung(individuum1, individuum2):
    # ...
    return (neuesIndividuum1, neuesIndividuum2)

def mutation(individuum):
    # ...
    return individuum

def selektionElternteil(population):
    # ...
    return elternteil

def naechstePopulation(population):
    # ...
    return neuePopulation

def maxFitness(population):
    # ...
    return (maxIndividuum, maximumFitness)

def loesungGenetischerAlgorithmus():
    # ...
    return loesung

# Test
for i in range(20):
    print(loesungGenetischerAlgorithmus())

Aufgabe 2

(a) Teste das Verfahren, das einen genetischen Algorithmus benutzt. Verwende deine eigene Implementierung oder die in der Datei rucksack_genetischer_algorithmus.txt.

(b) Experimentiere mit dem Lösungsverfahren, indem du die Parameter geeignet abänderst.

(c) Du kannst auch das Verfahren selbst geeignet abändern, z.B. so: In einer Population werden zuerst Nachkommen durch Kreuzung erzeugt. Die Population wächst also etwas. Danach bilden nur die fitesten Individuen die nächste Generation. Mutation muss natürlich auch an geeigneter Stelle vorgesehen werden.