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