گوگل پلاس انجمن مکاریتم پایان نامه وبلاگ الگوريتم بهينه سازي گروه ذرات پيشنهادي pso
  • کارشناس انجمن مکاریتم
  • 2094 بازدید
  • 0 نظر
  • آموزش

انجام پایان نامه وانجام پایان نامه کارشناسی ارشدوانتخاب موضوع پایان نامه و ترجمه و مقاله و ثبت اختراع


الگوريتم بهينه ­ سازي گروه ذرات پيشنهادي( (PSO

الگوريتم فرا ابتکاري بهينه ­سازي گروه ذرات روش محاسباتي تکاملي مبتني بر جمعيت جواب­ها است. مانند ساير الگوريتم ­هاي فرا ابتکاري، الگوريتم مذکور ابزار بهينه ­سازيي است که مي­تواند براي حل انواع مختلفي از مسایل بهينه ­سازي به­ کار گرفته شود. اين الگوريتم از جديدترين روش­هاي فرا ابتکاري است که با الهام ­گيري از رفتار اجتماعي گروهي از پرندگان مهاجر که در تلاش براي دستيابي به مقصد ناشناخته ­اي هستند، توسط کندي و ابرهارت([1] (1995 در سال 1995 ميلادي توسعه داده شده است. در الگوريتم PSO ، جمعيت جواب­ها، گروه[2] ناميده مي­شود و هر جواب مانند يک پرنده در گروهي از پرندگان است و ذره[3] نام دارد و شبيه کرموزوم در الگوريتم ژنتيک است. تمامي ذرات داراي مقدار شايستگي[4] هستند که با استفاده از تابع شايستگي[5] محاسبه مي­گردند و تابع شايستگي ذرات بايد بهينه گردد. جهت حرکت هر ذره توسط بردار سرعت[6] آن ذره معين مي­شود. برخلاف الگوريتم ژنتيک، در فرايند تکاملي الگوريتم مذکور، پرندگان جديدي از نسل قبل (جواب­هاي جديد از جواب‌هاي قبلي) ايجاد نمي­گردد، بلکه هر پرنده رفتار اجتماعي خود را با توجه به تجربياتش و رفتار ساير پرندگان گروه تکامل بخشيده و مطابق آن حرکت خود را به سوي مقصد بهبود مي­دهد. به عبارت ديگر، در اين الگوريتم عملگرهاي تکاملي چون تقاطع ( Crossover ) و جهش ( Mutation ) وجود ندارد. ساختار كلي الگوريتم بهينه ­سازي گروه ذرات در شكل 1 ارائه شده است.

شکل 1. ساختار الگوريتم بهينه ­سازي گروه ذرات

الگوريتم PSO با گروهي از جواب­هاي (ذرات) تصادفي آغاز و سپس با به هنگام ­سازي ذرات در هر تکرار به دنبال جواب بهينه مي­گردد .اگر متغيرهاي تصميم و به نوبه آن موقعيت ذرات، از نوع صفر و يك باشند؛ بردارهاي سرعت و موقعيت هريک از ذرات در هر تکرار الگوريتم، طبق روابط (1) الي (4) محاسبه مي­شوند (انجل، 2012).

طبق رابطه (1) بردار سرعت جديد هر ذره بر اساس سرعت قبلي خود ذره (Vi(t-1) )، بهترين موقعيتي که ذره تاکنون به آن دست يافته است (pBesti ) و موقعيت بهترين ذره در همسايگي ذره که تابحال بدست آمده است (nBesti )، محاسبه مي‌گردد. در صورتي كه همسايگي هر ذره شامل تمام ذرات گروه باشد، آنگاه nBesti بيانگر موقعيت بهترين ذره در ميان گروه است كه با gBest به آن اشاره مي­شود. r1 و r2 دو عدد تصادفي (با توزيع يکنواخت بين [0,1] ) هستند که مستقل از يکديگر توليد مي­شوند. c1 و c2 که با نام ضرايب يادگيري به آنان اشاره شده است، تأثیر pBest و nBest را بر فرا يند جستجو کنترل مي­نمايند. w بيانگر ضريب وزني اينرسي است. بردار سرعت ذرات با مقدار Vmax محدود شده است. Vmax به عنوان محدوديتي است که قابليت جستجوي جهاني گروه ذرات را کنترل مي­کند. با استفاده از رابطه (3) بردار سرعت هريک از ذرات به بردار احتمال تغيير، تبديل مي­شود. در رابطه فوق، si بيانگر احتمال آن است که xit   برابر با 1 شود. سپس با استفاده از رابطه (4) بردار موقعيت هريک از ذرات بهنگام مي­گردد. در رابطه فوق، p عددي تصادفي با توزيع يکنواخت بين صفر و يک است.

ساختار کلي الگوريتم پيشنهادي در شکل 2 ارائه شده است. همانگونه که در شکل نشان داده شده است، ساختار پيشنهادي مبتني بر الگوريتم بهينه ­سازي گروه ذرات، طراحي شده است. مطابق با شكل 2، الگوريتم پيشنهادي از دو مرحله تشکيل شده است که مرحله اول خود متشکل از دو بخش مجزاست. در بخش نخست، ابتدا به تعداد SSize ذره با استفاده از روشي شبه تصادفي به عنوان ذرات اوليه، ايجاد مي­شوند. پس از آن، همسايگي تصادفي به اندازه NSize ذره، حول هر جواب اوليه، شکل مي­گيرد. در طي گام­هاي الگوريتم، کيفيت و پراکندگي جواب­ها بهبود مي­يابد و حداکثر به تعداد SSize ذره از جواب­هاي خوب و غيرتکراري انتخاب و در مجموعه­اي با نام مجموعه مرجع -براي استفاده در مراحل بعدي الگوريتم- قرار داده مي­شود. در پايان بخش نخست، جواب­هاي موجود در مجموعه مرجع به عنوان ذرات اوليه براي شروع بخش دوم در نظر گرفته مي­شوند. در صورتي که تعداد ذرات موجود در مجموعه مرجع کمتر از SSize ذره باشد، ذرات باقيمانده موردنياز به صورت تصادفي ايجاد و افزوده مي­شوند. در بخش دوم نيز فرا يند بهبود جواب­ها با مکانيزمي متفاوت ادامه مي­يابد و در هر تکرار الگوريتم جواب­هاي خوب و غيرتکراري در مجموعه مرجع قرار داده مي­شوند. در پايان بخش دوم، جواب­هاي موجود در مجموعه مرجع به عنوان ذرات اوليه براي شروع بخش نخست در نظر گرفته مي­شوند. در اين بخش نيز، در صورتي که تعداد ذرات موجود در مجموعه مرجع کمتر از SSize ذره باشد، ذرات باقيمانده موردنياز به صورت تصادفي توليد و اضافه مي­شوند. بخش اول و دوم، هر کدام به ترتيب پس از P1S1 و P1S2 مرتبه تکرار يا در صورتي که به ترتيب پس از طي CR11 و CR12 مرتبه تکرار در مقدار شايستگي بهترين جواب تغييري حاصل نشود، خاتمه مي­يابند. همچنين، مرحله اول الگوريتم -رويه تکرار پياپي بخش اول و دوم- پس از طي P1 مرتبه تکرار پايان مي­پذيرد. در پايان مرحله نخست الگوريتم، مجموعه مرجع تشکيل شده در طي اين مرحله، به عنوان جواب­هاي آغازين مرحله دوم الگوريتم، در نظر گرفته و الگوريتم وارد مرحله دوم مي­شود. در مرحله دوم، ابتدا با استفاده از مدل برنامه­ريزي خطي، مقادير بهينه متغيرهاي تصميم پيوسته با توجه به مقادير متغيرهاي صفر و يک  تعيين و از بين جواب­ها، بهترين جواب انتخاب مي­شود. پس از آن با استفاده از رويه جستجوي محلي کيفيت جواب منتخب بهبود مي­يابد. مرحله دوم الگوريتم، بعد از P2 مرتبه تکرار يا در صورتي که پس از CR2 مرتبه تکرار تغييري در مقدار بهترين ذره حاصل نگردد، خاتمه مي­يابد.

هرچند در تمام مراحل الگوريتم پيشنهادي مي‌توان مقادير متغيرهاي تصميم پيوسته را با استفاده از حل يک مدل برنامه­ريزي خطي بدست آورد؛ با وجود اين، به دليل افزايش سرعت الگوريتم، در مرحله اول، روشي تقريبي براي تعيين مقادير متغيرهاي تصميم پيوسته توسعه و استفاده مي­شود.

در مرحله اول الگوريتم، بردارهاي سرعت و موقعيت هريک از ذرات در هر تکرار الگوريتم، طبق روابط (1) الي (4) محاسبه مي­شوند. در بخش دوم از مرحله نخست الگوريتم، در رابطه (1) مقدار nBesti با مقدار بهترين ذره در ميان تمام ذرات (gBest ) جايگزين مي­شود.


شكل 2. ساختار الگوريتم بهينه ­سازي گروه ذرات پيشنهاد

نحوه نمايش ذرات:

يکي از مهمترين تصميماتي که در زمان طراحي يک الگوريتم فرا ابتکاري مي­بايستي اتخاذ شود، نحوه نمايش جواب­ها و نيز چگونگي برقراري ارتباطي مؤثر، يکتا و قابل شناسايي ميان جواب­ها و فضاي جستجوي مسأله مورد بررسي است که در زیر به صورت جزیی بررسی گردیده است.

توليد جواب­ هاي اوليه:

به طور کلي کيفيت جواب­هاي آغازين بر عملکرد الگوريتم ­هاي فرا ابتکاري تأثیر بسزايي دارد. بنابراين، طراحي روشي مؤثر براي توليد جواب­هاي اوليه از اهميت بالايي برخوردار است. از اين رو، در الگوريتم پيشنهادي، براي توليد ذرات اوليه، روشي شبه تصادفي طراحي شده است که با به­کارگيري آن ذرات بين دو حالت کمترين و بيشترين تعداد دفعات ارسال ايجاد شوند. گام­هاي رويه پيشنهادي براي توليد ذرات آغازين در زير تشريح شده است:

1-  تمام مؤلفه­هاي ذره نخست را برابر 1 قرار دهيد. اين ذره، ذره­اي با بيشترين تعداد دفعات ارسال و همواره شدني است. به عبارت ديگر، ذره نخست بيانگر حالتي است که در آن، در تمام دوره­ها توليد و در تمام دوره­ها و براي تمام خرده­فروشان ارسال داشته باشيم.

2-  با استفاده از رويه ارائه شده در شكل 3، ذره دوم را ايجاد کنيد. ذره دوم، ذره­اي با کمترين تعداد دفعات ارسال است. براي توليد ذره دوم، محدوديت انباشت که با استفاده از رابطه زیر بيان مي­شود، آزاد شده است.

شكل 3. شبه كد توليد ذره با كمترين تعداد دفعات توليد و ارسال

3-  ذره اول و دوم را به عنوان والد اول و دوم قرار دهيد. پس از آن، با استفاده از عملگر تقاطع پراکنده (Scattered crossover )ساير ذرات موردنياز را ايجاد کنيد. براي انجام عملگر تقاطع پراکنده، ابتدا يک آرايه تصادفي صفر و يک با اندازه برابر با اندازه ذرات ايجاد مي­گردد. مؤلفه i ام ذره فرزند (ذره جديد) اگر مؤلفه i ام آرايه تصادفي 1 بود، برابر با مؤلفه i ام والد 1 (ذره اول) و در غير اينصورت برابر با مؤلفه i ام والد 2 (ذره دوم) خواهد بود. نحوه انجام عملگر تقاطع پراکنده در شكل 5 ارائه شده است.

شكل 4. نحوه انجام عملگر تقاطع پراكنده

محاسبه مقادير شايستگي:

به طور معمول، در الگوريتم ­هاي فرا ابتکاري هر جواب در هر مرحله با استفاده از تابع شايستگي ارزيابي و مقدار شايستگي آن محاسبه مي­شود.

محاسبه مقدار شايستگي ذرات با استفاده از حل مدل برنامه­ريزي خطي تا حدي به زمان محاسباتي بالايي نياز دارد، بنابراين براي افزايش سرعت الگوريتم، فقط در مرحله دوم الگوريتم از اين روش استفاده مي­شود و براي محاسبه مقدار شايستگي در مرحله نخست الگوريتم، روشي تقريبي گفته شده استفاده  می شود.

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

 

ايجاد همسايگي تصادفي ذرات:

در مرحله نخست الگوريتم، به منظور افزايش پراکندگي ذرات و جستجوي مناطق بيشتري از محدوده جواب، با بهره­گيري از عملگر جهش، حول هر ذره همسايگي تصادفي تشکيل مي­شود. بدين منظور:

1-  تعداد NSize-1 کپي از ذره ايجاد مي­شود.

2-  به تعداد NSize-1 آرايه تصادفي صفر و يک، با تعداد مؤلفه­هاي برابر با مؤلفه­هاي يک ذره، ايجاد مي­گردد. HDRate درصد از مؤلفه­هاي آرايه توليدشده، به صورت تصادفي برابر 1 قرار داده مي­شود.

3-  مطابق با مؤلفه­هاي با مقدار 1 در آرايه تصادفي، مؤلفه متناظر در ذره کپي معکوس مي­گردد؛ به عبارت ديگر، مقدار 0 به 1 و بالعکس مقدار 1 به 0 تبديل مي­شود.

نمايي کلي از نحوه انجام عملگر جهش در شكل 5 ارائه شده است.

شكل 5. نحوه انجام عملگر جهش

 

 

 

 

 

بهبود همسايگي ذرات:

پس از ايجاد همسايگي ذرات، طي گام­هاي الگوريتم، جواب­هاي موجود در هر همسايگي مستقل از ذرات ساير همسايگي­ها بهبود مي­يابند. اما به منظور افزايش ميزان بهبود در کيفيت جواب­ها طي گام­هاي الگوريتم، لازم است ميان همسايگي­هاي مختلف ذرات، به گونه­اي تبادل اطلاعات صورت گيرد. بدين منظور، پس از بهنگام­سازي مقادير nBest در هر تکرار الگوريتم، با به­کارگيري روش انتخاب مسابقه( Tournament selection ) به تعداد 2SSize ذره از ميان ذرات nBest به عنوان والدين( Parent ) انتخاب مي­شوند. پس از آن با بهره­گيري از عملگر تقاطع پراکنده که در بخش قبل تشريح شد، SSize ذره جديد (فرزند(Child )) ايجاد مي­شود. ذرات جديد، جايگزين بدترين ذره در هر همسايگي مي­شوند.

تشکيل و بهنگام­سازي مجموعه مرجع (RSet ):

در ساختار الگوريتم پيشنهادي، در مرحله نخست الگوريتم، به منظور حفظ جواب­هاي غيرتکراري خوب در طي گام­هاي الگوريتم و همچنين به منظور فرا هم­سازي جواب­هاي اوليه با تنوع و کيفيت بالا براي گام­هاي آتي الگوريتم، مجموعه مرجع تشکيل مي­گردد. بدين منظور از ميان تمامي ذرات غيرتکراري موجود در گروه ذرات، حداکثر به تعداد SSize ذره با بهترين مقادير شايستگي انتخاب و در مجموعه مرجع قرار داده مي­شوند. در تکرارهاي بعدي الگوريتم، تنها ذراتي در مجموعه مرجع قرار مي­گيرند که تکراري نبوده و به مقادير شايستگي بهتري دست يافته باشند. رويه تشکيل مجموعه مرجع در دو بخش اول و دوم از مرحله نخست الگوريتم پيشنهادي، يکسان است.

متنوع­سازي ذرات:

در ساختار الگوريتم ، به منظور جلوگيري از همگرايي زودهنگام و ايجاد جواب­هاي اوليه با پراکندگي و کيفيت خوب براي مراحل بعدي الگوريتم، مکانيزم متنوع­سازي ذرات انجام مي­گيرد. به همين منظور، در بخش نخست مرحله اول الگوريتم، بهترين ذره در ميان مجموعه مرجع انتخاب و به تعداد MRate درصد از ذرات گروه، از ذره منتخب کپي ايجاد مي­شود. ذرات کپي با به­کارگيري عملگر جهش که در بخش قبل تشريح شد، تغيير مي­يابند و جايگزين بدترين ذرات گروه مي­شوند. با استفاده از اين روش، با اعمال تغيير تصادفي محدود در بهترين ذره گروه، با افزايش مؤلفه­هاي خوب در ميان جواب­ها، فرآيند جستجو بهبود مي­يابد.

 جستجوي محلي:

در مرحله دوم از ساختار الگوريتم پيشنهادي، پس از انتخاب بهترين ذره، کيفيت ذره منتخب با استفاده از جستجوي محلي بهبود مي­يابد. براي اين هدف، يکي از مؤلفه­هاي ذره به صورت تصادفي انتخاب و مقدار آن مؤلفه معکوس مي­شود؛ به عبارت ديگر، اگر مؤلفه برابر 1 باشد به 0 و بالعکس اگر 0 باشد به 1 تبديل مي­شود. بدين ترتيب ذره جديدي تنها با يک مؤلفه متفاوت نسبت به ذره اوليه بدست مي­آيد. با استفاده از مدل برنامه­ريزي خطي که در بخش قبل ارائه شد، مقدار شايستگي ذره جديد محاسبه مي­گردد. اگر مقدار شايستگي ذره جديد از ذره اوليه بهتر باشد، ذره جديد جايگزين ذره اوليه مي­شود و در غير اينصورت ذره جديد حذف و ذره اوليه بدون تغيير باقي مي­ماند. رويه مذکور حداکثر پس از P2 مرتبه تکرار يا در صورتي که در بهترين مقدار شايستگي که ذره بدان دست يافته است، طي CR2 تکرار متوالي بهبودي حاصل نشود، الگوريتم متوقف مي­گردد



جهت آشنایی با رویکرد مکاریتم به شرافت کاری مکاریتم مراجعه فرمائید



نظرات کاربران
نظر خود را درباره این مطلب ارسال کنید
 
 
 
 





فیسبوک موسسه انجام پایان نامه مکاریتم View Association of Mecharithm's LinkedIn profile لینکدین موسسه انجام پایان نامه مکاریتم View Mecharithm Associatoion's LinkedIn profile موسسه انجام پایان نامه و رساله دکتری Instagram Instagram