С. Н. Гринченко Поисковая оптимизация
| скачать Методы поисковой оптимизации при моделировании приспособительного поведения и эволюции природных систем С.Н.Гринченко Поисковая оптимизация – последовательность действий, реализующих неизвестную a priori траекторию движения к экстремуму оптимизируемой функции: класс итеративных процессов оптимизации, использующийся в тех случаях, когда аналитическая зависимость целевой функции от оптимизационных переменных либо неизвестна, либо её вычисление представляет собой сложную задачу. В обоих случаях от целевой функции  требуется только возможность измерения (вычисления) в области определения её переменных  . Поисковый метод описывается итеративным процессом (рекуррентным выражением), определяющим переход от (N-1)-го шага к N-му:  , причем шаг  зависит от ситуации в точке  ; в простейшем случае  , где  - алгоритм поискового процесса оптимизации. В более сложном случае адаптивной поисковой оптимизации сам вид и параметры функции зависят от более глубокой предыстории поиска [1]. Таким образом, когда количество начальной информации об объекте недостаточно для достижения цели управления, естественный путь восполнения – определение её в процессе поиска. Поисковая оптимизация применяется для решения как статических задач (целевая функция в которых не зависит от времени), где её целесообразно называть собственно поисковой оптимизацией, так и динамических (в последнем случае её традиционно называют экстремальным управлением объектом, характеристики которого от времени зависят). Важнейшим направлением теории поисковой оптимизации является теория случайного поиска, впервые изобретенного в 1959 году Л.А.Растригиным. Начиная с 70-х гг. получило широкое распространение одно из направлений теории поисковой оптимизации, связанное с методологией синтеза новых алгоритмов на базе бионических представлений. В частности, использования для этого моделей эволюции живой природы: эволюционного подхода (Г.Бремерманн), «эволюционного моделирования» (Л.Фогель, А.Оуэнс, М.Уолш, И.Л.Букатова), эволюционного формообразования (А.И.Половинкин), эволюционной глобальной оптимизации (Э.М.Куссуль, А.Лук; Р.Джарвис), эволюционной адаптации коллективом вероятностных автоматов (Ю.И.Неймарк с соавт.), «эволюционной стратегии» (И.Рехенберг, Г.-П.Швефель, К.Беллман, Дж.Борн), «генетической адаптации» (У.Петерзон, К.Восс, К.Вебер), «генетических алгоритмов» (Дж.Холланд, Д.Голдберг, Д.И.Батищев, В.М.Курейчик, С.А.Исаев и др.) и тому подобных. Использование именно эволюционной и генетической терминологии оказалось удобным языком при синтезе широкого спектра новых разновидностей алгоритмов поисковой оптимизации. Среди авторов бионических работ в области поисковой оптимизации, опирающихся на аналогии с иными биологическими объектами, следует упомянуть В.Ф.Коропа, Л.Н.Фицнера, Л.А.Растригина, Н.П.Дидиченко и др.). Близки к ним и «муравьиные алгоритмы» (М.Дориго) – подробности см. в [2]. Наряду с использованием биологических аналогий для синтеза новых алгоритмов поисковой оптимизации, т.е. с движением от биологии к технической кибернетике, поисковая оптимизация используется и при моделировании самих биологических (и других природных) систем, т.е. налицо и обратное движение: от технической кибернетики к биологии [2-3]. В этих моделях алгоритмы поисковой оптимизации реализуют приспособительное поведение и/или эволюцию моделируемого объекта посредством подбора (поиска) таких комбинаций его соответствующих параметров, которые соответствуют движению (в функциональном пространстве параметров) в направлении экстремума зависящих от них целевых критериев (энергетического характера). Тем самым воспроизводится присущая этим объектам активность, которая здесь интерпретируется как «поисковая». В системе неживой природы алгоритмы поисковой оптимизации реализуют характерные для неё вариационные принципы (опять таки энергетического характера). При таком моделировании используются различные варианты алгоритма адаптивного случайного поиска, поскольку именно этот механизм является средством – по-видимому, единственно адекватным – моделирования поведения системы природы. Действительно, довольно трудно представить себе некоторый живой объект, параметры адаптивного поведения которого (например, значение градиента целевой функции) рассчитывались бы в каком-то гипотетическом вычислительном блоке (что необходимо для любого регулярного метода оптимизации). Применительно же к адаптивному случайному поиску – это вполне реально, поскольку он не требует никаких подобных вычислений, а оценивает искомый градиент на базе нескольких имеющихся конкретных реализаций целевой функции (экстремального вида). Адаптивный случайный поиск по определению всегда содержит, помимо вероятностной, существенную регулярную составляющую. Это может, в частности, выражаться в различии вероятностей выбора величин приращений по каждой из координат поискового пространства (т.е. поиск осуществляется не в гипершаре, а в гиперконусе), в ненулевой глубине памяти алгоритма адаптации и т.п. Может возникнуть вопрос: насколько оптимизационная модель соответствующего биообъекта отличается от типовой, знакомой по аналогичным приложениям? Не отменяет ли её появление имеющихся наработок? Проведем их сравнение (см. рис. 1). Простейшую схему типовой модели некоторого неиерархического объекта можно представить себе следующим образом:  (обозначения приведены на рис. 1а). Принципиальное отличие поисково-оптимизационной модели от типовой заключается во введении в её состав дополнительно всего 2-х основных блоков: блока вычисления целевой функции (ЦФ) энергетического характера  и собственно блока оптимизации – генератора поисковой переменной  . При этом два последних блока непосредственно соединяются между собой: выход первого (целевая функция  ) поступает на вход второго (оптимизатора), управляя им.  Рис. 1. Упрощенные схемы типовой и «поисково-оптимизационной» моделей некоторых биообъектов Что же касается связи между выходом оптимизатора и входом блока вычисления целевой функции, то, как раз, здесь и находится все разнообразие элементов модели и связей между ними, характерное, в том числе, и для «типовой» модели объекта. Таким образом, два вышеуказанных блока образуют некоторый «каркас» модели, обеспечивающий её приспособительное поведение. Всё же остальное разнообразие функциональных связей, отражающих специфику конкретного объекта, введение такого «каркаса», вообще говоря, непосредственно не затрагивает. Конечно, рассмотрение объекта как самооптимизирующегося само по себе является источником новых идей относительно структуры его модели и предложений по наиболее адекватному их воплощению, но, повторюсь, поисково-оптимизационная модель – это фактически соответствующее расширение (надстройка) типовой модели. Другой ракурс их сравнения: переходная функция  типовой модели фиксирована (именно её часто и называют моделью объекта). В оптимизационной же модели переходная функция  зависит от поисковой переменной , перманентно изменяющейся блоком оптимизации. В ситуации найденного устойчивого состояния объекта, когда поисковый процесс представляет собой лишь небольшие рыскания в районе экстремума оптимизируемой функции , изменения переходной функции также будут весьма малыми. Тем самым воспроизводится вариант, близкий к типовому (т.е. с «почти» фиксированной переходной функцией ). В ситуации же процесса обнаружения (поиска) такого устойчивого состояния переходная функция изменяется слишком значительно, и её фиксация невозможна из-за неминуемой потери принципиально важной информации о поведении моделируемого биообъекта. В заключение уместно высказать надежду, что широкое распространение методики моделирования природных объектов с использованием алгоритмов адаптивной поисковой оптимизации позволит синтезировать их модели, демонстрирующие адекватное приспособительное и эволюционное поведение (см. [2-3]). Литература 1. Растригин Л.А. Адаптация сложных систем. Методы и приложения. Рига: Зинатне, 1981. 375 с. 2. Гринченко С.Н. Системная память живого (как основа его метаэволюции и периодической структуры). М.: ИПИРАН, Мир, 2004. 512 с. – см. также http://www.ipiran.ru/publications/publications/grinchenko/ 3. Гринченко С.Н. Метаэволюция (систем неживой, живой и социально-технологической природы). М.: ИПИРАН, 2007. 456 с. – см. также http://www.ipiran.ru/publications/publications/grinchenko/book_2/
|
Ваша оценка этого документа будет первой.
Ваша оценка: 