سامانه پژوهشی – تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه-  …

سامانه پژوهشی – تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه- …

در لیست فعالیت های IDیعنی λD ، ژن های (موقعیت های) i=1,…, q1 از مادر عیناً انتقال میابند.
یعنی قرار می دهیم:
jiD:=jiM (۳-۲۶)
بخش دیگر لیست فعالیت ها، یعنی محتوی ژن های (موقعیت های) i=1,…, q1 در λD از پدر گرفته می شود، بدین ترتیب که از سمت راست لیست فعالیت های پدر شروع کرده و فعالیت ها را جایگزین می کنیم و فقط توجه داشته باشید، فعالیتهائی که در حال حاضر از مادر گرفته شده اند، مجددا انتخاب نمی شوند.
jiD:=jkjkF  { j1D ,…, ji-1D } (۳-۲۷)
توجه داشته باشید با این پروسه، در روابط پیش نیازی هیچ گونه خللی به وجود نمی آید و ترتیب فعالیتها در کروموزوم ایجاد شده به گونه ایست که قید روابط پیش نیازی را ارضا کرده و به اصطلاح جایشگت شدنی از فعالیت ها بدست می آید.
در سطر دوم کروموزوم، مد فعالیتها در موقعیت i=1,…,q2 کروموزوم دختر ID ، از تخصیص مُد مادر گرفته می شود. یعنی قرار می دهیم
µD(jiD):=μM(jiD) (3-28)
مد فعالیتهای باقی مانده در موقعیت i=q2+1,…,J کروموزوم دخترID، از تخصیص مُد پدر گرفته می شود.
µD(jiD):=μF(jiD) (3-29)
کروموزوم پسر IF نیز از مادر و پدر به همین ترتیب بدست می آیند، با این تفاوت که موقعیت i=1,…, q1 در لیست فعالیت های کروموزوم پسر Sλاز پدر گرفته می شود و باقیمانده از مادر گرفته می شود. به طور مشابه برای تخصیص مُد کروموزوم پسرSμتا موقعیتq2از تخصیص مُد کروموزوم پدرFμگرفته شده و بقیه از مادر Mμگرفته شده است.
برای نشان دادن تعاریف بالا مثال زیر را در نظر بگیرید. این کروموزوم های مادر و پدر (۳۰-۳) تشکیل شده اند. ما در اینجا ۴=q2 و ۳=q1در نظر گرفتیم.
(۳۰-۳)
برای مثال در کروموزوم دختر یعنی ID، سه ژن (موقعیت) اول در لیست فعالیت ها از لیست فعالیت های مادر Mλگرفته شده و فعالیت های باقی مانده از لیست فعالیت های پدرFλانتخاب می شوند. بر طبق عددی که برای qانتخاب شده، تخصیص مُد چهار فعالیت اول کروموزوم دخترID، از تخصیص مُد مادر Mμ، و مابقی از تخصیص مُد پدرFμ، گرفته می شوند.
عملگر جهش[۱۸۷]
با اجرای عملگر آمیزش، جمعیتی مختلط متشکل از والدین و فرزندان ایجاد می شود. اکنون در این مرحله، جهش محتوی یک ژن (موقعیت) را در کروموزوم انتخاب شده به صورت تصادفی تغییر می دهد. این عمل به منظور افزایش تنوع در جمعیت و یافتن اعضای گم شده صورت می گیرد. به علاوه اینکه عملگر جهش از افتادن الگوریتم در دام جواب های بهینه محلی جلوگیری می کند. در اینجا عملگر جهش در هر دو بخش کروموزوم (لیست فعالیت ها λ و تخصیص مُد μ) به صورت جداگانه با احتمال Pmut=0.05 اعمال میشود.
در مورد اول برای اعمال جهش در لیست فعالیت ها λ، یک فعالیت (ژن) به صورت راندوم انتخاب می شود. موقعیت جدید این فعالیت بین بالاترین موقعیت پیش نیاز های آن و پایینترین موقعیت پس نیازهای آن می باشد. این موقعیت به صورت راندوم از موقعیت های ممکن انتخاب می شود. برای درک بهتر این موضوع کروموزوم دختر (۳۰-۳) را در نظر بگیرید. فعالیت ۴ در ژن (موقعیت) دوم لیست قرار دارد. با توجه به شبکه فعالیت های شکل (۲-۳) فعالیت ۲ تنها پیش نیاز و فعالیت ۶ تنها پس نیاز این فعالیت می باشند. این فعالیت ها در لیست فعالیت های کروموزوم دختر در ژن های (موقعیت) اول و ششم قرار گرفته اند. در نتیجه عملگر جهش به گونه ای تعریف شده است که فعالیت ۴ بتواند یکی از موقعیت های دوم، سوم، چهارم و پنجم را به صورت تصادفی انتخاب کند. ما در اینجا فرض می کنیم ژن (موقعیت) پنجم به صورت راندوم انتخاب شده است. کروموزوم یافته در (۳۱-۳) آورده شده است.
(۳-۳۱)
توجه شود با توجه به این راهکارها بعد از اعمال جهش در لیست فعالیت ها، همچنان ترتیب فعالیتها به گونه ای است که از روابط پیش نیازی تخطی نمی کنند. همچنین در این انتقال، فعالیت مُد تخصیص داده شده به خود را حفظ می کند و تغییری در مُد فعالیت بوجود نمی آید.
برای اعمال جهش در تخصیص مُد ها μ، یک ژن به صورت راندوم انتخاب می شود و در صورتی که فعالیت بیش از یک مُد اجرا داشته باشد، یک مُد دیگر از مجموعه مُد های فعالیت Mj، به آن فعالیت تخصیص میابد.
مرتب سازی اعضا بر مبنای مفهوم چیرگی
در الگوریتم NSGA-II بعد از آنکه کروموزوم های فرزندان از اعمال آمیزش و جهش تولید گردیدند، جمعیت والدین (Pt) با جمعیت فرزندان (Qt) آمیخته شده و جمعیت مختلط (Rt) حاصل می شود. در ادامه برای مرتب سازی اعضای جمعیت مختلط بر مبنای مفهوم چیرگی، ابتدا باید مقادیر تابع هدف معرفی شده ، برای هر یک محاسبه صورت گیرد. مدت زمان تکمیل پروژه، هزینه کل پروژه و تسطیح منابع، سه هدفی هستند که میزان شایستگی اعضا بر پایه آنها سنجیده می شوند.
اعضای جمعیت مختلط (Rt)که حاصل ترکیب جمعیت والدین و فرزندان می باشد، باید بر طبق میزان شایستگی هر یک که با توجه به دو تابع هدف اشاره شده در بخش ۴-۳ سنجیده می شود، مرتب سازی شده و جبهه های پارتوی مختلف بر اساس روش Goldberg تعیین گردد.
اعضای جمعیت در داخل دسته هایی قرار گرفته به گونه ای که اعضای موجود در دسته اول، یک مجموعه کاملاً غیرمغلوب توسط دیگر اعضا جمعیت فعلی می باشند. اعضای موجود در دسته دوم نیز بر همین مبنا تنها توسط اعضای دسته اول مغلوب شده و این روند به همین صورت در دسته های دیگر ادامه یافته تا به تمام اعضای موجود در هر دسته، یک رتبه برمبنای شماره دسته اختصاص داده شود.
شکل ۴-۳- رتبه بندی بر مبنای شماره دسته
در این مدل برای مرتب سازی اعضا در جبهه های پارتو از رویکرد مرتب سازی سریع[۱۸۸] استفاده می شود.
 
