Dopo la rassegna prettamente teorica con cui abbiamo analizzato gli Algoritmi Genetici, vediamo tramite un semplice esempio come sia possibile mettere in pratica i principi sui quali si fondano. L' esempio che prenderemo in considerazione è il classico problema dello zaino (Knapsack Problem): supponiamo di dover partire per le tanto attese vacanze estive; supponiamo inoltre di avere una valigia con una capacità C limitata, e un insieme di n oggetti ciascuno con un peso wi e un valore ci; il problema consiste nel decidere quali oggetti mettere in valigia massimizzandone il valore, non superando la capacità massima della valigia. In termini un pò più formali possiamo definire la seguente formulazione:

 max Si cixi  tale che Si wixi < C

Il problema dello zaino può essere affrontato con diversi metodi risolutivi, noi ci concentreremo sugli algoritmi genetici; innanzitutto prima di buttarsi a capo fitto nel codice vi sono diverse elementi che vanno definiti in fase di progettazione :

  • Metodologia di creazione e codifica dei cromosomi
  • Algoritmo di selezione dei genitori per la ricombinazione
  • Definizione del processo di crossover e mutazione

Innanzitutto un cromosoma deve contenere l’informazione sulla soluzione che rappresenta, di conseguenza la scelta sulla modalità di codifica dipende principalmente dal problema da risolvere. Nel caso in esame la scelta è ricaduta quasi naturalmente su di una codifica di tipo binario: ogni bit rappresenta il fatto che un oggetto venga inserito o meno all'interno della valigia; ogni cromosoma viene quindi rappresentato da una stringa di bits (0 o 1) facilitando di fatto l' implementazione dei rispettivi operatori genetici. Per quanto concerne l' algoritmo di selezione ho scelto di utilizzare il metodo della Roulette Wheel utilizzando l' elitismo mantenendo di fatto i migliori cromosomi. Il crossover è stato realizzato tenendo conto del tipo di codifica scelto nel seguente modo: selezionato in modo random un punto di crossover all' interno del cromosoma, la stringa binaria compresa tra l’inizio e il punto di crossover viene copiata dal primo genitore, il resto viene copiato dal secondo genitore. La mutazione consiste nel cambiamento casuale del valore di alcuni bits da 0 a 1 o vicerversa.

Prese queste decisioni preliminari (di fondamentale importanza) si giunge finalmente alla parte di modellazione dell' object model in questione. Esistono diverse ottime librerie/framework C# scaricabili gratuitamente tra le quali spiccano AForge.NET e quella di Federico Chicchi . La prima è un vero e proprio framework di Artificial Intelligence composta da una serie di librerie che forniscono un ottimo supporto per coloro che devono effettuare lavori di ricerca nei diversi campi di intelligenza artificiale. La seconda  è una libreria per lavorare con gli algoritmi genetici del quale apprezzo sia il l' approccio molto OO con il quale sono state modellate le classi sia l'utilizzo dei delegates per il calcolo della funzione di fitness (calcolo variabile in base al problema in esame). Detto questo nello sviluppo del problema dello zaino ho deciso di non appoggiarmi a queste librerie per non sovraccaricare la difficoltà di comprensione specie per i neofiti in materia. vi mostro quindi il modello a oggetti del GA che ho utilizzato come base nell' affrontare il problema dello zaino:

