Методы генетического программирования. Теоремы генетических алгоритмов презентация

Схемы - Стринги
схемы (schema)
Холланд
множества хромосом, которые обладают некоторыми общими свойствами, то есть в каком- то смысле подобны друг другу
{0, 1, *}, где * означает неопределенное значение
схема (0*0001) – стринги {000001, 010001}
схема (*0110*) – стринги {00100, 101100, 001101, 101101}

Схемы - Стринги
Для количественной оценки вводятся две характеристики:
порядок схемы O(H) - число фиксированных позиций (не равных *).
схема H= 0*1*** - порядок O(H)= 2.
определенная длина L(H)– это расстояние между первой и последней определенной (не равной *) позицией.
Схема H = 0111*1** , L(H)= 6 – 1 = 5.
Схема H = 0**** , L(H)= 1 – 1 = 0.

Теоремы ГА
Влияние репродукции
Схемы "растут" как отношение среднего значения фитнесс-функции схемы к среднему значению фитнесс-функциипопуляции.
Схема со значением фитнесс-функции выше средней в популяции имеет больше возможностей для копирования и наоборот.
Правило репродукции Холланда : "схема со значением фитнесс-функции выше среднего живёт и размножается, а со значением фитнесс-функции ниже среднего умирает".

Теоремы ГА
Влияние кроссинговера
Число схем в новой популяции зависит от двух факторов:
значение фитнесс-функции схемы выше или ниже значения Целевой Функции популяции;
схема имеет "длинную" или короткую" (определенную длину).
Схемы со значением Целевой Функции выше средней и с короткой длиной имеют возможность экспоненциального роста в новой популяции.

Фундаментальная теорема ГА
Влияние мутации
Теорема. Схемы малого порядка, малой определенной длины и со значением фитнесс-функции выше средней формируют растущее по показательному закону число своих представителей в последующих поколениях генетического алгоритма.

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

Параметры генетических алгоритмов
мощность популяции N,
структура представления решения,
вид генетических операторов кроссинговера и мутации,
вероятности кроссинговера и мутации

мощность популяции
N большое – много вариантов для начала работы
N большое – высокая вычислительная сложность, опасность преждевременной сходимости
N=[30,200]

Виды операторов

Вероятность скрещивания и мутации
способность сходиться к оптимуму (локальному или глобальному) после нахождения области, содержащей этот оптимум;
способность находить новые области в пространстве решений в поисках глобального оптимума.
Увеличение значений вероятностей ведет к расширению пространства поиска.
Pc=[0.5, 1]
Pm=[0.001, 0.05]

Преимущества генетических алгоритмов
Концептуальная простота
Широкая применимость
Менее жесткие требования при решении реальных задач
Потенциальное использование априорных знаний и гибридизация с другими методами
Параллелизм
Устойчивость к динамическим изменениям
Способность к самоорганизации
Решение проблем, для которых отсутствует опыт решений

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

No Free Lunch теорема
Существует ли некоторый лучший эволюционный алгоритм, который дает всегда лучшие результаты при решении всевозможных проблем?
1996
Сумма условных вероятностей посещения в пространстве решений каждой точки одинакова для множества всевозможных целевых функций независимо от используемого алгоритма.
Не существует лучшего алгоритма (эволюционного или любого другого) для решения всех проблем.