دانلود پایان نامه

برخي توابع اکتشافي استفاده ميکنند تا جست و جو را به سمت قسمتهاي اميد بخشتري از فضاي جستجو بکشانند. الگوريتم انفجاري توزيع شده و الگوريتم احتمالي توزيع شده DSA38 مثالهاي خوبي از الگوريتم هاي ناقص DCSP هستند. الگوريتم احتمالي توزيع شده، تکنيک تپه نوردي توزيع شده است که مشهورترين نسخه آن DSA-B است که با مجبور کردن عاملها به تغيير تخصيص هايشان با احتمال p عمل ميکند. هم چنين ايده اوليه DSA اين است که مکررا عاملها را وادار به بهبود همزمان مجموعه تخصيص هاي ناقص و موقت براي متغيرهايشان کنند، در حالي که چنين مجموعه هاي موقتي را تا زماني که راه حلي براي نمونهاي از مسائل ارضا محدوديت توزيع شده پيدا کنند به هم ارتباط ميدهند.
از آنجا که CSP، پايه و اساس DCSP است، بسياري از الگوريتمهاي مطرح شده براي حل CSP نيز پايه الگوريتمهاي مطرح براي حل DCSP هستند. مثلا الگوريتم عقبگرد نامتقارن نسخه توزيع شده الگوريتم عقبگرد است که قبلا توضيح داده شد، و يا الگوريتم الزام ضعيف نامتقارن نسخه توزيع شده الگوريتم الزام ضعيف متمرکز39 است که در ادامه توضيح خواهيم داد.
در الگوريتم ABT هر عامل يک مقدار تصادفي از مقادير موجود در دامنه اش را به متغيرش منتسب ميکند. از آنجا که در اين الگوريتم هر عامل يک شماره الويت دارد، اگر مقدار منتسب به متغير يک عامل با مقدار عاملهاي با اولويت بالاترش سازگار نباشد عامل کم اولويتتر بايد مقدارش را تغيير دهد. به زبان ديگر، در چنين شرايطي عامل کم اولويتتر تمام مقادير ممکن براي انتساب به متغيرش را بررسي ميکند و در صورت عدم وجود مقدار سازگاري، به عقب باز ميگردد.
الگوريتم موفق ديگر، AWC است که بسياري از خصوصيات ABT را به ارث ميبرند اما از يک روش ابتکاري جديد به نام کمترين برخورد40 سود ميبرد. با استفاده از اين روش احتمال اتخاذ تصميمات بد و انتخاب راه حل هاي نامناسب کاهش مييابد. کارآيي اين دو الگوريتم با استفاده از انواع روشهاي ابتکاري و هوشمند ارائه شده به سرعت بهبود يافته است.
در ادامه ابتدا چند نمونه از الگوريتم هاي جستجوي آسنکرون کاملا توزيع شده که در آنها هر عامل متناظر با يک متغير است و اين عاملها براي حل CSP به صورت آسنکرون عمل ميکنند، را توصيف ميکنيم سپس نمونهاي از مدل ترکيبي توزيع شده و متمرکز را تشريح ميکنيم. پس از آن نمونهاي از تلاشهاي موفق انجام شده در حل اين نوع مسائل به صورت ترکيبي از روشهاي توزيع شده و متمرکز و در پايان يکي از کارهاي اخيرا انجام شده در اين فيلد بر پايه الگوريتمهاي ناقص را بررسي خواهيم کرد.
مدل ارتباطي زير را درنظر ميگيريم :
عاملها از طريق ارسال پيغام با هم ارتباط برقرار ميكنند.
تاخير دريافت پيغام، متناهي است.
بين هر جفت عامل پيغامها به ترتيب ارسال، دريافت ميشوند.
به علاوه عاملهايي که داراي اتصالاتي به xi هستند، همسايه xi ناميده ميشوند. فرض ميکنيم که هر متغير همسايگانش را ميشناسد.

الگوريتمهاي هرس دامنه41
تحت الگوريتمهاي هرس دامنه عاملها به منظور حذف مقاديري از دامنه اشان با همسايههايشان ارتباط برقرار ميکنند. ما به دو نمونه از اين دسته الگوريتم به صورت مشروح اشاره ميکنيم: الگوريتم تصفيه42 و فرا استدلال43.
2-2-1- الگوريتم تصفيه
در اين روش هر گره، دامنه اش را به همسايه اش اطلاع ميدهد و سپس هر گره مقاديري از دامنهاش که با مقادير دريافتي از همسايه اش سازگار نيست را حذف ميکند و اين روند تکرار ميشود.
Procedur Revise(xi, xj)
Forall vi ? Di do
if there is no value vj ? Dj such that vi is consistent with vj then
Delete vi from Di

