Лекция 8 (1121247)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Простой генетический алгоритм (алгоритм Холланда)

Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

Популяция - это множество битовых строк.

Каждая строка представляет в закодированном виде одно из возможных решений задачи.

По строке может быть вычислена функция выживаемости, которая характеризует качество решения.

Основные операции алгоритма: селекция, скрещивание и мутация выполняются над элементами популяции.

1. Сгенерировать случайным образом популяцию размера P.

2. Выполнить операцию скрещивания.

3. Выполнить операцию мутации.

4. Вычислить функцию выживаемости для каждой строки популяции.

5. Выполнить операцию селекции.

6. Если критерий останова не достигнут, перейти к шагу 2, иначе завершить работу.

Кодирование решений:

1. Однозначность, т.е. каждая закодированная строка должна соответствовать единственному решению исходной задачи.

2. Возможность кодирования любого допустимого решения.

3. Получение в результате генетических операций корректных вариантов решений.

4. Возможность перехода от любого корректного решения к любому другому корректному решению.

Для задач непрерывного и целочисленного математического программирования, оптимизируемые параметры задаются:

• двоичным кодом числа,

• кодами Грея.

Битовая строка получается склейкой битовых полей параметров.

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

1. Выделять каждой строке количество потомков в соответствии со значением её функции выживаемости:

• если f(x₁)>f(x₂), то вероятность того, что Ch(x₁)Ch(x₂) должна быть достаточно велика. Здесь f – целевая функция, x₁ и x₂ – строки популяции, Ch(x) – количество потомков, присваиваемых строке x.

1. Обеспечивать сохранение в популяции лучших решений.

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

Схема пропорциональной селекции:

1. Вычислить среднее значение функции выживаемости для популяции.

2. Для i-ой строки популяции выделить потомков, где F_i – значение функции выживаемости i-ой строки.

3. Из полученных строк сформировать новую популяцию.

Схема рулетки:

1. Вычислить среднее значение функции выживаемости для популяции.

2. Для i-ой строки популяции выделить сектор рулетки с центральным углом , где F_i – значение функции выживаемости i-ой строки.

3. Сделать P запусков рулетки, где P – размер популяции. Каждый раз выделяем строке в чей сектор мы попали 1-го потомка.

4. Из полученных строк сформировать новую популяцию.

Операция скрещивания:

1. выбрать пары строк для скрещивания;

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

Параметр операции - вероятность скрещивания ( ).

Одноточечное скрещивание:

1. Вся популяция случайным образом разбивается на пары.

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

   • если , то выбирается случайное целое число i в интервале (1, L-1), где L - длина строки, и строки обмениваются фрагментами, находящимися после i-го бита,

   • в противном случае ничего не происходит.

1  L

F_i

F_j

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

1. Для каждого бита генерируется случайное число .

2. Е сли , то бит инвертируется.

(бит ивертируется, если )

Вместо того, чтобы вычислять мутацию для каждого бита, вычислялось расстояние от текущего бита по формуле (*). Бит, отстоящий на вычисленное расстояние обязательно инвертировался.

, (*)

m= , p_m - вероятность мутации,

x_i - равномерно распределённая в промежутке [0, 1] случайная величина,

,

n - целое число.

Критерий останова:

• выполнение алгоритмом априорно заданного числа итераций;

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

• достижение некоторого априорно заданного значения функции выживаемости.

Эволюционные алгоритмы используют целочисленное или вещественное кодирование решений.

Задачи возникающие при построении ГА и ЭА:

1. Выбор способа кодирования решений.

2. Определение операций скрещивания и мутации для работы с используемым представлением решения.

3. Определение параметров алгоритма:

• размера популяции;

• вероятностей скрещивания и мутации.

1. Задание целевой функции и критерия останова.

Теория схем. Гипотеза строительных блоков

Схема - представляет подмножество всех возможных строк, которые имеют те же самые биты в некоторых фиксированных позициях.

Схема **000 представляет все строки с 0 в последних трёх позициях: 00000, 01000, 10000 и 11000.

Схема 1*00* представляет строки: 10000, 10001, 11000 и 11001.

Каждая строка представленная схемой называется примером схемы.

Количество фиксированных позиций в схеме - это её порядок (**000 имеет 3 порядок).

Определяющая длина схемы - это расстояние между самыми дальними фиксированными позициями

• у схемы **000 определяющая длина равна 2,

• у схемы 1*00* - равна 3.

Каждая строка одновременно является примером в 2^l схем (l - длина строки).

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

Представим схему c k фиксированными позициями.

Существует 2^k-1 других схем с теми же самыми фиксированными позициями, которые могут быть получены, перестановками 0 и 1 в этих k позициях.

Каждый такой набор фиксированных позиций образует соревнование схем, борьбу за выживание среди 2^k схем.

Так как существует 2^l возможных комбинаций фиксированных позиций - следовательно, возможно 2^l различных соревнований.

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

Следующее уравнение известно как теорема схем:

,

- ожидаемое количество примеров схемы h на шаге t+1,

- среднее значение целевой функции схемы h на шаге t,

- средние значение целевой функции в популяции на шаге t,

- определяющая длина схемы h, - порядок схемы h,

- вероятность мутации, - вероятность скрещивания,

l - количество бит в строке.

Выражение определяет ожидаемое число примеров схемы h в новой популяции.

Выражение определяет вероятность выживания схемы h после выполнения операций скрещивания и мутации:

• слагаемое определяет вероятность того, что пример схемы h будет разрушен скрещиванием,

• слагаемое определяет вероятность того, что пример будет разрушен мутацией.

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

• Скрещивание - схемы с большой определяющей длиной.

• Селекция обеспечивает сходимость популяции пропорционально мере давления селекции - отношение значения целевой функции лучшей строки к среднему значению целевой функции в популяции.

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

• Уменьшение , или увеличение меры давления селекции приводит к улучшению использования найденных схем, но замедляет исследование пространства решений в поисках новых хороших схем.

Поддержание равновесия известно как проблема “баланса исследования и использования”.

Строительные блоки это схемы:

• с короткими определяющими длинами,

• низким порядком,

• высокими значениями средних целевых функций.

Гипотеза строительных блоков утверждает, что комбинирование хороших строительных блоков даёт хорошую строку.

• Скрещивание старается сохранить генетическую информацию, имеющуюся в скрещиваемых строках.

• Мутация является не консервативной операцией и может создавать совершенно новые строительные блоки.

• Селекция обеспечивает увеличение в популяции количества примеров строительных блоков с высокими значениями целевых функций.

Описание динамики работы ГА с помощью цепей Маркова.

Данный подход предполагает, что строится система детерминированных уравнений, которая определяет вероятность того, что каждая конкретная строка будет присутствовать в популяции в момент времени t c учетом вероятностей для момента времени t-1.

Динамика работы ГА может быть описана вероятностями появления каждой строки (вектором размера 2^l на каждой итерации ГА):

• мутация является линейной операцией, она описывается матрицей размера 2^l2^l,

• операция скрещивания является двухместной и описывается тензором размера 2^l2^l2^l.

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

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

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

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лекций