Popülasyon optimizasyon algoritmaları: Parçacık sürüsü optimizasyonu (Particle Swarm Optimization, PSO)

      Güneş ışınlarında süzülmek veya fırtına bulutlarını takip etmek için ayrı sürüler oluştururlar.

                                        Fırtına bulutlarındaki atmosferik deşarjlardan enerji çekiyor olabilirler.

Ancak tehlike anında ya da daha geniş anlamda, varlıklarını tehdit eden ani bir değişiklik anında birleşirler...

Stanislaw Lem "Yenilmez"

İçindekiler

1. Giriş
2. Algoritma ilkeleri
3. Klasik uygulama
4. Değiştirilmiş versiyon
5. Test sonuçları
   

1. Giriş

Stanislaw Lem'in bilimkurgu türündeki çok satan harika kitabı "Yenilmez"i okumuş olan muhtemelen oldukça fazla kişi vardır. Şaşırtıcı bir şekilde, "sürü" zekasının ilk tanımlarından biri, tam da bu bilim kurgu romanının yayınlanmasıyla doğmuştur. Hikaye, merkezi kontrol olmadan hayatta kalan robotlar hakkındadır. Dikkat çekici bir şekilde, en karmaşık, zeki ve güçlü olanlardan ziyade en basit ve en çok sayıda olan örnekler hayatta kalmıştır.

Binlerce yıllık nekroevrim süreci boyunca bu makineler, hem zeka hem de enerji mevcudiyeti açısından kendilerini aşan rakipleriyle etkili bir şekilde başa çıkmayı öğrenmiştir. Sadece diğer robotlarla değil, aynı zamanda gezegenin canlı dünyasıyla da savaşmak zorundaydılar. Bu eserdeki fantastik unsurlar, evrim ve doğanın kendisiyle anlamlı bir şekilde karşılaştırılabilir.

En eski zamanlardan beri insanlar, hayvanların grup halindeki davranışlarıyla (sürü davranışı) ilgilenmişlerdir - kuşların sıcak ülkelere göç ederken nelere dayalı hareket ettikleri, arı sürüsünün nasıl yiyecek ürettiği, karınca kolonisinin karmaşık yapılar oluştururken nasıl hayatta kaldığı, balıkların davranışlarının neden bu kadar senkronize olduğu. Canlıların birlikte hareket ederken iyi koordine olmuş bütüncül bir organizmanın kalıplarını göstermesi, algoritmik optimizasyon alanında yeni fikirlerin araştırılmasını ve geliştirilmesini teşvik etmektedir.

Sürü zekası, kendi kendini organize eden bir sistemin kolektif davranışının simülasyonunu tanımlar. Oldukça fazla sayıda bu türde algoritma vardır. J. Kennedy ve R. Eberhart tarafından 1995 yılında yazılan kanonik versiyonda, Reynolds modeli sadeleştirilerek parçacık sürüsü yönteminin altında yatan model elde edilmiştir. Bu basitleştirmenin bir sonucu olarak, popülasyonun farklı bireyleri, bir büyüklüğe sahip olmayan, ancak belirli bir hıza sahip olan ayrı nesneler olarak temsil edilmeye başlanmıştır.

Madde parçacıklarına aşırı benzerlikleri nedeniyle, ortaya çıkan basit nesneler parçacıklar olarak, popülasyonu da sürü olarak adlandırılmıştır. Zamanın her anında (her yinelemede), parçacıklar uzayda belirli bir konum ve hız vektörüne sahiptir. Parçacığın her konumu için, hedef fonksiyonun karşılık gelen değeri hesaplanır ve bu temelde, belirli kurallara göre, parçacık arama uzayındaki konumunu ve hızını değiştirir. Parçacığın bir sonraki konumu belirlenirken, uygunluk fonksiyonunun görevlerine karşılık gelen diğer tüm komşu parçacıklar arasından en iyi konum hakkındaki bilgiler dikkate alınır.

Sürü algoritmalarına örnekler:

• Parçacık sürüsü yöntemi
• Karınca algoritması
  
• Arı algoritması
  
• Yapay bağışıklık sistemi
  
• Gri kurt algoritması
  
• Yarasa algoritması
  
• Yer çekimsel arama algoritması
  
• Özgecilik algoritması
  
• Ve daha birçoğu

Kolektif davranışın modellenmesinden kolektif optimizasyona geçiş şu biyolojik fikre dayanmaktadır: organizmalar yaşam koşullarını iyileştirmek için koloniler halinde birleşirler. Kolonideki her bir organizmanın ortalama olarak yırtıcılara karşı mücadelede hayatta kalma şansı daha yüksektir ve koloni bireysel organizmalara kıyasla gıdayı daha verimli bir şekilde arayabilir, işleyebilir ve depolayabilir. Başka bir deyişle, herhangi bir organizma kolonisi, var olduğu süre boyunca, çeşitli optimizasyon problemlerini farklı verimlilik dereceleriyle çözer; örneğin, avcılardan kaynaklanan kayıpları en aza indirmek ve yiyecek miktarını en üst düzeye çıkarmak gibi. Bu düşünceler, çeşitli matematiksel optimizasyon yöntemlerinin oluşturulmasına temel teşkil etmiştir.

