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

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

Основные определения и свойства

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

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

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

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

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

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

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

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

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

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

Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации . Основным параметром oпepaтоpa мутации также является вероятность мутации.

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

Таким образом, можно перечислить основные понятия и термины, ис­пользуемые в области генетических алгоритмов:

    генотип и фенотип;

    особь и качество особи;

    популяция и размер популяции;

    поколение;

    родители и потомки.

К характеристикам генетического алгоритма относятся:

    размер популяции;

    оператор скрещивания и вероятность его использования;

    оператор мутации и вероятность мутации;

    оператор отбора;

    оператор редукции;

    критерий останова.

Операторы отбора, скрещивания, мутации и редукции называют еще генетическими операторами.

Критерием останова работы генетического алгоритма может быть одно из трех событий:

    Сформировано заданное пользователем число поколений.

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

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

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

Последовательность работы генетического алгоритма

Рассмотрим теперь непосредственно работу генетического алгоритма. Общий алгоритм его работы выглядит следующим образом:

    Создание исходной популяции

    Выбор родителей для процесса размножения (работает оператор отбора)

    Создание потомков выбранных пар родителей (работает оператор скрещивания)

    Мутация новых особей (работает оператор мутации)

    Расширение популяции за счет добавления новых, только что порожденных, особей

    Сокращение расширенной популяции до исходного размера (работает оператор редукции)

    Критерий останова работы алгоритма выполнен?

    Поиск лучшей достигнутой особи в конечной популяции - результата работы алгоритма

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

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

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

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

Рассмотрим простейший оператор скрещивания. Он выполняется в два этапа. Пусть особь представляет собой строку из mэлементов. На первом этапе равновероятно выбирается натуральное число k от 1 доm-1. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки. На втором этапе строки обменива­ются своими подстроками, лежащими после точки разбиения, то есть эле­ментами сk+1-го поm-й. Так получаются две новые строки, которые на­следовали частично свойства обоих родителей.

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

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

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

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

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

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

Показатели эффективности генетических алгоритмов

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

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

Устойчивость поиска оценивается степенью устойчивости алгоритма к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению.

Два этих фактора - скорость и устойчивость - и определяют эффектив­ность генетического алгоритма для решения каждой конкретной задачи.

Скорость работы генетических алгоритмов

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

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

В первом же случае применяется структурирование популяции реше­ний на основе одного из двух подходов:

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

    Для каждой особи устанавливается ее пространственное положе­ние в популяции. Скрещивание в процессе работы происходит между ближайшими особями. Такой подход получил название концепции скрещивания в локальной области.

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

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

Устойчивость работы генетических алгоритмов

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

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

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

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

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

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

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

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

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

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

    случайный равновероятный отбор;

    рангово-пропорциональный отбор;

    отбор пропорционально значению целевой функции.

Виды операторов редукции особей с целью Сохранения размера попу­ляции практически совпадают с видами операторов отбора родителей. Среди них можно перечислить:

    случайное равновероятное удаление; удаление К наихудших;

    удаление, обратно пропорциональное значению целевой функции.

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

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

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

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название "репродуктивный план Холланда" и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

Представление объектов

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

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Кодирование признаков, представленных целыми числами

Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма. Значения кодов Грея рассмотрены в таблице ниже:

Таблица 1. Соответствие десятичных кодов и кодов Грея

Двоичное кодирование

Кодирование по коду Грея

Десятичный код

Двоичное значение

Шестнадцатеричное значение

Десятичный код

Двоичное значение

Шестнадцатеричное значение
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

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

Кодирование признаков, которым соответствуют числа с плавающей точкой

Самый простой способ кодирования, который лежит на поверхности – использовать битовое представление. Хотя такой вариант имеет те же недостатки, что и для целых чисел. Поэтому на практике обычно применяют следующую последовательность действий:

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

Рассмотрим вышеописанную последовательность действий на примере:

Допустим, что значения признака лежат в интервале . При кодировании использовалось разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется таким образом 8 бит. Допустим значение гена: 00100101bG (заглавная буква G показывает, что используется кодирование по коду Грея). Для начала, используя код Грея, найдем соответствующий ему номер интервала: 25hG->36h->54d. Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал . Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

Кодирование нечисловых данных

При кодировании нечисловых данных необходимо предварительно преобразовать их в числа. Более подробно это описано в статьях нашего сайта, посвященных использованию нейронных сетей.

Определение фенотипа объекта по его генотипу

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому . В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

0010 1010 1001 0100 1101

теперь мы можем определить значения признаков

Признак Значение гена Двоичное значение признака Десятичное значение признака
Признак 1
Признак 2
Признак 3
Признак 4
Признак 5

Основные генетические операторы

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

  1. из популяции выбираются две особи, которые будут родителями;
  2. определяется (обычно случайным образом) точка разрыва;
  3. потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора:

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 >> 1111111 000

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

