Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия среднего квадратичного отклонения функций f(x(k)i) от произвольного малого числа ε.
Химмельблау воспользовался традиционным математическим стилем для изложения описания алгоритма. Алгоритм имеет структуру вида "спагетти", что видно из схемы алгоритма, разработанной автором (рис. 5.15). Схема в виде "спагетти" — это скрытые go to, которые мы обнаруживаем в тексте программы, разработанной автором. Он же приводит графические рисунки принципа расчета точек и графический рисунок последовательности продвижения лучших точек симплекса по шагам метода при решении тестовой задачи. Затратив 11 страниц текста, приведя текст неструктурированной программы на 12 страницах, автор книги [26] так и не сумел понятно описать свой алгоритм.
Рис. 5.15. Схема алгоритма, разработанная Д. Химмельблау
Сравните способ подачи описания алгоритма, составленный автором [22], и функциональное описание алгоритма после рефакторинга. Функциональное описание алгоритма приведено ниже.
Особенностью алгоритма является продвижение к экстремуму целым облаком пробных точек, который условно назван симплексом (деформируемым многогранником). Общее число точек в симплексе равно увеличенному на единицу числу переменных поиска. Продвижение к экстремуму не по линии от одной точки к другой, а внутри какого-то множества пробных точек обеспечило нереагирование на мелкие дефекты целевой функции и прохождение относительно "широких" оврагов.
Вводимая информация:
n — число переменных минимизируемой функции;
X0 = (x01, x02…, x0n) — точка первого начального приближения;
h — шаг регуляризации симплекса;
εx — погрешность нахождения экстремума по параметрам.
Работа алгоритма начинается с начальной подготовки симплекса точек. После выполнения процедур регуляризация симплекса и расчета значений целевой функции во всех точках симплекса имеет вид
Процедура регуляризации симплекса состоит в копировании во все поля значений аргументов симплекса значения вектора X0, и далее производятся изменения значений диагональных компонент векторов с номерами от 2 до n + 1 путем их увеличения на шаг регуляризации симплекса h.
В симплексе Q1, Q2, Q3…, Qn+1 — это рассчитанные значения минимизируемой функции при соответствующих по строке значениях аргументов минимизируемой функции.
Далее до выполнения условия окончания поиска осуществляются итерации (шаги) поиска. Условием окончания поиска этого метода является неудаленность от лучшей точки симплекса остальных точек симплекса более чем на e2x.
Каждая итерация начинается с нахождения номеров l и k, соответственно лучшей и худшей по значению функции точек симплекса. Далее осуществляется расчет точки Xц — положения центра масс всех точек симплекса за исключением наихудшей точки 1. Это позднее улучшение алгоритма. Д. Химмельблау не исключал наихудшей точки.
где n — количество точек в симплексе; i — номер компоненты вектора X(i = 1, 2…, n); j — номер точки в симплексе.
Считаются нулевыми значения xkj слагаемых сумм, где k — номер наихудшей точки.
При работе метода на каждой из итерации может вычисляться одна из особых пробных точек: а — точка отражения, р — точка растяжения, у — точка сжатия. Точки вычисляются по формулам:
Xα = Xц + α(Xц — Xk), Xβ = Xц + β(Xц — Xk), Xγ = Xц + γ(Xц — Xk).
Целесообразно эти похожие формулы реализовать одной функцией.
Значения коэффициентов α = 1, β = 0,5 и γ = 2 подобраны экспериментальным путем (в оригинале описания алгоритма эти значения можно выявить лишь из текста программ). Расчет точек α, β, γ целесообразно осуществлять одной процедурой с параметром в виде значений коэффициентов α, β, γ.
После расчета точки Xц вычисляется пробная точка α. Далее выполняется одно из альтернативных действий.
Если Qα ≤ Q1, то выполняются действия достижения сильного успеха. Если Q1 ≤ Qα < Qk, то имеется слабый успех, а точка α записывается на место k-точки. Если Qα ≥ Qk, то выполняются действия отсутствия успеха. Рассчитывается Xβ и Qβ. Далее, если Qβ ≤ Qk, то точка β записывается на место k-точки, иначе, если точка β хуже точки k, выполняется процедура редукции симплекса и процедура расчета значения функции в точках симплекса.
Действия достижения сильного успеха. Рассчитывается Xγ и Qγ. Наилучшая из точек α или β записывается на место наихудшей k-точки симплекса.
Действия отсутствия успеха. Рассчитывается Xβ и Qβ. Далее выполняется действие по изменению симплекса при отсутствии успеха.
Действие по изменению симплекса при отсутствии успеха представляет собой альтернативу: если Qβ ≤ Qk, то точка β записывается на место k-точки, иначе, если точка β хуже точки k, выполняется процедура редукции симплекса.
При выполнении процедуры редукции симплекса все точки симплекса стягиваются к лучшей точке симплекса на половину своего прежнего удаления и далее выполняется процедура расчета значений целевой функции во всех точках симплекса.
5.8. КОДИРОВАНИЕ ТИПОВЫХ СТРУКТУР НА ЯЗЫКАХ ПРОГРАММИРОВАНИЯ
Обычно разработку алгоритмов программ совмещают с кодированием текста программы. Отдельное от программирования написание алгоритмов практически ничем не отличается от написания инструкций.
Кодирование программы должно осуществляться только с использованием стандартных структур! Запрещено использование меток, операторов безусловного перехода на метку (go to), операторов досрочного выхода из структуры break!
При кодировании на языке С оператор break может использоваться только при кодировании структуры switch.
При использовании другого процедурно-ориентированного языка программирования (не Pascal) необходимо предварительно закодировать на используемом языке программирования все описанные в этом подразделе стандартные структуры без изменения их логики!
Так, при программировании на языке С структура УНИВЕРСАЛЬНЫЙ ЦИКЛ — "ДО" будет включать операцию "!" (НЕ):
/* подготовка цикла */
do
{
/* Тело цикла */
…
}
while (! (L));
В приведенной выше структуре ненулевое значение переменной L соответствует окончанию выполнения цикла, а не его продолжению выполнения, как в операторе языка программирования! Использование "линией" операции (!) НЕ никак не удлинит программу. Современные компиляторы автоматически инвертируют логическое условие завершения цикла.
Структуре СЛЕДОВАНИЕ в программах могут соответствовать: выполнение всей программы; вызов процедуры.
Согласно стандарту проекта, АЛЬТЕРНАТИВА имеет четыре конструкции. Рассмотрим их запись на языке программирования Pascal.
Конструкция для одной альтернативы:
if L then begin