Представление вещественных решений в двоичной форме

Обобщим генетический алгоритм на случай вещественных чисел на следующем примере:

f (x) = (1,85 - x)*cos(3,5x – 0,5)

График функции представлен на следующем рисунке:

 

Необходимо найти вещественные аргументы функции, принадлежащие интервалу от -10 до +10,которые максимизируют функцию.

Для представления вещественного решения хромосомы будем использовать двоичный вектор, который применялся в классическом простом генетическом алгоритме. Его длина зависит от требуемой точности решений, которой в данном примере положим 3 знака после запятой. Т.к. отрезок области решений имеет длину 20, для достижения данной точности отрезок [AC] = [-10;+10] должен быть разбит на равные части (отрезки), число которых должно быть достаточно большим. Для нашего примера 20*1000 = 20000.

В качестве двоичного представления используем код номера маленького отрезка. Этот код позволяет определить соответствует ему вещественное число, если известны границы области решения. Отсюда следует, что двоичный вектор для кодирования вещественного решения должен иметь 15 бит, т.к. число 20000 находится в пределах 16384 = 2¹⁴ < 20000 ≤ 2¹⁵ = 32768. Это позволяет разбить отрезок от -10 до +10 на 32768 частей и обеспечить необходимую точность. Отображение из двоичного представления (b₁₄, b₁₃, b₁₂…b₀),  где b_i {0, 1}, в вещественное число из отрезка АС выполняется в 2 шага:

1. Перевод двоичного числа в десятичное:

(< b₁₄, b₁₃, b₁₂…b₀ >)₂ = ( b_i 2ⁱ) = x'

3. Вычисление соответствующего вещественного числа x:

x = a + x' * ' * , где -10 – левая граница области решения.

Хромосомы все нули и все 15 единиц представляют границы отрезка

[-10; +10].  При данном представлении вещественных чисел можно использовать классический генетический алгоритм.

ГА в отличии от других оптимизирующих и поисковых процедур обладают следующими особенностями:

1. Работают не с параметрами, а с закодированным множеством параметров.

2. Осуществляет поиск из популяции точек, а не из единственной точки.

3. Использует целевую функцию непосредственно, а не ее приращение.

4. Использует не детерминированные, а вероятностные правила поиска решений.

5. Каждая новая популяция состоит из жизнеспособных особей (хромосом).

6. Каждая новая популяция лучше (в смысле целевой функции) предыдущей.

7. В процессе эволюции последующая популяция зависит только от предыдущей.

Использование кода Грея в ГА

Рассмотренное двоичное представление вещественного числа, имеет существенный недостаток: расстояние между реальными числами (на числовой оси) часто не соответствует расстоянию (по Хеммингу) между их двоичными представлениями. Поэтому желательно получить двоичное представление, где близкие расстояния между хромосомами (двоичными представлениями) соответствовали близким расстояниям в проблемной области (в данном случае расстоянию на числовой оси). Это можно сделать, использовав код Грея. Приведем пример соответствия для 4-х битового представления и кода  Грея.

Двоичный код	Код Грея
0000	0000
0001	0001
0010	0011
0011	0010
0100	0110
0101	0111
0110	0101
0111	0100
1000	1100
1001	1101
1010	1111
1011	1110
1100	1010
1101	1011
1110	1001
1111	1000

 

Заметим, что в кодах Грея соседние двоичные представления отличаются на 1 бит (расстояние по Хеммингу равно 1).

Рассмотрим алгоритмы преобразования двоичного числа в код Грея и наоборот:

Procedure Binary-to-Gray()

{

g₁ = b₁

for k=2 to m do

g_k = b_k-1 xor b_k

}

Procedure Gray-to-Binary

{

value=g₁

b₁=value

for k=2 to m do

     begin

                      if g_k= l then value=NOTvalue

                      b_k=value

 }

end

 

Представление хромосомы может быть не обязательно двоичной.

Рассмотрим диофантово (имеющее только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые числа.

Для начала выберем 5 случайных решений в диапазоне от 1 до 30:      1 =< a,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), подставим каждую хромосому в уравнение и подсчитаем расстояние от полученного значения до 30.

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

Таблица 2. Коэффициенты выживаемости первого поколения хромосом (набора решений)

