|
Основные этапы работы генетического алгоритмаПредставьте, что вы собрались в поход и думаете, чтобы взять с собой в рюкзаке из некоторого набора предметов? Причем, у каждого предмета есть свой вес и своя ценность. Желательно подобрать предметы так, чтобы они умещались в рюкзак и при этом имели бы максимальную суммарную ценность.
Или, такая задачка. Необходимо составить график дежурств медперсонала, чтобы каждый из врачей дежурил два дня в неделю, но не более пяти раз в месяц и чтобы интервал между соседними дежурствами был, как минимум два дня. Кроме того, здесь могут быть отдельные пожелания врачей о времени проведения дежурств.
Наконец, бывают и еще более сложные задачи. Например, нужно создать алгоритм, который бы управлял тележкой так, чтобы подвижный шест не падал как можно дольше:
Что объединяет все эти задачи? Они имеют множество критериев и трудно реализуемые чисто математически. Для решения таких задач часто применяют эвристические или эволюционные алгоритмы, ярким представителем которых является генетический алгоритм. Идея, положенная в основу этого алгоритма, - имитация эволюционного процесса. Но как эволюция может помочь решать подобные задачи? Все дело в правильной формализации задачи. Чтобы все это лучше понять, давайте вначале рассмотрим простой, классический пример, известный под названием «задача OneMax». Задача OneMaxВ этой задаче у нас имеется список определенной длины, состоящий из нулей и единиц:
Наша цель – найти решение, которое бы давало максимальную сумму цифр этого списка:
Здесь N – длина списка. Очевидно, это список, состоящий из всех единиц:
Конечно, мы легко можем решить эту задачу без применения ГА, но на ее примере хорошо показать принцип его работы. ПопуляцияИтак, все начинается с формирования популяции – множества особей одного вида. Что из себя представляют особи в задаче OneMax? Это обычные списки из нулей и единиц:
И это типовое представление особей. Каждую задачу для генетического алгоритма стараются формализовать так, чтобы особи были представлены списком целых или вещественных чисел. В этом случае мы получаем естественную биологическую интерпретацию этих списков как хромосом, состоящих из генов (отдельных элементов):
Следующий важный вопрос, как сформировать начальную популяцию индивидуумов? То есть, как подобрать начальные значения генов? Часто для этого используют датчик случайных чисел и просто записывают то число, которое получилось на выходе этого датчика. В результате, получим множество самых разных особей, что очень хорошо для дальнейшего процесса эволюционной адаптации всей популяции. Функция приспособленности (целевая функция)
Как мы знаем, в процессе эволюционного отбора в популяции, как правило, остаются наиболее приспособленные особи. И нам нужно уметь определять эту степень приспособленности, чтобы имитировать процесс эволюции. Но что определяет приспособленность в задачах генетического алгоритма? В природе – это фактор выживаемости, а что у нас? У нас – это получение лучшего решения. То есть, те особи, которые представляют лучшее решение поставленной задачи, считаются более приспособленными. А чтобы оценивать качество решения для каждого конкретного индивидуума, необходимо задать функцию приспособленности (или, как еще говорят, - целевую функцию):
Например, в задаче OneMax, она суммирует все числа в генах и имеет следующий вид:
Чем больше значение этой суммы, тем больше единиц в хромосоме и тем лучшее решение представляет индивид. Конечно, для разных задач используется своя функция приспособленности, и ее конкретный математический вид определяется разработчиком ГА, исходя из поставленной задачи оптимизации. Имитация эволюционного процессаПосле того, как у нас сформирована популяция и определена функция, дающая оценку приспособленности каждой конкретной особи, мы готовы к имитации эволюционного процесса. То есть, будем воспроизводить изменение популяции от поколения к поколению в надежде получать все более и более приспособленных особей, а значит идти по пути улучшения решения поставленной задачи. Согласно Чарльзу Дарвину движущая сила эволюции определяется следующими тремя процессами:
В итоге, схему ГА можно представить в следующем виде:
ОтборОтбор – это первое действие, выполняемое в ГА при имитации эволюционного процесса. Цель этого оператора – с одной стороны оставить в популяции наиболее приспособленных особей, но с другой – сохранить популяционное разнообразие. Например, если оставлять только наиболее приспособленных, то можно потерять важные фрагменты хромосом у менее приспособленных особей. Возможно, оптимальное решение достигается скрещиванием одного из наиболее приспособленного родителя с другим – наименее приспособленным. Если же на этапе отбора второй родитель окажется утерянным, то оптимальное решение, возможно, будет достигаться за большее число шагов работы ГА. А может быть даже потеряется навсегда. Чтобы уменьшить вероятность такого исхода в следующем поколении следует оставлять не только самых лучших, но и давать возможность менее конкурентным оставаться в популяции. Вообще существует множество способов реализации механизма отбора. В рамках задачи OneMax мы воспользуемся идеей турнирного отбора, который довольно часто используется на практике. Вначале во всей популяции случайным образом отбирается n индивидуумов (допустим три), а затем, среди них выбирается наиболее приспособленный:
Победитель проходит отбор и будет использован как родитель в операции скрещивания. Соответственно, этот турнирный отбор повторяется с исходной популяцией до тех пор, пока не будет сформирован новый список особей того же числа, что и исходная популяция. Позже, мы с вами подробнее рассмотрим и другие способы отбора индивидуумов из популяции, а пока перейдем к следующему этапу – скрещивание. СкрещиваниеЭтап скрещивания в научной литературе называют кроссинговером или кроссовером (от англ. crossing – скрещивание). На этом этапе происходит обмен данными между частями хромосом родителей. Обычно в популяции перебирают пары родителей, и фрагменты их хромосом перемешивают, получая новый набор генов в хромосомах их потомков:
В данном случае представлена схема одноточечного скрещивания, когда случайным образом выбирается точка разреза хромосом у родителей, а затем, осуществляется их обмен. Так появляется два потомка. Эта операция выполняется с некоторой (высокой) вероятностью. При этом родители, давшие потомство, как правило, не переходят в следующее поколение, а не давшие – сохраняются. В результате, размер популяции после операции скрещивания не меняется. Существуют и другие виды скрещивания, о них мы также подробнее будем говорить на следующих занятиях. МутацияПоследний оператор имитации процесса эволюции – это мутация. Она применяется к полученной популяции и случайным образом с малой вероятностью меняет значения отдельных генов. В самом простом варианте двоичного кодирования генов, мутация выполняет инвертирование бита:
Этот механизм позволяет расширять область поиска решения задачи и сохранять разнообразие популяции. Возможно, благодаря полезной мутации, особь приобретет новое свойство и станет более конкурентно-способной в своей популяции. В дальнейшем у нее есть все шансы дать потомство и закрепить полезный признак. Так, через мутацию, происходит улучшение решения. Конечно, может произойти и обратный эффект – ухудшение приспособленности индивидуума. Но тогда, он не сможет конкурировать с более приспособленными особями и вскоре будет отсеян в процессе отбора. Мутации в генетических алгоритмах также имеют множество реализаций и мы о них позже еще будем говорить. А на следующем занятии применим текущие знания для реализации задачи OneMax с использованием языка Python и воочию увидим, как работает ГА. Видео по теме |
