Эволюционные алгоритмы

Генетические алгоритмы {genetic algorithms) совместно с эво­люционной стратегией и эволюционным программированием пред­ставляют три главных направления развития так называемого эволю­ционного моделирования (simulated evolution).

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

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

учеными вначале в рамках теории конечных автоматов и обобщен­ный позднее для приложений к проблемам оптимизации [13]. Оба на­правления возникли в шестидесятых годах XX века.

Сконцентрируем внимание на важнейших сходствах и различи­ях между эволюционными стратегиями и генетическими алгоритмами [33]. Очевидно, что главное сходство заключается в том, что оба ме­тода используют популяции потенциальных решений и реализуют принцип селекции и преобразования наиболее приспособленных осо­бей. Однако обсуждаемые подходы сильно отличаются друг от друга. Первое различие заключается в способе представления особей. Эво­люционные стратегии оперируют векторами действительных чисел, тогда как генетические алгоритмы - двоичными векторами.

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

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

Глава 4. Геи

алгоритмы

4.10. Эволюционные алгоритмы

кие операторы скрещивания и -мутации применяются к особям (выби­раемым с вероятностью скрещивания) и к генам (выбираемым с ве­роятностью мутации).

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

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

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

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

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

ра повторяется так долго, пока не будет найдено искомое решение либо не будет исчерпан лимит машинного времени.

Эволюционное программирование применяется для оптимиза­ции функционирования нейронных сетей. Также как и другие эволю­ционные методы, оно не требует градиентной информации и поэтому может использоваться для решения задач, в которых эта информация недоступна, либо для ее получения требуются значительные объемы вычислений. Одними из первых приложений эволюционного програм­мирования считаются задачи теории искусственного интеллекта, а са­мые ранние работы касались теории конечных автоматов [13].

Наблюдается большое сходство между эволюционными стра­тегиями и эволюционными программированием в их приложениях к задачам оптимизации непрерывных функций с действительными значениями. Некоторые исследователи утверждают, что эти процеду­ры, в сущности, одинаковы, хотя они и развивались независимо друг от друга [13]. Действительно, оба метода похожи на генетические ал­горитмы. Принципиальное различие между ними заключается в том, что эволюционное программирование не связано с конкретной фор­мой представления особей, поскольку оператор мутации не требует применения какого-либо специального способа кодирования.

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

Все три представленных метода, т.е. генетические алгоритмы, эволюционные стратегии и эволюционное программирование объе­диняются под общим названием эволюционные алгоритмы (evolution­ary algorithms). Также применяется термин эволюционные методы (evolutionary methods).

Эволюционными алгоритмами называются и другие методы, реализующие эволюционный подход, в частности, генетическое про­граммирование (genetic programming) [29], представляющее собой модификацию генетического алгоритма с учетом возможностей ком­пьютерных программ. При использовании этого метода популяция со­стоит из закодированных соответствующим образом программ, кото­рые подвергаются воздействию генетических операторов скрещива­ния и мутации, для нахождения оптимального решения, которым счи­тается программа, наилучшим образом решающая поставленную за­дачу. Программы оцениваются относительно определенной специ­альным образом функции приспособленности. Интересной представ­ляется модификация эволюционных алгоритмов для решения опти­мизационных задач методом так называемой мягкой селекции, кото­рая предложена Р. Галаром [14].

Для обозначения разнообразных алгоритмов, основанных на эволюционном подходе, также применяется понятие эволюционных

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

. Эволюционные алгоритмы

программ {evolution programs) [33]. Этот термин объединяет как гене­тические алгоритмы, эволюционные стратегии и эволюционное про­граммирование, так и генетическое программирование а также дру­гие аналогичные методы.

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

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

Согласно 3. Михалевичу [33], эволюционная программа - это вероятностный алгоритм, применяемый на /с-й итерации к популяции

Каждая особь представляет потенциальное решение задачи которое в произвольной эволюционной программе может отображать­ся некоторой (в том числе и достаточно сложной) структурой данных и. Любое решение х* оценивается по значению его «приспособленно­сти». Далее в процессе селекции на (/с+1)-й итерации из наиболее приспособленных особей формируется очередная популяция. Неко­торые особи этой новой популяции трансформируются с помощью «генетических операторов», что позволяет получать новые решения Существуют преобразования ц, (типа мутации), которые изменяют конкретные хромосомы (_w: D -» D), а также трансформации более вы­сокого порядка у, (типа скрещивания), создающие новые особи путем комбинирования фрагментов нескольких (двух или более) хромосом т.е. yr. D х... х D -> D. От эволюционной программы ожидается, что после смены некоторого количества поколений наилучшая особь бу­дет представлять решение, близкое к оптимальному. Структура эво­люционной программы может быть представлена в виде псевдокода [33] так, как это изображено на рис. 4.65 (рекомендуется сравнить ее с рис. 4.3).

