تحقیق درمورد نقطه مرجع، نمونه برداری، بهینه سازی چند هدفه

دانلود پایان نامه

نقطه غیرمسلط است. اگر و تابع قطر زیرفضای غیرمنفی برگردانده شده باشد به قسمی که . آنگاه غیر مسلط است. به شکل 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 سطوح ذخیره تابع هدف i ام می باشد. حداکثر تعداد تکرار های الگوریتم را می توان به عنوان یک شرط متوقف کننده در این مرحله تعیین نمود.
قدم دوم- نمونه برداری. یک گروه شامل 2P بردار وزنی پراکنده به شکل زیر تولید نمائید.

قدم سوم- حل. مساله چبیشف زیر را برای هر بردار وزنی حل نمائید.

که در آن ρ مقدار مثبت کوچکی می باشد. به تعداد P تا از مختلف ترین جواب ها را به تصمیم گیرنده ارائه دهید. اگر تصمیم گیرنده تمایل به ادامه جستجو برای یک پاسخ بهتر داشته باشد به قدم 4 بروید. در غیر این صورت از تصمیم گیرنده بخواهد مطلوب ترین جواب خود را برگزیند و متوقف شوید.
قدم چهارم-تنظیمات. از تصمیم گیرنده بخواهد که جواب های دردست را به دو مجموعه ارجح و غیر ارجح تقسیم بندی نماید، سطوح ذخیره را تنظیم کنید و به قدم دوم بر گردید.سطوح ذخیره را می توان به طور خودکار بتوسط روش پیشنهادی نویسندگان بهبود داد و یا مستقیم با نظر تصمیم گیرنده عوض نمود.
نویسندگان تابع کاهش فضای هدف زیر را پیشنهاد داده اند.

در این تابع و به ترتیب بدترین جواب ها برای i امین تابع هدف روی کل مجموعه پاسخ فعلی127 و بدترین جواب روی مجموعه با ارجحیت بالاتر128 می باشد. در اینجا r عامل کاهش بین صفر و یک می باشد. مقادیر کوچکتر r باعث کاهش سریعتر فضای اهداف می گردد. دامنه پیشنهاد شده برای پارامتر بین 0.0001 تا 0.01 می باشد(استیور،1986). با مشخص کردن سطوح ذخیره جدید به قدم سوم بر می گردیم.

6-5-2-5-4-سایر روش های برپایه نقاط مرجع
علاوه بر موارد ذکر شده رویکرد های دیگری بر مبنای نقاط مرجع و در چارچوب فاصله چبیشف وجود دارند که می توان از آنها در حل مسائل برنامه ریزی عدد صحیح و مختلط عدد صحیح استفاده نمود. یکی از این روش ها ثابت نگاه داشتن بردار w یا حذف آن و تغییر دادن ها یا همان نقاط مرجع می باشد که می تواند نشان دهنده سطوح تمایل129 تصمیم گیرنده باشد. این برنامه ریزی را با نشان می دهیم. همواره نقاط مرجعی وجود دارند که به ازای آنها داریم به گونه ای که یک جواب موثر خاص تولید می نماید. نقاط مرجعی که شرط را ارضا نمی نمایند را نیز می توان در نظر گرفت به شرطی که متغیر به شکل آزاد تعریف شده باشد. این امر به منظور کمینه کردن فاصله Z تا نقطه مرجع غیر شدنی و به منظور حداکثر کردن فاصله Z از نقطه مرجع شدنی می باشد. اگر نقاط مرجع یا سطوح تمایل به عنوان پارامترهای کنترل کننده استفاده شوند، فاصله (موزون) چبیشف نحوه وابستگی به پارامترهای کنترل کننده را تغییر می دهد و می بایست به عنوان یک تابع درجه بندی حصول130 تفسیر شود.
همانند ساده ترین نوع ، ساده ترین نوع ممکن است جواب های موثر ضعیف تولید نماید، اما حالت تقویت شده جایگزین کاربردی خوبی می باشد و حالت لکسیکوگراف آن می تواند حصول جواب های موثر را تضمین نماید. اطلاعات دقیق تر راجع به سیستم های کمکیار تصمیم را می توان در مقاله ارائه شده توسط ویرزبیکی131(1980) یافت.

مطلب مرتبط :   دانلود تحقیق با موضوعسرمایه اجتماعی، ساختمان ذهنی، سرمایه فرهنگی

7-5-2-5-4- نحوه ایجاد بردارهای وزنی پراکنده برای استفاده از در برنامه تعاملی
روش های گوناگونی برای تولید بردارهای وزنی پراکنده پیشنهاد شده است(استیور، 1986). در اینجا به دو مورد از مهمترین آنها با عناوین روش تولید وزن تصادفی و همچنین روش وزن های با معیار بازه ای132 ارائه شده توسط ستویر اشاره می نمائیم.
در نوع اول ایجاد بردار های وزنی از اعداد تصادفی استفاده می نمائیم و تنها می بایست دقت نمائیم که جمع بردارهای وزنی برابر یک شود. فایده این روش این است که می توانیم تعداد بی نهایت بردار وزنی متفاوت تولید نمائیم اما ممکن است با تعداد کم بردارهای وزنی تمام فضای اهداف پوشش داده نشود و اگر تعداد بردارهای وزنی ایجاد شده را زیاد کنیم حجم محاسباتی مساله بیشتر خواهد شد که مطلوبیت آن را کاهش می دهد. روش دیگری که برپایه اعداد تصادفی بوده و توسط جاشکویکز133 (1998) ارائه شده از طریق الگوریتم زیر به تولید بردار های اعداد تصادفی نرمال شده می پردازد و نتایج خوبی حاصل نموده است

در نوع دوم که روش وزن های با معیار بازه ای می باشد به شرح زیر عمل می نمائیم. فرض کنید که می خواهیم مساله ای با p تابع هدف را بهینه سازی نمائیم . با این روش می توانیم 2p+1 بردار وزنی مختلف ایجاد نمائیم. بردار های وزنی طبق روابط زیر به دست می آیند
که در آن می باشد. مشکل این روش ا
ین است که تعداد بردارهای وزنی ایجاد شده کم می باشد برای مثال برای یک مساله چند هدفه با دو تابع هدف می توان تنها 5 بردار وزنی ایجاد نمود که ممکن است بخش زیادی از فضای هدف را نتواند پوشش دهد.
3-5-4-سایر روش های تعاملی یافتن مجموعه جواب غیر مسلط در فضای غیرمحدب
روش های تعاملی دیگری برای بهینه سازی چند هدفه به منظور یافتن مجموعه جواب های پشتیبانی شده و نشده درفضای غیرمحدب در ادبیات موضوع بیان گردیده است. برای مروری کامل و جامع بر این مدل ها به کتاب ارائه شده توسط ارگات و گاندیبلکس134 (2004) و مقاله ارائه شده توسط آلوس و کلیمکائو(2000) مراجعه نمائید.

14-4- نتیجه گیری
روش های بهینه سازی چند هدفه بر پایه فاصل چبیشف در بین محققین از مطلوبیت بالایی برخوردار می باشند زیرا توانایی تولید دسته

پاسخی بگذارید