Лекция 1 (1121241)

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

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

АЛГОРИТМЫ ОПТИМИЗАЦИИ, ОСНОВАННЫЕ НА МЕТОДЕ ПРОБ И ОШИБОК

ЛЕКЦИЯ 1

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

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

Классические задачи комбинаторной оптимизации: задача коммивояжера и задача о рюкзаке.

ЛЕКЦИЯ 2

Задачи построения расписаний и их классификация.

Задачи, возникающие при проектировании вычислительных систем реального времени:

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

• Задача построения статико-динамических расписаний.

• Задача построения расписания обменов по шине с централизованным управлением (на примере стандарта MIL-STD 1533В).

ЛЕКЦИЯ 3

Алгоритмы случайного поиска

Ненаправленный случайный поиск (метод Монте-Карло)

Алгоритмы направленного случайного поиска без самообучения

Алгоритм с парной пробой

Алгоритм с возвратом при неудачном шаге

Алгоритм с пересчетом при неудачном шаге

Алгоритм с линейной экстраполяцией

Алгоритм наилучшей пробы

Алгоритм статистического градиента

Алгоритмы случайного направленного поиска с самообучением. Различные способы коррекции вектора направления наилучших шагов

ЛЕКЦИЯ 4

Алгоритмы имитации отжига

Концепция построения алгоритмов

Общая схема алгоритмов и проблемы построения алгоритмов для решения задач условной оптимизации

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

Методы распараллеливания алгоритмов имитации отжига:

• асинхронный параллельный алгоритм

• параллельный алгоритм с синхронизацией

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

• подходы, основанные на декомпозиции пространства решений

ЛЕКЦИЯ 5

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

• математическая формулировка задачи

• способы представления расписания и операций его преобразования

• стратегии применения операций преобразования текущего решения

• стандартные операции алгоритма

ЛЕКЦИЯ 6

Параллельный алгоритм имитации отжига для построения статических многопроцессорных расписаний:

• метрика в пространстве расписаний

• разбиение исходного пространства решений на области

• операции преобразования расписания внутри области

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

• сравнение эффективности алгоритмов

ЛЕКЦИЯ 7

Генетические и эволюционные алгоритмы

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

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

Модификации генетических алгоритмов

Алгоритмы дифференциальной эволюции

ЛЕКЦИЯ 8

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

математическая формулировка задачи

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

операции генетического алгоритма

функция выживаемости и критерий останова

ЛЕКЦИЯ 9

Муравьиные алгоритмы

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

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

Модификации муравьиных алгоритмов:

• Максиминный алгоритм

• Модификация с поглощением феромона

• Совместное использование с алгоритмами локального поиска

ЛЕКЦИЯ 10

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

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

• Второй способ сведения задачи построения статико-динамического расписания к задаче нахождения на графе маршрута

ЛЕКЦИЯ 11

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

Задача условной оптимизации заключается в нахождении компонентов вектора X=(x₁,,x_n) минимизирующих целевую функцию f(X) при выполнении ограничений g_i(X) и X  S:

min f(X)

g_i(X)  0, i=1,,m (1.1.)

X  S

Если , то как минимум одна из функций f, g_i в этом случае будет не определена на этом значении X.

По свойствам функций f, g_i и определению множества S можно ввести классификацию различных задач оптимизации

[М. Мину. Математическое программирование. Теория и алгоритмы.- М.: Наука, 1990.].

Например, если функции f,g_i – линейные и S  Zⁿ , то задача (1.1) относится к классу задач целочисленного линейного программирования.

В отдельный класс выделим задачи комбинаторной оптимизации.

Множество S состоит из решений X, описывающих всевозможные:

• размещения

• упорядочивания

• разбиения на группы исходно заданных объектов

Математически множество S описывается набором ограничений, которые требуют согласованного изменения значений элементов X: изменение значения одного из элементов для сохранения корректности решения может требовать принятия конкретных значений ряда других элементов.

Расписание: {“привязка к процессору”, “порядковый номер”}

{“привязка к процессору”,“приоритет ”}

↓

{“привязка к процессору”,“порядковый номер”}

Сложные задачи условной оптимизации – задачи для которых отсутствует априорная информация о функциях f,g_i и множестве S, которая может быть использована для организации поиска оптимального решения, или сложность получения этой информации неприемлема:

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

• Множество S может быть компонентно разнородным: S = S^R  S^Z  S^F  S^KS.

Идея о целесообразности случайного поведения, при наличии неопределенности, сформулирована У.Р. Эшби в работе

[У. Росс Эшби. Конструкция мозга.- М.:, ИЛ, 1962.]

Алгоритмы, опирающиеся на метод проб и ошибок:

• алгоритмы случайного поиска (ненаправленного, направленного, направленного с самообучением)

[ Л.А. Растригин. Статистические методы поиска.- М.: Наука, 1968.],

• алгоритмы имитации отжига

[Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика.- М.: Мир, 1992. – 240с.],

• генетические и эволюционные алгоритмы

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

• муравьиные алгоритмы

[Dorigo M. Optimization, Learning and Natural Algorithms. // PhD Thesis. Dipartimento di Elettronica, Politechnico Di Milano, Milano. 1992.],

[Штовба С.Д. Муравьиные алгоритмы: теория и применение// Программирование. 2005. №4.].

Задача коммивояжера

Задачу коммивояжёра можно представить в виде нахождения маршрута на графе.

• Вершины графа – города.

• Ребра - пути сообщения между этими городами.

• Каждому ребру сопоставлен вес.

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

Длина маршрута - сумма весов входящих в него ребер.

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

,

где - номер города находящийся в i –ой позиции перестановки.

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

Cимметричная задача коммивояжера:

• неориентированный граф,

• для любого ребра (i,j) .

Асимметричная задача коммивояжера:

• ориентированный граф,

• дуги между одними вершинами могут иметь разный вес, т.е. .

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

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

Данная задача принадлежит к классу NP-трудных задач.

Задача о рюкзаке

Имеется:

• рюкзак объемом b,

• набор n различных товаров: объем a_i и стоимость c_i.

Требуется:

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

Если товар упакован в рюкзак, то x_i=1, если нет x_i=0.

Если все коэффициенты a_i целые числа и b целое число, то задача является NP-трудной.

Если все коэффициенты a_i вещественные, то задача может быть решена жадным алгоритмом сложности O(n∙log n).

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

• вынув товар i из оптимально загруженного рюкзака, получим решение задачи о рюкзаке с максимальным объемом b-a_i и набором из n-1 товара.

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

Вычислим относительную стоимость всех товаров в расчете на единицу объема .

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

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

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

В [Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.]

показано, что аналогичный жадный алгоритм может не получать оптимум в дискретной задаче о рюкзаке.

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

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

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

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

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

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