{"id":741,"date":"2021-09-19T03:11:09","date_gmt":"2021-09-19T03:11:09","guid":{"rendered":"https:\/\/es-andreabianchini.it\/andrewsblog\/?p=741"},"modified":"2021-09-20T04:40:45","modified_gmt":"2021-09-20T04:40:45","slug":"algoritmi-genetici","status":"publish","type":"post","link":"https:\/\/es-andreabianchini.it\/andrewsblog\/?p=741","title":{"rendered":"Algoritmi genetici"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code># DEAP_generico.py\n#\n# esempio di utilizzo della libreria per la computazione genetica evolutiva\n# dei problemi denominata DEAP.\n# in questo caso ho utilizzato lo scheletro della risoluzione di un\n# problema generico per risolvere il problema di ottimizzazione\n# noto come Knapsack Problem.\n# documentazione su : https:\/\/deap.readthedocs.io\/en\/master\/index.html\n#\n# by Andrea Bianchini (2021)\n\n\n\nimport random\n\nfrom deap import base\nfrom deap import creator\nfrom deap import tools\n\nIND_SIZE = 50\nC = 10000\nMIN_WEIGHT = int(C*0.01)\nMAX_WEIGHT = int(C*0.07)\nMAX=0\nsol=&#91;]\nitems=&#91;random.randint(MIN_WEIGHT,MAX_WEIGHT) for _ in range(IND_SIZE)]\n\ncreator.create(\"FitnessMax\", base.Fitness, weights=(1.0,))\ncreator.create(\"Individual\", list, fitness=creator.FitnessMax)\n\ntoolbox = base.Toolbox()\n# Attribute generator \ntoolbox.register(\"attr_bool\", random.randint, 0, 1)\n# Structure initializers\ntoolbox.register(\"individual\", tools.initRepeat, creator.Individual, \n    toolbox.attr_bool, IND_SIZE)\ntoolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)\n\ndef evalOneMax(individual):\n    global sol\n    global MAX\n    e1 = sum(&#91;items&#91;i]*individual&#91;i] for i in range(len(individual))])\n    if e1>MAX and e1&lt;=C:\n        MAX = e1\n        sol=individual\n    return e1,\n\ntoolbox.register(\"evaluate\", evalOneMax)\ntoolbox.register(\"mate\", tools.cxTwoPoint)\ntoolbox.register(\"mutate\", tools.mutFlipBit, indpb=0.05)\ntoolbox.register(\"select\", tools.selTournament, tournsize=3)\n\nsumma=0\ndef main():\n    global summa\n    pop = toolbox.population(n=300)\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    # CXPB  is the probability with which two individuals\n    #       are crossed\n    #\n    # MUTPB is the probability for mutating an individual\n    CXPB, MUTPB = 0.5, 0.2\n\n    # Extracting all the fitnesses of \n    fits = &#91;ind.fitness.values&#91;0] for ind in pop]\n\n    # Variable keeping track of the number of generations\n    g = 0\n    \n    # Begin the evolution\n    \n    while max(fits) &lt; C and g &lt; 1000:\n        # A new generation\n        g = g + 1\n        print(\"-- Generation %i --\" % g)\n\n        # Select the next generation individuals\n        offspring = toolbox.select(pop, len(pop))\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&#91;::2], offspring&#91;1::2]):\n            if random.random() &lt; 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() &lt; MUTPB:\n                toolbox.mutate(mutant)\n                del mutant.fitness.values\n\n        # Evaluate the individuals with an invalid fitness\n        invalid_ind = &#91;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        pop&#91;:] = offspring\n\n        # Gather all the fitnesses in one list and print the stats\n        fits = &#91;ind.fitness.values&#91;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)\n\n        if max(fits) &lt;=C and summa&lt;max(fits):\n            summa = max(fits)\n\nmain()\nprint()\nprint(\"Soluzione ottima = %d\" %MAX)\nprint(\"Lista items completa :\")\nprint(items)\nprint(\"Lista items soluzione :\")\nosol = &#91;items&#91;i]*sol&#91;i] for i in range(IND_SIZE)]\nprint(osol)<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Esempio:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Soluzione ottima = 10000\nLista items completa :\n&#91;481, 167, 361, 111, 670, 602, 119, 331, 654, 155, 400, 227, 651, 531, 413, 134, 409, 140, 488, 457, 495, 628, 153, 632, 327, 159, 593, 633, 682, 392, 368, 526, 599, 478, 408, 315, 466, 582, 302, 172, 427, 173, 551, 673, 272, 158, 502, 269, 685, 588]\nLista items soluzione :\n&#91;0, 0, 361, 0, 670, 0, 0, 331, 654, 0, 0, 0, 651, 0, 0, 0, 409, 140, 488, 0, 0, 628, 0, 632, 327, 0, 593, 0, 682, 0, 368, 0, 0, 478, 0, 315, 0, 582, 0, 172, 427, 0, 551, 0, 272, 0, 0, 269, 0, 0]\n>>> <\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esempio:<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,12,11,7],"tags":[],"class_list":["post-741","post","type-post","status-publish","format-standard","hentry","category-intelligenza-artificiale","category-python","category-or","category-stem"],"_links":{"self":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/741","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=741"}],"version-history":[{"count":3,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/741\/revisions"}],"predecessor-version":[{"id":746,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/741\/revisions\/746"}],"wp:attachment":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=741"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=741"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=741"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}