---
title: Praxisprojekt
author: Sebastian Müller
date: 30. Oktober 2023
---
<style>
#title {
text-align: center;
font-weight: bold;
font-size: 220%;
padding-top: 1em;
padding-bottom: 1em;
}
</style>

<div id="title">Praxisprojekt</div>

[toc]

# Einleitung
Dieses Praxisprojekt beschäftigt sich inhaltlich mit dem Aufbau und der Implementierung einer Evolutionsstrategie.
Die fertige Implementierung soll im Nachgang für eine Untersuchung der Frage, wie sich die Selektionsmethode auf das Ergebnis auswirkt, verwendet werden und bildet das Ziel der Arbeit.
Dazu soll eine Evolutionsstrategie genutzt werden in Kombination mit dem COCO (Comparing Continuous Optimizers) Framework[^coco].
Die Arbeit wird zu Beginn die Grundlagen evolutionärer Algorithmen beleuchten und ihre Herkunft. Im folgenden werden dann die einzelnen Bestandteile der Evolutionsstrategie genauer betrachtet und die Implementierung erklärt.
Zum Schluss wird auf die fertige Implementierung auch im Zusammenhang mit dem COCO Framework eingegangen.
Die Motivation für diese Arbeit kommt zum einen aus dem auch in der Öffentlichkeit steigende Interesse an Künstlicher Intelligenz und dem persönlichen Wunsch, das in Vorlesungen erhaltene Wissen zu vertiefen.
Die Arbeit soll eine lauffähige Implementation einer Evolutionsstrategie liefern, welche in der darauffolgenden Bachelorarbeit genutzt werden soll.

# Evolutionäre Algorithmen

## Grundlagen
Seit den 1950er-Jahren dient die natürliche Evolution als Vorbild für die Lösung von Optimierungsproblemen. [^weicker]
Unter einem Optimierungsproblem versteht man eine Aufgabe, welche durch Veränderung der Parameter so beeinflusst werden kann, dass sich ein messbares Ergebnis verbessert.
Es lassen sich viele Beispiele für solche Optimierungsproblemen finden, sowohl in der Wirtschaft als auch im alltäglichen Leben.
Die Evolutionstheorie für die natürliche Evolution wurde von Charles Darwin entdeckt und niedergeschrieben in seinem Buch 'On the Origin of Species' im Jahre 1859.
Darin beschreibt er, dass in der Natur ein Lebewesen eine höhere Wahrscheinlichkeit zum überleben und sich fortzupflanzen hat, wenn es besser an seine Gegebenheiten angepasst ist.[^darwin]
Evolutionäre Algorithmen versuchen mithilfe der natürlichen Evolution als Vorbild ebenfalls Optimierungsprobleme zu lösen.
In der Informatik wird bei einem evolutionären Algorithmus eine Population von $\mu$ Individuen erstellt als initiale Elternpopulation. Diese Population wird bewertet auf das Ergebnis des Problems hin.
Danach folgt der immer gleich bleibende Aufbau des EA, der sich aus verschiedenen Phasen zusammensetzt. Zuerst der Rekombination, der Paarung der Individuen, woraus eine Kindspopulation der Größe $\lambda$, gefolgt von der Mutation, der zufälligen Veränderung mancher Gene, der Evaluierung, der Bewertung der gebildeten Kinder und zum Schluss der Selektion, der natürlichen Auslese der Individuen.
Dieser Zyklus wird n mal wiederholt, oder bis ein anderes definiertes Abbruchkriterium erreicht ist. [^kramer]
In einigen Quellen findet der Begriff des Suchoperators Verwendung, welcher den wesentlichen Teil des Algorithmus beschreibt, der den Suchraum erforscht und die Feinabstimmung vornimmt, so zum Beispiel im Buch *Evolutionäre Algorithmen* von Karsten Weicker. [^weicker]
In den folgenden Kapiteln wird weiter auf die verschiedenen Bausteine des Algorithmus eingegangen und ihre Implementierung vorgestellt.
Es gibt verschiedene Typen des evolutionären Algorithmus, welche unterschieden werden müssen. Der allgemeine Aufbau bleibt bei diesen Formen jedoch bestehen.
Diese Arbeit implementiert eine Evolutionsstrategie, welche Mitte der Sechziger von Rechenberg und Schwefel an der Technischen Universität Berlin entwickelt wurden. [^kramer]
Der Unterschied zwischen dem EA und der ES ist im wesentlichen, das der Algorithmus während der Laufzeit die Mutationswerte und die Schrittgröße adaptiert. Das bedeutet, dass die ES fähig ist, optimale Strategieparameter während der Optimierung dynamisch anzupassen, sozusagen zu erlernen.[^hoff]
Auf die genaue Umsetzung wird im Kapitel der Mutation genauer eingegangen.
Man muss erwähnen, dass sich im Laufe der Zeit der EA und die ES sich mehr und mehr angenähert haben und heute oft in Mischformen angewandt werden und nicht strikt getrennt werden.
Eine weitere Form der evolutionären Algorithmen sind die sogenannten Covariance Matrix Adaptation Evolution Strategies (kurz CMA-ES). Auf diese wird aufgrund ihrer Komplexität jedoch nicht näher in dieser Arbeit eingegangen und wurde deswegen trotz das sie aktuell als state-of-the-art gilt, nicht genutzt als Implementierung.[^cma]
Abschließend sollten auch die Genetischen Algorithmen(GA) Erwähnung finden, welche in den Siebzigerjahren von John Holland entworfen wurden. [^kramer]
Der größte Aspekt eines GA ist es, dass ein Individuum binär codiert wird. Diese Bits werden Allele genannt, was in einigen Anwendungsfällen es nötig macht, die Bit Strings zu Objekt Variablen zu mappen.[^hoff]
Zudem nutzt der GA die Rekombination als hauptsächliche Methode für den Suchoperator, lernt nicht selbst dazu. [^hoff]

