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

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

انجام می‌دهیم. هنگامی‌که یک سلول قابل قبول ایجاد شد، این فرایند را متوقف می‌کنیم. این کاهش دامنه جهش، تا زمانی که یک حل قابل قبول ایجاد شود، موقتی است.
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- سرعت همگرائی
به عنوان یک معیار برای سنجش عملکرد الگوریتها، ما از سرعت همگرا شدن الگوریتم استفاده کرده ایم. باتوجه به اینکه این مسأله، یک مسأله سه هدفه است، باید همگرایی را

پایان نامه
Previous Entries منابع پایان نامه ارشد با موضوع بهینه سازی چندهدفه، نخبه گرایی، رتبه بندی Next Entries منابع پایان نامه ارشد با موضوع مکانیابی، طراحی الگو، مکان‌یابی