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

850
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (2 оценок, среднее: 5,00 из 5)
Загрузка...
  • Название: Генетический алгоритм (Genetic Algorithm — GA);
  • Применение: Поиск глобального экстремума;
  • Сложность: Очень сложный;
  • Входные параметры: целевая функция (фитнесс-функция), заданные ограничения;
  • Результат: Эвристический. Глобальный максимум или минимум

Краткая предыстория:

Закономерности сущестования и развития живых организмов интересовали ученых и исследователей давно. Но основной неразрешимой проблемой была научная модель описывающая динамическую и сложную природу изменчивости различных живых видов. Пока в начале 19 века (1809) Ж.Б.Ламарк не предложил модель эволюции, как процесс возникновения новых форм путем постепенного изменения старых. Он считал, что идет постепенное усложнение биологических организмов под воздействием окружающей среды — происходит своеобразное «упражнение» органов и внутреннее стремление к прогрессу.

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

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

Еще было много научных работ, исследований, открытий (В. Иогансен, Г. Фриз, Г. Харди, В. Вайнберг, Т. Морган и др.)  в этой научной области, которые продолжаются и по сегодняшний день, но к сожалению выходят за рамки заявленной тематики.

Из вышеизложенного, необходимо резюмировать следующие основные идеи, которые понадобятся в дальнейшем. Условно обобщенная схема развития живых организмов, основана на:

  1. Наследовании при котором происходит передача части родительских признаков своим потомкам (механизм наследования);
  2. Отборе наиболее приспособленных особей к среде (механизм селекции), которые обладают элементами, позволящие выжить в окружающей среде. В противном случае, особи погибают;
  3. Формировании нового поколения (механизм скрещивания). При этом могут происходить случайные изменчивости (механизм мутации) наследуемых признаков.

Пример из жизни:

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

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

Этот механизм поиска не даст 100 % точного результата, потому что в нем присутствует случайная (стохастическая) и комбинаторная составляющая. Поэтому ответ будет приблизительный, в таких случаях, говорят эвристический.  Обобщим рассмотренный пример на реальные задачи, которые могут встретиться на практике. Существует большая область таких задач, которые требуют сложных вычислений на основе полного перебора, как, задача коммивояжёра (поиск кратчайшего пути через города, при условии не посещать их дважды). Такие задачи еще называют NP — полные.

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

Для дальнейших рассуждений необходимо раскрыть минимальный понятийных аппарат для упрощения дальнейших рассуждений.

Определения:

Генетические алгоритмы (далее по тексту ГА) возникли в результате наблюдения и попыток копирования естественных процессов, происходящих в живой природе. Впервые, идею этих алгоритмов высказал Дж.Холланд в 1960-1970 годах. Он был уверен в том, что можно реализовать программный алгоритм, который будет решать сложные задачи так как их решает природа — путем эволюции. Таким образом, применяется ряд терминов, заимствованных из генетики, прежде всего гены и хромосомы, а так же популяция, особь, аллель, генотип, фенотип.

Данные определения целесообразно рассмотреть на конкретном примере. Например, нужно найти глобальный максимум (экстремум) функции: f(x) = 2x2+1, где x ограничена на промежутке [0; 18]. Т.е. множество {0, 1, …, 18} составляет пространство поиска, одновременно — множество потенциальных решений. Каждое из потенциальных решений называется — точкой пространства поискафенотипом.

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

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

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

Аллель — это значение конкретного гена ( в данном случае 1 или 0 ), так же определяемое как значение свойства или вариант свойства, а позиция этого значения назвается локусом. Но на каждой итерации ГА используют урезанное пространство решений для эффективной работы алгоритма и называют популяцией.

Популяция — это выборка потенциальных решений из пространства поиска, например, {0, 1, 2, 3, 4, 5, 6, 7, 8}.

Самым важным понятием в ГА является так называемая функция приспособленности (fitness function) в данном примере она задается выражением — f(x) = 2x2+1, которая на языке оптимизации называется целевой.

Функция приспособленности — функция, которая определяет меру приспособленности данной особи в популяции. От выбора этой функции и ограничений допустимых решений (области определения) зависит правильность построения ГА.

