روش بهینه‌سازی ازدحام ذرات

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مقدمه[ویرایش]

روش PSO یا به لاتین (Particle swarm optimization) یک روش سراسری کمینه‌سازی است که با استفاده از آن می‌توان با مسائلی که جواب آنها یک نقطه یا سطح در فضای n بعدی می‌باشد، برخورد نمود. در اینچنین فضایی، فرضیاتی مطرح می‌شود و یک سرعت ابتدایی به آنها اختصاص داده می‌شود، همچنین کانال‌های ارتباطی بین ذرات درنظر گرفته می‌شود. سپس این ذرات در فضای پاسخ حرکت می‌کنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازهٔ زمانی محاسبه می‌شود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب می‌گیرند. علی‌رغم اینکه هر روش در محدوده‌ای از مسائل به خوبی کار می‌کند، این روش در حل مسائل بهینه‌سازی پیوسته موفقیت بسیاری از خود نشان داده است.

انواع الگوریتم ازدحام ذرات[ویرایش]

الگوریتم ازدحام ذرات پیوسته[ویرایش]

مقدمه[ویرایش]

الگوریتم PSO یک الگوریتم جستجوی جمعی است که از روی رفتار اجتماعی دسته‌های پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینه‌ی دسته به کار گرفته شد. در PSO، ذرات در فضای جستجو جاری می‌شوند. تغییر مکان  ذرات در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است. بنابراین موقعیت دیگر توده ذرات روی چگونگی جستجوی یک ذره اثر می‌گذارد. نتیجه‌ی مدل‌سازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل می‌کنند. ذرات از یکدیگر می‌آموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود می‌روند اساس کار PSO بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگی‌اش وجود دارد، تنظیم می‌کند.

در ادامه کمی به توضیح مفهوم هوش جمعی می­پردازیم.

هوش جمعی[ویرایش]

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

اولین الگوریتم ازدحام ذرات[ویرایش]

در سال 1995 ابرهارت و کندی براي اولین بار PSO به عنوان یک روش جستجوي غیر قطعی براي بهینه سازي تابعی مطرح گشت این الگوریتم از حرکت دسته جمعی پرندگانی که به دنبال غذا می­باشند، الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا مي­گردند. تنها يك تكه غذا در فضاي مورد جستجو وجود دارد. هر راه ­حل كه به آن يك ذره گفته مي­شود، PSO  در الگوريتم معادل يك پرنده در الگوريتم حركت جمعي پرندگان مي­باشد. هر ذره يك مقدار شايستگي دارد كه توسط يك تابع شایستگی محاسبه مي­شود. هر چه ذره در فضاي جستجو به هدف (غذا در مدل حركت پرندگان) نزدیكتر باشد، شايستگي بيشتري دارد. همچنين هر ذره داراي يك سرعت است که هدايت حركت ذره را بر عهده دارد. هرذره با دنبال كردن ذرات بهينه در حالت فعلي، به حركت خود در فضاي مساله ادامه مي­دهد.

به ا ين شكل است كه گروه ي از ذرات در آغاز كاربه صورت تصادفي به وجود مي آيند و با به روز كردن نسلها سعي در يافتن راه­حل بهينه مي­نمايند. در هر گام، هر ذره با استفاده از دو بهترين مقدار به روز ميشود. اولين مورد، بهترين موقعيتي است كه تاكنون ذره موفق به رسیدن به آن شده است. موقعیت مذكورشناخته و نگهداري ميشود که این بهترین مقدار نوستالژی آن ذره نیز گفته می­شود که آن را با pbest نمایش می­دهیم. بهترين مقدار ديگري كه توسط الگوريتم مورد استفاده قرار مي­گيرد، بهترين موقعيتي است كه تا كنون توسط جمعيت ذرات بدست آمده است که آن را gbest می­گوییم(هوش جمعی).

پس از يافتن بهترين مقادير، سرعت و مكان هر ذره با استفاده از رابطه 6 و 7به روز ميشود.

رابطه 6

