روش مرتبسازی سریع برای جستجوی افراد غالب

مشکل هزینه محاسباتی روشهای MOEA  مانند NSGA-II که برای ابعاد جمعیت N و تعداد توابع مطلوبیت  mمعادل O(m) بود، با این الگوریتم حداکثر معادل O(m)  خواهد شد. ذکر این نکته الزامی است که این مزیت در مقابل افزایش فضای ذخیره از ON به O() میسر میگردد. در صورتی که برای هر فرد i دو مشخصه محاسبه شود: ni تعداد افراد غالب برi و Si مجموعه افراد مغلوب i محاسبه این دو مشخصه O(m)  مقایسه در پی خواهد داشت. افرادی که دارای=۰ هستند همان جبهه پارتو اول یا میباشند. اکنون برای هر فرد عضو   مجموعه مغلوب   را در نظر گرفته وnj مربوط به j امین عضو آن یکی کاهش داده میشود. افرادی که در آنها =۰ است به مجموعه H تعلق خواهند یافت. بعد از تکمیل H برای کلیه اعضای می توان گفت H جبهه پارتو دوم میباشد. برای ادامه کار را به کناری نهاده وH  به عنوان جبهه پارتو اول منظور و فرآیند فوق برای باقیمانده اعضاء تکرار میشود (براجعه، ۱۳۹۲).
پیش از تشریح روش انتخاب (به عنوان سومین جزء مورد نیاز برای بیان روش NSGA-II) بکارگرفته شده در این الگوریتم به توضیح مراحلی که قبل از مرحلهی انتخاب باید انجام گردد میپردازیم :

کدگذاری

الگوریتم ژنتیک به جای این که بر روی پارامتر‌ها یا متغییرهای مسئله کار کند، با شکل کد شده آن‌ها به طور مناسب سرو کار دارد.در این پژوهش از روش کدگذاری جایگشتی استفاده میشود، در این روش کروموزوم‌ها به صورت رشته‌ای از اعداد طبیعی نشان داده می‌شوند که هرکدام از این اعداد، مربوط به پارامتر ویژه‌ای در فضای حلّ مسأله است. ترتیب قرارگیری این اعداد مهم بوده و طول رشته دقیقاً با تعداد پارامترهای تعریف شده در مسأله برابر است.

ایجاد جمعیت اولیه

پس از تعیین سیستم کدینگ و مشخص شدن روش تبدیل هر جواب به کروموزوم، باید جمعیت اولیه‌ای از کروموزوم‌ها تولید نمود. در اکثر موارد، جمعیت اولیه به صورت تصادفی تولید می‌شود. اما گاهی اوقات برای بالا بردن سرعت و کیفیت الگوریتم از روش‌های ابتکاری نیز برای تولید جمعیت اولیه استفاده می‌گردد. در هر صورت عمومی‌ترین و راحت‌ترین روش، استفاده از یک رویکرد تصادفی می‌باشد. که در این پژوهش نیز همین رویکرد بکار گرفته شده است (خلیلی نیا،۱۳۹۰).

   محاسبه شاخص تراکم افراد در جمعیت

برای تعیین میزان تراکم افراد جمعیت حول یک نقطه مشخص که معیاری برای تنظیم تنوع در جمعیت به دست خواهد داد، متوسط نزدیکترین افراد در دو طرف نقطه مزبور برای کلیه توابع مطلوبیت درنظر گرفته میشود. کمیت idistance  مبین اندازه بزرگترین فرامستطیلی است که اولاً فرد i را در برمیگیرد و ثانیاً هیچ فرد دیگری را دربر نمیگیرد که به آن فاصله ازدحام می گویند (براجعه، ۱۳۹۲).
شکل ۳-۱ این مفهوم را برای دو تابع مطلوبیت نشان میدهد.
شکل ۳-۱ : فاصله ازدحام برای دو تابع مطلوبیت
تابع مطلوبیت
تابع مطلوبیت

