Компьютерное моделирование. Лабораторный практикум. Алтаев А.А - 38 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

75
Комментарий по п.5. Если выполняется условие f
r
< f
h
, то это означает, что точка R вполне может быть
принята в качестве новой вершины. Операция замены
H на
R называется отражением. Но имеет смысл проверить и
более отдаленную точку
− E, выбор которой позволит
увеличить размеры многогранника. Такая возможность
увеличения размера позволяет повысить скорость движения
многогранника, что повышает эффективность алгоритма в
случае, если размеры исходного многогранника были
выбраны небольшими и он находится далеко от точки
минимума.
6. Проверяется точка
E в качестве альтернативы
точке
R:
xe
j
=2·x
rj
−
xo
j
.
7. Вычисляется f
e
.
8. Если
f
e
< f
h
, то идти к п. 9, иначе к п. 11.
9. В качестве новой вершины выбирается точка
E
(выполняется
растяжение):
x
hj
=xe
j
.
10. Идти к п. 20.
11. В качестве новой вершины выбирается точка
R
(выполняется
отражение):
x
hj
=xr
j
.
12. Идти к п. 20.
13. Так как точка
R не подходит в качестве новой
вершины (
f
r
> f
h
), то следующей рассматривается точка C,
лежащая посередине отрезка
HO:
2
jhj
j
xox
xc
+
=
.
14. Вычисляется
f
c.
15. Если f
c
< f
h
, то идти к п. 16, иначе к п. 18.
16. В качестве новой вершины выбирается точка
C
(выполняется
сжатие):
76
x
hj
=xc
j
.
17. Идти к п. 20.
18. Так как точки
R и C не подошли в качестве
альтернативы вершине
H, выполняется всеобщее сжатие
многогранника, причем наилучшая вершина
L остается на
месте, а координаты других пересчитываются так, чтобы
они сместились в сторону наилучшей вершины:
.,1,1,1,
2
njni
xx
x
ljij
ij
=+=
+
=
19. Вычисляются функции
f
i
.
20. Выводятся на печать:
l − номер наилучшей
вершины,
f
l
− значение целевой функции в данной вершине,
x
lj
− координаты вершины.
21. Проверяется условие выхода из цикла. Для этого
вычисляется среднеквадратичное отклонение целевых
функций для всех вершин, которое сравнивается с
погрешностью расчета
ε.
1
1
2
1
1
1
1
2
+
+
−
=
∑
∑
+
=
+
=
n
n
f
f
n
i
i
n
i
i
σ
.
Комментарий по п.21. После перемещения
многогранника в область минимума начинают преобладать
операции сжатия и вершины постепенно стягиваются в одну
точку, целевые функции при этом выравниваются по своим
значениям. Это обстоятельство используется для
завершения вычислений.
22. Если
σ < ε, то идти к п. 23, иначе к п. 1.
23. Выводятся на печать:
f
l
− значение целевой
функции в наилучшей вершине,
x
lj
− координаты вершины. 
       Комментарий по п.5. Если выполняется условие fr                                      xhj =xcj .
< fh , то это означает, что точка R вполне может быть             17. Идти к п. 20.
принята в качестве новой вершины. Операция замены H на            18. Так как точки R и C не подошли в качестве
R называется отражением. Но имеет смысл проверить и        альтернативы вершине H, выполняется всеобщее сжатие
более отдаленную точку − E, выбор которой позволит         многогранника, причем наилучшая вершина L остается на
увеличить размеры многогранника. Такая возможность         месте, а координаты других пересчитываются так, чтобы
увеличения размера позволяет повысить скорость движения    они сместились в сторону наилучшей вершины:
многогранника, что повышает эффективность алгоритма в                         xij + xlj
случае, если размеры исходного многогранника были                     xij =               , i = 1, n + 1,       j = 1, n.
выбраны небольшими и он находится далеко от точки                                2
минимума.                                                          19. Вычисляются функции fi .
       6. Проверяется точка E в качестве альтернативы              20. Выводятся на печать: l − номер наилучшей
точке R:                                                   вершины, fl − значение целевой функции в данной вершине,
                          xej =2·xrj − xoj.                xlj − координаты вершины.
       7. Вычисляется fe .                                         21. Проверяется условие выхода из цикла. Для этого
       8. Если fe < fh , то идти к п. 9, иначе к п. 11.    вычисляется среднеквадратичное отклонение целевых
       9. В качестве новой вершины выбирается точка E      функций для всех вершин, которое сравнивается с
(выполняется растяжение):                                  погрешностью расчета ε.
                               xhj =xej .                                                                   2
                                                                                                     n+1 
       10. Идти к п. 20.                                                                             ∑ fi 
       11. В качестве новой вершины выбирается точка R                               n +1
(выполняется отражение):                                                             ∑      f i 2 −  i =1 
                               xhj =xrj .                                                                n +1
                                                                               σ=    i =1
                                                                                                              .
       12. Идти к п. 20.                                                                          n +1
       13. Так как точка R не подходит в качестве новой           Комментарий по п.21. После перемещения
вершины (fr > fh), то следующей рассматривается точка C,   многогранника в область минимума начинают преобладать
лежащая посередине отрезка HO:                             операции сжатия и вершины постепенно стягиваются в одну
                             xhj + xo j                    точку, целевые функции при этом выравниваются по своим
                    xc j =                .                значениям. Это         обстоятельство     используется для
                                  2                        завершения вычислений.
      14. Вычисляется fc.
                                                                  22. Если σ < ε, то идти к п. 23, иначе к п. 1.
      15. Если fc < fh , то идти к п. 16, иначе к п. 18.
      16. В качестве новой вершины выбирается точка C             23. Выводятся на печать: fl − значение целевой
(выполняется сжатие):                                      функции в наилучшей вершине, xlj − координаты вершины.


                             75                                                             76

Страницы