06-fallstudie-genetic-algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5727c59b",
   "metadata": {},
   "source": [
    "# Genetische Algorithmen\n",
    "\n",
    "#### Patrick Schnider, Departement Mathematik und Informatik, Universität Basel "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0c72071",
   "metadata": {},
   "source": [
    "In dieser Fallstudie werden wir eine Strategie kennenlernen, um schwierige Probleme zu lösen. Der Ansatz ist einfach: Wir probieren verschiedene Lösungen aus, und kombinieren die vielversprechendsten davon zu neuen, hoffentlich besseren Lösungen. \n",
    "\n",
    "Die Strategie, die wir hier anwenden ist unter dem Namen *Genetische Algorithmen* bekannt, da diese einen evolutionären Prozess simulieren.  \n",
    "\n",
    "Genetische Algorithmen sind auch eine Anwendung, bei der wir extensiv mit Listen, Listen von Tupeln, und Listen von Listen arbeiten müssen. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6583a4af",
   "metadata": {},
   "source": [
    "### Problemstellung: Knapsack Problem\n",
    "\n",
    "Als praktisches Problem, das wir mit genetischen Algorithmen lösen wollen, betrachten wir das Knapsack-Problem. Dies ist ein klassiches Problem in der Informatik. Die Aufgabe ist es, einen Rucksack so zu packen, dass die darin enthaltenen Gegenstände einen möglichst grossen Nutzen bringen. Der gepackte Rucksack darf aber ein bestimmtes Maximalgewicht nicht überschreiten. \n",
    "\n",
    "Als Beispiel berachten wir folgende Gegenstände:\n",
    "\n",
    "| Gegenstand | Gewicht | Nutzen | \n",
    "|------------|---------|--------|\n",
    "| Schlafsack | 15      |  15    |\n",
    "| Seil       | 3 | 7 |\n",
    "| Messer | 2 | 10 | \n",
    "| Taschenlampe | 5 | 5|\n",
    "| Flasche | 9 | 8 | \n",
    "| Essen | 20 | 17|\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a58700d",
   "metadata": {},
   "source": [
    "#### Aufgabe\n",
    "\n",
    "* Wie können wir so eine Tabelle in Python abbilden?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ab38d71",
   "metadata": {},
   "source": [
    "Diese Liste können wir als Liste von Tupeln abbilden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8fdaf847",
   "metadata": {},
   "outputs": [],
   "source": [
    "packing_list = [\n",
    "    (\"Schlafsack\", 15, 15),\n",
    "    (\"Seil\", 3, 7),\n",
    "    (\"Messer\", 2, 10),\n",
    "    (\"Taschenlampe\", 5, 5),\n",
    "    (\"Flasche\", 9, 8),\n",
    "    (\"Essen\", 20, 17)\n",
    "]\n",
    "\n",
    "# Das erlaubte Maximalgewicht\n",
    "max_weight = 30\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46f4e04e",
   "metadata": {},
   "source": [
    "### Gene zur Repräsentation der Lösung\n",
    "\n",
    "Die Idee hinter genetischen Algorithmen ist jetzt, dass wir eine mögliche Lösung als Liste von 0 und 1 abbilden. Wenn an der ersten Stelle eine 1 steht, dann nehmen wir den Entsprechenden Gegenstand mit. Wenn eine 0 steht, wird der Gegenstand zuhause gelassen. Die Liste\n",
    "\n",
    "```\n",
    "[0, 1, 0, 0, 1, 0] \n",
    "```\n",
    "repräsentiert eine Lösung, bei der wir das Seil und die Flasche mitnehmen. \n",
    "\n",
    "Eine solche Liste wird, in Anlehnung an die Genetik,  Chromosom genannt. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1555c651",
   "metadata": {
    "tags": []
   },
   "source": [
    "##### Aufgabe \n",
    "\n",
    "Schreiben Sie eine Funktion, die ein zufälliges Chromosom der richtigen Länge generiert. Nutzen Sie dazu die Funktion `random.randint`, die Sie schon früher kennengelernt haben. Zur Erinnerung:\n",
    "```\n",
    "random.randint(0, n)\n",
    "```\n",
    "erzeugt zufällige Ganzzahlen im Interval $[0, n]$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f97a5e94",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def random_chromosome():\n",
    "    chromosome = []\n",
    "    # Implementation missing\n",
    "    return chromosome\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33ff7028",
   "metadata": {},
   "source": [
    "Wir schreiben nun eine Funktion, die ein Chromosom entgegennimmt und eine Liste mit den Gegenständen ausgibt, die in der Lösung enthalten sind. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1cd7313",
   "metadata": {},
   "outputs": [],
   "source": [
    "def packed_items(chromosome):\n",
    "    item_list = []\n",
    "    # Implementation missing\n",
    "    return item_list\n",
    "\n",
    "print(packed_items(random_chromosome()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab38bba3",
   "metadata": {},
   "source": [
    "Zudem brauchen wir noch eine Funktion, die uns eine zufällige Population von Chromosomen erzeugt. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40a27bbf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_population(n):\n",
    "    population = []\n",
    "    for i in range(0, n):\n",
    "        chromosome = random_chromosome()\n",
    "        population.append(chromosome)\n",
    "    return population\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b91a935",
   "metadata": {},
   "source": [
    "### Fitnessfunktion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1615cb8",
   "metadata": {},
   "source": [
    "Nun können wir eine Fitnessfunktion schreiben. Die Fitnessfunktion gibt uns für jedes Chromosom (also jede Lösung) einen Fitnesswert. Dieser entspricht einfach dem aufsummierten Nutzen. Wenn das Gewicht über dem erlaubten Totalgewicht liegt, ist die Fitness 0. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9706e9df",
   "metadata": {},
   "source": [
    "#### Aufgabe\n",
    "\n",
    "Implementieren und testen Sie die Fitnessfunktion "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0ff52d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fitness(chromosome):\n",
    "    # Implementation missing\n",
    "    return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98ea6c9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(fitness([0, 1, 0, 1, 1, 1]))\n",
    "print(fitness([1, 0, 0, 0, 0, 0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "838f40fc",
   "metadata": {},
   "source": [
    "### Genetische Algorithmen\n",
    "\n",
    "Genetische Algorithmen führen nun eine Simulation durch, in der eine Population von Chromosomen über Generationen entwickelt wird. Dabei kommt folgender Mechanismus zum tragen:\n",
    "\n",
    "1. Fittere Chromosomen werden mit höherer Wahrscheinlichkeit ausgewählt\n",
    "2. Diversität in der Population wird gewahrt, indem eine Art Fortpflanzung (cross_over) stattfindet, bei der die Chromosomen gemischt werden. \n",
    "3. Es werden zufällige Mutationen eingeführt. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a20a134e",
   "metadata": {},
   "source": [
    "#### Selektion von guten Chromosomen\n",
    "\n",
    "Die folgende Funktion selektiert zufällig Chromosomen aus der Population. Dabei ist die Wahrscheinlichkeit eines Chromosoms selektiert zu werden proportional zur Fitness.\n",
    "\n",
    "*Hinweis: Sie müssen diesen Algorithmus nicht im Detail verstehen. Dies ist auch manchmal in der Praxis so. Sie müssen die Funktion aber anwenden können*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e8527ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def select_surviving(population):\n",
    "    roulette_wheel = []\n",
    "    for chromosome in population:\n",
    "        fitness_of_chromosome = fitness(chromosome)\n",
    "\n",
    "        for i in range(0, fitness_of_chromosome):\n",
    "            roulette_wheel.append(chromosome)\n",
    "\n",
    "    new_population = []\n",
    "    for i in range(0, len(population)):\n",
    "        r = random.randint(0, len(roulette_wheel) - 1)\n",
    "        new_population.append(roulette_wheel[r])\n",
    "        \n",
    "    return new_population\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "061a1317",
   "metadata": {},
   "source": [
    "Wir können nun eine Simulation starten. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "10217325",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulate(num_initial_genes, num_generations):\n",
    "    \n",
    "    population = random_population(num_initial_genes)    \n",
    "    for i in range(0, num_generations):\n",
    "        population = select_surviving(population)\n",
    "        i = i + 1\n",
    "    return population\n",
    "\n",
    "# Hier folgt eine Ausgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15f913b4",
   "metadata": {},
   "source": [
    "#### Aufgabe:\n",
    "\n",
    "* Geben Sie die Population nach 100 Generationen aus. Wie sieht dies aus?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab87c537",
   "metadata": {},
   "source": [
    "Um die Diversität zu erhalten, können wir eine zufällige Mutation auf jedem Chromosomen einführen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a1dfbd87",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate(chromosome):\n",
    "    new_chromosome = []\n",
    "    r = random.randint(0, len(chromosome) - 1)\n",
    "    for i in range(0, len(chromosome)):\n",
    "        if i != r:\n",
    "            new_chromosome.append(chromosome[i])\n",
    "        else:\n",
    "            new_chromosome.append(1 - chromosome[i])\n",
    "    return new_chromosome"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec6e18ef",
   "metadata": {},
   "source": [
    "In der Simulation mutieren wir dann jedes Chromosome mit einer bestimmten Wahrscheinlichkeit. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d075015",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulate(num_initial_genes, num_generations):\n",
    "    \n",
    "    mutation_probability = 0.5\n",
    "    \n",
    "    population = random_population(num_initial_genes)    \n",
    "    for i in range(0, num_generations):\n",
    "        population = select_surviving(population)\n",
    "        for j in range(0, len(population)):\n",
    "            \n",
    "            if random.randint(0, 100) < mutation_probability * 100:\n",
    "                population[j] = mutate(population[j])\n",
    "        i = i + 1\n",
    "    return population\n",
    "\n",
    "# Hier folgt eine Ausgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f182e368",
   "metadata": {},
   "source": [
    "Eine weitere Möglichkeit die Diversität zu erhalten ist, dass wir Chromosomen mischen. Der erste Teil des Chromosomens wird von einem Elternteil genommen, der Zweite Teil vom anderen. Der Punkt, an welchem die Chromosomen geteilt werden, wird zufällig ausgewürfelt. In folgendem Beispiel ist dies an Position 4. \n",
    "\n",
    "Beispiel\n",
    "\n",
    "| | | \n",
    "|----------|----------|\n",
    "| Parent 1 | Parent 2 | \n",
    "| 00100101 |  11011110 |  \n",
    "| Child 1  | Child 2 | \n",
    "| 00101110 | 11010101 |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f150f77",
   "metadata": {},
   "source": [
    "Die crossover Funktionalität kann wie folgt implementiert werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3cd9e713",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cross_over(chromosome1, chromosome2):\n",
    "    \n",
    "    crossover_point = random.randint(1, len(chromosome1))\n",
    "    child1 = []\n",
    "    child2 = []\n",
    "    for i in range(0, crossover_point):\n",
    "        child1.append(chromosome1[i])\n",
    "        child2.append(chromosome2[i])\n",
    "\n",
    "    for i in range(crossover_point, len(chromosome1)):\n",
    "        child1.append(chromosome2[i])\n",
    "        child2.append(chromosome1[i])\n",
    "    return (child1, child2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d914132",
   "metadata": {},
   "source": [
    "Nun haben wir alle Bausteile zusammen, um die finale Simulation zu implementieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e066414e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulate(num_initial_genes, num_generations):\n",
    "    \n",
    "    mutation_probability = 0.01\n",
    "    crossover_probability = 0.1\n",
    "\n",
    "    population = random_population(num_initial_genes)\n",
    "    parents = select_surviving(population) \n",
    "    \n",
    "    for i in range(0, num_generations):        \n",
    "        for j in range(0, len(parents) // 2):\n",
    "            if random.randint(0, 100) < crossover_probability * 100:\n",
    "                (child1, child2) = cross_over(parents[2 * j], parents[2 * j + 1])\n",
    "            else:\n",
    "                (child1, child2) = (parents[2 * j], parents[2 * j + 1])\n",
    "                \n",
    "            if random.randint(0, 100) < mutation_probability * 100:\n",
    "                child1 = mutate(child1)\n",
    "            if random.randint(0, 100) < mutation_probability * 100:\n",
    "                child2 = mutate(child2)\n",
    "            \n",
    "            population[2 * j] = child1\n",
    "            population[2 * j + 1] = child2\n",
    "             \n",
    "        parents = select_surviving(population)   \n",
    "\n",
    "\n",
    "        i = i + 1\n",
    "    return parents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f63a55c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hier folgt eine Ausgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65a269f4",
   "metadata": {},
   "source": [
    "### Aufgabe \n",
    "\n",
    "* Experimentieren Sie mit dieser Simulation. Wie gut ist die Lösung? Bekommen Sie jedes Mal die optimale Lösung?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8418020",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}