
به آنها میبخشد. و ممکن است برای یک مسأله 2 یا چند راهحل پیدا شود، که هر کدام با در نظرگرفتن یک پارامتر خاص به جواب رسیدهاند.
به طور خلاصه مزایای الگوریتم ژنتیک را میتوان در موارد زیر برشمرد:
با متغیرهای پیوسته و هم گسسته میتواند عمل بهینهسازی را انجام دهد.
نیازی به محاسبه مشتق توابع ندارد.
بطور همزمان میتواند تمامی ناحیه جستجو شونده وسیع تابع هزینه را جستجو کند.
قادر به بهینه سازی مسائل با تعداد متغیرهای زیاد میباشد.
قابل اجرا از طریق کامپیوترهای موازی است.
توابع هزینهای که بسیار پیچیده باشند نیز از این طریق قابل بهینهسازی میباشند و الگوریتم در اکسترمم محلی به دام نمیافتد.
قادر است تا چند جواب بهینه را بطور همزمان به دست آورد نه فقط یک جواب.
الگوریتمهای ژنتیک بر روی مجموعهای از راهحلها اعمال میشوند و نه بر روی یک راهحل خاص.
قادر است تا متغیرها را کد بندی نموده و بهینهسازی را با متغیرهای کدبندی شده انجام دهد. کد بندی سرعت همگرایی الگوریتم را افزایش میدهد.
الگوریتم توانایی کار کردن با دادههای عددی تولید شده و دادههای تجربی را علاوه بر توابع تحلیلی دارد.
فرآیند ارایه شده توسط الگوریتمهای ژنتیک بر روی فضایی از مجموعه نمایندگان یا همان فضای کروموزومها اعمال میگردد و نه بر روی خود فضای راهحلها.
الگوریتمهای ژنتیک از قوانین انتقالی احتمالی بجای قوانین انتقالی قطعی استفاده میکنند، بدین معنا که حرکت آن در هر نقطه از الگوریتم کاملا احتمالی بوده و بر اساس قطعیت صورت نمیپذیرد. این امر از مزایای مهم این روش بوده و از افتادن سیستم در کمینه محلی جلوگیری مینماید.
البته میزان احتمال به گونهای است که احتمال حرکت به سمت مسأله بیشتر از احتمال حرکت آن به سمت مخالف جواب میباشد.
تنها ملاک ارزشیابی و سنجش میزان شایستگی هر راهحل توسط الگوریتمهای ژنتیک، مقدار تابع شایستگی آن در فضای کروموزومها میباشد و نه معیارهای مورد نظر در سطح فضای راهحلها.
برای حل برخی از مسائلی از رده NP-Hard نیز استفاده میشود.
این الگوریتم بیشتر در مسائل بهینه سازی و امثالهم بکار میرود.
محدودیتهای GA ها
یک مشکل چگونگی نوشتن عملگر ارزیاب است که منجر به بهترین راهحل برای مسأله شود. اگر این کارکرد برازش به خوبی و قوی انتخاب نشود ممکن است باعث شود که راهحلی برای مسأله پیدا نکنیم یا مسألهای دیگر را به اشتباه حل کنیم. به علاوه برای انتخاب تابع مناسب برای ارزیاب، پارامترهای دیگری مثل اندازه جمعیت، نرخ ترکیب، قدرت و نوع انتخاب هم باید مورد توجه قرار گیرند.
مشکل دیگر، که آن را «نارس» مینامیم این است که اگر یک ژنوم که فاصلهاش با سایز ژنومهای نسلاش زیاد باشد. (خیلی بهتر از بقیه باشد) خیلی زود دیده میشود (ایجاد میشود) ممکن است محدودیت ایجاد کند و راهحل را به سوی جواب بهینه محلی سوق دهد. این اتفاق معمولاً در جمعیتهای کم اتفاق میافتد. روشهای Rank Scaling , Tournament Selection بر این مشکل غلبه میکنند.
استراتژی برخورد با محدودیتها
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیتهای مسأله میباشد، زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزومهای غیرموجّه میشود. «میکالویچ» چند تکنیک معمول جهت مواجهه با محدودیتها تقسیمبندی نموده است که در ادامه به چند تا از آنها اشاره میشود.
استراتژی اصلاح عملگرهای ژنتیک
یک روش برای جلوگیری از تولید کروموزوم غیرموجّه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزمها، کروموزوم تولید شده نیز موجّه باشد. در این حالت یکسری مشکلات وجود دارد. مثلاً پیدا کردن عملگری که دارای شرط فوق باشد بسیار دشوار بوده و از مسأله دیگر متفاوت میباشد.
استراتژی رَدّی
در این روش پس از تولید هر کروموزوم آنرا از نظر موجّه بودن تست کرده و در صورت غیرموجّه بودن حذف میگردد. این روش بسیار ساده و کارا میباشد.
استراتژی اصلاحی
در این روش به جای اینکه کروموزوم غیرموجّه حذف گردد تبدیل به یک کروموزوم موجّه میشود. این روش نیز مانند روش اول به مسأله وابسته بوده و یافتن فرآیند اصلاح گاهی بسیار پیچیده میباشد.
استراتژی جریمهای
در این روش بر خلاف سه روش قبل که از ورود جوابهای غیرموجّه جلوگیری میکردند، جواب غیرموجّه با احتمال کم امکان حضور مییابند. سه روش فوق دارای این عیب بودند که به هیچ نقطهای بیرون از فضای موجّه توجّه نمیکردند، اما در بعضی مسائل بهینهسازی، جوابهای غیرموجّه درصد زیادی از جمعیت را اشغال میکنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجّه انجام گیرد شاید یافتن جواب موجّه خیلی وقتگیر و مشکل باشد.
استراتژی جریمهای از متداولترین تکنیکهای مورد استفاده برای سر و کار داشتن با جوابهای غیرموجّه میباشد که در آن ابتدا محدودیتهای مسأله در نظر گرفته نمیشوند پس برای هر تخلّف از محدودیتها یک جریمه اختصاص داده میشود که این جریمه در تابع هدف قرار میگیرد.
مسأله اصلی چگونگی انتخاب یک مقدار مناسب برای مقدار جریمه میباشد تا در حل مسائل به ما کمک نماید.
نکتهای که در روش جریمه وجود دارد این است که یک جواب غیرموجّه به سادگی حذف نمیشود زیرا ممکن است در ژنهای آن اطلاعات مفیدی وجود داشته باشد که با اندکی تغییر به جواب بهینه تبدیل شود.
مرور ادبیات کاربرد الگوریتم ژنتیک در مسایل مکانیابی
الگوریتم ژنتیک برای اولین بار روی مسایل مکانیابی – تخصیص توسط هسیج67 و گودچایلد68 در سال 1986 بکار برده شد. گنگ و همکارانش69 در سال 1999 از یک ژنتیک برای تخصیص m ماشین به m محل استفاده کردند و مقایسهای بین این الگوریتم و دیگر روشهای حل زمانبر انجام دادند. مورنو و همکارانش70 در سال 1994 ژنتیک را برای مسایل p-median بکار بردند. کراتیکا و همکارانش71 در سال 2001 یک ژنتیک برای یک مثال ساده مکانیابی کارخانه بکاربردند و بزکیا و همکارانش72 یک ژنتیک کارا برای مسایل p-median توسعه دادند و ثابت کردند که الگوریتم نسبت به دیگر الگوریتمهای ارایه شده کارایی بیشتری دارد. جارامیلو و همکارانش73 در سال 2002 مقایسهای از عملکرد ژنتیک روی انواع مسایل مختلف مکانیابی داشتند. ایتوگ74 و سایدام75 یک ژنتیک ترکیبی را برای مسایل مکانیابی حداکثر پوشش مورد انتظار با استفاده از الگوریتم تقریبی هایپروکوب توسعه دادند. همچنین یک مقایسه بین ژنتیک بکار رفته روی مسایل جایابی حدکثر پوشش مورد انتظار و دیگر روشها و الگوریتمها انجام و نشان دادند که حداقل یکی از ژنتیکهای بکار برده شده در این مدل به یک جواب نزدیک به بهینه با زمان حل قابل قبول منجر میشود. توپوگلو و همکارانش76 در سال 2007 یک ژنتیک جدید ارایه کردند و مقایسهای بین ژنتیک ارایه شده و جستجوی ممنوع انجام دادند. شوندی و محلوجی در سال 2006 پس از ارایه مدل FQMCLP و با توجه به شباهت این مدل به مساله P-median یک ژنتیک مانند ژنتیک ارایه شده توسط بزکایا برای مدل p-median، برای مدلشان اراده دادند. شینگ و همکارانش77 در سال 2007 یک ژنتیک برای مکانیابی- تخصیص ارایه کردند، آنها در این الگوریتم از تکنیک ساب گرادیان برای حل کاراتر آن استفاده کردند. یانگ و همکارانش در سال 2007 یک ژنتیک برای جایابی ایستگاههای آتشنشانی که با استفاده از برنامهریزی چندهدفه فازی بهینه میشدند، ارایه کردند (شوندی و مردانه خامنه، 1390).
سابقه پژوهشهای دارای موضوعات مشابه
پژوهش حاضر به لحاظ بهرهگیری از مدل و الگوریتمی جدید جهت اخذ تصمیم مکانیابی دارای سابقهی مشابه نمیباشد اما از آنجاییکه در پایان نامه موجود از تمامی مباحث مرتبط همچون مکانیابی، مساله حداکثر پوشش و الگوریتم ژنتیک استفاده گردیده است، میتوان به گروهی از سوابق مرتبط با موارد فوق که بیشترین قرابت را با پژوهش حاضر داشته اند اشاره نمود. در رابطه با مکانیابی صنایع پژوهشهای داخلی و خارجی زیادی انجام گرفته است که غالب روشهای بکار گرفته شده در آنها مدلهای تصمیم گیری چندمعیاره و مدلهای ریاضی مکانیابی که عموماً به برنامه ریزی آرمانی و برنامه ریزی صفر و یک محدود میگردد است. در سالهای اخیر کارهای قابل قبولی در رابطه با بکارگیری مدل ریاضی حداکثر پوشش انجام گرفته است که البته بیشتر در قالب مقاله و بدون بکارگیری مورد مطالعاتی واقعی ارایه گردیده است. در اینجا به تعدادی از این پژوهش ها اشاره میکنیم :
علی حسینی (1379) در مطالعهای با عنوان «بکارگیری الگوریتم ژنتیک برای حل مساله پوشش مجموعه» با استفاده از يك مساله آزمون كه به صورت تصادفی توليد شده بود. بهينه ترين وضعيت الگوريتم را از نظر بكارگيری عملگر جهشی ، مكانيسم انتخاب و نرخ تقاطعی معرفی کرد. سپس الگوريتم پيشنهادی طراحی و بر روی تعدادی مساله آزمون كه آنها نيز به صورت تصادفی توليد شده بودند پياده کرده و نتايج حاصله را با الگوريتم ابتكاری (Greedy Heuristic) هيراگو مقايسه کرد. الگوريتم پيشنهادی او دارای شرايط ذيل بود : الف – سيستم كدينگ : رشته دودويی ب – ايجاد جمعيت اوليه : تصادفی – بدون كروموزوم تكراری و غير موجه پ – عملگر تقاطعی : دو نقطه برش با نرخ تقاطعی 0/95 ت – عملگر جهشی: يكنواخت با نرخ جهشی0/1 ج- تابع برازش : تابع هدف مساله چ – برخورد با محدوديت ها : استراتژی ردی (علیحسینی، 1379)
صادقی در سال 1387 در پژوهش خود با عنوان «جایابی بهینه مراکز توزیع در فرآیند بازاریابی با استفاده از روشهای ریاضی» به ارایه الگو و مدلی جهت مکان یابی مراکز فروش و خدمات پس از فروش شرکت تالیا پرداخته است. او از تلفیق دو مدل TOPSIS و برنامهریزی صفر و یک به ترتیب برای عوامل مشتری مدار – بازاریابی و محدودیت های مالی – جغرافیایی استفاده کرده است (صادقی،1387)
صفاریان (1388) در مقالهای با عنوان «کاربرد الگوریتم ژنتیک برای حل مساله پوشش حداکثر» يك الگوريتم ژنتيك مناسب براي حل مدلهاي Maximal Covering ارایه کرد. اين الگوريتم را برروي 75 مساله متفاوت اجرا نموده و نتايج آن را با نتايج حاصل از دو الگوريتم لاگرانژ و گردي ادينگ برروي همان مسايل مقايسه کرد.. همچنين نتايج حاصل از اين الگوريتم را با نتايج حاصل از نرم افزار لينگو مقايسه كرده و از نظر ميزان دقت و كارايي مورد بررسي و مطالعه قرار داد (صفاریان، 1388).
سید حسینی و همکاران (1388) به حل مساله مکانیابی پایانههای اتوبوس رانی درون شهری با استفاده از الگوریتم ژنتیک پرداختند. آنها براي حل مساله يك الگوريتم ژنتيك پيشنهاد دادند. مهمترين مزيت الگوريتم ژنتيك پيشنهادي، رسيدن به جواب دقيق تر در زمان كمتر مي باشد. براي تاييد کارایی روش خود، الگوريتم را براي شبكه هاي اتوبوسراني مشهد و تهران اجرا و نتايج آن را با نتايج كوشش هاي پيشين مقايسه کردند (سیدحسینی و همکاران، 1388).
فرقانی و همکاران (1389) در مقالهای تحت عنوان «توسعه یک مدل دو هدفه برای مساله حداکثر پوشش با محدودیت پارامترهای صف» مدل ارایه شده توسط کورآ و لورنا که به صورت يک مساله حداکثر پوشش با محدوديت شاخصهاي صف است، توسعه دادند بگونه اي که علاوه بر تابع هدف حداکثر پوشش، هدف حداقل نمودن فواصل خدمت دهنده ها تا مشتريان نيز در نظر گرفته شود. سپس مدل توسعه داده شده خود را توسط الگوريتم ژنتيک و نرم افزارCPLEX حل کردند (فرقانی و همکاران، 1389).
مرادی و همکاران (1389) در مقاله «مکانیابی مراکز ارایه خدمات رقابتی با هدف کاهش ازدحام ترافیک شهری» مدلی برای مکان يابی مراکز با محدوديت ظرفيت، طراحی کرده و سپس يک الگوريتم شبيه سازی تبريدی موازی برای حل اين مدل ارایه کردند. در پايان، الگوريتم پيشنهادی برای تعيين مکان های مراکز سلامت در شهر اصفهان استفاده قرار داده و کارايی آن را بررسی کردند (مرادی و همکاران 1389).
شوندی و خامنه (1390) مساله جایابی پوششی با در نظر گرفتن تراکم مشتریان و تقاضای از دست
