دانلود پایان نامه ارشد درباره مکانیابی، استراتژی، الگوریتم ژنتیک

جابه‌جایی حقیقی، ترکیب تک‌نقطه‌ای، ترکیب دو نقطه‌ای، ترکیب n نقطه‌ای، ترکیب یکنواخت، ترکیب حسابی، ترتیب، محدّب، بخش نگاشته، چرخه.
جهش64
جهش نیز عملگر دیگری هست که جواب‌های ممکن دیگری را متولد می‌کند. در الگوریتم ژنتیک بعد از اینکه یک عضو در جمعیت جدید بوجود آمد هر ژن آن با احتمال جهش، جهش می‌یابد. در جهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری روش‌های متفاوت جهش استفاده می‌شود.
انواع روشهای عملگر جهش عبارتند از :
جهش باینری، جهش حقیقی، وارونه سازی بیت، تغییر ترتیب قرارگیری، وارون سازی، تغییر مقدار.
رمزگشایی65
رمزگشایی، عکسِ عمل رمزگذاری است. در این مرحله بعد از اینکه الگوریتم بهترین جواب را برای مسأله ارایه کرد لازم است عکس عمل رمزگذاری روی جواب‌ها یا همان عمل رمزگشایی اعمال شود تا بتوانیم نسخه واقعی جواب را به وضوح در دست داشته باشیم.
نقاط قوّت الگوریتم‌های ژنتیک
اولین و مهمترین نقطه قوّت این الگوریتم‌ها این است که الگوریتم‌های ژنتیک ذاتاً موازی‌اند. اکثر الگوریتم‌های دیگر موازی نیستند و فقط می‌توانند فضای مسأله مورد نظر را در یک جهت در یک لحظه جستجو کنندو اگر راه‌حل پیدا شده یک جواب بهینه محلی باشد و یا زیر مجموعه‌ای از جواب اصلی باشد باید تمام کارهایی که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجایی که GA چندین نقطه شروع دارد، در یک لحظه می‌تواند فضای مسأله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه‌ها ادامه می‌یابند و منابع بیشتری را در اختیارشان قرار می‌گیرد.
به دلیل موازی بودن و این که چندین رشته در یک لحظه مورد ارزیابی قرار می‌گیرند الگوریتم های ژنتیک برای مسائلی که فضای راه‌حل بزرگی دارند بسیار مفید‌ند. اکثر مسائلی که این گونه‌اند به عنوان غیرخطی شناخته شده‌اند. در یک مسأله خطی،Fitness هر عنصر مستقل است، پس هر تغییری در یک قسمت بر تغییر و پیشرفت کل سیستم تأثیر مستقیم دارد. می‌دانیم که تعداد کمی از مسائل دنیای واقعی به صورت خطی‌اند. در مسائل غیرخطی تغییر در یک قسمت ممکن است تاثیری ناهماهنگ بر کل سیستم و یا تغییر در چند عنصر تاثیر فراوانی بر سیستم بگذارد. خوشبختانه موازی بودن GA باعث حل این مسأله می‌شود و در مدت کمی مشکل حل می‌شود. مثلاً برای حل یک مسأله خطی 1000 رقمی 2000 امکان حل وجود دارد ولی برای یک غیرخطی 1000 رقمی امکان. یکی از نقاط قوت الگوریتم‌های ژنتیک که در ابتدا یک کمبود به نظر می‌رسد این است که: GA ها هیچ چیزی در مورد مسائلی که حل می‌کنند نمی‌دانند و اصطلاحاً به آنها «ساعت‌ساز نابینا»66 می‌گوییم. آنها تغییرات تصادفی را در راه‌حل‌های کاندیدشان می‌دهند و سپس از تابع برازش برای سنجش این که آیا آن تغییرات پیشرفتی ایجاد کرده‌اند یا نه، استفاده می‌کنند. مزیت این تکنیک این است که به GA اجازه می‌دهد تا با ذهنی باز شروع به حل مسائل کند. از آنجایی که تصمیمات آن اساساً تصادفی است، بر اساس تئوری همه راه‌حل‌های ممکن به روی مسأله باز است، ولی مسائلی که محدود به اطلاعات هستند باید از راه قیاس تصمیم بگیرند و در این صورت بسیاری از راه‌حل‌های نو و جدید را از دست می‌دهند.
یکی دیگر از مزایای الگوریتم این است که آنها می‌توانند چندین پارامتر را همزمان تغییر دهند. بسیاری از مسائل واقعی نمی‌توانند محدود به یک ویژگی شوند تا آن ویژگی ماکسیمم شود و باید چند جانبه در نظر گرفته شوند.GA ها در حل این گونه مسائل بسیار مفیدند، و در حقیقت قابلیت موازی کار کردن آنها این خاصیت را به آنها می‌بخشد. و ممکن است برای یک مسأله 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).
سابقه پژوهشهای دارای موضوعات مشابه
پژوهش حاضر به لحاظ بهرهگیری از مدل و الگوریتمی جدید جهت اخذ تصمیم مکانیابی دارای سابقهی مشابه نمیباشد اما از آنجاییکه در پایان نامه موجود از تمامی مباحث مرتبط همچون مکانیابی، مساله حداکثر پوشش و الگوریتم ژنتیک استفاده

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *