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

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

از ارائه مجدد این حل‌ها در حافظه جلوگیری کند.
سال‌های اخیر، روش‌های گوناگونی در زمینه کاربرد AIS در مسائل بهینه سازی چندهدفه ایجاد شده‌است که عناوین بعضی از این روش‌ها به صورت زیر است: MOCSA94، IDCMA95، IFMOA96، CSADMO97، Tan & Mao’s MOIA، PAIA98، omni-aiNet، ACSAMO99، CNMOIA100، QUICMOA101، EMOIA102، NNIA، MAM-MOIA103، MLIA104، IMOA105، HIMO106.
در ادامه ما به بررسی و شرح مختصر سه الگوریتم MISA، VIS و NNIA که ازجمله الگوریتم‌هایی هستند که مورداستفاده تحقیق ما قرار گرفته‌اند، می‌پردازیم.
2-4-3-2- الگوریتم MISA
این الگوریتم براساس مفهوم انتخاب کلونال است و بر این اساس مدل سازی شده‌است که تنها آنتی بادی‌هایی که بالاترین قرابت را با آنتی ژن‌ها دارند، تکثیر شوند. همچنین این الگوریتم، از مفهوم غلبه پارتو برای تولید بردارهای غیرمغلوب استفاده می‌کند. همچنین، باتوجه به حرکت به سمت جبهه‌ی پارتو واقعی درطول زمان، یک حافظه اضافی (ثانویه) نیز برای ذخیره بردارهای غیرمغلوبی که درطول فرایند تکاملی یافت می‌شوند، استفاده می‌شود (که می‌تواند به صورت شکلی از نخبه گرایی در بهینه سازی مسائل چندهدفه تکاملی دیده شود).
این الگوریتم، همانطور که به صورت فلوچارت در شکل (2-6) نشان داده شده‌است، به صورت زیر خواهد بود [18]:
1) جمعیت اولیه را باتوجه به تقسیم فضای متغیر تصمیم به تعداد مشخصی از بخش‌ها، نسبت به اندازه جمعیت موردنظر، ایجاد می‌کنیم. بنابراین، ما یک جمعیت اولیه را با توزیع یکنواخت به گونه‌ای تولید کرده ایم که هر بخشی که فضای متغیر تصمیم تقسیم شده‌است، حل‌هایی دارد. به این خاطر این کار را انجام می‌دهیم که قابلیت جستجوی الگوریتم را به جای استفاده از یک اپراتور جهش، بهبود دهیم. به هر حال، حل‌هایی که برای جمعیت اولیه تولید می‌شوند، هنوز تصادفی هستند، از این رو، ما فقط این محدودیت را به این خاطر گذاشته ایم که مطمئن شویم توزیعشان در دامنه متغیرهای تصمیم، یکنواخت است.
2) حافظه ثانویه را که تاکنون خالی است، مقدار دهی می‌کنیم.
3) برای هر عضو در جمعیت مشخص می‌کنیم که مغلوب (پارتو) هست یا خیر؟ برای مسائل محدودیت دار، مشخص می‌کنیم که آیا یک عضو قابل قبول هست یا خیر؟

شکل 2-6- فلوچارت الگوریتم MISA

