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

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

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

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

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

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

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

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

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

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

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

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

Лекция 9

См. презентацию

Модель прикладной программы определим:

1. Множеством рабочих интервалов процессов, составляющих программу PR:

1. Частичным порядком на P:

={ _ik=(p_i,p_k)}_{(i,k)(1...N)};

1. Вычислительной сложностью рабочих интервалов:

;

1. Объемом данных обмена для каждой связи из :

{v_ik}_{(i,k)(1...N)};.

Расписание выполнения программы определено, если заданы:

• привязка,

• порядок.

Модель расписания выполнения программы определим набором простых цепей и отношением частичного порядка _HP на множестве P:

HP=({SP_i}_i=(1...K) , _HP).

{SP_i}_i=(1...M) -набор простых цепей (ветвей параллельной программы).

Отношение частичного порядка _HP на множестве P для HP определим как объединение отношений: _HP= _c ₁ _M, _i - отношение полного порядка на SP_i, которое определяется порядковыми номерами рабочих интервалов в SP_i; _c - набор секущих ребер, которые определяются связями рабочих интервалов, распределенных на разные процессоры.

Расписание HP является корректным, если выполнены следующие ограничения:

1. Каждый рабочий интервал должен быть назначен на процессор (в SP_i).

2. Каждый рабочий интервал должен быть назначен лишь на один процессор (в один SP_i).

3. Частичный порядок, заданный в H сохранен в HP:

4. Расписание HP должно быть беступиковым. Условием беступиковости является отсутствие контуров в графе HP: .

5. Все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор (в один и тот же SP_i).

Дано:

1. H(PR)=(P, )- модель программы,

2. T=f(HP,HW)- функция вычисления времени выполнения расписания HP на архитектуре HW,

3. - директивный срок выполнения программы.

Требуется построить: HP– расписание выполнения программы такое, что:

- число процессоров, на котором выполняется расписание.

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

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

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

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

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

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

Параметрическое представление расписаний с использованием приоритетов

Расписание задается вектором Y_N+K :

K - число процессов в H,

N_i – число рабочих интервалов в i-ом процессе,

- операция построения вектора из параметров и .

содержит номер процессора, на котором выполняются рабочие интервалы i-го процесса.

используются алгоритмом восстановления расписания (определение отношения полного порядка в каждом SP_i) в качестве приоритетов рабочих интервалов.

Алгоритм восстановления полного порядка рабочих интервалов в SP (A1)

Mножество рабочих интервалов разобьем на три подмножества: :

• P1 - множество рабочих интервалов распределенных в SP алгоритмом восстановления на предыдущих шагах;

• P2 - множество рабочих интервалов, у которых все предшественники принадлежат P1;

• P3 - множество рабочих интервалов, у которых хотя бы один из предшественников не принадлежит P1.

1. Начальное разбиение множества P:

• P1=;

• - множество рабочих интервалов в H без предшественников;

• - множество рабочих интервалов в H, у которых имеются предшественники.

2. Находим в P2 рабочий интервал с наименьшим значением параметра (если таких интервалов более одного, то выбираем интервал с наименьшим номером):

• размещаем его в конец соответствующего списка SP (номер списка определяется значением параметра );

• переносим его из P2 в P1.

3. Проверяем P3 с целью возможности переноса рабочих интервалов в P2:

• если есть рабочие интервалы, у которых все предшественники принадлежат P1, то переносим их в P2.

4. Если P2, то к п.2, иначе завершить работу.

Утверждение. Алгоритм A1 восстановления расписания по его параметрическому представлению Y_N+K получает расписание , и расписание восстанавливается однозначно.

Теорема. Любое допустимое расписание может быть задано параметрическим представлением с использованием приоритетов (Y_N+K) и однозначно восстановлено алгоритмом A1, если допустимая верхняя граница L значений параметров больше или равна числу рабочих интервалов (LN).

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

– закодированное решение,

– привязка,

– приоритеты,

– оператор конкатенации строк.

Преобразование решения

1. Параметры могут принимать целочисленные значения в диапазоне [1,…,K],

2. Параметры могут принимать целочисленные значения в диапазоне [1,…,N],

3. количество изменяемых параметров может быть от 1 до N+K.

Операции преобразования решений, удовлетворяющие условиям 1-3 при использовании алгоритма восстановления A1, будут получать решения удовлетворяющие ограничениям на корректность расписаний 1-5, что следует непосредственно из утверждения 1.

Из теоремы 2 следует, что операции преобразования решения, удовлетворяющие условиям 1-3, и алгоритм восстановления A1 позволяют получить любой допустимый вариант решения.

Операции мутации и скрещивания

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

Операция селекции

Для выполнения селекции используется комбинация схемы пропорциональной селекции и схемы рулетки:

• если или это первая итерация алгоритма, то запоминаем как лучшую строку и переносим ее в новую популяцию,

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

• для распределения остатка – схема рулетки.

Функция выживаемости

F(k_t, k_e)=C₁k_t+C₂k_e,

С₁+С₂=1, C_i≤0 (i=1,2)

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

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

Лекция 10

Концепция построения алгоритмов (биологическая модель)

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

Общая схема работы муравьиных алгоритмов

1. Задание начального количества феромона на ребрах графа, количества и начального положения муравьев.

2. Построение муравьями пути (каждый муравей строит путь независимо от остальных).

3. Вычисление целевой функции для каждого пути.

4. Обновление количества феромона на ребрах.

5. Если условие останова не выполнено, то переход к п.2.

Операция построение муравьем пути

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

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

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

Вероятность перехода k-го муравья из i-й вершины в j-ю на t-й итерации алгоритма рассчитывается по следующей формуле:

_ij(t) - количество феромона на ребре (i,j),

- значение локальной целевой функции на ребре (i,j),

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

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