برای جستجو در بین هزاران پایان نامه در موضوعات مختلف     

      و دانلود متن کامل آنها با فرمت ورد اینجا کلیک کنید     

 
دانلود پایان نامه
(11.3)
اگر نقاط شدنی برای w بدست نیاید، بنابراین تامین کردن بعضی از مشتریان امکان پذیر نخواهد شد و سمت راست عبارت (8.3) بی معنی خواهد شد و بعنوان هزینه پنالتی تابع هدف زیر جایگزین می شود [5] :
(12.3)
3-6- تشریح الگوریتم ژنتیک
الگوریتم های ژنتیک تکنیک نسبتا جدید هستند که، از آنها برای حل مسائل مختلف استفاده شده است. دو ویزگی اصلی این تکنیک یکی الهام گیری آن از پدیده های طبیعی خلقت و دیگری قابلیت پردازش موازی می باشد. الگوریتم های ژنتیک با الهام از فرایند تکامل طبیعی به عنوان یک روش جستجوی هوشمند در حل مسائل بهینه سازی کاربرد گسترده ای یافته است. الگوریتم ژنتیک برگرفته از الگوریتم تکاملی است که اولین بار توسط جان هالند [33] در دانشگاه میشیگان پیشنهاد شد و استراتژی ها و برنامه ریزی های تکاملی که توسط رچنبرگ و چیفل و فوگوگل و کوزا ایجاد شدند، از جمله روش های محاسبه تکاملی هستند.
روش های بهینه سازی الهام گرفته از طبیعت با روش های متعارف بهینه سازی تفاوت مهمی دارند. در روش های متعارف هر جواب کاندیدای جدید در صورتی به عنوان جواب جدید انتخاب می شود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتم های الهام گرفته از طبیعت به تمام جواب های کاندیدای جدید شانس انتخاب داده می شود. الگوریتم های ژنتیک، تکنیک های جستجوی تصادفی هستند که بر اساس انتخاب طبیعی و نسل شناسی طبیعی کار می کنند. الگوریتم ژنتیک روشی مستقل از دامنه مساله است و به سرعت فضای جستجو را برای نقاطی با تابع صلاحیت بهتر، جستجو می کند.
3-6-1- مفاهیم کلیدی الگوریتم ژنتیک
با نگاهی به آنچه که تاکنون مطرح شده مشخص است که در تبیین الگوریتم ژنتیک مباحث کلیدی ذیل باید مورد بررسی قرار گیرند. بنابراین در ادامه این مباحث بررسی خواهند شد:
تعریف یک سیستم کدینگ
ایجاد جمعیت اولیه
تعریف عملیات ژنتیک
تابع برازش
استراتژی برخورد با محدودیت ها
3-6-1-1- کدینگ
اولین گام در بکارگیری و پیاده سازی یک الگوریتم ژنتیک نمایش جوابهای مساله بصورت یک کروموزوم است. در حقیقت این عمل یک مفهوم کلیدی در الگوریتم های ژنتیک می باشد که با استفاده از عمل کدینگ ما می توانیم مساله را به زبان برنامه نویسی تبدیل نماییم.
3-6-1-2- ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار می رود، ایجاد یک جمعیت اولیه از کروموزوم هاست. در این مرحله جواب اولیه معمولا بصورت تصادفی تولید می شود. البته در بعضی موارد با توجه به نوع مساله و برای بالا بردن سرعت همگرایی الگوریتم از روش های ابتکاری نیز استفاده گردیده است.
3-6-1-3- عملگرهای الگوریتم های ژنتیک
عملیات ژنتیک فرآیند انتقال موروثی ژن ها را برای ایجاد اولاد جدید در هر نسل تقلید می کنند. یک بخش مهم در الگوریتم ژنتیک ایجاد کروموزوم های جدید موسوم به اولاد از طریق بعضی کروموزوم های قدیم موسوم به والدین است. این فرآیند مهم توسط عملیات ژنتیک صورت می گیرد. به طور کلی این عملیات توسط دو عملگر عمده انجام می شود. عملگر جهشی و عملگر تقاطعی. اما عملا عملگرها بر حسب نوع مساله تعریف شده و کاملا به توانایی تحلیل گر وابسته بوده و تجربی می باشند. کارایی این عملگرها در رسیدن به جواب بهنه در مسائل مختلف متفاوت است. بعضی از عملگرها فقط یک کروموزوم را در نظر گرفته و بر اساس اطلاعات آن، کروموزوم ایجاد می کنند اما بعضی دیگر بر روی چند کروموزوم یا حتی کلیه کروموزوم های جمعیت قبل عملیات انجام می دهند.
3-6-1-3-1- عملگرهای جهشی
عملگرهایی که یک یا چند ژن از یک کروموزوم را انتخاب و مقادیر آنها را تغییر می دهند. در این عملگرها یک یا چند محل از یک رشته کاراکتری با طول خاص در نظر گرفته شده و مقادیر کاراکترها در آن محل ها تغییر می یابند. مواردی که در این نوع مهم است عبارتند از:
تعداد محل هایی که قرار است تغییر یابند،
نحوه انتخاب محل ها،
نحوه عملیات تغییر،
با مشخص شدن موارد فوق یک عملگر خاص ایجاد می شود که به آن عملگر جهشی گفته می شود. در این نوع عملگرها از اطلاعات یک جواب استفاده کرده و جواب دیگری ایجاد می شود. این تغییر ممکن است کم یا زیاد بوده که به همان میزان از اطلاعات کم یا زیاد استفاده می شود. به عبارت دیگر هر چه تغییرات زیادتر باشد جواب حاصله تصادفی تر خواهد بود و این تصادفی بودن برای ورود مواد ژنتیکی جدید به داخل جمعیت مفید است.
وقتی که جمعیت به سمت جوابی خاص همگرا می شود، احتمال جهش باید زیاد شده تا از این عمل جلوگیری نماید و بالعکس وقتی جمعیت دارای جواب های غیر یکسان است باید احتمال جهش کم شود.
دسته بندی : علمی