In questo articolo vi presento un possibile algoritmo genetico da me implementato in C++ per questioni di velocit\u00e0 di calcolo (e non solo…).<\/p>\n\n\n\n
L’algoritmo \u00e8 molto semplice e compatto, ma vi assicuro che funziona benissimo! Come esempio di problema da risolvere ho adottato il subset sum problem.<\/p>\n\n\n\n
\/\/==========================================================================\n\/\/ Name : aga.cpp\n\/\/ Author : Andrea Bianchini (2021)\n\/\/ Version : 1.0.0\n\/\/ Copyright : SOME RIGHT RESERVED CREATIVE COMMONS BY 4.0\n\/\/ License : https:\/\/creativecommons.org\/licenses\/by\/4.0\/\n\/\/ Description : AGA - Andrew's Genetic Algorithm\n\/\/ Use : AGA p = AGA(PSIZE,ISIZE,RMIN,RMAX,IMAX,PCROSS,PMUT);\n\/\/ : p.evolve();\n\/\/ Where : PSIZE = Population size (number of individuals)\n\/\/ : ISIZE = Individual size (number of variables)\n\/\/ : RMIN = Individual variables min value\n\/\/ : RMAX = Individual variables max value\n\/\/ : IMAX = Max number of iteration\n\/\/ : PCROSS= Crossover probability\n\/\/ : PMUT = Mutation probability\n\/\/ Example : AGA p = AGA(500,20,0,1,10,0.5,0.3);\n\/\/ : p.evolve();\n\/\/ :\n\/\/ : Personalize your objective into evalIndividual().\n\/\/ : This file is personalized to solve subset sum problem.\n\/\/==========================================================================\n#include <stdlib.h>\n#include <limits.h>\n#include <stdio.h>\n#include <math.h>\n#include <time.h>\n\n\nclass AGA\n{\nprotected:\n\tint POP_SIZE = 500;\n\tint IND_SIZE = 20;\n\tint RANGE_MIN = 0;\n\tint RANGE_MAX = 1;\n\tint MAXITER = 10;\n\tfloat PCROSS = 0.5;\n\tfloat PMUT = 0.3;\n\tint **pop;\n\tint first=1;\n\tint solfound;\n\tint niter;\n\npublic:\n\tint *w;\n\tint *bestIndividual;\n\tint c = 400;\n\n\tvoid initSSP()\n\t{\n\t\tw=new int [IND_SIZE];\n\t\tfor(int i=0;i<IND_SIZE;i++)\n\t\tw[i]=c*0.1+(int)(rand()%(int)(c*0.3-c*0.1+1));\n\n\t}\n\tAGA(int pops, int inds, int rmin, int rmax, int maxiter, float pcross, float pmute)\n\t\t{\n\t\t\tsolfound=0;\n\t\t\tniter=0;\n\t\t\tfirst=1;\n\t\t\tPOP_SIZE=pops;\n\t\t\tIND_SIZE=inds;\n\t\t\tRANGE_MIN=rmin;\n\t\t\tRANGE_MAX=rmax;\n\t\t\tMAXITER = maxiter;\n\t\t\tPCROSS = pcross;\n\t\t\tPMUT = pmute;\n\t\t\tpop = new int* [POP_SIZE];\n\t\t\tint i;\n\t\t\tfor(i=0;i<POP_SIZE;i++)\n\t\t\t{\n\t\t\t\tpop[i] = new int [IND_SIZE+1]; \/\/ +1 for fit\n\t\t\t\tpop[i][IND_SIZE]=0;\n\t\t\t}\n\t\t\tbestIndividual=new int [IND_SIZE+1];\n\t\t\tbestIndividual[IND_SIZE]=0;\n\t\t\tinitSSP();\n\t\t}\n\n\t~AGA()\n\t{\n\t\tfor(int i=0;i<POP_SIZE;i++)\n\t\t\tdelete[] pop[i];\n\t\tdelete[] pop;\n\t\tdelete[] bestIndividual;\n\t\tdelete[] w;\n\t}\n\n\tint * individual(int i)\n\t{\n\t\treturn pop[i];\n\t}\n\n\tvoid populate()\n\t{\n\t\tint ind;\n\t\tfor(ind=0;ind<POP_SIZE-1;ind++)\n\t\t\tfor(int k=ind+1;k<POP_SIZE;k++)\n\t\t\t\tif (abs(individual(ind)[IND_SIZE]-c)>abs(individual(k)[IND_SIZE]-c))\n\t\t\t\t{\n\t\t\t\t\tint *p=individual(ind);\n\t\t\t\t\tpop[ind]=pop[k];\n\t\t\t\t\tpop[k]=p;\n\t\t\t\t}\n\t\t\/\/..........\n\t\tif (first==1)\n\t\t{\n\t\t\tfor(ind=0;ind<POP_SIZE;ind++)\n\t\t\t{\n\t\t\t\tint *in;\n\t\t\t\tin = individual(ind);\n\t\t\t\tfor(int j=0;j<IND_SIZE;j++)\n\t\t\t\t{\n\t\t\t\t\tin[j] = rndInRange();\n\t\t\t\t}\n\t\t\t\tin[IND_SIZE]=0; \/\/ fit\n\t\t\t}\n\t\t\tfirst=0;\n\t\t}\n\t\telse\n\t\t{\n\t\t\tint p2=POP_SIZE*PCROSS+1;\n\t\t\tint p1=0;\n\t\t\twhile(p2<POP_SIZE && p1<POP_SIZE*PCROSS+1)\n\t\t\t{\n\t\t\t\tCross(p1,p2);\n\t\t\t\tif (p2<POP_SIZE*PMUT)\n\t\t\t\t\tMutate(p2);\n\t\t\t\tp1++;\n\t\t\t\tp2++;\n\t\t\t}\n\t\t\twhile (p2<POP_SIZE)\n\t\t\t{\n\t\t\t\tint *in;\n\t\t\t\tin = individual(p2);\n\t\t\t\tfor(int j=0;j<IND_SIZE;j++)\n\t\t\t\t{\n\t\t\t\t\tin[j] = rndInRange();\n\t\t\t\t}\n\t\t\t\tin[IND_SIZE]=0; \/\/ fit\n\t\t\t\tp2++;\n\t\t\t}\n\t\t}\n\t}\n\n\tvoid Cross(int p1, int p2)\n\t{\n\t\tint *c1,*c2,*c3;\n\n\t\tc1=individual(p1);\n\t\tc2=individual(p1+1);\n\t\tc3=individual(p2);\n\n\t\tfor(int i=0;i<IND_SIZE\/2;i++)\n\t\t{\n\t\t\tc3[i]=c1[i];\n\t\t}\n\t\tfor(int i=IND_SIZE\/2;i<IND_SIZE;i++)\n\t\t{\n\t\t\tc3[i]=c2[i];\n\t\t}\n\t\tc3[IND_SIZE]=0;\n\t}\n\n\tvoid Mutate(int p2)\n\t{\n\t\tint c = rand() % IND_SIZE;\n\t\tint *d=individual(p2);\n\t\td[c] = rndInRange();\n\t}\n\n\tint rndInRange()\n\t{\n\t\tint a = RANGE_MIN+(int)(rand()%(RANGE_MAX-RANGE_MIN+1));\n\t\tif (a>RANGE_MAX)\n\t\t\ta=RANGE_MAX;\n\t\t\/\/printf(\"%d\\n\\r\",a);\n\t\treturn a;\n\t}\n\n\tvoid evalPopulation()\n\t{\n\t\tfor(int i=0;i<POP_SIZE;i++)\n\t\t{\n\t\t\tevalIndividual(i);\n\t\t}\n\n\t}\n\n\tvoid evalIndividual(int i)\n\t{\n\t\tint z=0;\n\t\tint *p = individual(i);\n\t\tfor(int j=0;j<IND_SIZE;j++)\n\t\t\tz+=w[j]*p[j];\n\t\t\/\/if (z<c)\n\t\t\tp[IND_SIZE]=z;\n\t\t\/\/else\n\t\t\t\/\/p[IND_SIZE]=0;\n\t\tif (z<=c && z>bestIndividual[IND_SIZE])\n\t\t{\n\t\t\tfor(int j=0;j<IND_SIZE;j++)\n\t\t\t\tbestIndividual[j]=p[j];\n\t\t\tbestIndividual[IND_SIZE]=z;\n\t\t\tprintf(\"Best Fit=%d\\r\",z);\n\t\t\tif (z==c)\n\t\t\t{\n\t\t\t\tsolfound=1;\n\t\t\t\tprintf(\"Optimal Solution z=%d found!\\r\",z);\n\t\t\t}\n\t\t}\n\t\n\t}\n\t\n\tvoid evolve()\n\t{\n\t\tniter=0;\n\t\twhile(niter<MAXITER && solfound==0)\n\t\t{\n\t\t\tprintf(\"--------------------\\rGenerazione n.%d\\r\",niter);\n\t\t\tpopulate();\n\t\t\tevalPopulation();\n\t\t\tint ind;\n\t\t\tint tot=0;\n\t\t\tfor(ind=0;ind<POP_SIZE-1;ind++)\n\t\t\t{\n\t\t\t\ttot+=individual(ind)[IND_SIZE];\n\t\t\t\tfor(int k=ind+1;k<POP_SIZE;k++)\n\t\t\t\t\tif (individual(ind)[IND_SIZE]<individual(k)[IND_SIZE])\n\t\t\t\t\t{\n\t\t\t\t\t\tint *p=individual(ind);\n\t\t\t\t\t\tpop[ind]=pop[k];\n\t\t\t\t\t\tpop[k]=p;\n\t\t\t\t\t}\n\t\t\t}\n\t\t\ttot+=individual(POP_SIZE-1)[IND_SIZE];\n\t\t\ttot\/=POP_SIZE;\n\t\t\tprintf(\"MAX=%d AVG=%d MIN=%d\\r\",pop[0][IND_SIZE],tot,pop[POP_SIZE-1][IND_SIZE]);\n\t\t\tniter++;\n\t\t}\n\t}\n};\n\nint main() {\n\tint POP_SIZE=500;\n\tint IND_SIZE=20;\n\tint RANGE_MIN=0;\n\tint RANGE_MAX=1;\n\tint MAXITER = 10;\n\tfloat PCROSS = 0.5;\n\tfloat PMUT = 0.3;\n\n\tAGA p = AGA(POP_SIZE,IND_SIZE,RANGE_MIN,RANGE_MAX,MAXITER,PCROSS,PMUT);\n\tp.c=600;\n\tp.initSSP();\n\tclock_t tStart = clock();\n\tp.evolve();\n\tprintf(\"\\rTempo di esecuzione: %.4fs\\r\", (double)(clock() - tStart)\/CLOCKS_PER_SEC);\n\n\tprintf(\"\\r---------------\\rSoluzione: %d\\r\",p.bestIndividual[IND_SIZE]);\n\tprintf(\"Items:\\r[\");\n\tfor(int i=0;i<IND_SIZE;i++)\n\t\tprintf(\"%d \",p.w[i]);\n\tprintf(\"]\\r\");\n\tprintf(\"Items soluzione:\\r[\");\n\tfor(int i=0;i<IND_SIZE;i++)\n\t\tprintf(\"%d \",p.w[i]*p.bestIndividual[i]);\n\tprintf(\"]\\r\");\n\treturn 0;\n}<\/code><\/pre>\n\n\n\nEsempio di output:<\/p>\n\n\n\n
--------------------\nGenerazione n.0\nBest Fit=524\nBest Fit=548\nBest Fit=579\nMAX=1833 AVG=382 MIN=339\n--------------------\nGenerazione n.1\nBest Fit=593\nMAX=1689 AVG=333 MIN=283\n--------------------\nGenerazione n.2\nBest Fit=598\nMAX=1189 AVG=351 MIN=283\n--------------------\nGenerazione n.3\nBest Fit=600\nOptimal Solution z=600 found!\nMAX=1189 AVG=406 MIN=203\n\nTempo di esecuzione: 0.0267s\n\n---------------\nSoluzione: 600\nItems:\n[92 123 109 82 174 110 148 147 96 136 169 67 114 129 100 124 122 101 62 81 ]\nItems soluzione:\n[92 0 0 0 0 0 0 0 0 136 0 67 0 0 100 124 0 0 0 81 ]<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"In questo articolo vi presento un possibile algoritmo genetico da me implementato in C++ per questioni di velocit\u00e0 di calcolo (e non solo…). L’algoritmo \u00e8 molto semplice e compatto, ma vi assicuro che funziona benissimo! Come esempio di problema da risolvere ho adottato il subset sum problem. Esempio di output:<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,13,11,7],"tags":[],"class_list":["post-922","post","type-post","status-publish","format-standard","hentry","category-c","category-intelligenza-artificiale","category-or","category-stem"],"_links":{"self":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/922","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=922"}],"version-history":[{"count":2,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/922\/revisions"}],"predecessor-version":[{"id":932,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=\/wp\/v2\/posts\/922\/revisions\/932"}],"wp:attachment":[{"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=922"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=922"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/es-andreabianchini.it\/andrewsblog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=922"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}