Il modello è piuttosto semplice e rispecchia tutti gli elementi dei quali ho parlato nel post precedente; la classe Cromosoma rispecchia le informazioni proprie di un individuo quali array di bit dei geni, caratteristica di casualità e numero di geni componente il cromosoma; di seguito la parte di codice più interessante nella definizione di questa classe 

   1: public class Cromosoma: IComparable
   2:  
   3:    {
   4:  
   5:        private BitArray _bits;
   6:        private Int32 _importance;
   7:        private Int32 _length;
   8:        private Random _random;
   9:  
  10:    ... 
  11:  
  12:     public Cromosoma()
  13:  
  14:    {
  15:        Random= new Random();
  16:    }   
  17:  
  18:    
  19:  
  20:        public Cromosoma(int length, Random r)
  21:  
  22:    {
  23:  
  24:        Random= r;
  25:        Length = length;
  26:        Bits = new BitArray(length);
  27:        for(int i=0;i<length;i++)
  28:        {
  29:            double number = Random.NextDouble();
  30:            Bits[i] = number > 0.5 ? true : false;
  31:        }
  32:        
  33:    }
  34:  
  35:    
  36:  
  37:        /// <summary>
  38:        /// Costruttore di copia
  39:        /// </summary>
  40:        /// <param name="g"></param>
  41:        /// <param name="r"></param>
  42:        public Cromosoma(Cromosoma g,Random r)
  43:  
  44:    {
  45:  
  46:        Random = r;
  47:        Bits = new BitArray(g.Length);
  48:        Importance= g.Importance;
  49:        Length= g.Length;
  50:        for(int i=0;i<Length;i++)
  51:        {
  52:            Bits[i] = g.Bits[i];
  53:        }
  54:        
  55:    }   
  56:        /// <summary>
  57:        /// costruttore che esegue il crossover fra due cromosomi
  58:        /// </summary>
  59:        /// <param name="crom1">primo cromosoma</param>
  60:        /// <param name="crom2">secondo cromosoma</param>
  61:        /// <param name="r">parametro che serve per scegliere in maniera randomica il punto di crossover</param>
  62:  
  63:        public Cromosoma(Cromosoma crom1, Cromosoma crom2, Random r)
  64:    {
  65:        Random = r;
  66:        Bits = new  BitArray(crom1.Length);
  67:        Importance= 0;
  68:        Length = crom1.Length;
  69:        int crosspoint = Math.Abs(Random.Next())%Length;
  70:  
  71:        for(int i = 0;i<crosspoint;i++)
  72:        {
  73:            Bits[i]=crom1.Bits[i];
  74:        }
  75:        for(int i = crosspoint;i<Length;i++)
  76:        {
  77:            Bits[i]=crom2.Bits[i];
  78:        } 
  79:    }
  80:  
  81:    /// <summary>
  82:    /// Mutazione genomica, serve per mantenere alcune informazione del corredo genetico
  83:    /// </summary>
  84:    /// <param name="rate">la mutazione dei bit viene effettuata confrontandone il valore con un tasso fisso</param>
  85:  
  86:    public void mutate(double rate)
  87:  
  88:    {
  89:        for(int i=0;i<Length;i++)
  90:        { 
  91:            if(Math.Abs(Random.NextDouble()) < rate)
  92:            {
  93:                Bits[i] = !Bits[i];
  94:            }
  95:        }
  96:    }
  97:   
  98:   public int CompareTo(object obj)
  99:  
 100:    {
 101:        Double f = ((Cromosoma)obj).Importance;
 102:        return (this.Importance == f) ? 0 : (Importance < f) ? 1 : -1;
 103:    }

La classe GeneticAlgorithm è il nucleo dell' algoritmo dove vengono definiti sia gli operatori genetici di selezione che quelli di mutazione e crossover. Vediamo la parte di codice relativa a queste operazioni:

   1: public void RegeneratePopulation()
   2:  
   3:        {
   4:  
   5:        List<Cromosoma> nextGeneration = new List<Cromosoma>(CromosomaLength);
   6:  
   7:        //il miglior elemento viene mantenuto anche nella generazione successiva
   8:  
   9:        nextGeneration.Add(Population[0]);
  10:  
  11:        int i;
  12:  
  13:        
  14:  
  15:        SumFitness = 0;
  16:  
  17:         LowestFitness= (int)Worst().Importance-1;
  18:  
  19:        
  20:  
  21:        for(i=0;i<PopulationSize;i++)
  22:  
  23:        {
  24:  
  25:            SumFitness+= (int)(Population[i].Importance-LowestFitness);
  26:  
  27:        }
  28:  
  29:        
  30:  
  31:        
  32:  
  33:        
  34:  
  35:        for(i=1;i<PopulationSize;i++)
  36:  
  37:        {
  38:  
  39:            nextGeneration.Add(new Cromosoma(RouletteSelection(),
  40:  
  41:                                          RouletteSelection(),
  42:  
  43:                                          Random));
  44:  
  45:            
  46:  
  47:            if(Mutation)
  48:  
  49:            {
  50:  
  51:                nextGeneration[i].mutate(MutationFitnessRate);
  52:  
  53:            }
  54:  
  55:            
  56:  
  57:        }
  58:  
  59:        Population = nextGeneration;
  60:  
  61:     
  62:  
  63:    }
  64:  
  65:  
  66:  
  67:        //Seleziona un cromosoma in base alla roulette selection
  68:  
  69:        public Cromosoma  RouletteSelection()
  70:  
  71:        {
  72:  
  73:            if (SumFitness == 0)
  74:  
  75:            {
  76:  
  77:                return Population[Math.Abs(Random.Next()) % PopulationSize];
  78:  
  79:            }
  80:  
  81:            else
  82:  
  83:            {
  84:  
  85:                int x = Math.Abs(Random.Next()) % SumFitness;
  86:  
  87:                int count = 0;
  88:  
  89:  
  90:  
  91:                for (int i = 0; i < PopulationSize; i++)
  92:  
  93:                {
  94:  
  95:                    count += (int)(Population[i].Importance - LowestFitness);
  96:  
  97:                    if (count >= x)
  98:  
  99:                    {
 100:  
 101:                        return Population[i];
 102:  
 103:                    }
 104:  
 105:                }
 106:  
 107:            }
 108:  
 109:            return Population[PopulationSize- 1];
 110:  
 111:        }
 112:  
 113:  
 114:  
 115:        ///Metodo che dopo aver caricato tramite reflection la funzione di calcolo del valore di fitness,
 116:  
 117:        ///effettua il sorting della popolazione in base proprio ad esso
 118:  
 119:        public void evaluatePopulation()
 120:  
 121:    {
 122:  
 123:        for (int i = 0; i < PopulationSize; i++)
 124:  
 125:        {
 126:  
 127:            Object[] args = new Object[]{Population[i].Bits};
 128:  
 129:            Type[] parameters = new System.Type[]{Population[i].Bits.GetType()};
 130:  
 131:            Type c = Target.GetType();
 132:  
 133:            System.Reflection.MethodInfo m = 
 134:  c.GetMethod(FitnessFunction, (parameters == null)?new System.Type[0]:(System.Type[]) parameters);               
 135:  
 136:            Population[i].Importance= ((Int32) m.Invoke(Target, (System.Object[]) args));
 137:  
 138:        }
 139:  
 140:         //il sort sfrutta l' implementazione fornita del metodo CompareTo() definito per Cromosoma
 141:  
 142:            Population.Sort();
 143:  
 144:    }
 145:  

Definito il modello a oggetti per il nostro GA ci rimane da definire il modello a oggetti del dominio del problema

Abbiamo quindi definito la classe KnapSackContainer( valigia o bisaccia...chiamatela come volete) che presenta un campo per la capacità massima e la lista di oggetti da includere ed una classe che rappresenta gli oggetti che vogliamo inserire con campi peso e valore. Il metodo testFitness prende come input i geni (bits) di un cromosoma e verifica se questi rispettino o meno le specifiche di capacità imposte dello zaino. A questo punto non rimane altro che effettuare delle prove per verificare la corretta implementazione dell' algoritmo utilizzando alcuni dati di test (screenshot di esecuzione)

   1: static void Main(string[] args)
   2:  
   3:     {
   4:  
   5:         InitializeProblem();
   6:         GAalgorithm = 
   7:          new GeneticAlgorithm(knapSack.Items.Count,10,crossOver,mutation,0.1,knapSack,"testFitness");
   8:  
   9:         GAalgorithm.InitPopulation();
  10:         GAalgorithm.evaluatePopulation();
  11:         bestCromo = GAalgorithm.Best();
  12:         generation = 0;
  13:         Console.WriteLine("\n Capacità massima in kili che può sopportare lo zaino: 200");
  14:         Console.WriteLine("\nDopo un numero di generazioni pari a {0}", generation);
  15:         Console.WriteLine("La migliore soluzione ottenuta è {0} con un valore di {1}",
  16:          bestCromo.StringRepresentation(), bestCromo.Importance.ToString());
  17:  
  18:         Console.WriteLine("\nIndicami il numero di generazioni che deve analizzare l' algoritmo genetico);
  19:              per trovare una migliore soluzione"
  20:  
  21:         string numGens = Console.ReadLine();
  22:         int countGens;
  23:         if (Int32.TryParse(numGens, out countGens))
  24:         {
  25:             for (int i = 0; i < Int32.Parse(numGens); i++)
  26:             {
  27:                 generation++;
  28:                 GAalgorithm.RegeneratePopulation();
  29:                 GAalgorithm.evaluatePopulation();
  30:             }
  31:  
  32:             /* Miglior Cromosoma*/
  33:             bestCromo = GAalgorithm.Best();
  34:             Console.WriteLine("\nDopo un numero di generazioni pari a {0} \n", generation);
  35:             Console.WriteLine("La migliore soluzione ottenuta è {0} con un valore di {1} \n",
  36:                  bestCromo.StringRepresentation(), bestCromo.Importance.ToString());
  37:  
  38:             Console.ReadLine();
  39:         }
  40:         else
  41:         Console.WriteLine("\n Non hai inserito un numero ciaoooooooooo.........");
  42:     }
  43:     /// <summary>
  44:     /// Inizializza lo zaino settando la capacità a 200 kili e 
  45:     /// inserendo 20 elementi random
  46:     /// </summary>
  47:  
  48:     private static void InitializeProblem()
  49:  
  50:     {
  51:         crossOver = true;
  52:         mutation = true;
  53:         random = new Random();
  54:         knapSack = new KnapSackContainer(200);
  55:         knapSack.Items = new List<KnapSackItem>();
  56:         for (int i = 0; i < 20; i++)
  57:         {
  58:             knapSack.Items.Add( new KnapSackItem((Math.Abs(random.Next()) + 1) % 50,
  59:             (Math.Abs(random.Next()) + 1) % 50));
  60:  
  61:             numItems++;
  62:         }
  63:         foreach (KnapSackItem  item in knapSack)
  64:         {
  65:             Console.WriteLine("Inserito elemento con peso pari {0} e valore pari a {1}", item.Weight,
  66:              item.Value);
  67:         }
  68:     }
  69: }

Il consiglio quindi che mi sento di darvi è quello di fare qualche piccola prova come quella che vi ho mostrato per poi passare ad utilizzare una delle librerie che sopra vi ho citato per risolvere tipologie di problemi ben più complesse. In coda vi allego una serie di risorse utili.

Nunc est bibendum, nunc pede libero pulsanda tellus...

ITALIANO

Wikipedia

Vita Artificiale (ottimo)

Algoritmi Evolutivi

INGLESE

MSDN MAG

AAAI

Genetic Algorithms

C# Corner (diversi articoli con sorgente allegato)

 

Technorati tags: ,