عملگر انتخاب در NSGA-II

در NSGA-II از روش تورنمت باینری برای عملگر انتخاب استفاده میشود. این عملگر انتخاب امکان دستیابی به جبهه پارتو در نسل آخر را به صورت یکنواخت و همگون میسر میسازد.این در حالی است که حتی الگوریتم های دیگرMOEA  مانند PAES  در صورت همگرایی به جبهه پارتو، تضمین دسترسی یکنواخت به تمامی نقاط جبهه پارتو را نمیدهند. با فرض کردن دو مشخصه irank(درجه غلبه) و idistance  (فاصله ازدحام موضعی) برای هر فرد در جمعیت، می توان عملگر مقایسه ازدحام را به صورت زیر تعریف نمود:
If ((irank = jrank) and (idistance > jdistance))
or (irank < jrank) then i≥n j
در واقع هنگام مقایسه دو فرد، فردی انتخاب میشود که مربوط به جبهه پارتو بالاتر(بهتر) یا درجه غلبه کمتری داشته باشد. در صورتی که هر دو فرد مربوط به یک جبهه پارتو باشند یعنی درجه غلبه یکسان داشته باشند، فردی انتخاب میشود که مشابه کمتری داشته باشد یعنی در محیط کم تراکمتر یا با فاصله ازدحام بزرگتری قرار گرفته باشد. شرط اول باعث همگرایی جمعیت به سمت نقاط بهینه و شرط دوم باعث همگون شدن نقاط بهینه در سراسر جبهه پارتو اول میشود (براجعه، ۱۳۹۲).

ترکیب

یکی از روشهای ترکیب جابجایی دودویی[۷۸] است، روش‌های معمول جابجایی تک نقطه[۷۹]، دو نقطه[۸۰] و جابجایی یکنواخت[۸۱] می‌باشد. ساده‌ترین جابجا کردن، جابجایی تک نقطه‌ای است. در جابجایی تک نقطه‌ای، ابتدا جفت کروموزوم والد (رشته دودوئی) در نقطه مناسبی در طول رشته بریده شده و سپس قسمت‌هایی از نقطه برش، با هم عوض می‌شوند، بدین ترتیب دو کروموزوم جدید به دست می‌آید که هر نقطه از آن ژن‌هایی را از کروموزوم‌های الد به ارث می‌برند.
برای جابجایی چند نقطه‌ای[۸۲] ، m موقعیت جابجا شدن،  که  نقطه جابجایی و  طول کروموزوم می‌باشد را به صورت تصادفی و بدون تکرار انتخاب می‌کنیم، سپس جهت ایجاد فرزندی جدید بیت‌های بین نقاط مشخص شده در والدین با هم عوض می‌شوند.
که در کدینگ جایگشتی و در این پژوهش از این روش استفاده گردیده است.

جهش