_п^{Рассмотрим о6обш}.^енный пример эволюционной программы [33]. Допустим, что ищется граф, который удовлетворяет определен-

ным ограничениям (например, производится поиск топологии комму­никационной сети, оптимальной по конкретным критериям, например, по стоимости передачи и т.п.). Каждая особь в эволюционной про­грамме представляет одно из потенциальных решений, т.е. в данном случае некоторый граф. Исходная популяция графов Р(0), формиру­емая случайным образом либо создаваемая при реализации како­го-либо эвристического процесса, считается отправной точкой (к = 0) эволюционной программы. Функция приспособленности, которая обычно задается, связана с системой ограничений решаемой задачи. Эта функция определяет «приспособленность» каждого графа путем выявления «лучших» и «худших» особей. Можно предложить не­сколько различных операторов мутации, предназначенных для транс­формации отдельных графов, и несколько операторов скрещивания, которые будут создавать новый граф в результате рекомбинации структур двух или более графов. Очень часто такие операторы обус­ловливаются характером решаемой задачи. Например, если ищется граф типа «дерево», то можно предложить оператор мутации, кото­рый удаляет ветвь из одного графа и добавляет новую ветвь, объеди­няющую два отдельных подграфа. Другие возможности заключают­ся в проектировании мутации независимо от семантики задачи, но с включением в функцию приспособленности дополнительных огра­ничений - «штрафов» для тех графов, которые не являются деревья­ми.

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

Классический генетический алгоритм, который оперирует дво­ичными последовательностями, требует представить решаемую за­дачу в строго определенном виде (соответствие между потенциаль-

procedure эволюционная_программа begin k = 0

инициализация популяции Р(к) оценивание приспособленности особей из Р(к) while (not условие завершения) do begin к = к+1

селекция особей из Р(к - 1) в Р(к) применение генетических операторов оценивание приспособленности особей из Р(к) end end

ie эволюционной программы в виде псевдокода.

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

4.11. Приложения эволюционных алгоритмов

Решаема проблема (з

та)

т

Решаема проблема (з

Модификация задачи к виду, соответствующе классическому генети­ческому алгоритму

Модификация классическог генетического алгоритма

к виду, соответствующему решаемой задаче

HZ

ZL.

Модифицированн задача

Эволюционная программа

етического алгоритма для решения ифицированной задачи

Применение ионной програм

решения задачи

Наилучш решение за

Рис.4.66. Решение задачи с помощью классического генетического алгоритма.

Рис. 4.67. Решение задачи с помощью эволюционного алгоритма (эволюци­онной программы).

ными решениями и двоичными кодами, декодирование и т.п.). Сде­лать это не всегда просто.

Эволюционные программы могут оставить постановку задачи в неизменном виде за счет модификации хромосом, представляющих потенциальные решения (с использованием «естественных» структур данных), и применения соответствующих «генетических» операторов

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

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

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

В июле 1996 г. состоялась первая Всепольская конференция по эволюционным алгоритмам, организованная Институтом основ элек­троники Варшавского политехнического университета и Клубом эво­люционных алгоритмов. На этой конференции обсуждалась класси­фикация эволюционных алгоритмов, согласно которой в их состав входят генетические алгоритмы, эволюционные стратегии, эволюци­онное и генетическое программирование, а также другие технологии эволюционных вычислений, причем именно последние имеют наи­больший удельный вес (около 95 %). Это свидетельствует о появле­нии множества новых методов, основанных на эволюционном моде­лировании, но использующих базовые технологии - главным образом классический генетический алгоритм, эволюционные стратегии и эво­люционное программирование.

Упомянутая конференция также позволила выработать ряд ре­шений по упорядочению терминологии, применяемой для описания эволюционных алгоритмов. Они касались перевода таких базовых по­нятий, как fitness function, crossover, steady-state и многих других, ко­торые различные авторы переводили с английского языка по собст­венному усмотрению.

Терминология, применяемая в настоящем разделе, соответст­вует рекомендациям этой конференции.

Дата добавления: 2015-06-04