AntSimulator.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import copy\n",
    "import random\n",
    "\n",
    "import numpy\n",
    "\n",
    "from functools import partial\n",
    "\n",
    "from deap import algorithms\n",
    "from deap import base\n",
    "from deap import creator\n",
    "from deap import tools\n",
    "from deap import gp\n",
    "\n",
    "def progn(*args):\n",
    "    for arg in args:\n",
    "        arg()\n",
    "\n",
    "def prog2(out1, out2): \n",
    "    return partial(progn,out1,out2)\n",
    "\n",
    "def prog3(out1, out2, out3):     \n",
    "    return partial(progn,out1,out2,out3)\n",
    "\n",
    "def if_then_else(condition, out1, out2):\n",
    "    out1() if condition() else out2()\n",
    "\n",
    "class AntSimulator(object):\n",
    "    direction = [\"north\",\"east\",\"south\",\"west\"]\n",
    "    dir_row = [1, 0, -1, 0]\n",
    "    dir_col = [0, 1, 0, -1]\n",
    "    \n",
    "    def __init__(self, max_moves):\n",
    "        self.max_moves = max_moves\n",
    "        self.moves = 0\n",
    "        self.eaten = 0\n",
    "        self.routine = None\n",
    "        \n",
    "    def _reset(self):\n",
    "        self.row = self.row_start \n",
    "        self.col = self.col_start \n",
    "        self.dir = 1\n",
    "        self.moves = 0  \n",
    "        self.eaten = 0\n",
    "        self.matrix_exc = copy.deepcopy(self.matrix)\n",
    "\n",
    "    @property\n",
    "    def position(self):\n",
    "        return (self.row, self.col, self.direction[self.dir])\n",
    "            \n",
    "    def turn_left(self): \n",
    "        if self.moves < self.max_moves:\n",
    "            self.moves += 1\n",
    "            self.dir = (self.dir - 1) % 4\n",
    "\n",
    "    def turn_right(self):\n",
    "        if self.moves < self.max_moves:\n",
    "            self.moves += 1    \n",
    "            self.dir = (self.dir + 1) % 4\n",
    "        \n",
    "    def move_forward(self):\n",
    "        if self.moves < self.max_moves:\n",
    "            self.moves += 1\n",
    "            self.row = (self.row + self.dir_row[self.dir]) % self.matrix_row\n",
    "            self.col = (self.col + self.dir_col[self.dir]) % self.matrix_col\n",
    "            if self.matrix_exc[self.row][self.col] == \"food\":\n",
    "                self.eaten += 1\n",
    "            self.matrix_exc[self.row][self.col] = \"passed\"\n",
    "\n",
    "    def sense_food(self):\n",
    "        ahead_row = (self.row + self.dir_row[self.dir]) % self.matrix_row\n",
    "        ahead_col = (self.col + self.dir_col[self.dir]) % self.matrix_col        \n",
    "        return self.matrix_exc[ahead_row][ahead_col] == \"food\"\n",
    "   \n",
    "    def if_food_ahead(self, out1, out2):\n",
    "        return partial(if_then_else, self.sense_food, out1, out2)\n",
    "   \n",
    "    def run(self,routine):\n",
    "        self._reset()\n",
    "        while self.moves < self.max_moves:\n",
    "            routine()\n",
    "    \n",
    "    def parse_matrix(self, matrix):\n",
    "        self.matrix = list()\n",
    "        for i, line in enumerate(matrix):\n",
    "            self.matrix.append(list())\n",
    "            for j, col in enumerate(line):\n",
    "                if col == \"#\":\n",
    "                    self.matrix[-1].append(\"food\")\n",
    "                elif col == \".\":\n",
    "                    self.matrix[-1].append(\"empty\")\n",
    "                elif col == \"S\":\n",
    "                    self.matrix[-1].append(\"empty\")\n",
    "                    self.row_start = self.row = i\n",
    "                    self.col_start = self.col = j\n",
    "                    self.dir = 1\n",
    "        self.matrix_row = len(self.matrix)\n",
    "        self.matrix_col = len(self.matrix[0])\n",
    "        self.matrix_exc = copy.deepcopy(self.matrix)\n",
    "\n",
    "ant = AntSimulator(600)\n",
    "\n",
    "pset = gp.PrimitiveSet(\"MAIN\", 0)\n",
    "pset.addPrimitive(ant.if_food_ahead, 2)\n",
    "pset.addPrimitive(prog2, 2)\n",
    "pset.addPrimitive(prog3, 3)\n",
    "pset.addTerminal(ant.move_forward)\n",
    "pset.addTerminal(ant.turn_left)\n",
    "pset.addTerminal(ant.turn_right)\n",
    "\n",
    "creator.create(\"FitnessMax\", base.Fitness, weights=(1.0,))\n",
    "creator.create(\"Individual\", gp.PrimitiveTree, fitness=creator.FitnessMax)\n",
    "\n",
    "toolbox = base.Toolbox()\n",
    "\n",
    "# Attribute generator\n",
    "toolbox.register(\"expr_init\", gp.genFull, pset=pset, min_=1, max_=2)\n",
    "\n",
    "# Structure initializers\n",
    "toolbox.register(\"individual\", tools.initIterate, creator.Individual, toolbox.expr_init)\n",
    "toolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)\n",
    "\n",
    "def evalArtificialAnt(individual):\n",
    "    # Transform the tree expression to functionnal Python code\n",
    "    routine = gp.compile(individual, pset)\n",
    "    # Run the generated routine\n",
    "    ant.run(routine)\n",
    "    return ant.eaten,\n",
    "\n",
    "toolbox.register(\"evaluate\", evalArtificialAnt)\n",
    "toolbox.register(\"select\", tools.selTournament, tournsize=7)\n",
    "toolbox.register(\"mate\", gp.cxOnePoint)\n",
    "toolbox.register(\"expr_mut\", gp.genFull, min_=0, max_=2)\n",
    "toolbox.register(\"mutate\", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)\n",
    "\n",
    "def main():\n",
    "    # random.seed(69)\n",
    "    \n",
    "    # there are 89 bits of food...\n",
    "    with  open(\"ant_santafe_trail.txt\") as trail_file:\n",
    "      ant.parse_matrix(trail_file)\n",
    "    \n",
    "    pop = toolbox.population(n=800)\n",
    "    hof = tools.HallOfFame(1)\n",
    "    stats = tools.Statistics(lambda ind: ind.fitness.values)\n",
    "    stats.register(\"avg\", numpy.mean)\n",
    "    stats.register(\"std\", numpy.std)\n",
    "    stats.register(\"min\", numpy.min)\n",
    "    stats.register(\"max\", numpy.max)\n",
    "    \n",
    "    algorithms.eaSimple(pop, toolbox, 0.5, 0.2, 50, stats, halloffame=hof)\n",
    "    \n",
    "    return pop, hof, stats\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gen\tnevals\tavg\tstd    \tmin\tmax\n",
      "0  \t800   \t1.8\t3.34739\t0  \t28 \n",
      "1  \t507   \t5.1325\t4.86518\t0  \t28 \n",
      "2  \t469   \t8.6225\t6.5892 \t0  \t31 \n",
      "3  \t495   \t11.6163\t9.04193\t0  \t44 \n",
      "4  \t480   \t15.685 \t11.708 \t0  \t44 \n",
      "5  \t457   \t20.1513\t13.3115\t0  \t44 \n",
      "6  \t477   \t23.24  \t15.4595\t0  \t50 \n",
      "7  \t463   \t26.8738\t16.8297\t0  \t50 \n",
      "8  \t459   \t27.6788\t18.5668\t0  \t50 \n",
      "9  \t474   \t29.6962\t18.5059\t0  \t50 \n",
      "10 \t479   \t29.8675\t19.5672\t0  \t50 \n",
      "11 \t465   \t31.5138\t20.2697\t0  \t50 \n",
      "12 \t466   \t32.985 \t21.0249\t0  \t50 \n",
      "13 \t464   \t33.9637\t20.8809\t0  \t50 \n",
      "14 \t483   \t33.8588\t20.6262\t0  \t50 \n",
      "15 \t486   \t33.33  \t21.1036\t0  \t52 \n",
      "16 \t467   \t33.7   \t20.8723\t0  \t52 \n",
      "17 \t482   \t33.46  \t20.9215\t0  \t53 \n",
      "18 \t479   \t35.465 \t20.743 \t0  \t53 \n",
      "19 \t513   \t37.4625\t20.6521\t0  \t65 \n",
      "20 \t471   \t39.7388\t20.3535\t0  \t65 \n",
      "21 \t515   \t40.835 \t21.0385\t0  \t65 \n",
      "22 \t492   \t42.8563\t22.7152\t0  \t65 \n",
      "23 \t481   \t48.5138\t22.5853\t0  \t67 \n",
      "24 \t502   \t50.2188\t23.1774\t0  \t67 \n",
      "25 \t455   \t53.18  \t21.0495\t0  \t67 \n",
      "26 \t474   \t52.2587\t22.1085\t0  \t67 \n",
      "27 \t466   \t51.405 \t22.5031\t0  \t67 \n",
      "28 \t480   \t52.315 \t22.1793\t0  \t67 \n",
      "29 \t473   \t50.0463\t23.3896\t0  \t67 \n",
      "30 \t456   \t50.6887\t23.3058\t0  \t67 \n",
      "31 \t484   \t50.4862\t22.7564\t0  \t67 \n",
      "32 \t503   \t49.79  \t22.9382\t0  \t67 \n",
      "33 \t475   \t49.83  \t23.779 \t0  \t67 \n",
      "34 \t446   \t52.4925\t21.9766\t0  \t67 \n",
      "35 \t484   \t51.7812\t22.3019\t0  \t67 \n",
      "36 \t482   \t51.8025\t22.854 \t0  \t67 \n",
      "37 \t491   \t51.8575\t21.9879\t0  \t67 \n",
      "38 \t456   \t53.2587\t22.1592\t0  \t67 \n",
      "39 \t501   \t52.2512\t22.6464\t0  \t67 \n",
      "40 \t455   \t53.545 \t21.8614\t0  \t67 \n",
      "41 \t464   \t54.6662\t21.3673\t0  \t67 \n",
      "42 \t436   \t55.685 \t20.965 \t0  \t67 \n",
      "43 \t472   \t54.7625\t21.2126\t0  \t67 \n",
      "44 \t490   \t55.2437\t20.5138\t0  \t67 \n",
      "45 \t488   \t56.0187\t20.1217\t0  \t67 \n",
      "46 \t509   \t56.38  \t20.1978\t0  \t67 \n",
      "47 \t481   \t57.175 \t19.9816\t0  \t67 \n",
      "48 \t464   \t57.1025\t19.8637\t0  \t67 \n",
      "49 \t454   \t57.5838\t19.9092\t0  \t67 \n",
      "50 \t469   \t58.5513\t18.599 \t0  \t67 \n"
     ]
    }
   ],
   "source": [
    "pop, hof, stats = main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  prog3\n",
      "    prog3\n",
      "      move_forward\n",
      "      if_food_ahead\n",
      "        prog2\n",
      "          move_forward\n",
      "          move_forward\n",
      "        turn_right\n",
      "      move_forward\n",
      "    prog2\n",
      "      move_forward\n",
      "      move_forward\n",
      "    if_food_ahead\n",
      "      prog2\n",
      "        if_food_ahead\n",
      "          if_food_ahead\n",
      "            move_forward\n",
      "            turn_right\n",
      "          move_forward\n",
      "        prog3\n",
      "          move_forward\n",
      "          turn_left\n",
      "          turn_right\n",
      "      turn_left\n"
     ]
    }
   ],
   "source": [
    "stack = [1]\n",
    "for node in hof[0]:\n",
    "    print(\"  \" * len(stack) + str(node.name))# + str(stack))\n",
    "    if isinstance(node, gp.Primitive):\n",
    "        stack.append(node.arity)\n",
    "    while stack[-1] == 0:\n",
    "        del stack[-1]\n",
    "    stack[-1] -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.4.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}