به طور خاص هر گره xi با دامنه Di به صورت مکرر روند Revise(xi,xj) را براي هر همسايه xj ، تکرار ميکند. اين پروسس زماني خاتمه مييابد که هيچ حذف ديگري اتفاق نيفتد و يا تا زمانيکه دامنه يکي از متغيرها خالي شود (که در اين مورد هيچ راه حلي براي اين مسأله وجود ندارد). حال اگر الگوريتم با يک مقدار در هر دامنه خاتمه يابد، آنگاه مجموعهاي از مقادير تشکيل يک راه حل را ميدهند و اگر با چند مقدار در هر دامنه خاتمه يابد نتيجه نامعلوم است. مسأله ممکن است يک راه حل داشته باشد يا نداشته باشد. به طور واضح، الگوريتم تضمين ميکند که خاتمه پيدا ميکند. و علاوه بر اين قانوني44 است (يعني اگر راه حلي را اعلام کند يا اعلام کند که راه حلي وجود ندارد، اين درست است) اما کامل نيست (يعني ممکن است راه حلي وجود داشته باشد اما پيدا نکند). شکل زير 4 حالت مختلف از مسأله کلاسيک رنگ آميزي گراف را نشان ميدهد. نتيجه پياده سازي الگوريتم تصفيه براي هر يک از اين مسائل به شرح زير است:

شکل 2-2 چهار حالت مختلف از مسأله کلاسيک رنگ آميزي گراف و نتيجه پياده سازي الگوريتم تصفيه براي هر يک از اين مسائل[4]

