БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
во многих алгоритмах, явившихся предшественниками алгоритма А*; к ним относятся алгоритмы поиска в ширину, поиска в глубину и поиска по критерию стоимости [97], [399]. Важность применения аддитивных стоимостей путей для упрощения алгоритмов оптимизации особо ярко была показана в работа Беллмана [97].
Пол [1220], [1223] впервые провел исследования связи между ошибками в эвристических функциях и временной сложностью алгоритма А*. Доказательство того, что работа алгоритма А* завершается за линейное время, если ошибка в эвристической функции ограничена некоторой константой, можно найти в работах Пола [1223] и Гашнига [522]. Перл [1188] развил этот результат, что позволило учитывать логарифмический рост ошибки. Применение "эффективного коэффициента ветвления" в качестве критерия эффективности эвристического поиска было предложено Нильссоном [1141].
Существует много вариантов алгоритма А*. Пол [1222] предложил использовать в алгоритме А* динамическое взвешивание (dynamic weighting), в котором в качестве функции оценки применяется взвешенная сумма текущей длины пути и эвристической функции fv[n) =wgg{n) +whh{n), а не просто сумма f(n) =д(п) +п{п). Веса wg и wh корректируются динамически по мере развития поиска. Можно доказать, что алгоритм Пола является е-допустимым (т.е. гарантирует нахождение решений с отклонением от оптимального решения на коэффициент 1+е), где 8 — параметр, предусмотренный в алгоритме. Таким же свойством обладает алгоритм Ае*[1188], который способен выбрать из периферии любой узел, при условии, что его f-стоимость находится в пределах коэффициента 1+е от стоимости периферийного узла с наименьшей f-стоимостью. Выбор соответствующего коэффициента может быть сделан таким образом, чтобы существовала возможность минимизировать стоимость поиска.
Алгоритм А* и другие алгоритмы поиска в пространстве состояний тесно связаны с методами ветвей и границ, которые широко используются в исследованиях операций [901]. Соотношения между алгоритмами поиска в пространстве состояний и методами ветвей и границ были глубоко исследованы в [867], [869], [1115]. Мартелли и Монтанари [990] показали связь между динамическим программированием (см. главу 17) и некоторыми типами поиска в пространстве состояний. Кумар и Канал [868] предприняли попытку "великой унификации" методов эвристического поиска, динамического программирования, а также методов ветвей и границ под общим названием CDP (Composite Decision Process — комплексный процесс принятия решений).
Поскольку компьютеры в конце 1950-х — начале 1960-х годов имели не больше нескольких тысяч слов оперативной памяти, темой ранних исследовательских работ часто служил эвристический поиск с ограничением памяти. Одна из самых первых программ поиска, Graph Traverser [404], фиксирует свои результаты в виде некоторого оператора после выполнения поиска по первому наилучшему совпадению вплоть до заданного предела объема памяти. Алгоритм IDA* [835], [836] стал одним из первых широко применяемых оптимальных алгоритмов эвристического поиска с ограничением памяти, после чего было разработано большое количество его вариантов. Анализ эффективности алгоритма IDA* и сложностей, возникающих при его применении с эвристическими функциями, которые встречаются в реальных задачах, приведен в работе Патрика и др. [1182].
Алгоритм RBFS [840], [841] фактически является лишь немного более сложным по сравнению с алгоритмом, приведенным в листинге 4.1. Последний вариант ближе к независимо разработанному алгоритму, получившему название алгоритма итеративного развертывания, или сокращенно IE (Iterative Expansion) [1324]. В алгоритме RBFS используется не только верхняя, но и нижняя граница; эти два алгоритма при использовании допустимых эвристических функций ведут себя одинаково, но RBFS развертывает узлы в порядке первого наилучшего совпадения даже при наличии недопустимой эвристической функции. Идея отслеживания наилучшего альтернативного пути появилась еще раньше в изящной реализации алгоритма А* на языке Prolog, предложенной Братко [174], и в алгоритме DTA* [1332]. В последней работе обсуждаются также метауровневые пространства состояний и метау-ровневое обучение.
Алгоритм МА* впервые опубликован в [229]. Появление алгоритм SMA*, или Simplified МА*, стало результатом попытки реализовать МА* в качестве алгоритма сравнения для метода IE [1324]. Кайндл и Корсанд [763] применили алгоритм SMA* для создания алгоритма двунаправленного поиска, который функционирует значительно быстрее по сравнению с предшествующими алгоритмами. В [845] описан подход по принципу "разделяй и властвуй", а в [1645] представлен алгоритм А* поиска в графе с ограничением памяти. Обзор методов поиска с ограничением памяти приведен в [842].
Идея о том, что допустимые эвристические функции могут быть получены с помощью ослабления условий задачи, впервые опубликована в оригинальной статье [645], авторы которой использовали эвристику на основе минимального связующего дерева для решения задачи TSP (см. упр. 4.8).
Автоматизация процесса ослабления условий задачи была успешно осуществлена Придитисом [1237] на основе его более ранней совместной работы с Мостоу [1092]. Использование баз данных шаблонов для составления допустимых эвристических функций предложено в [313] и [523]; базы данных с непересекающимися шаблонами описаны в [844]. Вероятностная интерпретация эвристических функций глубоко исследована в [616] и [1188].
Безусловно, наиболее исчерпывающим источником сведений об эвристических функциях и алгоритмах эвристического поиска является книга Перла Heuristics [1188]. В этой книге приведено особенно хорошее описание широкого разнообразия версий и вариантов алгоритма А*, включая строгие доказательства их формальных свойств. В работе Канала и Кумара представлена антология важных статей по эвристическому поиску [767]. Результаты новейших исследований в области алгоритмов поиска регулярно публикуются в журнале Artificial Intelligence.
Методы локального поиска имеют долгую историю в математике и компьютерных науках. Безусловно, как очень эффективный метод локального поиска в непрерывных пространствах, в которых доступна информация о градиенте, может рассматриваться метод Ньютона-Рафсона [1132], [1266]. В [182] можно найти классический справочник по алгоритмам оптимизации, для которых не требуется такая информация. Алгоритм лучевого поиска, представленный в данной книге как алгоритм локального поиска, впервые появился в виде одного из вариантов методов динамического программирования с ограничением по ширине, предназначенного для распознавания речи, в системе Harpy [952]. Еще один алгоритм подобного типа был глубоко проанализирован Перлом [1188] (глава 5).
В последние годы снова пробудился интерес к теме локального поиска под влиянием исключительно качественных результатов, полученных при решении таких крупных задач удовлетворения ограничений, как задача с п-ферзями [1058] и задача формирования логических рассуждений [1382], а также под влиянием успешного включения в алгоритмы методов рандомизации, методов множественного одновременного поиска и других усовершенствований. Это возрождение интереса к алгоритмам, названным Кристосом Пападимитриу алгоритмами "новой эры", вызвало также повышенный интерес теоретиков в области компьютерных наук [13], [848]. В области исследования операций завоевал широкую популярность один из вариантов поиска с восхождением к вершине, получивший название поиска с запретами [563], [564]. В этом алгоритме, основанном на моделях ограниченной кратковременной памяти человека, ведется список запретов, состоящий из к ранее посещенных состояний, которые нельзя посещать повторно; это позволяет данному алгоритму не только выполнять поиск в графах более эффективно, но и выходить из некоторых локальных минимумов. Еще одним полезным усовершенствованием алгоритма поиска с восхождением к вершине является алгоритм Stage [163]. Идея этого алгоритма состоит в том, что для получения представления об общей форме ландшафта должны использоваться локальные максимумы, найденные в результате восхождения к вершине с перезапуском случайным образом. Данный алгоритм согласует гладкую поверхность с множеством локальных максимумов, а затем аналитическим путем вычисляет глобальный максимум этой поверхности. Полученный глобальный максимум становится новой точкой перезапуска. Успешное функционирование этого алгоритма было испытано на практике при решении трудных задач. В [573] показано, что распределения времени выполнения алгоритмов, в которых систематически применяются возвраты, часто имеют форму распределений с широким хвостом (heavy-tailed distribution), а это означает, что вероятность очень продолжительного времени выполнения выше, чем можно было бы предположить в случае нормального распределения значений времени выполнения. Данные результаты могут служить теоретическим обоснованием применимости алгоритмов с перезапуском случайным образом.
Метод поиска с эмуляцией отжига был впервые описан Кирпатриком и др. [799], которые заимствовали соответствующую идею непосредственно из алгоритма Мет-рополиса (этот алгоритм применялся для эмуляции сложных систем в физике [1036] и был, как многие полагают, изобретен на одном из званых обедов в Лос-Аламосе). Методы поиска с эмуляцией отжига теперь лежат в основе отдельного научного направления, в котором ежегодно публикуются сотни статей.
Поиск оптимальных решений в непрерывных пространствах является предметом исследований в нескольких научных областях, включая теорию оптимизации, теорию оптимального управления и вариационное исчисление. Подходящие для нашей темы (и практически применимые) вступительные сведения приведены в [133] и [1236]. Одним из первых приложений для компьютеров было линейное программирование (Linear Programming — LP); относящийся к этой области симплексный алгоритм [322], [1611] все еще используется, несмотря на то, что в наихудшем случае он характеризуется экспоненциальной сложностью. Кармаркар [771] разработал практически применимый алгоритм для задач LP с полиномиальной временной сложностью.
Важной работой, предшествующей разработке генетических алгоритмов, было исследование концепции ландшафта пригодности (fitness landscape), проведенное Сьюэллом Райтом [1623]. В 1950-х годах некоторые специалисты в области статистики, включая Бокса [161] и Фридмана [504], использовали эволюционные методы для решения задач оптимизации, но этот подход приобрел популярность только поеле того, как Рехенберг [1270], [1271] предложил использовать стратегии эволюции (evolution strategy) для решения задач оптимизации аэродинамических поверхностей. В 1960-х и 1970-х годах генетические алгоритмы глубоко исследовал Джон Холланд [669], применяя их и в качестве полезного инструментального средства, и в качестве способа расширения знаний в области адаптации, как биологической, так и связанной с другими научными направлениями [670]. Сторонники движения, доказывающие возможность искусственной жизни [886], развили эту идею на один шаг дальше, рассматривая продукты генетических алгоритмов как организмы, а не как решения задач. В результате исследований в этой области, проведенных Хинтоном и Ноуланом [656], а также Экли и Литтманом [3], было сделано очень многое для выяснения последствий действия эффекта Болдуина. Для ознакомления с общими сведениями об эволюции авторы настоятельно рекомендуют книгу [1439].
Сравнение генетических алгоритмов с другими подходами (особенно с алгоритмом стохастического поиска с восхождением к вершине) чаще всего показывает, что генетические алгоритмы сходятся более медленно [66], [754], [1060], [1158]. Такие исследования не находят всеобщего признания в сообществе приверженцев алгоритмов GA, но недавние попытки представителей этого сообщества трактовать поиск на основе популяций как приближенный аналог байесовского обучения (см. главу 20) могут способствовать преодолению разногласий между представителями этой области и ее критиками [1200]. Для анализа производительности алгоритмов GA может также применяться теория квадратичных динамических систем [1262]. В [944] можно найти пример применения GA для проектирования антенн, а в [890] — пример применения этих алгоритмов для решения задачи коммивояжера.
С генетическими алгоритмами тесно связана область генетического программирования. Принципиальное различие между ними состоит в том, что представлениями, к которым применяются операции мутации и комбинирования, являются программы, а не битовые строки. Программы представлены в форме деревьев выражений; выражения могут быть сформированы на таком стандартном языке, как Lisp, или специально спроектированы для представления технических схем, контроллеров роботов и т.д. Операция скрещивания предусматривает соединение друг с другом поддеревьев, а не подстрок. Такая форма мутации гарантирует, что потомки будут представлять собой правильно построенные выражения, а это не было бы возможно в случае проведения манипуляций с программами, представленными в виде строк.
Недавно возникший широкий интерес к генетическому программированию был стимулирован работой Джона Козы [855], [856], но исследования в этой области проводились уже давно, начиная с экспериментов с машинным кодом [502] и с конечными автоматами [476]. Как и в отношении генетических алгоритмов, еще не утихли споры по поводу эффективности методов генетического программирования. В [857] описаны результаты ряда экспериментов по автоматизированному проектированию схемотехнических устройств с использованием генетического программирования.
Работы в области генетических алгоритмов и генетического программирования публикуются в журналах Evolutionary Computation и IEEE Transactions on Evolutionary Computation] статьи на эти темы можно также найти в журналах Complex Systems, Adaptive Behavior и Artificial Life. Основными конференциями являются International Conference on Genetic Algorithms и Conference on Genetic Programming, а недавно произошло их слияние и создана конференция Genetic and Evolutionary Computation Conference. Хорошие обзоры этой области приведены в книгах Мелани Митчелл [1059] и Дэвида Фогеля [475].
Алгоритмы исследования неизвестных пространств состояний привлекали интерес ученых в течение многих столетий. Поиск в глубину в лабиринте можно осуществить, постоянно держась левой рукой за стену; циклов можно избежать, отмечая каждую развилку. При наличии необратимых действий поиск в глубину оканчивается неудачей; более общая задача исследования графов Эйлера (т.е. графов, в которых каждый узел имеет одинаковое число входящих и исходящих ребер) была решена с помощью алгоритма, предложенного Хирхольцером [652]. Первое исчерпывающее описание алгоритмов решения задачи исследования для произвольных графов было приведено в [385]; авторы этой работы предложили полностью общий алгоритм, но показали, что невозможно определить ограниченный коэффициент конкурентоспособности для задачи исследования графа общего вида. В [1171] приведены результаты исследования проблемы поиска путей к цели в геометрических вариантах среды планирования пути (где все действия являются обратимыми). Эти результаты показали, что достичь того, чтобы коэффициент конкурентоспособности оставался небольшим, можно при наличии квадратных препятствий, но если препятствия имеют произвольную прямоугольную форму, то невозможно добиться того, чтобы значения коэффициента конкурентоспособности оставались ограниченными (см. рис. 4.13).
Алгоритм LRTA* был разработан Корфом [839] в ходе исследований в области поиска в реальном времени для вариантов среды, в которых агент должен действовать после проведения поиска лишь в течение ограниченного времени (эта ситуация встречается гораздо чаще в играх с двумя участниками). По сути, алгоритм LRTA* представляет собой частный случай алгоритмов обучения с подкреплением для стохастических вариантов среды [74]. Применяемый в нем принцип оптимистического отношения к неопределенности (согласно которому следует всегда отправляться к ближайшему непосещенному состоянию) может в случае отсутствия информации о среде привести к формированию такого подхода к исследованию, который является менее эффективным по сравнению с простым поиском в глубину [818]. В [327] показано, что поиск с итеративным углублением в оперативном режиме обладает оптимальной эффективностью поиска цели в однородном дереве при отсутствии эвристической информации. В сочетании с различными методами поиска и обновления в известной части графа было разработано несколько вариантов алгоритма LRTA*, предусматривающих использование информации о среде [1201]. Тем не менее еще нет полного понимания того, как следует находить цели с оптимальной эффективностью при использовании эвристической информации.
Тема алгоритмов параллельного поиска в этой главе не рассматривалась, отчасти потому, что для этого требуется привести подробное описание параллельных компьютерных архитектур. Параллельный поиск становится важной темой и в искусственном интеллекте, и в теоретических компьютерных науках. Краткое введение в тематику литературы по искусственному интеллекту можно найти в книге Ма-ханти и Дэниелса [969].