7.1.1.5 Метод деформируемого многогранника (метод Нелдера—Мида)
Данный метод состоит в том, что для минимизации функции ппеременныхf(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому векторух.Вычисляются значения целевой функцииf(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершинах[h].Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точках[q] с меньшим значением целевой функции, чем в вершинех[h] (рис. 7.5). Затем исключается вершинах[h].Из оставшихся вершин и точкиx[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.
Рис. 7.5 ‑ Геометрическая интерпретация метода деформируемого многогранника
Введем следующие обозначения:
x[i, k] =(x1[i, k], …,xj[i, k], …,xn[i, k])T
где i = 1, ..., п+ 1;k =0, 1, ..., - i-я вершина многогранника наk-м этапе поиска;х[h, k]—вершина, в которой значение целевой функции максимально, т. е.f(х[h, k] = max{f(x[1,k]), …,f(x[n+1,k])};х[l,k]-вершина, в которой значение целевой функции минимально, т. е.f(х[l,k]) =min {f(x[1,k]), …,f(x[n+1,k])};х [п+2,k]-центр тяжести всех вершин, за исключениемх[h, k]. Координаты центра тяжести вычисляются по формуле
Алгоритм метода деформируемого многогранника состоит в следующем.
1. Осуществляют проецирование точки х[h, k] через центр тяжести:
x[n+3, k] =x[n+2, k] + a(x[n+2, k] - x[h, k]) ,
где а> 0 - некоторая константа. Обычноа =1.
2. Выполняют операцию растяжения вектора х[n+3, k]- х[n+2, k]:
x[n+4, k] =x[n+2, k] + (x[n+3, k] - x[n+2, k]),
где > 1 - коэффициент растяжения. Наиболее удовлетворительные результаты получают при 2,8 <=<= 3.
Если f(x[n+4,k]) <f(х[l,k]), тох[h , k] заменяют наx[n+4, k] и продолжают вычисления с п. 1 приk = k +1. В противном случаех[h, k] заменяют нах[n+3, k] и переходят к п. 1 приk = k+ 1.
3. Если f(x[n+3, k])> f(х[i, k])для всехi, не равныхh,то сжимают векторx[h, k] - x[n+2, k]:
x[n+5, k] =x[n+2, k] +(х[h, k] – x[n+2, k] ), где> 0 - коэффициент сжатия. Наиболее хорошие результаты получают при 0,4 <=<= 0,6.
Затем точку х[h, k] заменяют нах[n+5, k] и переходят к п. 1 приk = k+ 1.
4. Если f(x[n+3, k])>f(x[h, k]), то все векторых[i, k] - х[l,k] . i=1,...,п + 1, уменьшают в два раза:
x[i, k] = x[l, k] + 0,5(x[i, k] - x[l, k]) .
Затем переходят к п. 1 при k= k+ 1.
В диалоговой системе оптимизации выход из подпрограммы, реализующей метод деформируемого многогранника, осуществляется при предельном сжатии многогранника, т. е. при выполнении условия
, (7.10)
где e = (е1 ,..., еn)‑ заданный вектор.
С помощью операции растяжения и сжатия размеры и форма деформируемого многогранника адаптируются к топографии целевой функции. В результате многогранник вытягивается вдоль длинных наклонных поверхностей, изменяет направление в изогнутых впадинах, сжимается в окрестности минимума, что определяет эффективность рассмотренного метода.
- Основы информационных технологий
- Оглавление
- Предисловие
- Современные информационные технологии
- 1.1 История, современное состояние и перспективы развития вычислительной техники
- 1.2 Элементная база, архитектура, сетевая компоновка, производительность
- 1.3 Понятие информации. Классификация и виды информационных технологий
- Основные свойства информационных технологий.
- 1 .4 Операционные системы
- 2 Основные программные средства информационных технологий
- 2.1. Программное обеспечение. Текстовые редакторы, их возможности и назначение
- 2.2. Графические редакторы
- 2.3. Электронные таблицы
- 2.4. Сервисные инструментальные программные средства
- 2.5. Системы математических вычислений MatLab
- 2.6 Система подготовки презентаций
- 3 Сетевые технологии и интернет
- 3.1 Классификация компьютерных сетей
- 3.2 Семиуровневая модель структуры протоколов связи
- 2.3. Взаимодействие компьютеров в сети
- 3.3 Организационная структура Internet
- 3.4 Инструментальные средства создания web-сайтов. Основы web-дизайна
- 3.5 Языки разметки гипертекста html и xml
- 3.6 Скриптовые языки программирования
- 4 Системы управления базами данных
- 4.1. Классификация систем управления базами данных
- 4.2 Модели данных
- 4.3 Моделирование баз данных
- 4.4 Архитектура и функциональные возможности субд. Языковые и программные средства субд
- 4.5 Общая характеристика субд ms Access
- 4.6 Основные объекты ms Access
- 4.7 Основы языка sql
- Контрольные вопросы
- 5 Защита информации при использовании информационных технологий
- 5.1 Основы информационной безопасности
- 5.2. Методы и средства защиты информации
- 5.3 Защита от несанкционированного доступа к данным
- 5.4 Классы безопасности компьютерных систем
- 5.5 Основные аспекты построения системы информационной безопасности
- 6 Математическое моделирование и численные методы
- 6.1 Математические модели и численные методы решения задач в различных предметных областях
- 6.2 Численное дифференцирование и интегрирование
- 6.2.1 Особенность задачи численного дифференцирования
- 6.2.2 Интерполяционная формула Лагранжа для равноотстоящих узлов
- 6.2.3 Численное дифференцирование на основе интерполяционной формулы Лагранжа
- 6.2.4 Численное дифференцирование на основе интерполяционной формулы Ньютона
- 6.2.5 Постановка задачи численного интегрирования
- 6.2.6 Квадратурные формулы Ньютона-Котеса
- 6.2.7 Формула трапеций
- 6.2.8 Формула Симпсона
- 6.2.9 Оценка точности квадратурных формул
- 6.3 Методы решения обыкновенных дифференциальных уравнений
- 6.3.1 Задача Коши и краевая задача
- 6.3.1.1 Классификация уравнений
- 6.3.1.2 Задача Коши
- 6.3.2 Одношаговые методы решения задачи Коши
- 6.3.2.1 Метод Эйлера
- 6.3.2.2 Модифицированный метод Эйлера
- 6.3.2.3 Метод Рунге-Кутта четвертого порядка
- 6.3.2.4 Погрешность решения и выбор шага
- 6.3.3 Многошаговые методы решения задачи Коши
- 6.3.3.1 Многошаговые методы
- 6.3.3.2 Метод Адамса
- 6.3.3.3 Методы прогноза и коррекции (предиктор-корректор)
- 6.3.3.4 Общая характеристика многошаговых методов
- 6.3.4 Краевая задача и метод стрельбы
- 6.3.4.1 Краевая задача
- 6.3.4.2 Метод стрельбы
- 6.3.4.3 Метод стрельбы для линейного дифференциального уравнения
- 6.4 Решение дифференциальных уравнений в чстных производных
- 6.4.1 Краткие теоретические сведения
- 6.4.2 Классификация уравнений по математической форме
- 6.4.3 Основы метода конечных разностей
- 6.4.3.1 Построение сетки
- 6.4.3.2 Аппроксимация уравнения эллиптического типа
- 6.4.3.3 Аппроксимация уравнения гиперболического типа
- 6.4.3.4 Аппроксимация уравнения параболического типа
- 6.4.3.5 Погрешность решения
- 6.4.4 Основы метода конечных элементов
- 6.4.4.1. Формирование сетки
- 6.4.4.2 Конечно-элементная аппроксимация
- 6.4.4.3 Построение решения
- 6.6 Элементы математической статистики
- 6.6.1 Генеральная совокупность. Выборка. Статистические ряды
- 6.6.2 Графическое изображение вариационных рядов. Эмпирическое распределение
- 6.6.3 Средние величины и показатели вариации
- 6.6.4 Средняя арифметическая и ее свойства
- 6.6.5 Дисперсия и ее свойства. Среднее квадратическое отклонение
- 6.6.6 Коэффициент вариации
- 6.6.7 Структурные средние
- 6.6.8 Законы распределения случайных величин
- 6.6.9 Статистические гипотезы
- 7 Методы оптимизации и системы поддержки принятия решений
- 7.1 Характеристика методов решения задач оптимизации
- 7.1.1 Численные методы безусловной оптимизации нулевого порядка
- 7.1.1.1 Основные определения
- 7.1.1.2 Классификация методов
- 7.1.1.3 Общая характеристика методов нулевого порядка
- 7.1.1.4 Метод прямого поиска (метод Хука-Дживса)
- 7.1.1.5 Метод деформируемого многогранника (метод Нелдера—Мида)
- 7.1.1.6 Метод вращающихся координат (метод Розенброка)
- 7.1.1.7 Метод параллельных касательных (метод Пауэлла)
- 7.1.2 Численные методы безусловной оптимизации первого порядка
- 7.1.2.1 Минимизация функций многих переменных. Основные положения
- 7.1.2.2 Метод наискорейшего спуска
- 7.1.2.3 Метод сопряженных градиентов
- 7.1.3 Численные методы безусловной оптимизации второго порядка
- 7.1.3.1 Особенности методов второго порядка
- 7.1.3.2 Метод Ньютона
- 7.2 Линейное программирование
- 7.2.1 Транспортная задача линейного программирования
- 7.2.1.1 Постановка задачи
- 7.2.1.2 Венгерский метод
- 7.2.1.3 Метод потенциалов
- 7.3 Прямые методы условной оптимизации
- 7.3.1 Основные определения
- 7.3.2 Метод проекции градиента
- 7.3.3 Комплексный метод Бокса
- 7.4 Методы штрафных функций
- 7.4.1 Основные определения
- 7.4.2 Методы внутренних штрафных функций
- 7.4.3 Методы внешних штрафных функций
- 7.4.4 Комбинированные алгоритмы штрафных функций
- 7.5 Информационные технологии поддержки принятия решений
- 7.6 Информационные технологии экспертных систем Характеристика и назначение
- Список литературы