برای هر عضو p از جمعیت p مراحل زیر را انجام می گیرد:
S(p)=[∅] قرار می گیرد؛ این مجموعه تمام اعضائی را که عضو p بر آنها چیره می شود را ذخیره می کند.
n(p)=0 قرار می گیرد؛ این متغیر تعداد اعضائی را که بر p چیره می شوند را ذخیره می کند.
برای هر عضو q در جمعیت p:
– اگر p بر q چیره شد؛ q به s(p) اضافه می شود.
– اگر q بر p چیره شد؛ یک واحد به n(p) اضافه می شود.
(n(p)=n(p)+1)
اگر n(p)=0 باشد، بدین معنی است که هیچ عضوی بر p چیره نشده است. پس p به اولین جبهه ی پارتو متعلق است و pبه F(1) اضافه می گردد.(F مجموعه ذخیره کننده جبهههای پارتو می باشد.)
مراحل بالا برای همه اعضای جمعیت p انجام می گیرد.
متغیر i به عنوان شمارنده جبهه های پارتو استفاده می شود. i=1 قرار می دهیم.
مراحل زیر تا زمانی ادامه پیدا می کند که i-امین جبهه پارتو خالی از عضو نباشد.(F(i)≠[∅])
Q=[∅]؛ (این مجموعه در جهت مرتب کردن اعضای جبهه های پارتو th(i+1) استفاده میشود.)
برای هر عضو p در جبهه ی F(i)
برای هر عضو q در مجموعه s(p). s(p) مجموعه ایست که اعضائی را که p بر آنها چیره شده است را ذخیره می کند.)
۱- n(q)=n(q)-1، شمارنده تعداد اعضای چیره شده بر Q یک واحد کاهش پیدا می کند.
۲- n(q)=0 باشد، آنگاه هیچ عضوی در جبهه های بعدی بر q غلبه نمی کند. عضو q به مجموعه Q اضافه می گردد.
 
I=i+1. شمارنده جبهه های پارتو یک واحد افزایش پیدا می کند.

این مطلب را هم بخوانید :
بررسی عوامل موثر بر وفاداری مشتری در صنعت تکمیل فرش (مطالعه موردی در ...

برای دانلود متن کامل این فایل به سایت torsa.ir مراجعه نمایید.
برچسب گذاری شده با: