- •Теория принятия решений
- •Часть 2 нелинейное программирование, теория игр, многокритериальные задачи принятия решений
- •Введение
- •4. Нелинейное программирование
- •4.1. Характеристика задач
- •4.2. Условия оптимальности
- •4.3. Квадратичное программирование
- •4.4. Сепарабельное программирование
- •4.5. Задачи дробно-линейного программирования
- •4.6. Методы спуска
- •4.7. Методы одномерной минимизации
- •4.7.3. Метод деления интервала пополам
- •4.7.4. Метод золотого сечения
- •4.7.6. Метод первого порядка
- •4.8. Многомерный поиск безусловного минимума
- •4.8.1. Метод Гаусса – Зейделя (покоординатного спуска)
- •4.8.2. Метод Хука – Дживса (метод конфигураций)
- •4.8.3. Симплексный метод
- •4.8.4. Градиентные методы
- •4.8.6. Методы сопряженных направлений
- •4.8.7. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •4.8.8. Генетические алгоритмы
- •Исходная популяция
- •Результаты работы оператора скрещивания
- •Популяция первого поколения
- •4.9. Методы условной оптимизации
- •4.9.2. Метод проектирования градиента
- •4.9.3. Метод штрафных функций
- •Минимизация по методу Ньютона
- •4.9.4. Метод барьерных функций
- •Результаты поиска алгоритмом барьерных функций
- •4.9.5. Другие методы условной оптимизации
- •5. Методы теории игр в управлении
- •5.1. Теория игр в контексте теории принятия решений
- •5.2. Матричные игры с нулевой суммой
- •Использование линейной оптимизации при решении матричных игр. Пусть игра не имеет оптимального решения в чистых стратегиях, т.Е. Седловая точка отсутствует .
- •5.3. Игры с природой
- •5.4. Критерии, используемые для принятия решений
- •В играх с природой. Критерии, основанные
- •На известных вероятностях стратегий природы
- •Иногда неопределенность ситуации удается в некоторой степени ослабить с помощью нахождения вероятностей состояний на базе данных статистических наблюдений.
- •5.5. Оценка необходимости эксперимента
- •6. Многокритериальные задачи принятия решений
- •6.1. Основы многокритериальный оптимизации
- •6.2. Принцип оптимальности Парето.
- •6.3. Принцип равновесия по Нэшу
- •6.4. Конфликты, переговоры и компромиссы
- •6.5. Краткий обзор методов решения задачи векторной оптимизации
- •Значения компонентов вектор-функции
- •1. Оптимальность по Парето
- •Исходные данные для задачи оптимизации по Парето
- •Эффективность операции
- •2. Принятие решений в условиях неопределенности
- •Исходные данные для задачи принятия решения в условиях неопределенности
- •3. Многокритериальная оптимизация
- •Заключение
- •Библиографический список
- •Оглавление
- •Теория принятия решений
Алгоритм с возвратом при неудачном шаге
Задать начальный шаг h0, число проб s n и точность .
Сгенерировать или задать начальную точку X0 и вычислить в ней функцию f; положить i = 1 (i – счетчик проб).
Сгенерировать случайный вектор направления .
На направлении определить точку Xk+1 = Xk + hk k и вычислить в ней функцию f.
Проверить: а) если f(Xk+1) < f(Xk), положить k = k + 1, i = 1 и вернуться на шаг 3; б) если f(Xk+1) f(Xk) и i < s, положить i = i + 1 и вернуться на шаг 3; в) если f(Xk+1) f(Xk), i = s и hk > , положить hk = hk/2, i = 1 и вернуться на шаг 3. г) если f(Xk+1) f(Xk), i = s и hk , поиск закончить, приняв Xk за точку минимума.
Таким образом, поиск останавливается, если в текущей точкеs направлений, сгенерированных подряд, оказались неудачными при шаге, меньшем заданной точности. На рис. 4.37 показан характер движения при поиске по данному алгоритму (жирной линией выделены успешные шаги).
Алгоритм с обратным шагом
Он построен путем модификации предыдущего алгоритма с целью уменьшить число розыгрышей направлений. Внесено следующее изменение: если сгенерированное направление неудачное, то после возврата в исходную точку Xk делается шаг в противоположном направлении; если же и оно неудачное, то генерируется новое направление из точки Xk. Логика действия очевидна: если в данном направлении функция ухудшается, то можно ожидать, что в противоположном направлении она улучшится. Понятно, что эффект модернизации алгоритма тем выше, чем ближе функция в текущей области к линейной.
Алгоритм наилучшей пробы
Здесь используются два шага: пробный и рабочий h. Величина пробного шага соответствует необходимой точности. Задается также число пробных шагов m, меньшее числа переменных n, причем разница между m и n увеличивается с ростом n.
В текущей точке генерируются m направлений j и на них делаются пробные шаги. Вычисляются изменения функции
.
В направлении с наименьшим (отрицательным) приращением fj выполняется рабочий шаг:
.
Поиск заканчивается, если .
По аналогии с предыдущим алгоритмом можно рассматривать и неудачные направления: вычислить . Если максимум соответствует положительному приращению fj, то рабочий шаг делается в противоположном направлении.
Алгоритм статистического градиента
Все параметры и начальные действия такие же, как в предыдущем алгоритме. Отличие состоит в выборе направления движения. Оно определяется с учетом всех разыгранных направлений:
. (4.53)
Направление y называется статистическим градиентом. В пределе (m → ) он стремится к градиенту f. Но определение y требует меньше вычислений, чем f, и тем в большей степени, чем сильнее неравенство m < n.
Согласно (4.53) каждый компонент вектора у вычисляется по формуле
.
Новая точка находится перемещением на рабочий шаг h в направлении статистического антиградиента:
.
Поиск завершается при выполнении условия или
Эффективность рассмотренных алгоритмов можно повысить за счет незначительных изменений их отдельных элементов или шагов. Так, при успешном шаге можно продолжать шаги в найденном направлении до тех пор, пока функция улучшается (использование идеи одномерной минимизации).
Другая возможная модификация заключается во введении в алгоритм процедуры самообучения (адаптации). Это касается вероятностных характеристик случайного вектора . Первоначально все направления этого вектора равновероятны. В процессе поиска накапливается информация об эффективности разыгранных направлений, на основе которой корректируется распределение вероятностей направлений случайного вектора. В результате повышается вероятность удачных направлений при одновременном снижении вероятности неудачных.
Как следует из логики алгоритмов случайного поиска, при прочих равных условиях их эффективность выше вдали от экстремума и снижается по мере приближения к нему, так как падает вероятность выпадения удачных направлений.
Целесообразность применения случайного поиска возрастает с увеличением числа переменных, а при средней и большой размерности он становится практически безальтернативным. В отличие от методов, использующих производные, алгоритмы случайного поиска, как и прямые методы, могут применяться в условиях помех (погрешностей вычислений).