Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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

Различные модификации ГА

Кодирование

Аргументы в пользу кодирования бинарным алфавитом:

· обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество.

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

· для встречаемости каждого символа в каждой позиции требуется меньший размер популяции

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

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

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

Пример: пусть требуется минимизировать функцию

Если в начальной популяции преобладали хорошие отрицательные решения, то скорее всего мы придём к решению −1 = 11…1. Но достигнуть глобального минимума 00…0 будет практически невозможно, поскольку изменение любого бита будет приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.

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

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

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

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

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

Кроссовер

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

010.1001.1011 -> 010.1011.1011110.1011.0100 110.1001.0100

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

Однородный кроссовер: один из детей наследует каждый бит с вероятностью p0 у первого родителя и с (1 - p0) у второго, второй ребенок получает не унаследованные первым биты. Обычно p0 = 0.5.

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

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

Два основных типа формирования нового поколения после кроссовера и мутации:

· дети замещают родителей

· новое поколение составляется из совокупности и детей, и их родителей

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

Использование второй стратегии и элитизма не допускает потери лучших решений.

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

Некоторые модели ГА

Genitor (Whitley)

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

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

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

CHC (Eshelman)

CHC – это Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation.

Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.

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

При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover), разновидность однородного кроссовера – каждому потомку переходит ровно половина битов каждого родителя.

Размер популяции небольшой. Этим оправдано использование однородного кроссовера.

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




©2015 studopedya.ru Все права принадлежат авторам размещенных материалов.