۱۶
۷۵
همانطور که در جدول (۳-۲) مشاهده می شود ستون های سمت چپ اندازه متفاوت مسائلی را نشان می دهند که در آزمایشات استفاده شده است. اندازه مسأله تعداد گرهها در گراف محدودیت را نشان میدهد. اولین ردیف این جدول نسبت تعداد یال ها به تعداد گره در هر مسأله را نشان میدهد. مقادیر متفاوت (۲، ۲٫۳ و ۲٫۷) که برای این نسبت انتخاب شده اند مسائل متفاوتی را با درجات متفاوتی از دشواری نشان می دهند. این مقادیر مخصوص به صورتی انتخاب شده اند که سه ناحیه مهم در مرحله انتقالی را ارائه میدادند [۵۱]. سختترین مسأله آنهایی بودند که دقیقا در فاز انتقال هستند و تراکم آنها برابر ۲٫۳ است. به عنوان مثال، مسأله ای با اندازه ۳۰ و تراکم ۲٫۳ گرافی را با ۳۰ گره و ۶۹ =۲۰*۲٫۳ یال ارائه میدهد. همه یالها به طور تصادفی بین یالهای گراف ایجاد شده اند. در آزمایشاتی که در این تحقیق انجام شدند تعداد مورچه ها با بزرگتر شدن و سخت تر شدن حل مسأله افزایش مییابد. در ساده ترین مسأله با ۱۵ گره و ۳۰ یال، که الگوریتم از دو مورچه استفاده می کند، الگوریتم می تواند خیلی سریع راه حلی پیدا کند، همانطور که دشواری افزایش مییابد: نهایتا سختترین مسأله با ۷۵ گره و ۱۷۲ یال به ۱۸ عدد مورچه برای جست و جوی فضای مسأله برای یافتن راه حلی در طول زمانی مناسب نیاز دارد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
نتایج تجربی
در این بخش الگوریتم مبتنی بر کلونی مورچه ها را که در این مقاله ارائه شده است با دو الگوریتم تحقیقی دیگر DCSP یعنی الگوریتم عقبگرد آسنکرون و الگوریتم انفجاری توزیع شده مقایسه شده است. هر دو الگوریتم های به روز هستند و در بسیاری از مقالات به عنوان الگوریتم های مرجع در مقایسه با سایر الگوریتم ها بکار میروند. ABT یک الگوریتم کامل است. اما DBA الگوریتمی ناقص است که اگر هیچ راه حلی برای یک مسأله وجود نداشته باشد خاتمه یافتن را ضمانت نمیکند.
دو متریک در این مقاله انتخاب شده که یکی برای ارزیابی پیچیدگی محاسباتی الگوریتم پیشنهادی و دیگری برای ارزیابی پیچیدگی ارتباطاتی آن: “تعداد پیام ها” و “تعداد وارسی های ناموافق محدودیت “.
همانطور که در ساختارهای آزمایشی قبل که در مقالات پیشین در مورد DCSP چاپ شده اند معمول است، در این مقاله نیز آزمایشات بر روی رنگ آمیزی گراف توزیع شده با سه رنگ انجام شده است. این مورد آزمایش پیش از ارزیابی ABT و DBA استفاده شد. هر گره از گراف در مسأله رنگ آمیزی گراف به یک عامل DCSP تخصیص داده شده است، و هم چنین به یک گره در محیط توزیع شده تخصیص داده شده است. الگوریتم با حرکت مورچه ها در این گراف توزیع شده پیش میرود که به وسیله ارسال و دریافت پیام پیاده سازی شده است. هزینه هر نقض محدودیت ۱ محسوب می شود بنابراین هزینه یک راه حل با تعداد محدودیتهای نقض شده اندازه گیری می شود.
شکل های ۳-۸ تا ۳-۱۳ نتیجه آزمایشهای تجربی این الگوریتم پیشنهادی را بر روی مسأله رنگ آمیزی گراف با گره ها و تراکم متنوع را نشان می دهند. این شکل ها سه الگوریتم را بر اساس دو مقیاس مهم ارزیابی می کند: NCCC ها و تعداد پیام ها. به علت زمانبر بودن حل هر تست برای الگوریتم ABT، نتایج ABT را برای مسائلی با ۶۰ و ۷۵ گره در این آزمایشات به دست نیامده است.
شکل ۳-۸ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲ ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها
شکل ۳-۹ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲ ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC
شکل ۳-۱۰ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .۳۲ ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها
شکل ۳-۱۱ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲٫۳ ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC
شکل ۳-۱۲ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .۷۲ ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها
شکل ۳-۱۳ مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم ۲٫۷ ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC
اگرچه هر دو الگوریتم مورچه ها و DBA الگوریتم های ناقص هستند، اما آنها میتوانند مسائلی را که به طور تصادفی ایجاد شده اند در بازه زمانی معقولی حل کنند. در هیچ یک از موارد الگوریتم مورچه ها، تعداد چرخه ها از ماکسیمم از پیش تعیین شده فراتر نرفت. همانطور که در این شکل ها دیده می شود الگوریتم مورچه ها از دو الگوریتم دیگر در همه تراکمها نسبت به تعداد پیام ها بهتر عمل کرده است. برای این پارامتر الگوریتم مورچه ها بسیار بهتر از ABT عمل میکند و هم چنین به وضوح از DBA به عنوان الگوریتم ناقص بهتر عمل می کند. البته از آنجا که در DBA در هر زمان همه عامل ها ماکسیمم مقدار ممکن پیشرفت را علاوه بر برخی از اطلاعات دیگر به همه همسایگانشان میفرستند که این خود موجب تولید تعداد زیادی پیام می شود، در این تحقیق انتظار میرفت که الگوریتم مورچه ها نتایج بهتری برای این پارامتر نسبت به DBA داشته باشد.
هم چنین به وضوح الگوریتم مورچه ها از ABTنسبت به NCCC بهتر عمل می کند اما DBA تقریبا بهتر از الگوریتم مورچه ها در این پارامتر عمل می کند. اگرچه تعداد چرخه های کلونی مورد نیاز برای حل مثال های بزرگتر و پیچیدهتر مسائل رنگ آمیزی گراف زیاد نیستند، اما افزایش تعداد مورچه ها یی که در حل مسائل بزرگتر شرکت دارند پارامتر NCCC را ترفیع میدهد. به خاطر اینکه داشتن تعداد بیشتر مورچه ها، تعداد وارسیهای محدودیت انجام شده عامل در هر چرخه الگوریتم کلونی مورچگان را افزایش میدهد.
برای مقایسه DBA و الگوریتم مورچه های پیشنهادی جدید، میتوانیم بگوییم که الگوریتم مورچهها قطعا انتخاب بسیار خوبی در مسائلی است که هزینه ارتباط، عامل مهمیاست. این در حالی است که DBA هزینه محاسباتی خیلی بهتری در مسائلی با موضوعات محاسباتی فراهم نمیکنند. بنابراین الگوریتم مورچه ها جایگزین مناسبی برای DBA در بسیاری از مسائل است.
نکته مهم دیگر این است که افزایش تعداد مورچه ها به الگوریتم مورچه ها کمک می کند تا نتایج بهتری در مسائل بزرگتر و پیچیده تر علاوه بر مسائل کوچکتر و آسان تر داشته باشد. این پارامتر که می تواند بر اساس شرایط مسأله وفق داده شود انعطاف پذیری حل مسأله را افزایش میدهد. در نتیجه اگر ما مسأله ای داشته باشیم که در آن داشتن هزینه محاسباتی پایین بسیار مهم است ما میتوانیم به آسانی تعداد مورچه هایی را که در حل مسأله هستند را کاهش دهیم و سپس پارامتر NCCC به میزان زیادی کاهش مییابد. این حقیقت انعطاف پذیری الگوریتم مورچه ها را افزایش میدهد و می تواند به عنوان دیگر مزیت الگوریتم مورچه ها نسبت به الگوریتم های موجود دیگر محسوب شود. در این نسخه جدید سعی شده است تا از تکنیکهایی استفاده شود که آسنکرونی پروسه حل مسأله هم چنین امنیت افزایش یابد و تعداد پیام های مبادله شده را کاهش پیدا کند. نتایج نشان دادند که الگوریتم مورچه ها از ABT در تمام موارد شامل مسائلی با تعداد متفاوت گرهها و یال ها بهتر عمل می کند. اگرچه نیازمند تعداد کمی بیشتری NCCC نسبت به DBA است اما این مقدار می تواند با کاهش تعداد مورچه ها در مسائلی که هزینه محاسباتی کمی دارد، کاهش یابد.
فصل چهارم
روش جدید ارائه شده
همانطور که گفته شد بسیاری از مسائل اعم از مسائل کلاسیکی همانند مسأله چند وزیر و رنگ آمیزی گراف گرفته و تا مسائل کاربردی بزرگ دنیای واقعی همچون زمانبندی و برنامه ریزی و تخصیص منابع میتوانند برای حل شدن به عنوان یک مسأله DCSP فرموله شوند. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. بنابراین ارائه یک شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد می گذارد .در این فصل تکنیک جدید ارائه شده را به همراه جزئیاتی از اینکه چگونه این شیوه جدید پیشنهادی ما می تواند یک مسأله DCSP را حل کند توضیح میدهیم. ایده اصلی مطرح در این تکنیک، بر پایه تقسیم بندی مسائل DCSP در گروه های مختلف و ارائه الگوریتمهایی خاص برای هر گروه استوار است. روش پیشنهادی ما، تلفیقی از روش های توزیع شده و متمرکز است که برای حل دسته ای خاص و پر کاربرد از مسائل DCSP ها طراحی و پیاده سازی شده است. ارائه الگوریتمی خاص منظوره که قطعا کارآیی بیشتری نسبت به الگوریتمهای همه منظوره دارد، تقسیم عاملها به دو گروه مختلف کاری و همچنین تشکیل اجتماعاتی بین عاملها بر مبنای یک ویژگی خاص، خصوصیاتی است که روش پیشنهادی ما را از دیگر روش های موجود متمایز کرده است. این دو ویژگی اخیر یعنی طبقه بندی کردن عاملها و تشکیل ساختارهای اجتماع، با دخیل کردن درجه ای از متمرکز سازی در روند حل مسأله موجب کاهش تعداد پیامهای ارسال و دریافتی که یکی از پارامترهای مهم در این فیلد است، شده است. علاوه بر این، استفاده از توابع اکتشافی در روند حل مسأله ویژگی دیگری است که به افزایش کارآیی این الگوریتم کمک می کند. ادامه این فصل در ۶ بخش به شرح زیر تنظیم شده است:
بخش (۴-۱) مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی، بخش (۴-۲) تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ، بخش (۴-۳) توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن، بخش (۴-۴) حل یک مثال با بهره گرفتن از این الگوریتم، بخش (۴-۵) ارزیابی و مقایسه این الگوریتم با ۳ روش دیگر، و در نهایت در بخش (۴-۶) نتیجه گیری و برشمردن مزایا و معایب این روش را خواهیم داشت.
۴-۱- مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی
توصیف مسائل ارضاء محدودیت توزیع شده[۱۲۹]؛(DCSP)
وقتی یک مسأله قرار است توسط سیستمهای چند عامله حل شود فرم مسأله به یک حالت توزیع شده تبدیل می شود. مسأله ارضاء محدودیت توزیع شده حالت توزیع شده مسأله ارضاء محدودیت کلاسیک است که پیش تر به طور کامل توصیف شد. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را حمل و کنترل می کنند. مسأله ارضاء محدودیت توزیع شده اولین بار توسط سیکارو، یوکو و همکارانشان به صورت رسمی مطرح شد [۹] و [۱۰]. به طور کلی یک مسأله ارضاء محدودیت توزیع شده شامل یک ۴تایی مرتب 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 ;
یک مجموعه از محدودیتها، { 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 بگیرد.
هدف نهایی حل مسأله ارضاء محدودیت توزیع شده، مشابه مسأله ارضاء محدودیت استاندارد که پیشتر تعریف شد، هنوز یافتن مقادیری برای انتساب به متغیرهاست که کل محدودیت های موجود را ارضاء کند. یک الگوریتم خوب در این فیلد الگوریتمی است که تضمین می کند که یک پروسه با یک راه حل قانونی و در یک مدت زمان قابل قبول خاتمه مییابد و یا نشان دهد هیچ راه حل قانونی وجود ندارد. منظور از راه حل قانونی راه حلی است که به هر متغیر یک مقدار از مقادیر دامنه اش انتساب یافته باشد به طوریکه هیچ محدویتی از محدودیتهای تعریف شده در مسأله نقض نشده باشد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب می شود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر میباشد. هر عامل سعی می کند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را میتوان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. بسیاری از مسائل مطرح در دنیای واقعی و مسائل چند عاملی را میتوان تحت این مدل در نظر گرفت، که از جمله میتوان به مواردی نظیر زمانبندی توزیع شده [۱۱]، مسائل انتساب منابع توزیع شده [۱۲] و نگهداری واقعیات یا صحت چند عاملی [۱۳]، اشاره کرد.
تعریف محدودیت Alldiff یا Alldifferent
برخی از محدودیتها آنقدر زیاد در مسائل اتفاق میافتند که میتوان آنها را به عنوان حالتهای خاص بررسی کرد.
محدودیت Alldiff : همه متغیرها بایستی مقادیر متفاوت داشته باشند. مسأله ۸-وزیر یا پازل ریاضیات رمزی از این دسته محدودیتها دارد.
به شکلی رسمیتر میتوان محدودیت Alldiff را به صورت زیر تعریف کرد[۵۶]:
با داشتن یک مجموعه از متغیرهای X={x1, x2, . . . , xn} با دامنه های D1, . . . , Dn ، مجموعه ای از چندتایی های مجاز به وسیله Alldiff(X) عبارتند از:
{ (d1, d2, . . . , dn) | di ϵ Di , di ≠ dj i ≠ j }
