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

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

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

1.2 Представление объектов. Кодирование признаков

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

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

Глава 2. Задачи оптимизации

2.1 Задачи, решаемые с помощью генетических алгоритмов

2.2 Математическая постановка задачи оптимизации

2.3 Решение Диофантова уравнения

2.4 Пути решения задач оптимизации

2.5 Задача коммивояжера

Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам

3.1 Обоснование выбора программного обеспечения

3.2 Описание программной реализации

Заключение

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

“XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?..”

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

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

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

При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов . Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

1.2. Представление объектов. Кодирование признаков

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

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

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

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

В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.

Щепотка истории

Как говорит Википедия: «Отец-основатель генетических алгоритмов Джон Холланд, который придумал использовать генетику в своих целях аж в 1975 году». Для справки в этом же году появился Альтаир 8800, и нет, это не террорист, а первый персональный компьютер. К тому времени Джону было уже целых 46 лет.

Где это используют

Поскольку алгоритм самообучающийся, то спектр применения крайне широк:

• Задачи на графы
• Задачи компоновки
• Составление расписаний
• Создание «Искусственного интеллекта»

Принцип действия

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

• Скрещивание
• Селекция (отбор)
• Формирования нового поколения

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

• Количество поколений (циклов) достигнет заранее выбранного максимума
• Исчерпано время на мутацию

Более подробно о шагах

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

Практика

Вы успешно прослушали «сказку» про чудо-алгоритм и вполне возможно заждались, когда мы его начнем эксплуатировать наконец, хочу вас обрадовать, время настало.
Давайте рассмотрим на примере моих любимых Диофантовых уравнений (Уравнения с целочисленными корнями).
Наше уравнение: a+2b+3c+4d=30
Вы наверно уже подозреваете, что корни данного уравнения лежат на отрезке , поэтому мы берем 5
случайных значений a,b,c,d. (Ограничение в 30 взято специально для упрощения задачи)
И так, у нас есть первое поколение:

1. (1,28,15,3)
2. (14,9,2,4)
3. (13,5,7,3)
4. (23,8,16,19)
5. (9,13,5,2)

Для того чтобы вычислить коэффициенты выживаемости, подставим каждое решение в выражение. Расстояние от полученного значения до 30 и будет нужным значением.

1. |114-30|=84
2. |54-30|=24
3. |56-30|=26
4. |163-30|=133
5. |58-30|=28

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

1. (1/84)/0.135266 = 8.80%
2. (1/24)/0.135266 = 30.8%
3. (1/26)/0.135266 = 28.4%
4. (1/133)/0.135266 = 5.56%
5. (1/28)/0.135266 = 26.4%

Далее будем выбирать пять пар родителей, у которых будет ровно по одному ребенку. Давать волю случаю мы будем давать ровно пять раз, каждый раз шанс стать родителем будет одинаковым и будет равен шансу на выживание.
3-1, 5-2, 3-5, 2-5, 5-3
Как было сказано ранее, потомок содержит информацию о генах отца и матери. Это можно обеспечить различными способами, но в данном случае будет использоваться «кроссовер». (| = разделительная линия)

• Х.-отец: a1 | b1,c1,d1 Х.-мать: a2 | b2,c2,d2 Х.-потомок: a1,b2,c2,d2 or a2,b1,c1,d1
• Х.-отец: a1,b1 | c1,d1 Х.-мать: a2,b2 | c2,d2 Х.-потомок: a1,b1,c2,d2 or a2,b2,c1,d1
• Х.-отец: a1,b1,c1 | d1 Х.-мать: a2,b2,c2 | d2 Х.-потомок: a1,b1,c1,d2 or a2,b2,c2,d1

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

• Х.-отец: (13 | 5,7,3) Х.-мать: (1 | 28,15,3) Х.-потомок: (13,28,15,3)
• Х.-отец: (9,13 | 5,2) Х.-мать: (14,9 | 2,4) Х.-потомок: (9,13,2,4)
• Х.-отец: (13,5,7 | 3) Х.-мать: (9,13,5 | 2) Х.-потомок: (13,5,7,2)
• Х.-отец: (14 | 9,2,4) Х.-мать: (9 | 13,5,2) Х.-потомок: (14,13,5,2)
• Х.-отец: (13,5 | 7, 3) Х.-мать: (9,13 | 5, 2) Х.-потомок: (13,5,5,2)

