منابع پایان نامه ارشد با موضوع ترتیب نزول، بهینه سازی چندهدفه، رگرسیون خطی

انجام می‌دهیم. هنگامی‌که یک سلول قابل قبول ایجاد شد، این فرایند را متوقف می‌کنیم. این کاهش دامنه جهش، تا زمانی که یک حل قابل قبول ایجاد شود، موقتی است.
2-4-3-4- الگوریتم NNIA [20]
این روش، اعضاء غیرمغلوبی را که تاکنون یافت شده را در یک جمعمیت اضافی که جمعیت غالب نامیده می‌شود، ذخیره می‌کند. فقط کسری از اعضاء غیرمغلوبی که دارای تراکم کمتری هستند و آنتی بادی‌های فعال نامیده می‌شوند، برای انجام تکثیر نسبی، بازترکیب و جهش، انتخاب می‌شود. به علاوه، این جمعیتی که کلون‌ها را ذخیره می‌کند، جمعیت کلون نامیده می‌شود. جمعیت غالب، جمعیت فعال و جمعیت کلون در زمان t، به ترتیب بوسیله معیارهای متغیر وابسته به زمان ، و بیان می‌شود. حلقه اصلی NNIA به صورت زیر است:
ورودی‌:
Gmax: حداکثر تعداد تولید
: حداکثر اندازه جمعیت غیرمغلوب
: حداکثر اندازه جمعیت فعال
: اندازه جمعیت کلون
خروجی:
: مجموعه بهینه پارتو

