تعريف محدوديت 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].


پاسخی بگذارید