بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
حل مسئله فروشنده دوره گرد سود ده با الگوريتم تقريبي چند معياره همزمان
چکيده :حل مسئله فروشنده دوره گرد سود ده يکي از مسائل پايه اي در بهينه سازي به شمار مي آيد.اين مسئله داراي پيچيدگي سخت است .در اکثر کاربردهاي فروشنده دوره گرد سود ده ١، حل نزديک بهينه مي تواند جانشين مناسبي براي حل دقيق مسئله باشد. اين مسئله دو معيار کمترين هزينه مسير و بيشترين سود فروش در هر نود را ادغام مي کند و به دنبال کمترين هزينه مسير با کسب بيشترين سود است . روش هاي تقريبي،جواب نزديک به جواب بهينه ارائه مي دهد.پرسش تحقيق آن است که آيا مي توان الگوريتم تقريبي دو معياره براي مسائلي ارائه داد که دو هدف هزينه و سود را باهم به تعادل برسانند تا جواب نزديک بهينه يافت گردد؟دراين تحقيق طرح تقريبي براي برنامه ريزي صحيح و غير صحيح دو معياره مطرح مي گردد. در روالهاي روش پيشنهادي، يک زير مجموعه از نقاط موثر محاسبه مي گردد و اين نقاط موثر توسط هر دو معياربررسي مي گردد. اين طرح با تغييرات ساده در الگوريتم هاي کلاسيک براي ساخت زيرمجموعه نقاط کارا بکار مي رود.
در روال هاي معرفي شده يک زير مسئله تک هدفه معرفي مي گردد که در هر مرحله بايد حل گردد.در نهايت نشان خواهيم داد که هم حل زير مسئله ها و هم تعداد نقاط کارا با روش چند جمله اي و با ورودي اندازه مسئله وخطاهاي مجاز دو جانبه انجام مي گيرد. نشان داده مي شود که پردازشهاي بعدي سريع ، تعداد نقاط برگردانده شده را ضمانت مي نمايد.در ضمن نقاط کارا در حداکثر سه برابر نياز به تقريب مجموعه کارا با انحراف خاص دارد.در پياده سازي آن سودها و هزينه ها به عنوان اهداف متناقض در نظر گرفته مي شود.نتايج به طور تصادفي با دادهاي کتابخانهاي تي اس پي ليب مورد بررسي و ارزيابي قرار گرفته است .
واژگان کليدي:الگوريتم تقريبي ، فروشنده دوره گرد سود ده ،پيچيدگي سخت ، نقاط کارا
١- مقدمه
مسائل تصميم گيري در حوزه هاي کاربردي اغلب مسائل مختلفي هستند که چندين هدف متعارض با هم را برآورده مي سازند.بهبود يک يا چند هدف به بدتر شدن هدف ديگر مي انجامد.يک مبادله متناسب بين اين اهداف مي تواند تصميم گيري مناسب براي حل مسئله ارائه نمايد.روشهاي معيار چندگانه يکي از روشهاي حل مسئله چند هدفه است .[١]در اين روش ها چند هدف در غالب يک تابع هدف آورده مي شود.که حل آن ،يک حل ممکن براي مسئله را مي دهد ولي مبادله خوبي بين اهداف انجام نمي دهد.اين رويکرد طبيعي بسيار ساده انگارانه است .و قوانين جمع اوري اطلاعات در خيلي مواقع اختياري است و براي حل بهينه مناسب براي تصميم گيري مناسب نيست .در اين حالت ليست هاي کوتاه در حل هاي غير عمده اي به وجود مي آيد که اين حل ها در يک يا چند هدف بهبود خوبي پيدا نمي کند مگر اينکه يکي ديگر را خيلي بدتر نمايد.اين مورد ممکن است در فرايند تصميم گيري حمايت نا مناسبي را داشته باشد.
مسائل تصميم گيري چند هدفه به اختصار موکو٣ ناميده مي شود.نمونه خاصي از موکو ،مسائل تصميم گيري دوهدفه و به اختصار بوکو٤ناميده مي شود.اين مسائل فقط دو هدف متعارض با هم را براي تصميم گيري در نظر مي گيرند.[٢]تحقيق حاضر روي مسائل تصميم گيري دو هدفه متمرکز مي شود.
Min f(x)
Min g(x)
Subject to xϵX
X ناحيه امکان پذير است که توسط محدوديتهاي در مدل برنامه ريزي معرفي مي شود.و xεX يک حل امکان پذير است . ,f gتوابع هدف محدود هستند و ارزش صحيح نامنفي دارند.
2 حل مسائل دو هدفه با دو هدف متناقض مورد اهميت متخصصين در دهه اخير است . عدوني و شيرازي حل مسائل با دو هدف متناقض را مورد بررسي قرار دادند و با محدود کردن محدوديتها به حل مسائل دو هدفه پرداختند.[٣]
پيچيدگي الگوريتم هاي تقريبي براي حل مسئله فروشنده دوره گرد سود ده براي داده هاي زياد بالا است و پيچيدگي زماني با کاهش پيچيدگي تقريب بالا مي رود.[٥][٤]
ماکزيمم مسيرفروشنده دوره گرد و بسياري از الگوريتم هاي ديگر از روشهاي بهينه سازي ترکيباتي دو هدفه استفاده مي نمايند.[٧][٦]
روشهاي تصادفي و فرامکاشفه اي نيز روش هاي تقريبي مناسبي را ارائه مي دهند.ولي همگرايي قطعي در تقريب را تضمين نمي نمايند. [٩][٨].
روشهاي مختلف بهينه سازي ترکيباتي دو هدفه و چند هدفه در مسئله فروشنده دوره گرد سود ده و اصلاحات براي تقريب بهتر، هنوز مورد اهميت فراوان در اين حوزه تحقيق مي باشد.[١٠]
٢- معرفي موضوع تحقيق
يکي از روشهاي حل مسئله فروشنده دوره گرد سود ده ، استفاده از مدل برنامه ريزي خطي بوکو است .در مدل برنامه ريزي خطي بوکو ،انواع حل هاي پارتو ، کارا، قابل پذيرش تعريف مي گردد . همچنين جهت الگوريتم هاي تقريبي ،شاخص تقريب پارتو معرفي مي شود.در ادامه به معرفي اين متغيرها و شاخص ها پرداخته مي شود و در ادامه تعريف دقيق مسئله فروشنده دوره گرد سودده مورد بررسي قرار مي گيرد.
٢-١-حل پارتو
در بوکو يک حل نبايست طوري باشد که همزمان دو هدف را به طور کامل مي نيمم نمايد.يک حل امکان پذير x يک بهينه پارتو است اگر حل امکان پذير 'x وجود نداشته باشدکه شرايط زير برقرار باشد.[١]
٢-٢- مجموعه نقاط کارا
مجموعه کارا مجموعه اي از نقاط پارتو است .اگر x حل بهينه پارتو باشد واين حل با شرط وجود داشته باشد آنگاه x يک نقطه کارا است .مجموعه کارا مجموعه اي از نقاط کارا است که شروط بالا در آن برقرار باشد.[١]
.٢-٣- نقاط قابل پذيرش
يک نقطه قابل پذيرش است اگر براي حل هاي ممکن xεX باشد.همچنين يک نقطه کارا است .و نقاط قابل پذيرش يک تقريب ε-appr از مي باشد.اگردوشرط زير برقرار باشد:
٢-٤- تقريب پارتو
EεR2 مجموعه نقاط قابل پذيرش ε-apprاست .اگر براي هر يک وجود داشته باشد.ما انتظار داريم که ε-appr از Eرابطه زير برقرار باشد
پس هر تقريب پارتو يک مجموعه نقاط کارا است که مجموعه ε را تشکيل مي دهد.و ε يک تقريب از خودش است و همچنين يک تقريب است .[١]
٢-٥-تعريف مسئله فروشنده دوره گرد سود ده
دريک گراف بدون جهت کامل با n نودکه هر نود يک سود آوري دارد.هدف پيدا نمودن مسير فروشنده دوره گرد با کمترين هزينه يال و ماکزيمم کردن سود نودها هستيم .که دو هدف کمترين هزينه مسير و سودآوري نودها با هم در تعارض مي باشند.که نمايانگر کوتاهترين مسير هاميلتون و نمايانگر حداکثر سود نودها در مسير فروشنده دوره گرد است .فرم دو هدفه برنامه ريزي خطي صحيح آن به شرح زير است .[٤]
Xe انتخاب يالهاي مسير فروشنده دوره گرد سود ده را نمايش مي دهد.که دو مقدار يک (انتخاب يال ) يا صفر (عدم انتخاب يال ) را نشان مي دهد. و yi نمايش انتخاب نودهاي با دو مقدار صفر و يک است . محدويت اول نشان مي دهد اگر نودي انتخاب مي شود و در صورت انتخاب متغير درجه آن ٢ و گرنه متغير درجه آن صفر است . و در ضمن نود حداکثر يکبار انتخاب مي شود. اين نشان مي دهد که هيچ زير توري نبايد از ميان نودهاي ملاقات شده انتخاب گردد.مدل مطرح شده يک مدل بوکو هست زيرا اگر ماکزيمم تابع هدف دوم در يک منفي ضرب شود و به جاي تابع هدف دوم قرار گيرد.مسئله به مدل استاندارد بوکو تبديل مي شود.واضح است که مي نيمم کردن منفي تابع هدف دوم معادل ماکزيمم کردن تابع هدف دوم است .[١]
٣- کارهاي انجام شده و ايده يابي براي روش جديد
يک نمود مهم از مسائل موکو آن است که نگاشت ε به صورت نمايي با اندازه ورودي مسئله رشد مي کند.در اين حالت محدوديتها نيز به خاطر معيارهاي چندگانه با اندازه مسئله به طور نمايي رشد پيدا مي نمايد.اين نکات در بسياري از مسائل مثل فروشنده دوره گرد سود ده مشخص است .به منظور کاهش پيچيدگي زماني تعدادي از روشهاي مختلف مکاشفه اي و فرامکاشفه اي در دهه هاي اخير گسترش پيدا کرده اند.اين روش ها مبادله خوبي بين زمان اجرا و حل تقريبي مي دهد.وليکن اين حل ها به نقاط اوليه حل و تابع فرامکاشفه اي وابسته است .و تضمين تقريب را به صورت دقيق و مناسب ضمانت نمي کنند.ضمانت مناسبي نظري براي فاصله بين نقاط محاسبه شده در تابع هدف و نقاط کارا دقيق را ارائه نمي دهندبا توجه به مناسب نبودن الگوريتم هاي فرا مکاشفه اي در تقريب مناسب و نظر به تغييرات در الگوريتم هاي کلاسيک اين ايده به وجود آمد که بررسي همزمان دو هدف باعث مي گردد تقريب مناسب داشته باشيم و در ضمن با بهبود يک هدف آن هدف ديگر خيلي بدتر نشود.ABE الگوريتمي است به طور تکراري هر نقطه کارا را بررسي مي کند و با ٤ قسمت کردن ناحيه توسط نقطه کارا دو ناحيه مناسب که براي بازرسي آينده مورد نياز است
،را مشخص مي نمايد.به اين ترتيب ناحيه هاي کوچکتر مورد بررسي قرار مي گيرد اين تقسيم بندي ناحيه با تقريب ε در ناحيه هاي خاص هدف به تمام مي رسد.که ممکن است شامل فقط نقاطي باشدکه تقريب هاي يک محاسبه قبلي هستند.الگوريتم CBE يک تغييرات ساده به منظورتغييرات همزمان دو هدفه در الگوريتم کلاسيک محدوديت جزيي مي دهد.
شکل ١: ايده يابي براي طرح جديد
٤- ارائه روش جديد
٤-١-معرفي روش قديم ABE
روال روش ABEيک جستجوي دودويي است که ناحيه هاي خاص را از فضاي هدف بررسي مي کندو از طريق آن محدوديتها، جستجو را محدود مي نمايندوزير ناحيه ها معرفي مي شوند. اين مجموعه داده هاي کارا را مي دهد.روش BE روش دقيقي است که از روش محدوديت جزيي پايدارتر است .ABE با توسعه روش BE محدوديتها را قوي تر نموده و به جستجوي نقاط کارا مي پردازد .که نقاط تقريبي را به دست مي آورد .در اينجا مي خواهيم مدل بوکو را حل کنيم که مي توان همزمان دو تابع هدف f و g را مي نيمم کرد.براي همين مجموع توابع f,g را مي نيمم مي کنيم که محدوديتهايي نيز دارد .هر تابع يک کران ماکزيمم با تقريب دارد.اين مسئله را P مي ناميم .[١٠]
براي حل مسئله مينيمم همزمان fو g براي اين کار ابتدا دو نقطه اوليه را در نظر مي گيريم .که اولين نقطه φ را ارضا نمايد و σ را مي نيمم نمايد و دومين نقطه σ را ارضا نمايدوφ را مينيمم کند. اين دو نقطه اوليه را مجموعه جواب اوليه در نظر مي گيريم .و انها را يکي يکي برداشته و در محدوديتها تست مي کنيم و اگر برقرار بود به مجموعه جواب اضافه مي کنيم .اين نقطه با کرانهاي قبلي چهار ناحيه مي سازد که دو ناحيه آن امکان پذير در محدوديتهاي مسئله نيست و دو ناحيه ديگر نيز بايد مثل روش بالا مورد بررسي قرار گيرد تا اين ناحيه هاي قسمت بندي شده کل ناحيه جواب را بپوشاند .اين ناحيه ها با تقريب محدوديت معرفي شده تقسيم بندي شده و مسائل جديد از نوع مسئله P ساخته مي شود و الگوريتم تا زماني که کل ناحيه مورد بررسي قرر بگيرد، ادامه مي يابد. در شکل ٢ زير حوزه هاشور تيره خورده شده خارج از فضاي جواب است .و محدوده نقطه چين مجموعه فضاي نقاط کارا را نشان مي دهد.
شکل ٣ توليد زير مسئله ها را نمايش مي دهد.[١٠]