Теперь вычислим коэффициенты выживаемости потомков.

• (13,28,15,3) - |126-30|=96(9,13,2,4) - |57-30|=27
  (13,5,7,2) - |57-30|=22
  (14,13,5,2) - |63-30|=33
  (13,5,5,2) - |46-30|=16

  Печально так как средняя приспособленность (fitness) потомков оказалась 38.8, а у родителей этот коэффициент равнялся 59.4. Именно в этот момент целесообразнее использовать мутацию, для этого заменим один или более значений на случайное число от 1 до 30.
  Алгоритм будет работать до тех, пор, пока коэффициент выживаемости не будет равен нулю. Т.е. будет решением уравнения.
  Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому уровню (0) более быстро и стабильно.

  Код

  На этом простота заканчивается и начинается чудесный C++...
  Класс на C++ требует 5 значений при инициализации: 4 коэффициента и результат. Для вышепривиденного примера это будет выглядеть так: CDiophantine dp(1,2,3,4,30);

  Затем, чтобы решить уравнение, вызовите функцию Solve(), которая возвратит аллель, содержащую решение. Вызовите GetGene(), чтобы получить ген с правильными значениями a, b, c, d. Стандартная процедура main.cpp, использующая этот класс, может быть такой:

  #include "" #include "diophantine.h" void main() { CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) { cout << "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles << "." << endl; cout << "b = " << gn.alleles << "." << endl; cout << "c = " << gn.alleles << "." << endl; cout << "d = " << gn.alleles << "." << endl; } }

  Сам класс CDiophantine:

  #include #include #define MAXPOP 25 struct gene { int alleles; int fitness; float likelihood; // Test for equality. operator==(gene gn) { for (int i=0;i<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population;// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i 25) break; } temppop[i] = Breed(parent1, parent2);// Create a child. } for(i=0;i

  Статья основана на материалах Википедии и сайта

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 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) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

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

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

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

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

ГА производит над особями следующие действия

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

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

Целевая функция будет иметь вид

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

Мутацией будет являться операция генерации нового случайного числа рассматриваемой популяции.

