Генетические алгоритмы и их практическое применение

Таблица 5: Кроссоверы между родителями 
 

     Есть  достаточно много путей передачи информации потомку, и кроссовер - только один из них. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты.

     А теперь попробуем проделать это  с нашими потомками 
 

Таблица 6: Симуляция кросс-оверов хромосом родителей 

     Теперь  мы можем вычислить коэффициенты выживаемости (fitness) потомков.

Таблица 7: Коэффициенты выживаемости потомков (fitness) 

     Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30.

     Продолжая таким образом, одна хромосома в  конце концов достигнет коэффициента выживаемости 0, то есть станет решением.  

     Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому  уровню (0) более быстро и стабильно.²⁷ 

1.1 Принцип работы программы 

     Oбранимся к теоретическим пояснениям в практической реализации данной задачи в среде программирования С++ :

Первым делом  посмотрим на заголовок класса:  

#include <stdlib.h> 

#include <time.h> 

#define MAXPOP 25 
 

struct gene { 

   int alleles[4]; 

   int fitness; 

   float likelihood; 
 

   // Test for equality. 

   operator==(gene gn) { 

      for (int i=0;i<4;i++) { 

         if (gn.alleles[i] != alleles[i]) return false; 

      } 

      return true; 

   } 

}; 
 

class CDiophantine { 

   public: 

      CDiophantine(int, int, int, int, int); 

      int Solve(); 

      // Returns a given gene. 

      gene GetGene(int i) { return population[i];} 

   protected: 

      int ca,cb,cc,cd; 

      int result; 

      gene population[MAXPOP]; 
 

      int Fitness(gene &); 

      void GenerateLikelihoods(); 

      float MultInv();inverse. 

      int CreateFitnesses(); 

      void CreateNewPopulation();

      int GetIndex(float val); 
 

      gene Breed(int p1, int p2); 
 

}; 

     Существуют  две структуры: gene и класс CDiophantine. gene используется для слежения за различными наборами решений. Создаваямая популяция - популяция ген. Эта генетическая структура отслеживает свои коэффициенты выживаемости и вероятность оказаться родителем. Также есть небольшая функция проверки на равенство.  

Теперь  по функциям:  

Fitness function 

     Вычисляет коэффициент выживаемости (приспособленности - fitness) каждого гена. В нашем случае это - модуль разности между желаемым результатом и полученным значением. Этот класс использует две функции: первая вычисляет все коэффициенты, а вторая – поменьше - вычисляет коэффициент для какого-то одного гена.  

int CDiophantine::Fitness(gene &gn) { 

   int total = ca * gn.alleles[0] + cb * gn.alleles[1] 

             + cc * gn.alleles[2] + cd * gn.alleles[3]; 
 

   return gn.fitness = abs(total - result); 

} 
 

int CDiophantine::CreateFitnesses() { 

   float avgfit = 0; 

   int fitness = 0; 

   for(int i=0;i<MAXPOP;i++) { 

      fitness = Fitness(population[i]); 

      avgfit += fitness; 

      if (fitness == 0) { 

         return i; 

      } 

   } 

  

   return 0; 

} 
 

     Заметим, что если fitness = 0, то найдено решение - возврат. После вычисления приспособленности (fitness) нам нужно вычислить вероятность выбора этого гена в качестве родительского.

Likelihood functions

     Как и было объяснено, вероятность вычисляется  как сумма обращенных коэффициентов, деленная на величину, обратную к коэффициенту данному значению. Вероятности кумулятивны (складываются), что делает очень легким вычисления с родителями. Например:

 
 

     В программе, при одинаковых начальных  значениях, вероятности сложатся: представьте  их в виде кусков пирога. Первый ген - от 0 до 8.80%, следующий идет до 39.6% (так  как он начинает 8.8). Таблица вероятностей будет выглядеть приблизительно так: 

 

     Последнее значение всегда будет 100. Имея в нашем  арсенале теорию, посмотрим на код. Он очень прост: преобразование к float необходимо для того, чтобы избегать целочисленного деления. Есть две функции: одна вычисляет smi, а другая генерирует вероятности оказаться родителем.  

float CDiophantine::MultInv() { 

   float sum = 0; 

   for(int i=0;i<MAXPOP;i++) { 

      sum += 1/((float)population[i].fitness); 

   }

   return sum; 

}

void CDiophantine::GenerateLikelihoods() { 

   float multinv = MultInv(); 

   float last = 0; 

   for(int i=0;i<MAXPOP;i++) { 

      population[i].likelihood = last  

      = last + ((1/((float)population[i].fitness) / multinv) * 100); 

   } 

} 

     Итак, у нас есть и коэффициенты выживаемости (fitness) и необходимые вероятности (likelihood). Можно переходить к размножению (breeding).

Breeding Functions

     Функции размножения состоят из трех: получить индекс гена, отвечающего случайному числу от 1 до 100, непосредственно  вычислить кроссовер двух генов  и главной функции генерации  нового поколения. Рассмотрим все эти функции одновременно и то, как они друг друга вызывают. Вот главная функция размножения:  

void CDiophantine::CreateNewPopulation() { 

   gene temppop[MAXPOP]; 

   for(int i=0;i<MAXPOP;i++) { 

      int parent1 = 0, parent2 = 0, iterations = 0; 

      while(parent1 == parent2 || population[parent1] 

            == population[parent2]) { 

         parent1 = GetIndex((float)(rand() % 101)); 

         parent2 = GetIndex((float)(rand() % 101)); 

         if (++iterations > (MAXPOP * MAXPOP)) break;

      }

      temppop[i] = Breed(parent1, parent2);  // Create a child. 

   }

   for(i=0;i<MAXPOP;i++) population[i] = temppop[i]; 

} 

     Итак, первым делом мы создаем случайную  популяцию генов. Затем делаем цикл по всем генам. Выбирая гены, мы не хотим, чтобы они оказались одинаковы (ни к чему скрещиваться с самим собой, и вообще - нам не нужны одинаковые гены (operator = в gene). При выборе родителя, генерируем случайное число, а затем вызываем GetIndex. GetIndex использует идею кумулятивности вероятностей (likelihoods), она просто делает итерации по всем генам, пока не найден ген, содержащий число:  

   int CDiophantine::GetIndex(float val) { 

   float last = 0; 

   for(int i=0;i<MAXPOP;i++) { 

      if (last <= val && val <= population[i].likelihood) return i; 

      else last = population[i].likelihood; 

   }

   return 4; 

} 

     Возвращаясь к функции CreateNewPopulation(): если число  итераций превосходит MAXPOP2, она выберет  любых родителей. После того, как  родители выбраны, они скрещиваются: их индексы передаются вверх на функцию размножения (Breed). Breed function возвращает ген, который помещается во временную популяцию. Вот код:  

gene CDiophantine::Breed(int p1, int p2) {

   int crossover = rand() % 3+1; 

   int first = rand() % 100; 

   gene child = population[p1]; 

   int initial = 0, final = 3; 

   if (first < 50) initial = crossover; 

   else final = crossover+1; 

   for(int i=initial;i<final;i++) { 

      child.alleles[i] = population[p2].alleles[i]; 

      if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);