Parçacık sürüsü, başlangıcından bu yana en ünlü ve popüler optimizasyon algoritmalarından biridir. Çeşitli uygulamalarının birçok yazarı, algoritmanın birçok argümana sahip karmaşık fonksiyonları optimize etmede çok etkili olduğunu ve hatta sinir ağlarını eğitmek için uygun olduğunu iddia etmektedir.

Bu makalede, algoritmanın karmaşık problemleri çözmek için gerçekten iyi olup olmadığını anlamaya çalışacağız. Algoritmanın klasik versiyonunda ve birçok modifikasyonunda, optimize edilen fonksiyonun düzgün ve sürekli olması gerektiği gerçeğiyle ilişkili önemli sınırlamalar vardır, bu da onun ayrık fonksiyonlar için tamamen uygun olmadığı anlamına gelir. Ancak, makale serisinin amacı doğrultusunda, söz konusu tüm algoritmalar, eksiklikler ortadan kaldırılacak, en azından algoritmaların tamamen teknik olarak çalışması sağlanacak şekilde (herhangi bir kısıtlama varsa) değiştirilecektir. Diğer bir deyişle, tüm algoritmalar fonksiyonların düzgünlüğüne kayıtsız olmalı (yatırımcı problemlerinde olduğu gibi) ve argüman adımı üzerinde herhangi bir kısıtlamaya sahip olmamalıdır.

2. Algoritma ilkeleri

Bir önceki makale optimizasyon dünyasına giriş niteliğinde olduğundan, ana programın (Uzman Danışman, komut dosyası, gösterge) optimizasyon algoritması çekirdeğiyle etkileşimi ilkesini kapsamıyordu. Ancak buna dikkat etmek önemlidir, çünkü her durumda dikkatli bir okuyucunun aklına bir soru gelecektir: algoritmalar ve örnek programlar neden bu şekilde yazılmaktadır? Optimizasyon algoritmalarının mevcut versiyonları, algoritma ana çalıştırılabilir program iken, algoritmanın uygunluk fonksiyonuna harici bir nesne olarak başvuracağı şekilde yapılandırılmıştır.

Aşağıdaki Şekil 1, algoritmanın optimize edilen parametreleri uygunluk fonksiyonuna ilettiği ve uygunluk değerini (değerlendirme kriteri) geri aldığı bir diyagramı göstermektedir. Bu sistem, yatırımcılar da dahil olmak üzere kullanıcılar tarafından problemlerin çözülmesi adına bir program oluşturmak için elverişsizdir. Peki neden elverişsizdir? Örneğin, bu şekilde geçmiş veriler üzerinde sınayıcıyı çalıştıramayız.

Şekil 1. PSO ve uygunluk fonksiyonu arasındaki etkileşim

Şekil 2'de gösterilen yapı çok daha kullanışlıdır. Buradaki optimizasyon algoritması bağımsız bir program değil, ayrı bir modül veya "kara kutu"dur. Bu modül, optimize edilen her bir argüman için 'min', 'max' ve 'step' parametrelerine sahiptir. MQL programı istek üzerine optimize edilen argümanları alır ve uygunluk değerlerini veya başka bir deyişle uygunluk fonksiyonu değerlerini geri döndürür. Bu yapı, Uzman Danışmanlarda otomatik optimizasyon kullanmaktan özel bir optimizasyon yöneticisi yazmaya kadar çok esnek çözümler oluşturmaya olanak tanır.

Şekil 2. MQL programı ve PSO arasındaki etkileşim

Ayrıca, optimizasyon algoritmalarının metotlarına yapılan çağrıların organizasyonunun (Şekil 2'deki MQL bloğu) tüm optimizasyon algoritmaları için aynı olan genel bir şema ile temsil edilebileceğini belirtmek gerekir:

Başlatma_АО_0

Yineleme (dönem/epoch) döngüsü
{
1) Metot_АО_1
2) Optimize edilen parametrelerin her bir varyantı için uygunluk değerlerinin elde edilmesi
3) Metot_АО_2
}

Böylece, yalnızca üç public metodun kullanıldığını görüyoruz: Başlatma_АО_0, Metot_АО_1 ve Metot_АО_2. Bu, herhangi bir karmaşıklığa sahip kullanıcı projelerinde optimizasyon sürecini düzenlemek için yeterlidir.

