مقاله با موضوع رتبه بندی، نمونه برداری، ترتیب نزول

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

جبهه دوم قرار میگیرد. به همین ترتیب جبهههای بعدی نیز تشکیل مییابند. در زیرنحوه مرتب سازی نامغلوب سریع به صورت شکل و شبهکد۶۴ ارائه شده است.
شکل ۳-۱- نحوه مرتب سازی جواب های نامغلوب یک جمعیت

شکل۳-۲. شبهکد رویه مرتبسازی نامغلوب سریع
۳-۵-۲- رویه حفظ تنوع و پراکندگی
یکی از فاکتورهای مهم و تأثیرگذار بر عملکرد الگوریتمهای تکاملی، در جهت همگرایی به مجموعه جواب بهینه پارتو، داشتن رویکردی گسترش گرایانه در جستجوی جوابها، در فضای حل است. دستیابی به جوابهای با کیفیت بهتر، به کمک جوابهای متنوعتر امکانپذیر است. در واقع در شرایطی که دو جواب از نظر برازندگی وضعیت یکسانی را دارند، جوابی ترجیح داده میشود که نسبت به دیگر جوابهای جستجو شده جمعیت، از میزان پراکندگی بیشتری برخوردار باشد. از این رو، در الگوریتم NSGA-II نیز رویهای برای این منظور طراحی شده است. جهت تشریح این رویکرد، ابتدا مفهومی را تحت عنوان فاصله تراکمی ارائه میکنیم.

فاصله تراکمی۶۵
برای بدست آوردن تخمینی از چگالی جوابهای موجود در کنار یک جواب خاص، مانند جواب i ام در جمعیت، میانگین فاصله دو جواب واقع در طرفین جواب i ام برای هر کدام از M تابع هدف، محاسبه میشود. مقدار عددی di که از محاسبه تقریبی فضای مکعبی اطراف جواب i با بکار بردن نزدیکترین همسایههای آن بدست میآید را فاصله تراکمی مینامیم. در شکل (۳-۲) فاصله تراکمی جواب i ام برابر است با میانگین طول اضلاع مستطیلی که رئوس آن، نقاط مجاور جواب i ام میباشند.

برای محاسبه فاصله تراکمی جوابها، لازم است که ابتدا هر تابع هدف به ترتیب نزولی مرتب شود و بردار اندیسهای مرتب شده جوابها ایجاد گردد. سپس، برای جوابهای ابتدایی و انتهایی بردار اندیسهای مرتب شده، فاصله تراکمی، بینهایت مقداردهی میشود و برای مابقی، فاصله تراکمی هر جواب بر اساس تفاضل مقادیر تابع هدف جواب بعد و قبل آن در بردار اندیس، طبق رابطه زیر محاسبه میشود:
(۳-۳۸)
d_(I_j^m )=d_(I_j^m )+(f_m^((I_(j+1)^m))-f_m^((I_(j-1)^m)))/(f_m^max-f_m^min ) ; m=1,2,…,M
که در آن f_m^max و f_m^min به ترتیب بیشترین و کمترین مقدار بدست آمده برای تابع هدف m ام در جمعیت حاضر است و f_m^((I_(j+1)^m)) و f_m^((I_(j-1)^m)) بترتیب مقدار تابع هدف m ام برای جواب بعدی و قبلی جواب j ام در بردار اندیس مرتبشده تابع هدف m ام میباشند. ذکر این نکته لازم است که برای هر جواب j ام، دو جواب j+1 ام و j-1 ام بعنوان همسایگان جواب j ام، برای تمام توابع هدف یکسان نمیباشند. به ویژه برای M?3 همسایهها متفاوت خواهند بود. بعلاوه با توجه به ناهمسان بودن مقادیر توابع هدف، شکل نرمالیزهشده آنها در نظر گرفته شده است. در ادامه شبهکد مربوط به محاسبه فاصله تراکمی جوابها ارائه میگردد.

