ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ Область применения 1.Нахождение экстремумов функций 2. Решение задач размещения ресурсов 3. Решение задач экономического планирования Пример. max f(x), где D = {x = (x 1, x 2, :, x N ) | x i на [a i, b i ], i=1, 2,:N} x из D Решение задачи - вектор x = (x 1, x 2, :, x N ).

ГА = (P0,, l, s, р, f, t) Поиск глобального оптимума

ГА = (P 0,, l, s, р, f, t) Формальное описание ГА где P 0 = (a 0 1,..., a 0 ) - исходная популяция, где, a 0 i - решение задачи, представленное в виде хромосомы; - целое число ( размер популяции); l - целое число (длина каждой хромосомы популяции); s - оператор отбора; p - отображение, определяющее рекомбинацию (кроссовер, мутация, инверсия); f - функция оптимальности; t - критерий остановки.

ОСОБЬ – ОДНО ИЗ ВОЗМОЖНЫХ РЕШЕНИЙ ПОСТАВЛЕННОЙ ЗАДАЧИ ПОПУЛЯЦИЯ – СОВОКУПНОСТЬ ОСОБЕЙ Х1Х2Х3 ОСОБЬ ИЛИ ХРОМОСОМА ГЕН ОСОБИ Х1Х2Х3 ……………… ПОПУЛЯЦИЯ

ПРИНЦИПЫ КОДИРОВАНИЯ ГЕНОВ Двоичное кодированиеКодирование по коду Грея Десяти чны й код Двоич. значе ние Шестн. значе ние Десят. код Двоич.з начен ие Шестн. значен ие h000000h h100011h h300113h h200102h h601106h h701117h h501015h h401004h h121100Ch h131101Dh Ah151111Fh Bh141110Eh Ch101010Ah

Х1Х2Х3 Как выбрать длину гена в соответствии с точностью?? Пример. Функция от двух переменных x 1 и x 2, определенной на прямоугольной области D = {0

1. Разбивают весь интервал допустимых значений признака на участки с требуемой точностью. 2. Принимают значение гена как целочисленное число, определяющее номер интервала (используя код Грея). 3. В качестве значения параметра принимают число, являющиеся серединой этого интервала. 2 алгоритм решения задачи выбора длины гена и кодировки для чисел с плавающей точкой Допустим, что значения признака лежат в интервале [0,1]. При кодировании использовалось разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется таким образом 8 бит. Допустим значение гена: bG. Найдем соответствующий ему номер интервала: 25hG->36h->54d. Получаем интервал [0, , 0, ]. Значит значение нашего параметра будет (0, , )/2=0,

1.Каждый интервал [a i, b i ] разбиваем на k отрезков равной длины. Определяем шаг h i = (b i - a i ) / k, i = 1, 2, :N. 2. Покроем i-ый интервал [a i, b i ] сетью s i из (k+1) узла с постоянным шагом h i. x i,j = a i + jh i, j = 0, 1, : k. 3. Длина кода q выбирается таким образом, чтобы k < 2 q. Наиболее целесообразно и экономично использовать сетку с k = 2 q алгоритм решения задачи выбора длины гена и кодировки для чисел с плавающей точкой Символьная запись j-ого узла по i-ой координатной оси в двоичном коде 1 i 2 i... q i

После дискретизации по всем N координатным осям, s = N 2 N... N особь Пример. f(x) = 10 + x sin(x), х [0, 10]. Пусть q=3. Тогда 2 3 =8- отрезков. Шаг h=10:8=1,25.

Пусть у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина особи будет 5*4=20 бит Определение. Приспособленность особи – значение соответственной целевой функции f(x) Например. Имеем функцию y=3 x 2 + 5x 3. Необходимо на участке х [1; 5] найти ее максимум. 1.Задаем популяцию особей согласно алгоритмам. 2.Рассчитываем приспособленность особей и всей популяции. Пусть 1 особь = 1, 2 особь – 2 и т.д. Приспособленность 1 особи 1 = 8, 2 =52 и т.д. Приспособленность всей популяции ( ….+ n )\n

Генетические операторы МУТАЦИЯ ИНВЕРСИЯ КРОССОВЕР ПОТОМКИ

Шаг 1.Инициализация начальной популяции. Ввести точку отсчета эпох t=0. Инициализировать случайным образом М генотипов особей и сформулировать из них начальную популяцию Вычислить приспособленность особей популяции a потом среднюю приспособленность популяции ПЛАН РАЗВИТИЯ ПОПУЛЯЦИИ ХОЛЛАНДА

Шаг 2. Выбор родителей для скрещивания 2.1. Увеличить номер эпохи на единицу t=t+1. Определить случайную переменную Rand t, на множестве М = {1,..., М}, назначив вероятность выпадения любого h М пропорциональной 2.2. Сделать одно испытание Rand t, и вычислить результат i(t}, который определит номер первого родителя Повторным испытанием определить номер второго родителя i(t).

Шаг 3. Формирование генотипа потомка С вероятностью кроссовера - Р с произвести над выбранными родителями кроссовер Выбрать одного из потомков и сохранить его как 1 A(t) Последовательно применить к 1 A(t) оператор инверсии (с вероятностью Р і,), а потом - мутации (с вероятностью P т ) Полученный генотип потомка сохранить как

Шаг 4. Отбор особи на элиминирование и замена ее потомком С равной вероятностью 1/М для всех h М определить случайным образом номер j(t) особи в популяции, которую заменит потомок Обновить текущую популяцию (t) путем замены на

Шаг 5. Определение приспособленности потомков Вычислить приспособленность потомка Е ( ) Обновить значение средней приспособленности (t) и вектор приспособленностей v(t). Шаг 6. Перейти к шагу 2.