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

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

2019, Корлякова М.О.

2. Схемы - Стринги

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

3. Схемы - Стринги

Для количественной оценки вводятся две
характеристики:
порядок схемы 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.

4. Теоремы ГА

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

5. Теоремы ГА

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

6. Фундаментальная теорема ГА

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

7.

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

8. Параметры генетических алгоритмов

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

9. мощность популяции

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

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

11. Вероятность скрещивания и мутации

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

12. Преимущества генетических алгоритмов

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

13. Недостатки генетических алгоритмов

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

14. No Free Lunch теорема

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

15. Вопрос

Какие генетические операторы используются в ГА?
Каковы основные параметры ГА
Вычислить определенную длину и порядок схемы
вариант
1
2
3
схема
*1*1*1
***111
*00*0*