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

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

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

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

     Имеются много способов реализации идеи биологической  эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме:  

     НАЧАЛО /* генетический алгоритм */

     Создать начальную популяцию

     Оценить приспособленность каждой особи

     останов := FALSE

     ПОКА  НЕ останов ВЫПОЛНЯТЬ

     НАЧАЛО /* создать популяцию нового поколения */

     ПОВТОРИТЬ (размер_популяции/2) РАЗ

     НАЧАЛО /* цикл воспроизводства */

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

Скрестить выбранные особи и получить двух потомков.

     Оценить приспособленности потомков

     Поместить потомков в новое поколение 

     КОНЕЦ

     ЕСЛИ  популяция сошлась ТО останов := TRUE

     КОНЕЦ

     КОНЕЦ 

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

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

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

     1. Canonical GA (J. Holland)

     Данная  модель алгоритма является классической. Она была предложена Джоном Холландом  в его знаменитой работе "Адаптация  в природных и исусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Пропорциональный отбор.

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

     - Одноточечный кроссовер и одноточечная мутация.

     Следующее поколение формируется из потомков текущего поколения без "элитизма". Потомки занимают места своих  родителей.

     2. Genitor (D. Whitley)

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

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

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

     - Ограничений на тип кроссовера и мутации нет.

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

     3. Hybrid algorithm (L. "Dave" Davis)

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

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Любые комбинации стратегий отбора и формирования следующего поколения

     - Ограничений на тип кроссовера и мутации нет.

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

     4. Island Model GA

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

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

     - Фиксированная разрядность генов.

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

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

     5. CHC (Eshelman)

     CHC расшифровывается как Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В силу этого после нахождения некоторого решения алгоритм перезапускается, причем лучшая особь копируется в новую популяцию, а оставшиеся особи подвергаются сильной мутации (мутирует примерно треть битов в хромосоме) существующих и поиск повторяется. Еще одной специфичной чертой является стратегия скрещивания: все особи разбиваются на пары, причем скрещиваются только те пары, в которых хромосомы особей существенно различны (хэммингово расстояние больше некоторого порогового плюс возможны ограничения на минимальное расстояние между крайними различающимися битами). При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover) – это разновидность однородного кроссовера, но в нем к каждому потомку попадает ровно половина битов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Перезапуск алгоритма после нахождения решения.

     - Небольшая популяция.

     - Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.

     Отбор в следующее поколение проводится между родительскими особями  и потомками.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.     Другие пути решения задач оптимизации

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

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

     

     Рисунок 1 – Кратчайший путь 

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

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

     

     Рисунок 2 – Переборный метод 

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