Алгоритм поиска глобального экстремума

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

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

Приведем основные рекомендации построения процедур СДС и ШЛП.

В некоторых случаях построение процедуры СДС можно свести к предварительному составлению набора допустимых структур, из которого выбирают структуры при каждом обращении к процедуре СДС. Если суть этой процедуры состоит в выборе по возможности допустимого набора переменных структурной оптимизации, то представляется полезным включать в нее правила выбора переменных, основанные на эвристических соображениях, аналитических и экспериментальных исследованиях, изучении опыта проектирования и эксплуатации аналогичных TО. Для некоторых сложных или малоизученных задач проектирования трудно построить процедуру СДС, обеспечивающую получение допустимых структур. В этом случае в процедуру целесообразно включать операции преобразования недопустимых структур в допустимые. Набор таких операций можно составить из подходящих эвристических приемов (для задач, связанных с техническими объектами, сборники таких приемов можно найти в соответствующей литературе, в которой решение изобретательских задач рассматривается более подробно). Преобразование недопустимых структур в допустимые можно также решать как задачу оптимизации. В диалоговом режиме работы санкцию процедуры СДС может взять на себя проектировщик.

В целом по процедуре СДС можно дать следующие рекомендации, направленные на повышение вероятности выбора допустимых структур и снижение объема вычислений по оценке недопустимых:

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

Процедуры ШЛП включают обычно способы изменения переменных, ориентированные на решение задач как структурной, так и параметрической оптимизации. Приведенные рекомендации по построению процедур СДС можно использовать и при построении способов локального изменения дискретных переменных. Для изменения непрерывных переменных, как правило, применяют различные алгоритмы локального поиска. Ниже указаны наиболее предпочтительные (о ГА смотри замечание ниже).

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

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

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

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

Для удобства изложения алгоритма решение будем называть также точкой (в многомерном пространстве поиска) и независимо от того, решается ли задача параметрической оптимизации (1)—(4) или задача структурной оптимизации (6)—(9), будем обозначать его X.

Содержание раздела