Л.А. Растригин - Теория и применение случайного поиска (1121205)
Текст из файла
650,1 т 336 УДК 62-505 ТЕОРИЯ И ПРИМЕНЕНИЕ СЛУЧАИНОГО ПОИСКА. Изд.во «Зинатне», Рига, 1969. АВТОРСКИИ КОЛЛЕКТИВ: А. Т. БАХАРЕВ, А. К. ЗУЕВ, М. М. КАМИЛОВ, Г. А, МЕДВЕДЕВ, Ш. ПЕТРАШ, П. И. ПОПОВ, Л, А. РАСТРИГИП, К, К. РИПА, Б. С. РУБИИШТЕИИ, В, С. ТРАХТЕИБЕРГ В»юнографни рассматриваются и анализируются проблемы случайного поиска как эффективного метода многопараметрической оптимизации сложнмх систем.
большое внимание уделена связи случайного поиска с другими методами оптимальных решений (поисковыми и непонсковымн). Монография имеет обзорный характер, в ней затрагиваются такие актуальные проблемы теории поиска, как обучение, сходимость, планирование экстремальных экспериментов, идентификация, синтез динамических моделей и другис теоретические аспекты случайного поиска.
Кроме того, здесь нашли отражение и прикладные проблемы, связанные с многомерной экстраполяцией, снитезом оптимальных многопороговых логичсскик элементов и оптимальным управлением одним химико-технологическим процессом. Книга рассчитана на инженеров и техников, занимающихся теорией и практикой поисковых самонастраивающихся систем, а также иа лнц, интересую. шихся различными применениями поиска. Табл. !3, илл. 99, библ. 475 паза. Печатаегсл ло решению Редакционно-издательского совета Академии наук Латвийской ССР от 26 сентября 7968 года. 2-2-3 1969-!3 П Р ЕД И СЛ О В И Е Широкое внедрение вычислительных методов в практику инженерных расчетов обеспечило возможность решения задач оптимизации сложных многопараметрических объектов.
Среди различных методов решения задач оптимизации— таких, как линейное и нелинейное программирование, динамическое программирование и т. д. — большое распространение получили поисковые методы оптимизации (градиентные методы, стохастическая аппроксимация и т. д.), среди которых в последнее десятилетие значительное распространение получили методы случайного поиска. Эффективность случайного поиска объясняется хорошей «работоспособностью» при его большой сложности и многоэкстремальности функции качества, которая, кроме того, может быть искажена ошибками измерения.
Существенным является и то обстоятельство, что алгоритмы случайного поиска универсальны н просты для реализации. Поэтому понятен повышенный интерес, проявляемый к теории случайного поиска и ее приложениям со стороны исследователей самых различных специальностей и направлений. Настоящая монография в некоторой степени подводит итог десятилетним исследованиям в области теории случайного поиска. В отличие от предыдущих работ, посвященных в основном исследованию конкретных алгоритмов в частных ситуациях, в монографии сделана попытка рассмотреть проблему в целом и установить место случайного поиска среди прочих алгоритмов оптимизации.
В связи с этим в некоторые главы включены обзоры по соответствующей тематике. В первой главе (автор Л. А. Растригин) предлагается обобщенная схема поиска, описывающая как статистические, так и детерминированные алгоритмы оптимизации. Изложенные в этой главе соображения могут лечь в основу синтеза обобщенных алгоритмов. Общий подход к проблемам поиска рассматривается и во норой главе, написанной 1В.
Г!страшсм. 11а языке теории управляемых марковских процессов здесь сформулированы актуальные проблемы теории поиска и намечены пути их решения. Некоторые из этих проблем нашли свое отражение и в следующих главах книги. Так, в третьей главе (автор К. К. Рипа) с помощью теории марковских процессов исследуются различные способы и эффективность введения обучения при случайном поиске. Необходимость и актуальность исследования подобных вопросов вызвана тем, что, как показывает практика решения многочисленных задач, алгоритмы с обучением являются наиболее аффективными с точки зрения быстродействия н помехоустойчивости. В этой главе методы обучения в основном используются для определения оптимального направления движения к цели.
Однако полное решение задачи синтеза оптимального алгоритма предполагает выбор длины шага, адаптирующейся к свойствач объекта. В связи с этим возникает необходимость определения свойств объекта (его идентификации) в процессе поиска.
Статистическим методам решения проблемы идентификации объекта посвящена четвертая глава (автор А. К. Зуев). Здесь подробно рассматриваются вопросы оценки параметров объекта как в процессе нормальной эксплуатации, так и во время случайного поиска, что дает возможность адаптировать процесс поиска. Известно, что задача оптимизации может решаться и регулярными методами, например градиентным спуском и его модификацией — процедурой Роббинса-Монро.
Поэтому некоторые главы книги посвящены вопросам сравнения эффективности методов случайного поиска с другими известными методами. Так, в пятой главе (автор Я. С. Рубинштейн) сопоставляется случайный поиск со стохастпческой аппроксимацией. Показывается, что по мере усложнения объекта относительная эффективность случайного поиска возрастает как по быстродействию, так и по надежности, Аналогичные результаты получены и в главе шестой (автор П. Н.
Попов), в которой случайный поиск сравнивается по быстродействию с одной из модификаций градиентной процедуры— симплексным методом планирования экстремальных экспериментов. Проведенное сравнение намечает пути к синтезу оптимальных алгоритмов в зависимости от степени сложности объекта. Прп сравнении различных методов поиска в главе седьмой (автор Г. А.
Медведев) применен оригинальный метод вероятностных графов. В отличие от алгебраического подхода к изучению марковских цепей, примененным в главе третьей, здесь рассматриваются и топологические методы, Последующие главы книги в той или иной степени связаны с приложениями методов случайного поиска. В главе восьмой (автор В. С. Трахтенберг) рассматривается применение случайного поиска для определения динамических характеристик стационарного объекта с помощью самонастраивающейся модели.
В случае нестационарного объекта, как показано в главе девятой (написанной также В. С. Трахтенбергом), целесообразно комбинировать поисковые методы с методом многомерной экстраполяции. В главе десятой (автор А. Т. Бахарев) случайный поискприменеи для решения некоторых задач синтеза логических элементов. Как известно, традиционный метод полного перебора неприменим при синтезе достаточно сложных схем. В связи с этим развитие и применение поисковых методов, а в особенности метода случайного поиска, представляется перспективным.
Наконец, в последней, одиннадцатой главе (автор М. М. Камилов) случайный поиск успешно применен в задачах идентификации и оптимизации некоторых конкретных химико-технологических объектов. Следует отметить, что терминология в области поисковой адаптации в настоящее время еще не установилась. Тем более она несовершенна в области случайного поиска. Это, например, нашло свое отражение в терминах «случайный», «статистичесйнй» и «стохастпческий», которые, являясь, по сути дела, синонимами, используются в одном и том же смысле.
Коллектив авторов надеется, что монография окажется полезной для широкого круга инженеров, аспирантов и научных работников, занимающихся вопросами оптимизации сложных систем, и поможет им в решении проблем, выдвигаемых современной наукой. Л, А. Растригин, ГЛАВА ! СТАТИСТИЧЕСКИЕ МЕТОДЫ ПОИСКОВОЙ ОПТИМИЗАЦИИ $ !.!. ПРОБЛЕМА ПОИСКОВОИ ОПТИМИЗАЦИИ Задача поисковой оптимизации сложных многопараметрических систем возникла сравнительно недавно. Исторически эта задача сложилась в результате возрастания сложности проблем оптимизации, которые перестали решаться путем приравниваиия нулю частных производных показателя качества по оптимизируемым параметрам. С другой стороны, появилось большое число задач планирования экспериментов, в которых объект оптимизации был лишен частично или полностью математического описания, что также исключало возможность применения классических методов.
Именно поэтому для решения таких задач оптимизации была предложена поисковая процедура, которая путем последовательного повторения циклов (зтапов) поиска позволяет оптимизировать объект. Пусть Я=Я(Х) — скалярный показатель качества объекта оптимизации, функционально зависящий от вектора состояния Х=- (х!, хъ..., х„). Задача оптимизации может быть сформулирована следующим образом: следует определить состояние Х*„ минимизирующее показатель качества системы при соблюдении заданных ограничений, наложенных на эту систему, т. е.
прп Я(Х*) (Я(Х); й!(Х*) ~~0; Ь!(Х) )О; !=1,2,..., !), где Ь!(Х) — скалярная функция ограничений. На показатель качества и ограничения в общем случае могут накладываться случайные ошибки, препятствующие пх точному определению. Решение такой задачи производится путем поиска, т. е. путем организации такого целенаправленного процесса, в течение которого объект переходит из одного состояния в другое, причем эта последовательность состояний объекта в некотором смысле приближается к искомому решению Х~. В чем состоит процесс поиска? Каковы его особенностиу Рассмотрим общую схему поиска.
В Ьа. ОБЩАЯ СХЕМА ПОИСКА Разобьем весь процесс поиска на однотипные этапы (итерации), на каждом из которых будет самостоятельно решаться задача оптимизации, т. е, в конце этапа объект в некотором смысле должен быть ближе к решению задачи, чем в начале этого этапа. Последовательное повторение таких этапов и позволяет решить поставленную задачу оптимизации. Под этапом поиска будем подразумевать такой законченный цикл действий, в процессе которого производятся следующие операции: а) собирается информация о состоянии объекта оптимизации (т. е. объект идентифицируется); б) на базе имеющейся в памяти и полученной информации принимается решение о переводе объекта в другое состояние, которое предполагается оптимальным с точки зрения выбранного алгоритма; в) объект переводится в это состояние; г) в соответствии с алгоритмами адаптации и самообучения (если таковые имеются) в памяти откладываются сведения, которые могут быть использованы на последующем этапе.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.