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

• Диофантово уравнение
• C++ код
• CDiophantine

Рассмотрим диофантово (только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d).

Конечно, Вы можете спросить: почему бы не использовать метод грубой силы: просто не подставить все возможные значения a, b, c, d (очевидно, 1 <= a,b,c,d <= 30) ?

Архитектура ГА-систем позволяет найти решение быстрее за счет более 'осмысленного' перебора. Мы не перебираем все подряд, но приближаемся от случайно выбранных решений к лучшим.

Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30.

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

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

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

к началу

Класс на C++ требует 5 значений при инициализации: 4 коэффициента и результат. Для вышепривиденного примера это будет выглядеть так:

CDiophantine dp(1,2,3,4,30);

#include "<iostream.h>"
#include "diophantine.h"

void main() {

   CDiophantine dp(1,2,3,4,30);

   int ans;
   ans = dp.Solve();
   if (ans == -1) {
      cout << "No solution found." << endl;
   } else {
      gene gn = dp.GetGene(ans);

      cout << "The solution set to a+2b+3c+4d=30 is:\n";
      cout << "a = " << gn.alleles[0] << "." << endl;
      cout << "b = " << gn.alleles[1] << "." << endl;
      cout << "c = " << gn.alleles[2] << "." << endl;
      cout << "d = " << gn.alleles[3] << "." << endl;
   }
}

к началу

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

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

}