Генетические алгоритмы

Эволюционные алгоритмы Генетические алгоритмы (genetic algorithms) совместно с эволюционной стратегией и эволюционным программированием представляют три главных направления развития эволюционного моделирования. Эволюционный алгоритм – это оптимизационный метод, базирующийся на эволюции популяции «особей», каждая из которых характеризуется приспособленностью –многомерной функцией её генов. Основные эволюционные алгоритмы Генет ический алгоритм (ГА) предназначен для оптимизации функций дискретных переменных и акцентирующий своё внимание на рекомбинации геномов. Эволюционная ст ратегия, ориентирована на оптимизацию непрерывных функций с использованием рекомбинаций. Эволюционное программирование ориентировано на оптимизацию непрерывных функций безиспользованием рекомбинаций. Генет ическое программирование использует эволюционный метод для оптимизации компьютерных программ. Эффективность ГА эффективность методы, использующие элемент случайности переборные методы градиентные методы комбинаторные задачи унимодальные задачи мультимодальные тип задачи задачи Рисунок 1.1 – Зависимость эффективности методов от типа решаемой задачи История создания ГА Парадигму генетических алгоритмов предложил Джон Холланд, опубликовавший в начале 60-х годов её основные положения. А всеобщее признание она получила после выхода в свет в 1975 году его классического труда “Адаптация в естественных и искусственных системах”. Основные термины  генотип и фенотип, особь и качество особи,  популяция и размер популяции,  поколение,  родители и потомки. К х аракт ерист икам генет ического алгорит ма от носят ся:       размер популяции, оператор скрещивания и вероятность его использования, оператор мутации и вероятность мутации, оператор отбора, оператор редукции, критерий останова. Операт оры от бора, скрещивания , мут ации и редукции назы вают еще генет ическими операт орами. Критерии останова ГА Критерием останова работы генетического алгоритма может быть одно из трех событий:  Сформировано заданное пользователем число поколений.  Популяция достигла заданного пользователем качества (например, значение качества всех особей превысило заданный порог)  Достигнут некоторый уровень сходимости. То есть особи в популяции стали настолько подобными, что дальнейшее их улучшение происходит очень медленно. Ст руктура классического генет ического алгоритма 1. Создание исходной популяции (задается случайным образом). 2. Выбор родителей для процесса размножения (работает оператор отбора -селекции). 3. Создание потомков выбранных пар родителей (работает оператор скрещивания - crossover). 4. 5. Мутация новых особей (работает оператор мутации). Расширение популяции за счет добавления новых, только что порожденных особей. 6. Сокращение расширенной популяции до исходного размера (работает оператор редукции). 7. Останов работы генетического алгоритма по заданному критерию или цикл с шага 2. Поиск лучшей достигнутой особи в конечной популяции является результатом работы генетического алгоритма. 8. Вероятность участия особи в процессе размножения n  i fi  fj, j1 где n – размер популяции; i – номер особи; Pi – вероятность участия особи в процессе размножения; fi – значение целевой функции для i-й особи. Виды ф ункции приспособленност и (оценки) (fitnes function) 1. 2. 3. 4. В задачах оптимизации –это целевая функция В теории управления – это функция погрешности В теории игр – это функция стоимости При обучении нейронной сети – это среднеквадратичная ошибка обучения Методы селекции Каждый сектор пропорционален вероятности участия особи в размножении в методе «рулетки» Р4=11/43 Р1=18/43 Р3=12/43 Р2=2/43 Скрещивание особей Родители Строка 1 000000 * 000 Строка 2 111111 * 111 Потомки 000000111 111111000 Двухточечный кроссинговер Родители Строка 1 000* 000 * 000 Строка 2 111* 111 * 111 Потомки 000111000 111000111 Элитизм При этом элитные особи участвуют еще и в процессе отбора родителей для последующего скрещивания. Количество элитных особей определяется обычно по формуле K=(1-P)N, где К- количество элитных особей; Р – вероятность применения оператора скрещивания; N- размер популяции. Пример решения задачи Пример поиска максимума одномерной функции. Пусть имеется набор натуральных чисел от 1 до 31 и функция, определенная на этом наборе чисел, f(x)=x. Требуется найти максимальное значение функции. Шаг1- Исходная популяция Номер строки Код генотипа Значение целевой функции Вероятность участия в размножении 1 01011 11 11/43 2 10010 18 18/43 3 00010 2 2/43 4 01100 12 12/43 Σ=43 Шаг 2 – Отбор особей Предположим, что оператор отбора выбрал для производства потомков две пары строк (1, 2) и (2, 4).. Шаг 3- Скрещивание Шаг 4 - Мутация Номер строки Родители Потомки Значение целевой функции для потомков 1 0*1011 00010 2 2 1*0010 11011 27 3 100*10 4 011*00 10000 10001 01110 16 17 (мутация) 14 Шаг 5- Расширенная популяция Шаг 6 - Редукция № строки 1 исходная Код 01011 Значение ЦФ 11 2 исходная 10010 18 3 исходная 4 исходная 5 потомки 00010 01100 00010 2 12 2 6 потомки 7 потомки 8 потомки 11011 10001 01110 27 17 14 Шаг 7 –Новое первое поколение Номер строки Код генотипа Значение целевой функции Вероятность участия в размножении 1 10010 18 18/76 2 11011 27 27/76 3 10001 17 17/76 4 01110 14 14/76 Σ=76 Результаты работы ГА Очевидно, что даже за эту одну итерацию качество популяции значительно возросло. Если в исходной популяции среднее значение целевой функции было 10, 75, а ее минимальное значение составляло 2, то в популяции первого поколения среднее значение увеличилось до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31. Задача коммивояж ера Задача коммивояжера является классической оптимизационной задачей. Суть ее заключается в следующем. Дано множество из n городов и матрица расстояний между ними или стоимостей переезда (в зависимости от интерпретации). Цель коммивояжера – объехать все эти города по кратчайшему пути или с наименьшими затратами на поездку. Причем в каждом городе он должен побывать один раз и свой путь закончить в том же городе, откуда начал. Матрица стоимости переезда • Город • Город • Город • Город • Город 1 2 3 4 5 Г1 Г2 0 4 4 0 6 3 2 2 9 9 Г3 6 3 5 9 Г4 2 2 5 8 Г5 9 9 9 8 Двухточечный оператор скрещивания Родительские перестановки (1*234*5) (*/452/*)  (34521) (3*452*1) (*/234/*)  (52341) 1 этап обмен фрагментами 2 этап замена * на цифру, начиная со 2-ой цифры в выделенном звёздочками фрагменте Шаг1- Исходная популяция Номер строки Код генотипа Значение целевой функции Вероятность участия в размножении 1 12345 29 32/122 2 21435 29 32/122 3 54312 32 29/122 4 43125 32 29/122 Σ=122 Шаг 2 – Отбор особей Предположим, что оператор отбора выбрал для скрещивания следующие пары: (1,3) и (2,4). Шаг 3- Скрещивание Шаг 4 - Мутация Номер строки Родители Потомки Значение целевой функции для потомков 1 (1 особь) 12345 54312 32 2 (3 особь) 54312 12354 28 3 (2 особь) 21435 43125 мутация 13254 32 4 (4 особь) 43125 21435 28 29 Шаг 7 –Новое первое поколение Номер строки Код генотипа Значение целевой функции Вероятность участия в размножении 1 12345 29 28/115 2 21435 29 28/115 3 13254 28 31/115 4 21435 29 28/115 Σ=115 Принципы обучения нейронной сет и с помощью генет ических алгорит мов Wij Vij * Х1  Y 1 Х2  3  2 Х3 Входной Скры ты й Вы ходной Характеристики нейронов В каждом нейроне активационная функция имеет вид F(Sum) = 1/[1+e – *Sum], Sum =  xi * wi, i=1 где  - параметр функции активации, ответственный за её крутизну; xi – значение на i-м входе; wi – вес i-го входа; n – количество входов нейрона. Хромосома Хромосома в нашем случае будет представлять массив из 11 действительных чисел, по четыре на каждый скрытый нейрон и три для выходного нейрона, которые представляют собой веса соответствующих входов нейронов и параметры их функций активации: W11 W12 W13 1W21W22W23  2V31V32  3 Для элементов хромосомы – генов – введем ограничения, обусловленные природой нейросетей: -1 wij1 и  i>0. Целевая ф ункция Целевая функция может представлять собой: 1. максимальное для набора примеров отклонение от эталонного значения (значение 25). 2. максимальное для набора примеров суммарное отклонение от эталонного значения(25+11+…+16) Чем меньше значение целевой функции, тем сеть лучше обучена. Здесь уже можно задать критерий останова генетического алгоритма. Можно указать число поколений, а можно задать условие на значение целевой функции. Обучающая вы борка X1 X2 … X10 Out Yрас ч  10,1 12,3 … 17,2 135 110 25 9,6 11,5 … 16,8 161 150 11 7,9 13,1 .. 15,2 178 162 16 Исходная популяция (Не менее 100 хромосом) 1.W11 W12 W13 1W21W22W23  2V31V32  3  25% 2. W11 W12 W13 1W21W22W23  2V31V32  3  11% … 100. W11 W12 W13 1W21W22W23  2V31V32  3  4,5% Скрещивание Однот очечны й кроссинговер Родит ели W11 W12 W13 1W21 W22W23  2V31V32  3  11% W11 W12 W13 1W21 W22W23  2V31V32  3  3% W11 W12 W13 1W21 W11 W12 W13 1W21 Пот омки W22W23  2V31V32  3 W22W23  2V31V32  3  1%  7,2 % Мут ация В качестве оператора мутации будем использовать случайное изменение значений весов и параметра функции активации для каждого нейрона на случайную величину. Вероятность мутации 0,01. Причем одновременно будет изменяться параметр функции только для одного нейрона, и для каждого будет изменяться один из входных весов. Редукция Удаление хромосом с большими значениями суммарного отклонения от эталонных значений. Например, мутация может быть следующей: значение 2 увеличивается на 0,1; значение w11 уменьшается на 0,05; w21– уменьшается на 0,01; w31– увеличивается на0,05. Дополнит ельная литерат ура • • Рутковская Д. И др.Нейронные сети, генетические алгоритмы и нечеткие системы:Пер. с польск. И.Д. Рудинского. М.:Горячая линия-Телеком, 2004.-452с. Корнеев В.В. и др. Базы данных. Интеллектуальная обработка информации . – М.:”Нолидж”, 2000. – 352 с www/ Know ledge. ru Принципы обучения нейронной сет и с помощью генет ических алгорит мов Wij Vij * Х1  Y 1 Х2  3  2 Х3 Входной Скры ты й Вы ходной Характеристики нейронов В каждом нейроне активационная функция имеет вид F(Sum) = 1/[1+e – *Sum], Sum =  xi * wi, i=1 где  - параметр функции активации, ответственный за её крутизну; xi – значение на i-м входе; wi – вес i-го входа; n – количество входов нейрона. Хромосома Хромосома в нашем случае будет представлять массив из 11 действительных чисел, по четыре на каждый скрытый нейрон и три для выходного нейрона, которые представляют собой веса соответствующих входов нейронов и параметры их функций активации: W11 W12 W13 1W21W22W23  2V31V32  3 Для элементов хромосомы – генов – введем ограничения, обусловленные природой нейросетей: -1 wij1 и  i>0. Целевая ф ункция Целевая функция может представлять собой: 1. максимальное для набора примеров отклонение от эталонного значения (значение 25). 2. максимальное для набора примеров суммарное отклонение от эталонного значения(25+11+…+16) Чем меньше значение целевой функции, тем сеть лучше обучена. Здесь уже можно задать критерий останова генетического алгоритма. Можно указать число поколений, а можно задать условие на значение целевой функции. Обучающая вы борка X1 X2 … X10 Out Yрас ч  10,1 12,3 … 17,2 135 110 25 9,6 11,5 … 16,8 161 150 11 7,9 13,1 .. 15,2 178 162 16 Исходная популяция (Не менее 100 хромосом) 1.W11 W12 W13 1W21W22W23  2V31V32  3  25% 2. W11 W12 W13 1W21W22W23  2V31V32  3  11% … 100. W11 W12 W13 1W21W22W23  2V31V32  3  4,5% Скрещивание Однот очечны й кроссинговер Родит ели W11 W12 W13 1W21 W22W23  2V31V32  3  11% W11 W12 W13 1W21 W22W23  2V31V32  3  3% W11 W12 W13 1W21 W11 W12 W13 1W21 Пот омки W22W23  2V31V32  3 W22W23  2V31V32  3  1%  7,2 % Мут ация В качестве оператора мутации будем использовать случайное изменение значений весов и параметра функции активации для каждого нейрона на случайную величину. Вероятность мутации 0,01. Причем одновременно будет изменяться параметр функции только для одного нейрона, и для каждого будет изменяться один из входных весов. Редукция Удаление хромосом с большими значениями суммарного отклонения от эталонных значений. Например, мутация может быть следующей: значение 2 увеличивается на 0,1; значение w11 уменьшается на 0,05; w21– уменьшается на 0,01; w31– увеличивается на0,05. Генетическое программирование Идею генетического программирования (ГП) - впервые предложил Коза в 1992 году, опираясь на концепцию генетических алгоритмов Хромосомы в ГП В ГП хромосомами являются программы. Программы представлены как деревья с функциональными (промежуточные) и терминальными (конечные) элементами. Терминальными элементами являются константы, действия и функции без аргументов, функциональными - функции, использующие аргументы. Пример Для примера можно рассмотреть функцию 2+x*4/7, представленную на рисунке 1. Терминальные элементы T = {2,x,4,7}, функциональные F = {+,*,/}. Древовидное представление функции 2+x*4/7 Скрещивание Разрешение конфликтной ситуации Мутация Литература 1. Рутковская Д. и др. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И.Д. Рудницкого М.: Горячая линия- Телеком, 2004.-452с.