Инверсия будет изменять значение хромосомы на некоторую небольшую величину, таким образом осуществляя поиск в окрестностях точки с наилучшим решением.
Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#define _USE_MATH_DEFINES
#include
#include
#include
using namespace std;
double func(double x)
{
return sin(M_PI * x / 180) - 1 / x;
}
double mutation(double x0, double x1) // мутация: генерация случайной величины
{
const int NUM = 100000000;
return fabs((double )((rand() * NUM) % (int )((x1 - x0)*NUM) + 1) / NUM) + x0;
}
double inversion(double x, double eps) // инверсия: поиск в окрестностях точки
{
static int sign = 0;
sign++;
sign %= 2;
if (sign == 0) return x - eps;
else return x + eps;
}
void crossover(double *x, double eps, double x0, double x1) // кроссовер: среднее арифметическое
{
int k = 99;
for (int i = 0; i < 8; i++)
for (int j = i + 1; j < 8; j++)
{
x[k] = (x[i] + x[j]) / 2;
k--;
}
for (int i = 0; i < 8; i++)
{
x[k] = inversion(x[i], eps); k--;
}
for (int i = 8; i < k; i++)
x[i] = mutation(x0, x1);
}
void sort(double *x, double *y) // сортировка
{
for (int i = 0; i < 100; i++)
for (int j = i + 1; j < 100; j++)
if (fabs(y[j]) < fabs(y[i])) {
double temp = y[i];
y[i] = y[j];
y[j] = temp;
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
double genetic(double x0, double x1, double eps) // поиск решения с использованием ГА
{
double population;
double f;
int iter = 0;
for (int i = 0; i < 100; i++) // Формирование начальной популяции
{
population[i] = mutation(x0, x1);
f[i] = func(population[i]);
}
sort(population, f);
do {
iter++;
crossover(population, eps, x0, x1);
for (int i = 0; i < 100; i++)
f[i] = func(population[i]);
sort(population, f);
} while (fabs(f) > eps && iter<20000);
cout << iter << " iterations" << endl;
return population;
}
int main()
{
srand(time(NULL ));
cout << genetic(1.0, 10.0, 0.000001);
cin.get();
return 0;
}

Результат выполнения

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

Голосование: 27, 3

Введение

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

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

• Генетические алгоритмы (ГА).
• Эволюционные стратегии.
• Генетическое программирование.
• Эволюционное программирование.

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

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

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

Природный механизм

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

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

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

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

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

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

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

Родителем современной теории генетических алгоритмов (ГА) считается Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems» (1975), стала классикой в этой области. В ней Холланд впервые ввел термин «генетический алгоритм». Сейчас описанный там алгоритм называют «классический ГА» (иногда «канонический ГА», canonical GA), а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.

Ученики Холланда Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David E. Goldberg) внесли огромный вклад в развитие ГА. На книгу Голдберга «Genetic algorithms in search optimization and machine learning» (1989), ссылаются авторы практически каждой работы по этой теме.

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

Функция приспособленности и кодирование решений

Итак, пусть перед нами стоит задача оптимизации. Варьируя некоторые параметры, к примеру, если решать задачу размещения, координаты размещаемых элементов, нужно найти такую их комбинацию, чтобы минимизировать занимаемую площадь. Такую задачу можно переформулировать как задачу нахождения максимума некоторой функции f (x 1 , x 2 , …, x n). Эта функция называется функцией приспособленности (fitness function) и используется для вычисления приспособленности особей. Она должна принимать неотрицательные значения, а область определения параметров должна быть ограничена.

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

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

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

Например, пусть переменная x k принадлежит отрезку [ x min , x max ]. Закодируем ее бинарной строкой из l битов. Тогда строка s k обозначает следующее значение переменной x k:

X k = x min + s k (x max − x min) ⁄ 2 l

если в формуле s k обозначает значение бинарного числа, кодируемого этой строкой.

Если же некоторый параметр принимает конечное количество значений, к примеру, целые от 0 до 1000, то закодируем его бинарной строкой достаточной длины, в данном случае 10. Лишние 23 строки могут повторять уже закодированные значения параметра, либо они могут быть доопределены в функции приспособленности как «худшие», т. е. если параметр кодируется одной из этих строк, то функция принимает заведомо наименьшее значение.

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

101100 11001011 01101100 1100 1 11101 | x 1 | x 2 | | | | x n |

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

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

Алгоритм работы

На рисунке изображена схема работы любого генетического алгоритма:

В классическом ГА начальная популяция формируется случайным образом. Фиксируется размер популяции (количество особей в ней будем обозначать символом N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L -битная строка, где L — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.

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

Шаг алгоритма состоит из трех стадий: генерация промежуточной популяции (intermediate generation ) путем отбора (selection ) текущего поколения (current generation ), скрещивание (recombination ) особей промежуточной популяции путем кроссовера (crossover ), что приводит к формированию нового поколения (next generation ), и мутация нового поколения. На рисунке изображены первые две стадии:

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

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection ). Можно его реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора каждой особи пропорционален ее приспособленности. Изначально промежуточная популяция пуста. N раз запуская рулетку, выберем требуемое количество особей для записи в промежуточную популяцию. Ни одна выбранная особь не удаляется с рулетки. Такой отбор называется stochastic sampling .

Другой способ отбора, который также является пропорциональным, это . Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная — это ее вероятность попасть туда еще раз. Пусть, к примеру, для некоторой особи i f i ⁄ < f > = 1.36 (< f > — средняя приспособленность текущей популяции). Тогда она будет выбрана один раз, а затем с вероятностью 0.36 еще раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N , причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:

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

В классическом генетическом алгоритме применяется одноточечный оператор кроссовера (1-point crossover ): для родительских хромосом (т. е. строк) случайным образом выбирается точка раздела, и они обмениваются отсеченными частями. Полученные две строки являются потомками:

11010 01100101101 ⇒ 10110 01100101101 10110 10011101001 ⇒ 11010 10011101001

К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью p m инвертируется. Эта вероятность обычно очень мала, менее 1%.

1011001100 101101 ⇒ 1011001101 101101

Таким образом, процесс отбора, скрещивания и мутации приводит к формированию нового поколения. Шаг алгоритма завершается объявлением нового поколения текущим. Далее все действия повторяются.

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

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

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

Шаблоны

Шаблоном (schema ) называется строка длины L (т. е. той же длины, что и любая строка популяции), состоящая из символов {0, 1, *} (где * — «don"t care» символ). Будем говорить, что строка является представителем данного шаблона, если в позициях, где знак шаблона равен 0 или 1, она имеет тот же символ. Например, у шаблона 01*0*110 следующие представители:

• 010 00 110
• 010 01 110
• 011 10 110
• 011 11 110

Порядком (order ) шаблона называется количество фиксированных битов в нем. Определяющей длиной (defining length ) шаблона называется расстояние между его крайними фиксированными битами. Например, для шаблона *1***01* порядок o = 3, а определяющая длина Δ = 5.

Очевидно, что количество представителей шаблона H равно 2 L − o (H) , а количество шаблонов равно 3 L (действительно, шаблоны — это строки, у которых на каждой позиции может находиться один из трех символов).

Если представить пространство поиска в виде гиперкуба, то строки это его вершины, а шаблон определяет в нем гиперплоскость. К примеру, шаблон **1 определяет правую грань этого трехмерного куба:

Поэтому термины «гиперплоскость» и «шаблон» взаимозаменяемы. Следующий рисунок изображает другое представление шаблонов:

На нем видно, что некоторые шаблоны имеют с среднем по всему пространству поиска большую приспособленность, чем другие.

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

Внешне кажется, что генетический алгоритм при отборе выбирает строку, однако при этом неявным образом происходит выборка шаблонов, представителем которых она является. Это означает, что на каждом поколении количество представителей шаблона изменяется в соответствии с текущей приспособленностью этого шаблона. У «хороших» шаблонов представители в среднем более приспособленные, а значит, они чаще будут выбираться в промежуточную популяцию. «Плохие» шаблоны имеют много шансов вымереть. Одна строка является представителем сразу многих шаблонов (а именно 2 L: на каждой позиции мы либо оставляем бит строки, либо заменяем его на «*»). Поэтому при отборе одной строки отбирается сразу целое множество шаблонов. Это явление получило название неявный параллелизм (implicit parallelism ).

Теорема шаблонов

Теорема шаблонов (The Schema Theorem ) была приведена в упомянутой выше работе Холланда и является первой попыткой объяснить, почему генетические алгоритмы работают. Она показывает, как изменяется доля представителей шаблона в популяции.

Пусть M (H , t) — число представителей шаблона H в t -ом поколении. В силу того, что при построении промежуточной популяции используется пропорциональный отбор, в ней количество представителей данного шаблона будет

M (H , t + intermediate) = M (H , t) f (H , t) ⁄ < f (t)>

где f (H , t) — приспособленность шаблона H в t -ом поколении, а < f (t)> — средняя приспособленность t -го поколения.

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

Δ(H) (1 − P (H , t) f (H , t) ⁄ < f (t)>) ⁄ (L −1)

где P(H, t) — доля представителей шаблона H в t -ом поколении. Первый множитель произведения равен вероятности точки раздела попасть между фиксированными битами шаблона, а второй — вероятности выбрать в пару представителя другого шаблона.

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

Таким образом, после кроссовера, переходя от количества представителей к их доле, получаем следующее неравенство:

< f (t)>) ⁄ (L −1)] ⁄ < f (t)>