ГА как и любой алгоритм состоит из строгой последовательности операций или операторов. Выделяют следующие основные операторы ГА (скрещивание, мутация, селекция). Данные операторы составляют основу алгоритма и обладают многообразными вариациями. В соотвествии с этими вариациями определяют разные типы ГА такие как канонический (классический), генитор, СНС (Cross-population selection, Heterogeneous recombination and Cataclysmic mutation) и т.д. В данной случае будет рассмотрен простейший вариант ГА — канонический.

Основные операторы:

Скрещивание (рекомбинация) — последовательность операций при которых созданные потомки должны наследовать генную информацию от обоих родителей. Различают дискретную рекомбинацию (применяется к вещественным переменным) и кроссинговер (применяется к закодированным = бинарным данным).

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

Селекция — представляет собой форму искусственного отбора наилучших решений (особей), которые составят популяцию для скрещивания. 

Лингвистическое описание:

Канонический (классический) алгоритм состоит из следующих последовательных этапов:

  1. Инициализация, или выбор исходной популяции решений. На начальном этапе производится случайный выбор потенциальных решений, принадлежащих области определения функции приспособленности. Слишком большое количество может замедлить работу алгоритма, поэтому за начальную выборку (популяцию) принимается четное количество (для обеспечения скрещивания) не превышающее 15 % ( условная величина, которая часто принимается за начальную популяцию ) всей области.
  2. Оценивание приспособленности решений в популяции.  Все потенциальные решения подставляются в функцию приспособленности, которая и определяет их «качество». Предполагается, что функция приспособленности всегда принимает неотрицательные значения, и кроме того, что для решения оптимизационной задачи требуется максимизировать эту функцию (задачу минимизации можно свести к задаче максимизации).
  3. Проверка условия остановки алгоритма. Определение условия остановки ГА зависит от конкретного применения: если в оптимизационных задачах известно максимальное (минимальное значение) — остановка происходит после достижения заданного результата с заданной точностью; если длительное выполнение не приводит к улучшению достигнутого результата; если время выполнения или количество итераций исчерпано. В противном случае, на следующем шаге выполняется селекция.
  4. Селекция «лучших» решений заключается в выборе (рассчитанных на втором шаге значений) родителей для создания будущего «потомства». Существуют различные методы селекции наиболее популярным считается метод рулетки. Рассмотрим этот метод поподробней. 

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

Сектор = (значение функции приспособленности решения / сумма всех решений функции приспособленности) * 100 %;

Например, проведем селекцию следующих значений {1,2,3,4} с функцией приспособленности f(x) = 2x2+1 получим следующие потенциальные решения {3, 9, 19, 33}. Выберем родителей для скрещивания: для первого решения = 3 / (3+9+19+33) =0,047 * 100 % = 5 % (округляем в большую сторону), остальные сектора рассчитаем таким же образом: 14 % (9), 30 %(19),  51%(33). Вполне возможно, что может получится так — выбранная особь (решение) составит брачную пару с собой. Нанесем на рулетку данные значения:

Теперь необходимо разыграть случайные значения четыре раза (для выбора пар для скрещивания) от 0 до 100 %.

   

5. Применение генетических операторов. Используются два оператора: скрещивания и мутации. Необходимо отметить, что оператор мутации играет второстепенную роль по сравнению с скрещиванием. Т.е. скрещивание происходит всегда, а мутация относительно редкое явление. Вероятность мутации достигает 10 %. Может происходить, как до скрещивания так и после.  

Скрещивание выбирается метод кроссинговера. Родители должны быть представлены в закодированном виде (например, бинарные данные 1 = 0001 ). Разыгрывается случайным образом позиция «разрыва» (точке где произойдет обмен генами). Например, рассмотрим брачную пару ( 1010110011 и 0100011101 )

Мутация. Вероятность возникновения, как правило, принимается  — от 1 до 10 % для каждого полученного потомка.  Разыграем случайную величину и если она попадает в этот интервал, то производим инверсию одного гена т.е. если было 0 стало 1 и обратно. При этом разыгрывается так же позиция инверсии, если всего генов 5, то производится разыгрывание значений от 1 до 5 и т.д.

    

