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

 

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

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

Хромосома	Вероятность
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);

 

}

 

}

 

Итак, у нас есть и коэффициенты выживаемости (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);

 

}

 

return child;

 

}

 

В конце концов мы определим точку кроссовера. Заметим, что мы не хотим, чтобы кроссовер состоял из копирования только одного родителя. Сгенерируем случайное число, которое определит наш кроссовер. Остальное понятно и очевидно. Добавлена маленькая мутация, влияющая на скрещивание. 5% - вероятность появления нового числа.

Теперь уже можно взглянуть на функцию 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;

 

}

 

Описание завершено.

 

 

Листинг программы

 

 

#include <stdlib.h>

#include <time.h>

#include <iostream.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);          // Constructor with coefficients for a,b,c,d.

                   int Solve();                                                                       // Solve the equation.

                       

                   // Returns a given gene.

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

 

       protected:

                   int ca,cb,cc,cd;                                                                 // The coefficients.

                   int result;

                   gene population[MAXPOP];                                  // Population.

 

                   int Fitness(gene &);                                                          // Fitness function.

                   void GenerateLikelihoods();                                            // Generate likelihoods.

                   float MultInv();                                        // Creates the multiplicative inverse.

                   int CreateFitnesses();

                   void CreateNewPopulation();

                   int GetIndex(float val);

 

                   gene Breed(int p1, int p2);

 

};

 

CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {}

 

int CDiophantine::Solve() {

       int fitness = -1;

 

       // Generate initial population.

       srand((unsigned)time(NULL));

 

       for(int i=0;i<MAXPOP;i++) {                 // Fill the population with numbers between

                   for (int j=0;j<4;j++) {                                                       // 0 and the result.

                              population[i].alleles[j] = rand() % (result + 1);

                   }

       }

 

       if (fitness = CreateFitnesses()) {

                   return fitness;

       }

 

       int iterations = 0;                                                  // Keep record of the iterations.

       while (fitness != 0 || iterations < 50) {// Repeat until solution found, or over 50 iterations.

                   GenerateLikelihoods();                                        // Create the likelihoods.

                   CreateNewPopulation();

                   if (fitness = CreateFitnesses()) {

                              return fitness;

                   }

                       

                   iterations++;

       }

 

       return -1;

}

 

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;

}

 

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

       }

}

 

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;       // Create the crossover point (not first).

       int first = rand() % 100;                                                   // Which parent comes first?

 

       gene child = population[p1];                                // Child is all first parent initially.

 

       int initial = 0, final = 3;                                                    // The crossover boundaries.

       if (first < 50) initial = crossover;               // If first parent first. start from crossover.

       else final = crossover+1;                                                  // Else end at crossover.

 

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

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

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

       }

 

       return child;                                                                             // Return the kid...

}

 

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 > 25) break;

                   }

                       

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

       }

 

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

}

 

 

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;

       }

}

 

 

Заключение

 

Мы с вами проделали большой путь, открывая для себя генетические алгоритмы, их, казалось бы, тривиальную и одновременно с этим гениальную идею, взятую из природы. По окончанию работы можно сделать выводы о том, что: во-первых, генетические алгоритмы являются универсальным методом оптимизации многопараметрических функций, что позволяет решать широкий спектр задач; во-вторых, они имеют множество модификаций и сильно зависят от параметров. Зачастую небольшое изменение одного из них может привести к неожиданному улучшению результата. Но следует помнить, что применение ГА полезно лишь в тех случаях, когда для данной задачи нет подходящего специального алгоритма решения.

Несмотря на небольшое количество задач в данной научно-исследовательской работе, которое мы с вами рассмотрели: решение Диофантова уравнения и задачу коммивояжера, мы полностью подтверждаем гипотезу. Задачи оптимизации успешно решаются при помощи генетических алгоритмов.

 

Список используемой литературы

1. http://www.basegroup.ru/download/genebase.htm

2. http://www.basegroup.ru/genetic/math.htm

3. http://saisa.chat.ru/ga.html

4. http://algolist.manual.ru/ai/ga/ga1.php

5. http://www.ai.tsi.lv/ru/ga/ga_intro.html

6. http://port33.ru/users/acp/articles/Genetic_algorithms/index.html

7. http://paklin.newmail.ru/mater/gene_net.html

8. http://www.iki.rssi.ru/ehips/genetic.htm

9. http://fdmhi.mega.ru/ru/senn_ga.htm

10. http://www.vspu.ru/public_html/cterra/20.html

11. http://www.chat.ru/~saisa

12. http://www.xakep.ru/post/18589/default.asp

13. http://g-u-t.chat.ru/ga/oper.htm

14. http://iissvit.narod.ru/rass/vip4.htm

15. http://www.nestor.minsk.by/kg/index.html

16. http://algo.ekaboka.com/algo-rus/index.htm

17. http://www.neuroproject.ru

18. http://math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html

19. http://www.interface.ru/home.asp?artId=8109

20. http://algolist.ru/ai/ga/dioph.php

21. http://ru.wikipedia.org/wiki/Диофантово_уравнение

[1] http://paklin.newmail.ru/mater/gene_net.html

 

[2] http://www.ai.tsi.lv/ru/ga/ga_intro.html

 

[3] http://iissvit.narod.ru/rass/vip4.htm

[4] http://algo.ekaboka.com/algo-rus/index.htm

 

[5] http://www.neuroproject.ru

[6] http://www.interface.ru/home.asp?artId=8109

 

[7] http://math.nsc.ru/AP/benchmarks/UFLP/uflp_ga.html

 

[8] http://www.basegroup.ru/genetic/math.htm

[9] http://www.basegroup.ru/download/genebase.htm

 

[10] http://www.nestor.minsk.by/kg/index.html

[11] http://www.iki.rssi.ru/ehips/genetic.htm

[12] http://fdmhi.mega.ru/ru/senn_ga.htm

 

[13] http://chat.ru/ga.html

[14] http://www.chat.ru/~saia

 

[15] http://www.xakep.ru/post/18589/default.asp

[16] http://port33.ru/users/acp/articles/Genetic_algorithms/index.html

 

[17] http://paklin.newmail.ru/mater/gene_net.html

[18] http://www.vspu.ru/public_html/cterra/20.html

[19] http://algolist.manual.ru/ai/ga/ga1.php

[20] http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html

[21] http://algo.ekaboka.com/algo-rus/index.htm

 

[22] http://algolist.ru/ai/ga/dioph.php

[23] http://g-u-t.chat.ru/ga/oper.htm

[24] http://g-u-t.chat.ru/ga/oper.htm

 

[25] http://chat.ru/ga.html

[26] http://ru.wikipedia.org/wiki/Диофантово_уравнение

[27] http://algolist.ru/ai/ga/dioph.php