graph LR
A(Initialisierung) --> B(Evaluierung)
B --> C(Rekombination)
C --> D(Mutation)
D --> E(Evaluierung)
E --> F(Selektion)
F --> G{Abbruchbedingung} 
G -->|Erreicht| H(Abbruch)
G--> |Neue Schleife| C

## Initialisierung
Der Start der Evolutionsstrategie ist die Initialisierung dieser, wobei eine erste Elterngeneration erstellt wird mit $\mu$ Individuen.
Diese ersten Lösungskandidaten können auf unterschiedliche Weise erstellt werden, doch es gibt 3 gängige Arten. [^weicker]
In der ersten Variante werden die Individuen zufällig gleichverteilt initialisiert.
Die zweite Variante wählt einen bereits bekannten Lösungskandidaten als Startpunkt der Initialisierung. Die Individuen werden um diesen Startpunkt herum verteilt initialisiert.
Die letzte gängige Variante ist das Nutzen von Ergebnissen anderer Optimierungsverfahren. [^weicker]
In dieser Arbeit wird die erste Variante angewandt, da die Initialisierung auf verschiedenen Lösungsfunktionen des CoCo Frameworks angewandt werden soll.

 population = np.zeros(shape=(self._mu, D + 2))

Zuerst wird eine initiale Population angelegt, welche eine Matrix darstellt mit den Dimensionen ($\mu$, D+2), wobei $\mu$ die Anzahl der Elternindividuen ist und D die Anzahl der Parameter des Individuums. Die letzten beiden Gene des Individuums stellen seine Mutationsrate und seinen Fitnesswert dar.

 population[:, D] = self._sigma*np.exp(τ * rnd.normal(0, 1, size=self._mu))

Anschließend werden bei allen Individuen der Population die initialen Schrittweiten der Mutation bestimmt. Dafür wird die initiale Schrittweite $\sigma$ mit dem Ergebnis der Exponentialfunktion von $\tau$, welches $\frac{1}{\sqrt{2*D}}$ ist, und einer normalverteilten Zufallszahl im Raum von 0 bis 1 multipliziert.
Die mathematische Formel für die Schrittweite ist also:
$\sigma_1$=$\sigma_0 \cdot e^{\tau \cdot \phi}$