رابطه 7 سمت راست معادله 6 از سه قسمت تشكيل شده است كه قسمت اول، سرعت فعلي ذره است () و قسمتهاي دوم () و سوم () میزان تغيير سرعت ذره و جهت آن به سمت بهترين تجربه شخصي (نوستالژی) و بهترين تجربه گروه (هوش جمعی) را به عهده دارند. اگر قسمت اول را در اين معادله درنظر نگيريم ()، آنگاه سرعت ذرات تنها با توجه به موقعيت فعلي و بهترين تجربه ذره و بهترين تجربه جمع تعيين مي‌­شود و عملا تاثیر سرعت کنونی و لختی آن حذف می شود. به اين ترتيب، بهترين ذره گروه، در جاي خود ثابت ميماند و سايرين به سمت آن ذره حركت ميكنند. در واقع حركت دسته جمعي ذرات بدون قسمت اول معادله 6، پروسه اي خواهد بود كه طي آن فضاي جستجو به تدريج كوچك ميشود و جستجويي محلي حول بهترين ذره شكل ميگيرد. در مقابل اگر فقط قسمت اول معادله 6 را در نظر بگيريم، ذرات راه عادي خود را ميروند تا به ديواره محدوده برسند و به نوعي جستجويي سراسري را انجام مي­دهند. پارامترهای c1 و c2 (مقدار آن حدود 2 است) میزان اهمیت و وزن هوش جمعی و نوستالژی را مشخص می‌­کنند. پارامتر

با صفر قرار دادن یا ندادن پارامترهای c1 و c2 سه حالت مختلف زیر به وجود می‌­آید.

·       هیچکدام از این دو پارامتر را صفر نگذاریم که می­شود pso با لختی سرعت، هوش جمعی و نوستالژی.

·       وزن نوستالژی را صفر کنیم و فقط براساس هوش جمعی و لختی عمل کنیم.

·       وزن هوش جمعی را صفر کنیم و فقط براساس نوستالژی و لختی عمل کنیم.

برای مقداردهی اولیه توسط رابطه 8 عمل می­کنیم. سرعت اولیه نیز طبق 9 صفر است.

رابطه 8

رابطه 9

شبه کد الگوریتم PSO :

For each particle
    Initialize particle
End For
Do
For each particle
    Calculate fitness value of the particle fp
    /*updating particle’s best fitness value so far)*/
    If fp is better than pBest
    set current value as the new pBest
End For
/*updating population’s best fitness value so far)*/
Set gBest to the best fitness value of all particles
For each particle
    Calculate particle velocity according equation
    Update particle position according equation
End For While maximum iterations OR minimum error criteria is not attained 

اما در مورد شرط توقف باید گفت که راه­های زیر موجود است.

·       تعداد تکرار معین

·       رسیدن به یک شایستگی آستانه

·       یک تعداد تکرار که شایستگی تغییر نکند (مثلا اگر بعد از 10 تکرار شایستگی ثابت بود و بهتر نشد).

·       راه آخر بر اساس چگالی تجمیع اطراف نقطه بهینه است. به این صورت که می­گوییم اگر 80 درصد ذرات در فاصله­ای کمتر از 20 درصد بیشترین فاصله نسبت به بهترین جواب قرار داشتند، الگوریتم باید متوقف شود.

روش آخر به این صورت است که طبق رابطه 10 می توان را بدست آورد. همانطور که گفته شد یک مقدار بین 0 و 1 است و همینطور F بیشترین فاصله بین دو ذره در حالت کنونی است.

رابطه 10

مشکل اساسی اولین الگوریتم ازدحام ذرات[ویرایش]

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

برای این کار چند راه حل ارائه شده است.

استفاده از سرعت بیشینه برشی[ویرایش]

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

استفاده از سرعت بشینه تانژانت هیپربولیکی[ویرایش]

در این روش از یک تابع تانژانت هیپربولیک برای محدود کردن سرعت به یک مقدار خاص استفاده می شود. تفاوت این حالت با حالت برشی اینست که در این حالت تابع ما مشتق پذیر در همه­ ی نقاط است درحالیکه در حالت برشی مشتق پذیری از بین می­ رود.

