از روی شکل توضیح داده خواهد شد.
4-4- تشخیص بردار های اهداف غیر مسلط از روی شکل
فضای R+ را زیر فضای غیرمنفی فضای Rk در نظر بگیرید.برای اینکه از روی شکل مشخص نمائیم که آیا یک مسلط است یا غیر مسلط، R+ را بر روی برگردانید. با این کار مجموعه ای به نام زیرفضای غیرمنفی برگردانده شده116 روی به وجود می آوریم و آنرا با نشان می دهیم که علامت جمع کراندار نشان دهنده جمع مجموعه ها در نظر گرفته شده است. بردار اهداف غیر مسلط است اگر و تنها اگر اشتراک و فضای شدنی اهداف Z ، تنها شامل نقطه باشد. .
در برنامه چند هدفه عدد صحیح نشان داده شده در شکل 4-4 داریم و . برای مثال، z3 غیر مسلط است زیرا اگر یک داشتیم که بر این جواب مسلط بود، می بایست داخل زیرفضای غیرمنفی برگردانده شده روی z3 قرار می گرفت. از طرف دیگر، z5 تحت تسلط است زیرا z6 درزیرفضای غیرمنفی برگردانده شده روی آن واقع شده است.
شکل 4-4- فضای اهداف گسسته
در شکل 5-4 ، مجموعه غیر مسلط را با نمایش می دهیم که منظور از bls پاره خط مرزی117 در جهت گردش عقربه های ساعت از نقطه z1 به نقطه z2 می باشد. در شکل z4 غیرمسلط است و z3 تحت تسلط می باشد.
شکل 5-4- یافتن نقاط غیر مسلط در فضای اهداف پیوسته
در شکل 6-4 که یک فضای غیر خطی را نشان می دهد ، مجموعه غیرمسلط برابر است با:
که پرانتز های باز نشان دهنده این است که نقاط حدی مربوطه در داخل مجموعه نیستند.
شکل 6-4- یافتن نقاط غیر مسلط در فضای اهداف غیر خطی
5-4-روش های پایه یافتن مجموعه جواب غیرمسلط در مسائل مختلط عدد صحیح
همانطور که بیان شد،از آنجا که فضای تصمیم یک مساله بهینه سازی مختلط عدد صحیح غیر محدب است صلاح نیست از روش های مبتنی بر جمع موزون اهداف به شکل استفاده نمود زیرا از یافتن پاسخ های غیر مسلط پشتیبانی نشده عاجز می باشند. محققین از سال های دور به این مطلب پی برده اند و به طور کلی دو روش پایه جهت یافتن مموعه جواب غیر مسلط در مسائل مختلط عدد صحیح پیشنهاد شده است (آلوس و کلیماکو، 2004)
1-5-4- برنامه ریزی مجموع موزون با محدودیت های اضافی
در این روش محدودیت هایی به مساله اضافه می شود. این محدودیت ها حدودی را روی مقادیر تابع هدف تحمیل می کنند. این امر باعث می شود برنامه مجموع موزون پاسخ های موثر پشتیبانی نشده را نیز بدست بیاورند. این برنامه مدرج شده را می توان به شکل زیر نمایش داد:
که در آن بوده و g یک بردار سطری از حدود اهداف می باشد.
علاوه بر این که هر جوابی که از حل به دست می آید موثر است، همواره یک وجود دارد که به ازای آن یک جواب موثر خاص تولید می کند.
2-5-4- برنامه ریزی بر مبنای نقطه مرجع
تئوری چبیشف ارائه شده توسط بومن118 (1976) می تواند رویکرد دیگری برای حل در اختیار ما بگذارد .با استفاده از این تئوری می توان به تولید یک مجموعه جواب غیر مسلط ( پشتیبانی شده یا نشده) در فضای اهداف پرداخت.
1-2-5-4- نقطه مرجع
فرض کنید K=1،…،k و یک بردار معیار مرجع باشد که المان های آن برابر است با :
و در آن می بایست اپسیلون مقدار کوچکی انتخاب شود. برای راحتی می توان اپسیلون را کوچکترین عددی انتخاب نمود که به اضافه آن عدد، برابر یک عدد صحیح می شود. منطقه قسمت پائین و چپ نقطه مرجع را دامنه مساله می نامیم. در شکل 7-4 منطقه داخل خط چین ها دامنه مساله می باشد.
2-2-5-4-فاصله چبیشف
برای محاسبه فاصله بین و، می توان از معیار چبیشف موزون استفاده نمود
که در آن اولا داریم و ثانیا به همراه هر معیار چبیشف موزون یک اشعه کاوشگر119 که از در جهت پائین با ضرائب ساطع می شود وجود دارد. خطوط تراز 120 معیار چبیشف موزون یک دسته مستطیل به مرکز نقطه مرجع شکل می دهند. علاوه بر این، در دامنه مساله، قطرهای تمامی مستطیل ها همان اشعه کاوشگر می باشد. در شکل 7-4 که اشعه کاوشگر در جهت می باشد، مستطیل ها همان خطوط تراز معیار چبیشف موزون با بردار وزنی هستند که از نقطه مرجع ساطع می شوند. با این معیارz1 نزدیک ترین گزینه به نقطه مرجع است زیرا در کوچکترین مستطیل قرار می گیرد. توجه شود که با تغییر بردار وزنی، جهت اشعه کاوشگر را تغییر داده در نتیجه شکل مستطیل های تراز نیز تغییر می کند .
شکل 7-4- فاصله چبیشف و خطوط تراز
3-2-5-4- بردارهای ?-موزون راس-T 121
توجه کنید که در برخی موردها، چندین بردار وزن ? می توانند در برنامه موزون چبیشف نقطه غیرمسلط یکسانی را حاصل نمایند. با وجود این، یکی از همه این بردارهای وزنی به نام بردار وزنی راس-T ویژگی خاصی دارد. این بردار وزنی برداریست که موجب میشود راس کوچکترین خط تراز تداخل کننده به نقطه ای خاص برخورد نماید. برای یک نقطه خاص و نقطه مرجع، این بردار وزنی از رابطه زیر حاصل می شود
4-2-5-4- نقاط روی کوچکترین خطوط تراز
تا زمانی که نقطه روی کوچکترین خط تراز مماس یکتا باشد، نقطه غیرمسلط است. اگر و تابع قطر زیرفضای غیرمنفی برگردانده شده باشد به قسمی که . آنگاه غیر مسلط است. به شکل 8-4 دقت نمائید.
شکل 8-4- نقاط روی کوچکترین خط تراز مماس
قابل ذکراست که اگر بیش از یک نقطه روی کوچکترین خط تراز مماس قرار بگید ( مانند شکل 9-4) آنگاه طبق نظریه ارائه شده توسط استیور و چو، تنها یک نقطه غیرمسلط بوده و باقی نقاط روی خط تراز مماس طبق تعریفی که قبلا اشاره شد غیرمسلط ضعیف می باشند.
شکل 9-4- وجود بیش از یک نقطه روی خط تراز برخورد کننده
اگر مجموعه نقاط روی کوچکترین خط تراز مماس را با نشان دهیم نظریه زیر بیان می دارد که حداقل یک نقطه در آن غیر مسلط می باشد.
نظریه – یک نقطه غیرمسلط است اگر نقطه ای در باشد که با توجه به یک معیار L1 نزدیک تر به نقطه مرجع باشد.
5-2-5-4-انواع روش های بهینه سازی بر پایه فاصله چبیشف
بومن نشان داد که در یک مساله بهینه سازی چند هدفه ، اگر فاصله موزون چبیشف را به شکل معادل زیر نشان دهیم که که درآن نشان دهنده نقطه مرجع از فضای اهداف می باشد
آنگاه برای همه پاسخ ها متعلق به فضای شدنی مساله می توان با انجام عملیات پارامتری سازی روی پارامتر w از تابع تمام مجموعه جواب موثر را بدست آورد.
1-5-2-5-4-برنامه ریزی تقویت شده موزون بر اساس فاصله چبیشف
باید توجه داشت که می تواند جواب های موثر ضعیف نیز تولید بنماید که می توان توسط برنامه ریزی تقویت شده موزون بر اساس فاصله چبیشف از این امر احتراز نمودکه آنرا به شکل زیر نمایش می دهند
که در آن یک عدد مثبت بسیار کوچک است. این فرمولاسیون را می توان به شکل زیر نوشت:
استیور و چوو122(1983) ثابت کردند که همواره می توان یک به قدر کافی کوچک پیدا کرد که به تمام مجموعه جواب های موثر برای حالات دارای فضای جواب چند وجهی محدود و گسسته دست یافت.
با وجود این اگر حالت مختلط عدد صحیح را در نظر بگیریم ممکن است بخش هایی از مجموعه جواب موثر ( که نزدیک به جواب های موثر ضعیف می باشند) موجود باشند که حتی اگر بسیار کوچک باشند قادر به محاسبه آنها نیست. اما به هر حال می توان همواره یک به قدری کوچک انتخاب کرد که تصمیم گیرنده بین جواب های موثر ضعیف حاصل و جواب های کاملا موثر تفاوت قابل فهمی مشاهده نکند.
2-5-2-5-4-برنامه ریزی لکسیکوگراف موزون چبیشف
استیور و چو (1983) یک برنامه ریزی لکسیکوگراف موزون بر اساس فاصله چبیشف برای قلبه بر این مشکل ارائه دادند. با توجه به قابلیت معیار چبیشف موزون برای تولید بردارهای اهداف غیرمسلط، برنامه ریزی لکسیکوگراف موزون چبیشف ارائه گردیده است. در مرحله اول، یعنی مجموعه نقاط در فضای اهداف که با توجه به معیار موزون چبیشف ( با بردار وزنی ?) به نقطه مرجع نزدیکتر می باشند محاسبه می گردد. اگر تنها شامل یک نقطه باشد، آن تک نقطه غیر مسلط می باشد. در صورتی که بیش از یک نقطه در آن باشد، مرحله دوم برای پیداکردن نقطه ای در که به نقطه مرجع نزدیک تر است وارد محاسبات می شود. با وارد کردن این مفاهیم به یک مساله بهینه سازی، به برنامه ریزی دو مرحله ای لکسیکوگراف موزون چبیشف دست می یابیم.
این روش برنامه ریزی نه تنها یک بردار اهداف غیرمسلط، بلکه تصویر آن در فضای تصمیم یعنی یک بردار پاسخ موثر تولید می نماید. توجه شود که مرحله اول به کمینه کردن مقدار عددی ? برای اجرای معیار چبیشف موزون پرداخته و مرحله دوم، هنگامی که وارد می شود، مقداررا برای اجرای معیار کمینه می کند. به این مساله یک مساله “نمونه برداری123” هم گفته می شود زیرا بدین طریق با استفاده از گروهی از وزن های پراکنده و استفاده از روش برنامه ریزی اشاره شده، به رویکردی برای نمونه برداری نقاط از N دست می یابیم.
3-5-2-5-4- روش چبیشف تعاملی
استیور(1986) یک روش چبیشف تعاملی ارائه می دهد که در آن بجای اینکه در هر مرحله تنها یک جواب تولید کنیم، چندین اشعه را به منظور نمونه برداری زیرمجموعه های کوچک و کوچک تری از N به کار می گیریم. اگر P را تعداد جواب هایی که به تصمیم گیرنده در هر مرحله ارائه می شود در نظر بگیریم، با انتخاب P بردار وزنی پراکنده شروع می کنیم تا گروهی از اشعه های کاوشگر پراکنده همانند شکل زیر بدست آوریم. سپس برنامه ریزی موزون چبیشف را برای هرکدام از وزن های تولید شده حل می کنیم . با استفاده از P بردار هدف غیرمسلط بدست آمده، تصمیم گیرنده آن جوابی که به نظرش از همه ارجح تر می آید را انتخاب می نماید. فرض کنید این جواب را با نشان دهیم. حال با استفاده از بردار راس- T حاصل از کاربرد نقطه و نقطه مرجع، یک زیرمجموعه کاهش یافته بدست می آوریم. حال P بردار پراکنده وزنی از بدست می آوریم تا یک مجموعه متمرکز تر از اشعه های کاوشگر همانند شکل زیر بدست آوریم . سپس مدل چبیشف لکسیکوگراف برای هرکدام از آنها حل می شود. تصمیم گیرنده از P جواب حاصل شده مقبول ترینش را انتخاب می نماید و آنرا با نشان می دهیم. حال دوباره با استفاده از بردار وزنی راس-T حاصل از این نقطه و نقطه مرجع یک زیرمجموعه کاهش یافته جدید بدست می آید و این روند ادامه می یابد تا زمانی که تصمیم گیرنده به مقبول ترین جواب خود برسد. شکل های این روند را به تصویر می کشند.
شکل 10-4-اشعه های کاوشگر پراکنده
شکل 11-4- اشعه های جستجو گر متمرکز شده
سایر روش های تعاملی برپایه معیار چبیشف بتوسط استویر و چو(1983)،کارایوانوا و همکاران124(1993)و(1995)، واسلیف و نارولا125(1993)، ریوس و مک لوید126(1999) و آلوس و کلیماکو(1999)و(2000) ارائه گردیده اند. از میان آنها روش ریوس و مک لوید را به دلیل کاربردی بودن آن در ادامه معرفی می نمائیم.
5-5-2-5-4-روش تعاملی سطوح ذخیره بر پایه فاصله چبیشف
یک روش جایگزین برای کاهش مجموعه جواب های غیرمسلط حاصل از روش چبیشف، رویکرد برپایه سطوح ذخیره در فاصله چبیشف می باشد که توسط ریوس و مک لوید ارائه گردیده است. این روش از سطوح ذخیره حاصل شده از پاسخ های تصمیم گیرنده برای کاهش فضای اهداف استفاده می نماید. این روش انعطاف پذیر تر از روش های تعاملی دیگر بوده و پاسخ هایی با همان کیفیت بالا تولید می نماید. قدم های این الگوریتم به شرح زیر می باشند.
قدم اول- شروع. انتخاب تعداد پاسخ ها،P ، که می بایست به تصمیم گیرنده در هر تکرار ارائه شود که این تعداد باید بیشتر از تعداد توابع هدف باشد. سپس به محاسبه یک بردار اهداف مرجع بپردازید به نحوی که
و ها اعداد مثبت کوچکی می باشند. مقادیر سطوح ذخیره را برابر قرار بدهید که RLi سطوح ذخیره تابع هدف

این مطلب رو هم توصیه می کنم بخونین:   منابع پایان نامه درموردTechnology
دسته‌ها: No category

دیدگاهتان را بنویسید