## Rekombination
Die Rekombination stellt einen wesentlichen Bestandteil der Evolutionsstrategie dar, da sie genutzt wird für die Generierung von neuen Individuen durch die Rekombination der Merkmale zweier Elternindividuen um ein neues Kindindividuum zu erstellen. [^weicker]
Analog der Biologie dient die Rekombination der Durchmischung der Population und kann in verschiedenen Varianten implementiert werden. In Evolutionsstrategien werden Informationen aus mehreren Eltern (p) genutzt, um ein Kind zu erstellen häufig mit mehr als 2 Eltern.[^rowe]
Im Kontrast dazu werden in genetischen Algorithmen oft 2 Kinder aus 2 Eltern erstellt, und in der evolutionären Programmierung wird generell keine Rekombination genutzt. [^rowe]
In den Evolutionsstrategien gibt es drei gängige Varianten, die genutzt werden, diskrete oder dominante Rekombination, Intermediäre Rekombination oder die gewichtete Multirekombination, die eine Generalisierung der intermediären Rekombination darstellt. [^rowe]
Die diskrete Rekombination ist auch bekannt als *uniform crossover* in genetischen Algorithmen.[^rowe]
Bei dieser Art der Rekombination wird ein Austausch der Gene zwischen den Eltern zur Bildung der Nachkommen durchgeführt, dabei wird für jedes Gen entschieden, von welchem Elternteil der Wert entnommen wird. [^pohl]
Im allgemeinen ist die Rolle der Rekombination die Diversität in der Population hoch zu halten, die diskrete Rekombination erreicht dies durch das Erstellen neuer Lösungskandidaten. [^rowe]
Die diskrete Rekombination kann nur dann sinnvoll genutzt werden und erfolgreich Variation in die Population bringen, wenn die Gene nicht stark voneinander abhängig sind. [^rowe]
Ein klassisches Beispiel einer diskreten Rekombination ist der Uniformer-Crossover, welcher für jedes Gen zufällig entscheidet, ob das Kind das Gen des Elternindividuums A oder B erhält.

def uniformer_crossover(A,B):
    for index in A.length():
        rndNo = random(0,1)
        if rnd = 0:
            child1[index] = A[index]
            child2[index] = B[index]
        else:
            child1[index] = B[index]
            child2[index] = A[index]
    return child1, child2

Intermediäre Rekombination verfolgt den Ansatz, den Mittelwert aller Elternindividuen für ein Gen zu ermitteln und diesen in das Kind zu übernehmen. [^rowe]
Im Gegensatz zur diskreten Rekombination, welche die Diversität der Population erhält, führt die intermediäre Rekombination dazu, dass die Population sich auf einen Punkt zu konvergiert. [^rowe]
Diese Variante erlaubt es dem Mutationsoperator, durch die sogenannte genetische Reparatur eine zusätzliche Variation einzuführen. [^rowe]
Das Mitteln der Werte reduziert die Schrittgröße in eine der Lösung nicht zuträglichen Richtung um $\sqrt[]\mu$, lässt die Schrittgröße in Richtung einer Lösung aber fast unverändert. [^rowe]
Dies lässt die Möglichkeit offen, eine stärkere Mutation zu wählen, bis zu einem Faktor von $\mu$, um einen bestmöglichen Fortschritt zu erreichen. [^rowe]
Die gewichtete Multirekombination ist eine Generalisierung der intermediären Rekombination und nimmt normal an das p=$\mu$ ist.[^rowe]
Es wird ein gewichteter Mittelwert für die Gene ermittelt, wobei die Gewichtung der Eltern abhängig ihrer Fitnesswerte ist, also das bessere Elternindividuen immer größere Gewichte als schlechtere Individuen erhalten.[^rowe]
Sollten die Gewichte gleich sein bei allen Individuen ist man wieder bei der intermediären Rekombination.[^rowe]
In der Theorie ist es auch möglich, Rekombinationen wie den one-point Crossover zu verwenden, doch diese wurden nur selten in Evolutionsstrategien angewandt und werden daher in dieser Arbeit nicht näher betrachtet. [^rowe]
In Evolutionsstrategien ist das Ergebnis von Selektion und Rekombination oft deterministisch, also p=$\mu$ und eine intermediäre oder gewichtete Rekombination. [^rowe]
In dieser Arbeit wird die intermediäre Rekombination genutzt.

class IntermediateRecombination:
    def __init__(self, ρ):
        self._rho = ρ

    def __call__(self, population, λ):
        """Produce λ offspring from population by averaging the ρ best"""
        μ, D = population.shape
        children = np.zeros(shape=(λ, D))

        for l in range(λ):
            idx = rnd.choice(μ, replace=False, size=self._rho)
            children[l, :D] = np.mean(population[idx, :D], 0)
            children[l, -2] = np.median(population[idx, -2])
        # Clear function values
        children[:, -1] = np.nan
        return children