شکل 2-9- تکامل جمعیت NNIA
مراحل الگوریتم همانطور که در شکل (2-9) به صورت شمای کلی آورده شده‌است، به صورت زیر است:
1) مقداردهی اولیه: یک جمعیت آنتی بادی اولیه با اندازه ایجادکنید. و قرار دهید. t را برابر صفر تنظیم کنید.
2) به روز کردن جمعیت غالب: آنتی بادی‌های غالب را در مشخص کنید؛ همه آنتی بادی‌های غالب را برای تشکیل جمعیت غالب موقت (که با نشان می‌دهیم) کپی کنید؛ اگر اندازه بزرگتر از نیست، قرار دهید. درغیراینصورت، مقادیر فاصله ازدحام همه اعضاء در را حساب کنید، آن‌ها را به ترتیب نزولی فاصله ازدحام مرتب کنید، عضور اولیه از را انتخاب کنید.
3) پایان: اگر برقرار شد، را به عنوان خروجی الگوریتم اعلام کنید، متوقف شوید؛ درغیراینصورت، .
4) انتخاب غیرمغلوب براساس همسایگی: اگر اندازه بزرگتر از نیست، قرار دهید. درغیراینصورت، مقادیر فاصله ازدحام همه اعضاء را حساب کنید، آن‌ها را به ترتیب نزولی فاصله ازدحام مرتب کنید، عضو اول از را انتخاب کنید.
5) تکثیر نسبی: جمعیت کلون را بوسیله اجرای تکثیر نسبی بر روی تشکیل دهید.
6) بازترکیب و جهش: بازترکیب و جهش را بر روی اجرا کنید و مجموعه را که جمعیت بدست آمده‌است را تشکیل دهید.
7) جمعیت آنتی بادی‌های را بوسیله ترکیب و تشکیل دهید؛ به مرحله 2 بروید.
هنگامی‌که تعداد آنتی بادی‌های غالب، بزرگتر از حداکثر محدودیت شود و اندازه جمعیت غالب بزرگتر از حداکثر اندازه جمعیت فعال شود، هر دو کاهش جمعیت غالب و انتخاب آنتی بادی‌های فعال، از فاصله ازدحام استفاده می‌کنند. اپراتورهای تکثیر نسبی، بازترکیب و جهش، به صورت زیر تشریح می‌شوند.
تکثیر نسبی: در این الگوریتم، به طور خلاصه، اعضاء با مقدار فاصله ازدحام بیشتر، بیشتر تولید می‌شوند. عضوی که مقدار فاصله ازدحام بیشتری دارد، بیشتری دارد، به خاطر اینکه مقدار فاصله ازدحام حل‌های مرزی، مثبت بینهایت است، قبل از محاسبه مقدار هر آنتی بادی فعّال، مقدار اعضاء کرانه‌ها را برابر دوبرابر مقدار حداکثر مقدار آنتی بادی‌های فعال (به استثنای اعضاء مرزی) قرارمی‌دهیم. بنابراین، مقدار به صورت زیر محاسبه می‌شود:
(31.2)
که به مقدار فاصله ازدحام آنتی بادی اشاره دارد.
بازترکیب: برای بازترکیب، هر عضو مجموعه را با یک عضو از که به صورت تصادفی انتخاب شده‌است، عملگر تقاطع را انجام می‌دهیم.
جهش: بعد از بازترکیب، عملگر جهش را به صورت یکسان و با احتمال برابر، بر روی تک تک اعضاء اجرا می‌کنیم. بنابراین، هر عضو از جمعیت ، دستخوش جهش می‌شود که m ، اندازه بردار متغیرها و یا تعداد ژن‌های هر آنتی بادی و یک عدد تصادفی مانند می‌باشد.
2-5- روش‌های اندازه گیری عملکرد الگوریتم‌های چندهدفه [3]
یکی از مشکلاتی که در حل مسائل چندهدفه با آن مواجه می شویم، چگونگی ارزیابی کیفیت حل‌های نهایی است که بدلیل تناقض اهداف بکار رفته، گاهاً این امر کاری پیچیده خواهد بود.
به این منظور و در اوایل دهه ۹۰ میلادی از روش‌های دیداری (مشاهده ای) برای مقایسه مجموعه‌های پارتو استفاده می کردند. بدیهی است این روش‌ها دارای دو مشکل اساسی بودند ، اولاً اینکه ما در مقایسات علمی نیازمند مبنایی قابل اندازه گیری و کمّی بودیم و صرف اظهار نظر کیفی اشخاص، نمی توانست محکی مناسب در اندازه گیری کارایی الگوریتم‌ها باشد. ثانیاً مشکل اساسی دیگر این روش‌ها در مقایسه مجموعه‌های پارتو این بود که فقط برای حداکثر مسأله ۳ هدفه کاربرد داشتند. به این دلیل که امکان ترسیم فضای بیشتر از سه بعد برای مقایسه مجموعه جواب‌ها وجود نداشت. تمام این مشکلات باعث شد تا پژوهشگران به فکر بیافتند تا روش‌های منطقی، جامع و مناسب را به ا ین منظور ارائه نمایند. در مسائل تک هدفه، در پایان اجرای الگوریتم‌ها، حلی را با توجه به نوع هدف (ماکزیمم یا مینیمم)، به عنوان بهترین حل انتخاب می شود و در این حالی است که در مسائل چندهدفه در پایان حل، مجموعه ای از جواب‌ها ایجاد می شوند که بایستی با توجه به این مجموعه حلها راجع به عملکرد الگوریتم اظهارنظر شود. این روشها از این جهت مهم هستند که به پژوهشگر کمک می کنند تا عملکرد الگوریتم‌های مورد بررسی را با روشی کمّی، ارزیابی و انحراف الگوریتم را مدیریت نمایند.
در این روشها غالباً مبنای اصلی طراحی هر معیار عملکرد بر مبنای یکی از سه حالت زیر است:
• تعداد حل‌های غیرغالب بدست آمد
ه
توسط الگوریتم
• تراکم و نزدیکی بین حل‌های بدست آمده و حل‌های بهینه (اگر حل‌های بهینه موجود باشد)
• پوشش، توزیع و پراکندگی حل‌های غیرغالب
در این بخش، ابتدا مروری بر معروفترین این روش‌ها می‌کنیم. برای بیان روش‌های مرتبط با این بخش لازم است اصطلاحات زیر تعریف شوند:
: مجموعه حل‌های غیرمغلوب نهایی الگوریتم
: مجموعه حل‌های بهینه (یا بهترین جواب‌های شناخته شده)
البته همیشه مجموعه حل‌های بهینه برای مسائل چندهدفه موجود نمی باشد و گاهی تعیین آن غیرممکن است.
2-5-1- فاصله نسلی108
این روش اولین بار در سال 2000 توسط وَن وِلدهویزِن و لامونت109 پیشنهاد شده‌است. این معیار، فاصله بین و را اندازه گیری می‌کند. برای تعیین این مقیاس، لازم است که پژوهشگر، را دراختیار داشته باشد. نمایش ریاضی این معیار به صورت زیر است:
(32.2)
که در این رابطه، n، نشاندهنده تعداد بردارها در است و فاصله اقلیدسی بین هر عضو از مجموعه با نزدیکترین عضو در مجموعه می‌باشد. لذا هنگامی‌که GD=0 است، و معادل هم هستند.
اما در مسائل بهینه سازی چندهدفه، همانند مسأله ما، همیشه مجموعه دراختیار نیست. در این مطالعه برای رفع این مشکل، روش تغییریافته‌ای از این الگو به کار رفته‌است. نحوه محاسبه عملکرد مجموعه جواب‌های پارتو، بصورت رابطه زیر خواهد بود:
(33.2)
که فاصله اقلیدسی بین هر عضو از مجموعه از مبدأ مختصات بوده که از رابطه بدست می‌آید. در این رابطه منظور از ، مقدار kامین تابع هدف در بردار جواب پارتو iام است. بدیهی است که برای مجموعه‌های موردمقایسه، هرچقدر که این مقدار کوچکتر باشد، مطلوبیت آن مجموعه بیشتر خواهدبود.
2-5-2- درجه توازن در رسیدن همزمان به اهداف
در اینجا، روش دیگری مبتنی بر مسافت پیشنهاد شده‌است. اما ابتدا لازم است مقدماتی راجع به کیفیت حل‌ها بیان شود.
در شکل (2-10)، حل‌های مناسب مسأله دوهدفی را نشان داده شده‌است و همچنان که مشاهده می‌شود، اگر حلی درامتداد یک محور باشد، مناسب نیست، زیرا آن حل تنها برای یک هدف مناسب بوده و برای هدف دیگر عملکرد مناسبی نداشته‌است، ولی حل‌هایی که با فلش نشان داده شده‌اند، حل‌های مناسبی هستند، زیرا که به یک توازن قابل قبول بین اهداف مسأله رسیده‌اند. حال با این توصیف، در اینجا لازم است معیاری کمّی برای اندازه گیری رسیدن به این توازن در بین اهداف مختلف مسأله تعریف شود. به این منظور، در این مطالعه رابطه زیر پیشنهاد شده‌است:
(34.2)

