Читайте также:
|
|
Алгоритм, описанный в разд. 3.5.1, можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины n вместо вершины х n, соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках;
(3.39)
Геометрическая иллюстрация этих процедур для пространства E 2 приведена на рис. 3.5 и 3.6. Так как величина a Î (0; 1), то выбор точек z1 и z2 соответствует сжатию симплекса; b» 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. Численные эксперименты показывают, что этот
алгоритм хорошо работает в пространстве E n для п £ 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х0 Î E n, по формулам
, (3.40)
где e i – i– й базисный вектор; a – параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек z i в формулах (3.39):
a = 1/2, b = 1 и g =2.
Рис. 3.5. Пробные точки z1,z2,z3,z4 для перехода к новому симплексу
Рис. 3.6. Новые симлексы полученные в результате процедур сжатия (а,б); отражения (в); растяжения(г).
Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.
Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовую точку х0, параметр a и построить начальный симплекс по формулам (3.37) или (3.40). Вычислить f (х0).
Шаг 1. Вычислить значения функции в вершинах симплекса х1,..., x n.
Шаг 2. Упорядочить вершины х0,..., x n так, чтобы f (х0) £ … £ f (х n).
Шаг 3. Проверить достижение заданной точности (условие (3.38)). Если оно выполняется, то вычисления завершить, полагая х *» х0, f *» f (х0). Иначе – перейти к шагу 4.
Шаг 4. Найти и пробные точки z k, k= 1, …, 4 пo формулам (3.39). Найти f (z*)= min f (z k). Если f (z*) < f (z n). то положить x n =z* и перейти к шагу 2. Иначе – перейти к шагу 5.
Шаг 5. Уменьшить симплекс, полагая х i = (х i + х0)/2, i = 1,.., n и перейти к шагу 1.
Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки х0 снова строят симплекс по формулам (3.37) или (3.40), полагая а = ||x0–x n ||.
С теоретической точки зрения описанные методы минимизации слабо исследованы, однако практика показывает их работоспособность.
Перейдем теперь к описанию вычислительных процедур вида
(3.31): x k+\ = x k +a kpk. В зависимости от способа выбора направления pk и шага a k получаются различные алгоритмы минимизации.
Дата добавления: 2015-05-05; просмотров: 11 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
МИНИМИЗАЦИЯ ПО ПРАВИЛЬНОМУ СИМПЛЕКСУ | | | АЛГОРИТМ ХУКА – ДЖИВСА |