یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم PSO برای انتخاب ویژگی

در PSOهرجواب،یکپرندهدرفضایجستجواستکهانرا "فرد یا جزء" (Particle)می­نامند. هر جزء موقعیت خود را دارد و یک مقدار برازندگی که توسط تابع برازندگی بهینه می­شود. ذرات در میان فضای جستجو پرواز می­کنند و دو تواناییضروری دارند:

1)    حافظه ای برای ذخیره سازی بهترین مکان خود

2)    اگاهی در موردبهترین موقعیت در همسایگی خود یا در کل فضای پاسخ­ها

برای هر ذره دو مقدار موقعیت و سرعت، تعریف می­شود که به ترتیب با یک بردار مکان ویک بردار سرعت، مدل می‌شوند.اجزا در هر تکرار (پرواز) خود، بنابر جدیدترین بردار سرعت، از موقعیتی به موقعیت­های دیگر می­روند. بردار سرعت، در نتیجه تجربه هر جزء که از دیگر اجزا به دست می­اورد و همچنین با استفاده از بهترین موقعیت در گروه، تعیین می­شود. اعضای گروه، مکان­های خوب را به یکدیگر از طریق ارتباط، انتقال می­دهند و موقعیت و سرعتشان را با مکان­های خوبتنظیم می­کنند.

 به طور خاص بردار سرعت هر جزء، با استفاده از دو مقدار بهینه، بروز رسانی می­شود. اولین مقدار بهینه، بهترین مقدار شخصی جزء (pbest)[1]است که بهترینموقعیتیاستکهتاکنونذرهموفقبه رسیدنبه انشدهاست. دومین مقدار بهینه که با (gbest)[2]نشان داده می­شود، بهترینموقعیتیاستکهتاکنونتوسطجمعیت ذراتبه دستامدهاست. اثر بهترین شخصی و بهترین عمومی، روی بروزرسانی سرعت، به وسیله فاکتورهای یادگیری کنترل می­شوند.

هر ذره برای اعمال تغییری مناسب در مکان و سرعت خود، اطلاعات زیر را دارا می­باشد:

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

·         بهترین همسایگی: که ذره از طریق ارتباط با زیر مجموعه­های گروه،ان را به دست می­اورد.

·        بهترین محلی: که بهترین راه حلی است که ذره تاکنونتجربه کرده است.

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

اگر تعداد اجزا Nباشد، ما به هر جزء یا ذره با اندیس i(i= 1,2,…,N)اشاره می­کنیم. در ان صورت برای بردار مکان هر ذره iدر هر تکرار tخواهیم داشت [Alpe10]:

رابطه (7)                                                                               Xit  = (xi1t, xi2t,…,xikt)

که بُعد جزء، برابر تعداد ویژگی­ها (K)خواهد بود. بنابراین (X1t, X2t,…,XNt)گروهی از اجزا را در تکرار tنشان می­دهد.

همچنین بهترین موقعیت شخصی برای هر ذره iمطابق رابطه زیر است:

رابطه (8)                                                                            Pit = (pi1t, pi2t,…, piKt)   

بهترین موقعیت عمومی برای گروه نیز با رابطه زیر نشان داده می­شود:

رابطه (9)                                                                               Gt = (g1t, g2t,…, gKt)

بعداز هر تکرار tالگوریتم PSO، بردار سرعت (Vit+1)به صورت زیر بروزرسانی خواهد شد:

رابطه (10)                                               Vit+1 = wvit + c1r1 (Pit - Xit) + c2r2 (Gt - Xit)

که در ان wضریب اینرسی است. c1فاکتور بهترین جواب محلی و c2فاکتور بهترین جواب عمومی است. به عبارت دیگر c1نمایانگر تفکر شخصی هر ذره و فاکتور شخصی[3] است، در حالی که c2نمایانگر همکاری بین ذرات در گروه و فاکتور جمعیتی[4] است [Song04]و بهترتیب میزانتاثیر تجاربشخصیوتجربه جمعیرادرتصمیم­گیریذره،نشانمی­دهند.

ضرایب شتاب c1و c2میزان شتاب تصادفی را برای کشاندن ذرات به سوی pbestو gbestتعیین می­کنند. مقادیر کم ان­ها، به ذرات اجازه می­دهد دور از مناطق هدف حرکت کنند، ولی مقادیر زیاد باعث می­شود، ذرات حرکت ناگهانی به سوی مناطق هدف داشته باشند. ضرایب یادگیری c1و c2معمولا در بازه [0,2]اختیار می­شوند [Chan10]. r1و r2اعداد تصادفی حاصل از توزیع یکنواخت در بازه [0,1]هستند.

سرعت ذره­ها در هر بعد، محدود به ماکزیمم سرعت Vmaxاست که چگونگی حرکت ذره­ها در فضای جستجو را مشخص می­کند [Cler02]. اگر Vmaxخیلی کوچک باشد، ممکن است ذره­ها به خوبی در فضاهای مناسب محلی کاوش نکنند و در بهینه محلی به دام بیفتند. از سوی دیگر، اگر این مقدار بیش از حد زیاد باشد، ممکن است ذرات در فضاهای دور از جواب پرواز کنند.

در نهایت، ذرات به سوی موقعیت جدید، بنا به رابطه مکانی زیر حرکت می­نمایند.

رابطه (11)                                                                             Xit+1 = Xit+1 + Vit+1

مزیت اصلیPSO این است که پیاده‌سازی این الگوریتم ساده بوده و نیاز به تعیینپارامتر‌های کمی  دارد. همچنینPSO قادر به بهینه‌سازی توابع هزینه‌ پیچیده باتعداد زیاد مینیمم محلی است.

فرایند الگوریتم PSOمی­تواند به صورت زیر خلاصه شود:

Input:

    m: the swarm size; c1, c2: positive acceleration constants;

    w: inertia weight

    MaxV: maximum velocity of particles

    MaxGen: maximum generation

    MaxFit: maximum fitness value

Output:

    Gbest: Global best position

    // Initialize the particle positions and their velocities

for I = 1 to number of particles n do

   for J = 1 to number of dimensions m do

       X[I][J] = lower limit + (upper limit - lower limit) * uniform

random number

       V[I][J] = 0

   enddo

enddo

// Initialize the global and local fitness to the worst possible

fitness_gbest = inf;

    for I = 1 to number of particles n do

fitness_lbest[I] = inf

enddo

// Loop until convergence, in this example a finite number of

iterations chosen

for k = 1 to number of iterations t do

// evaluate the fitness of each particle

fitness_X = evaluate_fitness (X)

// Update the local bests and their fitness

for I = 1 to number of particles n do

    if (fitness_X (I) < fitness_lbest (I))

         fitness_lbest[I] = fitness_X (I)

         for J = 1 to number of dimensions m do

        X_lbest[I,J] = X (I,J)

   enddo

endif

enddo

// Update the global best and its fitness

[min_fitness, min_fitness_index] = min (fitness_X (I))

if (min_fitness < fitness_gbest)

    fitness_gbest = min_fitness

    for J = 1 to number of dimensions m do

         X_gbest[J] = X (min_fitness_index,J)

    enddo

endif

// Update the particle velocity and position

 for I = 1 to number of particles n do

    for J = 1 to number of dimensions m do

        R1 = uniform random number

        R2 = uniform random number

        V[I][J] = w*V[I][J] + C1*R1*(X_lbest[I][J] - X[I][J])

                      + C2*R2*(X_gbest[J] - X[I][J])

        X[I][J] = X[I][J] + V[I][J]

    enddo

 enddo

enddo


[1] personal best

[2] global best

[3] individual factor

[4] social factor

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26