شکل 2-10- نمایش حل‌های مناسب
که در این رابطه است.
2-5-3- مساحت زیر خط رگرسیون
روش مبتنی بر مساحت پوشش، روشی است که برای مقایسه مجموعه‌های پارتو، از مفهوم مساحت زیر نمودار برازش شده به هر مجموعه پارتو استفاده کرده و به منظور این برازش، از مفهوم رگرسیون خطی استفاده می‌کند. هدف در این روش، عبور دادن بهترین خط راست از مجموعه جواب‌های غیرمغلوب، بااستفاده از روابط شیب و عرض از مبدأ است.
با توجه به شکل (2-11)، در این روش، هدف تعیین و مقایسه مثلث‌های و AOB می‌باشد. همچنان که در شکل مشاهده می‌کنید، مساحت مثلث کوچکتر از مساحت مثلث AOB بوده و کاملاً مشخص است از لحاظ رسیدن به مقادیر بهتر در دو تابع هدف، الگوریتم متناظر با خط کارایی بهتری دارد.
بدیهی است هر چه این خط تخمینی به نقطه (0.0) نزدیکتر باشد، آنگاه محل تقاطع آن با محورها کوچکتر بوده و درنتیجه، مساحت مثلث زیر خط برازش شده کوچکتر خواهدبود که این امر، نشان دهنده بهتر بودن مجموعه حل‌های غیرمغلوب متناظر آن خط است.