В нашем случае большие численные значения коэффициентов выживаемости подходят меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы произвести потомков. Одним из вариантов решения является вычисление суммы обратных значений.

Хромосома	Подходящесть
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. Имитируем бросание кости 2 раза и зафиксируем пару хромосом.

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

Таблица 4: Симуляция выбора потомков

 

В результате кроссинговера над выбранными парами получены потомки:

 

Хромосома-отец	Хромосома-мать	Хромосома-потомок
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

Таблица 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)	|52-30|=22
(14,13,5,2)	|63-30|=33
(13,5,5,2)	|46-30|=16

Таблица 7: Коэффициенты выживаемости потомков (fitness)

Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4.

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

 

Модификация генетических алгоритмов

Раннее рассмотренная реализация относится к классической. Далее рассмотрим различные модификации для каждого функционального блока простого ГА.

 

Создание исходной популяции

Существует основных 3 способа создания исходной популяции:

1. Стратегия "одеяла" - формирование полной популяции, содержащей все возможные решения. Например, для n - разрядной хромосомы мы имеем всего 2ⁿ вариантов решений, которые формируют полную популяцию.

2. Стратегия "дробовика" - генерация достаточно большого случайного подмножества решений.

3. Стратегия фокусировки - генерация подмножества решений, включающих разновидности одного решения.

Первый подход (стратегия «одеяла») практически не реализуем даже для задач большой и средней размерности, вследствие больших вычислительных затрат. Популяция не может развиваться, т.к. в ней уже содержатся всевозможные решения.

Третий способ используется тогда, когда есть предположение, что некоторое решение является вариацией известного значения. В этом случае время поиска оптимального решения существенно сокращается, т.к. алгоритм начинает работу в окрестности оптимального решения.

Чаще всего применяют второй способ. В этом случае в результате эволюции есть возможность перейти в другие подобласти поиска.

Эффективность ГА во многом зависит от качества и структуры начальной популяции.

На практике часто применяют комбинацию второго и третьего способов. Сначала определяются особи с высокими значениями целевой функции, а затем случайно формируются начальные решения в этих подобластях.

 

Отбор родителей (селекция)

Оператор отбора S порождает промежуточную популяцию ^tиз текущей популяции   ^t  → Р ^t.

При отборе конкурентно-способных особей используют целевую (fitness) функцию, как единственно доступный источник информации о качестве решения.

Рассмотрим наиболее распространенные методы решения:

Пропорциональный отбор (метод "рулетки")

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

Номер особи	1	2	3	4	5	6	7	8	9	10	11
Значение ЦФ	2,0	1,8	1,6	1,4	1,2	1,0	0,8	0,6	0,4	0,2	0,0
Вероятность выбора	0,18	0,16	0,15	0,13	0,11	0,09	0,07	0,06	0,03	0,02	0,0

Здесь на отрезке [0,1] для каждой особи строятся отрезки, длины которых пропорциональны вероятностям выбора особей, как это показано на рисунке.

           

1               2         3       4       5     6  7 8

 

Рисунок - Вероятность выбора особей методом рулетки

 

Случайно генерируются числа от 0 до 1 и в промежуточную популяцию выбираются те особи, в "чей отрезок" попадают эти случайные числа.

Данный метод имеет следующие недостатки:

- зависимость от положительных значений целевой функции;

- без модификации метод может использоваться без модификации только для максимизации функции;

- простое добавление очень большой константы к целевой функции, может свести способ отбора практически к случайному выбору;

- особи с очень маленькими значениями фитнесс-функции слишком быстро исключаются из популяции, что может привести к преждевременной сходимости ГА.

Для устранения этих недостатков используют масштабирование относительно минимального значения в популяции или используется метод ранжирования.

Для приведенного примера можно привести следующую гистограмму выбора особей.

 

 

Метод ранжирования

 

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

       P_s (a_i) = ,

где 1 ≤ a ≤ 2 выбирается случайным образом;

b = 2 – a;

N – мощность популяции;

i – номер особи в упорядоченном списке.

Для приведенного примера гистограмма вероятностей выбора особей методом ранжирования, представлена на следующем рисунке. Высота "ступенек " в отличие от предыдущего выбора.

 

 

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