در حالت برشی در نقطه برش مشتق پذیری از بین می­رود. ولی در تانژانت هیپربولیک این مشکل وجود ندارد.

استفاده از ضریب کاهنده سرعت[ویرایش]

در این روش از یک  که باید بین 0 و 1 باشد، استفاده می شود. در غیر این صورت اگر بیش از 1 باشد، سرعت افزاینده خواهد بود.

  14

حال تعیین کردن خود این  یک مسئله است که روش های متعددی برای آن وجود دارد.

روش اول:

  15

روش دوم:

  16

در این روش باید  را طوری تعیین کنیم که  کمتر از 1 شود.

روش سوم:

  17

برای  می توان 0.9 را انتخاب کرد و برای  مقدار 0.2 مناسب است.

روش چهارم:

در این روش براساس مقدار شایستگی  تغییر می کند که این روش مناسب تری از روش های بالا است.

  18
  19

که  شایستگی راه­حل بهینه سراسری است.

روش پنجم:

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

  20
  21 +   , 
  22 ; k ∈[0,1]
استفاده از تابعی برحسب تکرار برای سرعت بیشینه[ویرایش]

در این روش سعی می‌شود تا از یک سرعت بیشینه به صورت تابعی از تکرار استفاده شود. در این روش سرعت بیشینه طبق رابطه 13 برای هر بعد جداگانه حساب می شود.

[null 13]

این قابلیت باعث می­شود که سرعت بیشینه با توجه به نیاز ما برای تنظیم وزن کاوش و انتفاع در هر تکرار مربوطه تعیین شود.

الگوریتم ازدحام ذارت آسنکرون[ویرایش]

الگوریتم ازدحام ذرات گفته شده نوع سنکرون بود، یک نوع دیگری از این الگوریتم وجود دارد که به آن آسنکرون گویند. در این حالت پس از محاسبه شایستگی هریک از ذرات اگر بهینه سراسری عوض شد بلافاصله به­روزرسانی می­شود. این کار باعث می­شود که سرعت همگرایی تا حدودی افزایش یابد. ولی امکان پیاده سازی موازی را می گیرد.

الگوریتم ازدحام ذرات تمام آگاه[ویرایش]

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

  23

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

الگوریتم ازدحام ذرات استخوان خالی[ویرایش]

این الگوریتم نسبت به الگوریتم­های قبلی خیلی سریع تر همگرا می‌شود و دارای دو نسخه است که در نسخه اول سرعت به شیوه زیر محاسبه می شود.

نسخه اول:

  24
  25
  26

نسخه دوم:

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

  27
الگوریتم ازدحام ذرات پیش کشیدن و پس زدن[ویرایش]

در این الگوریتم ذره به سمت بهینه سراسری جذب می‌شود وقتی که به مقدار آستانه اول برسد، دفع می‌شود تا به جستجوی بیشتری بپردازد و این دفع شدن تا جایی ادامه پیدا می­کند که به آستانه دوم برسد. عملیات جذب شدن با فرمول 32 ولی دفع شدن با فرمول 33 صورت می گیرد.

  [null 32]
  [null 33]
الگوریتم ازدحام ذرات شکار و شکارچی[ویرایش]

هنگامی که ذرات همگرا شوند یک پارامتر ترس اعمال می کنیم با احتمال  که باعث دور شدن ذرات از بهینه سراسری می‌شود و درنتیجه جستجو بیشتر می شود.

  34
  35
الگوریتم ازدحام ذرات چندشروعه[ویرایش]

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

جمع بندی[ویرایش]

الگوریتم ازدحام ذرات دودویی[ویرایش]

این یکی از الگوریتم هایی است که برای مسائل جایگذاری یا عدم جایگذاری استفاده می شود. برای این کار باید از یک نگاشت برای تبدیل از پیوسته به دودویی استفاده شود.

  36
  37

الگوریتم ازدحام ذرات جایگشتی[ویرایش]

برای مطالعه بیشتر[ویرایش]

الگوریتم پرندگان یا اجتماع ذرات چیست؟

پیوند به بیرون[ویرایش]