4) برای هر آنتی بادی مشخص می‌کنیم که جزء بهترین آنتی بادی‌ها هستند یا خیر؟ از این رو آن‌ها را با اجرای معیارهای زیر تکثیر می‌کنیم:
– اگر مسأله، بدون محدودیت است، همه اعضاء غیرمغلوب تکثیر می‌شوند.
– گر مسأله محدودیت دار است، با دو حالت مواجه می‌شویم: الف) حل‌های قابل قبول در جمعیت وجود دارد، و ب) هیچ حل قابل قبولی در این جمعیت وجود ندارد. برای مورد ب)، همه اعضاء غیرمغلوب تکثیر می‌شوند. برای مورد الف) فقط اعضاء قابل قبولی که غیرمغلوب هستند تکثیر می‌شوند (در این مورد، غلبگی فقط نسبت به دیگر اعضاء قابل قبول اندازه گیری می‌شود).
5) بهترین آنتی بادی‌ها را که از مرحله قبل بدست آمده‌است را در حافظه ثانویه کپی می‌کنیم.
6) برای بهترین آنتی بادی‌ها، تعداد تکثیری که موردنظرمان است را ایجاد می‌کنیم. این کار را به این شکل انجام می‌دهیم که کل تعداد تکثیرهایی که انجام می‌دهیم، برابر 60% کل جمعیّتی است که استفاده می‌کنیم. هنگامی‌که حافظه ثانویه پر است، به صورت زیر عمل می‌کنیم:
– اگر عضوی که وارد حافظه ثانویه می‌شود، اجازه ورود نداشته باشد (یا به این خاطر که تکراری است و یا به این علت که به متراکم ترین ناحیه فضای تابع هدف تعلق دارد)، تعداد تکثیرهایی که انجام می‌دهیم برابر صفر است.
– هنگامی‌که عضوی داریم که به سلولی تعلق دارد که تعداد حل‌هایی که دارد، زیر متوسط است (نسبت به همه سلول‌های اشغال شده در حافظه ثانویه)، تعداد تکثیرهایی که انجام می‌دهیم دو برابر می‌شود.
– هنگامی‌که عضوی داریم که به سلولی تعلق دارد که تعداد حل‌هایی که دارد، زیر متوسط است، تعداد تکثیرهایی که انجام می‌دهیم، به نصف کاهش می‌یابد.
7) بهترین آنتی بادی‌ها را براساس اطلاعاتی که از مرحله قبل بدست آمده‌است، تکثیر می‌کنیم.
8) یک اپراتور جهش را به طریقی بر روی کلون‌ها انجام می‌دهیم که تعداد ژن‌هایی که در هر رشته کروموزومی جهش می‌یابند، برابر تعداد متغیرهای تصمیم مسأله باشد. این کار را به این علّت انجام می‌دهیم که حداقل یک جهش در رشته اتفاق بیفتد، اگر غیر از این باشد، ما همان حل را دوبرابر کرده ایم (یعنی رشته اصلی و تکثیر شده دقیقاً یکسان خواهندبود).
9) یک اپراتور جهش غیریکنواخت را به بهترین آنتی بادی‌هایی که یافت شده‌اند اعمال می‌کنیم، اما تضمین نمی‌کنیم که تکراری صورت نگیرد (برخلاف اپراتور جهش مرحله قبل). نرخ جهش اولیه بالاست و به مرور زمان کاهش می‌یابد (از 0.9 به 0.3).
10) اگر حافظه ثانویه پر باشد، تقاطع را به کسری از محتویاتش اجرا می‌کنیم. اعضاء جدیدی که تولید شده‌اند، اگر نسبت به حافظه ثانویه غیرمغلوب باشند، به آن اضافه می‌شوند.
11) فرایند مرحله 3 به بعد را درمدت زمان مشخصی که از پیش تعیین کرده ایم، تکرار می‌کنیم.
علت اینکه جمعیت اولیه را با توزیع یکنواخت متغیرهای تصمیم درنظر گرفته ایم، این است که فضای جستجو را یکنواخت کنیم. این به ما کمک می‌کند که فضای جستجو را به طور مؤثرتری جستجو کنیم.
ما تقاطع را زمانی به حافظه ثانویه اعمال می‌کنیم که پر باشد و ما بتوانیم به نقاط میانی بین آن‌ها دست یابیم. چنین اطلاعاتی برای بهبود کارایی الگوریتم استفاده می‌شود.
حافظه ثانویه: ما از یک حافظه ثانویه یا اضافی به عنوان یک مکانیسم نخبه گرایی استفاده می‌کنیم تا بهترین حل‌هایی که در طول فرایند یافت می‌شوند را نگهداری کنیم. اعضائی که در این حافظه ذخیره می‌شوند، نه تنها نسبت به یکدیگر، بلکه نسبت به همه اعضاء قبلی که سعی داشته‌اند وارد حافظه ثانویه شوند، غیرمغلوب هستند. بنابراین، این حافظه ثانویه، ما را به جبهه‌‌ی پارتو مسأله نزدیک نگه می‌دارد.
باتوجه به اجرای یک توزیع یکنواخت بر روی حل‌های غیرمغلوبی که جبهه‌ی پارتو یک مسأله را پوشش می‌دهند، از شبکه تطبیقی که بوسیله نولِس و کورنه107 ارائه شده‌است، استفاده می‌کنیم (شکل 2-7).

