در طی چند نسل متوالی هیچگونه بهبودی دریافتن بهترین شایستگی ایجاد نگردد و یا تا زمان مشخصی تغییری نکند.
میتوانیم ترکیبی از موارد فوق را به عنوان شرط خاتمه به کار ببندیم.
۳-۷ الگوریتم تجمع ذرات( Particle Swarm Optimization)
الگوریتم تجمع ذرات که بهاختصار به آن PSO نیز میگویند، یک الگوریتمی هوشمند و مبتنی بر ازدحام است که تحت تأثیر رفتار اجتماعی جانوران میباشد، همانند ازدحام پرندگان هنگام یافتن یک منبع غذایی یا دستهای از ماهیان که از خود در برابر دشمن محافظت میکنند. یکذره در PSO متقارن است با یک پرنده یا ماهی که در فضای جستجو (مسئله) در حال جستوخیز و حرکت میباشد. موقعیت هر ذره در هرلحظه زمانی تحت تأثیر بهترین موقعیت خودش و موقعیت بهترین ذره در یک فضای مسئله است. عملکرد و کارایی یکذره توسط مقدار تناسب اندازهگیری میشود که مخصوص مسئله میباشد.
برای فهم الگوریتم به مثال زیر توجه نمایید:
فرض میکنیم که ما برای اینکه در درس خود پیشرفت داشته باشیم دو کار را میتوانیم انجام دهیم یا اینکه بر اساس تجربیات خود جلو رویم و یا از تجربیات شخصی دیگر الگوبرداری کنیم. اگر به دنبال تجربیات خود برویم یک تصمیم خودخواهانه را انجام دادیم یعنی به دانش خود اعتماد کامل داریم و ممکن است دانش ما اشتباه باشد و اگر فقط از تجربهی شخصی دیگر الگوبرداری کنیم ممکن است یک خودباختگی برای ما پیش آید که به دانش خود اعتماد نداریم. بهترین کار این است که از ترکیب این دو استفاده کنیم.
در الگوریتم pso ما np تا ذره داریم که در فضای مسئله بهصورت کاملاً تصادفی پخش گردیدهاند و هر ذرهای برای خود یک موقعیت و هزینهای دارد.
برای جابجایی هر ذره از ترکیب خطی تجربیات خود و تجربیات الگو استفاده میکنیم:
xi_jadid=xi_ghadim + Vi_jadid (3-1)
که V سرعت حرکت ذره است که از فرمول زیر به دست میآید:
Vi_jadid=c1r1(xi_localBest – xi_ghadim) +c2r2 (x_globalBest – xi_ghadim) + wvi_ghadim
(۳-۲)
xi_localBest تجربیات خودمان و x_globalBest تجربیات شخص الگو میباشد. برای هر ذرهای یک xi_localBest و برای تمام ذرات یک x_globalBest داریم.
c1, c2 ضریبهای تصمیمگیری میباشند بیانکننده این موضوع هستند که کدامیک برای ما بیشتر اولویت دارد و اینکه بیشتر به سمت تجربیات خود حرکت کنیم یا به سمت تجربیات شخص الگو که در پیادهسازیها معمولاً c1+c2=4 در نظر میگیرند مثلاً:
c1=c2=2 (3-3)
r1 و r2 هم اعداد تصادفی که از توزیع یکنواخت بین صفر و یک به دست میآیند و معادل دستور rand در متلب میباشند.
wvi_ghadim هم به ضریب اینرسی معروف است و در نظر داشته باشید در الگوریتم pso دو ضریب اول مهم هستند و میتوانیم از ضریب اینرسی چشمپوشی کنیم.
اول np ذره را در فضای مورد جستجو بهصورت کاملاً ً تصادفی قرار داده و سپس برای هر ذرهای نسبت به موقعیت آن ذره، هزینهاش را حساب میکنیم. برای جابهجایی موقعیت هر ذره از فرمول بالا
استفاده میکنیم و در گام اول xi_localBest مقدار ذره و برای x_globalBest بهترین مقدار ذرهبین تمام ذرات میباشد. طبق فرمول بالا موقعیت هر ذره و هزینه آن آپدیت میگردد. بعد از آپدیت شدن موقعیت هر ذره نوبت به آپدیت کردن نقاط xi_localBest و x_globalBest میرسد. برای هر ذره تصمیم میگیریم که آیا هزینه موقعیت جدید از xi_localBest آن بهتر است یا نه اگر بهتر بود xi_localBest را آپدیت میکنیم و درنهایت موقعیت بهترین ذره را در x_globalBest قرار میدهیم و این فرایند را به تعداد مشخصی تکرار میکنیم.
۳-۸ الگوریتم رقابت استعماری
شکل ۳-۶ شمای کلی الگوریتم رقابت استعماری[۴۹] (ICA) را نشان میدهد.
الگوریتم رقابت استعماری نیز مانند سایر الگوریتمهای تکاملی، دارای چندین جمعیت اولیه میباشد. به هر عنصر جمعیتی، یک کشور میگویند. در کشورها از مفاهیم مستعمره و استعمارگر استفاده میکنیم. هر استعمارگر، با توجه به قدرت خود، تعدادی کشور (مستعمره) را کنترل میکند. هسته اصلی در این الگوریتم را سیاست جذب و رقابت استعماری، تشکیل میدهد. شکل ۳-۷ حرکت دادن مستعمرات یک امپراطوری را نشان میدهد.
شکل ۳-۶: الگوریتم رقابت استعماری [۶]
شکل ۰‑۷: حرکت مستعمرات به سمت امپریالیست [۶]
اگر در حین حرکت، موقعیت مستعمره از استعمارگر بهتری شود جای آنها باهم عوض میگردد. از مجموع قدرتهای کشور استعمارگر بهعلاوه درصدی از قدرت میانگین مستعمراتمان، قدرت کل یک امپراطوری بیان میشود.
(۳-۴)
در حین رقابت استعماری، امپراطوریهای ضعیفی که قدرت خود را ازدستدادهاند، از بین میروند. میروند. در رقابت استعماری باگذشت زمان حالتی پیش میآید که تنها یک امپراطوری در دنیا وجود دارد که آن را اداره میکند و این حالت درزمانی اتفاق میافتد که الگوریتم رقابت استعماری با رسیدن به نقطه بهینه تابع هدف، متوقف شود. شکل ۳-۸ زیر شمای رقابت استعماری را بیان میکند.
شکل ۳-۸: شمای کلی رقابت استعماری [۶]
۳-۹ حل مسئله زمانبندی با بهره گرفتن از الگوریتم ترکیبی
مسئله زمانبندی وظایف مستقل شامل n وظیفه و m ماشین میباشد که هر وظیفه باید با هرکدام از ماشینها مورد پردازش قرار بگیرد بهطوریکه زمان انجام کار کمینه شود. ICA اورجینال برای مقادیر حقیقی و فضاهای پیوسته تعریفشده بود درصورتیکه زمانبندی وظایف گسسته میباشد بنابراین نسخه گسسته این الگوریتم]۳۱[موردنیاز است. در این نسخه الگوریتم ICA با ترکیب شدن با الگوریتمهای ژنتیک و ازدحام ذرات، به حالت فضای گسسته تبدیل میشود.
الگوریتم ترکیبی را با افزودن گروه دیگری به نام کشورهای مستقل بررسی میکنیم. علیرغم ایده اصلی الگوریتم ICA که مبتنی بر استعمارگر و کلونی(مستعمره) بود، یک گروه از کشورهای بیطرف و صلحآمیز در اینجا در نظر گرفتهشده است. این کشورها متحده هستند و با بهره گرفتن از هوش ازدحامی با همدیگر ارتباط برقرار میکنند.
-
- ۱. تولید جمعیت اولیه
جمعیت اولیه در این الگوریتم بهصورت تصادفی تولید میشوند. هر کشور یک آرایه با ابعاد ۱*n میباشد که در آن n تعداد وظایف ورودی میباشد. مقادیر موجود در هر کشور، تعداد منابع هستند. شکل ۳-۹ یک مثال از مسئله زمانبندی مستقل را نشان میدهد. در این مثال ۹ وظیفه و ۳ منبع داریم که وظایف T1 , T2 , T6 و T9 روی منبع R3 اجرا میشوند. هزینه هر کشور مطابق رابطه زیر میباشد.
fitness (country) = makespan (country) (3-5)
شکل ۳-۹ مسئله زمانبندی با ۹ وظیفه و ۳ منبع [۱۴]
مطابق تابع هزینه، کمترین زمان اجرای کشورها برای راهحل ارائهشده جهت حل مسئله زمانبندی مناسبتتر است. در جمعیت اولیه، به تعداد Nimp کشور (آنهایی که کمترین هزینه رادارند) را به عنوان امپریالیست و به تعداد Nind کشور( آنهایی که از میان کشورهای باقیمانده بهترین هستند ) را به عنوان کشورهای مستقل و باقیمانده کشورها را که در مستعمره امپریالیستها هستند را با Ncol نشان میدهیم. کلونیها در میان استعمارگرها بهتناسب قدرت استعمارگرها تقسیم میشوند. برای انجام این کار هزینه نرمال Ci از هر استعمارگر i بر اساس هزینه همه استعمارگرها محاسبه میشود. معادله زیر:
Ci = maxj(cj) – ci (3-6)
که در آن ci، هزینه استعمارگر i و maxj(cj) ، بیشترین هزینه استعمارگرها میباشد. استعمارگری با بالاترین هزینه ( ضعیفترین آنها ) کمترین هزینه نرمال را خواهد داشت. با بهره گرفتن از هزینه نرمال، قدرت نرمال Pi هر استعمارگر توسط معادله ۵ به دست میآید. این مقادیر در فرایند پخش مستعمرهها کاربرد دارند.
تعداد N.Ci از کلونیهای آغازین استعمارگر i سپس مطابق معادله زیر تعریف میشود:
N.Ci = round(Pi * Ncol) (3-6)
که در آن round ، تابعی است که نزدیکترین عدد صحیح یک مقدار اعشاری را تولید میکند. تعداد اولیه کلونیها برای هر استعمارگر بهطور تصادفی انتخاب میشود، بعد از مشخص شدن وضعیت اولیه استعمارگرها، رقابت استعماری آغاز میشود و فرایند تکامل تا رسیدن به شرایط توقف، ادامه مییابد.
مرحله ۲. اعمال الگوریتم ژنتیک برای هرکدام از کلونیهای موجود در امپریالیستها
با الهام گرفتن از الگوریتم ژنتیک، عملگرهای این الگوریتم (انتخاب، تلفیق و جهش) جهت متنوع ساختن جمعیت امپریالیستها روی کلونیها اعمال میشوند.
۱) عملگر انتخاب بالاترین رتبه: در این روش، اولین کلونی که بیشترین سازگاری را داشته باشد انتخاب میکنیم درحالیکه بقیه بهطور تصادفی انتخاب میشوند. این روش کلونیها را با گرفتن خصوصیات خوب از کلونی با بیشترین سازگاری، بهبود میبخشد.
۲) عملگر تلفیق تک نقطهای: در تلفیق تک نقطهای یک موقعیت تلفیق (k) بهطور یکپارچه و تصادفی در دورههای [۱,۲,…,Nvar – ۱]، انتخاب میشود. سپس متغیرها میان کلونیهای موجود در آن نقطه تعویض و مبادله میشوند و دو کلونی جدید ایجاد میشود. شکل (۳ -۱۰)این فرایند را نشان میدهد.
شکل (۳-۱۰) فرایند تلفیق تک نقطهای [۱۴]
با این عملگر تلفیق، طرح ژنتیکی بهتر در یک کشور با احتمال تلفیق از پیش تعیینشده (Pc) از نسل جاری به نسل بعدی به ارث برده میشود. هنگامیکه دو کلونی والد در یک بهینه محلی واقع شوند، عملگر تلفیق، شانس پرش فرزند را از بهینه محلی فراهم میکند. در این الگوریتم وقتیکه تلفیق میان دو کلونی نتیجه بدی داشته باشد، به مرحله قبل از تلفیق و کلونی قبلی بازمیگردیم.
فرم در حال بارگذاری ...