Гибридный алгоритм решения задачи удовлетворения ограничений

Представлен гибридный алгоритм improved Guided Local and Systematic Search для решения распределенной задачи удовлетворения ограничений. Алгоритм объединяет компоненты локального и конструктивного поиска. Доказаны полнота и корректность алгоритма. Приведены результаты его экспериментальной оценки на...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Галковская, Л.А., Глибовец, Н.Н., Гороховский, С.С.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2012
Schriftenreihe:	Управляющие системы и машины
Schlagworte:	Информационные технологии
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/83111
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Гибридный алгоритм решения задачи удовлетворения ограничений / Л.А. Галковская, Н.Н. Глибовец, С.С. Гороховский // Управляющие системы и машины. — 2012. — № 6. — С. 72-80, 88. — Бібліогр.: 20 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-83111
record_format	dspace
spelling	irk-123456789-831112015-06-15T03:01:56Z Гибридный алгоритм решения задачи удовлетворения ограничений Галковская, Л.А. Глибовец, Н.Н. Гороховский, С.С. Информационные технологии Представлен гибридный алгоритм improved Guided Local and Systematic Search для решения распределенной задачи удовлетворения ограничений. Алгоритм объединяет компоненты локального и конструктивного поиска. Доказаны полнота и корректность алгоритма. Приведены результаты его экспериментальной оценки на модельной задаче о ферзях и проведено сравнение его производительности с производительностью алгоритмов Dis-GLS и iGL. The improved Guided Local and Systematic Search hybrid algorithm is presented for solving the Distributed Constraint Satisfaction Problem, which combines two local and one systematic search methods. The completeness and correctness of the algorithm are proved. The results of our experiments with queens' problem, and a comparison of productivity for our hybrid and two other algorithms Dis-GLS and iGL are given. Представлено гібридний алгоритм improved Guided Local and Systematic Search розв’язання розподіленої задачі задоволення обмежень, який поєднує компоненти локального та конструктивного пошуку. Доведено повноту і коректність алгоритму. Описано результати його експериментальної оцінки на модельній задачі про ферзі. Проведено порівняння його продуктивності з продуктивністю алгоритмів класу Dis-GLS та iGL. 2012 Article Гибридный алгоритм решения задачи удовлетворения ограничений / Л.А. Галковская, Н.Н. Глибовец, С.С. Гороховский // Управляющие системы и машины. — 2012. — № 6. — С. 72-80, 88. — Бібліогр.: 20 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/83111 681.3 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Информационные технологии Информационные технологии
spellingShingle	Информационные технологии Информационные технологии Галковская, Л.А. Глибовец, Н.Н. Гороховский, С.С. Гибридный алгоритм решения задачи удовлетворения ограничений Управляющие системы и машины
description	Представлен гибридный алгоритм improved Guided Local and Systematic Search для решения распределенной задачи удовлетворения ограничений. Алгоритм объединяет компоненты локального и конструктивного поиска. Доказаны полнота и корректность алгоритма. Приведены результаты его экспериментальной оценки на модельной задаче о ферзях и проведено сравнение его производительности с производительностью алгоритмов Dis-GLS и iGL.
format	Article
author	Галковская, Л.А. Глибовец, Н.Н. Гороховский, С.С.
author_facet	Галковская, Л.А. Глибовец, Н.Н. Гороховский, С.С.
author_sort	Галковская, Л.А.
title	Гибридный алгоритм решения задачи удовлетворения ограничений
title_short	Гибридный алгоритм решения задачи удовлетворения ограничений
title_full	Гибридный алгоритм решения задачи удовлетворения ограничений
title_fullStr	Гибридный алгоритм решения задачи удовлетворения ограничений
title_full_unstemmed	Гибридный алгоритм решения задачи удовлетворения ограничений
title_sort	гибридный алгоритм решения задачи удовлетворения ограничений
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2012
topic_facet	Информационные технологии
url	http://dspace.nbuv.gov.ua/handle/123456789/83111
citation_txt	Гибридный алгоритм решения задачи удовлетворения ограничений / Л.А. Галковская, Н.Н. Глибовец, С.С. Гороховский // Управляющие системы и машины. — 2012. — № 6. — С. 72-80, 88. — Бібліогр.: 20 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT galkovskaâla gibridnyjalgoritmrešeniâzadačiudovletvoreniâograničenij AT glibovecnn gibridnyjalgoritmrešeniâzadačiudovletvoreniâograničenij AT gorohovskijss gibridnyjalgoritmrešeniâzadačiudovletvoreniâograničenij
first_indexed	2025-07-06T09:50:45Z
last_indexed	2025-07-06T09:50:45Z
_version_	1836890661895274496
fulltext	72 УСиМ, 2012, № 6 Информационные технологии УДК 681.3 Л.А. Галковская, Н.Н. Глибовец, С.С. Гороховский Гибридный алгоритм решения задачи удовлетворения ограничений Представлен гибридный алгоритм improved Guided Local and Systematic Search для решения распределенной задачи удовлетворения ограничений. Алгоритм объединяет компоненты локального и конструктивного поиска. Доказаны полнота и корректность алгорит- ма. Приведены результаты его экспериментальной оценки на модельной задаче о ферзях и проведено сравнение его производитель- ности с производительностью алгоритмов Dis-GLS и iGL. The improved Guided Local and Systematic Search hybrid algorithm is presented for solving the Distributed Constraint Satisfaction Problem, which combines two local and one systematic search methods. The completeness and correctness of the algorithm are proved. The results of our experiments with queens' problem, and a comparison of productivity for our hybrid and two other algorithms Dis-GLS and iGL are given. Представлено гібридний алгоритм improved Guided Local and Systematic Search розв’язання розподіленої задачі задоволення обме- жень, який поєднує компоненти локального та конструктивного пошуку. Доведено повноту і коректність алгоритму. Описано ре- зультати його експериментальної оцінки на модельній задачі про ферзі. Проведено порівняння його продуктивності з продуктивніс- тю алгоритмів класу Dis-GLS та iGL. Введение. Парадигма программирования с ог- раничениями в конечных областях [1] возник- ла в конце 80-х годов как способ решения слож- ных комбинаторных задач (NP-полных задач). Она развилась из логического программирова- ния с ограничениями [2], которое в свою оче- редь было расширением парадигмы логическо- го программирования. Программирование с ог- раничениями можно рассматривать как про- граммную инфраструктуру для комбинирова- ния программных компонент, позволяющее по- лучать решатели на дереве поиска для конкрет- ных задач. Программирование с ограничения- ми служит гетерогенным полем исследований, начиная с математической логики и заканчивая практическими приложениями, такими как за- дачи календарного планирования, задачи о на- значениях и др. Многие задачи оптимизации и поиска могут быть формализованы как задачи удовлетворе- ния ограничений (Constraint Satisfaction Prob- lems – CSP) [1, 2]. Еще одним примером такой задачи может быть известная задача раскраски графа. С распространением концепции распре- деленных вычислений сформировался подкласс распределенных CSP-задач (Distributed Con- straint Satisfaction Problem – DISCSP). Во мно- гих случаях для их решения привлекают груп- пу независимых исполнителей (агентов). Каж- дый агент оперирует частью задачи (чаще все- го – одной переменной задачи или одной под- задачей) и обменивается информацией с дру- гими исполнителями, с которыми он связан оп- ределенными условиями и ограничениями (con- straints). Такая концепция положительно влия- ет на скорость нахождения решения и обеспе- чивает лучшую надежность. Задачу удовлетворения ограничений можно представить в виде тройки (X, D, C), где X = {x1, …, xn} – множество n переменных; D = {D(x1), …, D(xn)} – множество соответ- ствующих конечных доменов этих перемен- ных, т.е. множеств допустимых значений; C = {с1, …, сn} – множество ограничений на эти переменные. Для уточнения постановки задачи в распре- деленном варианте DISCSP будем считать, что исполнителей представляют агенты. Под аген- тами подразумеваются участники вычислений, которые могут обмениваться сообщениями [3]. Агент может послать сообщение другим аген- там, если он знает их имена. Задержка в дос- тавке сообщений конечна и случайна. Агенты получают сообщения в той же последователь- ности, в которой они отправлены. Тогда фор- мально DisCSP можно представить как пятер- ку (X, D, C, A, φ), где X, D определены как в CSP; C – множество ограничений, налагаемых на переменные из X; УСиМ, 2012, № 6 73 A = {1, ... , p} – множество агентов; : X → A функция, сопоставляющая каждому агенту пе- ременные из множества X. Каждый агент мо- жет оперировать несколькими переменными, но каждая переменная должна принадлежать толь- ко одному агенту. В связи с этим множество C делится на две части: множество внутренних ог- раничений агента Cintra = {cij \| (xi) = (xj)}, )}, т.е. множество ограничений, налагаемых на пе- ременные одного агента, и множество ограни- чений, налагаемых на переменные различных агентов Cinter = { cij \| (xi) ≠ (xj)} [4]. Известно, что каждая CSP сводится к бинар- ной. Бинарной задачей CSP называется задача, в которой предусмотрены только бинарные ог- раничения. Тогда функция  сопоставляет каж- дому агенту только одну переменную, и класс Cintra будет пустым (все ограничения бинарные, а каждый агент оперирует только одной пере- менной). Введем также следующие обозначения: be- longs(xj, i) – переменная xj принадлежит агенту и known(cm, k) – агент k знает об ограничении cm. Тогда DisCSP будем считать решенной в слу- чае, если выполняются следующие условия [3]: i xj belongs(xj, i) dj : xj = dj, т.е. всем пере- менным всех агентов присвоено какое-то зна- чение из их доменов. k, cm known(cm, k), cm выполняется для значения dj, присвоенного пе- ременной xj. Алгоритмы решения распределенных за- дач удовлетворения ограничений Алгоритмы решения DISCSP начали разви- ваться в конце прошлого тысячелетия и их число росло с каждым годом. Стало развиваться на- правление «улучшения существующих методов» разнообразными вариациями известных алго- ритмов. Причем два направления решения DIS- CSP (конструктивный и локальный) развива- лись параллельно, но базовые идеи по улучше- нию алгоритмов были вскоре исчерпаны. Сей- час внимание исследователей сосредоточено на:  разработке специальных алгоритмов для конкретных типов задач,  объединении существующих алгоритмов в гибриды, наследующие преимущества сразу не- скольких методов. В конструктивном подходе [5–8] алгоритмы пошагово расширяют частичное допустимое ре- шение до полного. Если частичное решение ока- залось недопустимым, то происходит бектре- кинг и предыдущее частичное решение расши- ряется в альтернативном направлении. Тот факт, что поиск происходит в пространстве частич- ных решений, есть отличительной чертой этих алгоритмов. Локальный поиск – основной метод решения сложных задач из класса задач поиска CSP. Более того, зачастую он – единственный воз- можный способ решения задач, где конструк- тивные методы бессильны вследствие слиш- ком большого размера пространства возмож- ных решений. Идея локального поиска заключается в том, чтобы начать с произвольно сгенерированного кандидата в решения проблемы и, если он ока- жется недопустимым, пошагово его улучшать путем уменьшения количества неудовлетворен- ных ограничений. Алгоритмы локального по- иска отличаются методами нахождения этого улучшения [5–8]. Один из недостатков локальных алгоритмов – их неполнота, т.е. в них поиск может остано- виться в локальном минимуме, который в дейст- вительности не является глобальным решением. Здесь используется терминология, сложившая- ся в области DISCSP [9]. Состояние – это одно возможное присвое- ние всем переменным, число состояний равно произведению объемов множеств определения переменных, значение оценки – количество на- рушений ограничений в состоянии, сосед – со- стояние, получаемое из текущего состояния из- менением значения только одной переменной, локальный минимум – состояние, которое не есть решением и значение оценки всех его со- седей больше или равно значению оценки это- го состояния. Для устранения возможности не- полноты часто используется рандомизация (с определенной вероятностью на каждом шагу выбирается произвольное решение). Такие ме- тоды называются стохастическими. Используют и другие подходы: Randomized Iterative Impro- vement, эволюционные алгоритмы, алгоритмы 74 УСиМ, 2012, № 6 на основе метода отжига, Tabu Search, динами- ческий поиск или алгоритмы на основе штра- фов, алгоритмы с использованием принципа муравьиной колонии [9–14]. Гибридные алгоритмы используют комбина- цию нескольких различных подходов к реше- нию задачи. В контексте DisCSP гибриды мо- гут сочетать в себе алгоритмы из разных клас- сов (локальный и конструктивный) и разного способа синхронизации (синхронные и асин- хронные). Общепринятой классификации этих алгоритмов нет. В работах [4, 15–19] встречается классификация гибридных алгоритмов по сте- пени интеграции локальной и конструктивной составляющих: ● низкий уровень (локальный поиск прово- дится до или после конструктивного); ● средний уровень (основа – локальный по- иск, который пользуется средствами конструк- тивного алгоритма для уменьшения простран- ства поиска); ● высокий уровень (операторы конструк- тивного и локального поиска применяются по- очередно). Алгоритм 1. Общий принцип работы гибрид- ного алгоритма search (a) { while a is not solution { if a is consistent a ← extend (a) else a ← repair (a) } return a } Цель гибридов – компенсация недостатков одной из компонент за счет другой. Примером может быть сочетание синхронного метода, ко- торый характеризуется последовательным вы- полнением (это минус) и относительно низким уровнем общения между агентами (это плюс) и асинхронного метода с противоположными ха- рактеристиками. Такой гибрид расходует ми- нимум ресурсов на общение между агентами и пользуется преимуществами параллельного вы- полнения. Гибридный алгоритм GLoSS Рассмотрим предложенный вариант гибрид- ного алгоритма. Алгоритм GLoSS по классифи- кации относится к третьей категории, т.е. сов- мещает компоненты конструктивного и локаль- ного поиска и характеризуется высоким уров- нем их интеграции, при этом операторы конст- руктивного и локального поиска применяются поочередно, как упоминалось. Фрагмент реше- ния задачи расширяется средствами конструк- тивного алгоритма, пока это возможно (функ- ция extend () в алгоритме 1). Когда же для сле- дующей присоединенной к частичному реше- нию переменной невозможно найти подходя- щее значение из ее домена, вместо стандартно- го бектрекинга используется оператор локаль- ного поиска (repair () в алгоритме 1). Он зани- мается улучшением частного решения, полу- ченного конструктивным поиском, до тех пор, пока значения всех переменных этого решения не удовлетворят все ограничения. По достиже- нии цели управление вновь передается опера- тору конструктивного поиска. Цикл повторяет- ся, пока не будет найдено решение. На первый взгляд, в алгоритме все хорошо. Проблемой ос- тается неполнота. Каждый раз, когда управле- ние передается локальному оператору, его мис- сия превращения недопустимого частичного ре- шения в допустимое с некоторой вероятностью может быть провалена. Если эта вероятность и не очень велика (для алгоритма локального по- иска DisBO-wd на произвольной бинарной DIS- CSP она составляет примерно 3–4% [20]), это делает его крайне ненадежным, поскольку по- иск решения может остановиться уже на пер- вом переходе между ветвями. Описанный недостаток можно преодолеть простым способом – ограничив количество ша- гов алгоритма локального поиска. В этом слу- чае он гарантированно остановится, даже не най- дя решения. В случае преждевременной останов- ки (т.е. вынужденной остановки по достиже- нии лимита шагов) работу по нахождению ре- шения продолжит конструктивный алгоритм. Воспользуемся такой схемой работы гибрид- ного алгоритма. Предлагаемый гибрид GLoSS базируется на трех алгоритмах: Synchronous УСиМ, 2012, № 6 75 Backtracking (SBT), improved Guided Local Se- arch (iGL) и Asynchronous Weak-Commitment Search (AWCS). Описание компонент алгоритма GloSS. Ос- новная компонента гибрида – SBT, которая может периодически обращаться к алгоритмам iGL и AWCS. Алгоритм Synchronous Backtracking (SBT). На этапе инициализации этого алгоритма для всех агентов устанавливается приоритет, чтобы мож- но было отсортировать агентов по этим прио- ритетам в нисходящем порядке. Каждый следу- ющий агент (движение происходит от агента с большим приоритетом к агенту с меньшим при- оритетом) получает от предыдущего агента зна- чения, присвоенные переменным пройденных агентов. Получив информацию, он пытается ус- тановить значение для собственной переменной, анализируя известные ему ограничения, свя- занные с этой переменной. Если допустимое значение будет найдено – решение передастся следующему по приоритету агенту; если нет – произойдет возврат к предыдущему агенту. Данный алгоритм не использует возможно- стей распараллеливания, поскольку в каждый момент времени активен только один агент. Пре- имущество алгоритма – значительная разгрузка каналов общения между агентами. Количество отправленных сообщений для этого алгоритма минимально, поскольку решение передается от одного агента к другому, как эстафета. Эта раз- грузка обеспечивает эффективную реализацию алгоритма. Алгоритм improved Guided Local Search (iGL) базируется на алгоритме локального поиска Di- stributed Guided Local Search [10]. Он относится к классу penalty-based алгоритмов локального поиска, практикующих наложения штрафов. Каждый агент имеет определенный неизменный приоритет. Во время инициализации каждый агент выбирает себе значение только после то- го, как все агенты с более высоким приорите- том выберут себе значение, которое должно минимизировать функцию: f(x) = количество конфликтов с агентами с высшим приоритетом + сумма инкрементных штрафов за данное значение + сумма времен- ных штрафов за данное значение, где x – опре- деленное значение из домена переменной агента. Во время инициализации существенно толь- ко первое слагаемое, поскольку все штрафы рав- ны нулю. Наложение штрафов на значение из домена переменной агента происходит в слу- чае попадания агента в квазилокальный мини- мум1. Штрафы бывают двух типов: временные и инкрементные. Процедуру наложения штра- фов можно описать так. ● Попав в квазилокальный минимум, агент проверяет состояние текущей ситуации (т.е. сво- его состояния и состояния соседей) в списке со- храненных ранее «плохих» ситуаций nogood_ store. Если такая ситуация ранее не возникала, то агент налагает временный штраф на теку- щее значение и рассылает сообщение всем со- седям меньшего приоритета с требованием так же наложить временный штраф на свои значе- ния. Этот штраф отменяется сразу после выбо- ра агентом для себя нового значения [10]. Вре- менный штраф, обычно очень большое число, гарантирует избрание агентом нового значения. ● Если ситуация уже встречалась ранее, то агент налагает на текущее значение инкремент- ный штраф (увеличивая штраф на единицу) и посылает запрос к соседям с низким приорите- том на выполнение этого действия для их зна- чений. Во избежание бесконечного увеличения штра- фов каждому агенту выставляется верхняя гра- ница. Когда штраф превышает этот предел, аген- ту присваивается его наихудшее значение (с наибольшим штрафом). Если агент находит для себя допустимое значение, все инкрементные штрафы аннулируются [10]. Проанализируем главный цикл алгоритма. Агент активируется только после получения со- общения. Последние бывают двух типов – со- общения о штрафах и сообщения, содержащие 1 Ситуация квазилокального минимума возникает у агента, когда он нарушает некоторые, связанные с ним ограни- чения и при этом не может изменить свое состояние к луч- шему. Поскольку в такой ситуации участвуют только дан- ный агент и его соседи, она не будет локальным мини- мумом, а только квазилокальным, потому что агенты, не связанные с данным, все еще могут улучшить ситуацию. 76 УСиМ, 2012, № 6 значение одного из соседей агента. В случае, ес- ли агент получает значение одного из своих со- седей (алг. 2, стр. 9–22), то проверяет, не кон- фликтует ли это значение с его собственным. Если конфликты отсутствуют, агент обнуляет все свои инкрементные штрафы (алг. 2, стр. 10, 11). Кстати, алгоритм Dis-GLS, на котором ба- зируется iGL, кроме обнуления инкрементных штрафов, рассылает всем агентам свое значе- ние (алг. 2, стр. 12). По мнению авторов, это дей- ствие лишнее, оно забивает и без того перегру- женный сообщениями канал общения агентов. Особых оснований для его использования не су- ществует, ибо значение агента с прошлого раза не менялось и конфликтов нет. Кроме того, каждое из отправленных сообщений активиру- ет всех соседей агента, вынуждая их проводить лишние вычисления. Алгоритм iGL лишен та- кой возможности и в этом его преимущество. Алгоритм 2. Главный цикл алгоритма iGL Алгоритм 3. Главный цикл алгоритма DisGLS procedure iGL_main { do when active evaluate state if penalty message received responde_to_message() else if curr val is consistent reset inc penalties 1 2 3 4 5 6 7 8 9 10 11 procedure DisGLS_main { do when active evaluate state if penalty message received responde_to_message() else if curr val is consistent reset inc penalties 12 send(id,val,null) to all else 13 else if sender priority < current agent’s prior 14 15 resolve_conflict() 16 resolve_conflict() else send(id_val,null) back end if 17 18 19 end if end if return to inactive state until terminate } 20 21 22 23 24 25 end if end if return to inactive state until terminate } Рассмотрим случай, когда значение агента имеет конфликты с полученным значением со- седа. Агент берется решать конфликт, только ес- ли он имеет приоритет выше конфликтного аген- та. Иначе агент возвращает текущее значение адресату (и только ему), вынуждая того начать процедуру разрешения конфликта. Как видно из псевдокода алгоритмов 1 и 2, поведение iGL и Dis-GLS в этой ситуации отличается. Dis- GLS вынуждает агента немедленно начать про- цедуру разрешения конфликта. Рассмотрим про- цедуру решения конфликтов (алг. 4 и 5). Процедура разрешения конфликта для iGL начинает проверку наличия текущей конфликт- ной ситуации в nogood_store (алг. 4, стр. 3, 4). В Dis-GLS она тоже имеется, но происходит не- сколько позже (алг. 5, стр. 12, 13). Проверка га- рантирует попадание конфликтной ситуации сразу в «черный список» с первого раза. В Dis- GLS для этого потребуется как минимум два шага, и как минимум одно лишнее сообщение всем агентам. Алгоритм 4. Процедура разре- шения конфликта в алгорит- ме iGL Алгоритм 5. Процедура разре- шения конфликта в алгорит- ме DisGLS procedure iGL_resolve_conflict { 1 2 procedure DisGLS_resolve_conflict { if state is not in nogood_store add state to nogood_store 3 4 5 if sender state has changed select new value send(id,val,null) to all return 6 7 8 9 if sender state has changed select new value send(id,val,null) to all return else 10 11 12 13 end if if state is not in nogood_store add state to nogood_store impose temp penalty select new value send(id,val,TempPen) to agents with lower priority 14 15 16 17 impose temp penalty select new value send(id,val,TempPen) to agents with lower priority end if 18 19 else if inc penalty on cur val < upper bound increase inc penalty by 1 select new value else select worst val in domain end if send(id,val,IncPen) to agents with lower priority end if } 20 21 22 23 24 25 26 27 28 29 30 31 32 33 else if inc penalty on cur val < upper bound increase inc penalty by 1 select new value else select worst val in domain end if send(id,val,IncPen) to agents with lower priority end if } Далее в процедуре алгоритма iGL происхо- дит проверка состояния адресата. Если он не изменился, необходимо принять меры для вы- хода из квазилокального минимума, поэтому на текущее значение налагается временный штраф, и аналогичные действия применяются для всех конфликтных агентов с низким приоритетом. Бесконфликтным агентам посылаются сообще- ния с новым значением агента (алг. 4, стр. 13– 18). Потом происходит наложение инкремент- ного штрафа. Видно, что основным преимуществом алго- ритма iGL над Dis-GLS есть способ выхода из квазилокального минимума. Интересным при- мером попадания в квазилокальный минимум стал случай попадания в конфликт агента с наи- меньшим приоритетом, и для разрешения кон- фликта должны быть задействованы все дру- гие агенты. Алгоритм iGL выходит из такой УСиМ, 2012, № 6 77 критической ситуацией в среднем на 30 про- центов быстрее Dis-GLS, одного из лучших сре- ди алгоритмов локального поиска. Это обусло- вило выбор алгоритма iGL на роль компонен- ты локального поиска в гибридном алгоритме. Алгоритм Asynchronous Weak-Commitment Se- arch (AWCS). Этот алгоритм относится к клас- су асинхронных алгоритмов конструктивного поиска. Поэтому все агенты всегда активны и координируют свои действия с помощью со- общений двух типов: ok? – для пересылки со- седям своего текущего значения, и nogood – для передачи информации о нарушении опре- деленных ограничений. Коротко работу алго- ритма можно описать как в [7]. ● Для каждого агента устанавливается при- оритет – неотрицательное целое число. Чем боль- ше число – тем выше приоритет. Если у не- скольких агентов числа оказались одинаковыми, больший приоритет получит тот, имя которого по алфавиту идет первым. Начальные значения приоритета для всех агентов равно нулю. ● Получив сообщение ok?, агент записывает полученное значение в свой agent_view – струк- туру данных, характеризующую представле- ние агента о «внешнем мире». ● Если текущее значение агента удовлетво- ряет всем ограничениям, связанным со значе- нием переменных высшего приоритета по его agent_view, оно считается допустимым, иначе агент должен выбрать новое допустимое зна- чение (алг. 7, стр. 9, 10). ● Если для переменной не существует допу- стимого значения, агент отсылает сообщения ти- па nogood конфликтным агентам с большим при- оритетом и меняет свой приоритет на max +1, где max – наибольший приоритет из приорите- тов его соседей на данный момент (алг. 8, стр. 10–14). Если при отправке сообщения nogood агент имел самый высокий приоритет среди соседей, то сформированный nogood будет пустым, и это послужит сигналом заверше- ния алгоритма в связи с отсутствием реше- ния задачи [3]. На роль третьей компоненты был выбран именно AWCS, поскольку он – один из наибо- лее эффективных алгоритмов конструктивного поиска. Он уступает разве что алгоритму Main- taining Asynchronously Consistencies (MAC). По- следний, как и целый ряд его алгоритмов–по- томков, теперь успешно развивают другое на- правление алгоритмов решения задач DisCOP (Distributed Constraint Optimisation Problem). Ал- горитм же AWCS и все его многочисленные ва- риации утвердили себя как эффективный метод решения DisCSP. По оценке его авторов [3], AWCS в 3–10 раз эффективнее Asynchronous Backtracking. Алгоритм 6. Процедура responde to message procedure responde_to_message { if message is inc penalty if inc penalty on cur val < upper bound increase inc penalty by 1 end if else impose temp penalty end if select new value send(id,val,null) } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Алгоритм 7. Псевдокод про- цедур AWCS Алгоритм 8. Псевдокод про- цедур AWCS procedure receive_ok (value) { add value to agent_view; check_agent_view() } procedure check_agent_view ( ) { if curr val is not consistent select new value if can’t find consistent val backtrack() else send ok message to all end if end if } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 procedure receive_nogood( ) { add state to nogood_store check_agent_view(); } procedure backtrack ( ) { add state to nogood_store for all agents with higher prior if not consistent with cur agent send nogood message prior ← max(all agents’ prior) + 1 select new value with min number of constraint violations send ok message to all } Гибридный алгоритм improve Guided Lo- cal and Systematic Search (GLoSS). Алгоритм GLoSS по классификации гибридных алгорит- мов относится к третьей категории, т.е. совме- щает в себе компоненты конструктивного и локального поиска и характеризуется высоким уровнем их интеграции, при этом операторы конструктивного и локального поиска приме- няются поочередно. База алгоритма – синхронный бектрекинг (Synchronous Backtracking). Он осуществляет ини- циализацию переменных. Учитывая синхрон- ность компонента, агенты действуют не парал- 78 УСиМ, 2012, № 6 лельно, но им уже не требуется сообщать о при- своении значения каждому соседу отдельно. Они передают свой agent view следующему аген- ту со всеми известными им значениями сосе- дей и собственным значением. Следующий агент, выбирающий себе значение, стремится выбрать его так, чтобы избежать возможных конфликтов с уже известными ему значениями соседей с высшим приоритетом. Этот процесс описывается процедурой extend (алг. 10). Алгоритм 9. Главный цикл Алгоритм 10. Процедура кон- структивного поиска procedure main { a is an empty partial solution while a is not solution { do { extend( a ) if a is solution terminate end if }until a is not consistent iGL( a ) if a is not consistent emergency( a ) end if if a is solution terminate end if } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 procedure extend(a) { select value for current agent add new value to a if new value is consistent if agent is not the last send a to next agent else return a end if else send a to all with higher prior send ok mess to conflict agents end if } В случае, когда очередной агент не может расширить частичное решение (не может най- ти себе значение), не попав в конфликтную си- туацию, происходит переход к локальному по- иску (алг. 9, стр. 8–10): ● агент выбирает себе значение с наимень- шим количеством конфликтов; ● агент рассылает всем соседям с высшим приоритетом свой agent_view для того, чтобы каждый агент имел собственный экземпляр ча- стичного решения, и был в курсе всех при- своений; ● агент рассылает конфликтным агентам со- общение со своим значением, инициируя про- цедуру локального поиска. Переход к локальному поиску происходит, когда в SBT должен начаться бектрекинг, но эта процедура в алгоритме GLoSS никогда не применяется. Следует заметить, что в локальном поиске будут участвовать только те агенты, ко- торые уже прошли этап инициализации. Такой подход существенно сокращает количество со- общений, которыми агенты обмениваются в процессе решения. Локальный поиск представлен в алгоритме 10 как repair-процедура. Алгоритм применяется к проинициализированным агентам максимум n раз. Ограничение необходимо для устранения проблемы неполноты локальных алгоритмов. Закончив локальный поиск, активный агент с наивысшим приоритетом отправляет дежур- ному по приоритету агенту (еще неактивному) частичное решение, и тем самым инициирует новый вызов процедуры Synchronous Back- tracking. Расширение частного решения про- должается до тех пор, пока очередной агент не сможет его расширить. Алгоритм 11. Процедура локаль- ного поиска Алгоритм 12. Процедура вспомогательного конст- руктивного поиска procedure iGL(a) { for n steps do { do iGL on a if a is consistent terminate } } 1 2 3 4 5 6 7 8 9 procedure emergency(a) { AWCS(a) } В цепочке вызовов SBT и iGL могут возник- нуть вызовы компоненты AWCS (алг. 12). Она становится нужна в случае, когда iGL не смог найти частичное решение за отведенные ему n шагов. Тогда AWCS завершает поиск, причем га- рантированно (он, в отличие от iGL, – полный). Остановимся на нескольких важных особен- ностях алгоритма. Все компоненты пользуются одним централизованным nogood_store, обеспе- чивая сохранение и передачу «неудачного» опы- та, приобретенного агентами на каком-то из эта- пов работы гибридного алгоритма, всеми компо- нентами. Переход к следующему компоненту не происходит, если решение найдено. Для это- го в алгоритме выполняются соответствующие проверки во всех трех компонентах (алг. 10–12). Теорема 1. Гибридный алгоритм GLoSS – по- лный и корректный. Доказательство. На каждой итерации глав- ного цикла алгоритма происходит поиск допус- тимого частичного решения. Поиск организует- ся средствами как локального, так и конструк- тивного операторов. Конструктивный оператор выполняется после локального и гарантирует УСиМ, 2012, № 6 79 нахождение допустимого частичного решения, если такое существует, или завершение работы алгоритма в связи с отсутствием решения. На последней итерации главного цикла ал- горитма частичное решение рассмотрения ста- новится полным при привлечении к частично- му решению последней незадействованной пе- ременной. Поэтому последовательное выполне- ние над ним операторов локального поиска, а затем, возможно, AWCS, гарантированно дает решение всей задачи, если такое существует. Теорема 2. Для решения DISCSP задачи с N переменными, в которой мощность каждого из доменов переменных не превышает M, времен- ная сложность алгоритма GLoSS есть О (M^N). Средняя временная сложность есть O (M * N). Доказательство. Оценка временной слож- ности гибрида требует оценки сложности каж- дой из его компонент. Начнем с SBT. На каждой итерации алго- ритма имеется выбор из M значений, которые можно присвоить переменной: M + M + M+ ... ... + M ~ M * N. В этой оценке не учтен бектре- кинг, поскольку он в данной реализации нико- гда не происходит. Сложность работы алгоритма iGL можно оце- нить константой C. Вследствие неполноты ал- горитма количество выполненных им итераций ограничивается некоторой константой C, кото- рая есть оценкой алгоритма в худшем случае. Алгоритм AWCS имеет экспоненциальную сложность в худшем случае. Поэтому слож- ность гибрида можно оценить как M * N + C + + M ^ N. Иначе говоря, просто M ^ N. Это наи- худшая оценка. Средней же оценкой алгорит- ма можно считать M * N + C или просто M * N, поскольку алгоритм AWCS, по теоретическим оценкам, участвует в решении задачи не более чем в трех процентах случаев. Отметим, что после появления метода Asyn- chronous Weak-Commitment Search, алгоритмы решения DisCSP стали оценивать еще и по объ- ему памяти, в частности, необходимой для за- поминания «неразрешимых ветвей» в процессе решения. Ведь выигрыш AWCS в скорости срав- нительно с его предшественниками, различными модификациями бектрекинга, компенсируется непомерно большим пространством «плохих» состояний. Эту характеристику AWCS насле- дует и гибрид GLoSS. Для оптимизации памяти введена общая для всех трех компонент гибри- да база неудовлетворительных состояний аген- тов, которая в указанных процедурах называет- ся nogood_store. Для каждого из операторов поиска опыт других должен сократить его соб- ственное пространство поиска. Экспериментальная оценка эффективно- сти алгоритма Алгоритм GLoSS предназначен для реше- ния бинарных DisCSP. Известно, что каждая CSP сводится к бинарной. Классическим при- мером задачи из этого класса служит задача о ферзи. Попытаемся оценить скорость рабо- ты алгоритма GLoSS на ней, варьируя коли- чество ферзей. Остановимся на основных моментах. Снача- ла поясним применение компонента Synchro- nous Backtracking – наименее эффективного ал- горитма. В нашем алгоритме GLoSS компонен- та SBT используется только для расширения ча- стичного решения, пока не возникнет первый конфликт. Разрешение конфликтных ситуаций происходит не путем бектрекинга, а средства- ми двух других компонентов алгоритма. Согласно проведенным экспериментам, SBT способен за первый же проход присвоить зна- чение в среднем 60–70 процентам агентов, на что расходуется примерно 20 процентов от об- щего времени решения. После этого управле- ние процессом поиска передается компоненту iGL. Он примерно в 96–97 процентах случаев находит решение задачи, не превышая отведен- ный ему лимит шагов. Возникает вопрос: как определить факт на- хождения локальным поиском частичного ре- шения и момент окончания работы этой ком- поненты? Самый простой способ – перерыв в работе в течение некоторого длительного про- межутка времени, существенно зависящего как от самого алгоритма и способа его реализации, так и от аппаратного обеспечения. Еще один вопрос требует комментария. Все агенты завершают выполнение процедуры ло- кального поиска в разное время. Время оста- 80 УСиМ, 2012, № 6 новки какого из агентов следует считать вре- менем окончания процедуры iGL? Поскольку для продолжения работы алгоритма требуется активный агент с самым высоким приорите- том, который бы направил следующему по при- оритету (еще не активному) агенту частичное решение, инициировав начало работы проце- дуры SBT, то временем окончания процедуры локального поиска следует считать время окон- чания работы этого агента. Временем начала работы процедуры SBT следует считать момент отправки агентом (с наибольшим приоритетом среди всех агентов) сообщения с частичным решением следующему соседу. Конец работы процедуры SBT инициирует начало работы про- цедуры iGL, поэтому простоя между ними нет. На рисунке изображены графики произво- дительности трех алгоритмов: вертикальная ось отражает время в миллисекундах, горизонталь- ная – количество агентов, т.е. количество фер- зей в задаче (поскольку каждому агенту соот- ветствует один ферзь, т.е. одна переменная). Верхний график соответствует производитель- ности работы Dis-GLS-алгоритма, средний – iGL-алгоритма, и нижний – алгоритма GLoSS. Итак, видим, что сочетание SBT с iGL дало вы- игрыш и положительный результат. Для коли- чества ферзей менее 50 гибрид GLoSS тратит на решение в пять–восемь раз меньше време- ни, чем его эффективный компонент iGL. Для большего количества ферзей (экспери- менты проводились для количества ферзей до 200) производительность гибрида в полтора– два раза больше iGL. Очевидно, что расширение частичного реше- ния на одно значение не дает значительного при- роста производительности. Во-первых, сам вы- зов процедуры SBT – затратный для алгоритма. Во-вторых, добавление к частичному решению только одной переменной говорит о том, что ее значение – конфликтно, поэтому SBT не может продолжать поиск, и процедура только «портит» допустимое частичное решение предыдущего этапа. Поэтому – это проблема на будущее. Временную оценку гибрида GLoSS желатель- но было бы сравнить с оценками других гибри- дов. К сожалению, реализация даже одного гиб- рида требует значительных усилий, поэтому вся работа по оценке производительности алгорит- ма была сведена к его сопоставлению с произ- водительностью работы его быстрой (эффектив- ной) компоненты. Таким образом, удалось по- казать, что гибрид, по крайней мере, не хуже каждого из своих компонент. Заключение. Сделан краткий обзор методов решения класса распределенных задач удовле- творения ограничений (Disctributed Constraint Satisfaction Problem). На основе анализа этих ме- тодов разработано два алгоритма: iGL (improved Guided Local Search), основанный на алгоритме локального поиска Dis-GLS, и гибридный алго- ритм GLoSS (Guided Local & Systematic Search). Гибрид сочетает в себе алгоритмы Synchronous Backtracking, improved Guided Local Search и Asynchronous Weak-Commitment Search. Компо- ненты гибридного алгоритма отличаются не только методами поиска решения задачи (ло- кальный и конструктивный), но и способом син- хронизации. Быстрый, но неполный алгоритм локального поиска iGL подстрахован конструк- тивным алгоритмом AWCS для обеспечения на- хождения решения, если оно существует. Син- хронный главный алгоритм существенно умень- шает поток сообщений между агентами, обес- печивая последовательную обработку перемен- ных. Недостаток синхронного бектрекинга – от- сутствие распараллеливания, компенсируется наличием параллельности вспомогательных ал- горитмов iGL и AWCS. В план дальнейших исследований входит усо- вершенствование алгоритма, связанное с поис- ком решения проблемы эффективности сотруд- ничества компонента SBT с другими компонен- тами гибрида, а также проблема рационализа- ции использования памяти, необходимой для хранения пространства ветвей решения, не при- водящих к решению. Окончание на стр. 88 88 УСиМ, 2012, № 6 Окончание статьи Л.А. Галковской и др. 1. Schulte Ch., Carlsson M. Finite Domain Constraint Pro- gramming Systems // Handbook of Constraint Program- ming / F. Rossi, P. van Beek, T. Walsh (Eds.). – El- sevier, 2006. – P. 493–524. 2. Letichevsky A., Gilbert D. A Model for Interaction of Agents and Environments // Lecture Notes in Comp. Sci. N 1827. Recent Trends in Algebraic Development Tech- niques. – 2000. – P. 119–131. 3. Yokoo M. Asynchronous Weak-commitment Search for solving Distributed Constraint Satisfaction Problems // Proc. of the First Int. Conf. on Principles and Prac- tice of Constraint Programming, 1995. – P. 88–102. 4. Brito I. Synchronous, Asynchronous and Hybrid Algo- rithms for DisCSP // Proc. of the Tenth Int. Conf. on Prin- ciples and Practice of Constraint Programming (CP–2004). Lecture Notes in Comp. Sci., Jan. 2004. – 3258. – 791 p. 5. Silaghi M.-C., Faltings B. Asynchronous aggregation and consistency in distributed constraint satisfaction, Artifi- cial Intelligence, Jan. 2005. – 161, Issues 1–2. – P. 25–53. 6. Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving / M. Yokoo, E. Durfee, T. Ishida et al. // Proc. of the Twelfth IEEE Int. Conf. on Distributed Computing Systems, 1992. – P. 614–621. 7. Yokoo M., Hirayama K. Distributed Constraint Satisfac- tion Algorithm for Complex Local Problems // Third Int. Conf. on Multiagent Systems (ICMAS–98), 1998. – P. 372–379. 8. Zivan R., Meisels A. Synchronous and Asynchronous Search on DisCSPs // Proc. of EUMAS–2003, Oxford, UK, 2003. – P. 103–107. 9. Salido M.F., Barber F. Stochastic Local Search for Di- stributed Constraint Satisfaction Problems // Proc. of IJCAI Workshop on Stochastic Search Algorithms, Acapulco, México, 2003. – P. 49–54. 10. Basharu M., Arana I., Ahriz H. Distributed Guided Lo- cal Search for Solving Binary DisCSPs // Proc. of the 18th Int. FLAIRS (The Florida AI Research Society) Conf. 16–18 May 2005. Florida, 2005. – P. 660–665. 11. Hirayama K., Yokoo M. Distributed Breakout Algo- rithm for Solving Distributed Constraint Satisfaction Problems // Proc. of the Second Int. Conf. on Multi- Agent Systems, MIT Press, 1996. – Р. 401–408. 12. Hoos H.H., Tsang E. Local search methods. Foundati- ons of Artificial Intelligence. – 2006. – 2. – Р. 135–167. 13. Morris P. The Breakout method for escaping from the local minima // Proc. of the Eleventh Nat. Conf. on Ar- tificial Intelligence, 1993. – P. 40–45. 14. Basharu M., Arana I., Ahriz H. Solving DisCSPs with Penalty Driven Search // Proc. of the 20th national conf. on Artificial intelligence, 2005. – 1. – P. 47–42. 15. Chatzikokolakis K., Boukeas G., Stamatopoulos P. Con- struction and Repair: A Hybrid Approach to Search in CSPs. G.A. Vouros, T. Panayiotopoulos (Eds.). – SETN 2004, LNAI 3025, 2004. – Р. 342–351. 16. Eisenberg C., Faltings B. A Hybrid Solving Scheme for Distributed Constraint Satisfaction Problems // The Fourth Int. Workshop on Distributed Constraint Rea- soning at IJCAI, 2003. – P. 19–35. 17. Jussien N., Lhomme O. Local search with constraint propagation and conflict-based heuristics. Artificial In- telligence 139, 2002. – P. 21–45. 18. A Hybrid Approach to Distributed Constraint Satisfac- tion / D. Lee, I. Arana, H. Ahriz et al. // Proc. of the 13th int. conf. on Artificial Intelligence, 2008. – P. 375–379. 19. Multi-hyb: a hybrid algorithm for solving DisCSPs with complex local problems / D. Lee, I. Arana, H. Ahriz et al. / P. Boldi, G. Vizzari, G. Pasi, R. Baeza-Yates (Eds.) // Web Intelligence and Intelligent Agent Technolo- gies, 2009. – P. 379–382. 20. Basharu M., Arana I., Ahriz H. DisBO-wd: a distributed constraint satisfaction algorithm for coarse-grained dis- tributed problems / M. Bramer, F. Coenen, M. Petridis (Eds.). Research and Development in Intelligent Sys- tems XXIV // Proc. of the 27th SGAI Int. Conf. on Ar- tificial Intelligence, AI–07. 10–12 Dec. 2007, Cambridge, 2007. – P. 23–36. Тел. для справок: +38 044 463-6985, +38 050 720-9361 E-mail: gloria.jjl@gmail.com, glib@ukma.kiev.ua, gor@ukma.kiev.ua © Л.А. Галковская, Н.Н. Глибовец, С.С. Гороховский, 2012 

Гибридный алгоритм решения задачи удовлетворения ограничений

Institution

Ähnliche Einträge