Die Klasse wird initialisiert mit dem übergebenen Wert $\rho$ und kann dann aufgerufen werden mit der aktuellen Population und $\lambda$. Zuerst werden $\lambda$ Kinder angelegt mit derselben Dimension wie bei der Elterngeneration.
Nun wird für jedes Kind folgendes wiederholt bis $\lambda$ Kinder generiert wurden.
Es wird begonnen, indem zufällig $\rho$ Werte ausgewählt werden, welche im Bereich von $\mu$ liegen müssen und nicht doppelt gewählt werden dürfen. Dies liefert eine Auswahl von $\rho$ zufälligen Eltern Individuen.
Anschließend wird der Mittelwert der Parameter an jeder Stelle der ausgewählten Eltern ermittelt und in das neue Kind eingefügt.
Als nächstes wird der Mutationsparameter des Kindes bestimmt, indem der Median über die ausgewählten Eltern bestimmt wird und in das Kind eingefügt wird.
Diese Schritte werden solange wiederholt, immer mit neu zufällig gewählten Eltern bis $\lambda$ Kinder erzeugt wurden.
Der letzte Schritt, welcher vorgenommen wird, ist den Fitnesswert aller erzeugten Kinder auf nan zu setzen und die neue Kinder Population zurückzuliefern.

## Mutation
Der Mutationsoperator kann unterschiedliche Aufgaben in der Evolutionsstrategie erfüllen, so kann die Mutation genutzt werden, um maßgeblich die Individuen Richtung Optimum zu führen oder sie stellt nur eine untergeordnete Rolle dar, da andere Operatoren die Rolle des Suchoperators erfüllen, und wird genutzt, um die Vielfalt der Population zu erhalten. [^weicker]
Stellt die Mutation die Rolle des Suchoperators, übernimmt sie zwei Funktionen, einmal die Feinabstimmung (engl. *exploitation*), welche von einem Lösungskandidaten ausgehend das lokale Optimum finden soll.[^weicker]
Zum anderen übernimmt sie in diesem Falle die Rolle des stichprobenartigen Erforschens (engl. *exploration*) von weiter entfernten Gebieten des Suchraums, um ein potenziell besseres lokales Optimum zu finden.[^weicker]
In dieser Arbeit übernimmt die Mutation nur eine untergeordnete Rolle und dient als Hintergrundoperator zur Erhaltung der Vielfalt der Population.
Wie in Evolutionsstrategien üblich, wird die Schrittweite $\sigma$ im Verlauf weiter adaptiert.
Die Mutation soll im Zuge des Verlaufs an die aktuelle Situation des Optimierungsprozesses angepasst werden. [^weicker]
Hierzu kann man sich eine von drei Strategien zunutze machen, welche die Mutationsrate anpassen.
Die erste Strategie ist eine vorbestimmte Anpassung von $\sigma$ mit einem Modifikationsfaktor $\alpha$, in der Hoffnung, das Lokalität im Genotyp und der Bezug auf die Fitness stark korrelieren. [^weicker]
Dies kann im Einzelfall sinnvoll sein, allgemein muss man aber feststellen, dass diese Vorgehensweise nicht garantiert, dass die Anpassung auch hilfreich für den Optimierungsverlauf ist, da es keine Kopplung zwischen Suchprozess und Anpassung gibt. [^weicker]
Die zweite Strategie ist das Einführen einer Regel, welche aus dem Stand der Optimierung die notwendigen Veränderungen ableitet. [^weicker]
Um dies abzubilden, wird der Erfolgsparameter $p_s$ eingeführt, welcher den Anteil der Mutationen in den letzten k Generationen entspricht, welche eine Verbesserung bewirkt haben. [^weicker]
Es folgt also, dass je kleiner $p_s$ ist, desto näher befindet man sich am Optimum, und die Mutation muss lokaler werden, dazu wird der Schwellwert $\Theta$ festgelegt, welcher angibt, wann $\sigma$ vergrößert oder verkleinert wird. [^weicker]
Die letzte Strategie ist die Selbstadaption, welche im Gegensatz zur Adaption eine individuellere und flexiblere Anpassung ermöglichen soll, damit verhindert wird, zum Beispiel bei vielen lokalen Optima zu schnell zu konvergieren. [^weicker]
Um dies zu erreichen, wird jedes Individuum um einen Strategieparameter ergänzt, welcher sich vereinfacht merkt, mit welchen Einstellungen dieses Individuum entstanden ist. [^weicker]
In dieser Arbeit wird der einfache Ansatz der Selbstadaptiven-Gauss-Mutation verwendet. Dieser setzt den Strategieparameter $\sigma$ und unterwirft die Veränderung des Strategieparameters selbst einer zufälligen Evolution.[^weicker]
Da $\sigma$ nicht kleiner als 0 werden darf, wird die Veränderung mit einer positiven Zahl der Exponentialfunktion unter Berücksichtigung der Dimension des Suchraums multipliziert.[^weicker]

