بهینه سازی ترکیبی
بهینه سازی ترکیبی شاخه ای از بهینه سازی در ریاضیات کاربردی وعلوم کامپیوتر می باشد که مرتبط با عملیات تحقیق ،تئوری الگوریتم وتئوری پیچیده محسباتی میباشد که فصل مشترک بسیاری زمینه های شاما هوش مصنوعی ،ریضیات ومهندسی نرم افزار می باشد.الگوریتم های بهینه سازی ترکیبی نمونه هایی از مسائل را که در کل سخت پنداشته می شوند ،توسط کشف فضای راه حل معمولا بزرگ این نمونه ها حل می کند.الگوریتم های بهینه سازی ترکیبی توسط کاهش سایز موثر این فضا وکشف فضای موثر این روال را به انجام می رسانند.مطالعه ای بر تئوری پیچیدگی محاسبه ای به فعال سازی بهینه سازی ترکیبی کمک می کند.
الگوریتم های بهینه سازی ترکیبی به طور نمونه با مسائلی مرتبط هستند که 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 بخش تقسیم می شود ،یکی با محدودیت اضافه شده که متغیر بزرگتر یا مساوی عدد صحیح بعدی وبزرگتر از نتیجه میانی باشد،و یکی در جایی که این متغیر کمتر یا مساوی عدد صحیح کمتر بعدی باشد.با این روش متغیر های جدیدی در اساس با توجه به تعداد متغیر های پایه که در راه حل میانی غیر صحیح هستند معرفی می شوند اما آن هایی که با توجه به محدودیت اصلی عدد صحیح هستند.برنامه های جدید خطی بعدا با استفاده از روش سیمپلکس حل می شوند و پردازش تا وقتی که یک راه حل همه محدودیت های اعدادصحیح را بیابد ادمه پیدا می کند.در طی پروسه شعبه ومرز ،برش های صفحه ای می توانن از هم جدا شوند ،که ممکن است برش های جهانی باشند ،و برای همه راه حل های محتمل اعداد صحیح یا برش های عمومی معتبر بوده ،بدین معنا که آنها با همه راه حل های پر کننده این محدودیت ها از زیر درخت مرز .شعبه فرض شده پ.شش داده می وشند.
مسئله برش ذخیره
مسئله برش ذخیره ازبسیاری کاربردهای فیزیکی رد صنعت منشأ می گیرد .فرض کنید که شما در ماشین کاغذسازی کار میکنید،و شما مدیر بخش برش کاغذ هستید.شما تعدادی رل کاغذ با عرض معلوم دارید منتظر بریده شدن هستند ،و تولید کنندگان متفاوت نیاز به رل های کاغذ با سایز عرضی متفاوت دارند.شما چگونه می خواهید این رل ها را ببرید که کمترین هدر رفتگی کاغذ را داشته باشید؟این مورد به نظر مسئله بهینه سازی می رسد ،یا تخصصی تر ،یک مسئله برنامه نویسی خطی عدد صحیح می باشد.یک دیدگاه برای حل آن فراموش کردن بخش عدد صحیح است ،که به آن تمدد گویند.در کل حل آن بسیار آسانتر از حل مسئله برنامه نویسی خطی صحیح می باشد.یک روش برای حل مسائل خطی روش سیمپلکس یا دو تایی میباد،که ازبرخی مواردغیر بهینه آغاز می شود و متناوبا راه حل های بهتر وبهتر می یابند.الگوریتم با راه حل بهینه وقتی هیچ کاری برای اصلاح راه حل نباشد ،نتیجه گیری می کند .برای مسئله برش ذخیره فرمول استاندارد همه روش های ممکن را که ممکن است از یک رل بریده شود را به وجود می آورد.برنامه خطی تعیین می کند که چه تعداد دفعاتی هر روش استفاده می شود ،در خلال مدتی که سفارشات آماده می شوند.در کل ،تعداد روش های ممکن ،تحت تابعی از عرض های متفاوت سفارشات برای برش از رل کاغذ رشد میکند .بسته به تعداد عرض های متفاوت اگرچه ممکن است به شمار آوردن روش های ممکن دشوار باشد از این رو برنامه خطی مرتبط حل می شود.راه چاره استفاده از دیدگاه Delayed Column Generation می باشد.این روش مسئله برش ذخیره را با تعداد کمی شیوه شروع می کند.و مولد شیوه های اضافی است وقتی لازم باشند.شیوه های جدید
با حل مسئله دیگری از بهینه سازی که مسئله کوله پشتی نامیده میشود معرفی مشود.مسئله کوله پشتی دارای روش های معروفی برای حا آن میباشد ،که در میان آنها برنامه نویسی دینامیک وشعبه ومرز موجود میباشند.روش Delayed Column Generation موثر تر از دیدگاه اصلی می باشد.این روش توسط گیلمور وگوموری در یک سری از مقالات منتشر شده در سال 1960 مطرح گردیده است.روش مذکور با انتخاب یک سری شیوه های ابتدایی برای شامل شدن در مدل آغاز می شود و برنامه خطی را حل می کند.ازآنجایی که سری آغازین همان سری مورد نظر نیست ، اطلاعات متغیر دوگانه از برنامه خطی برای تولید شیوه ای جدید استفاده می شود.شیوه جدید با استفاده از مسئله کوله پشتی تولید می شود.این دو مسئله ،برنامه خطی اصلی و مسئله کوله پشتی ،در برگشت خپحل می شوند تا زمانیکه شیوه های دیگری تولید شوند که تعداد برش های رل کاغذ را کاهش دهند.یک محدودیت روش گوموری وگیلمور آن است که تمامیت را برعهده نمی گیرد ،پس راه حل ممکن است دارای کسری هایی باشد،وروش خاصی می بایست 1.67 زمان تولید شود.گردیدن به نزدیک ترین عدد صحیح اغلب کار نمی کند ،این مورد ممکن است منجر به یک راه حل
خرده بهینه یا / و تحت تولیدبرخی سفارشات گردد.این محدودیت ها در الگوریتم های مدرن از بین رفته اند ،که می توانند نمونه های بسیار بزرگی از بهینگی را حل کنند .
Greedoid
در تعداد راه های انجام یک کار ،نوعی از سیستم سری است.از اندیشه متروید بر میخیزد ،که در اصل توسط ویتنی در سال 1935 برای مطالعه گراف های سطحی معرفی شده بود وبعدها توسط ادموندز برای طبقه بندی کلاسی از مسائل بهینه سازی استفاده شده بود تا با الگوریتم های گیریدی قابل حل باشند.حدود 1980،کورتی و لوواز گریدوید را معرفی کردند تا بعدها طبقه بندی الگوریتم گیریدی را تعمیم دهند. در کنار بهینه سازی ریاصیاتی ،گریگوید همچنین با تئوری گراف ،تئوری زبان ،تئوری پوزت ،و دیگر حوزه های ریاضیات مرتبط شد.
الگوریتم گیریدی
در کل ،الگوریتم گیریدی فقط یک پروسه متناوب است که در آن بهترین مورد عمومی ،معمولا یک ورودی با کمترین وزن ،در هر دور تا وقتی که همه موارد در دسترس تحلیل رفته باشند ،انتخاب می شود.برای تشریح حالت بر پایه گیریدی که در آن یک الگوریتم گیریدی بهینه است ، ما به تعداد بیشتری اصطلاحات معمول در تئوری گیریدوید بدون کسر کلیت نیاز داریم ،ما یک گیریدوید G=(F,E) with E متناهی در نظر میگیریم.ما
همه مطلب را اینجا بحث نخواهیم کرد.درک مستقیم مطلب این است که ،در طی پروسه متناوب هر تغییر بهینه کمترین وزن توسط متعلقات تغییر ممکن می شود ،و نتایج بهینه قابل دستیابی از سری های محتمل در
گیریدوید های مشخص شده میباشد.در هر مورد ،این نتیجه ای مفید وکلی میباشد که بهینگی بسیاری الگوریتم های معروف را گارانتی می کند.مثال 5 یک گراف غیر مستقیم که در آن هر لبه توسط یک عدد حقیقی غیر منفی و متروید چرخه همراه وزن می شود .سپس کمترین پوشش جنگل ،منظور جنگلی که در برگیرنده همه
رئوس با کمترین وزن کل میباشد ،که با استفاده از الگوریتم کروسکال به دست می آید. یا ،به طور هم ارز ،ما می توانیم الگوریتم گیریدی را روی جمع وزن منفی هر سری محتمل از متروید های مشترک به کار بگیریم .