![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Шима (Schema)
Schema – строка длины l, состоящая из 0 или 1 и неопределенных символов. Пример: Каждая шима имеет 2 свойства – порядок и определенная длина. · Порядок – число определенных битов; · Определенная длина – расстояние между крайними определенными битами;
Строящие блоки – шимы, обладающие следующими свойствами: · Высокая приспособленность; · Низкий порядок; · Короткая определенная длина;
Приспособленность шимы определяется средним количеством строк, которые её содержат. После отбора остаются только строки с более высокой приспособленностью. Скрещивание реже разрушают шимы с более короткой определенной длиной, с более низким порядком, а мутация реже разрушает шимы с низким порядком и более высокой определенной длиной, поэтому такие шимы имеют больше шансов переходить из поколения в поколение. Теорема шим Простой генетический алгоритм экспоненциально увеличивает число примеров полезных шим или строящих блоков.
Вычислим ожидаемое число примеров шимыH в Вероятность того, что шимаHпереживет мутацию равна (2). Тогда ожидаемое число примером шимыH в поколении Теорема шим показывает, что строящие блоки растут по экспоненте, в то время как шимы с приспособленностью ниже средней распадаются с той же скоростью. Теорема шим описывает следующие аспекты поведения генетического алгоритма: 1) Мутации с большей вероятностью разрушают шиму более высокого порядка, а скрещивание с большей вероятностью разрушает шимы с большей определенной длиной; 2) Когда происходит отбор, популяция сходится пропорционально отношению приспособленности лучшей особи к средней приспособленности популяции. Это отношение называется мерой давления отбора; 3) Увеличение вероятности скрещивания или вероятности мутации, или уменьшение давления отбора ведет к увеличению выборки или исследованию пространства поиска, но не позволяет использовать все хорошие шимы, которым располагает генетический алгоритм; 4) Уменьшение вероятности скрещивания или вероятности мутации, или увеличение давления отбора ведет к улучшению использования найденныхшим, но тормозит исследование пространства поиска новых хороших шим; 5) Генетический алгоритм должен поддерживать равновесие между тем и другим, что известно как проблема баланса исследования и использования;
|