Zuerst erfolgt die Selbstadaption, dafür wird $\sigma_0$ wieder mit der Exponentialfunktion von $\tau$ mal der Standardabweichung multipliziert. Es ergibt sich also als Formel zur Selbstadaption:
$\sigma_1$=$\sigma_0 \cdot e^{\tau \cdot \phi}$

offspring[:, -2] *= np.exp(tau * rnd.normal(0, 1, size=self._lambda))

Nach der Selbstadaption werden die Gene der Kinder mit einer zufälligen Normalverteilung N(0,$\sigma$) addiert.

offspring[:, :D] += np.random.normal(0, offspring[:, -2][:, np.newaxis], size=(self._lambda, D))

## Evaluierung
Die Evaluierung ist der Teil der Evolutionsstrategie, welcher jedes Individuum anhand der gegebenen Zielfunktion des Optimierungsproblems evaluiert und den Individuen einen Wert zuweist. Dieser Score gibt an, wie gut das Individuum auf der gegebenen Zielfunktion ist, also das Optimierungsproblem löst.
In dieser Arbeit wird das Coco Framework verwendet, welches 25 Zielfunktionen bietet, auf denen das Individuum bewertet werden kann. Die Zielfunktionen werden "problem" im Framework genannt und sind Minimierungsprobleme, das bedeutet, wir möchten einen möglichst geringen Score erreichen auf der Zielfunktion.

offspring[:, -1] = np.apply_along_axis(fn, 1, offspring[:, :D])

## Selektion
Bei der Selektion in einer Population soll die Allelhäufigkeit durch unterschiedlich viele Nachkommen der einzelnen Allele beeinflusst werden. [^weicker]
In der Natur passiert dies durch Faktoren wie die Überlebenschance(Umweltselektion) oder der Fähigkeit, Geschlechtspartner zu finden(Sexuelle Selektion).[^weicker]
Die Selektion ist der einzige gerichtete Vorgang in der Evolution, betrachtet dabei allerdings nicht einzelne Gene, sondern betrachtet den gesamten Phänotyp. [^weicker]
Dieses Prinzip lässt sich über den Fitnesswert messen.
Bei einer reinen Auswahl der Selektion würde sich lediglich die vorteilhafteste Form einer Art durchsetzen.[^weicker]
Dem zuwider kann man den Polymorphismus beobachten, welcher verschiedene Erklärungen haben kann wie ein wechselseitiger Selektionsvorteil, doch insgesamt lässt sich sagen, dass eine Population mit Polymorphie durch eine große Vielfalt eine größere Anpassungsfähigkeit und eine bessere Überlebenschance hat. [^weicker]
Dieses Verhalten aus der Natur soll in den evolutionären Algorithmus nun mit einfließen.
Für die Selektion lassen sich verschiedene Anforderungen definieren. Es sollen aus der Population von den vorhandenen Individuen die nächsten Elternindividuen ausgewählt werden. Wir wollen eine möglichst große Vielfalt erhalten, aber auch die wirklich besten Individuen auswählen. [^weicker]
Diese Ziele können im direkten Widerspruch stehen, besonders wenn die Rekombination und Mutation unveränderte Kopien von Individuen ermöglichen. [^weicker]
Es gibt 2 Varianten, um mit diesen Anforderungen umzugehen. Zum einen die deterministische Selektion, welche nur die besten Individuen selektiert. Der zweite Ansatz ist die nicht-deterministische Selektion, welche zufällig Individuen auswählt und besseren Individuen eine höhere Wahrscheinlichkeit zuweist, selektiert zu werden.
Zusätzlich gibt es 2 Möglichkeiten, aus welcher Menge die Individuen selektiert werden, nur die Kindspopulation kann betrachtet werden, sofern $\lambda$ größer gleich $\mu$ ist. In der zweiten Option werden Eltern und Kindpopulation zusammengefasst und aus der gesamten Menge die Individuen selektiert.
Die Selektionsoperatoren bestimmen demnach maßgeblich den Selektionsdruck, dem die Individuen ausgesetzt sind. Ein hoher Selektionsdruck fördert die Feinabstimmung (Exploitation), während ein geringerer Selektionsdruck die Erforschung des Suchraums fördert(Exploration).[^bremen]
Die Selektion kann in einem evolutionären Algorithmus auf verschiedene Arten eingebunden werden. Die Elternselektion wählt die Individuen, welche sich reproduzieren sollen, während die Umweltselektion die Individuen wählt, welche in die nächste Generation übernommen werden sollen. [^bremen]

