{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# DEAP" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. It seeks to make algorithms explicit and data structures transparent. It works in perfect harmony with parallelisation mechanism such as multiprocessing and SCOOP. The following documentation presents the key concepts and many features to build your own evolutions.\n", "\n", "Library documentation: http://deap.readthedocs.org/en/master/" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## One Max Problem (GA)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This problem is very simple, we search for a 1 filled list individual. This problem is widely used in the evolutionary computation community since it is very simple and it illustrates well the potential of evolutionary algorithms." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import random\n", "\n", "from deap import base\n", "from deap import creator\n", "from deap import tools" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# creator is a class factory that can build new classes at run-time\n", "creator.create(\"FitnessMax\", base.Fitness, weights=(1.0,))\n", "creator.create(\"Individual\", list, fitness=creator.FitnessMax)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# a toolbox stores functions and their arguments\n", "toolbox = base.Toolbox()\n", "\n", "# attribute generator\n", "toolbox.register(\"attr_bool\", random.randint, 0, 1)\n", "\n", "# structure initializers\n", "toolbox.register(\"individual\", tools.initRepeat, creator.Individual, toolbox.attr_bool, 100)\n", "toolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# evaluation function\n", "def evalOneMax(individual):\n", " return sum(individual)," ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# register the required genetic operators\n", "toolbox.register(\"evaluate\", evalOneMax)\n", "toolbox.register(\"mate\", tools.cxTwoPoint)\n", "toolbox.register(\"mutate\", tools.mutFlipBit, indpb=0.05)\n", "toolbox.register(\"select\", tools.selTournament, tournsize=3)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " Evaluated 300 individuals\n" ] } ], "source": [ "random.seed(64)\n", "\n", "# instantiate a population\n", "pop = toolbox.population(n=300)\n", "CXPB, MUTPB, NGEN = 0.5, 0.2, 40\n", "\n", "# evaluate the entire population\n", "fitnesses = list(map(toolbox.evaluate, pop))\n", "for ind, fit in zip(pop, fitnesses):\n", " ind.fitness.values = fit\n", "\n", "print(\" Evaluated %i individuals\" % len(pop))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-- Generation 0 --\n", " Evaluated 189 individuals\n", " Min 40.0\n", " Max 65.0\n", " Avg 54.7433333333\n", " Std 4.46289766358\n", "-- Generation 1 --\n", " Evaluated 171 individuals\n", " Min 44.0\n", " Max 70.0\n", " Avg 58.48\n", " Std 3.98533980149\n", "-- Generation 2 --\n", " Evaluated 169 individuals\n", " Min 54.0\n", " Max 68.0\n", " Avg 61.6066666667\n", " Std 2.92779021714\n", "-- Generation 3 --\n", " Evaluated 185 individuals\n", " Min 57.0\n", " Max 73.0\n", " Avg 63.82\n", " Std 2.74364720764\n", "-- Generation 4 --\n", " Evaluated 175 individuals\n", " Min 54.0\n", " Max 73.0\n", " Avg 65.67\n", " Std 2.57961883489\n", "-- Generation 5 --\n", " Evaluated 164 individuals\n", " Min 60.0\n", " Max 76.0\n", " Avg 67.5466666667\n", " Std 2.57833710407\n", "-- Generation 6 --\n", " Evaluated 185 individuals\n", " Min 63.0\n", " Max 77.0\n", " Avg 69.0666666667\n", " Std 2.50510589707\n", "-- Generation 7 --\n", " Evaluated 194 individuals\n", " Min 62.0\n", " Max 78.0\n", " Avg 70.78\n", " Std 2.39963886172\n", "-- Generation 8 --\n", " Evaluated 199 individuals\n", " Min 63.0\n", " Max 79.0\n", " Avg 72.3133333333\n", " Std 2.57717330077\n", "-- Generation 9 --\n", " Evaluated 169 individuals\n", " Min 67.0\n", " Max 81.0\n", " Avg 74.0\n", " Std 2.62551582234\n", "-- Generation 10 --\n", " Evaluated 180 individuals\n", " Min 67.0\n", " Max 83.0\n", " Avg 75.9166666667\n", " Std 2.52910831893\n", "-- Generation 11 --\n", " Evaluated 193 individuals\n", " Min 67.0\n", " Max 84.0\n", " Avg 77.5966666667\n", " Std 2.40291258453\n", "-- Generation 12 --\n", " Evaluated 177 individuals\n", " Min 72.0\n", " Max 85.0\n", " Avg 78.97\n", " Std 2.29690371297\n", "-- Generation 13 --\n", " Evaluated 195 individuals\n", " Min 70.0\n", " Max 86.0\n", " Avg 80.13\n", " Std 2.35650164439\n", "-- Generation 14 --\n", " Evaluated 175 individuals\n", " Min 74.0\n", " Max 86.0\n", " Avg 81.3966666667\n", " Std 2.03780655499\n", "-- Generation 15 --\n", " Evaluated 181 individuals\n", " Min 74.0\n", " Max 87.0\n", " Avg 82.33\n", " Std 2.18504767301\n", "-- Generation 16 --\n", " Evaluated 198 individuals\n", " Min 74.0\n", " Max 88.0\n", " Avg 83.4033333333\n", " Std 2.22575580172\n", "-- Generation 17 --\n", " Evaluated 190 individuals\n", " Min 72.0\n", " Max 88.0\n", " Avg 84.14\n", " Std 2.34955314901\n", "-- Generation 18 --\n", " Evaluated 170 individuals\n", " Min 76.0\n", " Max 89.0\n", " Avg 85.1\n", " Std 2.20529665427\n", "-- Generation 19 --\n", " Evaluated 189 individuals\n", " Min 75.0\n", " Max 90.0\n", " Avg 85.77\n", " Std 2.1564863397\n", "-- Generation 20 --\n", " Evaluated 188 individuals\n", " Min 77.0\n", " Max 91.0\n", " Avg 86.4833333333\n", " Std 2.2589943682\n", "-- Generation 21 --\n", " Evaluated 180 individuals\n", " Min 80.0\n", " Max 91.0\n", " Avg 87.24\n", " Std 2.0613264338\n", "-- Generation 22 --\n", " Evaluated 179 individuals\n", " Min 80.0\n", " Max 92.0\n", " Avg 87.95\n", " Std 1.95298916194\n", "-- Generation 23 --\n", " Evaluated 196 individuals\n", " Min 79.0\n", " Max 93.0\n", " Avg 88.42\n", " Std 2.2249194742\n", "-- Generation 24 --\n", " Evaluated 168 individuals\n", " Min 82.0\n", " Max 93.0\n", " Avg 89.2833333333\n", " Std 1.89289607627\n", "-- Generation 25 --\n", " Evaluated 186 individuals\n", " Min 78.0\n", " Max 94.0\n", " Avg 89.7666666667\n", " Std 2.26102238428\n", "-- Generation 26 --\n", " Evaluated 182 individuals\n", " Min 82.0\n", " Max 94.0\n", " Avg 90.4633333333\n", " Std 2.21404356075\n", "-- Generation 27 --\n", " Evaluated 179 individuals\n", " Min 81.0\n", " Max 95.0\n", " Avg 90.8733333333\n", " Std 2.41328729238\n", "-- Generation 28 --\n", " Evaluated 183 individuals\n", " Min 83.0\n", " Max 95.0\n", " Avg 91.7166666667\n", " Std 2.18701978856\n", "-- Generation 29 --\n", " Evaluated 167 individuals\n", " Min 83.0\n", " Max 98.0\n", " Avg 92.3466666667\n", " Std 2.21656390739\n", "-- Generation 30 --\n", " Evaluated 170 individuals\n", " Min 84.0\n", " Max 98.0\n", " Avg 92.9533333333\n", " Std 2.09868742048\n", "-- Generation 31 --\n", " Evaluated 172 individuals\n", " Min 83.0\n", " Max 97.0\n", " Avg 93.5266666667\n", " Std 2.28238666507\n", "-- Generation 32 --\n", " Evaluated 196 individuals\n", " Min 86.0\n", " Max 98.0\n", " Avg 94.28\n", " Std 2.16985406575\n", "-- Generation 33 --\n", " Evaluated 176 individuals\n", " Min 85.0\n", " Max 98.0\n", " Avg 94.9133333333\n", " Std 2.22392046221\n", "-- Generation 34 --\n", " Evaluated 176 individuals\n", " Min 86.0\n", " Max 99.0\n", " Avg 95.6333333333\n", " Std 2.13359373411\n", "-- Generation 35 --\n", " Evaluated 174 individuals\n", " Min 86.0\n", " Max 99.0\n", " Avg 96.2966666667\n", " Std 2.23651266236\n", "-- Generation 36 --\n", " Evaluated 174 individuals\n", " Min 87.0\n", " Max 100.0\n", " Avg 96.5866666667\n", " Std 2.41436442062\n", "-- Generation 37 --\n", " Evaluated 195 individuals\n", " Min 84.0\n", " Max 100.0\n", " Avg 97.3666666667\n", " Std 2.16153237825\n", "-- Generation 38 --\n", " Evaluated 180 individuals\n", " Min 89.0\n", " Max 100.0\n", " Avg 97.7466666667\n", " Std 2.32719191779\n", "-- Generation 39 --\n", " Evaluated 196 individuals\n", " Min 88.0\n", " Max 100.0\n", " Avg 98.1833333333\n", " Std 2.33589145486\n" ] } ], "source": [ "# begin the evolution\n", "for g in range(NGEN):\n", " print(\"-- Generation %i --\" % g)\n", "\n", " # select the next generation individuals\n", " offspring = toolbox.select(pop, len(pop))\n", "\n", " # clone the selected individuals\n", " offspring = list(map(toolbox.clone, offspring))\n", "\n", " # apply crossover and mutation on the offspring\n", " for child1, child2 in zip(offspring[::2], offspring[1::2]):\n", " if random.random() < CXPB:\n", " toolbox.mate(child1, child2)\n", " del child1.fitness.values\n", " del child2.fitness.values\n", "\n", " for mutant in offspring:\n", " if random.random() < MUTPB:\n", " toolbox.mutate(mutant)\n", " del mutant.fitness.values\n", "\n", " # evaluate the individuals with an invalid fitness\n", " invalid_ind = [ind for ind in offspring if not ind.fitness.valid]\n", " fitnesses = map(toolbox.evaluate, invalid_ind)\n", " for ind, fit in zip(invalid_ind, fitnesses):\n", " ind.fitness.values = fit\n", "\n", " print(\" Evaluated %i individuals\" % len(invalid_ind))\n", "\n", " # the population is entirely replaced by the offspring\n", " pop[:] = offspring\n", "\n", " # gather all the fitnesses in one list and print the stats\n", " fits = [ind.fitness.values[0] for ind in pop]\n", "\n", " length = len(pop)\n", " mean = sum(fits) / length\n", " sum2 = sum(x*x for x in fits)\n", " std = abs(sum2 / length - mean**2)**0.5\n", "\n", " print(\" Min %s\" % min(fits))\n", " print(\" Max %s\" % max(fits))\n", " print(\" Avg %s\" % mean)\n", " print(\" Std %s\" % std)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Best individual is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], (100.0,)\n" ] } ], "source": [ "best_ind = tools.selBest(pop, 1)[0]\n", "print(\"Best individual is %s, %s\" % (best_ind, best_ind.fitness.values))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Symbolic Regression (GP)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Symbolic regression is one of the best known problems in GP. It is commonly used as a tuning problem for new algorithms, but is also widely used with real-life distributions, where other regression methods may not work.\n", "\n", "All symbolic regression problems use an arbitrary data distribution, and try to fit the most accurately the data with a symbolic formula. Usually, a measure like the RMSE (Root Mean Square Error) is used to measure an individual’s fitness.\n", "\n", "In this example, we use a classical distribution, the quartic polynomial (x^4 + x^3 + x^2 + x), a one-dimension distribution. 20 equidistant points are generated in the range [-1, 1], and are used to evaluate the fitness." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import operator\n", "import math\n", "import random\n", "\n", "import numpy\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", "# define a new function for divison that guards against divide by 0\n", "def protectedDiv(left, right):\n", " try:\n", " return left / right\n", " except ZeroDivisionError:\n", " return 1" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# add aritmetic primitives\n", "pset = gp.PrimitiveSet(\"MAIN\", 1)\n", "pset.addPrimitive(operator.add, 2)\n", "pset.addPrimitive(operator.sub, 2)\n", "pset.addPrimitive(operator.mul, 2)\n", "pset.addPrimitive(protectedDiv, 2)\n", "pset.addPrimitive(operator.neg, 1)\n", "pset.addPrimitive(math.cos, 1)\n", "pset.addPrimitive(math.sin, 1)\n", "\n", "# constant terminal\n", "pset.addEphemeralConstant(\"rand101\", lambda: random.randint(-1,1))\n", "\n", "# define number of inputs\n", "pset.renameArguments(ARG0='x')" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# create fitness and individual objects\n", "creator.create(\"FitnessMin\", base.Fitness, weights=(-1.0,))\n", "creator.create(\"Individual\", gp.PrimitiveTree, fitness=creator.FitnessMin)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# register evolution process parameters through the toolbox\n", "toolbox = base.Toolbox()\n", "toolbox.register(\"expr\", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)\n", "toolbox.register(\"individual\", tools.initIterate, creator.Individual, toolbox.expr)\n", "toolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)\n", "toolbox.register(\"compile\", gp.compile, pset=pset)\n", "\n", "# evaluation function\n", "def evalSymbReg(individual, points):\n", " # transform the tree expression in a callable function\n", " func = toolbox.compile(expr=individual)\n", " # evaluate the mean squared error between the expression\n", " # and the real function : x**4 + x**3 + x**2 + x\n", " sqerrors = ((func(x) - x**4 - x**3 - x**2 - x)**2 for x in points)\n", " return math.fsum(sqerrors) / len(points),\n", "\n", "toolbox.register(\"evaluate\", evalSymbReg, points=[x/10. for x in range(-10,10)])\n", "toolbox.register(\"select\", tools.selTournament, tournsize=3)\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", "# prevent functions from getting too deep/complex\n", "toolbox.decorate(\"mate\", gp.staticLimit(key=operator.attrgetter(\"height\"), max_value=17))\n", "toolbox.decorate(\"mutate\", gp.staticLimit(key=operator.attrgetter(\"height\"), max_value=17))" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# compute some statistics about the population\n", "stats_fit = tools.Statistics(lambda ind: ind.fitness.values)\n", "stats_size = tools.Statistics(len)\n", "mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size)\n", "mstats.register(\"avg\", numpy.mean)\n", "mstats.register(\"std\", numpy.std)\n", "mstats.register(\"min\", numpy.min)\n", "mstats.register(\"max\", numpy.max)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " \t \t fitness \t size \n", " \t \t---------------------------------------\t-------------------------------\n", "gen\tnevals\tavg \tmax \tmin \tstd \tavg \tmax\tmin\tstd \n", "0 \t300 \t2.39949\t59.2593\t0.165572\t4.64122\t3.69667\t7 \t2 \t1.61389\n", "1 \t146 \t1.0971 \t10.1 \t0.165572\t0.845978\t3.80667\t13 \t1 \t1.78586\n", "2 \t169 \t0.902365\t6.5179 \t0.165572\t0.72362 \t4.16 \t13 \t1 \t2.0366 \n", "3 \t167 \t0.852725\t9.6327 \t0.165572\t0.869381\t4.63667\t13 \t1 \t2.20408\n", "4 \t158 \t0.74829 \t14.1573\t0.165572\t1.01281 \t4.88333\t13 \t1 \t2.14392\n", "5 \t160 \t0.630299\t7.90605\t0.165572\t0.904373\t5.52333\t14 \t1 \t2.09351\n", "6 \t181 \t0.495118\t4.09456\t0.165572\t0.524658\t6.08333\t13 \t1 \t1.99409\n", "7 \t170 \t0.403873\t2.6434 \t0.165572\t0.440596\t6.34667\t14 \t1 \t1.84386\n", "8 \t173 \t0.393405\t2.9829 \t0.165572\t0.425415\t6.37 \t12 \t1 \t1.78132\n", "9 \t168 \t0.414299\t13.5996\t0.165572\t0.841226\t6.25333\t11 \t2 \t1.76328\n", "10 \t142 \t0.384179\t4.07808\t0.165572\t0.477269\t6.25667\t13 \t1 \t1.78067\n", "11 \t156 \t0.459639\t19.8316\t0.165572\t1.47254 \t6.35333\t15 \t1 \t2.04983\n", "12 \t167 \t0.384348\t6.79674\t0.165572\t0.495807\t6.25 \t13 \t1 \t1.92029\n", "13 \t157 \t0.42446 \t11.0636\t0.165572\t0.818953\t6.43667\t15 \t1 \t2.11959\n", "14 \t175 \t0.342257\t2.552 \t0.165572\t0.325872\t6.23333\t15 \t1 \t2.14295\n", "15 \t154 \t0.442374\t13.8349\t0.165572\t0.950612\t6.05667\t14 \t1 \t1.90266\n", "16 \t181 \t0.455697\t19.7228\t0.101561\t1.39528 \t6.08667\t13 \t1 \t1.84006\n", "17 \t178 \t0.36256 \t2.54124\t0.101561\t0.340555\t6.24 \t15 \t1 \t2.20055\n", "18 \t171 \t0.411532\t14.2339\t0.101561\t0.897785\t6.44 \t15 \t1 \t2.2715 \n", "19 \t156 \t0.43193 \t15.5923\t0.101561\t0.9949 \t6.66667\t15 \t1 \t2.40185\n", "20 \t169 \t0.398163\t4.09456\t0.0976781\t0.450231\t6.96667\t15 \t1 \t2.62022\n", "21 \t162 \t0.385774\t4.09456\t0.0976781\t0.421867\t7.13 \t14 \t1 \t2.65577\n", "22 \t162 \t0.35318 \t2.55465\t0.0253803\t0.389453\t7.66667\t19 \t2 \t3.04995\n", "23 \t164 \t0.3471 \t3.66792\t0.0253803\t0.482334\t8.24 \t21 \t1 \t3.48364\n", "24 \t159 \t1.46248 \t331.247\t0.0253803\t19.0841 \t9.42667\t19 \t3 \t3.238 \n", "25 \t164 \t0.382697\t6.6452 \t0.0173316\t0.652247\t10.1867\t25 \t1 \t3.46292\n", "26 \t139 \t0.367651\t11.9045\t0.0173316\t0.855067\t10.67 \t19 \t3 \t3.32582\n", "27 \t167 \t0.345866\t6.6452 \t0.0173316\t0.586155\t11.4 \t27 \t3 \t3.44384\n", "28 \t183 \t0.388404\t4.53076\t0.0173316\t0.58986 \t11.5767\t24 \t3 \t3.4483 \n", "29 \t163 \t0.356009\t6.33264\t0.0173316\t0.563266\t12.2433\t29 \t2 \t4.23211\n", "30 \t174 \t0.31506 \t2.54124\t0.0173316\t0.412507\t12.92 \t27 \t3 \t4.5041 \n", "31 \t206 \t0.361197\t2.9829 \t0.0173316\t0.486155\t13.9333\t33 \t1 \t5.6747 \n", "32 \t168 \t0.302704\t4.01244\t0.0173316\t0.502277\t15.04 \t31 \t3 \t5.40849\n", "33 \t160 \t0.246509\t3.30873\t0.012947 \t0.433212\t16.3967\t34 \t2 \t5.66092\n", "34 \t158 \t0.344791\t26.1966\t0.012947 \t1.57277 \t17.39 \t43 \t1 \t6.13008\n", "35 \t162 \t0.212572\t2.85856\t0.0148373\t0.363023\t17.64 \t37 \t2 \t6.04349\n", "36 \t183 \t0.240268\t5.06093\t0.0112887\t0.482794\t17.4333\t41 \t3 \t6.33184\n", "37 \t185 \t0.514635\t65.543 \t0.0103125\t3.7864 \t16.6167\t41 \t1 \t6.58456\n", "38 \t134 \t0.340433\t11.2506\t0.0103125\t0.827213\t16.2733\t34 \t1 \t6.08484\n", "39 \t158 \t0.329797\t15.8145\t4.50668e-33\t1.05693 \t16.4133\t34 \t1 \t6.09993\n", "40 \t164 \t0.306543\t14.3573\t4.50668e-33\t0.947046\t17.9033\t53 \t2 \t8.23695\n" ] } ], "source": [ "random.seed(318)\n", "\n", "pop = toolbox.population(n=300)\n", "hof = tools.HallOfFame(1)\n", "\n", "# run the algorithm\n", "pop, log = algorithms.eaSimple(pop, toolbox, 0.5, 0.1, 40, stats=mstats,\n", " halloffame=hof, verbose=True)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.9" } }, "nbformat": 4, "nbformat_minor": 0 }