Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод деформируемого многогранника

Читайте также:
  1. A. Методы измерения мертвого времени
  2. HR– менеджмент: технологии, функции и методы работы
  3. I метод.
  4. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  5. I. 2.4. Принципы и методы исследования современной психологии
  6. I. Анализ методической структуры и содержания урока
  7. I. Методические указания к изучению курса

В основу метода деформируемого многогранника (метода Нелдера-Мида [J.A.Nelder, R.Mead]) положено построение последовательности систем то­чек , которые являются вершинами выпуклого многогранни­ка. Точки системы на итерации совпадают с точками системы , кроме , где точка - наихудшая в системе , т.е. . Точка заменяется другой точкой по специальным правилам, описанным ниже. В результате много­гранники деформируются в зависимости от структуры линий уровня целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направ­ление в изогнутых впадинах и сжимаясь в окрестности минимума. Построение последовательности многогранников заканчивается, когда значения функции в вершинах текущего многогранника отличаются от значения функции в центре тяжести системы не более чем на .

Алгоритм:

Шаг 1. Задать координаты вершин многогранника ; параметры отражения , сжатия , растяжения ; число для остановки алгоритма. Положить .

Шаг 2. Среди вершин найти “наилучшую” и “наихудшую” , соответствующие минимальному и максимальному значениям функции:

; ,

а также точку , в которой достигается второе по величине после максимального значение функции .

Шаг 3. Найти “центр тяжести” всех вершин многогранника за исключением наихудшей :

Шаг 4. Проверить условие окончания:

а)если , процесс поиска можно завершить и в качестве приближенного решения взять наилучшую точку текущего многогранника ;

б) если , продолжать процесс.

Шаг 5. Выполнить операцию отражения наихудшей вершины через центр тяжести (рисунок 3.3):

Рисунок 3.3

 

Шаг 6. Проверить выполнение условий:

а)если , выполнить операцию растяжения (рисунок 3.4):

Рисунок 3.4

Найти вершины нового многогранника:

· если , то вершина заменяется на (при многогранник будет содержать вершины , , ). Затем следует положить и перейти к шагу 2;

· если , то вершина заменяется на (при многогранник будет содержать вершины , , ). Далее следует положить и перейти к шагу 2;

б) если , то выполнить операцию сжатия (рисунок 3.5):

Рисунок 3.5

 

Следует заменить вершину на , положить и перейти к шагу 2 (при многогранник будет содержать вершины , , );

в)если , то вершина заменить на . При этом следует положить и перейти к шагу 2;

г) если , выполнить операцию редукции (рисунок 3.6). Формируется новый многогранник с уменьшенными вдвое сторонами и вершиной :

.

Рисунок 3.6

 

При этом следует положить и перейти к шагу 2.

 

Замечание: Нелдер и Мид рекомендуют использовать параметры , , ; Павиани - , , ; Паркинсон и Хатчинсон - , , .

Пример: Найти локальный минимум функции методом деформируемого многогранника:

Решение:

1. Зададим вершины начального многогранника (треугольник, так как n = 2): , , , .

20. Т.к. то .

30. Найдем центр тяжести вершин и :

.

40. Т.к. , процесс продолжается.

50. Выполним отражение:

60. Т.к. то вершина заменяется на . Положим k = k + 1. Переходим к шагу 2.

21. Имеем вершины . Т.к. то .

31. Найдем центр тяжести вершин и :

.

41. Т.к. , процесс продолжается.

51. Выполним отражение:

61. Т.к. то выполним сжатие:

Заменим вершину на . Положим k = k + 1 = 2 и перейдем к шагу 2.

22. Имеем вершины . Т.к. то .

32. Найдем центр тяжести вершин и :

.

42. Т.к. , процесс продолжается.

52. Выполним отражение:

62. Т.к. то выполним редукцию:

.

Положим k = 3 и перейдем к шагу 2.

23. Т.к. то .

33. Найдем центр тяжести вершин и :

.

43. Т.к. , процесс продолжается.

53. Выполним отражение:

.

63. Т.к. то заменим на ,

положим k = 4 и перейдем к шагу 2.

24. Имеем вершины . Т.к. то .

34. Найдем центр тяжести вершин и :

.

44. Т.к. , процесс продолжается.

54. Выполним отражение:

.

64. Т.к. то выполним растяжение:

.

Т.к. то заменим на , положим k = 5 и перейдем к шагу 2.

25. Имеем вершины . Т.к. то .

35. Найдем центр тяжести вершин и :

.

45. Т.к. , процесс продолжается.

55. Выполним отражение:

.

65. Т.к. то заменим на , положим k = 6 и перейдем к шагу 2.

26. Имеем вершины . Т.к. то .

36. Найдем центр тяжести вершин и :

.

46. Т.к. , процесс продолжается.

56. Выполним отражение:

.

66. Т.к. то выполним редукцию:

.

Положим k = 7 и перейдем к шагу 2.

27. Имеем вершины . Т.к. то .

37. Найдем центр тяжести вершин и :

.

46. Т.к. , процесс завершается.

В качестве приближенного решения выбирается наилучшая точка .


Дата добавления: 2015-07-20; просмотров: 598 | Нарушение авторских прав


Читайте в этой же книге: Общие принципы методов поиска безусловного экстремума | Метод сопряженных направлений (метод Пауэлла) | Методы первого порядка | Метод градиентного спуска с постоянным шагом | Метод наискорейшего градиентного спуска (Метод Коши) | Метод Гаусса - Зейделя | Метод Ньютона | Метод Ньютона - Рафсона | Метод Марквардта | Пример отчета по лабораторной работе |
<== предыдущая страница | следующая страница ==>
Метод конфигураций (метод Хука - Дживса)| Метод вращающихся координат (метод Розенброка)

mybiblioteka.su - 2015-2024 год. (0.018 сек.)