Auf die verschiedenen Selektionsvarianten und die konkrete Umsetzung im Projekt wird nun näher eingegangen in den folgenden Kapiteln.

### Deterministische Selektion
Bei der deterministischen Selektion sollen die Individuen gemäß ihrer Fitness gewählt werden.
Die Individuen werden innerhalb der Population nach ihrem Fitnesswert sortiert und die $\mu$ besten Individuen werden für die neue Population ausgewählt.
Bei dieser Art der Selektion kann man oft eine vorzeitige Konvergenz in lokale Optima beobachten. [^weicker]
Dies kann aber auch ein gewünschter Effekt sein, eine schnelle Konvergenz zu erreichen, da man den Algorithmus gezielter zu einer Lösung konvergieren lassen kann.
Deterministische Selektion ist somit ein guter Kandidat, um einen hohen Selektionsdruck zu erzeugen.
Im folgenden werden 2 Varianten der deterministischen Selektion betrachtet die Kommaselektion und die Plusselektion.

#### Kommaselektion
Die Kommaselektion ($\mu$,$\lambda$) nutzt bei der Selektion nur die Kinder, die erzeugt wurden durch die Evolutionsstrategie.
Diese Art der Selektion wird teilweise als nicht-überlappend bezeichnet, da Eltern und Kindpopulation getrennt voneinander betrachtet werden. [^weicker]
Nach dem sortieren der Individuen nach dem Fitnesswert und anschließend die $\mu$ besten Individuen ausgewählt.

def CommaSelection(parents, children):
    N = parents.shape[0]
    r = rank(children[:, -1])
    return children[r < N, :]

#### Plusselektion
Die Plusselektion ($\mu$+$\lambda$) führt die Eltern- und Kindspopulation zusammen und sortiert nun die gesamte Population nach ihrem Fitnesswert.
Auch hier werden wieder die $\mu$ besten Individuen gewählt.
Diese Art der Selektion kann auch als überlappende Selektion bezeichnet werden. [^weicker]

def PlusSelection(parents, children):
    N = parents.shape[0]
    population = np.r_[parents,children]
    r = rank(population[:,-1])
    return children[r < N, :]

### Nicht-Deterministische Selektion
Nicht deterministische Selektion ist der Ansatz, Individuen "zufällig" auszuwählen, was dazu führt, die Vielfalt der Population zu erhalten.
Bei dieser Art der Selektion nehmen wir die Gesamtheit der Population als mögliche Kandidaten für die nächste Generation, aber die Wahrscheinlichkeit, gewählt zu werden, kann über die Fitnesswerte der Individuen beeinflusst werden.
Diese Variante ermöglicht es, den Suchraum weiter zu erkunden und die Suche breiter zu gestalten.
In dieser Arbeit werden eine Turnierselektion mit zufälliger Wahl der Teilnehmer und eine proportionale Selektion als nicht deterministische Selektionsoperatoren implementiert.

#### Turnierselektion
Die Turnierselektion verfolgt den Ansatz, die Wahl eines Individuums nicht zu nah an die Fitnesswerte des Individuums zu koppeln. [^weicker]
Dazu wird ein Parameter *k* verwendet, welcher unter der Bedingung k$\leq$$\mu$ gewählt wird. Darauf folgend werden *k* Individuen zufällig aus der Population gewählt und dann soll das beste Individuum gewählt werden. [^weicker]
Auch wenn *k* beliebig gewählt werden kann, ist der am häufigsten verwendete Parameter k=2. Desto näher *k* an $\mu$ gewählt wird, desto höher ist folglich die Wahrscheinlichkeit, das nur die besten Individuen der Population gewählt werden.[^weicker]
Die Wahrscheinlichkeit, dass ein Individuum gewählt wird, ist demnach:
W=$\frac{2r(i)-1}{\mu^2}$
Der gesamte Ablauf der Wahl eines Individuums wird $\mu$ mal durchgeführt, um die entsprechende Anzahl an Individuen für die neue Generation auszuwählen.

