بخشی از مقاله
چکیده
این مقاله یک روش مبتنی بر ارجحیات را ارائه می دهد که با یک الگوریتم بهینه سازی چندهدفه برای سوق دادن تصمیم گیرنده به سمت انتخاب جواب ارجح ترکیب می شود. با فرض اینکه تعداد فراخوانی های تصمیم گیرنده محدود است، الگوریتم در هر تکرار پس از آن که پیشرفت قابل قبولی در جواب حاصل شد، تصمیم گیرنده را برای بیان ارجحیتهایجدید فراخوانی کرده و سپس از این اطلاعات برای مدلسازی یک تابع ارزش اکیداً صعودی استفاده می کند. این تابع ارزش به هدایت الگوریتم به سمت نقطه مرجع کمک کرده به طوری که در انتهای هر تکرار با استفاده از یک معیار غلبه و یک معیار خاتمه جواب بهتری نسبت به تکرار قبلی و نزدیک تر به نقطه مرجع تولید می شود.
واژه های کلیدی: بهینه سازی چندهدفه تکاملی، الگوریتم های تعاملی، نقطه ی ارجح، تابع ارزش
١مقدمه
تصمیم گیری چندمعیاره کاربردهای زیادی در جهان واقعی دارد و از این رو روش های زیادی برای حل این گونه مسائل مطرح شده است که هر کدام از این روش ها نقاط قوت و ضعف مربوط به خودشان را دارند و در موارد خاص به خوبی قابل اجرا هستند. یکی از شاخه های تصمیم گیری چندمعیاره، بهینه سازی چندهدفه می باشد که به معنی بدست آوردن بهترین جواب برای مسأله ای با چند هدف مشخص روی ناحیه ی مفروض است. ولی معمولا برای این گونه مسائل تک جوابی که بتواند همزمان تمام اهداف را بهینه کند، وجود ندارد. لذا برای این مسائل ما با یک مجموعه جواب با عنوان جواب پارتو بهینه سروکار داریم که انتخاب بهترین و کارآمدترین جواب از بین این جواب ها بر مبنای اولویت های تصمیم گیرنده می باشد. یک نمونه از الگوریتم های بهینه سازی چندهدفه، الگوریتم های بهینه سازی چندهدفه تکاملی بوده و یکی از جدیدترین روش های تکاملی برای حل مسائل چندهدفه، روش تعاملی مطرح شده در ]٣[ می باشد که ویژگی اصلی آن فرض کردن تعداد محدود فراخوانی هایتصمیم گیرنده می باشد.
الگوریتم مذکور در هر تکرار به کمک مخروط های چندوجهی جهت جستجو را برای یافتن یک جواب پارتو بهینه جدید تعیین می کند. در این مقاله با به کار گرفتن راهکار ساخت تابع ارزش برمبنای اولویت های تصمیم گیرنده برای تعداد مفروضی جواب و مقایسه ی دودویی آنها، الگوریتم ارائه شده در ]٢[ را بهبود می بخشیم. در این مقاله، اولویت های تصمیم گیرنده با گام های میانی الگوریتم یکی می شود که این اجتماع منجربه هدایت الگوریتم به سمت نقطه ارجح - نقطه ای روی مرز پارتو بهینه است که بیشترین سودمندی یا خرسندی تصمیم گیرنده را در مقایسه با دیگر نقاط روی مرز دارد. - می گردد. سهمیه فراخوانی های تصمیم گیرنده در شروع الگوریتم به عنوان پارامتر ورودی داده می شود. ساختار کلی مسأله ی بهینه سازیچندهدفه ی مفروض در این مقاله به صورت زیر می باشد:
٢ چارچوب کلی الگوریتم
در اکثر روشهای تعاملی پیشرو یک مجموعه جواب آغازین بصورت تصادفی یا با استفاده از جستجوی تکاملی و معیار غلبه استاندارد تولید می شود. سپس اولویت های تصمیم گیرنده استخراج می شود، که این عمل به الگوریتم برای یک جستجویمتمرکز در ناحیه ی مورد علاقه کمک می کند. این الگوریتم معمولا یک تک جواب را به عنوان خروجی نهایی تولید می کند.طرح سهمیه ثابت فراخوانی های تصمیم گیرنده به یک نقطه ی ایده آل - !Iبرای شروع نیاز دارد. بعداز تعیین نقطه ایده آل،جمعیت آغازین بصورت تصادفی تولید می شود. نقطه یp از جمعیت آغازین به عنوان نزدیک ترین نقطه به برحسب فاصله ی اقلیدسی انتخاب شده و فاصله آن از نشان داده می شود. اگر DMحداکثر تعداد بصورت فراخوانی های تصمیم گیرنده باشد، فاصله ی DI ب dI = TDM بخش تقسیم می شود . dI را طول گام نامند. بعد از آن یک جستجوی تکاملی با نمونه های تصمیم گیری انجام می شود، تا زمانی که معیار خاتمه برقرار شود. قبل از شرح الگوریتم، ابتدا شیوه ی ساخت تابع ارزش، معیار خاتمه و قانون غلبه ی اصلاح شده بر مبنای این تابع را در بخش های بعدی توضیح می دهیم ]٢.[
٢ . ١ اطلاعات اولویت های تصمیم گیرنده و ساخت تابع ارزش چند جمله ای
گاهی فرض می شود که تصمیم گیرنده تصمیمات خود را بر پایه ی یک تابع بیان کند. این تابع که اولویت های تصمیم گیرنده را نشان می دهد و تابعی حقیقی مقدار است تابع ارزش Vنامیده می شود. تابع ارزش یک تابع اکیداً صعودی می باشد زیرا به بهترین جواب انتخابی توسط تصمیم گیرنده بیشترین مقدار را نسبت می دهد. این تابع یک تابع فرضی می باشد و در عمل نمی توانیم آن را به صورت صریح بنویسیم بلکه فقط می توان فرض کرد ساختار این تابع به صورت یک تابع خاص مانند تابعی چندجمله ای یا جمعی و یا شبه محدب است. در این مقاله فرض می کنیم که تابع ارزش تصمیم گیرنده دارای یک ساختار چندجمله ای است. فرض کنید در یک فراخوانی تصمیم گیرنده _ نقطه برای مقایسه وجود داشته باشد.
یک راه برای تصمیم گیرنده مقایسه دودویی جواب ها می باشد که برای هردو جواب Pi و Pj یکی از دو حالت رخ می دهد: جواب Pi از Pj بهتر است - Pi ≻ Pj - یا دو جواب Pi و Pj با هم قابل مقایسه نیستند . - Pi _ Pj - لذا در انتهای مقایسه دودویی _ جواب می توان جواب ها را این گونه مرتب کرد: ١P بهترین جواب، ٢P جواب بهتر مرتبه دوم، ... و P جواب آخر. که ١Pهمان Acbest می باشد. اکنون بعد از مرتب سازی جواب ها تابع ارزش را به صورت زیر در نظر می گیریم:که ١fM ; :::; f توابع هدف و ١lM ; :::; l و ١١:::; k ; - ١ - M ١k ;٢١::::k ; - ١kM - M پارامترهای تابع ارزش هستند. این پارامترها مجهول می باشند و باید از اطلاعات اولویت _ نقطه ی انتخابی توسط تصمیم گیرنده تعیین شوند. این تابع ارزش برای M تابع هدف نشان داده شده در بالا، به منظور ایجاد کردن M تابع خطی :::; M ;٢ ;١ Sm : RM ! R; m = درنظر گرفته می شود ]٢.[ برای این منظور مسأله ی بهینه سازی زیر را حل می کنیم:
٢ . ٢ معیار خاتمه
فرض کنید تابع ارزش V تعیین شده باشد. با استفاده از این تابع می توان تشخیص داد که آیا کل عمل بهینه سازی خاتمه یافته است یا خیر. ابتدا بهترین نقطه ١P و دومین نقطه بهتر ٢P را از مجموعه ی _ نقطه ای انتخاب می کنیم. تابع ارزش موردنظر می تواند اطلاعاتی را تأمین کند که آیا نقطه جدید P از بهترین نقطه جاری یعنی ١P بهتر است یا خیر. بنابراین اگر یک جستجوی تک هدفه در راستای گرادیان تابع ارزش از نقطه ی ١P را اجرا کنیم، انتظار داریم که نقطه ای بهتراز ١P تولید شود که با استفاده از این می توان معیار خاتمه را توسعه داده، برای این منظور مسأله ی ASF زیر را برای ١zb = P حل می کنیم، که در آن S فضای متغیرهای تصمیم شدنی مسأله ی اصلی را نشان می دهد.در حل این مسأله هر جواب در تکرارهای میانی - ::: ;٢ ;١ - z - i - ; i = را ذخیره می کنیم. اگر فاصله اقلیدسی z - i - و ١P از پارامتر خاتمه dA بزرگتر بود ]٣[، بهینه سازی ASF متوقف می شود و الگوریتم ادامه می یابد. که در این حالت z - i - جایگزین ١P می شود. از طرف دیگر اگر بهینه سازی ASF خاتمه یافت و فاصله ی جواب نهایی zT از ١P بزرگتر از dA نبود الگوریتم خاتمه می یابد و zT به عنوان جواب نهایی الگوریتم معرفی می شود.
٢. ٣ قانون غلبه اصلاح شده
فرض کنید V تابع ارزش در تکرار جاری باشد و ٢= V - ٢V - P که در آن ٢P دومین نقطه ی بهتر است. دراین صورت هر دو جواب شدنی - ١x - و - ٢x - می توانند با مقادیر تابع هدفشان این گونه با هم مقایسه شوند: اگر مقدار تابع ارزش هر دو جواب از ٢V کمتر یا مقدار تابع ارزش هر دو از ٢V بیشتر بود آنگاه این دو نقطه بهوسیله ی معیار غلبه ی معمول باهم مقایسه می شوند. در غیراین صورت اگر مقدار تابع ارزش یک جواب بیشتر از ٢V و جواب دیگر کمتر از ٢V بود آنگاه دو جواب به صورت زیر باهم مقایسه می شوند:با توجه به شکل ١ مقدار تابع ارزش در نقطه ی A از ٢V کمتر و در نقطه ی B از ٢V بیشتر می باشد لذا در نقطه ی A از معیار غلبه ی معمول استفاده می گردد و در نقطه ی B مطابق شکل ١ عمل می شود. نواحی که توسط نقاط A و B مغلوب می شوند هاشور زده شده است. دلیل انتخاب ٢P به عنوان نقطه ی پایه برای معیار غلبه این است که در بعضی مسائل این امکان وجود دارد که نقطه ی ارجح بین ١P و ٢P قرار گرفته باشد. در این حالت اگر ١P به عنوان نقطه پایه برای معیار غلبه در نظر گرفته شود، نقطه ی ارجح توسط ١P مغلوب خواهد شد.
٣ الگوریتم بهینه سازی چندهدفه تکاملی تعاملی مبتنی بر تابع ارزش
اکنون با توجه به توضیحات ارائه شده ی بالا و الگوریتم پیشنهادی در ]٣[، الگوریتم جدید مورد نظر که مشابه الگوریتم مقاله ]٣[ می باشد و تفاوتش با این الگوریتم در گام های ٣، ۴، ۵ و ٧ است. در واقع برای تعیین جهت جستجو، به جای استفاده از
