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