لینک پرداخت و دانلود در "پایین مطلب"
فرمت فایل: word (قابل ویرایش و آماده پرینت)
تعداد صفحات:23
بهینه سازی ترکیبی
بهینه سازی ترکیبی شاخه ای از بهینه سازی در ریاضیات کاربردی وعلوم کامپیوتر می باشد که مرتبط با عملیات تحقیق ،تئوری الگوریتم وتئوری پیچیده محسباتی میباشد که فصل مشترک بسیاری زمینه های شاما هوش مصنوعی ،ریضیات ومهندسی نرم افزار می باشد.الگوریتم های بهینه سازی ترکیبی نمونه هایی از مسائل را که در کل سخت پنداشته می شوند ،توسط کشف فضای راه حل معمولا بزرگ این نمونه ها حل می کند.الگوریتم های بهینه سازی ترکیبی توسط کاهش سایز موثر این فضا وکشف فضای موثر این روال را به انجام می رسانند.مطالعه ای بر تئوری پیچیدگی محاسبه ای به فعال سازی بهینه سازی ترکیبی کمک می کند.
الگوریتم های بهینه سازی ترکیبی به طور نمونه با مسائلی مرتبط هستند که NP-hard هستند.اینگونه مسائل
در کل به طور موثر حل شدنی به نظر نمی رسند. اگرچه ،شباهت های متنوعی ازتئوری پیچیدگی پیشنهاد می دهند که برخی نمونه ها از این مسائل می توانند موثرا حل شوند.این در واقع خود مسئله است ،و چنین نمونه هایی اغلب دارای انشعابات کاربردی مهمی هستند.
تشریح غیر رسمی
دامنه بهینه سازی ترکیبی مسائل بهینه سازی می باشند در جایی که سری راه حل های محتمل گسسته باشند و
قابل کاهش به عنوان جدای دیگری باشند ،وهدف یافتن بهترین راه حل ممکن می باشد.
تشریح رسمی
یک نمونه از مسئله بهینه سازی ترکیبی می تواند از راه رسمی به عنوان چند تایی (X,P,Y,f,extr)
درجاییکه
- X فضای راه حل می باشد.(f and p تشریح شده اند)
- P امکان مسندی بودن است
- Y سری راه حل های محتمل می باشد.
- F تابع هدف می باشد.
- Extr حد نهایی می باشد(معمولا کمینه یا بیشینه است).
مسائل نمونه
- مسئله فروشنده دوره گرد
- مسئله کمینه درخت پوشا
- برنامه نویسی خطی
- معمای هشت ملکه
- مسئله کوله پشتی
روش ها
روش های جستجوی ابتکاری (الگوریتم های فوق ابتکاری )همان گونه که در زیر لیست شده اند برای حل مسائل از این نوع استفاده شده اند :
- جستجوی عمومی
- بازپخت شبیه ساخته
- بازپخت کوانتومی
- GRASP
- هوش انبوه
- جستجوی تابو
- الگوریتم های زنتیک
- بهینه سازی کلنی مورچه ها
- جستجوی دوباره فعال شده
مسئله واگذاری
مسئله واگذاری یکی از مسائل بهینه سازی ترکیبی ابتدایی در شاخه بهینه سازی یا جستجوی عملکردها در ریاضیات می باشد.. شامل یافتن بیشینه وزنی که در گراف هم بازی هم وزنی می شود.
در فرم کلی ،مسئله این چنین دنبال می شود:
تعدادی عامل ومسئولیت وجود دارد.هر عامل می تواند هر کدام از وظایف را انجام دهد،که
در بردارنده مقداری هزینه است که ممکن است بسته به وظایف آنها تغییر کند.مورد نیاز است
مقاله درباره بهینه سازی ترکیبی
