Статистические методы поиска. Р а с т р и г и н Л. А., Главная редакция физико-математической литературы изд,-ва «Наука», 1968 г., 376 стр. Книга посвящена теории статистических методов поиска. В работе исследуются локальные свойства различных алгоритмов случайного поиска, приводятся оценки эффективности рассматриваемых алгоритмов, Исследование ограничивается изучением в основном локально-адаптирующихся алгоритмов случайного поиска. Как средство улучшения дисперсных свойств случайного поиска, его надежности рассмотрен поиск с накоплением в присутствии помех. Значительное место в книге уделено исследованию процессов самообучения при поиске, сводящихся к целенаправленному изменению вероятностных характеристик поиска. Изучены два вида самообучения: покоординатное, когда изменяются вероятностные свойства вдоль каждой из управляемых координат, и непрерывное, при котором преимущественное направление поиска может быть любым. В связи с рассматриваемым в книге кругом вопросов затронуты проблемы, касающиеся статистических методов глобального поиска, исследован ряд алгоритмов, В настоящей монографии содержится обширный фактический материал, иллюстрирующий эффективность рассматриваемых алгоритмов, приводятся результаты экспериментального решения ряда «тестовых» задач. Табл. 6. Илл. 165. Библ. 78 назв.
ПРЕДИСЛОВИЕ Развитие методов поисковой оптимизации сложных многопараметрических объектов, а также теории и практики поисковых самонастраивающихся систем привело к необходимости создания теории поисковой многопараметрической оптимизации сложных систем. Отличительным свойством этих систем является поиск, который обеспечивает получение информации, необходимой для управления объектом. В зависимости от характера поиска в области теории и практики многопараметрической оптимизации выделились два направления. Первое направление рассматривает поиск как вполне регулярный процесс-сбора и обработки информации об объекте. Второе направление подразумевает намеренное введение элемента случайности в алгоритм поиска. Эта случайность служит целям сбора информации о поведении объекта и целям управления. В ряде случаев введение такого случайного поведения дает возможность построить весьма простые и эффективные алгоритмы случайного поиска, которые в определенных случаях и по определенным критериям не только соперничают, но и превосходят известные регулярные алгоритмы поиска. Проблема случайного поиска возникла и разрабатывается сравнительно недавно. Она берет начало от известного гомеостата Р. Эшби, который Г. Уолтер остроумно, но несколько преждевременно назвал «машиной для ничего» Однако при более внимательном рассмотрении работы гомеостата оказалось, что заложенная в нем идея случайного поиска необыкновенно плодотворна в научном и очень-полезна в практическом смысле. ОГЛАВЛЕНИЕ Предисловие .................. ' Введение.........•.......... ^ § 0.1. Проблема поисковой оптимизации ...... П § 0.2. Модели объектов оптимизации ..... 22 § 0.3. Характеристики эффективности поиска .... 32 § 0.4, Регулярные методы поиска......... 41 Глава 1 Случайный поиск............. 50 § 1.1. Гомес^тат Эшби............. 50 § 1.2. Модернизации и применения гомеостата .... 58 § 1.3. Случайный поиск как метод управления .... 65 § 1.4. Случайный поиск как метод сбора информации . 69 § 1.5. Алгоритмы случайного поиска для целей оптимизации ........ ........ 75 Глава 2 Локальный шаговый поиск (случай без помех) 82 § 2.1. Алгоритмы локального поиска ....... 82 § 2.2. Шаговые алгоритмы случайного поиска в линейном поле............... . 89 § 2.3. Шаговые алгоритмы случайного поиска в центральном поле . .... 95 § 2.4. Сопоставление метода градиента и случайного поиска . . ... ......... 103 § 2.5. Случайный поиск с накоплением....... 108 Глава 3. Интегральное поведение шаговых алгоритмов случайного поиска (случай без помех) ... 121 § 3.1. Интегральное поведение в линейном поле .... 121 § 3.2. Сравнение случайного поиска с методом градиента по критерию надежности . . ....... 128 § 3.3. Поведение случайного поиска при сбоях .... 134 § 3.4. Блуждание системы в районе цели в процессе случайного поиска , . ...... 143 § 3.5. Влияние дрейфа цели на поведение случайного поиска..... ........... 151 Глава 4. Работа случайного поиска в обстановке помех . . 164 § 4.1. Локальные свойства случайного поиска в обстановке помех............... 166 § 4.2. Поведение марковских алгоритмов случайного поиска в обстановке помех . . , . ... 173 § 4.3. Блуждание системы в процессе пояска при наличии помех .............. 191 § 4.4. Накопление в обстановке помех....... 201 § 4.5. Пороговая фильтрация ...... 215 § 4.6. Оценка параметров объекта оптимизации при наличии помех ... . 222 Глава 5. Самообучение в процессе случайного поиска . . 234 § 5.1. Алгоритмы самообучения ...... . . 235 § 5.2. Динамика покоординатного самообучения в линейном поле (случай без помех) . . 248 § 5.3. Динамика покоординатного самообучения в линейном поле (случай с помехами) . . 265 § 5.4. Покоординатное самообучение в центральном поле 275 § 5.5. Непрерывный алгоритм самообучения .... 283 Глава 6. Глобальный поиск . ........ 291 § 6.1. «Независимый» глобальный поиск ....... 292 § 6.2. «Блуждающий» глобальный поиск .... . 298 § 6.3. Глобальный шаговый поиск как поиск с самообучением .......... 304 Глава 7. Непрерывный поиск........... 322 § 7.1. Случайный спуск . .......... 322 § 7.2. Автоколебательный спуск.......... 334 § 7.3. Одно частотны и поиск ..... .... 348 § 7.4. Коррекция в процессе од но частот но го поиска . . 359 Приложение. Плотности распределения некоторых функций случайных векторов в n-мерном пространстве . . . 365 Литература................... 370