def TournamentSelection(parents,children,tournament_size=2):
    N = parents.shape[0]
    offspring = np.zeros(shape=parents.shape)
    for i in range(N):
        tournament = rnd.choice(children.shape[0], tournament_size)
        contestant1 = children[tournament[0]]
        contestant2 = children[tournament[1]]
        if contestant1[-1] < contestant2[-1]:
            offspring[i] = contestant1
        else:
            offspring[i] = contestant2
    return offspring

#### Proportionale Selektion
Fitness proportionale Selektion ist der Ansatz, die Analogie der biologischen Fitness genau zu nehmen. In der Biologie ist die Fitness ein Wert dafür, wie viele Kinder bei einem Individuum zu erwarten sind. [^weicker]
In einer von der Größe festen Population in der Evolutionsstrategie wird dies modelliert durch den Ansatz, dass die Auswahl eines Individuums proportional zur Fitness ist. [^weicker]
Das bedeutet, dass die Wahrscheinlichkeit des Individuums gewählt zu werden sich beschreiben lässt als:
W=$\frac{f(x)}{\sum_{\mu+\lambda}f(\mu+\lambda)}$
Diese Art der Selektion wird oft durch den Rouletteerad-Algorithmus implementiert, weswegen er auch für diese Arbeit gewählt wurde.

def RouletteWheel(parents,children):
    N = parents.shape[0]
    offspring = np.zeros(shape=parents.shape)
    fitness_sum = np.sum(children[:,-1])
    for i in range(N):
        r = rnd.uniform(0, fitness_sum)
        c = 0
        for x in children:
            c += x[-1]
            if c > r:
                offspring[i] = x
                break
    return offspring

## Implementierung
Die Teile der Evolutionsstrategie werden als Funktionen bereitgestellt und im gesamten über eine Klasse realisiert.

class EvolutionaryStrategy:
        def __init__(self, μ: int, λ: int, σ0: int,
                 selection=PlusSelection,
                 recombination=BinaryRecombination,
                 verbose=False):
        self._mu = μ
        self._lambda = λ
        self._sigma = σ0
        self._selection = selection
        self._recombination = recombination
        self._verbose = verbose

Die Klasse wird in einem Python Programm initialisiert, welches auch die nötigen Komponenten des Coco Frameworks initialisiert. Darunter die entsprechende Suite, die die Fitnessfunktionen beinhaltet, im Coco "Problem" genannt.

suite = cocoex.Suite(suite_name, "", "")
observer = cocoex.Observer(suite_name, "result_folder: " + output_folder)
minimal_print = cocoex.utilities.MiniPrint()

### go
for problem in suite:  # this loop will take several minutes or longer
    problem.observe_with(observer)  # generates the data for cocopp post-processing
    x0 = problem.initial_solution
    es = EvolutionaryStrategy(μ=10, λ=70, σ0=1,
                              selection=CommaSelection,
                              recombination=IntermediateRecombination(5))
    # apply restarts while neither the problem is solved nor the budget is exhausted
    while (problem.evaluations < problem.dimension * budget_multiplier
           and not problem.final_target_hit):
        es(problem, x0, maxiter=500)
        x0 = problem.lower_bounds + ((rand(problem.dimension) + rand(problem.dimension)) *
                    (problem.upper_bounds - problem.lower_bounds) / 2)
    minimal_print(problem, final=problem.index == len(suite) - 1)

Der Observer wird genutzt, um die Ergebnisse der Evolutionsstrategie in einem Ergebnis Ordner festzuhalten.
Die Evolutionsstrategie wird mit den nötigen Parametern, darunter die gewünschte Selektion, initialisiert. Das Programm läuft solange, bis das Budget am Limit ist oder das Problem gelöst wurde.
Nach dem Durchlauf der Evolutionsstrategie wird eine neue zufällige Startposition innerhalb der Ränder des Optimierungsproblems erzeugt.
Nach Durchlauf der While-Schleife wird eine Ausgabe generiert, welche entweder "|" ausgibt, sollte das Optimum des Problems gefunden worden sein oder "." bei anderen Ergebnissen der Evolutionsstrategie.