شکل 2-11- مساحت زیر خط رگرسیون
باتوجه به اینکه مسأله این تحقیق، شامل سه تابع هدف می‌باشد، مبنای این مقایسه، به جای سطح، فضای زیر هر صفحه خواهد بود. امّا باتوجه به اینکه یافتن سطحی تخمینی که برایند اهداف مسأله باشد بسیار مشکل می‌باشد، ما اهداف را به صورت دو به دو با یکدیگر درنظر گرفته و با آن‌ها به صورت مساحت زیر خط رگرسیون برخورد می‌کنیم، سپس این مساحت‌ها را با یکدیگر جمع می‌کنیم. این روش، تغییر زیاد بزرگی در نتایجی که در حالت سه هدفه بدست می‌آید، ایجاد نمی‌کند.
2-5-4- تعداد جواب‌های غیرمغلوب نهائی
این روش، تعداد جواب‌های غیرمغلوب نهایی مسائل را با یکدیگر مقایسه می‌کند. بدیهی است که هرچه این تعداد بیشتر باشد، نشان دهنده این است که آن الگوریتم، جستجوی بهتری را در فضای مسأله انجام دهد. البته در بعضی از الگوریتم‌ها، محدودیتی بر روی اندازه جمعیت نهائی وضع شده‌است که ما این محدودیت را به ماهیت الگوریتم ربط داده و الگوریتم را با همان محدودیت وضع شده درنظر گرفته ایم.
2-5-5- فاصله گذاری110
تنوع در حل‌های بدست آمده با توجه به فضای حل، همان چیزی است که در بیشتر تحقیقات نادیده گرفته می‌شود. زمانی که پژوهشگر کیفیت مجموعه حل‌های غیرمغلوب را بیان می‌کند، اطلاعاتی را درباره تنوع حل‌ها در فضای حل بیان نمی‌کند. این نکته مهمّی است، زیرا اگرچه حل‌های غیرمغلوب ازلحاظ توزیع و پراکندگی ممکن است خوب باشند، ولی ممکن است هیچ کدام از آن‌ها از لحاظ ساختاری متفاوت نبوده و یا تعداد زیادی از آن‌ها مشابه باشند.
به این منظور، معیار فاصله گذاری توسط اسکات111 پیشنهاد شده‌است. این معیار به نوعی واریانس فاصله از بردارهای همسایه را در را اندازه گیری می‌کند. این مقیاس توسط فرمول زیر محاسبه می‌شود:
(35.2)
که در
آن برابر است با:
(36.2)
در رابطه فوق، بوده و میانگین همه هاست و n ، تعداد بردارها در است. در این روش، S=0 به این مفهوم است که همه عضوها به صورت یکنواخت و مجزا از هم پراکنده شده‌اند.
2-5-6- گسترش112
معیار گسترش، فاصله اقلیدسی بین کرانه‌هایی که از حل‌های غیرمغلوب بدست می‌آید را محاسبه می‌کند. همانطور که در شکل (2-12) مشاهده می‌کنید، هرچه این مقدار بیشتر باشد، نشان دهنده آن است که الگوریتم، حل‌هایی با دامنه و گستردگی بیشتری را یافته‌است. گسترش باتوجه به فرمول زیر بدست می‌آید:
(37.2)
در این روش نیز، باتوجه به اینکه ما سه هدف داریم، ما اهداف را دو به دو درنظر گرفته و بیشترین گسترش بین آن‌ها را محاسبه کرده و این مقادیر را با یکدیگر جمع می‌کنیم.

شکل 2-12- بیشترین گسترش
2-5-7- سرعت همگرائی
به عنوان یک معیار برای سنجش عملکرد الگوریتها، ما از سرعت همگرا شدن الگوریتم استفاده کرده ایم. باتوجه به اینکه این مسأله، یک مسأله سه هدفه است، باید همگرایی را