3.3.2. Некоторые простейшие алгоритмы случайного поиска

Существует огромное число алгоритмов случайного поиска (из сказанного в конце предыдущего подраздела явствует, что их значительно больше, чем детерминированных). Рассмотрим наиболее характерные из них. Начнем с локальных алгоритмов, глобальным будет посвящен отдельный параграф (§ 3.6).

3.3.2.1. Случайный поиск с линейной тактикой

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

— значение минимизируемой функции на этапе поиска. В зависимости от результата «включается» тот или иной оператор.

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

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

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

Рис. 3.3.3. Графы алгоритма случайного поиска с линейной тактикой: а — при удаче, б — при неудаче.

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

Этот алгоритм можно записать в рекуррентной форме:

где — величина шага — единичный случайный вектор, равномерно распределенный по всем направлениям пространства оптимизируемых параметров Это означает, что все направления случайного вектора равновероятны.

Алгоритм можно изобразить и более компактно в виде одного графа, имеющего условные переходы (рис. 3.3.4, условия реализации переходов — рядом с дугами соответствующих переходов от одного оператора к другому).

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

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

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

Рис. 3.3.4. Граф алгоритма случайного спуска с условными переходами.

Рис. 3.3.5. Граф алгоритма наискорейшего спуска

Легко заметить, что описанный алгоритм целесообразно применять в таких ситуациях, когда часто действует оператор повторения так как именно в эти моменты происходит уменьшение минимизируемой функции. Значит, для эффективной работы алгоритма необходимо, чтобы вероятность была велика, не мала. Например, для линейной функции имеем: т. е. идеальные условия. Следовательно, указанный алгоритм целесообразно применять при оптимизации квазилинейных функций, т. е. вдали от экстремума

Любопытно сравнить этот алгоритм случайного поиска с известным методом наискорейшего спуска [95], который отличается от случайного поиска тем, что вместо оператора случайного шага используется оператор вычисления градиента V:

минимизируемой функции, т. е. Граф алгоритма наискорейшего спуска приведен на рис. 3.3.5. Как видно, спуск в этом случае производится в антиградиентном направлении, т. е. в самом эффективном направлении минимизации для данной локальной ситуации. (Отсюда появилось ошибочное мнение, что лучшего метода, чем наискорейший спуск, и быть не может.) Сравним оба метода для случая, когда величина шага а стремится к нулю. Это означает, что минимум в процессе спуска определяется точно, т. е. решается задача минимизации

где для случайного поиска — случайный вектор, а для наискорейшего спуска Решение а этой задачи дает точку лучше исходной:

где индекс определяет номер этапа поиска.

Естественно сопоставить оба алгоритма для простейших объектов оптимизации. Таким простейшим объектом является квадратичная форма вида

Критерием сопоставления можно выбрать среднее значение отношения Очевидно, чем меньше это отношение, тем лучше алгоритм поиска. Для метода наискорейшего спуска оно имеет вид [95]

Здесь — число обусловленности:

осреднение произведено по случайной начальной точке Для случайного спуска при имеет место следующая оценка [145]:

где М — знак математического ожидания по случайному направлению

Хорошо видно, что по крайней мере при случайный спуск всегда будет эффективнее наискорейшего. Это означает, что плохо обусловленные задачи (их часто называют овражными) лучше решать методом случайного поиска. Действительно, чем больше тем хуже обусловленной и более «овражной» является задача. Случайный поиск всегда — даже для очень овражных задач — дает возможность минимизировать функцию (3.3.17) за один этап при любых начальных условиях. Антиградиентное движение при наискорейшем спуске исключает такую возможность. Преимущество данного алгоритма случайного поиска возникает за счет того, что он обладает большим спектром возможных направлений спуска, чем регулярные алгоритмы.

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