Сложный перебор и простой перебор

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

Итеративный поиск предполагает плавное движение от исходной точки по направлению уменьшения результата. Как правило, величина очередного шага определяется историей процесса, а первый и иногда второй и третий шаги делаются практически произвольно.

Если увеличение параметра дает уменьшение целевой функции, то далее осуществляется поиск «вовне», то есть осуществляется дальнейшее его увеличение. Может быть использован метод увеличения на фиксированную величину или увеличения в фиксированное количество раз (то есть на фиксированную величину в логарифмическом масштабе). В случае оптимизации регулятора выбор одного из этих методов не слишком существенен, поскольку при увеличении, например, коэффициента пропорционального регулятора нарушение устойчивости на практике может быть достигнуто достаточно легко – в несколько шагов. Разумеется, если изначально взят слишком маленький коэффициент, и увеличение осуществляется на небольшой процент, то эта процедура может неоправданно затянуться. Поэтому если увеличение параметра приводит к положительным результатам на одном-двух шагах, это может быть основанием увеличивать (например, удваивать) величину последующего увеличения. Это позволяет достаточно быстро достичь такого коэффициента, который будет идентифицирован как излишне большой. После этого поиск будет осуществляться лишь «вовнутрь», то есть интерполяцией.

Если необходимо подобрать один коэффициент с погрешностью 5%, и если имеется граничное значение, то достаточно перебрать 20 значений коэффициентов. Может оказаться, что перебор даст достаточно приемлемый результат по самому простому алгоритму. Например, обычный спуск даст следующую последовательность испытаний (в процентах по отношению к стартовому значению): 100, 95, 90, 85, 80 … и так далее.

 

Дихотомическое деление отрезка

 

Деление отрезков пополам аналогично методу «поразрядного уравновешивания», который используется в аналого-цифровых преобразователях. В этом случае после испытания со значением 100 следует осуществить испытание со значением 50. Но если новая целевая функция будет меньше предыдущей, то не понятно, где находится оптимальное значение – больше или меньше, чем 50. Поэтому для принятия решения требуется осуществить испытания еще и при других значениях, например, при значениях, соответствующих серединам полученных интервалов, то есть при 25 и при 75. Получив значения целевой функции в трех точках (25, 75 и 100) мы должны принять решение, какой из полученных интервалов содержит минимальное значение целевой функции. При этом мы должны согласиться, что, имея три значения, мы не можем утверждать ни об одном из этих значений, что оно не относится к границе отрезка, внутри которого заключено искомое число. Только имея четыре точки, мы могли бы отбросить ту точку, которая соответствует наибольшему значению целевой функции при условии, что она не является внутренней точкой.

Поэтому рассмотренный метод дихотомического деления (деления на два) не является оптимальным.

Рис. 6. Невозможность определения по трем точкам функции Ψ (K) положения отрезка, содержащего минимум

Рис. 7. Принятие по четырем точкам функции Ψ (K) решения об отбрасывании одной крайней точки для дальнейшего уточнения границ отрезка, содержащего минимум

Рис. 6 и 7 иллюстрируют тот факт, что при наличии трех значений целевой функции невозможно определить, к какому отрезку принадлежит минимум, и лишь при наличии четырех точек можно отбросить ту точку, которая является крайней (наименьшей или наибольшей) из четырех и при этом принимает наибольшее значение.

 

Метод золотого сечения

 

 

Метод чисел Фибоначчи

 

Метод локальной оптимизации

 

Метод локальной оптимизации [1, с.182] предполагает при движении из каждой новой точки давать приращение по каждой координате отдельно, получать набор ближайших значений параметров, анализировать набор значений целевых функционалов, и двигаться в направлении минимального из них. В таком случае порядок начертания параметров регулятора не будет иметь значения, в этом смысле этот метод предпочтителен, поскольку движение идет преимущественно по той координате, по которой градиент целевого функционала существенней.

ПРИМЕР 1. Получили регулятор после 5000 шагов [60/40/5]. После следующей итерации, например, получаем [60, 5/40, 2/5, 1]. Изменения всех коэффициентов идут в одну сторону. Поэтому можно предположительно начать новую итерацию не с новых значений, а с тех, которые отличаются от старых на удвоенную величину полученных приращение, то есть [61/40, 4/5, 2].

ПРИМЕР 2. В тех же условиях, что и пример 1, после третьей итерации получаем [60, 8/40, 4/5, 2]. Это говорит о том, что изменения коэффициентов идут монотонно, и в одном направлении, то есть мы достаточно далеки от экстремума. Скорее всего, следует повысить точность в настройках оптимизации, поскольку оптимизация, предположительно, завершается по признаку достаточно малого отличия полученного результата от истинного экстремума, то есть определена слишком грубая точность результата.

 

 

Эволюционные методы

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. Глава 23. Слишком простой выход.
2. Как сделать простой программатор для PIC-ов и AVR-ов
3. Напечатайте простой порядок проведения богослужения
4. Описание метода прямого перебора
5. Последствия несоблюдения простой письменной формы сделки
6. Простой генетический алгоритм
7. Простой и дисконтированный срок окупаемости
8. Простой и переводной вексель
9. Простой категорический силлогизм.
10. Простой категорический силлогизм: определение и структура.
11. Простой производственный процесс
12. ПРОСТОЙ ЧЕЛОВЕК. ПРОСТЫЕ ЛЮДИ