شکل۳-۳. شبهکد محاسبه فاصله تراکمی
با معرفی معیار فاصله تراکمی، برای مقایسه دو جواب، عملگری تحت عنوان عملگر مقایسه تراکمی ارائه میشود.
عملگر مقایسه تراکمی۶۶
عملگر مقایسه تراکمی (?_n) برای فرآیند انتخابی که در ادامه ذکر میشود، طراحی شده است. فرض میشود که هر جواب i دو ویژگی زیر را دارد:
یک رتبه یا درجه نامغلوب بودن که آن را با ri نشان میدهیم.
یک فاصله تراکمی محلی که آن را با di نمایش میدهیم.
فاصله تراکمی di یک اندازه از فضای جستجو حول جواب i است که توسط هیچ جواب دیگری از جمعیت اشغال نشده باشد. بر پایه دو ویژگی بیان شده، میتوانیم عملگر مقایسه تراکمی را با قاعده زیر تعریف کنیم:
تعریف: جواب i در مقایسه با جواب j پیروز میشود (i?_n j)، اگر و تنها اگر یکی از شرایط زیر برقرار باشد:
جواب i دارای رتبه بهتری باشد یا r_id_j.
شرط اول این اطمینان را بوجود میآورد که جواب پیروز از درجه نامغلوب بودن بهتری نسبت به حریف خود برخوردار است و شرط دوم که در هنگام همرتبه بودن جوابها با آن روبرو خواهیم شد، این اطمینان را میدهد که جواب پیروز از ناحیه تراکمی بزرگتری برخوردار باشد.
با مطالب ارائه شده در فوق میتوانیم مراحل الگوریتم NSGA-II را گام به گام تشریح سازیم.
۳-۵-۳- مراحل الگوریتم NSGA-II
ابتدا جمعیت اولیه والدین P_0 با اندازه N بصورت تصادفی ایجاد میشود. سپس جمعیت تولید شده، مرتبسازی نامغلوب گشته و جوابها در سطوح مختلفی از درجه نامغلوب بودن دستهبندی میشوند. به هر جواب بر حسب اینکه در چه جبههای قرار دارد، ارزش یا رتبهای اختصاص داده میشود (جوابهای جبهه اول که در پایینترین سطح قرار دارند رتبه یک، جوابهای جبهه دوم رتبه دو و به همین ترتیب بقیه رتبهبندی میشوند). در ادامه با استفاده از روش انتخاب مسابقه دودویی۶۷ مبتنی بر عملگر مقایسه تراکمی و عملگرهای تقاطع و جهش، جمعیت فرزندان Q_0 با اندازه N تولید میگردد. از ترکیب دو جمعیت والدین و فرزندان، جمعیت R_0=P_0?Q_0 با اندازه ۲N حاصل میشود. از جمعیت به دست آمده R_0 نسل بعد انتخاب میشود. از آنجا که الگوریتم رویکردی نخبه گرایانه دارد، مجدداً اعضای R_0 با روش مرتبسازی نامغلوب دستهبندی میشوند و پس از ایجاد جبهههای متفاوت از نظر درجه نامغلوب بودن، جمعیت نسل بعدP_1 با اندازه N بترتیب از جبهه اول به بعد به طریقی که در ادامه بیان میشود، پر میگردد. با ایجاد P_1 همان مراحلی که برای P_0 ذکر شد، انجام میشود و این حلقه تا رسیدن به شرط پایان و توقف الگوریتم ادامه مییابد. در نهایت جبهه اول حاصل از مرتبسازی R_t آخرین نسل، بعنوان مجموعه جوابهای بهینه پارتو معرفی میشود.
فرض میکنیم جمعیت R_t حاصل از ترکیب والدین P_t و فرزندان آن Q_t، مرتبسازی نامغلوب شده است و جبهههای F_i برای i=1,2,… ایجاد گشته است. اینک جوابهای موجود در جبهه اول F_1 بعنوان بهترین جوابهای موجود در نسل حاضر، اولین کاندید برای پیوستن به نسل بعد میباشند. اگر تعداد اعضای F_1 کمتر از N میباشد، همه آنها به P_(t+1) منتقل میشوند. مابقی اعضای P_(t+1) از F_2 و بعد از آن از F_3 و الی آخر انتخاب میشوند. این رویه ادامه دارد تا زمانی که F_l بعنوان آخرین جبههای که قرار است باقیمانده اعضای P_(t+1) از آن انتخاب گردد، در نظر گرفته شود. در این هنگام چون تعداد کل اعضای F_l از تعداد مورد نیاز باقیمانده بیشتر است، ابتدا اعضای F_l به ترتیب کاهش فاصله تراکمی مرتب میشوند و سپس تعداد مورد نیاز باقیمانده، از ابتدای این لیست انتخاب میگردند. شکل (۳-۸) این رویه را بهتر نمایش میدهد.

این مطلب مشابه را هم بخوانید :   تحقیق با موضوع گناهان کبیره و لواط و تفخیذ

در ادامه شبهکد تولید نسل بعد و فلوچارت کلیه مراحل الگوریتم آورده میشود.

شکل۳-۵. شبهکد رویه تولید نسل بعد