(a در ابتدا متغير x1 دامنه اش را به همسايگانش يعني x2 و x3 ، با ارسال يک پيام، اطلاع ميدهد. با دريافت پيام x2 و x3 مقدار red را از داخل دامنه اشان حذف ميکنند. سپس x2 دامنه جديدش را به x3 ارسال ميکند. متعاقبا x3 مقدار blue را از دامنه اش حذف ميکند. در اين مرحله الگوريتم به دليل عدم وقوع هيچ حذفي خاتمه مييابد در حاليکه يک راه حل صحيح يافته شده است.
(b الگوريتم به صورت مرحله قبل شروع ميشود. اما زمانيکه x2 دامنه جديدش را به x3 ارسال ميکند، دامنه x3 خالي ميشود. در اين مرحله الگوريتم پايان مييابد در حاليکه به صورت صحيح اعلام ميکند که مسأله هيچ راه حلي ندارد.
(c در اين مورد ارسال پيام اوليه موجب هيچ حذفي در دامنه ها نميشود. الگوريت
م خاتمه مييابد در حاليکه همه متغيرها چند مقداره هستند. و همچنين الگوريتم نيز قادر نخواهد بود نشان دهد که مسأله راه حل ندارد.
(d در اين حالت نيز الگوريتم تصفيه با شکست مواجه ميشود در حاليکه مسأله راه حل دارد. بنا به همان دليلي که در حالت c اتفاق افتاد باز هم الگوريتم قادر نخواهد بود نشان دهد که راه حلي وجود دارد.
به طور کلي الگوريتم تصفيه يک روش ضعيف است و بهتر است به عنوان يک مرحله پردازش براي متدهاي پيچيده استفاده شود. اين الگوريتم بر اساس قانون استدلال واحد45 سازماندهي شده است. قانون استدلال واحد به صورت زير است( Ai عبارتي مانند x1=1 است و همانطور که ميدانيم علامت ¬ در يک فرمول جبري به معني نقيض و علامت ? به معني “و” بکار برده ميشود.):

استدلال واحد يک قانون استنباط ضعيف است. بنابراين عجيب نيست که الگوريتم تصفيه نيز ضعيف باشد.
الگوريتم فرا استدلال
در اين الگوريتم همه محدوديتها در قالب” گزارهء نادرست”46 نمايش داده ميشوند که ترکيب ممنوعي از مقادير متغيرهاست. با استفاده از گزارههاي نادرست موجود قانون فرا استدلال، گزارهء نادرست جديد را توليد ميکند. قانون فرا استدلال، گزارههاي نادرست قبلي و شرطي را که نشاندهنده مقدارگيري متغير از دامنهاش است با هم ترکيب مي کند و گزارهء نادرست جديد را ميسازد. اين قانون به شکل زير تعريف ميشود:

در اين الگوريتم هر عامل محدوديتهايش را در قالب گزارهء نادرست بيان ميكند. سپس عامل با تركيب اطلاعات دامنه خود و گزارههاي نادرست فعلي توسط قانون فرا استدلال، گزارههاي نادرست جديد را توليد کرده و به عاملهاي مرتبط اطلاع ميدهد. با دريافت گزارهء نادرست جديد، عامل تلاش ميكند گزارههاي نادرست بيشتري توليد كند. به عبارتي در اين الگوريتم هر عامل به صورت مکرر محدوديتهاي جديدي را براي همسايگانش توليد ميکند و اين محدوديتهاي جديد را به همسايگانش اطلاع ميدهد و همچنين دامنه خودش را بر اساس محدويتهاي پاس شده از گراف همسايگانش هرس ميکند. پس از دريافت يک تعداد متناهي پيام، هر عامل ارسال پيام را متوقف خواهد کرد و گزارهءهاي نادرست را توليد ميکند. اين روش کامل است يعني اگر راه حلي وجود داشته باشد حتما آن را پيدا خواهد کرد. مسأله راه حل خواهد داشت اگر در پايان هيچ عاملي گزارهء نادرست تهي توليد نکند. در واقع الگوريتم فرا استدلال مبتني بر استخراج دانش است، هر عامل سعي ميکند تمام مسأله را حل کند و دانشي را که استخراج ميکند با بقيه به اشتراک ميگذارد. در اين روش هر عامل عاملهاي ديگر را نيز در نظر ميگيرد. در حالي که روش تصفيه مبتني بر شکستن مسأله است و هر عامل تنها خودش را ميبيند. روند کار اين الگوريتم بر روي نمونه مثال c که در روش تصفيه ذکر شد به صورت زير است:

الگوريتم فرا استدلال براي اين مورد به اين صورت عمل ميکند: در ابتدا x1 ، چهار گزارهء نادرست را به صورت زير نگه ميدارد:
(x1=red , x2=red)
(x1=red , x3=red)
(x1=blue , x2=blue)
(x1=blue , x3=blue)

که اين گزارهءهاي نادرست به طور مستقيم از محدوديتهاي شامل x1 استخراج ميشوند. علاوه بر اين x1 بايد يکي از مقادير درون دامنه اش را اختيار کند. بنابراين با استفاده از قانون فرا استدلال، x1 ميتواند به صورت زير نتيجه گيري کند:

بنابراين x1 يک گزارهء نادرست جديد به صورت (x2=red , x3=blue) ميسازد. به طور مشابه x1، گزارهء نادرست ديگري هم به اين فرم ميسازد: (x2=blue , x3=red) .سپس x1 هر دو اين گزارهءهاي نادرست را به همسايگانش يعني x2 و x3 ارسال ميکند. x2 با استفاده از دامنه اش، و همچنين يکي از گزارهءهاي نادرست موجود و يکي از گزارهءهاي نادرست جديد به استنباط زير ميرسد:

اولين گزارهء نادرست بر اساس استنباط مرحله قبل و دومين گزارهء نادرست را x2 بر اساس اطلاعات مربوط به دامنه خودش ميسازد. با استفاده از گزارهءهاي نادرست هاي جديد از x1 و x2، ميتوان گزارهءهاي نادرستي به صورت (x3=red) را ساخت. اين دو گزارهءهاي نادرست تکي بهx3 ارسال ميشوند و باعث ميشوند x3 يک گزارهء نادرست تهي توليد کند و اين اثبات ميکند که مسأله هيچ راه حلي ندارد. اين مثال اثبات ميکند که الگوريتم فرا استدلال نسبت به روش تصفيه قويتر است. علاوه بر اين همين مثال ضعفهاي الگوريتم فرااستدلال را نيز نمايان ميسازد. تعداد گزارهءهاي نادرست هاي توليد شده ميتواند به صورت غيرقابل مديريت رشد کند. يا به عبارتي اين الگوريتم پيچيدگي محاسباتي بالايي دارد و زماني که تعداد عاملها زياد باشد الگوريتم با شکست مواجه ميشود چون بايد تضمين شود که تمام واقعيتها47 استخراج ميشود. تا به اينجا به اين نتيجه رسيديم که هيچکدام از اين دو نوع استدلال پاسخگوي مسائل دنياي واقعي نيستند پس به همين دليل به سراغ الگوريتمهاي اکتشافي ميرويم.
الگوريتمهاي اکتشافي48
همانطور که پيشتر گفته شد روشهاي جستجوي عمومي قادرند با پاسخ دادن به سوالاتي از قبيل اينکه: متغير بعدي که قراگرهت مقدار بگيرد کدام است؟ و يا مثلا مقداردهي متغير جاري چه پيامدهايي براي ساير متغيرهاي انتساب نيافته دارد؟، توابع اکتشافي مناسبي را جهت افزايش کارايي الگوريتمهاي حل مسائل CSP پيشنهاد دهند. الگوريتم عقبگرد نامتقارن و الگوريتم الزام ضعيف نامتقارن دو نمونه از الگوريتمهاي کلاسيک اين دسته است که درآن عاملها در يک فرم توزيع شده به صورت موازي و غيرهمزمان به حل مساله ميپردازند. در ادامه توصيفي از نحوه عملکرد اين دو الگوريتم را خواهيم داشت.
الگوريتم عقبگرد نامتقارن
اين الگوريتم در ابتدا يک ترتيب کلي براي عاملها فرض ميکند يا به عبارتي عاملها اولويتبندي ميشوند. هر محدوديت باينري49 توسط دو عامل شناخته ميشود و در الگوريتم توسط عامل با اولويت پايينتر بين دو عامل چک ميشود. در گراف محدوديت هميشه يک لينک از عامل با اولويت بالاتر به يک عامل با اولويت پايينتر وجود دارد. عاملها متغيرهايشان را مقداردهي ميکنند (در ابتدا با يک مقدار تصادفي) و مقدار انتسابياشان را براي عاملهايي که به آنها متصل هستند به صورت همزمان ميفرستند. همه عاملها صبر ميکنند تا تمامي پيغامها ارسال شود سپس به پيغامها پاسخ ميدهند. حال هر عامل يک مقدار انتساب از عامل يا عاملهاي با اولويت بالاتر دريافت کرده است که اينها در مکاني به نام “ديدگاه عامل50” ذخيره ميکند. سپس بررسي براي رسيدن به يک راه حل آغاز ميشود. به طور کلي سه حالت ممکن است اتفاق بيفتد:
حالت اول: اينکه مقادير دريافتي از همسايه هاي با اولويت بالاتر يک عامل، با مقدار فعلي آن عامل سازگار است. که در اين صورت لازم نيست آن عامل کاري انجام دهد.
حالت دوم: اينکه مقادير دريافتي از همسايه هاي با اولويت بالاتر يک عامل، با مقدار فعلي آن عامل سازگار نيست اما آن عامل ميتواند مقدار ديگري را از دامنه اش انتخاب کند که با ديدگاه51 فعلياش سازگار باشد. در اين صورت آن مقدار جديد را انتخاب ميکند و اين مقدار را به همراه کل ديدگاهش يا به عبارتي کل دانشي را که تا الان کسب کرده به همسايگان با اولويت پايينترش اطلاع ميدهد.
حالت سوم: اينکه مقادير دريافتي از همسايه هاي با اولويت بالاتر يک عامل، با مقدار فعلي آن عامل سازگار نيست و آن عامل هم نميتواند مقدار ديگري را از دامنهاش انتخاب کند که با ديدگاه فعلياش سازگار باشد. در اين صورت عامل جاري مقدار فعلياش را حفظ ميکند و بازميگردد به عامل قبلي با پيغامي مبني بر اينکه امکان تغيير مقدار انتساب برايش وجود ندارد که اين کار با ارسال يک پيام گزارهء نادرست انجام ميشود. عامل قبلي در واقع عاملي با پايينترين اولويت در ليست ديدگاه عامل جاري است. حال عامل جاري فرض ميکند که آن عامل همسايه که پيغام گزارهءهاي نادرست را دريافت کرده مقدارش را تغيير خواهد داد پس مقدار آن عامل را از ديدگاهش حذف ميکند و تلاش براي يافتن يک مقدار جديد توسط عامل همسايه از سر گرفته ميشود و اين روند تا رسيدن به يک راه حل ادامه پيدا ميکند.
در ادامه مثالي ساده از پياده سازي اين الگوريتم را بر روي مسأله کلاسيک 4وزير را داريم:
در سيکل 1 هر عامل يک مقدار ميگيرد و مقدارش را به عاملهاي با اولويت پايينتر اعلام ميکند.

شکل 2-3 سيکل 1 الگوريتم ABT بر روي مسأله 4 وزير. تمامي عاملها فعالند[4] .

شکل 2-4 سيکل 2 از الگوريتم ABT بر روي مسأله 4وزير. عاملهاي A2 ، A3 و A4 فعالند. گزارهء نادرست در اين مرحله عبارت است از [4]:
A2 =1 ? A3?1 A1=1 ? .
در سيکل 2 هر عامل سعي ميکند مقداري را بيابد که با مقدار ديدگاهش سازگار باشد. عاملهاي A2 و A3 موفق ميشوند مقدار سازگار با ديدگاهشان را بيابند اما A4 قادر به پيدا کردن يک مقدار مناسب نيست پس يک پيغام گزارهء نادرست به صورت: A2 =1 ? A3?1 ? A1=1 به عامل A3 ارسال ميکند. البته اين در حالي است که ديدگاه عامل A4 هنوز ب


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