6. Формирование новой популяции. Полученная популяция после скрещивания и маленькой вероятности мутации снова проверяется на приспособленность через целевую функцию (чем больше значение, тем лучше «приспособленность» решений) после этого проверяется условие остановки алгоритма то есть возвращение к шагу 2. Количество членов популяции должно сохраниться, при этом замениться полностью на новую популяцию.

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

В целом схема работы алгоритма представлена ниже:

Общие рекомендации.

  • Вероятность кроссинговера обычно выбирается достаточной высокой 80–95 % (в некоторых задачах наилучший результат достигается при кроссинговере с вероятностью 60 %);
  • Вероятность мутации должна быть мала: 0,5–1 %;
  • Оптимальный размер популяции — 20–30 особей (однако в некоторых задачах требуется 50–100 особей).

Исследования показывают, что оптимальный размер популяции зависит от размера кодовых строк (хромосом). Для алгоритма с 32-битовыми хромосомами размер популяции будет больше, чем для алгоритма с 16-битовыми хромосомами. В основном используют рулеточный отбор, но и иногда лучше применить отбор с усечением. Существует много других методов, меняющих параметры отбора в течение всей работы ГА. Элитизм применяется, если не используются другие методы, сохраняющие найденное хорошее решение. Выбор способа кодирования обусловлен поставленной задачей и размером объекта поиска. Операторы жизненного цикла (кроссинговера и мутации) определяются выбранным кодированием.

Программная разработка.

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

Для данной реализации подберем фитесс-функцию в виде:

Построим графическую зависимость на интервале [2,7]. Как видно, существует один локальных максимума (при x=4) и один глобальный (при x=7).

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

Инициализация, или выбор исходной популяции решений. Формируем пробные решения (случайным образом), зная область допустимых значений (7 строка).

Оценивание приспособленности решений в популяции. На каждом поколении (итерации) решения пропускаются через целевую функцию. Максимальное значение целевой функции придает наибольшую приспособленность (6 строка).

Проверка условия остановки алгоритма. Реализуем самый простой случай остановки алгоритма — исчерпание всего количества отведенных поколений для выполнения. Забегая вперед — сформируем метод для запуска всей процедуры генетического перебора. Именно на 3 строке происходит проверка условия остановки алгоритма.

Селекция родителей для формирования нового поколения. Для этих целей существует множество методов (элитарный, с отсечением и т.д.) наиболее распространенный «метод рулетки», который рассматривался выше. В первую очередь, вычисляется сектора рулетки строка 11. Затем крутим рулетку, эта процедура реализована в строках (14-24). На строках 25-26 записываем предварительную популяцию родителей, которые составят брачные пары. 

Применение генетических операторов (мутация). Производится случайная инверсия значения гена (закодированного в двоичной форме решения). Таким образом, что выбирается случайная позиция гена и производится замена на 1 и обратно. Обратите внимание, что вероятность возникновения мутации крайне невилика и составляет меньше 10 %.

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

Формирование новой популяции. После применения соотвествующих операторов, формируется новая популяция. 

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

Вспомогательные методы кодирования-декодирования двоичной формы представления текущих решений. Метод «decode» производит перевод числа из десятичной формы представления в двоичную. Соотвественно, «code» — кодирует двоичную форму представления в десятичную. Метод «calculate» вычисляет значение функции принадлежности.

Выводы:

  • Не требуется модифицировать функцию (дифференцировать и т.д.)
  • Пригодны для решения крупномасштабных задач оптимизации
  •  Относительно просты в реализации
  • Могут применяться в задачах, с меняющимися условиями
  • Непривычная терминология, большое время вычисления
  • Подходит не для всех функций (ф-я Растригина, изолированные функции и т.д.)
  •  Не для всех задач можно подобрать оптимальное кодирование
  • Не может использоваться для точных решений

Полезные материалы:

Генетический алгоритм. Размещение графа на линейке

Генетический алгоритм (решение уравнений)

 

Поделиться

Отправить ответ

avatar
wpDiscuz