Вывод правил генетический алгоритм как реализовать. Генетические алгоритмы

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

Энциклопедичный YouTube

1 / 5

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

✪ 20: Введение в генетические алгоритмы (1 из 2)

✪ C# - Морской Бой - Самый лучший алгоритм ИИ

✪ 15 09 2018 Лекция «Генетические алгоритмы для поиска оптимальных структур» Ульянцев В. И.

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

Субтитры

История

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере, установленном в Принстонского университета. Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года, австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970) и Кросби (1973) , с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов. Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998).

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру, искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века - группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции . Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975) . Его исследование основывалось на экспериментах с клеточными автоматами , проводившимися Холландом и на его трудах написанных в университете Мичигана . Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем . Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США) .

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver - первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал об Evolver в 1990 году.

Описание алгоритма

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

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

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

Генетические алгоритмы применяются для решения следующих задач:

1. Оптимизация функций
2. Разнообразные задачи на графах (задача коммивояжера , раскраска, нахождение паросочетаний)
3. Настройка и обучение искусственной нейронной сети
4. Задачи компоновки
5. Игровые стратегии
6. Биоинформатика (фолдинг белков)
7. Синтез конечных автоматов
8. Настройка ПИД регуляторов

Пример простой реализации на C++

Поиск в одномерном пространстве, без скрещивания.

#include #include #include #include #include int main () { srand ((unsigned int ) time (NULL )); const size_t N = 1000 ; int a [ N ] = { 0 }; for ( ; ; ) { //мутация в случайную сторону каждого элемента: for (size_t i = 0 ; i < N ; ++ i ) a [ i ] += ((rand () % 2 == 1 ) ? 1 : - 1 ); //теперь выбираем лучших, отсортировав по возрастанию std :: sort (a , a + N ); //и тогда лучшие окажутся во второй половине массива. //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли: std :: copy (a + N / 2 , a + N , a ); //теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше. std :: cout << std :: accumulate (a , a + N , 0 ) / N << std :: endl ; } }

Пример простой реализации на Delphi

Поиск в одномерном пространстве с вероятностью выживания, без скрещивания. (проверено на Delphi XE)

program Program1 ; {$APPTYPE CONSOLE} {$R *.res} uses System . Generics . Defaults , System . Generics . Collections , System . SysUtils ; const N = 1000 ; Nh = N div 2 ; MaxPopulation = High (Integer ) ; var A : array [ 1 .. N ] of Integer ; I , R , C , Points , BirthRate : Integer ; Iptr : ^ Integer ; begin Randomize ; // Частичная популяция for I := 1 to N do A [ I ] := Random (2 ) ; repeat // Мутация for I := 1 to N do A [ I ] := A [ I ] + (- Random (2 ) or 1 ) ; // Отбор, лучшие в конце TArray . Sort < Integer > (A , TComparer < Integer >. Default ) ; // Предустановка Iptr := Addr (A [ Nh + 1 ]) ; Points := 0 ; BirthRate := 0 ; // Результаты скрещивания for I := 1 to Nh do begin Inc (Points , Iptr ^ ) ; // Случайный успех скрещивания R := Random (2 ) ; Inc (BirthRate , R ) ; A [ I ] := Iptr ^ * R ; Iptr ^ := 0 ; Inc (Iptr , 1 ) ; end ; // Промежуточный итог Inc (C ) ; until (Points / N >= 1 ) or (C >= MaxPopulation ) ; Writeln (Format ("Population %d (rate:%f) score:%f" , [ C , BirthRate / Nh , Points / N ])) ; end .

В культуре

• В фильме 1995 года «Виртуозность » мозг главного злодея выращен генетическим алгоритмом с использованием воспоминаний и поведенческих черт преступников.

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

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

Преимущества генетических алгоритмов особенно хорошо видны при рассмотрении их в сравнении с традиционными методами.

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

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

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

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

К недостаткам ГА следует отнести следующее:

· не гарантируется получение оптимального решения;

· эффективно сформулировать задачу, определить критерий отбора хромосом (задать код) и другие параметры ГА может только специалист;

· постановка задачи в терминах ГА не дает возможности проанализировать статистическую значимость получаемого с их помощью решения;

· достаточно высокая вычислительная ресурсоемкость ГА приводит к тому, что в ходе моделирования эволюции многие решения отбрасываются как неперспективные;

· при временной сложности в среднем ниже, чем у лучших конкурирующих алгоритмов, но не более (получено на основе экспериментальных данных), чем на один порядок;

· невысокая эффективность на заключительных фазах моделирования эволюции, объясняемая тем, что механизмы поиска ГА не являются жестко ориентированными на скорейшее попадание в локальный оптимум;

· не решенными остаются и некоторые другие вопросы, например проблема самоадаптация ГА.

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

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

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

· пакет Evolver 4.0 разработки компании Palisade Corp., представляющий собой дополнение к табличному процессору MS Exсel;

· пакет Gene Hunter 1.0 компании Ward System Group;

· пакет Genetic Training Option (GTO) компании California Scientific Software, созданный специально для обучения нейронных сетей и являющийся приложением пакета Brain Maker.

5.4. Комплексный подход к проектированию систем
искусственного интеллекта

Комплексное применение рассмотренных интеллектуальных методов обработки информации позволяет существенно повысить эффективность разрабатываемых ИнС.

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

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

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

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

· параллелизм в логическом выводе;

· экспертные системы и вывод в условиях неопределенности;

· аргументация и абдуктивный выход;

· квазиаксиоматические системы;

· машинное обучение и индуктивный вывод;

· мягкие вычисления: нечеткая логика и приближенные вычисления;

· нейронные сети;

· генетические алгоритмы;

· системы когнитивной графики;

· системы семантического web и онтологии;

· агентно-ориентированное и распределенное решение проблем;

· понимание естественного языка.

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

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

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

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

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

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

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

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

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

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

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

Реализация

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

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

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

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

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

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

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

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

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

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

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

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

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

P.S.

Исходный код

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

Теги: Добавить метки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма , которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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