تحقیق رایگان درمورد جستجوی محلی و ازدحام ذرات

دانلود پایان نامه
  • (2-4)
    در مرحله ابتدایی الگوریتم، ذرات با موقعیتها و سرعتهای تصادفی ایجاد میشوند. در طی اجرای الگوریتم، موقعیت وسرعت ذره در هر مرحله i+1ام از الگوریتم، از روی اطلاعات مرحله قبلی ساخته میشوند. اگر zj مولفهی jام از بردار z باشد، آنگاه روابطی که سرعت و موقعیت ذرات را تغییر میدهند عبارتند از:
    (2-5)
    (2-6)
    در این روابط،w ضریب اینرسی، r1 و r2 اعدادی تصادفی در بازه [1,0] با توزیع یکنواخت و همچنین c1 و c2 ضرایب یادگیری هستند. r1 و r2 باعث میشوند که نوعی گوناگونی در جوابها به وجود بیاید و به این نحو جستجوی تکاملی روی فضا میشود. c1 ضریب یادگیری مربوط به تجارب شخصی هر ذره است و در مقابل c2 ضریب یادگیری مربوط به تجارب کل جمع میباشد.از معادله (2-6) میتوان به این نتیجه رسید که هر ذره به هنگام حرکت، (الف) جهت حرکت قبلی خود، (ب) بهترین موقعیتی را که در آن قرار داشته است و (پ) بهترین موقعیتی را که به وسیله کل جمع تجربه شده است، درنظر میگیرد. در برخی موارد، رواب(2-5) و(2-6) به صورت زیر، برای همهی ابعاد جمع بندی میشود:
    (2-7)
    (2-8)
    که در آن R1 و R2 دو بردار هم اندازه با بعد فضای جستجو هستند، که مولفههایشان اعداد تصادفی مستقل با توزیع یکنواخت و در بازه ی [1,0] هستند. همچنین علامت ⨂ نشان دهنده عمل ضرب عضو به عضو برای ماتریسها است. به منظور محدود کردن میزان حرکت هر ذره، مقدار مولفههای سرعت ذرات در بازه ی [-vmax,vmax] در نظر گرفته میشود ومقادیر بزرگتر یا کوچکتر نیز به این بازه تصویر میشوند. البته فرض به این است که عرض فضای جستجو در تمام ابعاد ثابت و برابر با s باشد. در این صورت به طور معمول vmax=Ps در نظر گرفته میشود که P [0.1,1] است [92] و [99].
    در جدول (2-14) مراحل الگوریتم بهینهسازی انبوه ذرات که در بالا توضیح داده شده آمده است.
    شکل2-14: مراحل الگوریتم بهینهسازی انبوه ذرات
    2-19 پارامترهای الگوریتم بهینهسازی ازدحام ذرات
    ضریب اینرسی w بر روی همگرایی الگوریتم بهینهسازی انبوه ذرات تاثیر مستقیم دارد. در واقع میتوان برای برقراری موازنه بهتر میان جستجوی سراسری و جستجوی محلی مقدار w را تغییر داد. مقدر زیاد w باعث میشود که ذرات موجود در الگوریتم، به جستجوی مناطق جدیدتر روی بیاورند و یک جستجوی سراسری را انجام دهند. در مقابل یک مقدار کم برای w باعث میشود که ذرات در منطقه محدودی بمانند و در واقع یک جستجو محلی را انجام دهند. جستجوی محلی برای دقیق تر کردن جواب های فعلی مناسب است و جستجوی سراسری برای یافتن جوابهای بهتری که به احتمال درجاهای ناشناخته از فضای جستجو وجود دارند، به کار میرود[99]،[92] .
    معادله (2-8) به صورت زیر قابل بازنویسی است:
    (2-9)
    که در آن fi[t] معنی یک نیروی خارجی است و به صورت زیر تعریف شده است:
    (2-10)
    تغییرات سرعت ذره یا شتابی که به ذره وارد میشود، به این صورت قابل محاسبه است:
    (2-11)
    در واقع ضرب 1-w به عنوان یک ضریب اصطکاک عمل میکند و می توان w را به صورت ضریب سیالی محیطی که ذره در آن در حال حرکت است، در نظر گرفت. اگر معادله (2-10) را به صورت معادله فضای حالت یک سیستم گسسته فرض شود، مقادیر بزرگتر از یک برای w، باعث ناپایدار شدن سیستم ذرات میشود. از طرفی به ازای مقادیر کمتر برای w، سرعت همگرایی سامانه بیشتر خواهد شد [97] .
    یک مقدار مناسب برای w، باعث ایجاد تعادل بین جستجوهای محلی و سراسری میشود و در اغلب اوقات باعث کاهش تعداد تکرارهای لازم برای همگرایی به یک جواب مناسب میشود. در الگوریتم ابتدایی انبوه ذرات مقدار w ثابت در نظر گرفته میشود، اما نتایج عملی حاکی از آن هستند که بهتر است مقدار w در مرحله ابتدایی یک مقدار بزرگ در نظر گرفته شود تا یک جستجوی کامل و سراسری از فضای جستجو صورت گیرد. سپس در طی مراحل اجرای الگوریتم، مقدار w به تدریج کاهش داده میشود تا الگوریتم به مرز همگرایی نزدیک شود و جوابهای دقیق تری بدست آورد. با در نظر گرفتن w به صورت ضریب سیالی محیط، مقدار بیشتر برای w، به معنی راحتتر بودن حرکت در محیط است و محیط دارای گرانروی پایین تری است. با کمتر شدن مقدار w، حرکت ذرات در محیط سختتر میشود و به این ترتیب ذرات با گران روی بیشتری مواجه میشوند. در این حالت امکان همگرایی ذرات به سمت نقاط بهینه بیشتر میشود. به عنوان مثال در نظر گرفتن مقدار 2/1 برای w و کاهش دادن تدریجی آن تا مقدار صفر، شیوه خوبی برای بیشتر مسائل است. [97] , [99-100] .
    همچنین انتخاب w به صورت انتخاب یک عدد تصادفی با توزیع یکنواخت در بازه ی [0.5,1] نتایج خوبی را به همراه داشته است[101]. راه حل بهتر و البته پیچیدهتر، استفاده از روش های تطبیقی همانند کنترل فازی است [102-103] . در این روش ها ، با توجه به شرایط مساله مقدار پارامترها به صورت تطبیقی تعیین میشوند با وجود آن که در نسخههای اولیه الگوریتم بهینهسازی انبوه ذرات، عامل میراکننده همچون محدود کردن سرعت در بازه [-vmax,vmax] در نظر گرفته شده بود اما به ضرورت نیاز به چنین عاملی توجه نشده بود. اگر الگوریتم بدون در نظر گرفتن محدودیتهای سرعت اجرا شود، در عرض چندین تکرار، سرعت ذرات به شدت افزایش مییابد و به مقادیر غیر قابل قبول میرسد. کندی ضمن تحقیقات خود، در سال 1998 دریافت که برای ذرات تک بعدی که به صورت غیر تصادفی حرکت میکنند، اگر مقدار c1+c2 بین صفر و 4 باشد مسیرهایی که ذرات طی میکنند قابل قبولتر میباشد. با تحلیلهایی که بر روی سیستم حرکت ذرات انجام شد راهبردی برای تعیین ضرایب یادگیری c1 و c2 ایجاد شده است که(الف) از ناپایدار شدن سیستم حرکتی ذرات جلوگیری میکند، (ب) همگرایی ذرات را تضمین میکند و (پ) نیازی به تعریف پارامتر vmax وجود ندارد. همچنین به واسطه ی تحلیلهای انجام شده، روشی برای تعیین مقادیر حدسی برای ضرایب یادگیری نیز ارائه شده است.
    کلرک و کندی در تحقیقات شان به این نتیجه رسیدند که راههای زیادی برای تعیین مقادیر ضرایب یادگیری وجود دارد. یکی از ساده ترین روشها برای تعیین مقادیر مناسب برای ضرایب یادگیری به این ترتیب است[97]،[101]،[104].
    (2-12)
    که در آن Φ1 و Φ2 اعدادی مثبت هستند و به نحوی انتخاب می شوند که Φ= Φ1+ Φ2 باشد .X نیز از رابطه زیر تعیین می شود:
    (2-13)
    این نوشته در مقالات و پایان نامه ها ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.