منابع پایان نامه ارشد با موضوع رتبه بندی، نخبه گرایی، الگوریتم ژنتیک

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

اریب بودن اهداف، با مشکل مواجه می‌شود. درواقع هدف اول الگوریتم‌های بهینه یابی چندهدفه، یعنی رسیدن به جواب‌های بهینه پارتو، به نحو شایسته‌ای توسط این الگوریتم بدست می‌آید، ولی جواب‌های بدست آمده از گستردگی و تنوع خوبی برخوردار نیستند.
در ادامه این قسمت، به سه الگوریتم تکاملی چند هدفه که مبنای اصلی آنها، الگوریتم ژنتیک می‌باشد، می‌پردازیم. الگوریتم NSGA-II به این خاطر انتخاب شده‌است که این الگوریتم در بسیاری از مقالات به عنوان الگوریتم مرجع مقایسه گردیده‌است. الگوریتم CNSGA-II نیز به این علت انتخاب شده‌است که روشی مناسب برای برخورد با محدودیت‌های حل مسأله ارائه می‌کند؛ چون باتوجه به ماهیت مسأله، چندین محدودیت سر راه حل مسأله ایجاد شده‌است که راهکار مناسبی برای رسیدگی به این محدودیت‌ها ایجاب می‌کند. الگوریتم NRGA نیز چون جزء جدیدترین الگوریتم‌های ارائه شده در زمینه بهینه سازی چندهدفه می‌باشد مورداستفاده قرار گرفته‌است.
2-4-2-1- الگوریتم ژنتیک مرتب سازی نامغلوب
دب73 و همکارانش [14]، یک نخبه گرایی دسته بندی یا مرتب سازی نامغلوب را در الگوریتم‌های ژنتیک پیشنهاد دادند. در اغلب مواقع، این الگوریتم شباهتی به NSGA ندارد، ولی مبتکران نام NSGA-II را به دلیل نقطه پیدایش آن، یعنی همان NSGA، برای آن حفظ کردند.
در این روش، ابتدا جمعیت فرزندان، ، با استفاده از جمعیت والدین، ، ساخته می‌شود. در اینجا به جای پیدا کردن جواب‌های نامغلوب از ، ابتدا دو جمعیت با یکدیگر ترکیب شده و جمعیت با اندازه 2N را ایجاد می‌کنند. سپس از یک مرتب سازی نامغلوب برای دسته بندی تمام جمعیت استفاده می‌شود، البته این مرتب سازی، نسبت به مرتب سازی بر روی ، به تعداد مقایسه بیشتری نیاز دارد. در این شیوه، یک مقایسه عمومی در بین اعضای که مجموع دو جمعیت فرزندان و والدین است، انجام می‌شود و پس از ایجاد صف‌های متفاوت نامغلوب، به ترتیب اولویت (اولویت صفها نسبت به هم) جمعیت بعدی، یکی یکی از این صف‌ها پر می‌شود. پر کردن جمعیت ، با بهترین صف نامغلوب شروع شده و سپس به ترتیب با دومین صف نامغلوب و همین طور سومین و الی آخر، تا زمانی که پر شود، ادامه می‌یابد. از آنجا که اندازه برابر 2N است، تمام اعضای آن ممکن است نتوانند در قرارگیرند و به راحتی جواب‌های باقیمانده را حذف خواهیم کرد. شکل (2-3) نحوه عمل الگوریتم NSGA II را نمایش می‌دهد.

