Исследование возможностей генетических алгоритмов

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

ВВЕДЕНИЕ 4
ГЛАВА 1. ОСНОВЫ И ПРИНЦИПЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 6
1.1 Основные термины и определения ГА 6
1.2 Специфика алгоритма работы классического ГА 10
ГЛАВА 2. ОСОБЕННОСТИ И КЛЮЧЕВЫЕ ФАКТОРЫ ГА 19
2.1 Анализ существующих моделей ГА 19
2.2 Преимущества и недостатки ГА 23
ЗАКЛЮЧЕНИЕ 30
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 31

Задачи исследования:
1. Обзор основ и принципов действия генетических алгоритмов.
2. Анализ основных терминов и определений в сфере генетических алгоритмов.
3. Анализ специфики классического генетического алгоритма.
4. Анализ особенностей и ключевых факторов генетических алгоритмов.
5. Описание основных преимуществ и недостатков генетических алгоритмов.

Наиболее часто в практике используется классический ГА, называемый еще элементарным или простым. Он включает в себя следующий порядок действий [12]:
выбор исходной популяции хромосом (инициализация);
оценка степени приспособленности хромосом в имеющейся популяции;
проверка итогового условия остановки алгоритма;
селекция необходимых хромосом;
использование ГО;
создание новой популяции;
выбор оптимальной хромосомы.
Блок-схема основного ГА  изображена на рис.1.
Рисунок 1 – Блок-схема генетического алгоритма
Инициализация состоит в случайном выборе необходимого количества особей, которые представлены двоичными последовательностями чисел, обладающими фиксированной длинной.
Оценивание уровня приспособленности хромосом в конкретной популяции заключается в определении ФП для каждой отдельной хромосомы рассматриваемой популяции. Причем, чем выше значение ФП, тем лучше качество самой хромосомы.
Форма ФП существенно зависит от специфики решаемой задачи. ФП всегда принимает значения больше нуля, а в случае решения некоторой оптимизационной задачи необходимо максимизировать данную функцию. В случаях, когда исходная форма ФП не удовлетворяет таким условиям, то производиться выполняется преобразование, в частности задача минимизации ЦФ путем модификации параметров может быть представлена как задача максимизации [13].
Проверка критерия остановки работы ГА зависит от специфики его использования. Например, в оптимизационных задачах значение ФП (минимальное или максимальное) является известным, поэтому остановка может произойти только после достижения оптимального значения ФП с заданным уровнем точности.
Остановка работы ГА может произойти в случае, если его выполнение не может привести к улучшению достигнутого уровня. ГА может быть остановлен в том числе в случае завершения выделенного времени выполнения или по достижении определенной итерации. Когда условие остановки ГА выполнено производится переход к этапу проведения выбора лучшей хромосомы. Иначе, на следующем шаге осуществляется селекция.
Селекция хромосом состоит в выборе по ФП таких хромосом, которые будут участвовать в процессе создания потомков для новой популяции. Подобный выбор производится по принципу естественного отбора, когда наибольшие шансы в создании новых особей получают хромосомы с максимальными значениями ФП.
Существует ряд разных методов осуществления селекции. Наиболее удобным на практике является «Метод рулетки», названный так по причине схожести с известной азартной игрой. В данном методе каждой хромосоме ставиться в сопоставление отдельный сектор колеса рулетки, а его величина устанавливается прямо пропорциональной значению ФП данной хромосомы. В связи с этим, чем больше уровень ФП, тем больший размер сектора на колесе рулетки. Сумма всех колес рулетки равна сумме значений ФП всех имеющихся хромосом в рамках рассматриваемой популяции. Каждой хромосоме, обозначаемой chi для i = 1,2,…N , где N - общая численность популяции, соответствует некоторый сектор колеса , который выражается в процентах согласно (1.1) [14].
(1.1)
ps может быть найден по формуле (1.2)
(1.2)
где - это значение ФП хромосомы ;
-вероятность селекции хромосомы .
Селекция  представлена в виде результата поворота определенного колеса рулетки, т.к. выбранная хромосома принадлежит выпавшему сектору. Как было отмечено ранее, чем больше сектор, тем выше вероятность победы данной хромосомы. В связи с этим вероятность выбора хромосомы прямо пропорциональна значению её ФП. Для большего удобства можно представить окружность колеса рулетки в виде некоторого цифрового интервала, ограниченного нулем и 100. Тогда выбор хромосомы можно соотнести с выбором нужного числа из интервала [а, b], где а – начало, а b – окончание фрагмента окружности, который соответствует данному сектору.
Это позволяет установить, что выбор с помощью такого колеса рулетки сводится к получению числа, имеющего значение в интервале от 0 до 100, соответствующего конкретной точке на имеющейся окружности колеса. Пример отображения колеса селекции приведен на рис.2.
Рисунок 2 – Пример отображения колеса селекции
В результате выполнения селекции формируется родительская популяция, которая часто называется родительским пулом, имеющую численность равную N [15].
Применение ГО к хромосомам, которые отобраны при помощи помощью селекции, приводит к созданию новой популяции от созданной до этого родительской популяции.
В классическом ГА применяются два основных ГО:  скрещивания (crossover) и  мутации (mutation).
Оператор скрещивания называют кроссовером, с его помощью производится обмен генетическим материалом между скрещивающимися особями. Данный ГО моделирует процесс скрещивания 2-х особей. Случайно формируется выбор точки в хромосоме, где обе хромосомы делятся на две части, после чего происходит обмен материалом (данными). В литературе данную точку называют точкой разрыва, графически она приведена в виде линии на рис.3.
Рисунок 3 – Пример работы кроссинговера
ГО мутации применяется для перемещения популяции из достигнутого локального экстремума, что позволяет обеспечить защиту от преждевременной сходимости. Механизм действия заключается в инвертировании случайно выбранного бита в хромосоме (рис.4.).
Рисунок 4 – Пример выполнения ГО мутации
Аналогично скрещиванию, мутация реализуется не только по одной точке. Возможен выбор некоторого количества точек в хромосоме для проведения инверсии, как правило, их количество является случайным. Поддерживается возможность инвертирования целой группы идущих подряд точек [16].
Вероятность скрещивания, как правило, достаточно велика, а вероятность осуществления мутации намного меньше и на практике практически не превышает 1-2%. Это объясняет тем, что в мире живых организмов в нормальных условиях мутации происходят очень редко.
Поэтому для выбора вероятности проведения мутации применяются варианты 1/L (L - длина хромосомы) или 1/N (N - размер популяции).
Существует и ряд других ГО, общая схема приведена на рис.5.
Рисунок 5 – Схема существующих ГО [17]
ГЛАВА 2. ОСОБЕННОСТИ И КЛЮЧЕВЫЕ ФАКТОРЫ ГА
2.1 Анализ существующих моделей ГА
Существует большое количество различных модификаций классического ГА, рассмотрим наиболее распространенные из них.
1. Genitor. Данный алгоритм создан D. Whitley, он имеет принципиальное отличнее от классического ГА по трем свойствам [18]:
На каждом шаге выполнения только одна пара произвольным образом выбранных родителей может создать лишь одного потомка.
Потомок заменяет не одного из родителей, а наиболее худшую особь популяции.
Принцип отбора особи для замены ее новым потомком производится по ее рейтингу, формируемому по различным критериям, но не по степени приспособленности.
Экспериментально доказано, что в данном ГА  поиск гиперплоскостей происходит намного лучше, а сходимость осуществляется несколько быстрее, чем при применении классического ГА.
2. Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation (СHC), ГА который создан Eshelman в конце прошлого века. Для данного ГА характерными являются следующие аспекты:
Для создаваемого поколения выбираются N максимально приспособляемых особей среди родителей и потомков, а дублирование строк не может быть выполнено.
Для организации процесса скрещивания выбирается случайная пара, но запрещено, если между родителями было расстояние, меньшее Хэммингово или, если расстояние между крайними различающимися битами имеет слишком малое значение.
Для проведения процедуры скрещивания применяется разновидность однородного кроссинговера HUX, при котором потомку переходит 50% битов от каждого каждого родителя.
Размер популяции не превышает 50 особей, что обусловлено применением однородного кроссовера.
CHC ГА акцентируется на агрессивном отборе, уменьшая значение агрессивного скрещивания, однако малый размер исходной популяции приводит ее к такому состоянию, при котором создаются похожие строки. В таком случае применяет мутацию катаклизма, т.е все особи, кроме наиболее приспособленной, подвергаются мощной мутации, при которой модифицируются более 30% битов. Это позволяет продолжить работу алгоритма с применением кроссовера [19].
3. Гибридные ГА. Идея гибридных алгоритмов (ГГА) заключается в сочетании ГА с другими методами поиска, которые применимы для конкретной задачи.
На текущем поколении каждый новый потомок оптимизируется посредством применения данного метода, после чего осуществляются привычные действия [20].
При использовании метода hill-climbing (алгоритм схождения на вершину) каждая особь из популяции достигает своего локального максимума, после этого производятся операции отбора, скрещивания и мутации.
Подобный вид развития называют Ламарковой эволюцией, когда особь способна эффективно обучаться, после чего полученные навыки могут быть записаны в собственный генотип для дальнейшей передачи их потомкам. Не смотря на то, что подобный метод ухудшает способность алгоритма по поиску решения на базе применения механизмов отбора гиперплоскостей, на практике использование ГГА весьма перспективно.
Их преимуществом является то, что вероятность события, когда одна из особей попадает сразу в область глобального максимума, а после выполнения оптимизации окажется наилучшим решением задачи, является достаточно высокой.
Обычный ГА способен быстро найти в области поиска правильные решения, однако сложность возникает при поиске наилучших из них. Метод hill-climbing достаточно быстро достигает локального максимума, при этом возникают сложности при поиске глобального. Поэтому, сочетание данных алгоритмов позволяет обеспечить синергетический эффект [21].
4. Параллельные ГА (ПГА). В связи с тем, что в природе все существующие процессы происходят независимо друг от друга и параллельно, то ГА аналогичным образом могут быть представлены в виде нескольких параллельно выполняющихся процессов, что позволяет существенно увеличитт их общую производительность.
Для того, чтобы распараллелить классический ГА можно применить метод турнирного отбора. Вначале создается N ⁄ 2 процессов (процесс – это процессор или поток, который может функционировать независимо от других потоков).
После этого каждый из них выбирает случайным образом 4 особи из популяции, затем проводиться 2 турнира, победителей в которых скрещивают. Полученные потомки формируют новую популяцию. За один цикл функционирования одного процесса может быть сменено целое поколение [22].
5. Островная модель параллельного ГА. Идея данного ГА заключается в следующем, например, имеется 16 различных процессов и 1600 особей [23].
Можно кластеризовать их на 16 подпопуляций, в каждой из которых по 100 особей. Каждая особь будет развиваться отдельно на базе своего ГА. Фактически, происходит расселение особей по 16 отдельным изолированным островам.
Периодически (каждые n поколений) процессы могут обмениваться рядом особями, фактически происходит миграция, т.е. обмен генетическим материалом. Островная модель ГА на рис.6 [24].
Рисунок 6 – Островная модель ГА
В связи с тем, что населенность особями островов малая, подпопуляции часто склонны к преждевременной быстрой сходимости. При этом необходимо установить корректную частоту миграции. Слишком частая миграция может привести к смешению всех существующих подпопуляций, что может привести к переходу от островной модели к классическому ГА. В случае, когда миграция будет происходить очень редко, она не сможет предотвратить быстрое схождение подпопуляций.
В силу того, что ГА стохастичны, в разных запусках популяция может быть сведена к различным решениям. Островная модель ГА позволяет реализовать алгоритм параллельно несколько раз, для совмещения разных островов и получения в одной из итоговых подпопуляций оптимального решения.
6. Cellular ГА. Принцип работы данного ГА можно представить следующим образом.
Пусть существует 2500 процессов, которые расположены на сетке 50×50 ячеек, левая сторона замкнута с правой, а верхняя с нижней, как показано на рис.6.
Каждый отдельный процесс может взаимодействовать лишь с четырьмя соседями, расположены по разным сторона (снизу, сверху, справа, слева). В каждой из ячеек находится одна особь. Каждый из созданных процессов будет выбирать наилучшую особь, выполняя ее поиск по соседям, после чего осуществлять с ней операцию кроссинговера особи из своей ячейки, а одного полученного потомка помещать в свою ячейку на место родителя [25].
Рисунок 6 – Модель параллельного Cellular ГА
Данная модель похожа на островную модель. Т.е. изначально все особи имеют случайную степень приспособленности, которая отображается цветом. После прохождения нескольких поколений создаются небольшие области похожих особей, обладающих близкой степенью приспособленности. По мере работы данного алгоритма эти области растут и начинают конкуренцию между собой [26].
2.2 Преимущества и недостатки ГА
Преимущества ГА.
1. Первым достоинством ГА является их концептуальная простота. Основными шагами ГА являются: инициализация, анализ качества решения с помощью ФП, изменение популяции в итеративном режиме путем отбора особей и применения ГО. При этом главную роль играет не высокая точность оценки качества всех потенциальных решений, а их ранг, представляющий собой номер позиции. Данные по значениям градиента ЦФ также не нужны. Посредством выполнения ряда итераций над популяциями поиск может сойтись к оптимальному решению асимптотически. Эффективность ГА зависит в первую очередь от способа кодирования итогового решения, а также от используемых ГО. Существенно влияет на итоговый результат начальная инициализация популяции [27].
2. ГА могут быть адаптированы для решения практически любых задач оптимизации. Это обеспечивается тем, что ГА требуют разработки структуры данных для отображения потенциального решения, интегрального показателя качества для проведения оценки потенциального решения и ГО, которые формируют новые решения на базе старых.
Пространство допустимых решений может быть разделено на различные области, способные включать недостижимые зоны, а также зоны возможных изменений. Способ представления итогового решения обычно выбирается инженером-разработчиком на базе анализа его интуиции и имеющегося практического опыта. Поэтому процедура выбора типа кодирования решения независима в отличие от существующих численных методов, где допускаются лишь непрерывные значения из заданного диапазона.
Представление итогового решения должно позволять ГО при модификации решений сохранять поведенческую связь между всеми особями родителями и детьми. Изменения в структуре данных особи родителя приводят к изменениям всех свойств потомков и наоборот, поэтому существенные изменения у родителей должны вызывать аналогичные изменения свойств потомков.
Это способствует эффективному поиску решения во всем пространстве поиска. Множество всех возможных изменений может отслеживаться с помощью размера шага изменения в рассматриваемом пространстве поиска. Он может регулироваться разработчиком вручную или адаптироваться автоматически.
Подобный подход позволяет применять одну и ту же процедуру для решения задач численной и комбинаторной оптимизации [28].
3. Отсутствие жестких требований в процессе решения реальных задач. Реальные задачи оптимизации как правило:
формируют нелинейные ограничения;
требуют задания платежной функции, которая не связаа с наименьшей квадратичной ошибкой;
содержат шумы или выбросы, не позволяющие применять классические методы оптимизации.
ЦФ для реальных проблем является мультимодальной, поэтому градиентные методы быстро сходятся к установленным локальным экстремумам, дающим неудовлетворительные решения. Для решения простых задач, где поверхность отклика может быть выпуклой, ГА существенно хуже классических. Поэтому, для мультимодальных функций ГА дают лучшие результаты. При нелинейных ограничениях классические методы могут давать могут давать некорректные результаты при выпуклой поверхности. В то же время, ЭВ могут достаточно точно учитывать различные линейные и нелинейныые ограничения [29].
4. Гибкое использование априорных знаний, позволяющая осуществлять гибридизацию с другими существующими методами. При решении отдельной проблемы целесообразно учитывать в алгоритме априорные проблемно-ориентированные знания. Это означает, что специализированные алгоритмы, позволяющие учитывать такую информацию, существенно превосходят по всем характеристикам существующие неспециализированные методы. ГА по своей структуре способствуют глубокому учету различных априорных знаний. Это обусловлено специальной структурой данных, которая может быть использована для представления решений или с помощью специальных проблемно-ориентированных ГОО. Подобная информация может быть включена в ФП (химические или физические свойства вещества). Это позволяет акцентироваться на процедуре поиска решений в пространстве состояний.
ГА комбинируемы с другими традиционными методами. На практике на первом этапе процесса оптимизации применяется ГА вместе с градиентным методом, после нахождения так называемой зоны интереса на заключительном этапе. Данные алгоритмы могут применяться как совместно, так и параллельно. Следует заметить, что стартовая популяция потенциальных решений может быть сформирована посредством применения жадных алгоритмов, а не ЭВ. ГА эффективны для обучения нечетких продукционных систем и искусственных нейронных сетей. В таком случае удается преодолеть все ограничения, которые связаны с традиционными подходами.
5. Эволюция является параллельным процессом, в связи с тем, что популяция содержит множество особей, развивающихся параллельно. Это позволяет улучшить возможности применения ЭВ для решения сложных задач. Основные вычислительные ресурсы в ГА используются при оценке значений ФМ, которые для отдельных особей выполняются параллельно, последовательной является сама процедура отбора.
В связи с этим ЭВ реализуются в многопроцессорных компьютерных системах, все чаще используемых в различных областях науки и техники. При решении различных задач на распределенных вычислительных системах временные затраты на организацию решения могут быть обратно пропорциональны числу задач. Это позволяет упростить решение сложных задач высокой размерности, путем оптимизации затрат времени посредством применения ГА
6. ГА устойчивы к динамическим изменениям. Недостатком традиционных методов оптимизации является высокая степень неустойчивости к динамическим изменениям окружающей среды. Поэтому их реализация часто требует множество дополнительных операций для получения адекватного и качественного решения. ГА могут быть применены с целью адаптации возможных решений к изменившимся условиям. Полученная популяция дает основу для дальнейшей оптимизации решений, поэтому в большинстве случаев нет острой необходимости в проведении случайных инициализаций и дополнительной обработки [30].
7. Способность ГА к самоорганизации. Подавляющее большинство существующих методов нуждаются в изначальной установке параметров алгоритмов. Данное правило частично относится и к ГА, которые зависят от мощности популяции, значения вероятности мутации и кроссинговера, шага мутации и др. При этом в ЭВ легче реализовать самоадаптацию, что позволяет выполнять оптимизацию параметров в процессе поиска решения.
8. Весомым преимуществом ГА является поддержка возможностей исследования проблем, для которых нет эвристического описания, т.е. экспертов или документированного опыта решений. Экспертные оценки часто применяются для решения сложно-формализуемых задач, однако они в ряде случаев дают не слишком адекватные решения, по сравнению с автоматизированными методами. Существует ряд проблемы с выявлением и получением знаний через экспертов, т.к. они могут не согласиться на проведение подобной процедуры, могут оказаться неквалифицированными в данной предметной области или могут быть несовместимыми.