Оптимизационные методы минимизации и максимизации
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
проектируется через центр тяжести оставшихся вершин в новую точку.
Процедура продолжается до тех пор, пока не будет накрыта точка минимума.
Некоторые правила:
. Если вершина с максимальным значением целевой функции построена на предыдущем шаге, то отбрасывается вершина со следующим по величине значением целевой функции.
. Если вокруг одной из вершин начинается циклическое движение, то необходимо уменьшить размеры симплекса.
Поиск заканчивается тогда, когда размеры симплекса или разность значений целевой функции становятся достаточно малыми.
При заданной начальной точке и масштабном множителе , координаты остальных вершин симплекса в - мерном пространстве вычисляются по формуле:
Приращения и определяется по формулам:
Величина выбирается исследователем, исходя из характеристики решаемой задачи. При ребро симплекса имеет единичную длину.
Вычисление центра тяжести:
Если - точка, подлежащая отражению, то координаты центра тяжести определяются по формуле:
Координаты новой вершины удовлетворяют уравнению:
Для того чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, т.е.
Если некоторая вершина симплекса не исключается на протяжении нескольких итераций, то необходимо уменьшить размер симплекса и построить новый симплекс, выбрав в качестве базовой точку с минимальным значением целевой функции.
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку х(0) ;
. Масштабный множитель ?;
3. Приращения ?1 и ?2 ;
.Условие окончания поиска. Перейти к шагу 2.
Шаг 2. Вычислить координаты вершин х(1) и х(2) симплекса. Перейти к шагу 3.
Шаг 3. Определить значения целевой функции в вершинах симплекса. Перейти к шагу 4.
Шаг 4. Вершина, которой соответствует наибольшее значение целевой функции , построена на предыдущей итерации?
Да: отображается вершина, которой соответствует следующее по величине значение целевой функции
Нет: отображается точка с наибольшим значением целевой функции относительно двух других вершин симплекса. Перейти к шагу 5.
Шаг 5. Проверка на условие окончания.
Да: закончить поиск; результат- точка с наименьшим значением целевой функции;
Нет: перейти к шагу 3.
Ход решения :
Исходные данные:
- целевая функция;
Шаг 1. - начальная точка;
- масштабный множитель;
Минимизируем целевую функцию до первого уменьшения размера симплекса:
Пусть масштабный множитель -
;
;
Шаг 2-3.
-я итерация:
- максимально, следовательно, заменяем
Шаг 3-5.
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
8-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
Так как наибольшее значение целевой функции соответствует , которое получено на предыдущей итерации, отбрасываем .
11-я итерация:
Так как наибольшее значение целевой функции соответствует , которое получено на предыдущей итерации, отбрасываем .
-я итерация:
- максимально, следовательно, заменяем
-я итерация:
- максимально, следовательно, заменяем
Симплекс сделал один оборот в области расположения точки , то есть точку при заданных условиях можно считать точкой минимума целевой функции (для получения более точного решения необходимо уменьшить размер симплекса).
Таким образом, точка - точка минимума, значение функции в которой .
Рис 2. Графическое пояснение метода равномерного симплекса
2.2Метод поиска Хука-Дживса
Описание алгоритма:
Процедура Хука-Дживса представляет собой комбинацию "исследующего" поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление направления вдоль "оврагов". Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по "оврагам".
Исследующий поиск:
Для проведения исследующего поиска необходимо задать величину шага, которая может быть различна для разных координатных направлений, и изменяться в процессе поиска. Поиск начинается в некоторой исходной точке. Делается пробный шаг вдоль одного из координатных направлений. Если значение целевой функции в пробной точке меньше, чем в исходной, то шаг считается удачным. В противном случае возвращаются в исходную точку и делают шаг в противоположном направлении. После перебора всех координат исследующий поиск заканчивается. Получен