PSO çalışma akışı Şekil 3'te gösterilmektedir. Aşağıdaki mantıksal adımları içermektedir:

1. Rastgele parçacık üretimi (ilk yineleme)
2. Her parçacık için uygunluk değerinin elde edilmesi
3. Genel olarak tüm parçacıklar için uygunluk değerinin elde edilmesi
4. Parçacık hızı ayarı
5. Kesme noktası veya adım 2'ye gidiş
   
6. Programın tamamlanması

Şekil 3. PSO çalışma akışı

Parçacık sürüsü algoritmasını daha ayrıntılı olarak inceleyelim.

Sürü zekası sistemi, hem birbirleriyle hem de çevreyle etkileşim halinde olan çok sayıda parçacıktan oluşur. Her bir parçacık basit kurallara uyar, ancak her birine ne yapacağını söyleyen merkezi bir davranış kontrol sistemi yoktur. Aralarındaki yerel ve rastgele etkileşimler, bireyler tarafından kontrol edilmeyen akıllı grup davranışlarının ortaya çıkmasına neden olur.
Bir sürüye benzetirsek, tüm parçacıkların bazı basit görevleri yerine getirmesi gerektiğini söyleyebiliriz:

• Diğer parçacıklarla kesişmekten kaçınma
• Hızlarını çevredeki parçacıkların hızlarına göre ayarlama
• Kendileri ve çevre arasında oldukça küçük bir mesafe bırakmaya çalışma

PSO algoritması bir popülasyon başlatmayla başlar. İkinci adım, her bir parçacığın uygunluk değerlerini hesaplamaktır, ardından bireysel ve global en iyi puanlar güncellenir ve devamında parçacıkların hızı ve konumu güncellenir. PSO kullanırken, sayısal bir optimizasyon problemine olası bir çözüm, parçacığın konumu ile temsil edilir. Buna ek olarak, her bir parçacık, mutlak büyüklüğünü ve yönünü yeni, daha iyi olduğu varsayılan bir çözüme/konuma yansıtan bir mevcut hıza sahiptir.

Parçacık ayrıca uygunluk değerini, mevcut konumunu, bilinen en iyi konumunu (bilinen en iyi uygunluğa sahip önceki konum) ve bilinen en iyi konumun uygunluğunu saklar. Tamamlanma koşulu karşılanana kadar ikiden dörde kadar olan adımlar tekrarlanır. İlk yinelemede, tüm parçacıklar en iyi çözümü bulmak için dağıtılır (keşif). Her parçacık değerlendirilir. Komşuluk topolojisi için en iyi çözümler bulunur ve sürünün her bir üyesi için kişisel ve global en iyi parçacıklar güncellenir. Yakınsama, tüm parçacıkların en iyi çözüme sahip parçacığa çekilmesiyle elde edilir. 

PSO algoritması özünde oldukça basit olmasına rağmen, bu makaledeki kodu ihtiyaçlarımıza göre değiştirebilmek adına onu anlamamız gerekir. PSO yinelemeli bir süreçtir. Ana işlem döngüsündeki her yinelemede, ilk olarak her bir parçacığın mevcut hızı güncellenir. Parçacığın mevcut hızı, yerel bilgisi ve sürünün global bilgisi dikkate alınır. Daha sonra her bir parçacığın konumu, o parçacığın yeni hızının değeri kullanılarak güncellenir.

Matematiksel olarak, bu iki parçacık koordinat güncelleme denklemi şu şekildedir:

v(t+1) = w * v(t) + c1 * rp * (p(t) - x(t)) + (c2 * rg * (g(t) - x(t)))

x(t+1) = x(t) + v(t+1)

Konum güncelleme işlemi aslında bu denklemlerden çok daha basittir. İlk denklem parçacığın hızını güncellemek içindir.

v(t+1) terimi t+1 zamanındaki hızı ifade eder. Yeni hız üç terime bağlıdır.

• Birincisi: w * v(t). w katsayısı eylemsizliğin ağırlık kesri olarak adlandırılır ve basitçe bir sabittir; v(t) t zamanındaki mevcut hızdır.
  
  
• İkinci terim: c1 * rp * (p(t) – x(t)). c1 katsayısı, bilişsel (veya kişisel veya yerel) ağırlık kesri olarak adlandırılan bir sabittir. rp çarpanı [0, 1] aralığında rastgele bir değişkendir. p(t) vektör büyüklüğü parçacığın o ana kadar bulunan en iyi konumudur, x(t) vektör büyüklüğü ise parçacığın mevcut konumudur.
  
  
• Üçüncü terim: hız güncellemesi c2 * rg * (g(t) - x(t)). c2 katsayısı, sosyal (veya global) ağırlık kesri olarak adlandırılan bir sabittir. rg çarpanı [0, 1] aralığında rastgele bir değişkendir. g(t) vektörünün değeri, sürüdeki parçacıklardan herhangi birinin o ana kadar bulunan en iyi bilinen konumudur. Yeni bir hız v(t+1) belirlendikten sonra, parçacığın yeni konumunu x(t+1) hesaplamak için kullanılır.

