Файл: Генетические алгоритмы.ppt

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

Возникли ГА в результате попыток копирования естественных процессов, происходящих в мире живых организмов. Идею построения таких алгоритмов предложил в 1975 году Дж. Холланд в Мичиганском университете. В теории ГА за основу принят ряд принципов, существующих в природе, и упрощенных их до такой степени, чтобы их можно было реализовать на компьютере.
Конечной целью применения ГА в различных областях деятельности является решение задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров.
В отличие от других оптимизационных процедур поиск лучшего варианта осуществляется не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на некотором множестве решений


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


В методологии ГА используется биологическая терминология
в упрощенном виде
Особь (индивидуум, от лат . individuum - неделимое) - наименее неделимая единица биологического вида, самостоятельно существующий организм; в генетических алгоритмах представляются хромосомами.
Популяция – конечное множество особей.
Хромосомы (цепочки, кодовые последовательности) – упорядоченные последовательности генов.
Ген – атомарный элемент хромосомы, материальная единица наследственности.
Генотип – набор хромосом данной особи или совокупность генов данного организма.
Фенотип — совокупность внешних и внутренних признаков организма, приобретённых в результате индивидуального развития, и показывающих чем объект является в реальном мире; в теории ГА фенотип означает множество параметров решения задачи или декодированная структура.

---

Аллель – значение конкретного гена или значение свойства; альтернативная форма структурного состояния гена, от которой зависит проявление наследственного признака.


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

ЭТАПЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

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

Модель «эволюционного процесса»

ПРИНЦИП РАБОТЫ ГА
Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к
«скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» - crossover и «мутация» - mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма.

---

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


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


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


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


ОСНОВНЫЕ ОПЕРАЦИИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Операция скрещивания. Скрещивание является главной генетической операцией.
Эта операция выполняется над двумя хромосомами- родителями и создает отпрыск путем комбинирования особенностей обоих родителей.
В начале выберем некоторую случайную точку p (точка скрещивания - англ. Cut-point), после этого создадим хромосому-отпрыск путем комбинирования сегмента первого родителя, стоящего слева от выбранной точки скрещивания, с сегментом второго родителя, стоящего по правую сторону от точки скрещивания, как это показано на рисунке.
p


СХЕМА ОПЕРАЦИИ СКРЕЩИВАНИЯ

---

популяция


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


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

---

ПРЕИМУЩЕСТВА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Существуют два главных преимущества генетических алгоритмов перед классическими оптимизационными методиками:
1. ГА не имеет значительных математических требований к видам целевых
функций и ограничений. Исследователь не должен упрощать модель объекта, теряя ее адекватность, и искусственно добиваясь возможности применения доступных математических методов. При этом могут использоваться самые разнообразные целевые функции и виды ограничений (линейные и нелинейные), определенные на дискретных, непрерывных и смешанных универсальных множествах.
2. При использовании классических пошаговых методик глобальный оптимум может быть найден только в том случае, когда проблема обладает свойством выпуклости.
В тоже время эволюционные операции генетических алгоритмов позволяют эффективно отыскивать глобальный оптимум.

Пример ГА: Решение Диофантова уравнения

Рассмотрим диофантово (только целочисленные решения) уравнение:
a+2b+3c+4d=30, где a, b, c и d – некоторые положительные целые.
Применение ГА за очень короткое время находит искомое решение (a, b, c, d).
Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30

Хромосома	(a,b,c,d)
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)

Чтобы вычислить коэффициенты приспособленности (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30
и будет нужным значением.


Таблица 1: 1-е поколение хромосом и их содержимое


Таблица 2: Коэффициенты выживаемости первого поколения хромосом

Хромосома	Коэффициент приспособленности
1	|114-30|=84
2	|54-30|=24
3	|56-30|=26
4	|163-30|=133
5	|58-30|=28

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

---