Алгоритм случайного поиска

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

Простейший алгоритм – локальный неадаптивный алгоритм случайного поиска следующий (рис. 1).

1. Задаем начальную точку, представленную вектором X0, объявляем ее текущей и вычисляем в ней значений целевой функции.
2. Текущей точке придаем приращение в виде случайного вектора дельта X и вычисляется значение целевой функции.
3. Если значение целевой функции улучшилось, то данную точку делаем текущей.
4. Проверить условие останова. Если оно выполняется, то переходим на шаг 5, в противном случае на шаг 2.
5. Останов.

Рис. 1. Простой неадаптивный алгоритм случайного поиска локального оптимума

Достоинствами данного алгоритма являются его простота, устойчивость и интуитивная понятность. Недостатками – низкая скорость сходимости, а также неопределенность в выборе условия останова.

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

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

Рис. 2. Иллюстрация изменения плотности распределения вероятности для алгоритма случайного поиска (одномерный случай)

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

Литература

1. Сушков Ю.А. Об одном способе организации случайного поиска. Автоматика и вычислительная техника, 1974, № 6, 41-48.
2. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968.
3. Жиглявский А.А. Математическая теория глобального случайного поиска. М.: Изд-во. ЛГУ, 1985.
4. Жиглявский А.А., Жилинская А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.

Связанные понятия

• Математическое программирование
• Оптимизация
• Структурно-параметрический синтез
• Параметрический синтез