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 Erbinformation 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. Um die Nützlichkeit von genetischen Algorithmen zu zeigen, wird hier in dem Beispiel ein Rucksack mit 20 möglichen Gegenständen gezeigt, bei dem das schlichte Durchprobieren aller Lösungen schon eine ganze Weile braucht. Dieses Durchprobieren ist bereits implementiert.

Aufgabe 1

Ergänze die Funktionsdefinitionen.

from random import *

# 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),
                (0.8, 80), (3.2, 235), (2.9, 160),(3.7, 371), (2.6, 320),
                (2.1, 90), (3.1, 230), (1.2, 52), (1.8, 130),  (2.3, 56),
                (0.76, 76), (3.2, 290), (2.1, 100)]

grenzgewichtRucksack = 25.0



# Funktionen zur Erzeugung einer Lösung

anzahlIndividuen = 1000
mutationswahrscheinlichkeit = 0.05
kreuzungswahrscheinlichkeit = 0.5



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


def erzeuge_Individuum_aus_Zahl(zahl):
    s = bin(zahl)[2:].rjust(len(gegenstaende),'0')
    individuum=[]
    for i in range(len(gegenstaende)):
        individuum = individuum+ [int(s[i])]
    return individuum


def loesungDurchprobieren():
    maxfit =-1
    for i in range(2**len(gegenstaende)-1):
        ind = erzeuge_Individuum_aus_Zahl(i)
        fit = fitness(ind)
        if fit > maxfit:
            maxfit = fit
            maxfitind = ind
        if (i % 10000)==0:
            print(".",end="")
    print()
    print("Garantiert optimale Lösung und ihre Punktzahl:", maxfitind," --> ",maxfit)
    
# Hauptprogramm

print("Durchprobieren aller Lösungen (1 Punkt entspricht 10000 Lösungen)")
loesungDurchprobieren()

print("Genetischer Algorithmus (10 Durchläufe)")
for i in range(10):
    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.