AИ, ГА, Нейронные сети: Генетические алгоритмы.

Решение Диофантова Уравнения - разбор исходников

Перевод Кантор И.

CDiophantine

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

#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) каждого гена. В нашем случае это - модуль разности между желаемым результатом и полученным значением. Этот класс использует две функции: первая вычисляет все коэффициенты, а вторая - поменьше (желательно сделать ее inline) вычисляет коэффициент для какого-то одного гена.

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;
}

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

Хромосома	Вероятность
1	(1/84)/0.135266 = 8.80%
2	(1/24)/0.135266 = 30.8%
3	(1/26)/0.135266 = 28.4%
4	(1/133)/0.135266 = 5.56%
5	(1/28)/0.135266 = 26.4%

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

Хромосома	Вероятность (smi = 0.135266)
1	(1/84)/smi = 8.80%
2	(1/24)/smi = 39.6% (30.6+8.8)
3	(1/26)/smi = 68% (28.4+39.6)
4	(1/133)/smi = 73.56% (5.56+68)
5	(1/28)/smi = 99.96% (26.4+73.56)

Последнее значение всегда будет 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);
   }
}

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];
}

   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;
}

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);
   }

   return child;
}

И, наконец...
Теперь уже можно взглянуть на функцию Solve(). Она всего лишь итеративно вызывает вышеописанные функции. Заметим, что мы присутствует проверка: удалось ли функции получить результат, используя начальную популяцию. Это маловероятно, однако лучше проверить.

int CDiophantine::Solve() {
  int fitness = -1;

  // Generate initial population.
  srand((unsigned)time(NULL));

  for(int i=0;i<MAXPOP;i++) {
    for (int j=0;j<4;j++) {
      population[i].alleles[j] = rand() % (result + 1);
    }
  }

  if (fitness = CreateFitnesses()) {
    return fitness;
  }

  int iterations = 0;
  while (fitness != 0 || iterations < 50) {
    GenerateLikelihoods();
    CreateNewPopulation();
    if (fitness = CreateFitnesses()) {
      return fitness;
    }
    
    iterations++;
  }

  return -1;
}

Описание завершено. Пример использования был дан в предыдущем описании, а сам класс можно скачать тут.

Вверх по странице, к оглавлению и навигации.