۳-۶-تشریح مراحل الگوریتم (۶۸NRGA)
الگوریتم NRGA از نظر ساختار شبیه الگوریتم NSGAII می باشد، تنها تفاوت این الگوریتم
با NSGAIIدر بخش استراتژی انتخاب و بخش مرتب کردن جمعیت و انتخاب برای نسل بعد می باشد که در ادامه دو بخش مذکور تشریح می گردد.
ابتدا تمام جواب های جمعیت را در مرزهای نامغلوب مرتب می کنیم به طوریکه اولین مرز دارای بهترین جواب ها در جمعیت می باشد. لذا اگر در این مرحله ما ۵ مرز نامغلوب برای جمعیت داشته باشیم به اولین مرز نمره ۵ و به پنجمین مرز، نمره۱ می دهیم. بنابراین هر چه امتیاز بالاتر باشد جواب ها بهتر می باشد. بعد از رتبه بندی مرزها، جواب های درون هر مرز را نیز براساس فاصله ازدحامی رتبه بندی می کنیم. بنابراین بعد از محاسبه فاصله ازدحامی برای تمام جواب های موجود در هرمرز، جوابی که بیشترین فاصله ازدحامی را دارد بیشترین رتبه وبه جواب با کمترین فاصله ازدحامی رتبه یک می دهیم. بدین ترتیب هر کدام از جواب های موجود در جمعیت دارای یک رتبه بندی دو لایه ای هستند، که رتبه اول آنها نشان دهنده رتبه مرز نامغلوبی است که آن جواب در آن مرز قرار دارد و رتبه دوم نشان دهنده رتبه جواب براساس فاصله ازدحامی در آن مرز می باشد.
کاربرد عملگر مقایسه انبوهی برای دو جواب مفروض iوj در جمعیت بدین ترتیب است که درابتدا، مقایسه میان رتبه های مربوط به مرزهای نامغلوبی که این جواب ها درآن قرار دارد انجام می شود. اگر رتبه مرزی که جواب i ام در آن قرار دارد بیشتر باشد، آنگاه جواب iام برای تولید مثل در نسل بعد احتمال انتخاب بیشتری پیدا می کند. حال اگر هر دو جواب در یک مرز غیر مغلوب قرار داشته باشد، جوابی که دارای فاصله ازدحامی بیشتری است احتمال انتخاب بیشتری پیدا می کند. درواقع علت اینکه فاصله ازدحامی بیشتر، احتمال انتخاب بیشتری می گیرداین است که مابا این کاراحتمالاً نقاط بیشتری را در مناطقی که شلوغی کمتری دارند پیدا می کنیم. به عبارت دیگر این امر منجر به یکنواختی پراکندگی جواب ها در مرز نامغلوب نسل بعدی خواهد شد.در این بخش، از عملگر چرخه رولت مبتنی بر رتبه بندی۶۹ (RRWS) به جای استفاده از عملگر مسابقه ای ازدحام استفاده می کنیم به صورتی که در ادامه آورده شده است.
ساده ترین راه برای انتخاب، انتخاب به روش چرخ رولت می باشد. این روش یک نمونه برداری شانسی با جایگزینی است. این روش مبتنی بر شانس به این صورت انجام می شود که کلیه افراد بر مبنای میزان برازندگی خود بر روی نواحی همجوار یک خط نگاشت می شوند. اندازه ناحیه مربوط به هر فرد با توجه به اندازه برازندگی آن تعیین می شود. سپس یک عدد تصادفی تولید شده و با توجه به اندازه این عدد، فرد انتخاب می شود. این فرآیند آنقدر تکرار می شود تا اینکه تعداد مورد نظر والدین) جمعیت تولید مثلی( تامین گردد. می توان به جای خط از یک دایره به این منظور استفاده نمود.
انتخاب چرخ رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب ترین انتخاب های تصادفی بوده که ایده آن، احتمال انتخاب می باشد. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگی آن محاسبه شده که اگر مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
(۳-۳۹) P_k= f_k/(?_(i=1)^n?f_i )
حال کروموزوم ها را مرتب کرده، که همان مقادیر تجمعی می باشد به صورت زیر به دست می آید :

q_k=?_i^k?p_i (3-40)

چرخ رولت به این صورت عمل می کند که برای انتخاب هر کروموزوم یک عدد تصادفی بین یک و صفر تولید کرده و عدد مذکور در هر بازه ای قرار گرفت، کروموزوم متناظر با آن انتخاب می شود. البته روش پیاده کردن چرخ رولت به این شکل است که یک دایره در نظر گرفته و آن را به تعداد کروموزوم ها طوری تقسیم می کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوط باشد. حال چرخ را چرخانده و هر

دیدگاهتان را بنویسید