Categoria: Intelligenza Artificiale

In questo articolo vi presento un possibile algoritmo genetico da me implementato in C++ per questioni di velocità di calcolo (e non solo…).

L’algoritmo è molto semplice e compatto, ma vi assicuro che funziona benissimo! Come esempio di problema da risolvere ho adottato il subset sum problem.

//==========================================================================
// Name        : aga.cpp
// Author      : Andrea Bianchini (2021)
// Version     : 1.0.0
// Copyright   : SOME RIGHT RESERVED CREATIVE COMMONS BY 4.0
// License     : https://creativecommons.org/licenses/by/4.0/
// Description : AGA - Andrew's Genetic Algorithm
// Use         : AGA p = AGA(PSIZE,ISIZE,RMIN,RMAX,IMAX,PCROSS,PMUT);
//             : p.evolve();
// Where       : PSIZE = Population size (number of individuals)
//             : ISIZE = Individual size (number of variables)
//             : RMIN  = Individual variables min value
//             : RMAX  = Individual variables max value
//             : IMAX  = Max number of iteration
//             : PCROSS= Crossover probability
//             : PMUT  = Mutation probability
// Example     : AGA p = AGA(500,20,0,1,10,0.5,0.3);
//             : p.evolve();
//             :
//             : Personalize your objective into evalIndividual().
//             : This file is personalized to solve subset sum problem.
//==========================================================================
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <math.h>
#include <time.h>


class AGA
{
protected:
	int POP_SIZE = 500;
	int IND_SIZE = 20;
	int RANGE_MIN = 0;
	int RANGE_MAX = 1;
	int MAXITER = 10;
	float PCROSS = 0.5;
	float PMUT = 0.3;
	int **pop;
	int first=1;
	int solfound;
	int niter;

public:
	int *w;
	int *bestIndividual;
	int c = 400;

	void initSSP()
	{
		w=new int [IND_SIZE];
		for(int i=0;i<IND_SIZE;i++)
		w[i]=c*0.1+(int)(rand()%(int)(c*0.3-c*0.1+1));

	}
	AGA(int pops, int inds, int rmin, int rmax, int maxiter, float pcross, float pmute)
		{
			solfound=0;
			niter=0;
			first=1;
			POP_SIZE=pops;
			IND_SIZE=inds;
			RANGE_MIN=rmin;
			RANGE_MAX=rmax;
			MAXITER = maxiter;
			PCROSS = pcross;
			PMUT = pmute;
			pop = new int* [POP_SIZE];
			int i;
			for(i=0;i<POP_SIZE;i++)
			{
				pop[i] = new int [IND_SIZE+1]; // +1 for fit
				pop[i][IND_SIZE]=0;
			}
			bestIndividual=new int [IND_SIZE+1];
			bestIndividual[IND_SIZE]=0;
			initSSP();
		}

	~AGA()
	{
		for(int i=0;i<POP_SIZE;i++)
			delete[] pop[i];
		delete[] pop;
		delete[] bestIndividual;
		delete[] w;
	}

	int * individual(int i)
	{
		return pop[i];
	}

	void populate()
	{
		int ind;
		for(ind=0;ind<POP_SIZE-1;ind++)
			for(int k=ind+1;k<POP_SIZE;k++)
				if (abs(individual(ind)[IND_SIZE]-c)>abs(individual(k)[IND_SIZE]-c))
				{
					int *p=individual(ind);
					pop[ind]=pop[k];
					pop[k]=p;
				}
		//..........
		if (first==1)
		{
			for(ind=0;ind<POP_SIZE;ind++)
			{
				int *in;
				in = individual(ind);
				for(int j=0;j<IND_SIZE;j++)
				{
					in[j] = rndInRange();
				}
				in[IND_SIZE]=0; // fit
			}
			first=0;
		}
		else
		{
			int p2=POP_SIZE*PCROSS+1;
			int p1=0;
			while(p2<POP_SIZE && p1<POP_SIZE*PCROSS+1)
			{
				Cross(p1,p2);
				if (p2<POP_SIZE*PMUT)
					Mutate(p2);
				p1++;
				p2++;
			}
			while (p2<POP_SIZE)
			{
				int *in;
				in = individual(p2);
				for(int j=0;j<IND_SIZE;j++)
				{
					in[j] = rndInRange();
				}
				in[IND_SIZE]=0; // fit
				p2++;
			}
		}
	}

	void Cross(int p1, int p2)
	{
		int *c1,*c2,*c3;

		c1=individual(p1);
		c2=individual(p1+1);
		c3=individual(p2);

		for(int i=0;i<IND_SIZE/2;i++)
		{
			c3[i]=c1[i];
		}
		for(int i=IND_SIZE/2;i<IND_SIZE;i++)
		{
			c3[i]=c2[i];
		}
		c3[IND_SIZE]=0;
	}

	void Mutate(int p2)
	{
		int c = rand() % IND_SIZE;
		int *d=individual(p2);
		d[c] = rndInRange();
	}

	int rndInRange()
	{
		int a = RANGE_MIN+(int)(rand()%(RANGE_MAX-RANGE_MIN+1));
		if (a>RANGE_MAX)
			a=RANGE_MAX;
		//printf("%d\n\r",a);
		return a;
	}

	void evalPopulation()
	{
		for(int i=0;i<POP_SIZE;i++)
		{
			evalIndividual(i);
		}

	}

	void evalIndividual(int i)
	{
		int z=0;
		int *p = individual(i);
		for(int j=0;j<IND_SIZE;j++)
			z+=w[j]*p[j];
		//if (z<c)
			p[IND_SIZE]=z;
		//else
			//p[IND_SIZE]=0;
		if (z<=c && z>bestIndividual[IND_SIZE])
		{
			for(int j=0;j<IND_SIZE;j++)
				bestIndividual[j]=p[j];
			bestIndividual[IND_SIZE]=z;
			printf("Best Fit=%d\r",z);
			if (z==c)
			{
				solfound=1;
				printf("Optimal Solution z=%d found!\r",z);
			}
		}
	
	}
	
	void evolve()
	{
		niter=0;
		while(niter<MAXITER && solfound==0)
		{
			printf("--------------------\rGenerazione n.%d\r",niter);
			populate();
			evalPopulation();
			int ind;
			int tot=0;
			for(ind=0;ind<POP_SIZE-1;ind++)
			{
				tot+=individual(ind)[IND_SIZE];
				for(int k=ind+1;k<POP_SIZE;k++)
					if (individual(ind)[IND_SIZE]<individual(k)[IND_SIZE])
					{
						int *p=individual(ind);
						pop[ind]=pop[k];
						pop[k]=p;
					}
			}
			tot+=individual(POP_SIZE-1)[IND_SIZE];
			tot/=POP_SIZE;
			printf("MAX=%d   AVG=%d   MIN=%d\r",pop[0][IND_SIZE],tot,pop[POP_SIZE-1][IND_SIZE]);
			niter++;
		}
	}
};

int main() {
	int POP_SIZE=500;
	int IND_SIZE=20;
	int RANGE_MIN=0;
	int RANGE_MAX=1;
	int MAXITER = 10;
	float PCROSS = 0.5;
	float PMUT = 0.3;

	AGA p = AGA(POP_SIZE,IND_SIZE,RANGE_MIN,RANGE_MAX,MAXITER,PCROSS,PMUT);
	p.c=600;
	p.initSSP();
	clock_t tStart = clock();
	p.evolve();
	printf("\rTempo di esecuzione: %.4fs\r", (double)(clock() - tStart)/CLOCKS_PER_SEC);

	printf("\r---------------\rSoluzione: %d\r",p.bestIndividual[IND_SIZE]);
	printf("Items:\r[");
	for(int i=0;i<IND_SIZE;i++)
		printf("%d ",p.w[i]);
	printf("]\r");
	printf("Items soluzione:\r[");
	for(int i=0;i<IND_SIZE;i++)
		printf("%d ",p.w[i]*p.bestIndividual[i]);
	printf("]\r");
	return 0;
}

Esempio di output:

--------------------
Generazione n.0
Best Fit=524
Best Fit=548
Best Fit=579
MAX=1833   AVG=382   MIN=339
--------------------
Generazione n.1
Best Fit=593
MAX=1689   AVG=333   MIN=283
--------------------
Generazione n.2
Best Fit=598
MAX=1189   AVG=351   MIN=283
--------------------
Generazione n.3
Best Fit=600
Optimal Solution z=600 found!
MAX=1189   AVG=406   MIN=203

Tempo di esecuzione: 0.0267s

---------------
Soluzione: 600
Items:
[92 123 109 82 174 110 148 147 96 136 169 67 114 129 100 124 122 101 62 81 ]
Items soluzione:
[92 0 0 0 0 0 0 0 0 136 0 67 0 0 100 124 0 0 0 81 ]