3-2-3- مسائل زمانبندی …………………………………………………………………………………………………………………………………………………… 48
3-2-4- مسائل ارضاء محدودیت باینری ……………………………………………………………………………………………………………………………. 51
3-3- طراحی و پیاده سازی روشهای پیشنهادی و نتایج حاصله از آنها………………………………………………………. 52
3-3-1- استفاده از ترکیب الگوریتمهای تکاملی و سیستمهای چندعامله برای حل مسائل ارضاء محدودیت ……………… 52
3-3-2- قدرت مورچه ها در حل مسائل ارضاء محدودیت توزیع شده……………………………………………………………………………… 60
فصل چهارم: روش جدید ارائه شده
4-1- مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی…………………………………………………….. 69
توصیف مسائل ارضاء محدودیت توزیع شده؛(DCSP) ……………………………………………………………………………….. 69
تعریف محدودیت Alldiff یا Alldifferent ………………………………………………………………………………………………. 70
توابع اکتشافی …………………………………………………………………………………………………………………………………………………… 70
تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ……………………………………………………………. 71
4-3- توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن…………………………………………………………………… 73
4-4- حل یک مثال با استفاده از این الگوریتم…………………………………………………………………………………………….. 80
4-5- ارزیابی و مقایسه الگوریتم ما با دیگر روشها………………………………………………………………………………………. 82
4-6- نتیجه گیری و برشمردن مزایا و معایب این روش…………………………………………………………………………….. 84
فصل پنجم: نتیجه گیری

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

