الگوریتم فرا ابتکاری و الگوریتم ژنتیک

(3-9)
Widget not in any sidebars

(3-10)
(3-11)
(3-12)
(3-13)
, , (3-14)
معادله (3-1) نشان دهنده تابع هدف مدل است که شامل هزینههای خدمتدهی به مشتریان توسط تیمها و هزینههای جابجایی توسط وسایل نقلیه و همینطور هزینههای دیرکرد میباشد. محدودیت (3-2) و (3-3) بیان کننده این هستند که تمام وسایل نقلیه باید از مرکز پخش مسیر خود را شروع کنند و در انتهای مسیرشان به مرکز پخش بازگردنند. محدودیتهای (3-4) و (3-5) نشان میدهند که به هر مشتری تنها یک وسیله و یک تیم وارد و از آن خارج میشوند. محدودیت (3-6) بیان کننده این است که همان وسیله و تیم ورودی به هر مشتری ، باید از آن خارج شوند. محدودیت (3-7) محدودیت مورد نیاز جهت جلوگیری از ایجاد زیرتور است. محدودیتهای (3-8) و (3-9) بیان کننده ارتباط زمان خدمتدهی بین مشتریان متوالی در یک تور میباشد. محدودیتهای (3-10) و (3-11) محدودیتهای شدنی بودن مسأله هستند و به ترتیب مربوط به توانایی وسیله نقلیه و توانایی تیم برای خدمتدهی به یک مشتری هستند. محدودیتهای (3-12) و (3-13) نشان دهنده ارتباط بین زمان اتمام خدمتدهی به هر مشتری نسبت به موعد زمانی تعریف شده برای آن است.
3-3. روش حل مدل پیشنهادی
مدل پیشنهادی به دنبال کمینه کردن هزینههای جابجایی ، خدمتدهی و دیرکرد میباشد. در واقع هدف تعین تورهای وسایل نقلیه و تخصیص تیمها به مشتریان و پس از آن برنامهریزی همزمان مسیرهای وسایل نقلیه و تیمها به گونهایی است که به تمام مشتریان موجود در سیستم خدمتدهی انجام شود و همینطور هزینههای کل حداقل شود. مدل پیشنهادی جهت صحهگذاری و اطمینان توسط برنامه 11 CPLEX حل شده است. اما برای مسائل تولید شده در ابعاد بزرگتر از الگوریتم فرا ابتکاری ژنتیک بهره برده شده است. در ادامه به معرفی این الگوریتم و همینطور نحوه استفاده از آن برای حل مدل پیشنهادی پرداخته شده است.
3-4. الگوریتم ژنتیک (GA)
3-4-1. تعریف
از سال 1960 تقلید از پدیده‌های طبیعی برای استفاده در الگوریتم‌های قوی جهت حل مسایل مشکل بهینه‌سازی مورد توجه قرار گرفت که تکنیک‌های محاسبه تکاملی نام گرفتند. الگوریتم ژنتیک که اولین بار توسط جان هالند [34] در دانشگاه میشیگان پیشنهاد شد و استراتژی‌ها و برنامه‌ریزی‌های تکاملی که توسط رچنبرگ و چیفل و فوگوگل و کوزا ایجاد شدند، از جمله روش‌های محاسبه تکاملی هستند.
روش‌های بهینه‌سازی الهام گرفته از طبیعت با روش‌های متعارف بهینه‌سازی تفاوت مهمی دارند. در روش‌های متعارف هرجواب کاندیدای جدید در صورتی به عنوان جواب جدید انتخاب می‌شود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتم‌های الهام گرفته از طبیعت به تمام جواب‌های کاندیدای جدید شانس انتخاب داده می‌شود.
الگوریتم ژنتیک یکی از مهم‌ترین الگوریتم‌های ابتکاری می‌باشد که از آن برای بهینه‌سازی توابع مختلف استفاده می‌شود. در این الگوریتم اطلاعات گذشته با توجه به موروثی ‌بودن الگوریتم استخراج شده و در روند جستجو مورد استفاده قرار می‌گیرد.
ابتدا توسط هالند [34] یک مفهوم اولیه از الگوریتم ژنتیک ارائه شد و سپس گلدبرگ [35] آن را توصیف کرد. الگوریتم‌های ژنتیک، تکنیک‌های جستجوی تصادفی هستند که بر اساس انتخاب طبیعی و نسل‌شناسی طبیعی کار می‌کنند.
این الگوریتم‌ها تفاوت‌هایی اساسی با روش‌های جستجو و بهینه‌سازی متداول دارند که گلدبرگ این تفاوت‌ها را به صورت ذیل خلاصه کرده است [35].
الگوریتم ژنتیک با مجموعه‌ای از جواب‌های کدگذاری شده کار می‌کند نه با خود آنها.
الگوریتم ژنتیک در یک جمعیت از جواب‌ها و با مجموعه‌ای از آنها شروع به جستجو می‌کند نه با یک جواب.
الگوریتم ژنتیک از اطلاعات تابع برازش استفاده می‌کند، نه از مشتق‌ها و یا علوم کمکی دیگر.
الگوریتم ژنتیک از قواعد انتقال احتمالی استفاده می‌کند نه از قواعد قطعی.
3-4-2. گذری بر ژنتیک طبیعی