شکل 2-7- یک شبکه تطبیقی برای رسیدگی به حافظه ثانویه
به طور ایده آل، اندازه حافظه ثانویه باید بینهایت باشد. به هر حال، از آنجائی که این کار درعمل غیرممکن است، باید محدودیتی را بر سر تعداد اعضاء غیرمغلوبی که می‌خواهیم در حافظه ثانویه ذخیره شوند، قراردهیم. با اجرای این محدودیت، حافظه اضافی ما، حتی اگر اعضاء غیرمغلوب بیشتری که بخواهند وارد شوند، وجود داشته باشد، در بعضی نقاط، پر می‌شود. هنگامی‌که این اتفاق می‌افتد، ما از یک معیار اضافی برای اجازه به اعضاء غیرمغلوبی که بخواهند وارد حافظه اضافی بشوند، استفاده می‌کنیم: چگالی شبکه (یعنی، اعضائی که به ناحیه با چگالی کمتر جمعیت تعلق دارند، ارجحیت دارند).
برای اجرای شبکه تطبیقی به صورت زیر عمل می‌کنیم:
1) فضای تابع هدف را باتوجه به تعداد تقسیماتی که توسط کاربر مشخص می‌شود، تقسیم می‌کنیم.
2) برای هر عضو در حافظه اضافی، سلولی که به آن تعلق دارد را تعیین می‌کنیم.
3) اگر حافظه ثانویه پر باشد، متراکم ترین سلول را مشخص می‌کنیم.
4) برای تعیین اینکه یک آنتی ژن مشخص اجازه ورود به حافظه اضافی را دارد یا خیر، به صورت زیر عمل می‌کنیم:
– اگر به متراکم ترین سلول تعلق داشته باشد، اجازه ورود ندارد.
– درغیر اینصورت، این عضو اجازه ورود دارد. به همین علت، ما یک عضو را (به صورت تصادفی) از متراکم ترین سلول حذف می‌کنیم تا جای خالی برای این آنتی ژن داشته باشیم.
2-4-3-3- الگوریتم VIS
در این قسمت، براساس ساختار مسأله بهینه سازی opt-aiNet، یک رویکرد بهینه سازی چندهدفه جدید ارائه می‌شود. این الگوریتم، سیستم ایمنی برداری (VIS) نامیده می‌شود و همان ساختاری را دارد که برای مسأله تک هدفه در شکل (2-8) نشان داده شده‌است. رویکرد پیشنهادی، تکاملی بر اولین نسخه آن است که توسط فرسچي و رِپِتو ارائه شده‌است. این الگوریتم به شکل زیر عمل می‌کند [19]:
1) در ابتدا، یک جمعیت اولیه به صورت یکنواخت و تصادفی از بردارهایی از اعداد واقعی ایجاد می‌کنیم و یک برازش را به هر حل تخصیص می‌دهیم. حافظه در حال حاضر خالی است.
2) هر سلول را به تعداد بار تکثیر می‌کنیم و هر کدام را به صورت محلی بوسیله یک اختلال تصادفی جهش می‌دهیم.
3) برای هر کلون، مقدار توابع هدف و روابط غلبه پارتو (درمیان همه اعضاء: والدین، فرزندان و سلول‌های حافظه) ارزیابی می‌شود. از آنجاکه این برازش، به جمعیت واقعی بستگی دارد، مقدارش به همان کلون تخصیص داده می‌شود و برای سلول‌های پدر، دوباره محاسبه می‌شود. اعضاء غیرمغلوب در حافظه کپی می‌شوند. به خاطر اینکه حافظه، فقط شامل حل‌های غیرمغلوب محلی می‌شود، اعضائی از حافظه که درنتیجه آن، مغلوب می‌شوند نیز حذف می‌شوند.

