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

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

Эволюционные вычисления | Постановка задачи и функция приспособленности | Принцип работы ГА | Факторы, создающие сложность для ГА |


Читайте также:
  1. ГЛАВА 3. ФУНДАМЕНТАЛЬНАЯ ТЕОРЕМА ПОКЕРА
  2. Использование шаблонов
  3. Інтегральна теорема Муавра-Лапласа.
  4. Наказание карателя: Совершенная народная теорема для критерия гонки
  5. Настройка шаблонов
  6. Поощряющие игроки с наказанием: Совершенная народная теорема для критерия угасания.
  7. Превращение кодирования, модуляция. Назначение этих процессов при передаче данных. Теорема Котельникова (Найквиста)

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

M (H, t) — число представителей шаблона H в поколении t.

Количество представителей шаблона H в промежуточном поколении:

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

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

 

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

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

1.1011 -> 1. 1011 1.0100 1. 0100 Как видно, в этой ситуации шаблон не разрушается.

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

Учтём влияние мутации. В шаблоне o(H) фиксированных битов, и каждый не будет инвертирован с вероятностью (1 − pm). Откуда получаем итоговую формулу теоремы шаблонов:

 

· Полученное выражение не слишком удачно для анализа работы генетического алгоритма, т.к. в нём присутствует знак неравенства.

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

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

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

Настройка ГА

Генетический алгоритм производит поиск решений с помощью:

· отбора гиперплоскостей (hyperplane sampling), осуществляемого кроссовером, поскольку последний комбинирует и совмещает шаблоны родителей в их детях.

· метода hill-climbing, обеспечивающегося мутацией: особь случайным образом изменяется – неудачные варианты вымирают, полезные изменения сохраняются популяцией.

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

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

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

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

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

Необходимость сбалансированной сходимости ГА:

§ быстрая сходимость может привести к схождению к неоптимальному решению

§ медленная сходимость часто приводит к потере найденной наилучшей особи.

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


Дата добавления: 2015-11-16; просмотров: 47 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Критерии останова| Различные модификации ГА

mybiblioteka.su - 2015-2024 год. (0.007 сек.)