Лекции All in One (1121240), страница 6

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

Текст из файла (страница 6)

Алгоритм выполнения операции O2:

Шаг 1. Случайным образом выбирается рабочий интервал p.

Шаг 2. Строится множество процессоров , на которые возможно перенести рабочий интервал p: .

Шаг 3. Случайным образом выбирается процессор из и на него переносятся все рабочие интервалы из множества .

Алгоритм выполнения операции O1 :

Шаг 1. Случайным образом выбирается рабочий интервал p.

Шаг 2. Определяется допустимый диапазон ярусов . Этот диапазон выбирается таким образом, что рабочий интервал p может быть перенесён на любой ярус из найденного диапазона.

Шаг 3. Ярус из допустимого диапазона выбирается случайным образом и на него переносится рабочий интервал p.

Распределение областей по узлам вычислительной системы

Пусть n – количество областей разбиения,

m – количество узлов вычислительной системы, осуществляющих поиск решений в областях (n > m).

Области упорядочиваются по критическому пути в графах.

В i-й узел (1 i m) будут распределены области с номерами

j : j mod m = i (1 j n).

Р

ис. Сравнение времени работы алгоритмов.

Рис. Улучшение качества решений при использовании разбиения на области и параллельного алгоритма по сравнению с решениями, полученными классическим алгоритмом.

Лекция 8

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

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.

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

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