Popülasyon optimizasyon algoritmaları: Karınca kolonisi optimizasyonu (Ant Colony Optimization, ACO)
342
0
Herhangi bir davranışın en büyük sırrı sosyal davranıştır...
F. Bartlett
İçindekiler
1. Giriş
2. Algoritma ilkeleri
3. Değiştirilmiş versiyon
4. Test sonuçları
1. Giriş
Belçikalı araştırmacı Marco Dorigo, bir karınca kolonisindeki kolektif zeka sürecini bilimsel olarak tanımlayan matematiksel bir model oluşturmuştur. Onu 1992 yılında doktora tezinde yayınlamış ve bir algoritma olarak uygulamıştır. Karınca kolonisi optimizasyonu (Ant Colony Optimization, ACO), çok çeşitli kombinasyonel optimizasyon problemlerini çözmek için popülasyon tabanlı bir stokastik arama yöntemidir. ACO, stigmerji kavramına dayanmaktadır. 1959 yılında Pierre-Paul Grasset, termitlerin yuva yapma davranışını açıklamak için stigmerji teorisini ortaya atmıştır. Stigmerji Yunanca iki kelimeden oluşur: stigma - işaret ve ergon - eylem.
Kanonik tanım, çevre ile etkileşim yoluyla zaman içerisinde genişleyen bir popülasyonun üyeleri arasındaki dolaylı bir etkileşim türüdür. Başka bir deyişle, temsilcilerden biri bir iz bırakır ya da bir şekilde konumun ayarını değiştirir, böylece başka bir temsilci kendi alanına girerken bazı bilgiler alır. Karıncalar söz konusu olduğunda, stigmerji feromonlardır. Karıncaların yiyecek arama sürecindeki iletişimi stigmerjiye bir örnektir. Karıncalar birbirleriyle dolaylı olarak iletişim kurar: yere feromon izleri bırakırlar ve böylece diğer karıncaların karar verme süreçlerini etkilerler. Tek tek karıncalar arasındaki bu basit iletişim biçimi, bir bütün olarak koloninin karmaşık davranış ve yeteneklerini ortaya çıkarır.
Karıncalar sosyal böceklerdir, koloniler halinde yaşarlar. Karıncaların davranışları yiyecek arama amacı tarafından kontrol edilir. Arama yaparken kolonilerini dolaşırlar. Karınca yiyecek bulmak için sürekli olarak bir yerden başka bir yere atlar ve hareket ettikçe yere feromon adı verilen organik bir bileşik bırakır. Böylece karıncalar feromon izlerini kullanarak birbirleriyle iletişim kurarlar.
Bir karınca yiyecek bulduğunda, taşıyabileceği kadarını taşır. Geri dönerken, yiyecek miktarına ve kalitesine bağlı olarak yol boyunca feromon bırakır. Bunun sonucunda da diğer karıncalar bu rotayı takip edebilir. Feromon seviyesi ne kadar yüksekse, ilgili yolun seçilme olasılığı da o kadar yüksektir. Bu şekilde, belirli bir yoldan ne kadar çok karınca geçmeye devam ederse, bu rota üzerinde o kadar çok feromon birikecektir.
Bunu bir örnekle görelim. Koloniden aynı yiyeceğe giden iki yolun olduğunu varsayalım. Başlangıçta, yerlerde hiç feromon yoktur. Dolayısıyla, bu iki yolun seçilme olasılığı birbirine eşittir (%50). İki karıncanın yiyeceğe giden bu iki farklı yolu ayrı ayrı seçtiğini varsayalım. Bu iki yolun mesafeleri farklı olsun. Daha kısa yolu izleyen karınca yiyeceğe diğerinden daha önce ulaşacaktır. Yiyeceği bulduğunda bir kısmını alır ve koloniye geri döner. Geri dönüş yolunu izlerken, yere feromon bırakır. Daha kısa yolu izleyen karınca koloniye daha erken ulaşacaktır.
Üçüncü karınca yiyecek aramak için dışarı çıkmak istediğinde, yerdeki feromon seviyesine bağlı olarak daha kısa mesafeli yolu izlemek isteyecektir. Çünkü, daha kısa olan yol daha uzun olandan o anda çok daha fazla feromona sahiptir (2/1) ve dolayısıyla üçüncü karınca çok yüksek olasılıkla daha fazla feromona sahip olan yolu takip edecektir. Daha uzun yolu izleyen karınca koloniye geri döndüğünde, iki yol arasındaki feromon oranı azalacaktır (3/2 olacaktır). Daha sonra, başka bir karınca koloniden hedefine (yiyecek) ulaşmaya çalıştığında, yine daha kısa yolu seçme olasılığı daha yüksek olacaktır (her ne kadar ilk duruma göre feromon oranı düşmüş olsa da hala daha kısa yolda bulunan feromon miktarı daha yüksektir). Bu işlemin defalarca tekrarlanmasıyla bir süre sonra daha kısa olan yolda diğer yola göre çok daha fazla feromon birikecektir (iki yol arasındaki feromon oranı daha kısa olan yol lehine önemli ölçüde artacaktır) ve böylece karıncaların daha kısa olan yolu kullanma olasılığı zamanla daha da yüksek olacaktır.
ACO algoritması bir tür sürü zekası algoritmasıdır. Karınca kolonisinin yiyecek arama süreci modellenerek (karınca kolonisinin dahili veri aktarma mekanizması kullanılarak), çeşitli ortamlardaki en kısa yol belirlenebilir. Yol üzerinde kalan feromon konsantrasyonu ne kadar yüksek olursa, karıncanın ilgili yolu seçme olasılığı da o kadar yüksek olacaktır. Aynı zamanda, feromon konsantrasyonu zaman geçtikçe azalacaktır. Dolayısıyla, karınca kolonisinin davranışının sonucu olarak, karıncalar sürekli olarak bir geri bildirim mekanizması aracılığıyla en kısa yiyecek bulma yolunu belirleme sürecini öğrenecek ve optimize edecektir. ACO algoritması, yol planlamasında yaygın olarak kullanılmaktadır.
2. Algoritma ilkeleri
ACO'da, yapay karıncalar adı verilen yazılımsal temsilciler, belirli bir optimizasyon problemine iyi çözümler arar. ACO'yu uygulamak için optimizasyon problemi, ağırlıklı bir grafik üzerinde en iyi yolu bulma problemine dönüştürülür. Yapay karıncalar (bundan sonra karıncalar olarak ifade edilecektir) grafik boyunca hareket ederek kademeli olarak çözümler oluşturur. Çözüm oluşturma süreci stokastiktir ve feromon modeline - yürütme sırasında değerleri karıncalar tarafından değiştirilen grafik bileşenleriyle (düğümler veya kenarlar) ilişkili parametre kümesine - bağlıdır.
Gezgin satıcı problemi için algoritmayı inceleyelim. Elimizde bir şehir kümesi ve bunlar arasındaki mesafeler mevcuttur. Problem, her şehri yalnızca bir kez ziyaret eden minimum uzunlukta kapalı bir yol bulmaktır. Şehirler kümesinin grafik köşeleri kümesiyle ilişkilendirilmesiyle tanımlanan grafiğe yapı grafiği denir. Herhangi bir şehirden başka bir şehre gitmek mümkün olduğundan, yapı grafiği tamamen bağlantılıdır ve köşe sayısı şehir sayısına eşittir. Köşeler arasındaki kenar uzunluklarını, bu köşelerin temsil ettiği şehirler arasındaki mesafelerle orantılı olarak ayarlıyoruz ve feromon değerlerini ve sezgisel değerleri de grafik kenarlarıyla ilişkilendiriyoruz. Feromon değerleri çalışma zamanında değişir ve karınca kolonisinin kümülatif deneyimini yansıtır, sezgisel değerler ise probleme bağlı değerlerdir.
Karıncalar çözümleri şu şekilde oluştururlar. Her karınca rastgele seçilen bir şehirden (yapı grafiğinin tepe noktası) başlar. Ardından, her yapı adımında grafiğin kenarları boyunca hareket eder. Her karınca kendi yolunun hafızasını saklar ve sonraki adımlarda daha önce ziyaret edilen köşelere götürmeyen kenarlar arasından seçim yapar. Karınca, grafiğin tüm köşelerini ziyaret ettiği anda bir çözüm oluşturmuştur. Her inşa adımında karınca, henüz ziyaret edilmemiş köşelere götürenler arasından olasılıksal olarak takip edeceği bir kenar seçer. Olasılık kuralı, feromon değerlerine ve sezgisel bilgilere dayanır: bir kenarla ilişkili feromon ve sezgisel değer ne kadar yüksekse, karıncanın o kenarı seçme olasılığı da o kadar yüksektir. Tüm karıncalar yolculuklarını tamamladıktan sonra, kenarlardaki feromonlar güncellenir. Feromon değerlerinin her biri başlangıçta belirli bir yüzde oranında azaltılır. Bu prosedür, sonlanma kriteri karşılanana kadar tekrarlanır.
Feromon tabanlı iletişim, doğada yaygın olan bulunan en etkili iletişim yöntemlerinden biridir. Feromon, arılar, karıncalar ve termitler gibi sosyal böcekler tarafından temsilciler arasındaki iletişim için kullanılır. Uygulanabilirlikleri nedeniyle, yapay feromonlar çok robotlu ve sürü robot sistemlerinde benimsenmiştir.
Karıncalarımızın gerçekten en kısa yolu bulduğunu nasıl anlarız? Bunun için harika bir test örneği vardır: daire şeklinde dizilmiş noktalar. Onlar için en kısa yol her zaman aynı olacaktır - bir daire.
İlk ACO algoritması karınca sistemi olarak adlandırılmıştır ve gezgin satıcı problemini çözmeyi amaçlamıştır. Bu problemdeki hedef, bir şehir kümesini birbirine bağlamak için ileri geri en kısa yolu bulmaktır. Genel algoritma nispeten basittir ve her biri olası şehir turlarından birini yapan karıncalara dayanır. Her aşamada, karınca bazı kurallara göre bir şehirden diğerine bir yol seçer:
- Her şehri tam olarak bir kez ziyaret etmelidir;
- Uzak bir şehrin seçilme olasılığı daha düşüktür (görünürlük);
- İki şehir arasındaki sınıra döşenen feromon izi ne kadar yoğunsa, bu sınırın seçilme olasılığı da o kadar yüksektir;
- Yolunu tamamlayan karınca, yol kısaysa geçtiği tüm kenarlara daha fazla feromon bırakır;
- Her yinelemeden sonra feromon izleri buharlaşır.
Şekil 1. Beş düğüm noktasında olası yollara bir örnek
3. Değiştirilmiş versiyon
ACO algoritmalarının en popüler varyantlarından birkaçı bilinmektedir. Onları inceleyelim:
Karınca sistemi (Ant System, AS).
Karınca sistemi ilk ACO algoritmasıdır.
Karınca kolonisi sistemi (Ant Colony System, ACS).
Karınca kolonisi sistemi algoritmasında, orijinal karınca sistemi üç açıdan değiştirilmiştir:
1. Kenar seçimi sömürü lehinedir (yani, daha fazla feromon içeren en kısa kenarları seçme olasılığı lehinedir);
2. Karıncalar bir çözüm oluştururken yerel feromon güncelleme kuralı uygulayarak seçtikleri kenarlardaki feromon seviyelerini değiştirirler;
3. Her yinelemenin sonunda, yalnızca en iyi karınca, değiştirilmiş global feromon güncelleme kuralını uygulayarak izleri güncelleyebilir.
Elit karınca sistemi (Elite Ant System, EAS).
Bu algoritmada, global en iyi çözüm, her yinelemeden sonra diğer tüm karıncalarla birlikte izine feromon bırakır (iz tekrar ziyaret edilmemiş olsa bile). Elit stratejinin amacı, mevcut en iyi rotanın bağlantılarını içeren bir çözüm oluşturmak adına tüm karıncaların aramasını yönlendirmektir.
Maks-min karınca sistemi (Max-Min Ant System, MMAS).
Bu algoritma, her bir iz üzerindeki maksimum ve minimum feromon seviyesini kontrol eder. Sadece en iyi global tur veya en iyi tekrar turu, izine feromon ekleyebilir. Arama algoritmasının durgunlaşmasını önlemek için, her bir iz üzerindeki olası feromon miktarı aralığı [τ max, τ min] aralığı ile sınırlandırılmıştır. Çözümün keşfini hızlandırmak için tüm kenarlar τ max ile başlatılır. Durgunluğa yaklaşırken izler τ max değeriyle yeniden başlatılır.
Mertebeye dayalı karınca sistemi (rank-based Ant System, ASrank).
Tüm çözümlere uzunluklarına göre mertebe verilir. Bu yinelemede yalnızca sabit sayıda en iyi karınca zorluklarını güncelleyebilir. Biriken feromon miktarı her bir çözüm için tartılır, böylece daha kısa yollara sahip çözümler daha uzun yollara sahip çözümlerden daha fazla feromon biriktirir.
Paralel karınca kolonisi optimizasyonu (Parallel Ant Colony Optimization, PACO).
İletişim stratejileriyle karınca kolonisi sistemi (ACS).
Yapay karıncalar birkaç gruba ayrılır. Gezgin satıcı problemi üzerinde çalışan ACS'de gruplar arasındaki feromon seviyelerini güncellemek için yedi iletişim yöntemi önerilmiştir.
Sürekli ortogonal karınca kolonisi (Continuous Orthogonal Ant Colony, COAC).
COAC feromon biriktirme mekanizması, karıncaların iş birliği içerisinde ve verimli bir şekilde çözüm aramasına olanak tanır. Ortogonal tasarım yöntemi kullanılarak, izin verilen alandaki karıncalar, gelişmiş global arama yeteneği ve yüksek hassasiyetle seçtikleri alanları hızlı ve verimli bir şekilde keşfedebilirler. Ortogonal tasarım yöntemi ve adaptif yarıçap ayarlama yöntemi, pratik problemlerin çözümünde daha kapsamlı avantajlar sağlayacak şekilde diğer optimizasyon algoritmalarına da genişletilebilir.
Tekrarlamalı karınca kolonisi optimizasyonu (Recursive Ant Colony Optimization, RACO).
Bu, tüm arama alanını birkaç alt alana bölen ve sorunu bu alt alanlarda çözen karınca kolonisinin tekrarlamalı bir formudur. Tüm alt alan adlarının sonuçları karşılaştırılır ve en iyi birkaç tanesi bir sonraki seviyeye geçer. Seçilen sonuçlara karşılık gelen alt alanlar daha da alt bölümlere ayrılır ve istenilen doğruluk elde edilene kadar işlem tekrarlanır. Bu yöntem, yanlış jeofizik ters çözümler üzerinde test edilmiştir ve iyi bir şekilde çalışmaktadır.
Yukarıda ele alınan karınca kolonisi algoritmaları başlangıçta optimizasyon problemlerini grafikler üzerinde çözmek için geliştirilmiştir. Problem bu tür algoritmalara entegre edilir; problem koşulları algoritma parametreleri (grafik düğümlerinin koordinatları) olarak verilir. Bu nedenle, ACO ilkelerine dayanan algoritmalar oldukça özelleşmiştir. Sabit koordinatlar kullanmadığımız için bu tür algoritmalar bizim görevlerimiz için uygulanabilir değildir. Çünkü aynı olanlar da dahil olmak üzere herhangi bir koordinata sahip olabiliriz. Sinir ağlarının eğitimi de dahil olmak üzere finansal enstrümanların ticaretindeki çok çeşitli optimizasyon problemlerini çözmek amacıyla, özel testlerimizi geçebilmesi için yeni bir evrensel algoritma geliştirmemiz gerekiyor, yani bu, yepyeni bir ACO olmalıdır.
Algoritmanın temel konsepti üzerinde düşünelim. Tıpkı kanonik versiyonda olduğu gibi, bir karınca kolonimiz olacaktır. Seyahat edilen yolları feromonla işaretleyemeyiz, çünkü çok boyutlu bir uzayda herhangi bir yere gidebilirler, rotaları ezberleyip kaydedebilirler. Dahası, sürekli adım varlığıyla bu uygun değildir, çünkü aynı rotanın takip edilme olasılığı sıfıra eğilimlidir. Ek olarak, düğümleri ezberlemeye hiç gerek yoktur, çünkü tekrarlar olmadan sıralı geçiş sorunu olmayacaktır. Peki, ne yapmalıyız? Bu aşamada, konseptin geliştirilmesinde hangi yönde ilerleneceği tamamen belirsizdir.
O halde, yeni algoritmamızı kanonik olandan ayıran ana noktaları bir kez daha not edelim:
1. Uzayda sabit nokta yoktur.
2. Yoldan sadece belirli bir sırayla geçmeye gerek yoktur.
3. Yol olmadığı için feromonla işaretlenecek bir şey de yoktur.
Şimdi, karınca kolonisi fikrini aklımızda tutarak neye sahip olduğumuza bakalım. Feromonla karıncaların gittikleri yolu değil bulundukları noktaları işaretleyebiliriz. Uygunluk fonksiyonunun değerini, mevcut yinelemede karıncanın bulunduğu yerdeki feromon miktarı olarak belirleyelim. Daha sonra karıncalar en çok feromonun bulunduğu koordinatlara doğru hareket etmek zorunda kalacaklardır. Ancak tüm karıncalar tek bir noktaya, yani en fazla feromona sahip olan noktaya koştuğunda bir sorunla karşılaşabiliriz. Noktaların optimize edilen fonksiyonun değişkenleri olduğu düşünüldüğünde bu, problem için en iyi çözüm olmayabilir. Klasik ACO'da düğüme giden yolun uzunluğunun da önemli olduğunu biliyoruz. Seçilen yol ne kadar kısa olursa o kadar iyidir. Bu yüzden, karıncanın mevcut konumundan gitmesi gereken yere kadar olan mesafeyi hesaplamamız gerekiyor. Bir sonraki yer diğer karıncaların bulunduğu yerdir, yani karıncalar birbirlerine doğru belirli bir rastgelelikle hareket etmelidir.
Harekete ne tür bir rastgelelik ekleyebiliriz?
- İlk olarak, bir sonraki konum seçilirken etki edecek bir rastgelelik katsayısı (PheromoneEffect_P) ekleyelim.
- İkinci olarak, bir sonraki konuma olan mesafeyi dikkate alan bir rastgelelik katsayısı (PathLengthEffect_P) ekleyelim (mesafe ne kadar kısaysa, yolun seçilme ihtimali de o kadar yüksektir).
Böylece, bir sonraki konumu seçmek için iki kritere sahibiz - karıncaların bulunduğu her spesifik konumdaki feromon miktarı ve çiftler halinde tüm bu noktalar arasındaki mesafe. Ancak, bunu sadece bu iki seçim kriterini kullanarak yapsak bile, karıncalar uzayda düğümleri kendi konumları olan hayali bir şeklin kenarları boyunca hareket edeceklerdir. Dolayısıyla, daha iyi bir yer bulma konusunda hiçbir ilerleme kaydedilmeyecektir.
Bu durumda, karıncaların hissedebileceği feromonun etki yarıçapını (PheromoneRadius_P, noktalar arasındaki mesafenin katsayısı) ekleyelim. Böylece karıncalar hareket ettikleri noktayı geçebileceklerdir. Bu, çok boyutlu uzayda hareket ederken karıncalara ek bir serbestlik sağlayacaktır.
Karıncaların yeni alanları keşfedebilmeleri için, herhangi bir koordinat boyunca yön vektöründen sapmalarına izin verilmesi gerekir. Belirli bir koordinattaki artıştan sapmayı yapacak olan PathDeviation_P katsayısını tanımlayalım. Çok boyutlu bir uzaya sahip olduğumuz için, yer değiştirme vektörünü takiben, bazı koordinatlar pozitif bir artışa, bazıları da negatif bir artışa sahip olabilir ve bu artışlar farklı modül değerlerinde olabilir. Bu katsayı, tamamının hesaba katılmasını mümkün kılacak ve karıncalara yiyecek arayışında (fonksiyonun ekstremumu) bir miktar daha serbestlik sağlayacaktır.
Peki yer değiştirme vektörü nedir ve karıncanın kat etmesi gereken mesafeyi nasıl ölçeriz? Bu soruları yanıtlamak adına, üç boyutlu uzayda iki nokta arasındaki mesafeyi hesaplamak için şu formülü kullanalım:
Yer değiştirme vektörünün görsel bir temsili, Şekil 2'ye bakılarak görülebilir.
Şekil 2. Hareket eden karınca vektörü
n boyutlu uzaylar için hesaplama benzerdir.
Bir karınca bir yinelemede (epoch) A noktasından B noktasına hareket eder ve olası bir kayma ile R noktasına ulaşır. B noktasından R noktasına olan mesafe PheromoneRadius_P katsayısına bağlıdır ve BR = AB x PheromoneRadius_P olarak hesaplanabilir.
AR çizgisi üzerinde yeni bir konumun olasılığı Şekil 2'de şematik olarak (ölçeklendirilmemiştir) gri bir alan şeklinde gösterilmektedir. Böylece, karıncanın yeni konumunun B noktasına yönelme olasılığı daha yüksektir. Olasılıkta kayma ilkesi bir önceki makalede tartışılmıştır.
Algoritma, her yinelemede aşağıdaki adımları içerir:
1) Karıncaların uzayda rastgele dizilimi.
2) Karıncalar için feromon miktarının (uygunluk fonksiyonu) değerinin belirlenmesi.
3) Bir karıncadan diğerine olan mesafenin hesaplanması.
4) Karıncanın hareket edeceği tercih edilen noktanın seçimi.
5) AR vektörü üzerindeki bir noktanın olasılığının hesaplanması.
6) AR vektörü üzerinde elde edilen noktanın koordinatlarının hesaplanması.
7) Durma koşulu karşılanana kadar 2. adımdan itibaren tekrarlanır.
Algoritma kodunun tanımına geçelim. Öncelikle karıncanın tanımını içeren bir yapı yazalım:
- c [] - karınca koordinatları,
- cLast [] - önceki koordinatlar,
- cB [] - tüm yinelemeler için en iyi koordinatlar,
- f - mevcut feromon değeri,
- fB - tüm yinelemelerde ulaşılan maksimum feromon değeri.
Karınca yapısının yapıcısında, f ve fB değerlerini 'double' türüyle temsil edilebilecek mümkün olan en düşük değerle başlatıyoruz.
//—————————————————————————————————————————————————————————————————————————————— struct S_Ants { double cLast []; //last coordinates double c []; //coordinates double cB []; //best coordinates double f; //pheromone of the current coordinates double fB; //pheromone of the best coordinates S_Ants () { f = -DBL_MAX; fB = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Dizisi tüm karıncalar arasındaki ikili mesafeleri saklamamıza izin verecek bir yapıya ihtiyacımız vardır.
struct S_Paths { double a []; };
Değiştirilmiş ACO algoritmamızı, önceki makalelerde ele alınan optimizasyon algoritmaları oluşturma konsepti çerçevesinde yeterli ve gerekli olan yalnızca şu üç public metodun bulunduğu bir sınıf şeklinde yazacağız: InitAnts (), Preparation () ve Dwelling (). Ayrıca GenerateRNDants () ve AntsMovement () private metotlarının yanı sıra algoritmalarımız için halihazırda standart hale gelmiş olan diğer private metotlar da vardır. ants [] yapısı dizisi, bir karınca kolonisidir.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ACO { public: //---------------------------------------------------------------------------- S_Ants ants []; //ants double rangeMax []; //maximum search range double rangeMin []; //manimum search range double rangeStep []; //step search double cB []; //best coordinates double fB; //pheromone of the best coordinates void InitAnts (const int coordinatesP, //number of opt. parameters const int antHillSizeP, double pheromoneEffectP, double pathLengthEffectP, double pheromoneRadiusP, double pathDeviationP); void Preparation (); void Dwelling (); private: //---------------------------------------------------------------------------- S_Paths paths []; int coordinates; //number of coordinates int antHillSize; //ant hill size double goals []; double pheromoneEffect; double pathLengthEffect; double pheromoneRadius; double pathDeviation; bool dwelling; void GenerateRNDants (); void AntsMovement (); double SeInDiSp (double in, double inMin, double inMax, double step); double RNDfromCI (double min, double max); double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers); }; //——————————————————————————————————————————————————————————————————————————————
Başlatma metodunda, değişkenlere ve dizi büyüklüğüne ilk değerleri atıyoruz.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACO::InitAnts (const int coordinatesP, //number of opt. parameters const int antHillSizeP, double pheromoneEffectP, double pathLengthEffectP, double pheromoneRadiusP, double pathDeviationP) { fB = -DBL_MAX; coordinates = coordinatesP; antHillSize = antHillSizeP; pheromoneEffect = pheromoneEffectP; pathLengthEffect = pathLengthEffectP; pheromoneRadius = pheromoneRadiusP; pathDeviation = pathDeviationP; ArrayResize (rangeMax, coordinates); ArrayResize (rangeMin, coordinates); ArrayResize (rangeStep, coordinates); dwelling = false; ArrayResize (ants, antHillSize); ArrayResize (paths, antHillSize); for (int i = 0; i < antHillSize; i++) { ArrayResize (ants [i].c, coordinates); ArrayResize (ants [i].cLast, coordinates); ArrayResize (ants [i].cB, coordinates); ArrayResize (paths [i].a, antHillSize); } ArrayResize (cB, coordinates); ArrayResize (goals, antHillSize); } //——————————————————————————————————————————————————————————————————————————————
Her yinelemede ilk olarak Preparation () metodu çağrılır.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACO::Preparation () { if (!dwelling) { fB = -DBL_MAX; GenerateRNDants (); dwelling = true; } else AntsMovement (); } //——————————————————————————————————————————————————————————————————————————————
GenerateRNDants () metodu rastgele bir karınca kolonisi oluşturmaktan sorumludur. Karınca koordinatları belirlenen sınırlar dahilinde rastgele atanır.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACO::GenerateRNDants () { for (int s = 0; s < antHillSize; s++) { for (int k = 0; k < coordinates; k++) { ants [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]); ants [s].c [k] = SeInDiSp (ants [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); ants [s].cLast [k] = ants [s].c [k]; ants [s].cB [k] = ants [s].c [k]; } } } //——————————————————————————————————————————————————————————————————————————————
Dwelling () metodunda karıncaların mevcut koordinatlarını hatırlıyoruz ve mevcut yineleme sırasında elde edilen maksimum feromon değerlerini güncelliyoruz.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACO::Dwelling () { for (int i = 0; i < antHillSize; i++) { ArrayCopy (ants [i].cLast, ants [i].c, 0, 0, WHOLE_ARRAY); //remember the best coordinates for the ant if (ants [i].f > ants [i].fB) { ants [i].fB = ants [i].f; ArrayCopy (ants [i].cB, ants [i].c, 0, 0, WHOLE_ARRAY); } //remember the best coordinates for the anthill if (ants [i].f > fB) { fB = ants [i].f; ArrayCopy (cB, ants [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
AntsMovement (), algoritmanın ana metodudur. Şu eylemleri gerçekleştirir: bir karıncadan diğerine olan mesafeyi hesaplar, karıncanın hareket edeceği tercih edilen noktayı seçer, AR vektörü üzerindeki bir noktanın olasılığını hesaplar ve AR vektörü üzerinde elde edilen noktanın koordinatlarını hesaplar.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ACO::AntsMovement () { double rndPh; double rndPt; double summCoordinates = 0.0; double scores []; ArrayResize (scores, antHillSize); double maxPh = -DBL_MAX; double minPh = DBL_MAX; double maxPt = -DBL_MAX; double minPt = DBL_MAX; double goal; double goalBest = -DBL_MAX; int goalInd = 0; //measure the distance between all the ants----------------------------------- for (int i = 0; i < antHillSize; i++) { for (int k = 0; k < antHillSize; k++) { if (i == k) { paths [i].a [k] = DBL_MAX; continue; } for (int c = 0; c < coordinates; c++) summCoordinates += pow (ants [i].cLast [c] - ants [k].cLast [c], 2.0); paths [i].a [k] = pow (summCoordinates, 0.5); if (maxPt < paths [i].a [k]) maxPt = paths [i].a [k]; if (minPt > paths [i].a [k]) minPt = paths [i].a [k]; } } //---------------------------------------------------------------------------- for (int i = 0; i < antHillSize; i++) { maxPh = -DBL_MAX; minPh = DBL_MAX; for (int k = 0; k < antHillSize; k++) { if (i != k) { if (maxPh < ants [k].f) maxPh = ants [k].f; if (minPh > ants [k].f) minPh = ants [k].f; } } goalBest = -DBL_MAX; goalInd = 0; for (int k = 0; k < antHillSize; k++) { if (i != k) { rndPh = RNDfromCI (0.0, pheromoneEffect); rndPt = RNDfromCI (0.0, pathLengthEffect); goal = Scale (ants [k].f, minPh, maxPh, 0.0, 1.0, false) * rndPh * Scale (paths [i].a [k], minPt, maxPt, 0.0, 1.0, true) * rndPt; if (goalBest < goal) { goalBest = goal; goalInd = k; } } } double wayToGoal = paths [i].a [goalInd]; double radiusNearGoal = wayToGoal * pheromoneRadius; double endWay = wayToGoal + radiusNearGoal; double x = RNDfromCI (-1.0, 1.0); double y = x * x; if (x > 0.0) y = Scale (y, 0.0, 1.0, wayToGoal, endWay, false); else y = Scale (y, 0.0, 1.0, 0.0, wayToGoal, true); for (int j = 0; j < coordinates; j++) { double incrementFactor = y / wayToGoal; double coordDistance = ants [goalInd].cLast [j] - ants [i].cLast [j]; ants [i].c [j] = ants [i].cLast [j] + (coordDistance * incrementFactor); double w = coordDistance * RNDfromCI (-1.0, 1.0) * pathDeviation; ants [i].c [j] += w; ants [i].c [j] = SeInDiSp (ants [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } } //——————————————————————————————————————————————————————————————————————————————
Bir sayıyı bir sayısal aralıktan diğerine ölçekleme fonksiyonu da dikkat etmeye değerdir. Onu önceki makalelerde ele almıştık. Bu kez işlevselliğini genişleteceğiz. revers girdisi, aşağıdaki şekilde gösterildiği gibi ölçekleme yönünü değiştirmek için kullanılır.
Şekil 3. Bir sayıyı bir sayısal aralıktan diğerine ölçekleme.
1) Doğrudan ölçekleme; 2) Ters ölçekleme
//—————————————————————————————————————————————————————————————————————————————— double C_AO_ACO::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers) { if (OutMIN == OutMAX) return (OutMIN); if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0)); else { if (In < InMIN) return revers ? OutMAX : OutMIN; if (In > InMAX) return revers ? OutMIN : OutMAX; double res = (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN); if (!revers) return res; else return OutMAX - res; } } //——————————————————————————————————————————————————————————————————————————————
4. Test sonuçları
Skin test fonksiyonu üzerinde ACO.
Forest test fonksiyonu üzerinde ACO.
Megacity test fonksiyonu üzerinde ACO.
Şimdi sonuç zamanı. Geleneksel karınca kolonisi algoritması, finansal enstrümanların ticaretine yönelik optimizasyon problemleri için uygulanabilir değildir. Geleneksel versiyonun sınırlamalarından kaçınmak amacıyla, ACO'nun daha da geliştirilmesine olanak tanıyan tamamen yeni bir karınca kolonisi algoritması konseptinin ortaya çıkışına tanık olduk. Böyle bir algoritma, gezgin satıcı problemi de dahil olmak üzere çok çeşitli problemlere uygulanabilir.
Artık derecelendirme tablosunun yeni bir lideri vardır. Sonuçları daha ayrıntılı olarak inceleyelim. İlk olarak, test ortamının sonuçlarına göz atalım:
2022.10.27 16:46:28.678 Test_AO_ACO (EURUSD,M1) ============================= 2022.10.27 16:46:50.599 Test_AO_ACO (EURUSD,M1) 1 Skin's; Func runs 1000 result: 13.969156176320473; Func runs 10000 result: 13.986949123110085 2022.10.27 16:46:50.599 Test_AO_ACO (EURUSD,M1) Score1: 0.99502; Score2: 0.99599 2022.10.27 16:47:12.424 Test_AO_ACO (EURUSD,M1) 20 Skin's; Func runs 1000 result: 8.514904198298202; Func runs 10000 result: 11.56159524595023 2022.10.27 16:47:12.424 Test_AO_ACO (EURUSD,M1) Score1: 0.69826; Score2: 0.86403 2022.10.27 16:48:04.200 Test_AO_ACO (EURUSD,M1) 500 Skin's; Func runs 1000 result: 4.962716036996786; Func runs 10000 result: 6.488619274853463 2022.10.27 16:48:04.200 Test_AO_ACO (EURUSD,M1) Score1: 0.50498; Score2: 0.58800 2022.10.27 16:48:04.200 Test_AO_ACO (EURUSD,M1) ============================= 2022.10.27 16:48:25.999 Test_AO_ACO (EURUSD,M1) 1 Forest's; Func runs 1000 result: 15.805601165115196; Func runs 10000 result: 15.839944455892518 2022.10.27 16:48:25.999 Test_AO_ACO (EURUSD,M1) Score1: 0.99087; Score2: 0.99302 2022.10.27 16:48:47.897 Test_AO_ACO (EURUSD,M1) 20 Forest's; Func runs 1000 result: 3.568897096569507; Func runs 10000 result: 10.45940001108266 2022.10.27 16:48:47.897 Test_AO_ACO (EURUSD,M1) Score1: 0.22374; Score2: 0.65571 2022.10.27 16:49:41.855 Test_AO_ACO (EURUSD,M1) 500 Forest's; Func runs 1000 result: 1.3412234994286016; Func runs 10000 result: 2.7822130728041756 2022.10.27 16:49:41.855 Test_AO_ACO (EURUSD,M1) Score1: 0.08408; Score2: 0.17442 2022.10.27 16:49:41.855 Test_AO_ACO (EURUSD,M1) ============================= 2022.10.27 16:50:03.740 Test_AO_ACO (EURUSD,M1) 1 Megacity's; Func runs 1000 result: 11.8; Func runs 10000 result: 11.8 2022.10.27 16:50:03.740 Test_AO_ACO (EURUSD,M1) Score1: 0.78667; Score2: 0.78667 2022.10.27 16:50:26.002 Test_AO_ACO (EURUSD,M1) 20 Megacity's; Func runs 1000 result: 1.75; Func runs 10000 result: 3.9200000000000004 2022.10.27 16:50:26.002 Test_AO_ACO (EURUSD,M1) Score1: 0.11667; Score2: 0.26133 2022.10.27 16:51:21.075 Test_AO_ACO (EURUSD,M1) 500 Megacit 's; Func runs 1000 result: 0.6335999999999999; Func runs 10000 result: 1.2312 2022.10.27 16:51:21.075 Test_AO_ACO (EURUSD,M1) Score1: 0.04224; Score2: 0.08208 2022.10.27 16:49:41.075 Test_AO_ACO (EURUSD,M1) ============================= 2022.10.27 16:51:21.075 Test_AO_ACO (EURUSD,M1) All score for C_AO_ACO: 0.5468768583006471
Algoritma, özellikle 20 ve 500 fonksiyon testlerinde oldukça önde olmak üzere, mükemmel yakınsama ve iyi ölçeklendirme yetenekleri göstererek düzgün Skin fonksiyonunda iyi bir performans göstermiştir. Keskin kıvrımlara sahip düzgün Forest fonksiyonunda, ayrım daha da belirgindir. Algoritma, yerel ekstremumlara ulaştığında bile aramaya devam etmektedir. Ayrık Megacity fonksiyonunda, algoritma sadece 500 fonksiyonlu problemde rastgele RND algoritmasına üstünlük sağlamıştır.
| 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) | |||
| 1000 | 0.99502 | 0.69826 | 0.50498 | 0.99087 | 0.22374 | 0.08408 | 0.78667 | 0.11667 | 0.04224 | 0.54688 | |
| 10,000 | 0.99599 | 0.86403 | 0.58800 | 0.99302 | 0.65571 | 0.17442 | 0.78667 | 0.26133 | 0.08208 | ||
| 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 | ||
| 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 | ||
| 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 | ||
Değerlendirme
Algoritmanın çok sayıda ayarı vardır, bu nedenle daha da iyi sonuçlar almak mümkündür. Belirli görev türleri için özelleştirilebilir. İlk parametre PheromoneEffect_P yakınsama oranını doğrudan etkilemektedir. Bu özellikle parabol gibi düzgün monoton fonksiyonlar için iyidir. Yakınsama %100 olacaktır, ancak, yüksek olarak ayarlanırsa, bu aynı zamanda ayrık fonksiyonlarda yerel ekstremumlarda takılmaya da katkıda bulunacaktır.
İkinci parametre PathLengthEffect_P karıncaların tembellik derecesini yansıtır. Parametre değerinin yüksek olması durumunda, hareket için daha yakın hedefler seçilecektir. En iyi sonucu elde etmek adına bu parametreyi ilk parametreyle dengelemek gerekir. Bu parametre, karıncanın daha fazla yiyeceğin bulunduğu noktaya gitme arzusuna karşı bir denge sağlamak için tasarlanmıştır, böyle bir noktanın yerine küçük alanların daha ayrıntılı incelenmesi adına en yakın hedefler seçilebilir, bu da en iyi noktanın çok yakın olabileceği Forest fonksiyonu örneğinde olduğu gibi çok yararlı olabilir.
En önemli başarı, kanonik ACO'nun ana sorunundan kurtulmayı başarmış olmamızdır: sadece ayrık kombinasyonel problemleri çözme yeteneği. Artık karınca kolonisi algoritması sinir ağlarını eğitmek için kullanılabilir.
Görsel olarak, belirli bir kümelenmenin varlığı nedeniyle test ortamını gözlemlemek gerçekten ilginçtir: karıncalar çok boyutlu bir fonksiyonun ölçümlerinde belirli bir şekilde yoğunlaşarak yerel ekstremumların karakteristik gruplarını vurgulamaktadır. Belki de bu etki belirli problemleri çözmek için kullanılabilir, ancak bunun için daha fazla araştırma yapılması gerekecektir.
Algoritmanın ilginç bir özelliği vardır: iki değişkenli bir problemi çözerken, bir yerel ekstremuma takılma olasılığı, 40 değişkeni optimize ederken olduğundan biraz daha yüksektir. Algoritma, çok sayıda değişken olduğunda çözüm aramaya devam etmektedir. Bunun, arama uzayının tüm koordinatlarını birbirine bağlama aracı olarak bir vektör kullanmanın etkisi olduğunu varsayıyorum. Örneğin, bir karınca daha iyi yeni bir yere taşındıysa, bazı koordinatlarının tek tek değişmesi yerine, tüm koordinatları uzaysal olarak daha iyiye doğru değişecektir.
Oluşturulan algoritma yenidir ve ayrıntılı olarak keşfedilmemiştir, bu nedenle eğer bir kişi test ortamının 0,6'dan daha büyük bir nihai değer göstereceği algoritma ayarlarını paylaşırsa minnettar olurum, böylece tablonun sonuçlarını güncelleyebilirim. Bu talebim, daha önce ele aldığımız algoritmalar için de geçerlidir.
1. Algoritma oldukça hızlıdır.
2. Çok yönlüdür. Algoritma çeşitli optimizasyon problemlerinde kullanılabilir.
3. Sadece yerel ekstremumlara odaklanmaz.
4. Hem düzgün hem de ayrık fonksiyonlar için oldukça iyi yakınsar.
5. Ölçeklenebilirdir.
Dezavantajları:
1. Düzgün fonksiyonlarda PSO’dakinden daha fazla yakınsama için daha fazla yineleme gerekebilir, ancak bu, PSO'nun çoktan durduğu yerlerde bile aramaya devam etme yeteneğiyle kısmen dengelenir.
2. Algoritma parametrelerinin sonuç üzerinde güçlü etkisi vardır.
MetaQuotes Ltd tarafından Rusçadan çevrilmiştir.
Orijinal makale: https://www.mql5.com/ru/articles/11602
Popülasyon optimizasyon algoritmaları: Yapay arı kolonisi (Artificial Bee Colony, ABC)
Bear’s Power göstergesine dayalı bir ticaret sistemi nasıl geliştirilir?
Sıfırdan bir ticaret Uzman Danışmanı geliştirme (Bölüm 20): Yeni emir sistemi (III)
Force Index göstergesine dayalı bir ticaret sistemi nasıl geliştirilir?
- Ücretsiz ticaret uygulamaları
- İşlem kopyalama için 8.000'den fazla sinyal
- Finansal piyasaları keşfetmek için ekonomik haberler
Gizlilik ve Veri Koruma Politikasını ve MQL5.com Kullanım Şartlarını kabul edersiniz