یکی از تفاوت‌های برجسته بین بهینه‌سازی تک‌هدفی و چند‌هدفی این است که در بهینه‌سازی چند‌هدفی، توابع هدف، علاوه بر یک فضای متغیر تصمیم معمول، یک فضای چند بعدی را ایجاد می‌کنند. این فضای چند بعدی، فضای هدف نامیده می‌شود. به ازای هر جواب در فضای تصمیم، نقطه‌ای در فضای هدف وجود دارد که با f(X)=Z=(z1,z2,…,zM) نشان داده می‌شود. نگاشت بین یک بردار جواب و یک بردار هدف صورت می‌گیرد. بهینه‌سازی چند‌هدفی، گاهی اوقات به عنوان بهینه‌سازی برداری مطرح می‌شود، زیرا به جای یک هدف، به بهینه‌سازی برداری از اهداف پرداخته می‌شود.
یک جواب نامغلوب، به جوابی گفته‌می‌شود که جواب‌های دیگر را پوشش دهد ولی خود توسط سایر جواب‌ها، پوشش‌داده نشود. یک جواب بهینه پارتو، جواب‌هایی در فضای شدنی هستند که اجزای بردار هدف آنها باهم نمی‌توانند بهبود یابند و بهبود در یکی از اهداف باعث بدتر شدن مقادیر سایر اهداف می‌شود و در نتیجه یک جواب مناسب، جوابی است که عملکرد قابل قبولی را نسبت به همه اهداف داشته باشد. به عبارتی، اگر همه‌ی اهداف به یک میزان اهمیت داشته باشند، هیچ یک از جواب‌های این مجموعه با توجه به همه‌ی اهداف از دیگری بهتر نیستند. به همه این جواب‌ها، جواب‌های مرغوب یا موثر گویند. بنابراین، اگر اطلاعات اضافی در مورد مساله در دسترس نباشد، ترجیح یک جواب بر جواب‌های دیگر این مجموعه مشکل است (در غیاب هر‌گونه اطلاعات بیشتر همه جواب‌های پارتو از اهمیت یکسانی برخوردارند). قابل ذکر است که در صورتی که اهداف متضاد نباشند، مجموعه بهینه پارتو، تنها در برگیرنده یک جواب بهینه است. به عبارتی، شماره‌ی مجموعه بهینه پارتو برابر یک است و این بدین معنی است که یک جواب کمینه برای همه توابع هدف وجود دارد. پیچیدگی دیگر این است که بهینه‌سازی چند‌هدفی به جای یک فضای جستجو، دو فضای جستجو دارد، که علاوه بر فضای متغیر تصمیم شامل فضای هدف نیز هست. در برخی از الگوریتم‌ها، پیشروی در فضای هدف می‌تواند در راستای هدایت جستجو در فضای متغیر تصمیم مورد استفاده قرار‌گیرد.
( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
تعریف تابع هدف محدب
یک مسأله بهینه‌سازی چند‌هدفی محدب است، اگر همه توابع هدف و فضای شدنی آن محدب باشد. براساس این تعریف، یک مساله برنامه‌ریزی خطی چند‌هدفی، یک مسأله محدب است. چون یک مسأله بهینه‌سازی دارای دو فضا (فضای هدف و فضای متغیر تصمیم)، است، تحدب در هر فضا برای یک الگوریتم بهینه‌سازی چند‌هدفی مهم است. هم‌چنین، این امکان وجود دارد که فضای جستجو نامحدب باشد، در حالی که فضای بهینه-پارتو محدب است.
تفاوت بهینه‌سازی چند‌هدفی با بهینه‌سازی تک‌هدفی
به غیر از داشتن اهداف چندگانه، تفاوت‌های بنیادی دیگری بین بهینه‌سازی تک‌هدفی و چند‌هدفی به صورت زیر وجود دارند.
چند هدف به جای یک هدف
مواجهه با دو فضای جستجو
فقدان حدود ساختگی
الف- چند هدف به‌جای یک هدف
در بهینه‌سازی تک‌هدفی، یک هدف وجود دارد (جستجو برای یک جواب بهینه). اگرچه فضای جستجو، ممکن است دربرگیرنده چندین جواب بهینه موضعی باشد، هدف همیشه یافتن جواب بهینه سراسری است. در مجموع، هدف اغلب الگوریتم‌های بهینه‌سازی تک‌هدفی یافتن جواب یگانه‌ای است، حتی هنگامی که چند جواب بهینه وجود دارند. در یک الگوریتم بهینه‌سازی تک‌هدفی، هرگاه یک جواب جدید مقدار تابع هدف بهتری از یک جواب قبلی داشته باشد، جواب جدید پذیرفته می‌شود.
در بهینه‌سازی چند‌هدفی، پیشرفت در جهت طرح بهینه پارتو، هدف بسیار مهمی است. ضمناً، داشتن مجموعه جواب‌های گوناگون در طرح نامغلوب نیز حیاتی است. الگوریتمی که مجموعه محدودی از جواب‌ها را از طرح بهینه پارتو برمی‌گزیند، هدف اول یعنی همگرایی در طرح بهینه پارتو را برآورده‌می‌سازد، لیکن موجب فراهم آمدن چگالی و تنوع در مجموعه حاصل نمی‌شود. از آن‌جا که در یک بهینه‌سازی چند‌هدفی، همه اهداف با اهمیت هستند، مجموعه گوناگونی از جواب‌ها بدست آمده که مربوط به طرح بهینه-پارتو هستند، تنوعی را در جواب‌های بهینه ایجاد می‌کنند که هریک، اهداف را به طور متفاوتی برآورده می‌سازند.
ب- مواجهه با دو فضای جستجو
پیچیدگی دیگر این است که بهینه‌سازی چند‌هدفی به جای یک فضای جستجو، دو فضای جستجو دارد. در یک بهینه‌سازی تک‌هدفی تنها یک فضای جستجو (فضای متغیر تصمیم) وجود دارد. در این فضا، یک الگوریتم، با پذیرش یا رد جواب‌ها بر حسب مقدار تابع هدف آنها عمل‌می‌کند. در بهینه‌سازی چند‌هدفی، علاوه بر فضای متغیر تصمیم، فضای هدف یا معیار نیز وجود دارد. اگرچه این دو فضا با یک نگاشت یگانه با یک‌دیگر مرتبط هستند، این نگاشت در اغلب موارد، غیر‌خطی است و ویژگی‌های جستجو شبیه به‌هم نیستند. برای مثال مجاورت دو جواب در یک فضا به معنی مجاورت آنها در فضای دیگر نیست. بنابراین، اگرچه نیل به هدف دوم، برقراری پراکندگی در مجموعه جواب‌های بدست آمده است، تصمیم گیری در خصوص اینکه پراکندگی در کدام فضا ایجاد شود نیز اهمیت شایانی دارد.
در هر الگوریتم بهینه‌سازی، جستجو در فضای متغیر تصمیم صورت می‌گیرد. به هر حال جریان پیشروی یک الگوریتم در فضای متغیر تصمیم می‌تواند به فضای هدف، کشانده شود. در بعضی از الگوریتم‌ها، از پیش‌روی‌های حاصل در فضای هدف می‌تواند برای هدایت جستجو در فضای متغیر تصمیم مورد استفاده شود. هنگامی که چنین چیزی اتفاق‌می‌افتد، پیش‌روی‌ها در هر دو فضا باید به طریقی هماهنگ شوند، که ایجاد جواب‌هایی جدید در فضای متغیر تصمیم، معرف پراکندگی مورد نیاز در فضای هدف باشند. این امر، به هیچ وجه، کار ساده ای نیست و مهم‌تر اینکه به نگاشت بین متغیرهای تصمیم و مقادیر تابع هدف بستگی دارد.
ج- فقدان حدود ساختگی
بسیاری از مسایل دنیای واقعی به طور طبیعی به عنوان مسایل بهینه‌سازی چند‌هدفی مطرح می‌شوند. در گذشته، به دلیل فقدان ابزارهای مناسب برای حل مسایل چند‌هدفی، طراحان مجبور به ابداع حدود ثابت ساختگی شده‌بودند. در میان این روش‌ها، روش مجموع موزون و روش -محدودیت، به طور رایجی استفاده می‌شدند. در روش مجموع موزون، اهداف موزون، برای تشکیل تابع هدف مرکب با یک‌دیگر جمع‌می‌شوند. بهینه‌سازی این تابع مرکب منجر به بهینه‌سازی توابع هدف منفرد می‌شود. متأسفانه جواب یک چنین استراتژی بهینه‌سازی، به وزن‌های انتخاب شده بستگی دارد. روش دوم، یکی از توابع هدف را برمی‌گزیند و بقیه اهداف را به عنوان محدودیت‌هایی در محدوده حدود از پیش تعیین‌شده قرارمی‌دهد. حدود ثابت ساختگی نیز یک مسأله بهینه‌سازی چند‌هدفی را به یک مسأله بهینه‌سازی تک‌هدفی تبدیل می‌کند. متأسفانه، اینجا نیز، جواب‌های بهینه‌سازی تک‌هدفی همراه با محدودیت، بستگی به حدود انتخاب‌شده برای محدودیت‌ها دارد. بهینه‌سازی چند‌هدفی، برای یافتن جواب‌های بهینه‌ی پارتوی چندگانه، حدود ثابت ساختگی را نادیده می‌گیرد، و اصولاً می‌تواند مجموعه‌ای از جواب‌های بهینه متناسب با وزن‌های متفاوت و بردارهای متفاوت را بیابد. اگرچه در عمل تنها به یک جواب نیاز است، آگاهی نسبت به جواب‌های بهینه چندگانه، ممکن است طراح را در مقایسه جواب‌ها و انتخاب جواب بهینه یاری رساند [۲].
دسته‌بندی روش‌های چند‌هدفی
اولین قدم در باره مسایل بهینه‌سازی چند‌هدفی، تصمیم در مورد چگونگی ترکیب فرایند تصمیم‌گیری و جستجو است که با یکی از چهار روش زیر انجام می‌گیرد.
شکل۳- ۱- روش‌های حل مساله چند‌هدفی.
جستجوی بدون تقدم
در این روش، هیچ تقدمی از طرف تصمیم‌گیرنده اعمال نمی‌شود. مهم‌ترین روش از این دسته از روش‌های حل مسایل چند‌هدفی روش مین-ماکس است.
در روش مین-ماکس از مفهوم کمینه‌سازی فاصله نسبی هر جواب از بهترین جواب ممکن f* استفاده می‌شود. به عبارت دیگر، اگر fi(x) تابع هدف iام باشد و f*بهترین جواب ممکن برای تابع هدف منفرد fi(x) باشد، آنگاه مقدارf* به صورت f*=(f*1,f*2,…,f*n) بدست می‌آید. در روش مین-ماکس، تابع هدف مسأله چند‌هدفی به صورت زیر فرمول‌بندی می‌شود:
که در این رابطه p پارامتر فاصله است.
چنان‌که می‌بینید یکی از معایب این روش آن است که خروجی هر بار حل آنها تنها یک جواب است و تصمیم‌گیرنده ملزم به پذیرش آن به عنوان جواب نهایی است.
ابتدا تصمیم‌گیری سپس جستجو
در این روش ابتدا اولویت برای اهداف توسط تصمیم‌گیرنده مشخص‌می‌شوند، سپس یک یا چند جواب متنوع که اولویت در نظرگرفته‌شده را ارضا می کنند، بدست می‌آیند.
جستجو و تصمیم‌گیری هم‌زمان
در این روش، تصمیم‌گیرنده در روند انجام جستجو مداخله می‌کند تا با تنظیم اولیت‌ها در فرایند محاسبه جواب، جستجو برای رسیدن به جواب‌های مورد نظر انجام شود. تصمیم مهم در ارتباط با مسایل بهینه‌سازی چند‌هدفی به روش تصمیم‌گیری هم‌زمان، چگونگی ارزیابی کیفیت جواب‌ها است. زیرا بعضی از اهداف متناقض هستند و این فرایند ارزیابی را مشکل‌تر می‌کند.
ابتدا جستجو سپس تصمیم‌گیری
در این روش، ابتدا جواب‌های متنوعی حاصل می‌شوند، سپس تصمیم گیرنده از بین این جواب‌ها، جواب‌هایی را که مناسب‌تر باشند انتخاب می‌کند. این جواب‌ها باید از یک توازن نسبت به اهداف برخوردار باشند.
روش برنامه‌ریزی آرمانی
در یک مساله برنامه‌ریزی خطی، می‌توان اهداف سازمان را در قالب یک هدف عمده مثلاً بیشینه‌سازی کل سود و یا کمینه‌سازی کل هزینه‌ها، خلاصه کرد. در حقیقت، به تفصیلی که بحث خواهیم کرد، مطالعات انجام شده نشان می‌دهند که مدیریت شرکت‌های بزرگ هم خود را صرف هدف‌های دیگر نظیر تامین سود پایدار، افزایش )یا دست‌کم حفظ (سهم در بازار فروش، تنوع محصولات، تثبیت قیمت‌ها، ارتقای روحیه کارکنان، کنترل شرکت توسط افراد یک خانواده و سرانجام بالابردن وجهه شرکت نیز کرده‌اند. برنامه‌ریزی آرمانی، راه حرکت هم‌زمان به سوی چند هدف را نشان می‌دهد. مبنای کار چنین است که برای هر یک از هدف‌ها، عدد مشخصی به عنوان آرمان تعیین می‌شود. آنگاه جوابی جستجو می‌شود که مجموع (وزنی) انحراف هر هدف نسبت به آرمانی که به‌ازای همان هدف تعیین شده است را، کمینه‌کند.
برای بیان ریاضی این مطلب، فرض می‌کنیم کهx1,x2,…,xn متغیرهای تصمیم مساله وk تعداد هدف‌های موردنظر باشند. اگر cjk ضریب gk آرمان (j=1,2,…,n) در تابع هدف شماره (k=1,2,…,K) k ، هم‌چنین gk ، آرمان تعیین شده برای این هدف باشند. آنگاه در جستجوی جوابی هستیم که تا حدممکن دستیابی به آرمان‌های زیر را میسرسازد:
از آن‌جا که تحقق هم‌زمان همه این آرمان‌ها مقدور نیست، لذا ضروری است که عبارت تا حد ممکن دستیابی به هدف‌ها تعریف شود. در ساده‌ترین حالت، موقعی که انحراف از آرمان‌های تعیین شده در هر دو جهت دارای اهمیت یکسانی باشد، می‌توان تابع هدف تلفیقی برنامه‌ریزی آرمانی را به شرح زیر فرمول‌بندی کرد.
اما چگونه می‌توان چنین تابع هدف پیچیده ای را حل کرد؟ کلید اصلی برنامه‌ریزی آرمانی همین جاست. با بهره‌گیری از فن فرمول‌بندی متغیرهایی با درایه‌های مثبت و منفی که در بالا ارائه شد، می‌توان به سادگی Z را در چارچوب برنامه‌ریزی خطی گنجانید.
قدم اول، تعریف متغیرهای جدید (کمکی) است:
به طوری که
چون yk ها می‌توانند مقادیر مثبت و منفی را اختیار کنند، عناصر مثبت و منفی آنها یعنی- yk+,ykرا در چارچوب بحث بالا تعریف می‌کنیم. چنین فرمول‌بندی به نتایج زیر منتهی می‌شود:
که در آن،
بنابراین مدل برنامه‌ریزی خطی به‌صورت زیر می‌شود:
حال، می‌توان با بهره گرفتن از روش سیمپلکس جواب بهینه‌ای برای همه این متغیرها (و ازجمله xjها) بدست آورد. پس از آنyk+,yk – ها را که ماموریتشان به پایان رسیده‌است حذف کرد.
اکنون، فرض قبلی را که اهمیت انحراف از آرمان‌های تعیین شده را برای همه هدف‌ها یکسان می‌دانست، کنار می‌گذاریم. غالباً بعضی از هدف‌ها نسبت به سایرین اهمیت بیشتری دارند. علاوه بر این، حتی در مورد یک آرمان هم، انحراف در یک جهت ممکن است اهمیت زیادتری نسبت به جهت دیگر، داشته‌باشد. چنین تفاوت‌هایی را می‌توان با کمک ضرایب وزنیwk+,wk-,(k=1,2,…,k) که به ترتیب به متغیرهایyk+, yk- مربوط می‌شوند، در فرمول‌بندی وارد کرد. این ضرایب وزنی اهمیت نسبی نتایج حاصل از انحراف‌ها را می‌سنجند. در این حالت، تابع هدف برنامه‌ریزی آرمانی به صورت زیر در می‌آید:
