Генетические алгоритмы и традиционные методы оптимизации

Лабораторное занятие №3

Введение

Генетические алгоритмы возникли в результате на­блюдения и попыток копирования естественных процессов, происхо­дящих в мире живых организмов, в частности, эволюции и связанной с ней селекции (естественного отбора) популяций живых существ. Ко­нечно, при подобном сопоставлении следует обращать внимание на принципиально различ­ную длительность протекания упоминаемых естественных процес­сов, т.е. на чрезвычайно быструю обработку информации в нервной системе и очень медленный процесс естественной эволюции. Однако при компьютерном моделировании эти различия оказываются несу­щественными.

Идею генетических алгоритмов высказал Дж. Холланд в конце шестидесятых - начале семидесятых годов XX века. Он заин­тересовался свойствами процессов естественной эволюции (в том числе фактом, что эволюционируют хромосомы, а не сами живые су­щества). Холланд был уверен в возможности составить и реализо­вать в виде компьютерной программы алгоритм, который будет ре­шать сложные задачи так, как это делает природа - путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими по­следовательностями двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные про­цессы в поколениях таких хромосом. В них были реализованы меха­низмы селекции и репродукции, аналогичные применяемым при есте­ственной эволюции. Так же, как и в природе, генетические алгоритмы осуществляли поиск «хороших» хромосом без использования ка­кой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособ­ленность. Механизм селекции заключается в выборе хромосом с на­ивысшей оценкой (т.е. наиболее приспособленных), которые репроду­цируют чаще, чем особи с более низкой оценкой (хуже приспособлен­ные). Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация - это процесс, в результате которого возникают новые комбинации генов. Для этого используются две операции: скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбини­рования генетического материала пары родителей, а также мутация, которая может вызывать изменения в отдельных хромосомах.

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

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

Теоретическая часть

Генетические алгоритмы и традиционные методы оптимизации

Генетический алгоритм представляет собой метод, отражаю­щий естественную эволюцию методов решения проблем, и в первую очередь задач оптимизации. Генетические алгоритмы - это процеду­ры поиска, основанные на механизмах естественного отбора и насле­дования. В них используется эволюционный принцип выживания наи­более приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами.

Свойства генетических алгоритмов:

1) обрабатывают не значения параметров самой задачи, а их закодированную форму;

2) осуществляют поиск решения исходя не из единственной точки, а из их некоторой популяции;

3) используют только целевую функцию, а не ее производные либо иную дополнительную информацию,

4) применяют вероятностные, а не детерминированные пра­вила выбора.

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

Основные понятия генетических алгоритмов

При описании генетических алгоритмов используются опреде­ления, заимствованные из генетики.

Популяция - это конечное множество особей.

Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точка­ми в пространстве поиска (search points). В некоторых источниках осо­би называются организмами.

Хромосомы (другие названия - цепочки или кодовые последо­вательности) - это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.

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

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

Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи.

Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функ­цией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволя­ет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наиболь­шие значения функции приспособленности) в соответствии с эволюци­онным принципом выживания «сильнейших» (лучше всего приспосо­бившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функ­ционирование генетических алгоритмов и должна иметь точное и кор­ректное определение. В задачах оптимизации функция приспособлен­ности, как правило, оптимизируется. В теории уп­равления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой ите­рации генетического алгоритма приспособленность каждой особи дан­ной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляю­щих множество потенциальных решений проблемы, например, задачи оптимизации.

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

Пример 1.

Рассмотрим функцию

(1)

и допустим, что x принимает целые значения из интервала от 0 до 15.

Задача оптимизации этой функции заключается в перемещении по пространству, состоящему из 16 точек со значениями 0, 1,..., 15 для обнаружения той точки, в которой функция принимает максимальное (или минимальное) значение.

В этом случае в качестве параметра задачи выступает пере­менная х. Множество {0, 1,..., 15} составляет пространство поиска и одновременно - множество потенциальных решений задачи. Каждое из 16 чисел, принадлежащих к этому множеству, называется точкой пространства поиска, решением, значением параметра, феноти­пом. Следует отметить, что решение, оптимизирующее функцию, на­зывается наилучшим или оптимальным решением. Значения пара­метра x от 0 до 15 можно закодировать следующим образом:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

Это широко известный способ двоичного кодирования, связанный с записью десятичных цифр в двоичной системе. Представленные ко­довые последовательности также называются цепями или хромосо­мами. В рассматриваемом примере они выступают и в роли геноти­пов. Каждая из хромосом состоит из 4 генов (иначе можно сказать, что двоичные последовательности состоят из 4 битов). Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1. Популяция состоит из особей, выбираемых среди этих 16 хромосом. Примером популяции с численностью, рав­ной 6, может быть, например, множество хромосом {0010, 0101, 0111, 1001, 1100, 1110}, представляющих собой закодированную форму следующих фенотипов: { 2, 5, 7, 9, 12, 14}. Функция приспособленнос­ти в этом примере задается выражением (1). Приспособленность отдельных хромосом в популяции определяется значением этой функции для значений x, соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным генотипам.