ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ Область применения 1.Нахождение экстремумов функций 2. Решение задач размещения ресурсов 3. Решение задач экономического планирования. - презентация

1 ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ Область применения 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 ).

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

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

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

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

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

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

8 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

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

10

11 Пусть у объекта имеется 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

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

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

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

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

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

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