No category

پایان نامه ارشد با موضوع الگوریتم ژنتیک، کشاورزی و منابع طبیعی، الگوریتم های فراابتکاری، منابع طبیعی

دسامبر 1, 2018

فوتبال
۱۵۰
۱۵۰
۱۵۰
۱۵۰
۱۵۰
۱۵۰
۲۰
۲۰
۲۰
۲۰
۲۰
۲۰
۵۰
۸۰
۸۰
۰
۱۵۰
۵۰
۵۰
۴۰۰
۴۰۰
۰
۲۰
۲۰
مسجد
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۵۰
۲۰
۲۰
۰
۵۰
۵۰
۵۰
۶۰
۶۰
۶۰
۰
۳۰۰
مقبره شهدا
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۱۳۰
۵۰
۲۰
۲۰
۰
۵۰
۵۰
۵۰
۶۰
۶۰
۶۰
۳۰۰
۰
۴-۵ حل مسئله QAP با استفاده از الگوریتم ژنتیک
برای حل مسئله دو الگوریتم ارائه می شود. تفاوت الگوریتم ها در استراتژی انتخاب بین آن هاست. در اولین الگوریتم پس از تولید فرزندان جدید، آن ها بدون هیچ گونه برازشی به جمعیت اضافه می شوند. در ادامه دو والد از میان جمعیت اضافه می شود. معیار انتخاب نیز میزان برازندگی هر عضو از جمعیت است. در ابتدا n والد به صورت تصادفی انتخاب می شود. n یک پارامتر کنترلی است و می توان در ابتدای الگوریتم آن را تعیین کرد. در ادامه یک عدد تصادفی بین صفر و یک به هر عضو اختصاص داده می شود. دو عضو با بیشترین مقدار عدد تصادفی به عنوان والد انتخاب می شوند.
این استراتژی انتخاب، مشابه استراتژی انتخاب مسابقه۱۲ در الگوریتم ژنتیک است. پس از هر تولید مثل فرزندان به جمعیت اضافه می شوند و رویه تکرار می شود. شرط توقف در این الگوریتم تعداد جمعیت است. قدم های این الگوریتم را می توان به شرح زیر تشریح کرد.
گام ۱: n عضو را با بهترین مقدار برازندگی از جمعیت اولیه انتخاب کنید.
گام ۲: دو والد از میان n عضو انتخاب شده به تصادف انتخاب کنید.
گام ۳: عملگر تقاطع را به دو والد اعمال کنید و فرزند جدید را به جمعیت اولیه اضافه کنید.
گام ۴: یکی از دو والد را به تصادف انتخاب کنید و عملگر جهش را به آن اعمال کنید. فرزند جدید را به جمعیت اولیه اضافه کنید.
گام ۵: اگر شرط توقف برآورده شده است توقف کنید و در غیر این صورت به گام ۱ بروید.
الگوریتم دوم مشابه الگوریتم اول است با این تفاوت که در آن پس از هر تولید مثل فرزندان با اعضایی که در گام قبل به برای انتخاب والد، انتخاب شده اند مقایسه می شوند. اگر فرزند برازندگی بهتری نسبت به یکی از اعضای انتخابی مرحله قبل داشت، جایگزین آن می شود و در غیر این صورت فرزند جدید حذف می شود. در واقع استراتژی به کار رفته در این الگوریتم، ترکیبی از استراتژی مسابقه و حالت پیوسته۱۳ است. رویه الگوریتم دوم به شرح زیر است:
گام ۱: n عضو را با بهترین مقدار برازندگی از جمعیت اولیه انتخاب کنید.
گام ۲: دو والد از میان n عضو انتخاب شده به تصادف انتخاب کنید.
گام ۳: عملگر تقاطع را به دو والد اعمال کنید و فرزند جدید را ایجاد کنید.
گام ۴: فرزند جدید را با بدترین عضو در مجموعه انتخاب شده (n عضو) مقایسه کنید. اگر بهتر بود با آن جایگزین کنید و در غیر این صورت فرزند را حذف کنید.
گام ۵: یکی از دو والد را به تصادف انتخاب کنید و عملگر جهش را به آن اعمال کنید. فرزند جدید را ایجاد کنید.
گام ۶: فرزند جدید را با بدترین عضو در مجموعه انتخاب شده (n عضو) مقایسه کنید. اگر بهتر بود با آن جایگزین کنید و در غیر این صورت فرزند را حذف کنید.
گام ۷: اگر شرط توقف برآورده شده است توقف کنید و در غیر این صورت به گام ۲ بروید.
یکی از مزایای الگوریتم دوم آن است که عمل انتخاب n عضو با بهترین برازندگی را تنها یکبار در ابتدا انجام می دهد و در ادامه تنها از همین مجموعه و فرزندان متولد شده استفاده می کند. در حالیکه الگوریتم اول در هر تکرار دست به انتخاب n عضو می زد. همین امر سبب زمان بر بودن این الگوریتم می شد.
فلوچارت های دو الگوریتم ذکر شده در شکلهای (۴-۲) و (۴-۳) ارائه شده است.
شکل ۴-۲ فلوچارت الگوریتم اول
شکل ۴-۳ فلوچارت الگوریتم دوم
الگوریتم اول الگوریتمی زمانبر و غیر همگراست که نسبت به الگوریتم دوم جوابهای بهتری نمی دهد. فرض اساسی در این الگوریتم، بررسی جواب ها در هر مرحله، انتخاب بهترین والدها، تولید مثل و پس از رسیدن به تعداد مشخصی جمعیت انتخاب بهترین جواب است. در این حالت پس از پایان الگوریتم تعداد اعضای استخر جمعیت به اندازه متغیر run است. همین امر سبب می شود که با افزایش اندازه متغیر run زمان اجرای الگوریتم به صورت نمایی افزایش یابد. زیرا در هر بار تکرار، دو فرزند متولد شده به استخر جمعیت اضافه می شود و الگوریتم باید مجددا به منظور انتخاب والد دست به برازش استخر جمعیت بزند (استراتژی بد یا نامناسب).
الگوریتم دوم الگوریتمی همگرا (مزیت مهم) با زمان بسیار کمتر نسبت به الگوریتم اول است که جوابهای بهتری نسبت به الگوریتم اول در بر دارد. استراتژی به کار رفته در این الگوریتم بر پایه مقایسه فرزندان تولیدی با بدترین کروموزومهای انتخاب شده به عنوان والد، و سپس تصمیم گیری در مورد حذف فرزندان یا بدترین کروموزوم های والد انتخابی با توجه به مقادیر تابع هزینه است. بنابراین در این روش درهر بار تکرار اقدام به حذف کروموزوم های بدتر کرده و در نتیجه در طول الگوریتم تعداد کروموزوم های استخر جمعیت افزایش نمی یابد.
البته الگوریتم به تعداد متغیر run جواب ایجاد می کند اما چون با تولید هر استقرار (کروموزوم) یک استقرار نیز حذف می شود تعداد استقرارها ثابت می ماند (استراتژی خوب یا مناسب).
روند حرکت هر دو الگوریتم برای رسیدن به جواب بهینه در شکل های ۴-۴ و ۴-۵ برای یک مسئله طی ۵۰۰ تکرار مقایسه شده است.
شکل ۴-۴ عدم همگرایی الگوریتم اول (استراتژی بد)
شکل ۴-۵ همگرایی الگوریتم دوم (استراتژی خوب)
برای درک بهتر، کد متلب هر دو الگوریتم به صورت خط به خط در پیوست مورد تحلیل قرار می‌گیرد. با این شیوه عملگرهای انتخاب شده به صورت موثرتری قابل فراگیری خواهند بود.
۵۴
۴-۶ نتایج حاصل از حل مسئله با استفاده از الگوریتم ژنتیک
۵۵ ۴-۶-۱ نتایج حاصل از الگوریتم اول
همان طور که می دانیم الگوریتم های فراابتکاری توازنی میان کیفیت و زمان برقرار می کنند. بدین معنی که کیفیت جواب بهتر مستلزم صرف زمان بیشتر توسط الگوریتم برای جستجوی فضای حل است.
لازم به ذکر است که نقطه برش۱۴ برای عملگر تقاطع ژن ۱۲ است و تعداد ژن جهش یافته در هر مرحله نیز برابر با ۷ است. همچنین تعداد جواب اولیه در نظر گرفته شده در استخر جمعیت برابر با ۵ و تعداد کروموزوم برگزیده در هر مرحله انتخاب برابر با ۱۰ است. همان طور که در شرح الگوریتم گفته شده موارد بالا جزء پارامترهای کنترلی الگوریتم است که به طور مستقیم بر کیفیت جواب نهایی اثر گذار است.
بنابراین با استفاده از روش های طراحی آزمایش (DOE) می توان به تنظیم۱۵ کردن پارامترهای کنترلی الگوریتم پرداخت. بدین معنی که مشخص کرد چه سطحی از این پارامترها منجر به بهترین جواب برای الگوریتم می شود.
نتایج الگوریتم برای ۱۰۰۰ تکرار به شرح زیر است.
جدول ۴-۳ نتایج حاصل از ۱۰۰۰ بار تکرار الگوریتم
شماره مکان
۱
۲
۳
۴
۵
۶
۷
۸
۹
۱۰
۱۱
۱۲
۱۳
۱۴
۱۵
۱۶
۱۷
۱۸
۱۹
۲۰
۲۱
۲۲
۲۳
۲۴
شماره تسهیل
۳
۱۰
۱۹
۱۲
۱۸
۹
۱۱
۲۴
۷
۱
۸
۲۳
۱۶
۱۷
۲
۱۳
۱۴
۲۲
۱۵
۲۱
۲۰
۴
۶
۵
هزینه (کل جابه جایی به متر)
۱۱۵۴۶۵۵۰
زمان (ثانیه)
۱۶.۶۶
شکل ۴-۶ روند حرکت بهترین جواب هر تولید مثل الگوریتم (برای ۱۰۰۰ بار تکرار)
قبل از آنکه نتایج حاصل از الگوریتم برای سایر تکرارها شرح داده شود، نخست لازم است تا جواب به دست آمده از ۱۰۰۰ بار تکرار بر روی نقشه شرح داده شود. مکان های ساختمان موجود به شرح زیر در نقشه نام گذاری شده است.
شکل ۴-۷ نقشه ۱۰۰۰ بار تکرار
جواب به دست آمده از ۱۰۰۰ بار تکرار الگوریتم اول به صورت زیر است.
۳
۱۰
۱۹
۱۲
۱۸
۹
۱۱
۲۴
۷
۱
۸
۲۳
۱۶
۱۷
۲
۱۳
۱۴
۲۲
۱۵
۲۱
۲۰
۴
۶
۵
این جواب نشان می دهد که ساختمان شماره ۳ (دانشکده کشاورزی و منابع طبیعی) در مکان ۱، ساختمان شماره ۱۰ (اداری امور فرهنگی) در مکان ۲، ساختمان شماره ۹ (سایت) به مکان ۳ و به همین ترتیب ساختمان شماره ۵ (دانشکده علوم پایه) به مکان شماره ۲۴ منتقل گردد. چنین استقراری هزینه ای معادل۱۱۵۴۶۵۵۰ به همراه دارد. زمان به دست آمده برای این استقرار توسط برابر با ۱۶.۶۶ ثانیه است۱۶.
در ادامه نتایج الگوریتم با تکرارهای ۲۰۰۰، ۳۰۰۰، ۴۰۰۰، ۵۰۰۰ و ۱۰۰۰۰ ارائه می گردد.
جدول ۴-۴ نتایج حاصل از ۲۰۰۰ بار تکرار الگوریتم
شماره مکان
۱
۲
۳
۴
۵
۶
۷
۸
۹
۱۰
۱۱
۱۲
۱۳
۱۴
۱۵
۱۶
۱۷
۱۸
۱۹
۲۰
۲۱
۲۲
۲۳
۲۴
شماره تسهیل
۱۴
۲
۱۵
۱۹
۱۸
۱۰
۱
۹
۸
۳
۲۴
۲۳
۴
۶
۲۰
۲۲
۱۶
۱۲
۱۷
۱۳
۲۱
۵
۷
۱۱
هزینه (کل جابه جایی به متر)
۱۱۰۶۰۹۰۰
زمان (ثانیه)
۵۳.۴۶
شکل ۴-۸ روند حرکت بهترین جواب هر تولید مثل الگوریتم (برای ۲۰۰۰ بار تکرار)
جدول ۴-۵ نتایج حاصل از ۳۰۰۰ بار تکرار الگوریتم
شماره مکان
۱
۲
۳
۴
۵
۶
۷
۸
۹
۱۰
۱۱
۱۲
۱۳
۱۴
۱۵
۱۶
۱۷
۱۸
۱۹
۲۰
۲۱
۲۲
۲۳
۲۴
شماره تسهیل
۱۹
۱۵
۱۸
۱۶
۱۴
۷
۲۳
۱
۲۴
۹
۱۲
۴
۶
۱۳
۱۱
۳
۲۰
۲
۵
۱۷
۲۱
۲۲
۸
۱۹
هزینه (کل جابه جایی به متر)
۱۰۴۸۹۷۰۰
زمان (ثانیه)
۱۰۹.۲۴
شکل ۴-۹ روند حرکت بهترین جواب هر تولید مثل الگوریتم (برای ۳۰۰۰ بار تکرار)
جدول ۴-۶ نتایج حاصل از ۴۰۰۰ بار تکرار الگوریتم
شماره مکان
۱
۲
۳
۴
۵
۶
۷
۸
۹
۱۰
۱۱
۱۲
۱۳
۱۴
۱۵
۱۶
۱۷
۱۸
۱۹
۲۰
۲۱
۲۲
۲۳
۲۴
شماره تسهیل
۱۴
۱۵
۳
۱۸
۱۹
۱۰
۹
۲۴
۱۲
۲۳
۷
۸
۱۶
۱۷
۱۳
۶
۱
۲
۵
۴
۲۱
۲۰
۱۱
۲۲
هزینه (کل جابه جایی به متر)
۱۰۳۶۵۸۲۵
زمان (ثانیه)
۲۱۰.۰۳
شکل ۴-۱۰ روند حرکت بهترین جواب هر تولید مثل الگوریتم (برای ۴۰۰۰ بار تکرار)
جدول ۴-۷ نتایج حاصل از ۵۰۰۰ بار تکرار الگوریتم
شماره مکان
۱
۲
۳
۴
۵
۶
۷
۸
۹
۱۰
۱۱
۱۲
۱۳
۱۴
۱۵
۱۶
۱۷
۱۸
۱۹
۲۰
۲۱
۲۲
۲۳
۲۴
شماره تسهیل
۳
۱۵
۱۰
۱۴
۱۹
۱۸
۲۳
۱
۹
۷
۸
۲۴
۲۰
۱۳
۱۷
۶
۱۲
۲
۱۶
۴
۲۱
۵
۱۱
۲۲
هزینه (کل جابه جایی به متر)
۱۰۲۲۹۲۷۵
زمان (ثانیه)
۳۱۵.۳۵
شکل ۴-۱۱ روند حرکت بهترین جواب هر تولید مثل الگوریتم (برای ۵۰۰۰ بار تکرار)
در نهایت نتیجه حاصل از ۱۰۰۰۰ تکرار الگوریتم به شرح زیر به دست می آید.
جدول ۴-۸ نتایج حاصل از ۱۰۰۰۰ بار تکرار الگوریتم
شماره مکان
۱
۲
۳
۴
۵
۶
۷
۸
۹
۱۰
۱۱
۱۲
۱۳
۱۴
۱۵
۱۶
۱۷
۱۸
۱۹
۲۰
۲۱
۲۲
۲۳
۲۴
شماره

No Comments

Leave a Reply