در طبیعت برخی عوامل مانند تابش اشعۀ ماوراءِ بنفش باعث به وجود آمدن تغییرات غیرقابل پیش‌بینی در کروموزوم‌ها می‌شوند. از آنجایی که الگوریتم‌های ژنتیکی از قانون تکامل پیروی می‌کنند در این الگوریتم‌ها نیز عملگر جهش با احتمال کم اعمال می‌شود. جهش باعث جستجو در فضاهای دست نخورده مسأله می‌شود می‌توان استنباط کرد که مهمترین وظیفه جهش اجتناب از همگرایی به بهینه محلّی است. در جهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود یا ژنی که تا حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری، روش‌های متفاوت جهش استفاده می‌شود.
در این پژوهش به دلیل استفاده از کدینگ جایگشتی از روش تغییر ترتیب قرارگیری استفاده میشود.
۳-۴-۲- پیاده سازی الگوریتم NSGA-II
ابتدا جمعیت والد اولیه  ایجاد میگردد. جمعیت بر اساس الگوریتم مرتبسازی، مرتب سازی شده و به هر فرد درجه غلبه یا رتبه جبهه پارتو آن نسبت داده میشود. اکنون مساله بهینهسازی چندگانه به یک مساله ساده کمینهسازی تابع مطلوبیت جبهه پارتو تبدیل شده است. عملگرهای انتخاب تورنمنت باینری، لقاح و جهش برای ایجاد جمعیت فرزندان به تعداد N فرزند به کار گرفته میشوند. از این نسل به بعد روش کار به دلیل اعمال فرآیند الیتیسم متفاوت خواهد بود. فرآیند الیتیسم که در آن ابتدا یک جمعیت ترکیبی از والدین و فرزندان Rt= U Pt Qt تشکیل میشود. تعداد افراد در این جمعیت خواهد بود. سپس جمعیت ترکیبی بر اساس عملگر مقایسه ازدحام مرتبسازی شده و N فرد بهتر آن به عنوان جمعیت نسل آتی Pt+1 درنظر گرفته میشود. سپس با استفاده از جمعیت N تایی Pt+1 و با به کارگیری عملگرهای انتخاب، لقاح و جهش، جمعیت N تایی Qt+1  ساخته میشود و باید توجه  گردد که انتخاب با عملگر تورنمنت باینری صورت میگیرد اما معیار انتخاب بر مبنای عملگر مقایسه ازدحام ≥ n  خواهد بود.
در این الگوریتم تنوع جمعیت در هر نسل با اعمال عملگر مقایسه ازدحام هنگام انتخاب تورنمنت باینری تضمین خواهد شد که در آن اصولاً نیازی به هیچ گونه پارامتر “به اشتراک گذاری” نمیباشد. لذا ضعف روش های دیگر مانند NSGA را نخواهد داشت. هم چنین می توان دید که فاصله ازدحام در فضای توابع مطلوبیت محاسبه میگردد که البته با فضای پارامترها نیز قابل محاسبه میباشد. نکته دیگر این که در ساخت جمعیت هر نسل، روش انتخاب a+b بجای (a,b) به کار رفته است که این امر پایداری روش را بالاتر خواهد برد و عدم حذف افراد خوب نسل قبل را در نسل جدید بیمه خواهد نمود (براجعه، ۱۳۹۲).

فصل چهارم

تحلیل دادهها

۴-۱- مقدمه

پس انجام مطالعات کتابخانهای و بررسی کارهای صورت گرفته در زمینه این پژوهش و تعیین روش و متعاقباً مدل مناسب برای مکانیابی کیوسکهای خودپرداز بانک ملت، از میان روشها و مدلهای متعددی که برای مکانیابی مورد استفاده قرار میگیرد، نوبت به گردآوری دادههای مورد نیاز جهت حل مدل میرسد. پس از این مرحله و نوشتن الگوریتم مناسب جهت حل مدل، از دادههای مذکور برای تکمیل الگوریتم استفاده کرده و در نهایت با اجرای نرمافزار به پاسخهای مورد نظر میرسیم.
در این فصل به معرفی مکانهای کاندید، ارایهی دادههای مربوط به پارامترهای مدل و تبیین چگونگی تعیین این دادهها، تشریح الگوریتم پیشنهادی و در نهایت ارایه پاسخهای نرم افزار میپردازیم.
 
یافتههای پژوهش
همانطور که در فصل قبل اشاره شد، برای حل مدل تعیین شده جهت اخذ تصمیم تعیین مکان، از آنجاییکه وارد کردن محدودیت صف در الگوریتم ژنتیک تحت عنوان محدودیت قابل انجام نبود، این محدودیت به عنوان تابع هدف مینیمم سازی (حداقل کردن تعداد افراد موجود در صف) وارد الگوریتم شده و مدل تبدیل به مدل حداکثر پوشش با دو تابع هدف گردید. که اولین تابع حداکثر سازی سود بانک و تابع دوم حداقل سازی تعداد افراد موجود در صف میباشد.
۴-۲-۱- مکانهای کاندید