Теперь учтем влияние мутации. Для каждого фиксированного бита вероятность того, что он не будет инвертирован, равна (1 − p m). Поскольку всего в шаблоне фиксированных битов o (H), то верна следующая итоговая формула теоремы шаблонов:

P (H , t + 1) ≥ P (H , t) f (H , t) (1 − p m) o (H) ⁄ < f (t)>

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

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

Строительные блоки

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

Холланд (1992) показал, что в то время, как ГА обрабатывает N строк на каждом поколении, в то же время неявно обрабатываются порядка N 3 гиперплоскостей. Это доказывается с рассчетом на реально применимые размеры популяции и длины строки. Практически это означает, что большая популяция имеет возможность локализовать решение быстрее, чем маленькая. Для оценки рекомендуемого размера популяции в зависимости от длины строки можно вспомнить, что всего гиперплоскостей 3 L .

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

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

Все локальные максимумы приведенной функции приходятся на блок **0*, а минимумы — на **1*, поэтому очевидно, что после отбора основная часть особей будут представителями первого блока. Левая половина графика в среднем ниже правой, поэтому доля блока 1*** будет преобладать над долей 0***. Получается, что основная масса особей окажутся представителями блока 1*** и в то же время **0*, значит, большое их количество будут представителями блока 1*0*. Теперь, выбирая между блоками 100* и 110*, получаем, что второй блок будет преобладать над первым. Таким образом, можно сказать, что хорошие строительные блоки малого порядка сложились в приспособленные блоки большего порядка, и в результате мы оказались в области глобального максимума, чем приблизились к решению задачи.