Zum Schluss wird das von Coco bereitgestellte Postprocessing gestartet, welches die Ergebnisse in grafischer Form darstellt und in einem Browser direkt anzeigt.

cocopp.main(observer.result_folder)  
webbrowser.open("file://" + os.getcwd() + "/ppdata/index.html")

Das Programm kann über eine Kommandozeile leicht aufgerufen werden.

python3 ES_PP.py

Es wird mindestens Python 3.6 vom Coco benötigt, so wie die Module setuptools, numpy, scipy, matplotlib und six um, besonders für das Post-Processing, aber auch für Funktionen innerhalb der Evolutionsstrategie.
Ein beispielhafter Output nach dem Ausführen des Programms wäre:

# Schluss
Zusammenfassend lässt sich festhalten, dass es vielfältige Varianten gibt, um Evolutionsstrategien zu implementieren und fast jeder Teil der Evolutionsstrategie kann durch andere Verfahren abgebildet werden.
Dadurch wird das Thema sehr komplex, lässt sich aber auch auf viele Optimierungsprobleme anwenden und es könnte interessant sein, auch andere Operatoren neben dem Selektionsoperator untereinander zu vergleichen.
Das Ergebnis dieser Arbeit ist nun ein ausführbares Python Programm, welches die verschiedenen Selektionsoperatoren nutzen kann und mithilfe des Coco Postprocessing ist eine Auswertung der Ergebnisse gut und leicht möglich.
Das Programm wird im Zuge der Bachelorarbeit genutzt werden, um den angestrebten Vergleich der Selektionen durchzuführen und mehrere Testläufe zu machen.
Das Coco Postprocessing wird in der Bachelorarbeit genutzt werden, um leicht die verschiedenen Läufe der Operatoren und den Vergleich der Operatoren untereinander zu ermöglichen.
Der gesamte Code kann im folgenden Github Repository eingesehen und runtergeladen werden: https://github.com/Arraail/Evolutionsstrategie

# Literaturverzeichnis
[^coco]: N. Hansen, A. Auger, R. Ros, O. Mersmann, T. Tušar, D. Brockhoff. COCO: *A Platform for Comparing Continuous Optimizers in a Black-Box Setting*, Optimization Methods and Software, 36(1), S. 114-144, 2021.
[^weicker]: Vgl. Weicker, Karsten: *Evolutionäre Algorithmen*, 3. Aufl. Springer, 2015, Seite 1
[^darwin]: Vgl. Darwin, Charles: *The Origin of Species*, 6. Aufl. Signet Classics, New York 2003
[^kramer]: Vgl. Kramer, Oliver: *Evolutionäre Algorithmen kurz gefasst*, Version 1.1, Universität Paderborn, Seite 4 [Link](https://www.researchgate.net/profile/Oliver-Kramer/publication/251750785_Evolution_are_Algorithmen_kurz_gefasst1/links/543d135a0cf2c432f74247ea/Evolution-are-Algorithmen-kurz-gefasst1.pdf) (Zuletzt abgerufen am: 28.10.2023)
[^hoff]: Vgl. Hoffmeier, Bäck: *Genetic Algorithms and Evolution Strategies: Similarities and Differences*, Universität Dortmund, Seite 1
[^cma]: https://cma-es.github.io (Zuletzt abgerufen am 28.10.2023)
[^bremen]: Vgl. *Prinizpien Evolutionärer Algorithmen*, Uni Bremen
[Link](https://agra.informatik.uni-bremen.de/doc/lehrmat/wise0405/ea/kap3.pdf)
(Zuletzt abgerufen am: 08.02.2024)
[^rowe]: Vgl. Rowe, J.E. Genetic Algorithms. In: Kacprzyk, J., Pedrycz, W. (eds) *Handbook of Computational Intelligence*, Springer Handbooks, Springer , 2015
[^pohl]: Vgl. *Entwicklung und systemtechnische Anwendung Evolutionärer Algorithmen*, Hartmut Pohlheim [Link] http://www.pohlheim.com/diss/text/diss_pohlheim_ea-10.html (Zuletzt abgerufen am: 12.03.2024)