Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255)
Текст из файла
Алгоритмы оптимизации, основанные на методе проб и ошибок1. Задачи условной оптимизации .................................................................................................31.1. Математическая формулировка задач условной оптимизации и их классификация ..31.2. Понятие «сложных» задач условной оптимизации. Проблемы примененияоптимальных и эвристических алгоритмов, использующих априорно известныесвойства о целевой функции и функциях ограничений.........................................................41.3. Классические задачи комбинаторной оптимизации .......................................................61.3.1. Задача коммивояжера..................................................................................................61.3.2.
Задача о рюкзаке..........................................................................................................71.3.3. Задачи построения расписаний и их классификация...............................................81.4 Задачи, возникающие при проектировании вычислительных систем реальноговремени.....................................................................................................................................131.4.1. Задача определения минимально необходимого числа процессоров ипостроения расписания выполнения функциональных задач со временем выполненияне превышающим заданный директивный срок...............................................................131.4.2. Задача построения статико-динамических расписаний.........................................171.4.3.
Задача построения расписания обменов по шине с централизованнымуправлением (на примере стандарта MIL-STD 1533В) ...................................................192. Алгоритмы случайного поиска ..............................................................................................262.1. Ненаправленный случайный поиск (метод Монте-Карло) ..........................................262.2.
Алгоритмы направленного случайного поиска без самообучения .............................272.2.1. Алгоритм с парной пробой.......................................................................................272.2.2. Алгоритм с возвратом при неудачном шаге ...........................................................272.2.3. Алгоритм с пересчетом при неудачном шаге .........................................................272.2.4. Алгоритм с линейной экстраполяцией....................................................................272.2.5.
Алгоритм наилучшей пробы ....................................................................................272.2.6. Алгоритм статистического градиента .....................................................................272.3. Алгоритмы случайного направленного поиска с самообучением. Различныеспособы коррекции вектора направления наилучших шагов .............................................273. Алгоритмы имитации отжига.................................................................................................283.1. Концепция построения алгоритмов................................................................................283.2. Общая схема алгоритмов и проблемы построения алгоритмов для решения задачусловной оптимизации............................................................................................................293.3.
Модификация закона понижения температуры, позволяющая ускорить выход излокальных оптимумов.............................................................................................................313.4. Методы распараллеливания алгоритмов имитации отжига.........................................313.4.1. Асинхронный параллельный алгоритм ...................................................................313.4.2. Параллельный алгоритм с синхронизацией............................................................323.4.3.
Алгоритм, основанный на декомпозиции целевой функции ................................343.4.4. Подходы, основанные на декомпозиции пространства решений.........................353.5. Алгоритм имитации отжига для решения задачи построения статическихмногопроцессорных расписаний с минимальным временем выполнения на заданномчисле процессоров ...................................................................................................................363.5.1. Математическая формулировка задачи...................................................................363.5.2. Способы представления расписания и операций его преобразования.................373.5.3. Стратегии применения операций преобразования текущего решения ................433.5.4.
Стандартные операции..............................................................................................443.6. Параллельный алгоритм имитации отжига для построения статическихмногопроцессорных расписаний............................................................................................4413.6.1. Метрика в пространстве расписаний.......................................................................453.6.2.
Разбиение исходного пространства решений на области......................................473.6.3. Операции преобразования расписания внутри области ........................................503.6.4. Распределение областей по узлам вычислительной системы...............................513.7.
Сравнение эффективности алгоритмов ..........................................................................524. Генетические и эволюционные алгоритмы...........................................................................574.1.Простой генетический алгоритм (алгоритм Холланда).................................................574.2. Теория схем.
Гипотеза строительных блоков................................................................604.3. Модификации генетических алгоритмов .......................................................................644.3.1. Алгоритмы, использующие функции значимости фрагментов ............................644.4 Генетический алгоритм для решения задачи о рюкзаке................................................844.5. Генетический алгоритм для решения задачи определения минимальнонеобходимого числа процессоров и построения расписания выполненияфункциональных задач со временем выполнения не превышающим заданныйдирективный срок....................................................................................................................844.5.1.
Математическая формулировка задачи...................................................................844.5.2. Кодирование решений...............................................................................................844.5.3. Операции генетического алгоритма ........................................................................894.5.4. Функция выживаемости и критерий останова........................................................904.6. Алгоритмы дифференциальной эволюции ....................................................................905. Муравьиные алгоритмы..........................................................................................................935.1. Концепция построения алгоритмов (биологическая модель) ......................................935.2. Общая схема работы муравьиных алгоритмов..............................................................945.3.
Модификации муравьиных алгоритмов.........................................................................965.3.1. Максиминный алгоритм ...........................................................................................965.3.2. Модификация с поглощением феромона ................................................................975.3.3. Совместное использование с алгоритмами локального поиска............................975.4. Муравьиные алгоритмы для решения задачи построения статико-динамическихрасписания (два способа представления задачи) .................................................................975.4.1.
Первый способ сведения задачи построения статико-динамического расписанияк задаче нахождения на графе маршрута ..........................................................................975.4.2. Второй способ сведения задачи построения статико-динамического расписанияк задаче нахождения на графе маршрута ........................................................................1005.5. Муравьиный алгоритм для решения задачи построения расписания обменов пошине с централизованным управлением.............................................................................1026.
Алгоритмы, использующие аппроксимирующую модель целевой функции .................104Приложение 1. Операторы мутации и скрещивания .............................................................113Оператор мутации .................................................................................................................113Оператор скрещивания .........................................................................................................11621. Задачи условной оптимизации1.1. Математическая формулировка задач условной оптимизации и ихклассификацияЗадача условной оптимизации заключается в нахождении компонентов вектора X =(x1,,xn) (оптимизируемых параметров) минимизирующих целевую функцию f(X) привыполнении ограничений gi(X) и X S:min f(X)gi(X) 0, i=1,,m(1.1.)XSЕсли X S , то как минимум одна из функций f, gi в этом случае будет неопределена на этом значении X.По свойствам функций f, gi и определению множества S можно ввестиклассификацию различных задач оптимизации [М.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
