Обобщим генетический алгоритм на случай вещественных чисел на следующем примере:
f (x) = (1,85 - x)*cos(3,5x – 0,5)
График функции представлен на следующем рисунке:
Необходимо найти вещественные аргументы функции, принадлежащие интервалу от -10 до +10,которые максимизируют функцию.
Для представления вещественного решения хромосомы будем использовать двоичный вектор , который применялся в классическом простом генетическом алгоритме. Его длина зависит от требуемой точности решений, которой в данном примере положим 3 знака после запятой. Т.к. отрезок области решений имеет длину 20, для достижения данной точности отрезок [AC] = [-10;+10] должен быть разбит на равные части (отрезки), число которых должно быть достаточно большим. Для нашего примера 20*1000 = 20000.
В качестве двоичного представления используем код номера маленького отрезка. Этот код позволяет определить соответствует ему вещественное число, если известны границы области решения. Отсюда следует, что двоичный вектор для кодирования вещественного решения должен иметь 15 бит, т.к. число 20000 находится в пределах 16384 = 214 < 20000 ≤ 215 = 32768. Это позволяет разбить отрезок от -10 до +10 на 32768 частей и обеспечить необходимую точность. Отображение из двоичного представления (b14, b13, b12…b0), где bi {0, 1}, в вещественное число из отрезка АС выполняется в 2 шага:
1. Перевод двоичного числа в десятичное:
(< b14, b13, b12…b0 >)2 = ( bi 2i ) = x'
3. Вычисление соответствующего вещественного числа x:
x = a + x' * ' * , где -10 – левая граница области решения.
Хромосомы все нули и все 15 единиц представляют границы отрезка
[-10; +10]. При данном представлении вещественных чисел можно использовать классический генетический алгоритм.
ГА в отличии от других оптимизирующих и поисковых процедур обладают следующими особенностями:
1. Работают не с параметрами, а с закодированным множеством параметров.
2. Осуществляет поиск из популяции точек, а не из единственной точки.
3. Использует целевую функцию непосредственно, а не ее приращение.
4. Использует не детерминированные, а вероятностные правила поиска решений.
5. Каждая новая популяция состоит из жизнеспособных особей (хромосом).
6. Каждая новая популяция лучше (в смысле целевой функции) предыдущей.
7. В процессе эволюции последующая популяция зависит только от предыдущей.
Использование кода Грея в ГА
Рассмотренное двоичное представление вещественного числа, имеет существенный недостаток: расстояние между реальными числами (на числовой оси) часто не соответствует расстоянию (по Хеммингу) между их двоичными представлениями. Поэтому желательно получить двоичное представление, где близкие расстояния между хромосомами (двоичными представлениями) соответствовали близким расстояниям в проблемной области (в данном случае расстоянию на числовой оси). Это можно сделать, использовав код Грея. Приведем пример соответствия для 4-х битового представления и кода Грея.
Двоичный код
Код Грея
Заметим, что в кодах Грея соседние двоичные представления отличаются на 1 бит (расстояние по Хеммингу равно 1).
Рассмотрим алгоритмы преобразования двоичного числа в код Грея и наоборот:
Procedure Binary-to-Gray()
{
g1 = b1
for k=2 to m do
gk = bk-1 xor bk
}
Procedure Gray-to-Binary
{
value=g1
b1=value
for k=2 to m do
begin
if gk= l then value=NOTvalue
bk=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,28,15,3)
(14,9,2,4)
(13,5,7,3)
(23,8,16,19)
(9,13,5,2)
Таблица 1. 1-е поколение хромосом и их содержимое
Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждую хромосому в уравнение и подсчитаем расстояние от полученного значения до 30.
Хромосома
Коэффициент выживаемости
|114-30|=84
|54-30|=24
|56-30|=26
|163-30|=133
|58-30|=28
Таблица 2. Коэффициенты выживаемости первого поколения хромосом (набора решений)
В нашем случае большие численные значения коэффициентов выживаемости подходят меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы произвести потомков. Одним из вариантов решения является вычисление суммы обратных значений.
Хромосома
Подходящесть
(1/84)/0.135266 = 8.80%
(1/24)/0.135266 = 30.8%
(1/26)/0.135266 = 28.4%
(1/133)/0.135266 = 5.56%
(1/28)/0.135266 = 26.4%
Таблица 3: Вероятность оказаться родителем
Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-сторонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Имитируем бросание кости 2 раза и зафиксируем пару хромосом.
Хромосома отца
Хромосома матери
Таблица 4: Симуляция выбора потомков
В результате кроссинговера над выбранными парами получены потомки:
{0, 1}, в вещественное число из отрезка АС выполняется в 2 шага:
bi 2i ) = x'
' * 
, где -10 – левая граница области решения.