Генетические алгоритмы в задаче оптимизации действительных параметров

курсовая работа

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) более быстро и стабильно.

Делись добром ;)