شکل 2-3- نمایشی از نحوه عملکرد NSGA-II
درمورد جواب‌هایی که در صف آخر با استفاده از عملگر نخبه گرایی ازبین می‌روند، باید مهارت بیشتری به کار برده و جواب‌هایی که در ناحیه ازدحام کمتری قراردارند را حفظ کرد. درواقع برای رعایت اصل چگالی در بین جواب‌ها، جواب‌هایی که در ناحیه ازدحامی کوچکتری هستند، برای پر کردن ، در اولویت قرار دارند.
یک استراتژی شبیه بالا در پیشرفت مراحل اولیه از تکامل الگوریتم، تأثیر زیادی نخواهد داشت، چرا که اولویت‌های زیادی در جمعیت ترکیب شده از فرزندان و والدین وجود دارد. احتمالاً جواب‌های نامغلوب زیادی وجود دارند که آماده قرارگرفتن در جمعیت قبل از آن که اندازه‌اش از N تجاوز کند، می‌باشند. یک مسأله مهم و در عین حال سخت این است که مابقی جمعیت چگونه باید پر شود؟ اگرچه درخلال مراحل بعدی شبیه سازی الگوریتم، احتمالاً بیشتر جواب‌های موجود در جمعیت با اندازه 2N، در رده جواب‌هایی با بهترین درجه نامغلوب بودن قرار می‌گیرند و تعداد آن‌ها از N متجاوز خواهد شد، اما الگوریتم بالا با یک راهکار موقعیتی انتخاب، وجود مجموعه متنوعی از جواب‌ها در جمعیت را تضمین می‌کند. با چنین راهکاری، یعنی زمانی که به‌نحوی تمام ناحیه بهینه پارتو توسط جمعیت پوشانده می‌شود، در ادامه الگوریتم، جواب‌های گسترده تری را در فضای جواب فراهم خواهدآورد.
در ادامه، الگوریتم NSGA-II را به اختصار آورده ایم [15]:
گام 1: جمعیت فرزندان و والدین را با یکدیگر ترکیب کرده و را می‌سازیم:

جمعیت حاصل را با استفاده از یک مرتب سازی نامغلوب به صفوف دسته بندی می‌کنیم.
گام 2: قرارمی‌دهیم، i=1، سپس تا زمانی که ، عملیات زیر را تکرار می‌کنیم:

گام 3: روال مرتب سازی ازدحام74 را اجرا کرده و با استفاده از مفهوم فاصله ازدحام75، ارزشهای متفاوتی را برای از جواب‌های تعیین می‌کنیم.
گام 4: جمعیت فرزندان را از با استفاده از یک الگوریتم انتخاب مسابقه‌ای ازدحام76 و عملگرهای ترکیب و جهش ایجاد می‌کنیم.
گام سوم از الگوریتم بالا، مرتب سازی برحسب ازدحام جواب‌ها در صف i (منظور آخرین صفی است که احتمالاً برخی از جواب‌های موجود در آن نتوانسته‌اند در جمعیت قرار گیرند)، با بکارگیری مفهوم فاصله ازدحام انجام می‌شود. بنابراین، جمعیت به صورت نزولی تحت میزان بزرگی ارزش فاصله ازدحام مرتب شده و در گام چهارم یک عملگر انتخاب مسابقه‌ای ازدحام که مبنای مقایسه آن همان فاصله ازدحام است بکار برده می‌شود. لازم به ذکر است، مرتب سازی نامغلوب واقع در گام اول می‌تواند به همراه عمل پر کردن جمعیت به صورت موازی انجام شود. درواقع هر بار که یک صف نامغلوب، پیدا شده و تست می‌شود که ازنظر اندازه می‌تواند به جمعیت اضافه شود یا نه، درصورتی که نتواند، دیگر نیازی نیست که مرتب سازی بیشتری انجام دهیم. این موضوع، به کاهش زمان اجرا الگوریتم کمک می‌کند.
2-4-2-2- الگوریتم NSGA-II محدود شده
اگر در حین حل مسأله‌ای که باید حل شود، حل‌هایی ایجاد شود که با محدودیت‌های مسأله مغایرت داشته باشد و آن‌ها را نقض کند و درنتیجه غیرقابل قبول باشد، چگونه باید با این موضوع برخورد کرد؟ روش‌های مختلفی برای مقابله با این موضوع وجود دارد که از جمله آن‌ها می‌توان به توابع جریمه و یا نادیده گرفتن و حذف حل غیرقابل قبول ایجاد شده اشاره کرد.
الگوریتم CNSGA-II، همانند الگوریتم NSGA-II عمل می‌کند، تنها با این تفاوت که برای رسیدگی به محدودیت‌ها، روشی را برمی‌گزیند که براساس مفهوم غلبه و امتیازدهی عمل می‌کند [14].
این روش که به محدودیت رسیدگی می‌کند، از انتخاب تورنمنت دودویی77 استفاده می‌کند که دو حل از جمعیت، انتخاب و حل بهتر انتخاب می‌شود. باتوجه به محدودیتها، هر حل می‌تواند یا قابل قبول و یا غیرقابل قبول باشد. بنابراین، ممکن است حداکثر سه وضعیت به وجود آید:
1) هرد و حل قابل قبول باشند؛
2) یکی از حل‌ها قابل قبول و دیگری غیرقابل قبول باشد؛
3) هر دو حل غیر قابل قبول باشند.
برای مسائل بهینه سازی تک هدفه، از یک قانون ساده برای هر مورد استفاده می‌کنیم:
مورد 1) حلی که تابع هدف بهتری دارد را انتخاب می‌کنیم.
مورد 2) حل قابل قبول را انتخاب می‌کنیم.
مورد 3) حلی که کمترین انحراف از محدودیت‌ها را دارد انتخاب می‌کنیم. باتوجه به اینکه در هیچدام از موارد، اندازه تابع هدف و محدودیت‌ها با یکدیگر مقایسه نشده‌اند، هیچ نیازی به داشتن پارامترهای جریمه نیست، این موضوعی است که این رویکرد را مفید و جذاب کرده‌است.
درمورد مسائل بهینه سازی چندهدفه، دو مورد آخر می‌تواند همانطور که هستند استفاده شوند و مورد اول نیز می‌تواند با استفاده از اپراتور مقایسه ازدحام، حل شود. برای مقایسه کردن در این الگوریتم، تعریف «غلبه» را بین دو حل i و j تعریف می‌کنیم.
تعریف 1) حل i اگر یکی از وضعیت‌های زیر درست باشد، گفته می‌شود که از لحاظ محدودیت بر حل j غلبه دارد:
1) حل i قابل قبول است ولی حل j نیست.
2) حل i و j هر دو غیر قابل قبول می‌باشند، اما حل i انحراف از محدودیت کمتری دارد.
3) حل i و j قابل قبول هستند و حل i، حل j را مغلوب می‌کند.
اثر استفاده از مفهوم غلبه محدودیت این است که، هر حل قابل قبول، رتبه غیرمغلوبی بهتری از هر حل غیرقابل قبول دارد. همه حل‌های قابل قبول، باتوجه به سطح غلبه شان و براساس مقادیر توابع هدفشان رتبه بندی می‌شوند. به هر حال، از بین دو حل غیر قابل قبول، حلی که کمترین انحراف از محدودیت را دارد، دارای رتبه بهتری است. به هر حال، این اصلاح، در مفهوم غلبه، تغییری در پیچیدگی NSGA-II ندارد. بقیه فرایند CNSGA-II، همانطور که قبلاً درمورد
NSGA-II توضیح داده شد، اجرا می‌شود.
2-4-2-3- الگوریتم ژنتیک رتبه بندی نامغلوب
این الگوریتم که توسط الجدان78 و همکارانش [16] ارائه شده، الگوریتم انتخاب چرخ رولت رتبه‌بندی شده را با الگوریتم رتبه بندی جمعیت برمبنای پارتو ترکیب می‌کند. در این الگوریتم از الگوریتم انتخاب چرخ رولتی استفاده شده‌است که به هر عضو، یک اندازه برازش برابر با رتبه اش در جمعیت، تخصیص می‌دهد؛ بالاترین رتبه، بیشترین احتمال را دارد که انتخاب شود (درمورد ماکزیمم سازی).
این احتمال به صورت معادله زیر محاسبه می‌شود:
(29.2)
که N، تعداد اعضاء این جمعیت است. در این الگوریتم، اعضاء در یک جبهه، براساس فاصله ازدحامشان و جبهه ها براساس رتبه غلبه شان رتبه می‌گیرند.
الگوریتم NRGA، همان طور که سودوکد آن را در شکل (2-4) مشاهده می کنید، به این صورت است که ابتدا، یک جمعیت تصادفی والدین، P، ایجاد می‌شود. مرتب کردن جمعیت براساس غلبه است. به هر حل، برازشی (یا رتبه ای) برابر سطح غلبه اش، تخصیص داده می‌شود (1 برای بهترین سطح، 2 برای سطح بعدی و الی آخر).
1. Initialize Population P
2. { Generate random population-size N
3. Evaluate Objective Values
4. Assign Rank (level) Based on Pareto dominance-sort }
5. Generate Child Population Q
6. { Ranked based Roulette Wheel Selection
7. Recombination and Mutation }
8. for i=1 to g do
9. for each member of the combined population do
10. Assign Rank (level) Based on Pareto-sort
11. Generate sets of non-dominated fronts
12. Calculate the crowding distance between members on each front
13. end for
14. (eletist) Select the members of the combined population based on least dominated N solution to make the population of the next generation. Ties are resolvedby taking the less crowding distance.
15. Create next generation
16. { Ranked based Roulette Wheel Selection
17. Recombination and Mutation }
18. end for
شکل2-4- الگوریتم NRGA
بنابراین، فرض می‌کنیم که می‌خواهیم برازش را مینیمم کنیم. در ابتدا، از انتخاب چرخ رولت معمولی، اپراتورهای ترکیب و جهش را برای ایجاد جمعیت فرزندان، Q، با اندازه N، استفاده می‌کنیم. از این به بعد، برای مقایسه جمعیت جاری و بهترین حل‌های غیرمغلوبی که قبلاً استفاده کرده ایم، از نخبه گرایی استفاده می‌کنیم. روش کار بعد از تولید اولیه متفاوت خواهد بود.
این الگوریتم نشان می‌دهد که NRGA، ساده و سرراست است. در ابتدا، ترکیبی از جمعیت تشکیل می‌شود. اندازه جمعیت ترکیب شده، 2N است، بنابراین، جمعیت ترکیبی براساس غلبگی، مرتب می‌شود. بنابراین، همه اعضاء جمعیت فعلی و قبلی، در نخبه گرایی جمعیت ترکیبی استفاده می‌شوند. این فرایند، N حل را ازبین 2N حل انتخاب می‌کند.
جمعیت جدید که N عضو دارد، برای انتخاب استفاده می‌شود. حال، انتخاب چرخ رولت به صورت دو لایه اجرا می‌شود، یک لایه برای انتخاب جبهه، و لایه دیگر برای انتخاب حل از بین این جبهه. در اینجا، حل‌هایی که به بهترین مجموعه غیرمغلوب تعلق دارند، بیشترین شانس را برای انتخاب دارند. بنابراین، حل‌های مجموعه ، با احتمال کمتری نسبت به مجموعه انتخاب می‌شوند و این روند ادامه خواهد داشت. سپس، برای ایجاد جمعیت جدید P به اندازه N، جهش و تقاطع اجرا می‌شود. تنوع در حل‌های غیرمغلوب، بوسیله دومین لایه از انتخاب چرخ رولت براساس رتبه ایجاد می‌شود که در آن، حل‌ها براساس فاصله ازدحامشان (در همان لایه) رتبه بندی می‌شوند. حل‌های با کمترین فاصله ازدحام، بیشترین احتمال را دارند.
از این رو، حل‌ها با توجه به فاصله ازدحامشان (معیاری از چگالی حل‌ها

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