متغير بعدي که مقدار نگرفته است متغيري با کمترين مقادير مجاز را انتخاب ميکند. نامهاي ديگر اين تابع اکتشافي محدودترين متغير22 و اولين شکست23 ميباشند. علت نامگذاري اولين شکست آن است که اينگونه متغيرها، به احتمال زياد به زودي به حالت شکست خواهد رسيد.
2- تابع اکتشافي بالاترين درجه (MCO24)
اگر تمام دامنه ها داراي يک اندازه باشند، تابع اکتشافي MRV نخواهد توانست در انتخاب اول هيچ کمکي بکند. تابع اکتشافي بالاترين درجه متغير داري بالاترين درجه محدوديت در مقايسه با ساير متغيرهاي مقدار نگرفته را انتخاب ميکند.
3- تابع اکتشافي مقدار با حداقل محدوديت (LCV25)
پس از انتخاب متغير، مقدار خاصي براي انتساب بايد انتخاب شود. تابع اکتشافي مقدار با حداقل محدوديت، مقداري را براي يک متغير انتخاب ميکند که در گراف محدوديت باعث ايجاد کمترين محدوديت در متغيرهاي مجاور گردد.
در شکل 1-3 عملکرد اين توابع اکتشافي براي رنگ آميزي نقشه ايالات و نواحي استراليا به نحوي که هيچ دو ناحيه اي رنگ يکسان نداشته باشند نشان داده شده است.

(الف)

(ب)
شکل 1-3 (الف) ايالات و نواحي استراليا. رنگ آميزي اين نقشه ميتواند به صورت مسأله ارضاء محدوديت نمايش داده شود. هدف انتساب رنگها به هر ناحيه است، چنانچه هيچ دو ناحيه همسايه اي رنگ يکسان نداشته باشند. قسمت (ب) نحوه عملکرد توابع اکتشافي مختلف بر روي اين نقشه نشان ميدهد [2] .
محدوديتهاي ويژه
برخي از محدوديتها آنقدر زياد در مسائل اتفاق ميافتند که ميتوان آنها را به عنوان حالتهاي خاص بررسي کرد.
محدوديت Alldiff : همه متغيرها بايستي مقادير متفاوت داشته باشند. مسأله 8-وزير يا پازل رياضيات رمزي از اين دسته محدوديتها دارد.
به شکلي رسميتر ميتوان محدوديت Alldiff را به صورت زير تعريف کرد[56]:
با داشتن يک مجموعه از متغيرهاي X={x1, x2, . . . , xn} با دامنه هاي D1, . . . , Dn ، مجموعه اي از چندتايي هاي مجاز به وسيله Alldiff(X) عبارتند از:
{ (d1, d2, . . . , dn) | di ? Di , di ? dj ? i ? j }
محدوديت Atmost يا Resource: مقدار همه متغيرها بايستي حداکثر يک مقدار مشخص باشد.

کاربرد جستجوهاي محلي در حل مسائل ارضاء محدوديت
الگوريتمهاي جستجوي محلي براي حل بسياري از مسائل CSPبسيار موثرند. در اين حالت از فرموله سازي حالت کامل استفاده ميشود که در آن در ابتدا به هر متغير حالت اوليه اي نسبت داده ميشود و سپس در هر مرحله تابع مابعد مقدار يکي از متغيرها را تغيير ميدهد. به عنوان مثال در مسأله 8-وزير در ابتدا هر وزير به تصادف درون يک ستون قرار ميگيرد و سپس تابع مابعد يک وزير را انتخاب نموده و آن را به جاي ديگري درون همان ستون منتقل ميکند. در انتخاب يک مقدار جديد براي يک متغير، تابع اکتشافي حداقل تناقض ها26 بهترين اکتشاف ميباشد. اين تابع همواره مقداري را انتخاب ميکند که کمترين برخورد را با ساير متغيرها ايجاد ميکند.
ساختار مسأله
منظور از ساختار مسأله در مسائل CSP نحوه بيان محدوديتهاست. پيچيدگي حل يک CSP به شدت وابسته به ساختار گراف محدوديت است. گاهي ميتوان از ساختار مسأله به منظور شناخت سريع و آسان راه حل استفاده نمود. اصولا مسائل CSP به صورت گراف محدوديت بيان ميشوند که در موارد خاص ميتوان اين ساختار را تا حدودي ساده تر کرد، همانگونه که تنها راه برخورد با مسائل دشوار دنياي واقعي، تجزيه اين مسائل به مسائل کوچکتر است. اولين راه براي اين کار شناخت زير مسأله هاي مستقل درگراف است. به عنوان مثال در شکل زير T قسمتي مجزا از ساير متغيرهاست. به عبارتي رنگ آميزي T و رنگ آميزي ساير گرهها دو مسأله مستقل هستند پس هر جوابي براي T و هر جوابي براي ساير گرهها، در کنار هم جواب نهايي را تشکيل ميدهند. متأسفانه اين قبيل مسائل بسيار نادر هستند.