5-1- نتیجه گیری……………………………………………………………………………………………………………………………………… 87
5-2- پیشنهادات و کارهای آینده………………………………………………………………………………………………………………. 89
فهرست منابع……………………………………………………………………………………………………………………….. 90
فهرست تصاویر
عنوان صفحه
شکل 1-1 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 4
شکل 1-2 یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54] ……………………….. 5
شکل 1-3 (الف) نواحی استرالیا (ب) عملکرد توابع اکتشافی مختلف بر روی این نقشه [2] …………………………………………… 11 شکل 1-4 زیرمسأله های مستقل در گراف محدودیت [2] ……………………………………………………………………………… 13
شکل 1-5 کاهش گراف محدودیت به درخت توسط حذف گرهها [2] ………………………………………………………….. 13
شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2] ……………………………………………………………. 14
شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[4] ………………………………. 15
شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20
شکل 2-2 چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4] ……………………………………………………………………………………………………………………………………. 24
شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسئله 4 وزیر[4] ………………………………………………………………………… 29
شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 29
شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسئله 4 وزیر[4] …………………………………………………………………….. 30
شکل 2-6 سیکل 4 و 5 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………… 30
شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31
شکل 2-8 سیکل 7 و 8 از الگوریتم ABT بر روی مسئله 4وزیر[4] ………………………………………………………….. 31
شکل 2-9 سیکل 9 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31
شکل 2-10 سیکل 10 از الگوریتم ABT بر روی مسئله 4وزیر [4] ……………………………………………………………… 32
شکل 2-11 الگوریتم APO [22] ……………………………………………………………………………………………………………………. 35
شکل 2-12 مثالی از گراف ساختار [44] …………………………………………………………………………………………………………. 39
شکل 2-13 ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… 40
شکل 3-1 جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. 46
شکل 3-2 یک جواب برای مسأله 8-وزیر …………………………………………………………………………………………………………. 47
شکل 3-3 مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… 48
شکل 3-4 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 52
شکل 3-5 مدل فرض شده از محیط شبکه مانند عاملها[3] ……………………………………………………………………………. 53
شکل 3-6 میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [3] ……………………………………. 58
شکل 3-7 مقایسه الگوریتم MAEA-CSPs با 4 الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59
شکل 3-8 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… 63
شکل 3-9 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63
شکل 3-10 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .32 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 63
شکل 3-11 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.3 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64
شکل 3-12 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .72 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 64
شکل 3-13 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.7 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65
شکل 4-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72
شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA ………………………………………………………………………………………………….. 80
شکل 4-3 مرحله 5 از الگوریتم DACA ………………………………………………………………………………………………………….. 81
شکل 4-4 مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82
شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از 4 تا 104 در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82
فهرست جداول
عنوان صفحه
جدول 3-1 نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… 59
جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکمهای متفاوت …………………………………………….60
جدول4-1 مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل ……… 82
جدول4-2 مقایسه روش پیشنهادی ما با روش ERA از لحاظ میانگین زمان اجرا ……………………………………….. 82
فصل اول
مقدمه
از سال 1974، مسائل ارضاء محدویت (CSP1) در مسأله پردازش تصویر2 پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر3 و رنگ آمیزی گراف4 گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی5 و تخصیص منابع6 و دیگر مسائل کاربردی بزرگ میتوانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار میروند [4].
از طرف دیگر موقعیتهایی وجود دارد که در آن یک مسأله بایستی در یک مد توزیع شده حل شود به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه میخواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در چنین مواقعی عاملها7 برای رسیدن به یک هدف مشترک تلاش میکنند. هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار میکنند [4].
مسأله ارضاء محدودیت توزیع شده (DCSP8) در واقع حالت توزیع شدهی مسألهی ارضاء محدودیت کلاسیک است که در آن متغیرها بین عاملهای مستقل توزیع شدهاند. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را مالک میشوند و مقدار آن را کنترل میکنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم میگیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها میتواند با همسایه اش در گراف محدودیت ارتباط برقرار کند. هر عامل سعی میکند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب میشود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر میباشد [4] و [22]. این مسأله عمومی کاربردهای زیادی در زندگی واقعی دارد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده است. به عبارت دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است میتواند به عنوان DCSP طرح ریزی شود.
در این تحقیق به مسائل ارضاء محدودیت توزیع شده پرداخته میشود که در آن عاملها در یک مد توزیع شده برای یافتن یک راه حل ممکن برای مسأله تلاش میکنند.
مسأله ارضاء محدودیت
تعریف مسأله ارضاء محدودیت
به عنوان یک تعریف رسمی، یک CSP را میتوان با سه جزء اصلی آن تعریف کرد[3]:
یک مجموعه متناهی از متغیرها ، {x = {x1, x2, …, xn؛
یک مجموعه دامنه 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 بگیرد.
بنابراین فضای جستجوی S یک مسأله CSP عبارت است از یک ضرب کارتزین ازn مجموعه دامنه متناهی، به عبارت دیگر، S = D1 × D2 × . . . × Dn . یک راه حل برای یک CSP به صورت: s = 〈s1, s2, …, sn 〉 ∈ S، عبارت است از یک انتساب از مقادیر به متغیرها به طوریکه این انتساب تمام محدودیت ها را ارضاء کند. در اینجا یک مثال ساده از توصیف یک مسأله CSP داریم:
x = {x1, x2, x3}

در این سایت فقط تکه هایی از این مطلب(به صورت کاملا تصادفی و به صورت نمونه) با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود-این مطالب صرفا برای دمو می باشد

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

D = {D1, D2, D3}, Di = {1, 2, 3}, i = 1, 2, 3
C = {C1 ({x1, x2}) = <1,3>, C2({x1, x2}) = <3,3>,
C3 ({x1, x3}) = <2,1>, C4({x1, x3}) = <2,3>,
C5 ({x1, x3}) = <3,1>, C6({x1, x3}) = <3,3>,
C7 ({x2, x3}) = <1,1>, C8({x2, x3}) = <1,2>,
C9 ({x2, x3}) = <1,3>, C10({x2, x3}) = <2,1>,
C11 ({x2, x3}) = <3,1>}
تمام راه حلهای ممکن برای مسأله ای که به صورت بالا توصیف شده است عبارت است از: 〈〈1,2,2 ، 〈〈1,2,3 ، 〈〈2,2,2 ، 〈〈2,3,2 ، 〈〈3,2,2 .
به بیانی سادهتر، یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. شکل 1-1 مثالی ساده از یک مسأله CSP را نشان میدهد که دارای سه متغیر x1, x2, x3 و محدودیتهای x1<>x3 و x2<>x3 است.
شکل 1-1 مثالی از مسأله CSP [4]
همانطور که گفته شد بسیاری از مسائل دنیای واقعی میتواند برای حل شدن به صورت یک مسأله CSP فرموله شوند. شکل 1-2 یک طرح جامع از به کار بردن تکنیک ارضاء محدودیت برای حل مسائل را نشان میدهد. با داشتن یک توصیفی از مسأله یک راه برای تعیین اینکه چگونه این مسأله میتواند توسط تکنیک ارضاء محدودیت حل شود تعریف سه جزء: متغیرها، دامنه متغیرها و محدودیتهاست. اگر بتوان این سه جزء را برای مسأله تعریف کرد این مسأله میتواند توسط تکنیکهای ارضاء محدودیت حل شود [54].
شکل 1-2 یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54]
الگوریتمهای کلاسیک مسائل ارضاء محدودیت
به طور کلی 4 الگوریتم به عنوان الگویتمهای کلاسیک حل مسائل CSP معرفی شده است [1]:
الگوریتم بازگشت به عقب (BT9)، الگوریتم عمیق شونده تکراری (IB10)، الگوریتم بررسی رو به جلو (FC11)، الگوریتم پرش رو به عقب (BJ12).
این الگوریتمها از ساختار درختی برای نشان دادن حالت فعلی جستجو استفاده میکنند. هریک از گره های درخت میتواند به عنوان یک راه حل جزئی13 در نظر گرفته شود. به طور همزمان مقادیر برخی از متغیرها از هر گره توسط یک لایه گره تصمیم گیری والد شناسایی میشود، این متغیرها متغیرهای گذشته نامیده میشوند. در مقابل متغیرهای گذشته متغیرهای آینده هستند که مقدار متغیرشان در یک گره انتخاب نشده است و مقدار این متغیرها ممکن است در یک زمان بعد تعیین شود. علاوه بر این متغیرهای جاری نیز داریم که در واقع همان متغیرهایی هستند که در حال حاضر در نظر گرفته شده اند. شاخه های درخت مقادیر ممکن متغیرهاست. بعد از انتخاب یک شاخه در درخت الگوریتم یک مقدار را به متغیر انتساب خواهد داد و توسط راه حل یافته شده تا اینجا مقادیر ناسازگار را از محدوده مقادیر متغیرهای آینده حذف خواهد کرد. چند الگوریتم بالا در نحوه برخورد با متغیر های آینده متفاوت هستند.
الگوریتم BT
هر گره یک مقدار برای آن متغیر که در حال مقایسه با راه حل جزئی جاری است، مشخص خواهد کرد. اگر محدودیتی نقض شد یا برخوردی با مقادیر متغیرهای گذشته داشت آنگاه برای مقدار دیگری برای آن متغیر جستجو میشود. زمانی که تمامی مقادیر در محدوده جاری جستجو شد اگرهیچ مقداری برای آن متغیر یافت نشود که با مقادیر متغیرهای گذشته در تناقض نباشد آنگاه الگوریتم به متغیر قبلی باز خواهد گشت تا مقداری دیگر از محدوده آن متغیر را بیابد. اگر هر متغیر مقداری از محدوده اش را به خود بگیرد در حالیکه هیچ محدودیتی نقض نشده است این الگوریتم خاتمه خواهد یافت.
الگوریتم IB
این الگوریتم اساسا یک الگوریتم جستجوی اول- عمق است با یک مقدار آستانهb . اگر B مجموعه آستانه جاری باشد و یک گره از درخت جستجو یا یک متغیر b بار ملاقات شده باشد آنگاه به زیر-گرههایی که ممکن است نادیده گرفته شوند دسترسی پیدا نخواهد کرد. اگر در این محدوده راه حلی پیدا نشود مقدار آستانه رفته رفته افزایش مییابد. اما اگر یک راه حل یافته شود یا مقدار آستانه b بزرگتر مساوی بزرگترین تعداد شاخه های درخت جستجو باشد این الگوریتم ممکن است خاتمه یابد.
الگوریتم FC
فرایند الگوریتم FC اساسا مشابه الگوریتم بازگشت به عقب است با این تفاوت که در این الگوریتم هر بار که برای یک متغیر عملیات انتساب انجام میشود الگوریتم FC تعدادی از مقادیر ناسازگار با مقدار متغیر جاری را از دامنه مقادیر دیگر متغیرها حذف میکند. اگر دامنه ای خالی شود مقدار انتسابی به متغیر جاری رد خواهد شد؛ در غیر اینصورت، الگوریتم FC این روند را برای دیگر متغیرها ادامه خواهد داد تا زمانی که به همه متغیرها مقداری انتساب یابد. اگر متغیر جاری همه مقادیرش رد شود عملیات بازگشت به عقب به متغیر قبلی انجام میشود. اگر هیچ متغیری برای بازگشت به عقبی وجود نداشته باشد مسأله غیر قابل حل است.
الگوریتمBJ
تنها تفاوت بین الگوریتم BT و BJ فرایند بازگشت به عقب آنهاست، مابقی دو الگوریتم یکسان است. وقتی نیاز به بازگشت به عقب باشد الگوریتم BJ به دنبال متغیرهایی خواهد گشت که باعث شکست شده اند. اگر هر مقدار از دامنه متغیر فعلی با مقدار متغیر های قبلی برخورد داشته باشد الگوریتم به نزدیکترین متغیری که باعث شکست شده است به عقب باز خواهد گشت نه اینکه تنها به متغیر قبلی برگردد. به عبارت دیگر این الگوریتم از روشی هوشمند در زمان بازگشت به عقب استفاده خواهد کرد. در این روش مجموعه ای داریم به نام مجموعه برخورد14، مجموعه برخورد متغیر x شامل همه متغیرهایی است که قبلا مقدار گرفته اند و در گراف محدودیت به x متصل شدهاند. حال اگر در زمان حل مسأله نیاز به عقب گرد باشد، الگوریتم به آخرین گره از مجموعه برخورد آن متغیری که در آن به شکست رسیده است برمیگردد، یعنی به متغیری از آن مجموعه که نسبت به سایر اعضای مجموعه دیرتر مقداردهی شده است.

CSP به عنوان یک مسأله جستجو
یک مسأله CSP را میتوان توسط فرموله سازی افزایشی15 به صورت یک مسأله جستجوی استاندارد ارائه کرد [2]. برای این کار داریم:
حالت اولیه: انتساب تهی، که در آن هیچ متغیری مقدار ندارد.
تابع مابعد: انتساب یک مقدار به یکی از متغیرهای بدون مقدار. این مقداردهی بایستی به صورتی باشد که هیچ یک از محدودیت ها را نقض نکند.
آزمون هدف: آیا انتساب فعلی انتساب کاملی است؟
هزینه مسیر: یک هزینه ثابت برای هر مرحله در نظر گرفته میشود.
با استفاده از فرموله سازی مسائل CSP به صورت مسائل جستجو، میتوان از هر یک از الگوریتمهای جستجو برای حل این مسائل استفاده کرد.
از آنجایی که هر راهحل یک انتساب کامل میباشد بنابراین اگر مسأله ای دارای n متغیر باشد آنگاه راه حل در عمق n یافت خواهد شد و درخت جستجو نیز دارای عمق n میباشد. با توجه به این جستجوی عمقی برای CSP ها مناسبترند. از آنجایی که مسیری که از طریق آن به هدف میرسیم چندان اهمیتی ندارد بنابراین میتوانیم از فرموله سازی حالت کامل16 استفاده کنیم که در آن هر حالت یک انتساب کامل میباشد که ممکن است برخی از محدودیتها را ارضا نکند. از الگوریتمهای جستجوی محلی مانند تپه نوردی میتوان برای حل این مسائل استفاده نمود.
بهبود کارآیی الگوریتمهای جستجو توسط توابع اکتشافی
سیستم‌های پیچیده اجتماعی، تعداد زیادی از مسائلِ دارایِ طبیعتِ ترکیباتی را پیش روی ما قرار می‌دهند. مسیر کامیون‌های حمل‌ونقل باید تعیین شود، انبارها یا نقاط فروش محصولات باید جایابی شوند، شبکه‌های ارتباطی باید طراحی شوند، کانتینرها باید بارگیری شوند، رابط‌های رادیویی می‌بایست دارای فرکانس مناسب باشند، مواد اولیه چوب، فلز، شیشه و چرم باید به اندازه‌های لازم بریده شوند؛ از این دست مسائل بی‌شمارند. تئوری پیچیدگی به ما می‌گوید که زمان حل مسائل ترکیباتی اغلب چندجمله‌ای نیستند. این مسائل در اندازه‌های کاربردی و عملی خود به قدری بزرگ هستند که نمی‌توان جواب بهینۀ آنها را در مدت زمان قابل پذیرش به دست آورد. با این وجود، این مسائل باید حل شوند و بنابراین چاره‌ای نیست که به جواب‌های زیر بهینه بسنده نمود؛ به گونه‌ای که دارای کیفیت قابل پذیرش بوده و در مدت زمان قابل پذیرش به دست آیند. چندین رویکرد برای طراحی جواب‌های با کیفیت قابل پذیرش تحت محدودیت زمانی قابل پذیرش پیشنهاد شده است.
الگوریتم‌هایی وجود دارند که می‌توانند یافتن جواب‌های خوب در فاصله مشخصی از جواب بهینه را تضمین کنند که به آنها الگوریتم‌های تقریبی می‌گویند. الگوریتم‌های دیگری هستند که تضمین می‌دهند با احتمال بالا جواب نزدیک بهینه تولید کنند که به آنها الگوریتم‌های احتمالی گفته می‌شود. جدای از این دو دسته، می‌توان الگوریتم‌هایی را پذیرفت که هیچ تضمینی در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتایج آنها، به طور متوسط بهترین تقابل کیفیت و زمان حل برای مسأله مورد بررسی را به همراه داشته‌اند؛ به این الگوریتم‌ها، الگوریتم‌های اکتشافی گفته می‌شود.
توابع اکتشافی عبارتند از معیارها، روشها یا اصولی برای تصمیم‌گیری بین چندین خط‌مشی و انتخاب اثربخش‌ترین برای دستیابی به اهداف موردنظر. توابع اکتشافی نتیجه برقراری اعتدال بین دو نیاز هستند: نیاز به ساخت معیار‌های ساده و در همان زمان توانایی تمایز درست بین انتخاب‌های خوب و بد.
خاصیت توابع اکتشافی خوب این است که ابزار ساده‌ای برای تشخیص خط مشی‌های بهتر ارائه دهند و در حالی که به صورت شرطی لازم، تشخیص خط‌مشی‌های اثربخش را تضمین نمی‌کنند اما اغلب به صورت شرط کافی این تضمین را فراهم ‌آورند. بیشتر مسائل پیچیده نیازمند ارزیابی تعداد انبوهی از حالت‌های ممکن برای تعیین یک جواب دقیق می‌باشند. زمان لازم برای یافتن یک جواب دقیق اغلب بیشتر از یک طول عمر است. توابع اکتشافی با استفاده از روش‌هایی که نیازمند ارزیابی‌های کمتر هستند و جوابهایی در محدودیت‌های زمانی قابل قبول ارایه می‌نمایند، دارای نقشی اثربخش در حل چنین مسائلی خواهند بود.
الگوریتمهای جستجو اغلب برای افزایش کارایی به دانش مرتبط با جهان مسأله نیاز دارند، اما مسائل CSP میتوانند بدون دانش وابسته به جهان مسأله به صورت کارایی حل شوند. روشهای عمومی قادرند با پاسخ به سوالات زیر توابع اکتشافی عمومی مناسبی را جهت افزایش کارایی الگوریتمهای حل مسائل CSP پیشنهاد دهند:
متغیر بعدی که قرار است مقدار بگیرد کدام است؟17
مقدار گیری بر اساس چه ترتیبی انجام شود؟18
مقداردهی متغیر جاری چه پیامدهایی برای سایر متغیرهای انتساب نیافته دارد؟ 19

چگونه میتوان از تکرار مسیرهای منجر به شکست جلوگیری کرد؟20
برخی از این توابع اکتشافی عبارتند از:
تابع اکتشافی حداقل مقادیر باقیمانده(MRV21)
این تابع اکتشافی برای انتخاب متغیر بعدی که مقدار نگرفته است متغیری با کمترین مقادیر مجاز را انتخاب میکند. نامهای دیگر این تابع اکتشافی محدودترین متغیر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 = <V, A, D, C > است که هر جزء آن به صورت زیر تعریف میشود:
یک مجموعه متناهی از 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 ;


پاسخ دهید