- •Методы однокритериальной оптимизации
- •2. Порядок выполнения лабораторной работы
- •3. Требования к защите лабораторной работы
- •2. Порядок выполнения лабораторной работы
- •2. Порядок выполнения работы
- •3. Требования к защите лабораторной работы
- •3. Требования к защите лабораторной работы
- •Контрольные вопросы
- •Лабораторная работа № 5 случайный поиск с линейной и нелинейной тактикой
- •Параметрическая и структурная адаптация алгоритмов
- •3. Требования к защите лабораторной работы
- •Контрольные вопросы
- •Лабораторная работа № 6 эволюционный бионический алгоритм
- •3. Требования к защите лабораторной работы
- •Литература
- •Варианты заданий
Министерство образования Республики Беларусь
БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ
Кафедра «Системы автоматизированного проектирования»
Методы однокритериальной оптимизации
Лабораторный практикум
по дисциплине «Методы исследования операций»
для студентов специальности 40 01 02 -
«Информационные системы и технологии (по направлениям)»
направления 40 01 02-01 -
«Информационные системы и технологии в проектировании и производстве»
Минск 2005
Составители:
Придухо В.Т.
Кадач Т.В.
Белорусский национальный технический университет
Республика Беларусь, г.Минск, пр-т Скорины, 65
Тел.(017)232-77-52 факс (017)232-91-37
Компьютерная сеть БНТУ
CОДЕРЖАНИЕ
CОДЕРЖАНИЕ 3
Лабораторная работа №1 4
МЕТОД ПРЯМОГО ПЕРЕБОРА ПО СЕТКЕ 4
Лабораторная работа №2 5
МЕТОД МОНТЕ-КАРЛО 5
Лабораторная работа № 3 6
МЕТОД ХУКА-ДЖИВСА 6
Лабораторная работа № 4 8
МЕТОД ШТРАФНЫХ ФУНКЦИЙ 8
Лабораторная работа № 5 9
СЛУЧАЙНЫЙ ПОИСК С линейной и НЕЛИНЕЙНОЙ ТАКТИКОЙ 9
Лабораторная работа № 6 12
ЭВОЛЮЦИОННЫЙ БИОНИЧЕСКИЙ АЛГОРИТМ 12
ЛИТЕРАТУРА 14
Варианты заданий 16
Лабораторная работа №1
МЕТОД ПРЯМОГО ПЕРЕБОРА ПО СЕТКЕ
Цель работы: Изучение одного из простейших методов поиска экстремума функции нескольких переменных нулевого порядка; графическое построение и исследование области поиска.
Описание метода
1. Разбить отрезки [хimin, ximax], i=1,2,..n (где хi – оптимизируемые параметры)
на равные части.
Вычислить значения функции в узлах сетки (на пересечениях координат).
По полученным значениям функции в узлах сетки методом линейной интерполяции построить линии уровней функции (линии равных значений) и получить представление о поведении функции.
4. Найти экстремум функции.
2. Порядок выполнения лабораторной работы
Разработать алгоритм и программу поиска минимума функции двух переменных методом перебора на сетке. (Вариант задания взять у преподавателя). Задать область поиска решения, приняв следующие параметрические ограничения:
x1min=x2min= -1
x1mах=x2mах= 4
Принять шаг сетки х1=х2=0,5.
2. Построить область поиска экстремума и линии уровней минимизируемой функции.
3. Задать область допустимых решений, включив в программу функциональные ограничения в виде неравенств, приведенные в задании, выданном преподавателем. Найти минимум функции с учетом введенных ограничений.
Изменить область допустимых значений таким образом, чтобы найденный минимум функции не попадал в область поиска. Найти условный минимум функции.
3. Требования к защите лабораторной работы
Для защиты работы представить алгоритм и программу поиска минимума функции двух переменных. Программа выполняется в три этапа. Результатом первого этапа является построение сетки и линий уровней функции. На втором этапе необходимо найти минимум функции с учетом функциональных ограничений. На третьем этапе изменяется область поиска путем варьирования функциональными ограничениями.
Контрольные вопросы:
Структура оптимизационной модели.
Задачи анализа и синтеза в общей схеме оптимизации.
Классификация задач оптимизации.
Классификация методов оптимизации.
Лабораторная работа №2
МЕТОД МОНТЕ-КАРЛО
Цель работы: Изучение наиболее распространенного из простейших методов поиска экстремума функции нескольких переменных нулевого порядка; графическое построение и исследование области поиска.
1. Описание метода
Метод Монте-Карло является одним из методов случайного поиска.
1. Многократно смоделировать независимые случайные варианты решений из допустимой области с координатами
хij=ximin+ksiij(ximax-ximin),
где i=1,2,..n (n – число параметров)
j=1,2,..m (m – число испытаний)
ksi – случайное число в диапазоне [0,1].
Вычислить в каждом из вариантов значение заданной функции.
Выбрать вариант с минимальным значением функции.
Метод Монте-Карло относится к числу универсальных, поскольку позволяет решать многоэкстремальные задачи общего вида с отысканием приближенного глобального экстремума. Основной недостаток метода заключается в необходимости проведения большого числа испытаний для получения решения, достаточно близкого к оптимальному.