شکل 2-8- فلوچارت الگوریتم VIS
4) از بین پدر و فرزندانش، بهترین سلول ازنظر برازش، برای تولید بعدی انتخاب می‌شود (انتخاب کلونال). اگر یک کلون، برازشی شبیه سلول والدش دارد، آن کلون برای تولید بعدی انتخاب می‌شود. ازبین کلون‌های با برازش یکسان، انتخاب به صورت تصادفی انجام می‌شود.
5) مراحل 3 و 4 را (که با حلقه داخلی در شکل2-7 نشان داده شده‌است)، بار تکرار می‌کنیم.
6) سپس، اپراتور قرابت را برای حافظه به کار می‌بریم: فاصله اقلیدسی بین سلول‌های حافظه اندازه گیری می‌شود؛ باتوجه به، بدست آوردن یک جبهه‌ی پارتوی که به صورت یکنواخت توزیع شده‌است، به طور متفاوتی از الگوریتم AIS، این فاصله این بار در فضای هدف، ارزیابی می‌شود.
7) همه سلول‌های حافظه با بالاترین برازش که فاصله آن‌ها کمتر از یک حد آستانه است، حذف می‌شوند. مقدار آستانه باید به تعداد حل‌هایی که مایلیم در حافظه وجود داشته باشند ()، بستگی داشته باشد؛ اگر اهداف در فاصله [0,1] نرماله شوند، مقدار (M، تعداد اهداف است) بیانگر فاصله بین حل‌هایی است که به صورت یکنواخت بر روی یک جبهه‌ی پارتو پیوسته، توزیع شده‌اند. این مقدار، به عنوان آستانه تطبیقی برای حذف انتخاب می‌شود. این روش، محدودیتی را بر روی اندازه حافظه نمی‌گذارد.
8) بعد از حذف، حافظه در جمعیت اصلی کپی می‌شود. باتوجه به حفظ تنوع حل‌ها، سلول‌های جدید به صورت تصادفی تولید می‌شوند تا باقی جمعیت را پرکنند. یک حداقل درصدی از حل‌های جدید، ، در هر تکرار باید تولید شود.
9) این فرایند بار از مرحله 2 تکرار می‌شود.
اکتشاف فضای جستجو بوسیله مکانیسم انتخاب کلونال در حلقه داخلی، مدیریت می‌شود. این سلول‌ها، در جمعیت جستجوهای محلی را به صورت موازی انجام می‌دهند. عکس العمل شبکه بین سلول‌ها در حلقه خارجی، مسئول جلوگیری از افزایش حل‌های یکسان است و از تکثیر آنها جلوگیری می‌کند و آن‌ها را حذف می‌کند. با این روش، نگهداری کنترل پویایی تعداد سلول‌های شبکه ممکن می‌شود. کار اکتشاف فضای حل، بوسیله تعدادی از اعضاء جدید که در هر تکرار خارجی تولید می‌شوند، انجام می‌شود.
با درنظر گرفتن سیستم ایمنی، یک نرخ جهش که به مقدار برازش بستگی دارد، معرفی می‌شود. سلولی که بهترین برازش را دارد، فقط یک متغیرش جهش می‌یابد، سلولی که بدترین برازش را دارد، همه متغیرهایش جهش می‌یابند. مقدار که نشان دهنده تعداد جهش‌هایی است که باید بر i امین سلول انجام شود، بسته به جایگاه آن سلول در جمعیت رتبه بندی شده دارد:
(30.2)
که N، تعداد درجات آزادی و ، اندازه جمعیت است.
در VIS، حل‌های غیرقابل قبول می‌تواند به دو شکل ایجاد شود. اول هنگامی است که یک عضو تصادفی جدید تولید می‌شود. در این مورد، هر حل غیر قابل قبول به آسانی دور انداخته می‌شود (جریمه مرگ) و یک سلول جدید ایجاد می‌شود. همچنین یک حل غیرقابل قبول می‌تواند بعد از اجرای اپراتور جهش به یک سلول اتفاق بیفتد که به محدودیت نزدیک است. در این مورد، امکان پذیری حل را با کاهش دامنه جهش به نصف

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