Схема функционирования генетического алгоритма

Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

  1. Инициировать начальный момент времени $t=0$. Случайным образом сформировать начальную популяцию, состоящую из $k$ особей. $B_0 = \{A_1,A_2, \dots, A_k\}$
  2. Вычислить приспособленность каждой особи $F_{Ai} = fit(A_i)$ , $i=1…k$ и популяции в целом $F_t = fit(B_t)$ (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  3. Выбрать особь $A_c$ из популяции $A_c = \mbox Get(B_t)$
  4. С определенной вероятностью (вероятностью кроссовера $P_c$) выбрать вторую особь из популяции $A_{c1} = \mbox Get(B_t)$ и произвести оператор кроссовера $A_c = \mbox {Crossing}(A_c, A_{c1})$.
  5. С определенной вероятностью (вероятностью мутации $P_m$) выполнить оператор мутации $A_c = \mbox {mutation}(A_c)$.
  6. С определенной вероятностью (вероятностью инверсии $P_i$) выполнить оператор инверсии $A_c = \mbox {inversion}(A_c)$.
  7. Поместить полученную хромосому в новую популяцию $\mbox {insert} (B_{t+1},A_c)$.
  8. Выполнить операции, начиная с пункта 3, $k$ раз.
  9. Увеличить номер текущей эпохи $t=t+1$.
  10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой . При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть $P_{Get(Ai)} ~ Fit(A_i)/Fit(B_t)$. Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор . Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма , которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

  • Программирование

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

    Кратко об алгоритме

    Итак, что же такое генетический алгоритм? Это, прежде всего, метод многомерной оптимизации, т.е. метод поиска минимума многомерной функции. Потенциально этот метод можно использовать для глобальной оптимизации, но с этим возникают сложности, опишу их позднее.

    Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.

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

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

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

    Вот описание классического генетического алгоритма, он прост в реализации и есть место для фантазии и исследований.

    Постановка задачи

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

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

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

    Реализация

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

    В качестве исходных картинок я брал нонограмы («японские сканворды»), но, по правде говоря, можно брать просто черные квадраты - нет абсолютно никакой разницы. Ниже показаны результаты для нескольких изображений. Здесь для всех, кроме «домика», количество мутаций было 100 в среднем на каждую особь, особей в популяции было 100, при размножении популяция увеличивалась в 4 раза. Счастливчиков было 30% в каждой эпохе. Для домика значения были выбраны меньшие (30 особей в популяции, мутаций по 50 на особь).




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


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

    Глобальная оптимизация

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

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

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

    Здесь популяция вымирает, и добавляется небольшой штраф (в размере обычного расстояния до известного минимума). Это сильно снижает вероятность повторов.

    Более интересно, когда популяция не вымирает, а просто начинает подстрариваться под новые условия (след. рисунок). Это достигается при помощи штрафа в виде 0.000001 * sum ^ 4. В таком случае, новые образы становятся немного зашумлены:

    Этот шум устраняется путем ограничения штрафа в max(0.000001 * sum ^ 4, 20). Но мы видим, что четвертого локального минимума (динозавра) достичь не удается - скорее всего, потому, что он слишком близко расположен к какому-то другому.

    Биологическая интерпретация


    Какие же выводы мы можем сделать из, не побоюсь этого слова, моделирования? Прежде всего, мы видим, половое размножение - важнейший двигатель развития и приспосабливаемости. Но только его не достаточно. Роль случайных, маленьких изменений чрезвычайна важна. Именно они обеспечивают возникновение новых видов животных в процессе эволюции, а у нас обеспечивает разнообразие популяции.

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

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

    P.S.

    Писал программу на Matlab (вернее, даже на Octave), потому что тут все - голимые матрицы, и есть инструменты для работы с картинками. Исходный код прилагается.

    Исходный код

    function res = genetic(file) %generating global A B; im2line(file); dim = length(A(1,:)); count = 100; reprod = 4; mut = 100; select = 0.7; stagn = 0.8; pop = round(rand(count,dim)); res = ; B = ; localmin = ; localcount = ; for k = 1:300 %reproduction for j = 1:count * reprod pop = ; end %mutation idx = 10 * (length(res) > 5 && std(res(1:5)) == 0) + 1; for j = 1:count * mut a = floor(rand() * count) + 1; b = floor(rand() * dim) + 1; pop(a,b) = ~pop(a,b); end %selection val = func(pop); val(1:count) = val(1:count) * 10; npop = zeros(count,dim); = sort(val); res = ; opt = pop(i(1),:); fn = sprintf("result/%05d-%d.png",k,s(1)); line2im(opt*255,fn); if (s(1) == 0 || localcount > 10) localmin = ; localcount = ; B = ; % pop = round(rand(count,dim)); continue; % break; end for j = 1:floor(count * select) npop(j,:) = pop(i(j),:); end %adding luckers for j = (floor(count*select)+1) : count npop(j,:) = pop(floor(rand() * count) + 1,:); end %fixing stagnation if (length(res) > 5 && std(res(1:5)) == 0) if (localmin == res(1)) localcount = localcount+1; else localcount = 1; end localmin = res(1); for j = 1:count*stagn a = floor(rand() * count) + 1; npop(a,:) = crossingover(npop(a,:),rand(1,dim)); end end pop = npop; end res = res(length(res):-1:1); end function res = crossingover(a, b) x = round(rand(size(a))); res = a .* x + b .* (~x); end function res = func(v) global A B; res = inf; for i = 1:size(A,1) res = min(res,sum(v ~= A(i,:),2)); end for i = 1:size(B,1) res = res + max(0.000001 * sum(v == B(i,:),2) .^ 4,20); end end function = im2line(files) global A sz; A = ; files = cellstr(files); for i = 1:size(files,1) imorig = imread(char(files(i,:))); sz = size(imorig); A = )]; end A = A / 255; end function = line2im(im,file) global sz; imwrite(reshape(im*255,sz),file); end

    Теги:

    • генетический алгоритм
    • многомерная оптимизация
    • эволюция
    • matlab
    Добавить метки

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

    Другой пример: вы едете по скользкой дороге, и вдруг ваш автомобиль начинает заносить, справа в нескольких метрах от вас столб, а по встречной полосе едет грузовик. Внимание вопрос: как выйти из ситуации с наименьшими потерями, а лучше вообще без них. Факторов, которые нужно учитывать много: ваша скорость и скорость встречного автомобиля, расстояние до столба, «крутость» заноса и т.д. Что нужно делать? Давать газу, пытаясь выйти из заноса, или тормозить, или, может, попытаться аккуратно съехать в кювет, так чтобы не попасть в столб. Вариантов много, и для того чтобы определить оптимальный — нужно попробовать их все. Будь это компьютерной игрой – вы могли бы сохраниться и переигрывать до тех пор, пака результат вас не удовлетворит. Это и есть поиск оптимального решения.

    В системах искусственного интеллекта для решения подобных задач применяются .

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

    Скажем проще: по сути, генетический алгоритм — это метод перебора решений для тех задач, в которых невозможно найти решение с помощью математических формул. Однако простой перебор решений в сложной многомерной задаче – это бесконечно долго. Поэтому генетический алгоритм перебирает не все решения, а только лучшие. Алгоритм берёт группу решений и ищет среди них наиболее подходящие. Затем немного изменяет их – получает новые решения, среди которых снова отбирает лучшие, а худшие отбрасывает. Таким образом, на каждом шаге работы алгоритм отбирает наиболее подходящие решения (проводит селекцию), считая, что они на следующем шаге дадут ещё более лучшие решения (эволюционируют).

    Причём тут биология?

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

    Особь – одно решение задачи.

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

    И сразу самый простой классический пример. Допустим, роботу необходимо объехать шесть контрольных точек за наименьшее время. Расстояние от каждой точки до каждой задано в виде матрицы расстояний.

    Это вариация задачи о коммивояжёре (путешественнике) – относится к классу NP-полных, проще говоря, не может быть решена с помощью математических формул.

    Решение задачи – это последовательность прохождения контрольных точек. Возьмём несколько возможных решений (особей)– это и есть .

    Определения качества решений

    Функция пригодности – функция определяющая качество особей популяции. В нашем примере это будет сумма расстояний от точки до точки в выбранном маршруте.

    ФП = Р(1)+Р(2)+Р(3)+Р(4)+Р(5)+Р(6),

    где Р(1) … Р(6) – расстояние между точками в соответствующем переходе из матрицы расстояний

    Нам необходимо найти минимальное расстояние, поэтому, чем меньше значение ФП для особи, тем лучше.

    Давайте посчитаем функции пригодности. Для первой особи:

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

    1. Естественный отбор в природе

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

    Основной механизм эволюции - это естественный отбор.

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

    Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой.

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

    При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.

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

    2. Что такое генетический алгоритм

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

    Один из наиболее наглядных примеров - задача распределения инвестиций, описанная ранее. В этой задаче переменными являются объемы инвестиций в каждый проект (10 переменных), а функцией, которую нужно максимизировать - суммарный доход инвестора. Также даны значения минимального и максимального объема вложения в каждый из проектов, которые задают область изменения каждой из переменных.

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

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

    Вот как моделируется генетическое наследование

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

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

    Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:

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

    Возвращаясь к задаче оптимального распределения инвестиций, поясним особенности реализации генетического алгоритма в этом случае.

    • Индивидуум = вариант решения задачи = набор из 10 хромосом Х j
    • Хромосома Х j = объем вложения в проект j = 16-разрядная запись этого числа
    • Так как объемы вложений ограничены, не все значения хромосом являются допустимыми. Это учитывается при генерации популяций.
    • Так как суммарный объем инвестиций фиксирован, то реально варьируются только 9 хромосом, а значение 10-ой определяется по ним однозначно.

    Ниже приведены результаты работы генетического алгоритма для трех различных значений суммарного объема инвестиций K.

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


    Если увеличить суммарный объем инвестиций, становится прибыльным вкладывать деньги и в более дорогостоящие проекты.

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

    3. Особенности генетических алгоритмов

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

    Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера (TSP - travelling salesman problem). Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).

    Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.

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

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

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

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

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

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

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

    Компанией Ward Systems Group подготовлен наглядный пример решения задачи коммивояжера с помощью генетического алгоритма. Для этого была использована библиотека функций продукта GeneHunter.