بخشی از مقاله
چکیده
الگوریتم بهینهسازی فاخته1 یکی از جدید ترین و قویترین روشهای بهینه سازی تکاملی می باشد که تا کنون معرفی شده است. این الگوریتم الهام گرفته از روش زندگی پرنده ای بنام فاخته میباشد. روش زندگی و تخمگذاری جالب این پرنده نوید یک الگوریتم بهنیهسازی خوب و قابل را در طبیعت وحشی می دهد. برای هر متاهیوریستیک، پارامترهایی برای تنظیم وجود دارد.این پارامتر ها تاثیر زیادی بر کارایی الگوریتم دارد بنابراین تنظیم درست پارامترها برای حل یک مسئله خاص بسیار با اهمیت می باشد؛ از این رو در این تحقیق به تنظیم پارامترهای الگوریتم فاخته برای حل مسئله مسیر یابی خودرو همراه با پنجره های زمانی می پردازیم و با اجرا طراحی آزمایشهای گوناگون آماری، به دنبال پیدا کردن مناسبترین پارامترها برای نمود مطرح شده می باشیم.
کلمات کلیدی:الگوریتم بهینهسازی فاخته، تنظیم پارامتر، مسئله مسیر یابی خودرو همراه با پنجره های زمانی، طراحی آزمایشهای آماری
-1 مقدمه
مسائل مسیریابی حمل کننده با پنجره های زمانی یک حالت توسعه یافته از مسائل مسیریابی حمل کننده ظرفیت دار و با محدودیت مسافت است که محدودیت های ظرفیت به آن تحمیل می شوند و به هر مشتری i با یک زمان فرجه دار[ai,bi] که پنجره ی زمانی نامیده می شود نسبت داده می شود. زمانی که هر وسیله ی حمل ونقل انبار را ترک می کند،زمان سفر یعنی Tij برای هر کمان یا Te برای هر یال و زمان سرویس دهی Si برای هر مشتری نیز داده می شود. زمان سرویس دهی برای هر مشتری می بایست در فاصله پنجره زمانی اش شروع شود و هر وسیله ی نقلیه در محل خدمت رسانی اش به مدت Si توقف کند به علاوه اگر وسیله حمل ونقل زودتراز زمان به مشتری iرسید به آن اجازه داده می شود تا لحظه ی ai یعنی زمانی که سرویس دهی باید شروع شود، صبرکند. مسائل مسیریابی حمل کننده با پنجره های زمانی شامل پیداکردن مجموعه ای از مدارهای ساده ی K عضوی با کمترین هزینه است .[1]
-1-2فرمول بندی مسئله
مسائل مسیریابی حمل کننده ها با پنجره های زمانی می تواند همانند ذیل به صورت مدل جریان شبکه ی چندکالایی با پنجره ی زمانی و محدودیت ظرفیت ارائه شود:
محدودیت ها :تابع هدف این مدل غیر خطی هزینه ی کلی را بیان می کند. با توجه به این که N={0,n+1} بیان کننده ی مجموعه ی مشتریان است، محدودیت - 2-2 - تخصیص هر مشتری را دقیقا به یک مسیر محدود می کند. سپس محدودیت های - 5-2 - - - 4-2 - - - 3-2 - جریان یک مسیر را که توسط وسیله ی نقلیه ی k پیموده می شود، نشان می دهد. علاوه بر این محدودیت های - 8-2 - = - 7-2 - - - 6-2 - و - 9-2 - شدنی بودن برنامه ی زمانی با توجه به محدودیت های زمان و ظرفیت، تضمین می کند.
برای هر وسیله ی k محدودیت - 8-2 - نشان دهنده ی آن است که هر کجا مشتری i توسط آن وسیله ی نقلیه سرویس رسانی نشده باشد wik=0 است. شرایط - 11-2 - سبب می شوند که بتوان محدودیت های - 6-2 - را به صورت زیر خطی کرد:زمانی که Mij یک مقدار بزرگ است می تواند با max{bi + si + tij – aj ,0}, - i,j - ε A جابجا شود و محدودیت - 6- 2 - تنها روی یال هایε A - i,j - که در آنها Mij>0 است تاثیر می گذارد.درغیر اینصورت زمانی که max{bi + si + tij – aj ,0} این محدودیت ها تمام مقادیر wik ,wjk و xijk را شامل می شوند .
-2 الگوریتم بهینه سازی فاخته
فاخته مشهورترین پارازیت اولادی می باشد که به نوعی یک متخصص در زمینه فریب بی رحمانه می باشد. فاخته مادر یکی از تخم های پرنده مادر میزبان را از بین میبرد و تخم خود را لابلای تخمهای دیگر موجود در لانه میزبان قرار می دهد و سریعا از محل دور می شود و نگهداری از تخم را برگردن پرنده ماده میزبان می گذارد. همانند سایر الگوریتمهای تکاملی فاخته هم با یک جمعیت اولیه کار خود را شروع می کند. جمعیتی متشکل از فاخته ها، این جمعیت از فاخته ها تعدادی تخم دارند که آنها را در لانه تعدادی پرنده ی میزبان خواهند گذاشت. تعدادی از این تخم ها که شباهت بیشتری به تخم های پرنده میزبان دارند شانس بیشتری برای رشد و تبدیل شدن به فاخته بالغ خواهند داشت. سایر تخم ها توسط پرنده میزبان شناسایی شده و از بین می روند. هرچه تخمهای بیشتری در یک ناحیه قادر به زیست باشند و نجات یابند به همان اندازه سود بیشتری به آن منطقه اختصاص می یابد. بنابراین موقعیتی که در آن بیشترین تعداد تخمها نجات یابند پارامتری خواهد بود که الگوریتم فاخته قصد بهینه سازی آن را دارد.
1-2 تولید محلهای سکونت اولیه فاخته ها - جمعیت اولیه جوابهای کاندید -
الگوریتم بیهنه سازی توده این الگوریتم ژنتیک و برای حل یک مساله بهینه سازی لازم است تا مقادیر متغیرهای مساله بفرم یک آرایه شکل گیرند. در در .آرایه ها با نامهای "کروموزوم" و "موقعیت ذرات" مشخص می شوند. ولی در الگوریتم بهنیه سازی فاخته به این آرایه یا "محل سکونت"2 می گوییمخواهد بود که موقعیت فعلی زندگی فاخته ها را نشان می دهد. این آرایه به شکل N*1یک آرایه محل سکونت بعدی یکN یک مساله بهینه سازی زیر تعریف می شود:میزان مناسب بودن - یا مقدار سود - در محل سکونت فعلی با ارزیابی تابع سود - FP - درمحل سکومت بدست می آید. پس:
همانطور که دیده می شود فاخته الگوریتمی است که تابع سود را ماکزیمم می کند. برای استفاده ازالگوریتم فاخته برای حل مسایل کمینه سازی کافی است یک علامت منفی در تابع هزینه ضرب کنیم.
برای شروع الگوریتم بهینه سازی یک ماتریس محل سکونت به سایزNpop3*Nvar4 تولید می شود. سپس برای هر کدام از این محل سکونت ها تعدادی تصادفی تخم تخصیص می یابد. در طبیعت هر فاخته بین 5 تا 20 تخم می گذارد. این اعداد به عنوان حد بالا و پایین تخصیص تخم به هر فاخته در تکرارهای مختلف استفاده می شود. دیگر عادت هر فاخته حقیقی این است که آنها در یک دامنه مشخص تخم های خود را می گذارند .از این به بعد حداکثر دامنه تخمگذاری5 را ELR می نامیم. در یک مساله بهینه سازی به متغیرهای حد بالای6 و حد پایین7 هر فاخته دارای ELR ی خواهد بود که متناسب است با تعداد کل تخمها، تعداد تخم های فعلی فاخته و همچنین حد بالا و پایین متغیرهای مساله، بنابراین ELR بصورت زیر تعریف می شود :