شکل 1-4 زيرمسأله هاي مستقل در گراف محدوديت[2]
ساختار بعدي در مسائل CSP ساختار درختي است. به عبارتي گراف محدوديت مسأله يک درخت است. زمان اجراي هر مسأله CSP با ساختار درختي نسبت به تعداد متغيرها داراي رابطه اي خطي ميباشد. از آنجايي که حل يک CSP درختي آسان است ميتوان گرافهاي محدوديت را به درخت تقليل داد. دو راه اساسي براي اين کار شامل:
حذف گرهها: اين روش شامل انتساب مقادير به يکسري از متغيرهاست به نحوي که متغيرهاي باقيمانده يک درخت را تشکيل دهند. به عنوان مثال در شکل زير با انتساب يک مقدار به متغير SA ميتوان آن را از گراف ومقدار انتسابي به آن را از دامنه ديگر متغيرها حذف کرد و به اين صورت يک ساختار درختي را پديد آورد.

شکل 1-5 کاهش گراف محدوديت به درخت توسط حذف گرهها [2]
تجزيه گراف محدوديت به چند زيرمسأله همبند: در اين مدل هر زير مسأله مستقلا حل ميشود و سپس راه حلهاي بدست آمده با هم ترکيب ميشوند.

شکل 1-6 کاهش گراف محدوديت به درخت توسط تجزيه گراف [2]
شرايط لازم براي تجزيه گراف محدوديت به شرح زير است:
– هر متغير در گراف اصلي بايد حداقل در يکي از مسائل آورده شده باشد.
– هر محدوديت در گراف اصلي (و متغيرهايش) بايد حداقل در يکي از زيرمسائل آورده شده باشد.
– اگر يک متغير در دو زير مسأله در درخت آورده شود، آن متغير بايد در تمامي زيرمسائلي که در مسير اتصال آن دو زير مسأله قرار دارند نيز آورده شود.
سيستمهاي چند عامله
برطبق [5] و [6]، به طور کلي يک عامل را ميتوان به اين صورت تعريف کرد: يک عامل، يک موجوديت فيزيکي يا مجازي است که اساسا داراي خصوصيات زير است:
– قادر است در يک محيط زندگي يا عمل کند.

ميتواند محيط محلي را درک کند.
– با يک سري اهداف مشخص کار ميکند.
– تا حدودي رفتارهاي واکنش گرايانه دارد.
البته اين تعريف براي عامل بسيار جامع است و آنچه که يک عامل ارائه ميدهد براي مسائل مختلف متفاوت است.
هر سيستم چند عامله يک سيستم محاسباتي است که در آن چندين عامل جهت رسيدن به يک هدف خاص با هم در تعامل هستند و با هم کار ميکنند. به طور کلي چهار عنصر در هنگام معرفي سيستمهاي چند عامله مطرح ميشود تا مسأله حل شود: الف) معني و هدف هر عامل، ب) محيطي که تمامي عاملها در آن زندگي ميکنند، ج) تعريف محيط محلي با ذکر اين نکته که عاملها تنها قدرت درک محيط محلي خود را دارند و د) رفتارهايي که هر عامل ميتواند براي رسيدن به هدف انجام دهد [7].
حال اينکه چرا مهم است که سيستمهاي چند عامله وجود داشته باشد؛ موقعيتهايي وجود دارد که در آن يک مسأله نياز دارد در يک مد توزيع شده حل شود، يا به اين دليل که يک کنترل کننده مرکزي امکانپذير نيست يا به اين دليل که ميخواهد استفاده مناسبي از منابع توزيع شده داشته باشد. يک مثال خوب براي اين موضوع شبکه هاي حسگر27 است. چنين شبکه هايي حاوي چندين واحد پردازشي، هر کدام با قابليت يک حسگر28 محلي، با قدرت پردازش محدود، منبع تغذيه محدود (مثلا باطري) و ارتباط محدود بين آنهاست. عليرغم اين محدوديتها، اين شبکه ها هدفشان فراهم آوردن چند سرويس کلي است. شکل 1-7 يک شبکه حسگر براي تهويه هواي يک ساختمان را نشان ميدهد. هر حسگر تنها ميتواند ناحيه محلي خودش را مانيتور کند همچنين تنها ميتواند با همسايه هايش ارتباط داشته باشد. سوأل اين است که اين تک حسگرها چه الگوريتمي بايد اجرا کنند بطوريکه اين قطعات با هم يک تصوير قابل اعتماد از کل را داشته باشند [4].

