Философские аспекты проблемы систем ИИ




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


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

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

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

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

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

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

поиск глобального экстремума осуществляется несколькими конкурирующими решениями (точками);

условия конкуренции одинаковых для всех решений;

в определенные моменты некоторые "худшие" решения бракуются (уничтожаются);

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

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

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

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




Содержание  Назад  Вперед