Главная arrow Поиск arrow Задачи оптимизации
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Задачи оптимизации Печать

Рассматривавшиеся до сих пор алгоритмы поиска предназначались для систематического исследования пространств поиска. Такая систематичность достигается благодаря тому, что один или несколько путей хранится в памяти и проводится регистрация того, какие альтернативы были исследованы в каждой точке вдоль этого пути, а какие нет. После того как цель найдена, путь к этой цели составляет также искомое решение данной задачи.

Но при решении многих задач путь к цели не представляет интереса. Например, в задаче с восемью ферзями важна лишь окончательная конфигурация ферзей, а не порядок, в котором они были поставлены на доску. К этому классу задач относятся многие важные приложения, такие как проектирование интегральных схем, разработка плана цеха, составление производственного расписания, автоматическое программирование, оптимизация сети связи, составление маршрута транспортного средства и управление портфелем акций.

Если путь к цели не представляет интереса, то могут рассматриваться алгоритмы другого класса, в которых вообще не требуются какие-либо данные о путях. Алгоритмы локального поиска действуют с учетом единственного текущего состояния (а не многочисленных путей) и обычно предусматривают только переход в состояние, соседнее по отношению к текущему состоянию. Как правило, информация о путях, пройденных в процессе такого поиска, не сохраняется.

Хотя алгоритмы локального поиска не предусматривают систематическое исследование пространства состояний (не являются систематическими), они обладают двумя важными преимуществами: во-первых, в них используется очень небольшой объем памяти, причем обычно постоянный, и, во-вторых, они часто позволяют находить приемлемые решения в больших или бесконечных (непрерывных) пространствах состояний, для которых систематические алгоритмы не применимы.

Кроме поиска целей, алгоритмы локального поиска являются полезным средством решения чистых задач оптимизации, назначение которых состоит в поиске состояния, наилучшего с точки зрения целевой функции. Многие задачи оптимизации не вписываются в «стандартную» модель поиска.

Например, природа предусмотрела такую целевую функцию (пригодность для репродукции), что дарвиновская эволюция может рассматриваться как попытка ее оптимизации, но в этой задаче оптимизации нет компонентов «проверка цели» и «стоимость пути».

Авторы пришли к выводу, что для понимания сути локального поиска очень полезно рассмотреть ландшафт пространства состояний (подобный показанному на рисунке). Этот ландшафт характеризуется и «местонахождением» (которое определяется состоянием), и «возвышением» (определяемым значением эвристической функции стоимости или целевой функции).

Если возвышение соответствует стоимости, то задача состоит в поиске самой глубокой долины — глобального минимума, а если возвышение соответствует целевой функции, то задача заключается в поиске высочайшего пика — глобального максимума. (Минимум и максимум можно поменять местами, взяв их с обратными знаками.) Алгоритмы локального поиска исследуют такой ландшафт. Алгоритм полного локального поиска всегда находит цель, если она существует, а оптимальный алгоритм всегда находит глобальный минимум / максимум.


Ландшафт одномерного пространства состояний, в котором возвышение соответствует целевой функции. Задача состоит в поиске глобального максимума. Как обозначено стрелкой, в процессе поиска по принципу «подъема к вершине» осуществляются попытки модификации текущего состояния в целях его улучшения. Различные топографические особенности ландшафта определены в тексте