Технологии программирования | страница 119

Редукция — если f(x^>(k)_>n+3) > f(x^>(k)_>h), все векторы (x^>(k)_>i — x^>(k)_>1), i = 1…n + 1 уменьшаются в 2 раза с отсчетом от x^>(k)_>1 в соответствии с формулой x^>(k)_>i = x^>(k)_>i + 0,5(x^>(k)_>i — x^>(k)_>1), i = 1…n + 1. Затем возвращаемся к шагу 1 для продолжения поиска на k + 1 шаге.

Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия среднего квадратичного отклонения функций f(x^>(k)_>i) от произвольного малого числа ε.

Химмельблау воспользовался традиционным математическим стилем для изложения описания алгоритма. Алгоритм имеет структуру вида "спагетти", что видно из схемы алгоритма, разработанной автором (рис. 5.15). Схема в виде "спагетти" — это скрытые go to, которые мы обнаруживаем в тексте программы, разработанной автором. Он же приводит графические рисунки принципа расчета точек и графический рисунок последовательности продвижения лучших точек симплекса по шагам метода при решении тестовой задачи. Затратив 11 страниц текста, приведя текст неструктурированной программы на 12 страницах, автор книги [26] так и не сумел понятно описать свой алгоритм.

Рис. 5.15. Схема алгоритма, разработанная Д. Химмельблау

Сравните способ подачи описания алгоритма, составленный автором [22], и функциональное описание алгоритма после рефакторинга. Функциональное описание алгоритма приведено ниже.

Особенностью алгоритма является продвижение к экстремуму целым облаком пробных точек, который условно назван симплексом (деформируемым многогранником). Общее число точек в симплексе равно увеличенному на единицу числу переменных поиска. Продвижение к экстремуму не по линии от одной точки к другой, а внутри какого-то множества пробных точек обеспечило нереагирование на мелкие дефекты целевой функции и прохождение относительно "широких" оврагов.

Вводимая информация:

n — число переменных минимизируемой функции;

X^>0 = (x^>0_>1, x^>0_>2…, x^>0_>n) — точка первого начального приближения;

h — шаг регуляризации симплекса;

ε_>x — погрешность нахождения экстремума по параметрам.

Работа алгоритма начинается с начальной подготовки симплекса точек. После выполнения процедур регуляризация симплекса и расчета значений целевой функции во всех точках симплекса имеет вид

Процедура регуляризации симплекса состоит в копировании во все поля значений аргументов симплекса значения вектора X