Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 51
Текст из файла (страница 51)
Это возрождение интереса к алгоритмам, названным Кристосом Пападимитриу алгоритмами "новой эры", вызвало также повышенный интерес теоретиков в области компьютерных наук [13], [848]. В области исследования операций завоевал широкую популярность один из вариантов поиска с восхождением к вершине, получивший название 'в. поиска с запретами [563], [564]. В этом алгоритме, основанном на моделях ограниченной кратковременной памяти человека, ведется список запретов, состоящий из )г ранее посешенных состояний, которые нельзя посешать повторно; это позволяет данному алгоритму не только выполнять поиск в графах более эффективно, но и выходить из некоторых локальных минимумов.
Вше одним полезным усовершенствованием алгоритма поиска с восхождением к вершине является алгоритм Майе [163]. Идея этого алгоритма состоит в том, что для получения представления об общей форме ландшафта должны использоваться локальные максимумы, найденные в результате восхождения к вершине с перезапуском случайным образом. Данный алгоритм согласует гладкую поверхность с множеством локальных максимумов, а затем аналитическим путем вычисляет глобальный максимум этой поверхности. Полученный глобальный максимум становится новой точкой перезапуска.
Успешное функционирование этого алгоритма было испытано на практике при решении трудных задач. В [573] показано, что распределения времени выполнения алгоритмов, в которых систематически применяются возвраты, часто имеют форму 'з. распределений с широким хвостом (Ьеачу-1а11еб г]1згпЬи!1оп), а это означает, что вероятность очень продолжительного времени выполнения выше, чем можно было бы предположить в случае нормального распределения значений времени выполнения. Данные результаты могут служить теоретическим обоснованием применимости алгоритмов с перезапуском случайным образом.
Метод поиска с эмуляцией отжига был впервые описан Кирпатриком и др. [799], которые заимствовали соответствуюшую идею непосредственно из алгоритма Метрополиса (этот алгоритм применялся для эмуляции сложных систем в физике [1036] и был, как многие полагают, изобретен на одном из званых обедов в Лос-Аламосе). Методы поиска с эмуляцией отжита теперь лежат в основе отдельного научного направления, в котором ежегодно публикуются сотни статей. Поиск оптимальных решений в непрерывных пространствах является предметом исследований в нескольких научных областях, включая теорию оптимизации, теорию оптимального управления и вариавзюниое исчисление. Подходяшие для нашей темы (и практически применимые) вступительные сведения приведены в [133] и [1236].
Одним из первых приложений для компьютеров было линейное программирование (Ыпеаг Ргойгашпппй — 1.Р); относящийся к этой области симплексиый алгоритм ]322], [161Ц все еше используется, несмотря на то, что в наихудшем случае он характеризуется экспоненциальной сложностью.
Кармаркар [77Ц разработал практически применимый алгоритм для задач [ Р с полиномиальной временной сложностью. Важной работой, предшествующей разработке генетических алгоритмов, было исследование концепции ландшафта пригодности (йгпезз 1апбзсаре), проведенное Сьюэллом Райтом [1623]. В 1950-х годах некоторые специалисты в области статистики, включая Бокса [16Ц и Фридмана [504], использовали эволюционные методы для решения задач оптимизации, но этот подход приобрел популярность только по- Глава 4. Информированный поиск и исследование пространства состояний 203 спетого, как Рехенберг [1270],[1271] предложил использовать сь стратегии эволюции (ечо!цгюп ыгагейу) для решения задач оптимизации аэродинамических поверхностей.
В !960-х и !970-х годах генетические алгоритмы глубоко исследовал Джон Холланд [669), применяя их и в качестве полезного инструментального средства, и в качестве способа расширения знаний в области адаптации, как биологической, так и связанной с другими научными направлениями [670). Сторонники движения, доказывающие возможность 'т. искусственной жизни [886], развили эту идею на один шаг дальше, рассматривая продукты генетических алгоритмов как организмы, а не как решения задач.
В результате исследований в этой области, проведенных Хинтоном и Ноуланом [656], а также Экли и Литтманом [3], было сделано очень многое для выяснения последствий действия эффекта Болдуина. Для ознакомления с общими сведениями об эволюции авторы настоятельно рекомендуют книгу [1439). Сравнение генетических алгоритмов с другими подходами (особенно с алгоритмом стохастического поиска с восхождением к вершине) чаще всего показывает, что генетические алгоритмы сходятся более медленно [66], [754], [1060), [1158). Такие исследования не находят всеобщего признания в сообществе приверженцев алгоритмов ОА, но недавние попытки представителей этого сообщества трактовать поиск на основе популяций как приближенный аналог байесовского обучения (см.
главу 20) могут способствовать преодолению разногласий между представителями этой области и ее критиками [!200]. Для анализа производительности алгоритмов ОА может также применяться теория квадратичных динамических систем [1262]. В[944] можно найти пример применения ОА для проектирования антенн, а в [890] — пример применения этих алгоритмов для решения задачи коммивояжера. С генетическими алгоритмами тесно связана область Ж генетического программирования. Принципиальное различие между ними состоит в том, что представлениями, к которым применяются операции мутации и комбинирования, являются программы, а не битовые строки.
Программы представлены в форме деревьев выражений; выражения могут быть сформированы на таком стандартном языке, как Ызр, или специально спроектированы для представления технических схем, контроллеров роботов и т.д. Операция скрещивания предусматривает соединение друг с другом поддеревьев, а не подстрок. Такая форма мутации гарантирует, что потомки будут представлять собой правильно построенные выражения, а это не было бы возможно в случае проведения манипуляций с программами, представленными в виде строк.
Недавно возникший широкий интерес к генетическому программированию был стимулирован работой Джона Козы [855], [856), но исследования в этой области проводились уже давно, начиная с экспериментов с машинным кодом )502] и с конечными автоматами [476). Как и в отношении генетических алгоритмов, еще не утихли споры по поводу эффективности методов генетического программирования. В [857) описаны результаты ряда экспериментов по автоматизированному проектированию схемотехнических устройств с использованием генетического программирования.
Работы в области генетических алгоритмов и генетического программирования публикуются в журналах Еыо!илопагу Сотри!апоп и!ЕЕЕ Тгапгасг!опз оп Еыо!идопагу Сотригабоп; статьи на эти темы можно также найти в журналах Сотр(ех Бузгетз, Аг(арг!ые Вейаы!ог и Аггл)с!а! Ь~е. Основными конференциями являются 7пгегпаг!опа! Соп(егепсе оп Оепег!с А!8опуйтз и Соп(егепсе оп бепег(с рголгаттт8, а недавно произошло их слияние и создана конференция бепег!с апВ Еыо!ипопагу Сотригапоп Соп~егепсе.
Хорошие обзоры этой области приведены в книгах Мелани Митчелл [1059] и Дэвида Фогеля [475]. 204 Часть П. Решение проблем Алгоритмы исследования неизвестных пространств состояний привлекали интерес ученых в течение многих столетий. Поиск в глубину в лабиринте можно осуществить, постоянно держась левой рукой за стену; циклов можно избежать, отмечая каждую развилку. При наличии необратимых действий поиск в глубину оканчивается неудачей; более общая задача исследования 'в. графов Эйлера (т.е. графов, в которых каждый узел имеет одинаковое число входящих и исходящих ребер) была решена с помощью алгоритма, предложенного Хирхольцером [652].
Первое исчерпывающее описание алгоритмов решения задачи исследования для произвольных графов было приведено в [385]; авторы этой работы предложили полностью общий алгоритм, но показали, что невозможно определить ограниченный коэффициент конкурентоспособности для задачи исследования графа общего вида. В [117 Ц приведены результаты исследования проблемы поиска путей к цели в геометрических вариантах среды планирования пути (где все действия являются обратимыми). Эти результаты показали, что достичь того, чтобы коэффициент конкурентоспособности оставался небольшим, можно при наличии квадратных препятствий, но если препятствия имеют произвольную прямоугольную форму, то невозможно добиться того, чтобы значения коэффициента конкурентоспособности оставались ограниченными (см. рис.
4.13). Алгоритм ЬКТА* был разработан Корфом [839] в ходе исследований в области ;з. поиска в реальном времени для вариантов среды, в которых агент должен действовать после проведения поиска лишь в течение ограниченного времени (зта ситуация встречается гораздо чаще в играх с двумя участниками). По сути, алгоритм ЬКТА* представляет собой частный случай алгоритмов обучения с подкреплением для стохастических вариантов среды [74]. Применяемый в нем принцип оптимистического отношения к неопределенности (согласно которому следует всегда отправляться к ближайшему непосещенному состоянию) может в случае отсутствия информации о среде привести к формированию такого подхода к исследованию, который является менее эффективным по сравнению с простым поиском в глубину [818].
В [327] показано, что поиск с итеративным углублением в оперативном режиме обладает оптимальной эффективностью поиска цели в однородном дереве при отсутствии эвристической информации. В сочетании с различными методами поиска и обновления в известной части графа было разработано несколько вариантов алгоритма 1.КТА*, предусматривающих использование информации о среде [1201].
Тем не менее еще нет полного понимания того, как следует находить цели с оптимальной эффективностью при использовании эвристической информации. Тема алгоритмов ~х параллельного поиска в этой главе не рассматривалась, отчасти потому, что для этого требуется привести подробное описание параллельных компьютерных архитектур. Параллельный поиск становится важной темой и в искусственном интеллекте, и в теоретических компьютерных науках. Краткое введение в тематику литературы по искусственному интеллекту можно найти в книге Маханти и Дэниелса [969].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
