Пример ГА: Решение Диофантова уравнения

Путь: АИ, ГА, Нейронные сети » Генетические алгоритмы » Диофантово уравнение

Пример ГА: Решение Диофантова уравнения

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

Рассмотрим диофантово (только целые решения) уравнение: 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.

Хромосома	(a,b,c,d)
1	(1,28,15,3)
2	(14,9,2,4)
3	(13,5,7,3)
4	(23,8,16,19)
5	(9,13,5,2)

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

Хромосома	Коэффициент выживаемости
1	\|114-30\|=84
2	\|54-30\|=24
3	\|56-30\|=26
4	\|163-30\|=133
5	\|58-30\|=28

Таблица 2: Коэффициенты выживаемости первого поколения хромосом (набора решений)
Так как меньшие значения ближе к 30, то они более желательны. В нашем случае большие численные значения коэффициентов выживаемости подходят, увы, меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Одно решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел - ГСЧ)

Хромосома	Подходящесть
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%

Таблица 3: Вероятность оказаться родителем
Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-стонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем:

Хромосома отца	Хромосома матери
3	1
5	2
3	5
2	5
5	3

Таблица 4: Симуляция выбора родителей
Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a₁,b₁,c₁,d₁, а отец - a₂,b₂,c₂,d₂, тогда возможно 6 различных кросс-оверов (| = разделительная линия):

Хромосома-отец	Хромосома-мать	Хромосома-потомок
a₁ \| b₁,c₁,d₁	a₂ \| b₂,c₂,d₂	a₁,b₂,c₂,d₂ or a₂,b₁,c₁,d₁
a₁,b₁ \| c₁,d₁	a₂,b₂ \| c₂,d₂	a₁,b₁,c₂,d₂ or a₂,b₂,c₁,d₁
a₁,b₁,c₁ \| d₁	a₂,b₂,c₂ \| d₂	a₁,b₁,c₁,d₂ or a₂,b₂,c₂,d₁

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

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

Хромосома-отец	Хромосома-мать	Хромосома-потомок
(13 \| 5,7,3)	(1 \| 28,15,3)	(13,28,15,3)
(9,13 \| 5,2)	(14,9 \| 2,4)	(9,13,2,4)
(13,5,7 \| 3)	(9,13,5 \| 2)	(13,5,7,2)
(14 \| 9,2,4)	(9 \| 13,5,2)	(14,13,5,2)
(13,5 \| 7, 3)	(9,13 \| 5, 2)	(13,5,5,2)

Таблица 6: Симуляция кросс-оверов хромосом родителей
Теперь мы можем вычислить коэффициенты выживаемости (fitness) потомков.

Хромосома-потомок	Коэффициент выживаемости
(13,28,15,3)	\|126-30\|=96
(9,13,2,4)	\|57-30\|=27
(13,5,7,2)	\|57-30\|=22
(14,13,5,2)	\|63-30\|=33
(13,5,5,2)	\|46-30\|=16

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

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

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

C++ код.

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

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

Затем, чтобы решить уравнение, вызовите функцию Solve() , которая возвратит аллель, содержащую решение. Вызовите GetGene(), чтобы получить ген с правильными значениями a, b, c, d. Стандартная процедура main.cpp, использующая этот класс, может быть такой:

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

Подробный разбор этого класса и дальнейшие объяснения можно найти здесь. А здесь его можно просто скачать.