شکل 1-7 يک شبکه حسگر واقعي براي مانيتور کردن محيط داخلي يک ساختمان [4]

حل مسائل CSP توسط سيستمهاي چند عامله؛(DCSP)
وقتي يک مسأله قرار است توسط سيستمهاي چند عامله حل شود فرم مسأله به يک حالت توزيع شده تبديل ميشود. مسأله ارضاء محدوديت توزيع شده حالت توزيع شدهي مسألهي ارضاء محدوديت کلاسيک است که پيش تر به طور کامل توصيف شد. اين محيط توزيع شده شامل تعدادي عامل هوشمند است که هر کدام، يک يا چند متغير را حمل و کنترل ميکنند. مسأله ارضاء محدوديت توزيع شده اولين بار توسط سيکارو، يوکو و همکارانشان به صورت رسمي مطرح شد [9] و [10]. به طور کلي يک مسأله ارضاء محدوديت توزيع شده شامل يک 4تايي مرتب P = است که هر جزء آن به صورت زير تعريف ميشود:
يک مجموعه متناهي از n متغير، {V = {x1, x2, …, xn؛
يک مجموعه متناهي از g عامل، {A = {a1, a2, …, ag؛
يک مجموعه دامنه D، شامل يک دامنه گسسته و متناهي براي هر متغير:
D = {D1, D2, …, Dn} , Di = {d1, d2, . . ., d|Di| } for xi , i = 1, 2,. . . , n ;
يک مجموعه از محدوديتها، { C = {C1(x1 ), C2(x2 ), …, Cm(xm) ، که xi ، i=1, 2 , . . . , n ، زيرمجموعه اي از x است و Ci(xi) تعيين کننده مقاديري است که متغيرهاي درون xi نميتوانند به صورت همزمان به خود بگيرند. به عنوان مثال يک محدوديت به صورت ?C({x1, x2}) = ?d1, d2 بدين معني است که وقتي x1= d1 آنگاه مقدار d2 نميتواند به x2 انتساب يابد و زماني که x2 = d2 است x1 نميتواند مقدار d1 بگيرد.
هدف نهايي حل مسأله ارضاء محدوديت توزيع شده، مشابه مسأله ارضاء محدوديت استاندارد که پيشتر تعريف شد، هنوز يافتن مقاديري براي انتساب به متغيرهاست که کل محدوديت هاي موجود را ارضاء کند. يک الگوريتم خوب در اين فيلد الگوريتمي است که تضمين ميکند که يک پروسه با يک راه حل قانوني و در يک مدت زمان قابل قبول خاتمه مييابد و يا نشان دهد هيچ راه حل قانوني وجود ندارد. منظور از راه حل قانوني راه حلي است که به هر متغير يک مقدار از مقادير دامنه اش انتساب يافته باشد به طوريکه هيچ محدويتي از محدوديتهاي تعريف شده در مسأله نقض نشده باشد. در يک سيستم چند عاملي به هر عامل يک يا چند متغير از ميان متغيرهاي توزيع شده منتسب ميشود. وظيفه اين عامل خودمختار کنترل و مديريت مقدار اين متغير ميباشد. هر عامل سعي ميکند نه تنها با ارضاء محدوديتهاي محلي خود بلکه با برقراي ارتباط با ساير عاملها به منظور حل محدوديتهاي خارجي به اين هدف نزديک و نزديکتر شود. به طور کلي تمام مسائلي که در آنها هدف يافتن مقادير مناسب براي انتساب به متغيرهاي توزيع شده است را ميتوان جزء مسائل ارضاء محدوديت توزيع شده به حساب آورد. بسياري از مسائل مطرح در دنياي واقعي و مسائل چند عاملي را ميتوان تحت اين مدل در نظر گرفت، که از جمله ميتوان به مواردي نظير زمانبندي توزيع شده [11]، مسائل انتساب منابع توزيع شده [12] و نگهداري واقعيات يا صحت چند عاملي [13]، اشاره کرد.

فصل دوم

مروري بر تحقيقات پيشين
مرور کلي
همانطورکه پيشتر گفته شد، تمام مسائلي که در آنها هدف يافتن مقادير مناسب براي انتساب به متغيرهاي توزيع شده است را ميتوان جزء مسائل ارضاء محدوديت توزيع شده به حساب آورد. مثلا در بسياري از مسائل تخصيص منابع: در شبکه هاي حسگر بيسيم، کنترل علائم راهنمايي شهري، شبکه هاي حسگر توزيع شده، مسائل نجات يافتن از فاجعه و بسياري از مسائل مربوط به زمان بندي مثلا براي قطارها و دانشگاه ها. هدف معمول در حل همه اين مسائل يافتن مقادير مناسب براي تخصيص دادن به متغيرهاي توزيع شده است. به عبارت ديگر هر مسألهاي که هدف آن يافتن مقدار مناسبي براي تخصيص به متغيرهاي توزيع شده است ميتواند به عنوان DCSP طرح ريزي شود
. با توجه به وسعت اين دسته از مسائل، الگوريتمهاي متنوعي براي حل آنها از سال 1991 تاکنون ارائه شده است. برخي از اين الگوريتمها مانند الگوريتم عقب گرد نامتقارن (ABT29) [14]، و الگوريتم الزام ضعيف نامتقارن (AWC30) [15]، کاملا توزيع شده هستند در حاليکه برخي ديگر از ترکيب روشهاي توزيع شده و متمرکز استفاده ميکنند. يکي از موفق ترين الگوريتمهاي مطرح در دسته دوم الگوريتم (APO31) است که توسط ميلر و لزر ارائه شده است[16]. با يک ديد گسترده تر ميتوان يک دسته بندي همانند شکل 2-1 را براي الگوريتمهاي مسائل ارضاء محدوديت توزيع شده در نظر گرفت:

شکل 2-1 يک طبقه بندي از الگوريتمهاي مطرح در حل مسائل DCSP
به طور کلي الگوريتم هايي که براي حل DCSP وجود دارند ميتواند به دو گروه تقسيم شوند: کامل 32و ناقص33. الگوريتم هاي کامل، الگوريتم هايي هستند که يافتن راه حل را، البته اگر وجود داشته باشد، تضمين ميکنند و يا وقتي که مسأله راه حلي ندارد از کار متوقف ميشوند. الگوريتم هاي کامل خود به دو گروه تقسيم ميشوند: روشهاي کاملا توزيع شده و دوم ترکيب روشهاي توزيع شده و متمرکز. الگوريتم هاي کاملا توزيع شده، الگوريتم هايي هستند که يک گره مرکزي ندارند. و هر گره نيز اطلاعات محدودي درباره محدوديتهايش دارد. در اين گروه، عامل ها با هم هماهنگ ميشوند تا مسأله را با استفاده از دانش محدودي که دربارهاش دارند حل کنند. يوکو34 و سايرين همکاري هاي مهمي در الگوريتم هاي کاملا توزيع شده داشتهاند. آنها الگوريتم عقبگرد نامتقارن را ايجاد کردند که کامل بودن35 را تضمين ميکند[36-32]. بعدها اين الگوريتم را به الگوريتم کارامدتري با نام الزام ضعيف نامتقارن، با معرفي ترتيب پويا در ميان عاملها، گسترش دادند.
گروه ديگر الگوريتم هاي کامل، الگوريتم هايي هستند که در واقع از ترکيب روشهاي توزيع شده و متمرکز استفاده ميکنند. در اين دسته الگوريتمها برخي عامل ها در تلاشند تا اطلاعاتي را از عامل هاي ديگر جمع آوري کنند تا مسأله را از بنياد حل کنند و سپس اجازه دهند عامل هاي شرکت کننده مقاديري را که براي متغيرهايشان انتخاب شده است را بدانند. APO مثال خوبي براي اين گروه از الگوريتم ها است. استفاده از درجه اي از متمرکز سازي به الگوريتم ها اجازه ميدهد با پيامهاي کمتري نسبت به الگوريتم هاي کاملا نامتمرکز مسأله را حل کنند. از سوي ديگر اين متمرکز سازي آسنکروني حل مسأله را کاهش ميدهد. به عبارت ديگر همانطور که برخي از عامل ها اطلاعاتشان را به يال مرکزي ميفرستند تا پردازش شود، بار محاسباتي به طور نامتقارني بين عامل ها تقسيم ميشود که منجر به کاهش دادن همزماني پروسه حل مسأله ميشود[31].
در چارت بالا يک طبقه بندي کلي از الگوريتم هاي اصلي در اين زمينه را نشان دادهايم که در واقع ميتوان گفت اين چارت تقسيم بندي خوبي از الگوريتم هايDCSP بر اساس دو ويژگي مهم اين الگوريتم ها يعني کامل بودن36 و متمرکزسازي37 انجام ميدهد.
ميتوان گفت کامل بودن ويژگي بسيار مطلوبي است اما اين ويژگي در مسائل ترکيبي دشوار، غير قابل حل است. از اينرو، رويکردهاي ناقص پيشنهاد شدهاند که جامعيت را کنار گذاشتهاند و سعي در پيدا کردن سريع راه حل نسبتا خوب به شيوه فرصت طلبانه نمودهاند. اين شيوه ها معمولا


دیدگاهتان را بنویسید