§ 5.3. Альтернативная адаптация в процессах поисковой оптимизации

Рассмотрим структурную адаптацию в процессах поисковой оптимизации [168].

Проблема поисковой оптимизации возникла в связи с необходимостью решения сложных задач типа математического программирования:

возникающих при алгоритмизации процессов управления, принятии оптимальных решений и т. д. Здесь — скалярная функция качества векторного аргумента определенного в области Эта область может быть или континуальной и, задаваться системой равенств и неравенств:

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

или сочетанием этих ограничений. Возможны и другие формы задания области

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

Задача, таким образом, заключается в отыскании хотя бы одного решения X, удовлетворяющего очевидному условию

Суть поискового метода отыскания X сводится к построению последовательности

которая должна сходиться к достаточно малой окрестности решения X. Алгоритм поиска связывает следующие друг за другом состояния:

где фактор предыстории, например — глубина предыстории. Однако удобнее алгоритм определять для смещения

связывающего два соседних состояния в пространстве оптимизируемых параметров

Очевидно, что алгоритм должен удовлетворять определенным требованиям, предъявляемым к процессу поиска решения задачи. Эти требования можно представить в виде набора критериев, характеризующих эффективность процесса поиска:

Каждый из критериев зависит от алгоритма и ситуации сложившейся в процессе оптимизации:

Таким образом, каждый критерий в (5.3.8) имеет вид

Задача выбора оптимального алгоритма сводится тем самым к задаче оптимизации:

где К — оптимизируемый критерий эффективности алгоритма выбранный из множества (5.3.10); Е — множество допустимых алгоритмов, удовлетворяющих остальным критериям из (5.3.10). Решением задачи (5.3.11) является оптимальный алгоритм зависящий, естественно, от ситуации

Введя понятие класса ситуаций

и правило оценки критерия К на этом классе (например, как максимума или среднего на классе), получаем оптимальные алгоритмы поиска. Примерами таких оптимальных алгоритмов являются известные алгоритмы Кифера и Ньютона: первый — для класса одномерных унимодальных функций без случайных помех, заданных на ограниченном интервале, при мини максном критерии оптимальности, связанном с интервалом не определенности в оценке положения экстремума; второй — для класса положительно-определенных квадратичных форм при и отсутствии случайных помех.

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

Представим алгоритм поиска в виде двойки

где — его структура, а — параметры. Такое разделение условно, поскольку нет строго формального критерия выделения структуры алгоритма. Однако интуитивно структурные категории конкретного алгоритма довольно согласованно определяются специалистами по поиску.

Адаптация алгоритма может производиться по двум направлениям. Прежде всего, можно идти традиционным путем

изменения параметров алгоритма С (см. § 3,5, где описаны методы адаптации рабочего шага, объема накопления и параметров распределения случайного шага). Этот вид адаптации имеет ярко выраженный параметрический характер и широко используется при поисковой оптимизации сложных систем. Он хорошо исследован, и его применение не вызывает, как правило, серьезных алгоритмических трудностей [182].

Однако эффект от параметрической адаптации часто бывает не столь высок, как необходимо. Именно это обстоятельство заставляет обращаться к адаптации структуры алгоритма Тогда приходится решать задачу, которая получается путем декомпозиции из (5.3.11):

решением которой является оптимальная структура алгоритма естественным образом зависящая от ситуации Здесь — множество допустимых структур алгоритма — множество допустимых параметров алгоритма, имеющего структуру

Как видно, задача (5.3.14) адаптации структуры является двухуровневой задачей, где на первом уровне решается задача параметрической адаптации (быстрый контур адаптации), а на втором

— задача структурной адаптации (медленный контур) (рис. 5.3.1). Это означает, что каждый шаг структурной адаптации должен сопровождаться целым циклом работы контура параметрической адаптации. В противном случае решение, принятое на верхнем уровне, будет недостоверным из-за того, что значение критерия качества данной структуры оказалось неоптимизированным по параметрам этой структуры.

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

1. Идентификация ситуации из конечного множества [74, 84, 120] опирается на заранее описанное конечное множество альтернативных ситуаций

типа «яма», «овраг», «долина» и т. д. По выбранному критерию

Рис. 5.3.1. Двухкошурная система адаптации алгоритма поиска.

К каждой ситуации соответствует один из альтернативных алгоритмов:

т. е. имеет место определенное соответствие между сложившейся ситуацией и оптимальной структурой алгоритма: которое реализуется функцией Задание (или определение) функции однозначно решает задачу адаптации структуры. Теперь она сводится к идентификации ситуации т. е. к отнесению имеющейся ситуации к одной из множества (5.3.15). Процедура идентификации должна использовать прежде всего результаты работы предыдущего алгоритма, а также специальные тесты, наиболее быстро выявляющие принадлежность текущей ситуации к одной из (5.3.15).

2. Идентификация ситуации из континуального множества. В этом случае каждую ситуацию удобно кодировать вектором

в -мерном пространстве. Каждой точке этого пространства соответствует лучший алгоритм определяемый из очевид ного соотношения

Таким образом, имеет место -классовая задача распознавания образов, построенная на основе конечной обучающей выборки

элементы которой получены заранее путем -кратного решения оптимизационной задачи

где — ситуации, представляющие различные части пространства

Пример [165, 167]. Рассмотрим два алгоритма случайного поиска и (т. е. две альтернативные структуры с нелинейной тактикой —

с линейной тактикой —

(5.3.22)

где случайный шаг. Пространство ситуаций двумерно и образуется двумя вероятностями:

— вероятностью того, что случайный шаг окажется удачным, и

— вероятностью того, что шаг в удачном направлении удачен. Если в качестве критерия воспользоваться средним штрафом, т. е. средним числом неудачных шагов, то пространство нее, квадрат ситуаций разбивается пара болой на две части, соответствующие ситуациям, в которых целесообразно применять один из указанных алго ритмов:

При оба алгоритма по критерию среднего штрафа эквивалентны. Как видно, располагая значениями вероятностей (5.3.23), и (5.3.24), можно «включить» оптимальную в данной ситуации альтернативную структуру Этим задача адаптации сводится к задаче оценивания вероятностей на каждом шаге поиска.

Исходная информация для этой оценки — показатель

Определяющим является либо последний повторный шаг либо случайный либо возвратный Располагая парой

на каждом шаге поиска, можно оценивать искомые вероятности по следующим рекуррентным формулам:

где параметры, отражающие интенсивность изменения ситуации в оптимизируемом объекте в процессе поиска.

Однако предварительная идентификация несвойственна процессам адаптации. Поэтому для структурной адаптации поиска естественно использовать алгоритмы, описанные в § 5.1.

3. Начнем с алгоритмов, реализуемых автоматами с целесообразным поведением (см. п. 5.1.2.1). Приведем примеры реализации различных алгоритмов адаптации поиска [215].

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

которая является аналогом ускорения процесса поиска. Естественно выбрать тот алгоритм, который обеспечивает отрицательное значение этой функции. Тогда под удачей понимаем событие а под неудачей — событие Заметим, что функцию можно ввести и другим образом.

Был проведен ряд модельных экспериментов для исследования такого подхода к альтернативной адаптации алгоритмов поиска [215].

В первой серии экспериментов в качестве алгоритмов оптимизации бьши выбраны два одинаковых алгоритма «с пересчетом» с адаптацией величины рабочего шага [184]:

где — случайные независимые векторы, равномерно распределенные на единичной сфере; Эти алгоритмы отличались друг от друга только параметром согласно которому выбирались коэффициенты исходя из рассмотренного в § 3.5 равенства:

В работах [184, 215] было доказано (см. также § 3.5), что Для гладких модельных функций оптимальная величина асимптотически стремится к 0,27, а для небольших приблизительно равна 0,2. Поэтому естественно в одном алгоритме

взять а во втором, неоптимальном, Работа альтернативной адаптации исследовалась на функции вида

При начальном условии моменты времени переключения алгоритмов определялись следующим образом: т. е. через К тактов. На рис. 5.3.2 показано осредненное на базе десяти экспериментов поведение минимизируемой функции при . Видно, что и эффективность поиска незначительно уступала эффективности оптимального алгоритма (напомним, что — глубина памяти автомата).

На рис. 5.3.3 представлены аналогичные данные для . Как видно, лучшие результаты дает т. е. незначительная глубина памяти.

В следующем эксперименте изучался разброс двуальтернативных адаптивных алгоритмов. На рис. 5.3.4 представлены результаты расчетов для случая Здесь даны лучший и худший (по останову) результаты из десяти и осредненная траектория. Хорошо видно, что разброс невелик и худший

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

(кликните для просмотра скана)

вариант адаптивного алгоритма всегда лучше худшего алгоритма из двух его составляющих, а в среднем он примерно совпадает с лучшим.

Вторая серия экспериментов проводилась с тремя аналогичными алгоритмами случайного поиска. Значения выбирались следующие: Результаты экспериментов полностью повторили данные предыдущей серии: совместная работа трех алгоритмов не хуже, чем работа одного оптимального алгоритма.

В третьей серии экспериментов рассмотрена совместная работа «реальных» поисковых алгоритмов — метода Давидона—Флетчера—Пауэлла и метода случайного поиска «с пересчетом» с адаптацией величины рабочего шага и плотности распределения случайных векторов [182, 220]. В качестве класса минимизируемых функций было выбрано множество функций вида

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

Для функций, в которых присутствуют члены второй суммы (5.3.33), метод не является сходящимся, но для функции (5.3.32) он имеет неоспоримые преимущества перед рассматриваемым методом случайного поиска. Результаты экспериментов подтвердили высокую эффективность использования альтернативного метода структурной адаптации по сравнению с отдельными алгоритмами: для всех функций минимум находился с заданной точностью.

4. Рассмотрим теперь эксперименты по использованию стохастического автомата с переменной структурой (см. для целей альтернативной адаптации поиска [174]. Альтернативные алгоритмы были те же, что и ранее — (5.3.30) и (5.3.31), но с другими значениями параметра Таким образом, априори было известно, что второй алгоритм заведомо хуже первого по быстродействию. Эксперименты показали, что устойчивая работа алгоритма обеспечивалась лишь при дополнительном сглаживании вида

Рис. 5.3.5. (см. скан) Результаты экспериментов, динамика оптимизации для различных значений параметров адаптации. Пунктир — неоптимальный алгоритм штрихпунктир

— оптимальный сплошная линия — алгоритм со структурной адаптацией, — диаграмма переключения алгоритмов для случая

— приращение показателя качества на этапе при работе алгоритма

Параметрами альтернативной адаптации являлись:

— число К тактов, образующих один этап поиска, за время которого происходит оценка

(в течение одного этапа алгоритм поиска не. изменяется);

— параметр сглажи вания оценок (5.1.31) — (5.1.34)

— параметр Р сглажи вания в формуле (5.3.34).

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

Из рисунка видно, что алгоритм поиска со структурной адаптацией всегда лучше худшего в данной ситуации алгоритма. Более того, при удачном выборе параметров адаптации этот алгоритм может работать как лучший (см. рис. 5.3.5, г) или Даже лучше него (см. рис. 5.3.5, в).

Дело в том, что алгоритм переключения включает наилучший по критерию быстродействия алгоритм поиска. Но в процессе параметрической адаптации случайно таким наилучшим может оказаться худший в среднем алгоритм, который и внесет свой вклад в процесс поиска. Это объяснение подтверждается тем, что, хотя в среднем всюду структурная адаптация не исключала полностью что ожидалось в экспериментах (см. рис. 5.3.5, д). Как видно, альтернативная адаптация такого рода позволяет использовать положительные обстоятельства, складывающиеся в процессе оптимизации, и тем самым значительно повысить эффективность процесса поиска.

Заметим в заключение параграфа, что использование подобной альтернативной адаптации в пакете программ оптимизации, осуществляющей «переключение» различных программ пакета, позволяет существенно повысить эффективность работы пакета оптимизации, особенно в обстановке значительной неопределенности относительно специфики структуры решаемой задачи.