3. Klasik uygulama

Uzaydaki bir koordinat kümesini (optimize edilen parametreler) tanımlayan bir mantıksal birim, bir yapı olarak temsil edilebilen bir parçacıktır: burada, c[] - parçacığın koordinatları, cB[] - parçacığın tüm yinelemeler için en iyi koordinatları, v[] - parçacığın her bir koordinatı için hızı, ff - parçacığın mevcut uygunluk değeri ve ffB - parçacığın tüm yinelemeler için en iyi uygunluk değeridir. Parçacık yapısının yapıcısında, ff ve ffB değerlerini 'double' türüyle temsil edilebilecek minimum olası değeri kullanarak başlatıyoruz, çünkü algoritma fonksiyonun maksimumunu bulmak için tasarlanmıştır (minimumu bulmak için, elde edilen uygunluk değerinin önüne bir "-" işareti eklemek yeterlidir).

//——————————————————————————————————————————————————————————————————————————————
struct S_Particles
{
  public:
    double c  []; //coordinates
    double cB []; //best coordinates
    double v  []; //velocity

    double ff;    //the value of the fitness function
    double ffB;   //best value fitness function

    S_Particles ()
    {
      ff  = -DBL_MAX;
      ffB = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

PSO algoritmasını yalnızca şu üç public metodu içeren bir sınıf olarak uygulayalım: InitPS (), Preparation () ve Dwelling () (Başlatma_АО_0, Metot_АО_1 ve Metot_АО_2). Private metotlardan GenerateRNDparticles () ve ParticleMovement () PSO’ya özgüdür, geri kalanlar ise bir önceki makalede ele alınmıştır. p [] yapı dizisi bir parçacık sürüsüdür. Her bir parçacığın uygunluk değerlerine, kendi koordinatlarına ve en iyi koordinatlara sahip olmasına ek olarak, sürü bir bütün olarak en iyi koordinatlara cB ve en iyi uygunluk değerine ffB sahiptir.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_PSO
{
  public:
  //----------------------------------------------------------------------------
  S_Particles p    []; //particles
  double rangeMax  []; //maximum search range
  double rangeMin  []; //manimum search range
  double rangeStep []; //step search
  double cB        []; //best coordinates
  double ffB;          //FF of the best coordinates

  void InitPS (const int    params,       //number of opt. parameters
               const int    size,         //swarm size
               const double inertiaP,     //inertia
               const double selfBoostP,   //boost
               const double groupBoostP); //group boost

  void Preparation ();
  void Dwelling ();

  private:
  //----------------------------------------------------------------------------
  int swarmSize; //swarm size
  int parameters;//number of optimized parameters

  double inertia;
  double selfBoost;
  double groupBoost;
  bool   dwelling;

  void   GenerateRNDparticles ();
  void   ParticleMovement     ();
  double SeInDiSp             (double in, double inMin, double inMax, double step);
  double RNDfromCI            (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

InitPS () metodu, optimizasyon başlamadan (Başlatma_АО_0) önce algoritmayı başlatmak içindir. Metodun argüman değerleri metottaki özel üyelere atanır, ayrıca büyüklük sürüye ve sürüdeki her bir parçacığın dahili parametrelerine atanır.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::InitPS (const int    paramsP,
                       const int    sizeP,
                       const double inertiaP,
                       const double selfBoostP,
                       const double groupBoostP)
{
  ffB = -DBL_MAX;

  parameters = paramsP;
  swarmSize  = sizeP;

  ArrayResize (rangeMax,  parameters);
  ArrayResize (rangeMin,  parameters);
  ArrayResize (rangeStep, parameters);

  dwelling = false;

  inertia    = inertiaP;
  selfBoost  = selfBoostP;
  groupBoost = groupBoostP;

  ArrayResize (p, swarmSize);

  for (int i = 0; i < swarmSize; i++)
  {
    ArrayResize (p [i].c,  parameters);
    ArrayResize (p [i].cB, parameters);
    ArrayResize (p [i].v,  parameters);
  }

  ArrayResize (cB, parameters);
}
//——————————————————————————————————————————————————————————————————————————————

Preparation () metodu her yinelemede (dönem/epoch) ilk olarak çağrılır (Metot_АО_1). Metot basit ama çok önemlidir. Metodun ilk dönemde mi yoksa sonraki dönemlerde mi çağrılacağına bağlı olarak (dwelling bayrağı tarafından belirlenir), sürü uygunluk değeri sıfırlanacak ve rastgele bir sürü popülasyonu oluşturulacak veya parçacıklar yeni koordinatlara taşınacaktır.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::Preparation ()
{
  if (!dwelling)
  {
    ffB = -DBL_MAX;
    GenerateRNDparticles ();
    dwelling = true;
  }
  else ParticleMovement ();
}
//——————————————————————————————————————————————————————————————————————————————

GenerateRNDparticles () metodunda rastgele bir sürü popülasyonu oluşturulur. Parçacıklar, her biri için belirtilen aralıkta rastgele koordinatlara ve koordinatların her biri için rastgele bir hıza sahiptir.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::GenerateRNDparticles ()
{
  for (int s = 0; s < swarmSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      p [s].c  [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      p [s].c  [k] = SeInDiSp (p [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      p [s].cB [k] = p [s].c [k];
      p [s].v  [k] = RNDfromCI (0.0, (rangeMax [k] - rangeMin [k]) * 0.5);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

ParticleMovement () metodu, parçacıkları yeni konumlara taşımak için algoritmayı tetikler. Bu amaçla, yukarıdaki denkleme göre her koordinat için hızı hesaplamak gerekir. "Hız" teriminin neden kullanıldığını bilmiyorum, çünkü temelde bir yer değiştirme değeridir veya başka bir deyişle, parçacığın o anda bulunduğu yer ile hareket etmesi gereken yer arasındaki farktır. Her bir koordinat için bu farkı hesapladıktan sonra, mevcut değerlere eklememiz yeterlidir. Sonrasında, belirtilen adımla optimize edilen parametrelerin (bir parçacık için bunlar koordinatlardır) min/maks sınırlarının ötesine geçmenin kabul edilemez olup olmadığı kontrol edilir.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::ParticleMovement ()
{
  double rp;       //random component of particle movement
  double rg;
  double velocity;
  double posit;
  double positBest;
  double groupBest;

  for (int i = 0; i < swarmSize; i++)
  {
    for (int k = 0; k < parameters; k++)
    {
      rp = RNDfromCI (0.0, 1.0);
      rg = RNDfromCI (0.0, 1.0);
      
      velocity  = p [i].v  [k];
      posit     = p [i].c  [k];
      positBest = p [i].cB [k];
      groupBest = cB [k];

      p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit);
      p [i].c [k] = posit + p [i].v [k];

      p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Dwelling () metodu, optimizasyon için kullanılan algoritmanın üçüncü public metodudur (Metot_АО_2). Metodun amacı, her bir parçacığın en iyi koordinatlarını ve uygunluk değerlerini önceki performansına göre güncellemektir. Gerekirse sürünün uygunluğu ve en iyi koordinatları da güncellenir. Metot, yineleme döngüsünde uygunluk değerleri alındıktan sonra çağrılır.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSO::Dwelling ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    //remember the best position for the particle
    if (p [i].ff > p [i].ffB)
    {
      p [i].ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k];
    }

    if (p [i].ff > ffB)
    {
      ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Belirtilen aralıkta belirtilen adımla 'double' türündeki sayının ayrıklaştırılması için fonksiyon.

//——————————————————————————————————————————————————————————————————————————————
// Choice in discrete space
double C_AO_PSO::SeInDiSp (double in, double inMin, double inMax, double step)
{
  if (in <= inMin) return (inMin);
  if (in >= inMax) return (inMax);
  if (step == 0.0) return (in);
  else return (inMin + step * (double)MathRound ((in - inMin) / step));
}
//——————————————————————————————————————————————————————————————————————————————

Belirtilen aralıkta rastgele bir 'double' türünde sayı elde etmek için fonksiyon.

//——————————————————————————————————————————————————————————————————————————————
// Random number generator in the custom interval
double C_AO_PSO::RNDfromCI (double min, double max)
{
  if (min == max) return (min);
  double Min, Max;
  if (min > max)
  {
    Min = max;
    Max = min;
  }
  else
  {
    Min = min;
    Max = max;
  }
  return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0)));
}
//——————————————————————————————————————————————————————————————————————————————

Teori kısmı bitti. Hadi şimdi pratik yapmaya başlayalım.

Serinin ilk makalesinde kullandığımız (ve kullanmaya devam edeceğimiz), Şekil 2'de açıklanan algoritma oluşturma yapısının aynısını kullandığımız için, algoritmayı test ortamına bağlamak bizim için zor olmayacaktır.

Test ortamını çalıştırırken, aşağıda gösterilenlere benzer animasyonlar göreceğiz. Bu durumda, bir parçacık sürüsünün nasıl davrandığını açıkça görebiliriz. Sürü gerçekten de doğadaki bir sürü gibi davranmaktadır. Fonksiyonun ısı haritasında yoğun bir bulut şeklinde hareket etmektedir.

Hatırlayacağınız gibi, siyah daire fonksiyonun global optimumunu (maksimum) gösterirken, siyah nokta arama algoritmasının mevcut yineleme sırasında elde ettiği en iyi ortalama koordinatları göstermektedir. Ortalama değerlerin nereden geldiğini açıklayayım. Isı haritası koordinat cinsinden iki boyutludur ve optimize edilen fonksiyon yüzlerce değişken (ölçüm) içerebilir. Bu nedenle, sonucun koordinatlara göre ortalaması alınır.

  Skin test fonksiyonu üzerinde PSO.

  Forest test fonksiyonu üzerinde PSO.

  Megacity test fonksiyonu üzerinde PSO.

Animasyondan görebileceğiniz gibi, testler PSO'nun düzgün ilk fonksiyonla oldukça iyi başa çıktığını gösterdi (ancak yalnızca iki değişkeni optimize ederken). Arama uzayının boyutunun artmasıyla, algoritmanın verimliliği keskin bir şekilde düşmektedir. Bu durum özellikle ikinci ve ayrık üçüncü fonksiyonlarda belirgindir. Sonuçlar, bir önceki makalede açıklanan rastgele algoritmadan açık bir şekilde daha kötüdür. Karşılaştırmalı bir sonuç tablosu oluştururken sonuçlara geri dönecek ve onları ayrıntılı olarak tartışacağız.

Ünlü PSO algoritmasının rastgele algoritmaya karşı nasıl utanç verici bir şekilde kaybettiğine bakıldığında, algoritmaya ikinci bir şans vermek istenebilir. Bir sonraki bölümde, PSO algoritmasını değiştirmeye çalışacağız.

4. Değiştirilmiş versiyon

Bana göre PSO'nun zayıf yönleri şunlardır:

1) Koordinatların her biri neredeyse 1'e eşit olasılıkla mutlaka değişecektir. Bu, sürünün her bir parçacığının her yinelemede en iyi ihtimalle global bölgenin yerel ekstremumunda bir yerde salındığı, en kötü ihtimalle ise hiçbir zaman global ekstremum noktasına tam olarak ulaşamadığı anlamına gelir. Bu, algoritmanın karakteristik bir özelliği olan yerel ekstremumlarda takılmayı, yani kötü yakınsamayı ifade eder.

2) Algoritma, kısmen ilk kusur nedeniyle ayrık fonksiyonlarla iyi çalışmamaktadır. Parçacık koordinatları, optimize edilen fonksiyonun yüzeyinin en yakın "alanlarına" atlar, herhangi bir yerel ekstremumun komşuluğunu ayrıntılı olarak inceleyemez.

3) Algoritmanın yeni alanları keşfetme yeteneği zayıftır. Sürü, yerel "delikten" kaçmaya çalışmadan tek bir yere odaklanmaktadır. Bazı yazarlar, çok sürülü modifikasyonun bir uygulamasını oluşturma girişimlerinden bahsetmektedir, ancak karmaşık çok değişkenli fonksiyonları optimize etme soruları açık kalmaktadır, çünkü karşılıklı mesafe ilkesi belirsizdir ve sadece ortak hareket ilkesi değil, aynı zamanda karşılıklı itme olasılığı da yerine getirilmelidir. Aksi takdirde, böyle bir uygulamanın hiçbir anlamı yoktur çünkü bireysel sürüler sadece bir alanda veya noktada birleşecektir. Aynı zamanda, basit bir veya iki değişkenli fonksiyonların optimizasyonu, mükemmel yakınsama ile en basit yöntemlerle gerçekleştirilmektedir.

Peki algoritmayı iyileştirmek için ne yapabiliriz?

En iyi bireysel koordinatları diğer parçacıklardan parçacıklara aktarmamız gerektiği açıktır (mutlaka doğru olmasa da). "Donör" parçacığın genel koordinatları ne kadar iyi olursa, koordinatların iletilme olasılığı da o kadar yüksek olur. Parçacık seçme olasılığında kayma şematik olarak Şekil 4'te gösterilmektedir. 0'dan 1'e kadar rastgele bir sayı üretiyoruz, elde edilen sayıyı bir parabolik fonksiyonla dönüştürüyoruz ve ardından 0'dan SwarmSize-1'e kadar sürüdeki parçacıkların seri numaraları aralığına ölçeklendiriyoruz. Bunu yapmak adına, PSOm (değiştirilmiş algoritma) için ek bir parametre eklememiz gerekiyor - koordinatı kopyalama olasılığı. Ayrıca sürüyü, parçacık ne kadar iyi olursa 0 indeksine o kadar yakın olacak şekilde sıralamamız gerekiyor.

Şekil 4. Parçacık seçme olasılığında kayma

ParticleMovement () metodunu biraz değiştirelim. [0;1] aralığından rastgele bir sayı üretelim. Eğer sayı 'copy' parametresinden büyük çıkarsa, parçacıkla yukarıda ayrıntılı olarak açıklanan olağan işlemleri gerçekleştireceğiz, aksi takdirde Şekil 4'te grafiksel olarak gösterilen kurala göre seçilen bir indekse sahip başka bir parçacığın koordinatını kopyalayacağız.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSOm::ParticleMovement ()
{
  double rp;       //random component of particle movement
  double rg;
  double velocity;
  double posit;
  double positBest;
  double groupBest;

  for (int i = 0; i < swarmSize; i++)
  {
    for (int k = 0; k < parameters; k++)
    {
      rp = RNDfromCI (0.0, 1.0);
      rg = RNDfromCI (0.0, 1.0);

      double rC = RNDfromCI (0.0, 1.0);

      if (rC > copy)
      {
        velocity  = p [i].v  [k];
        posit     = p [i].c  [k];
        positBest = p [i].cB [k];
        groupBest = cB [k];

        p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit);
        p [i].c [k] = posit + p [i].v [k];

        p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      }
      else p [i].c [k] = p [GetPartcileAdress ()].cB [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Dwelling () metodu da değiştirilmelidir. SortParticles () sıralama fonksiyonunu çağırmayı ekleyelim.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_PSOm::Dwelling ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    //remember the best position for the particle
    if (p [i].ff > p [i].ffB)
    {
      p [i].ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k];
    }

    if (p [i].ff > ffB)
    {
      ffB = p [i].ff;
      for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k];
    }
  }

  SortParticles ();
}
//——————————————————————————————————————————————————————————————————————————————

GetParticleAdress () fonksiyonu, en iyi parçacığa doğru kaydırılmış bir olasılıkla bir parçacık adresinin seçilmesini sağlar.

//——————————————————————————————————————————————————————————————————————————————
//shift of probability in the smaller party (to an index 0)
int C_AO_PSOm::GetParticleAdress ()
{
  double x = RNDfromCI (-1.0, 0.0);
  x = x * x;
  x = Scale (x, 0.0, 1.0, 0, swarmSize - 1);
  x = SeInDiSp (x, 0, swarmSize - 1, 1);
  return ((int)x);
}
//——————————————————————————————————————————————————————————————————————————————

SortParticles () fonksiyonu geleneksel bir kabarcık sıralamadır.

//——————————————————————————————————————————————————————————————————————————————
//Sorting of particles
void C_AO_PSOm::SortParticles ()
{
  //----------------------------------------------------------------------------
  int   cnt = 1;
  int   t0 = 0;
  double t1 = 0.0;
  //----------------------------------------------------------------------------

  // We will put indexes in the temporary array
  for (int i = 0; i < swarmSize; i++)
  {
    ind [i] = i;
    val [i] = p [i].ffB; //ffPop [i];
  }

  while (cnt > 0)
  {

    cnt = 0;
    for (int i = 0; i < swarmSize - 1; i++)
    {
      if (val [i] < val [i + 1])
      {
        t0 = ind [i + 1];
        t1 = val [i + 1];
        ind [i + 1] = ind [i];
        val [i + 1] = val [i];
        ind [i] = t0;
        val [i] = t1;

        cnt++;
      }
    }
  }

  // On the received indexes create the sorted temporary population
  for (int u = 0; u < swarmSize; u++) pT [u] = p [ind [u]];

  // Copy the sorted array back
  for (int u = 0; u < swarmSize; u++) p [u] = pT [u];
}
//——————————————————————————————————————————————————————————————————————————————

Bir sayıyı bir sayısal aralıktan diğerine ölçekleme fonksiyonu.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_PSOm::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
  else
  {
    if (In < InMIN) return (OutMIN);
    if (In > InMAX) return (OutMAX);
    return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
  }
}
//——————————————————————————————————————————————————————————————————————————————

5. Test sonuçları

Son olarak, mevcut araştırmanın sonuçlarını özetleyelim. Ne yazık ki, PSO algoritması, iyi sonuçlar için ne kadar umut etmek istesek de kendini haklı çıkaramadı. Yürütülen çalışmalar, kesikli ve çok sayıda argümanı olan ayrık fonksiyonlar için zayıf yakınsama gösterdi. Algoritmayı değiştirme girişimi de başarısız oldu, sonuçların klasik uygulamadan bile daha kötü olduğu ortaya çıktı.

Kopyalama parametresinin 0.8'e yakın değerlere yükseltilmesi anlık yakınsama gösterebilmektedir (ancak yalnızca testlerdeki ilk düzgün fonksiyon için ve yalnızca iki argümanla). Diğer testler için bu parametre sadece sonuçları kötüleştirmektedir. PSO'nun klasik uygulaması sadece 1000 argümanlı Skin fonksiyonunda ilginç bir şey göstermeyi başardı. Diğer testlerde sonuçların vasat olduğu ortaya çıktı.

Nihai test sonucu klasik algoritma için 0.47695 ve değiştirilmiş algoritma için 0.45144'tür. Sonuçlar aşağıdaki tabloda gösterilmektedir. Test ortamı, ayarlarda test çalıştırma sayısını seçmemize olanak sağlar (varsayılan değer 5'tir), böylece okuyucular, hesaplama gücü izin veriyorsa bu parametreyi daha yüksek ayarlayarak istatistiksel olarak daha doğru sonuçlar elde edebilir.

Optimizasyon algoritması	Çalıştırma sayısı	Skin			Forest			Megacity (ayrık)			Nihai sonuç
		2 parametre (1 F)	40 parametre (20 F)	1000 parametre (500 F)	2 parametre (1 F)	40 parametre (20 F)	1000 parametre (500 F)	2 parametre (1 F)	40 parametre (20 F)	1000 parametre (500 F)
RND	1000	0.98744	0.61852	0.49408	0.89582	0.19645	0.14042	0.77333	0.19000	0.14283	0.51254
	10,000	0.99977	0.69448	0.50188	0.98181	0.24433	0.14042	0.88000	0.20133	0.14283
PSO	1000	0.98436	0.72243	0.65483	0.71122	0.15603	0.08727	0.53333	0.08000	0.04085	0.47695
	10,000	0.99836	0.72329	0.65483	0.97615	0.19640	0.09219	0.82667	0.10600	0.04085
PSOm	1000	0.96678	0.64727	0.57654	0.80616	0.13388	0.06800	0.53333	0.08067	0.04211	0.45144
	10,000	0.99505	0.64986	0.57654	0.90401	0.18194	0.07104	0.74667	0.10400	0.04211

Yukarıdakilerin tümünü özetlersek, PSO, ortalama optimal noktalarda hızlı ve erken yakınsamaya ve ek olarak rafine arama alanında yavaş yakınsamaya (yerel arama yeteneği zayıftır) yol açma eğilimindedir. Basitçe söylemek gerekirse, algoritma çok zayıftır ve karmaşık ve hatta ayrık fonksiyonları, özellikle de birden fazla argümanı olan fonksiyonları optimize etmek için uygun değildir.

Genel olarak PSO'yu iyileştirmek için kullanılabilecek çeşitli yaklaşımlar vardır. Sürü büyüklüğü önemli faktörlerden biridir. Daha yüksek bir sürü büyüklüğü, daha hızlı ve daha doğru yakınsama olasılığını artırabilir. Bununla birlikte, pratik problemlerde genellikle uygunluk fonksiyonunun çalıştırma sayısında bir eşik vardır ve sürü büyüklüğünü artırmak yalnızca orantılı olarak dönem (epoch) sayısını azaltacak ve dolayısıyla sürü evrimi olasılığını azaltacaktır.

İkinci yaklaşım ise keşif ve sömürü arasında bir denge kurmaktır. Yinelemelerin başlangıcında, yüksek derecede keşif, global optimuma yakın bir çözüm bulma şansını artıracaktır. Yinelemelerin sonunda da yüksek derecede sömürü, parçacığa gelecek vaat eden alanda en doğru çözümü bulma şansı verecektir. Sürü aşamasından önce diğer yöntemlerle yapılan ön optimizasyon, PSO'nun temel performansını iyileştirmek için kullanılabilecek bir başka tekniktir (günümüzde oldukça yaygın olarak kullanılmaktadır). Her bir alt gruba farklı görevler veya hedefler atamak da PSO'nun çok görevli problemlerdeki etkinliğini artırabilir. 

PSO'nun performansını iyileştirmek için bir başka yaklaşım da hız denkleminin bileşenlerini oluşturmaktır (dinamik hız kontrolü). Böyle bir yaklaşım parçacıkları farklı yönlere gönderebilir ve global optimuma daha hızlı yakınsamayı sağlayabilir, ancak bu sadece bir varsayımdır.

Avantajları:

1. Algoritma çok basittir ve fazla hesaplama kaynağı istemez, kod çok hızlı çalışır, çünkü klasik uygulamada diziler bile sıralanmaz.
2. Algoritma, düzgün fonksiyonlarla iyi bir iş çıkarır. Şu ana kadar PSO, birden fazla argümana sahip düzgün fonksiyonları optimize etme konusunda açık ara lider konumdadır.
   

Dezavantajları:

1. Optimize edilen fonksiyon üzerinde çalışma kalitesi düşüktür. Algoritma, birkaç benzersiz çözüm kümesinin gerekli olduğu problemleri çözmek için uygulanamaz.
2. Hız ve yakınsama hassasiyeti düşüktür.
3. Ayrık fonksiyonların optimizasyonu için uygunsuzdur.
   
4. Neredeyse tamamen ölçeklenemezdir.