Настройка ГА

Генетический алгоритм производит поиск решений двумя методами одновременно: отбором гиперплоскостей (hyperplane sampling ) и методом hill-climbing . Кроссовер осуществляет первый из них, поскольку комбинирует и совмещает шаблоны родителей в их детях. Мутация обеспечивает второй метод: особь случайным образом изменяется, неудачные варианты вымирают, а если полученное изменение оказалось полезным, то, скорее всего, эта особь останется в популяции.

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

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

Введем понятие давления отбора (selection pressure ) — это мера того, насколько различаются шансы лучшей и худшей особей популяции попасть в промежуточную популяцию. Для пропорционального отбора эта величина имеет свойство уменьшаться с увеличением средней приспособленности популяции. Действительно, при этом для каждой особи отношение f ⁄ < f > стремится 1, а значит шансы плохой и хорошей особей создать потомство уравниваются.

При увеличении p c или p m и при уменьшении давления отбора (например, за счет использования других стратегий отбора) размножение представителей приспособленных шаблонов замедляется, но зато происходит интенсивный поиск других шаблонов. Обратно, уменьшение p c или p m и увеличение давления отбора ведет к интенсивному использованию найденных хороших шаблонов, но меньше внимания уделяется поиску новых. Таким образом, для эффективной работы генетического алгоритма необходимо поддерживать тонкое равновесие между исследованием и использованием . Это можно сформулировать также как необходимость сбалансированной сходимости ГА: быстрая сходимость может привести к схождению к неоптимальному решению, а медленная сходимость часто приводит к потере найденной наилучшей особи.

Методология управления сходимостью классического ГА до сих пор не выработана.

Другие модели ГА

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

Кодирование

Если сравнивать кодирование бинарным алфавитом и небинарным, то первый вариант обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество. Действительно, если требуется закодировать 2 L значений, то для бинарного алфавита количество гиперплоскостей будет 3 L , тогда как при использовании, к примеру, четырехзначного алфавита длина слов будет в 2 раза меньше, и гиперплоскостей будет 5 L ⁄ 2 , т. е. меньше.

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

С другой стороны, небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи.

Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея , а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs , когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f (x) = x 2 . Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.

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

Кроссовер

Одноточечный кроссовер мы рассмотрели выше.

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

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

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

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

Стратегии отбора

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

Ранковый отбор (rank selection ) отличается от пропорционального тем, что для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.

Турнирный отбор (tournament selection ) осуществляется следующим образом: из популяции случайным образом выбирается t особей, и лучшая из них помещается в промежуточную популяцию. Этот процесс повторяется N раз, пока промежуточная популяция не будет заполнена. Наиболее распространен вариант при t = 2. Турнирный отбор является более агрессивным, чем пропорциональный.

Отбор усечением (truncation selection ): популяция сортируется по приспособленности, затем берется заданная доля лучших, и из них случайным образом N раз выбирается особь для дальнейшего развития.

Стратегии формирования нового поколения

Выделяют два типа формирования нового поколения после получения множества детей в результате кроссовера и мутации:

1. дети замещают родителей;
2. новое поколение составляется из совокупности и детей, и их родителей, например, выбором N лучших.

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

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

Некоторые модели генетических алгоритмов

Классический ГА был рассмотрен выше. Напомним, что его создал Holland (1975).

Genitor

Этот алгоритм был создан Уитли (D. Whitley). Genitor -подобные алгоритмы отличаются от классического ГА следующими тремя свойствами:

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

Утверждается (Syswerda, 1991), что в Genitor поиск гиперплоскостей происходит лучше, а сходимость быстрее, чем у классического ГА.

CHC

CHC расшифровывается как Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation . Этот алгоритм был создан Eshelman (1991) и характеризуется следующими параметрами:

• Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.
• Для скрещивания выбирается случайная пара, но не допускается, чтобы между родителями было мало Хэммингово расстояние или мало расстояние между крайними различающимися битами.
• Для скрещивания используется разновидность однородного кроссовера HUX (Half Uniform Crossover ): ребенку переходит ровно половина битов каждого родителя.
• Размер популяции небольшой, около 50 особей. Этим оправдано использование однородного кроссовера.
• CHC противопоставляет агрессивный отбор агрессивному кроссоверу, однако все равно малый размер популяции быстро приводит ее к состоянию, когда создаются только более или менее одинаковые строки. В таком случае CHC применяет cataclysmic mutation : все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.

Hybrid Algorithms

Идея гибридных алгоритмов (hybrid algorithms ) заключается в сочетании генетического алгоритма с некоторым другим методом поиска, подходящим в данной задаче (зачастую это бывает hill-climbing ). На каждом поколении каждый полученный потомок оптимизируется этим методом, после чего производятся обычные для ГА действия. При использовании hill-climbing получается, что каждая особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации.

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

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

Параллельные ГА

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

Сделаем из классического ГА параллельный. Для этого будем использовать турнирный отбор. Заведем N ⁄ 2 процессов (здесь и далее процесс подразумевается как некоторая машина, процессор, который может работать независимо). Каждый из них будет выбирать случайно из популяции 4 особи, проводить 2 турнира, и победителей скрещивать. Полученные дети будут записываться в новое поколение. Таким образом, за один цикл работы одного процесса будет сменяться целое поколение.

Island Models

island model ) — это тоже модель параллельного генетического алгоритма. Она заключается в следующем: пусть у нас есть 16 процессов и 1600 особей. Разобьем их на 16 подпопуляций по 100 особей. Каждая их них будет развиваться отдельно с помощью некого генетического алгоритма. Таким образом, можно сказать, что мы расселили особи по 16-ти изолированным островам.

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

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

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

Cellular Genetic Algorithms

Cellular Genetic Algorithms — модель параллельных ГА. Пусть дано 2500 процессов, расположенных на сетке размером 50×50 ячеек, замкнутой, как показано на рисунке (левая сторона замыкается с правой, верхняя с нижней, получается тор).

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

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

Другие модели

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

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

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

Наблюдения

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

Факторы, создающие сложность для ГА

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

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

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

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

Выводы

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

Примеры применения ГА

• Демонстрация работы классического ГА на многоэкстремальной функции (http://ai.bpa.arizona.edu/~mramsey/ga.html).
• Решение задачи коммивояжера (TSP) при помощи ГА (http://lib.training.ru/Lib/ArticleDetail.aspx?ar=803&l=&mi=93&mic=112).
• Обучение модели человека ходьбе при помощи ГА (http://www.naturalmotion.com/pages/technology.htm).
• Еще одна демонстрация работы ГА (http://www.rennard.org/alife/english/gavgb.html).

Литература

1. Darrel Whitley, A Genetic Algorithm Tutorial, Statistics and Computing (4): 65-85, 1994.
2. Darrel Whitley, An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls, Journal of Information and Software Technology 43: 817-831, 2001.
3. K. Deb, S. Agrawal, Understanding Interactions Among Genetic Algorithm Parameters, 1998.
4. Авторский сайт Ю. Цоя (http://www.qai.narod.ru/).
5. Исаев С.А. Популярно о генетических алгоритмах (http://algolist.manual.ru/ai/ga/ga1.php).

Булат Яминов

Спасибо, полезная статья.

Хочу обратить ваше внимание на несколько моментов.

В разделе?Шаблоны? в столбик перечислены представители шаблона. В третьем и четвертом представителях следует на четвертой позиции писать цифру 0, вместо 1. В абзаце перед изображением куба говорится, что?шаблон определяет в нем гиперплоскость?, что верно лишь для некоторых шаблонов. Например, *11 уже не гиперплоскость (коразмерность не равна 1).

Надеемся, посетители этой страницы обратят внимание на ваши замечания.

И некоторые языковые опечатки. <... ...="">

Спасибо, указанные вами опечатки устранены.

В разделе?Примеры применения ГА?, к сожалению, 3 битых ссылки.