Алгоритм мини-конфликтов
В информатике алгоритм минимальных конфликтов — это алгоритм поиска или эвристический метод решения проблем удовлетворения ограничений .
Один из таких алгоритмов — min-conflicts Hill Climbing . [1] Учитывая первоначальное присвоение значений всем переменным задачи удовлетворения ограничений (с одним или несколькими неудовлетворенными ограничениями), выберите переменную из набора переменных с конфликтами, нарушающими одно или несколько ее ограничений. Присвойте этой переменной значение, которое минимизирует количество конфликтов (обычно разрыв связей происходит случайным образом). Повторяйте этот процесс выбора конфликтующей переменной и присвоения минимального значения конфликта до тех пор, пока не будет найдено решение или не будет достигнуто заранее выбранное максимальное количество итераций. Если решение не найдено, алгоритм можно перезапустить с другим начальным назначением.
Поскольку проблему удовлетворения ограничений можно интерпретировать как задачу локального поиска, когда всем переменным присвоено значение (называемое полным состоянием), алгоритм минимальных конфликтов можно рассматривать как эвристику восстановления. [2] который выбирает состояние с минимальным количеством конфликтов.
Алгоритм
[ редактировать ]algorithm MIN-CONFLICTS is
input: console.csp, A constraint satisfaction problem.
max_steps, The number of steps allowed before giving up.
current_state, An initial assignment of values for the variables in the csp.
output: A solution set of values for the variable or failure.
for i ← 1 to max_steps do
if current_state is a solution of csp then
return current_state
set var ← a randomly chosen variable from the set of conflicted variables CONFLICTED[csp]
set value ← the value v for var that minimizes CONFLICTS(var,v,current_state,csp)
set var ← value in current_state
return failure
Хотя это и не указано в алгоритме, хорошее первоначальное задание может иметь решающее значение для быстрого поиска решения. Используйте жадный алгоритм с некоторым уровнем случайности и позвольте присваиванию переменных нарушать ограничения, когда другого присвоения будет недостаточно. Случайность помогает минимальным конфликтам избегать локальных минимумов, созданных первоначальным назначением жадного алгоритма. Фактически, задачи удовлетворения ограничений, которые лучше всего реагируют на решение с минимальным количеством конфликтов, преуспевают там, где жадный алгоритм почти решает проблему. Проблемы с раскраской карт плохо решаются с помощью жадного алгоритма, а также мини-конфликтов. Подобласти карты, как правило, сохраняют свои цвета стабильными, и минимальные конфликты не могут подняться на холм, чтобы вырваться за пределы локального минимума. Функция CONFLICTS подсчитывает количество ограничений, нарушенных конкретным объектом, при условии, что состояние остальной части присваивания известно.
История
[ редактировать ]Хотя искусственный интеллект и дискретная оптимизация знали и рассуждали о проблемах удовлетворения ограничений в течение многих лет, только в начале 1990-х годов этот процесс решения больших CSP был систематизирован в алгоритмической форме. Вначале Марк Джонстон из Научного института космического телескопа искал метод планирования астрономических наблюдений на космическом телескопе Хаббл . В сотрудничестве с Хансом-Мартином Адорфом из Европейского координационного центра космического телескопа он создал нейронную сеть, способную решить задачу игрушечных n -ферзей (для 1024 королев). [3] [4] Стивен Минтон и Энди Филипс проанализировали алгоритм нейронной сети и разделили его на две фазы: (1) первоначальное назначение с использованием жадного алгоритма и (2) фазы минимизации конфликтов (позже получившие название «минимальные конфликты»). Статья была написана и представлена на AAAI-90; Филип Лэрд предоставил математический анализ алгоритма.
Впоследствии Марк Джонстон и сотрудники STScI использовали мин-конфликты для планирования времени наблюдений астрономов на космическом телескопе Хаббл.
Пример
[ редактировать ]
Min-Conflicts решает проблему N -Queens, выбирая столбец на шахматной доске для переназначения ферзя. Алгоритм ищет каждый потенциальный ход на предмет количества конфликтов (количества атакующих ферзей), указанного в каждом квадрате. Алгоритм перемещает ферзя на поле с минимальным количеством конфликтов, разрывая ничьи случайным образом. Обратите внимание, что количество конфликтов генерируется каждым новым направлением, с которого может атаковать ферзь. Если два ферзя атакуют с одного направления (ряда или диагонали), то конфликт засчитывается только один раз. Также обратите внимание, что если ферзь находится в позиции, в которой ход может привести к большему конфликту, чем его текущая позиция, он не делает ход. Отсюда следует, что если ферзь находится в состоянии минимального конфликта, ему не обязательно двигаться.
Производительность этого алгоритма во многом зависит от выбора начальной позиции. Хорошую стартовую позицию можно создать, назначая ферзей столбец за столбцом, причем каждое назначение относится к строке, что сводит к минимуму количество нарушений ограничений. В результате получается начальная позиция со средним количеством нарушений ограничений, которое на удивление мало и очень медленно растет с увеличением n (например, 12,8 для n=10). 6 ).
При хорошей стартовой позиции количество переназначений, необходимых для решения, также постоянно: этот алгоритм решит даже задачу миллиона ферзей примерно за 50 переназначений. Количество оценок ограничений для каждого переназначения растет с увеличением n, что приводит к почти линейному времени выполнения.
Это открытие и наблюдения привели к большому объему исследований в 1990 году и положили начало исследованиям проблем локального поиска и различий между простыми и сложными задачами. N -Queens удобен для локального поиска, поскольку решения плотно распределены по пространству состояний. Он также эффективен при серьезных проблемах. Например, он использовался для планирования наблюдений на космическом телескопе Хаббл , что позволило сократить время, необходимое для планирования недели наблюдений, с трех недель примерно до 10 минут. [5]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Минтон, Стивен; Марк Д. Джонстон; Эндрю Б. Филипс; Филип Лэрд (1990). «Решение крупномасштабных проблем удовлетворения ограничений и планирования с использованием эвристического метода восстановления» (PDF) . Восьмая национальная конференция по искусственному интеллекту (AAAI-90), Бостон, Массачусетс : 17–24 . Проверено 27 марта 2013 г.
- ^ Минтон, Стивен; Марк Д. Джонстон; Эндрю Б. Филипс; Филип Лэрд (1992). «Минимизация конфликтов: эвристический метод устранения проблем удовлетворения ограничений и планирования» (PDF) . Искусственный интеллект . 58 (1): 161–205. CiteSeerX 10.1.1.308.6637 . дои : 10.1016/0004-3702(92)90007-к . S2CID 14830518 . Проверено 27 марта 2013 г.
- ^ Джонстон, доктор медицины; Адорф, Х.-М. (1989). «Обучение стохастическим нейронным сетям для решения проблем удовлетворения ограничений». Конференция НАСА. О космической телеробототехнике, 1989, Пасадена, Калифорния; Г. Родригес, Х. Сераджи (ред.) : 367–376, том II.
- ^ Адорф, Х.-М.; Джонстон, доктор медицины (1990). «Дискретный стохастический алгоритм нейронной сети для задач удовлетворения ограничений». 1990 Международная совместная конференция IJCNN по нейронным сетям . С. 917–924 т.3. дои : 10.1109/IJCNN.1990.137951 . S2CID 26917432 .
- ^ Стюарт Рассел, Питер Норвиг, «Искусственный интеллект: современный подход (3-е издание)», стр. 220-222, 11 декабря 2009 г.
Внешние ссылки
[ редактировать ]- [1] Эвристическая микроформа мин-конфликтов: эксперимент и теоретические результаты / Стивен Минтон… [и др.]. НАСА, Исследовательский центр Эймса, Отделение исследований искусственного интеллекта. Распространяется в депозитарные библиотеки на микрофишах.