Рассмотрим диофантово (только целые решения) уравнение: 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. Таблица 1: 1-е поколение хромосом и их содержимое Хромосома (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) Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением. Таблица 2: Коэффициенты выживаемости первого поколения хромосом (набора решений) Хромосома Коэффициент выживаемости 1 |114-30|=84 2 |54-30|=24 3 |56-30|=26 4 |163-30|=133 5 |58-30|=28 Так как меньшие значения ближе к 30, то они более желательны. В нашем случае большие численные значения коэффициентов выживаемости подходят, увы, меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Одно решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел - ГСЧ) Таблица 3: Вероятность оказаться родителем Хромосома Подходящесть 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% Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-стонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем: Таблица 4: Симуляция выбора родителей Хромосома отца Хромосома матери 3 1 5 2 3 5 2 5 5 3 Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кросс-оверов (| = разделительная линия): Таблица 5: Кросс-оверы между родителями Хромосома-отец Хромосома-мать Хромосома-потомок a1 | b1,c1,d1 a2 | b2,c2,d2 a1,b2,c2,d2 or a2,b1,c1,d1 a1,b1 | c1,d1 a2,b2 | c2,d2 a1,b1,c2,d2 or a2,b2,c1,d1 a1,b1,c1 | d1 a2,b2,c2 | d2 a1,b1,c1,d2 or a2,b2,c2,d1 Есть достаточно много путей передачи информации потомку, и кросс-овер - только один из них. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты. А теперь попробуем проделать это с нашими потомками Таблица 6: Симуляция кросс-оверов хромосом родителей Хромосома-отец Хромосома-мать Хромосома-потомок (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) Теперь мы можем вычислить коэффициенты выживаемости (fitness) потомков. Таблица 7: Коэффициенты выживаемости потомков (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 Средняя приспособленность (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; } } Подробный разбор этого класса и дальнейшие объяснения можно найти здесь.  8  Комментарии к статье  8 8  Обсудить в чате