Yapıcı işbirlikçi birlikte evrim - Constructive cooperative coevolution

yapıcı işbirlikçi birlikte evrimsel algoritma (C olarak da bilinir3) bir küresel optimizasyon algoritma yapay zeka çoklu başlangıç ​​mimarisine dayalı olarak açgözlü randomize uyarlamalı arama prosedürü (KAVRAMAK).[1][2] Mevcut olanı içerir işbirlikçi birlikte evrimsel algoritma (CC).[3] Ele alınan problem alt problemlere ayrıştırılır. Sorunun tamamını çözmek için bilgi alışverişi yapılırken bu alt problemler ayrı ayrı optimize edilir. Bir optimizasyon algoritması, genellikle ancak zorunlu değildir evrimsel algoritma, C'ye gömülüdür3 bu alt problemleri optimize etmek için. Gömülü optimizasyon algoritmasının doğası, C3davranışı belirleyici veya stokastik.

C3 optimizasyon algoritması başlangıçta şunlar için tasarlandı simülasyon tabanlı optimizasyon[4][5] ama için kullanılabilir küresel optimizasyon genel olarak sorunlar.[6] Diğer optimizasyon algoritmalarına, özellikle işbirlikli birlikte evrimleşmeye göre gücü, ayrılamayan optimizasyon problemlerini daha iyi idare edebilmesidir.[4][7]

Daha sonra Geliştirilmiş Yapıcı İşbirlikçi Birlikte Evrimsel Farklılık Evrimi (C3iDE), önceki sürümle birkaç sınırlamayı kaldırır. C'nin yeni bir öğesi3iDE, alt popülasyonların ileri düzeyde başlatılmasıdır. C3iDE, başlangıçta alt popülasyonları kısmen uyumlu bir şekilde optimize eder. Bir alt popülasyonun ilk optimizasyonu sırasında, birlikte adaptasyon için diğer alt bileşenlerin yalnızca bir alt kümesi dikkate alınır. Bu alt küme, tüm alt bileşenler dikkate alınana kadar adım adım artar. Bu C yapar3iDE, büyük ölçekli global optimizasyon problemlerinde (1000 boyuta kadar) çok etkilidir. işbirlikçi birlikte evrimsel algoritma (CC) ve Diferansiyel evrim.[8]

Geliştirilmiş algoritma daha sonra çok amaçlı optimizasyon.[9]

Algoritma

Aşağıdaki sözde kodda gösterildiği gibi, bir C iterasyonu3 iki aşamadan oluşur. Aşama I'de, yapıcı aşama, tüm soruna uygulanabilir bir çözüm adım adım inşa edilir. Her adımda farklı bir alt problem düşünmek. Son adımdan sonra, tüm alt problemler ele alınır ve sorunun tamamı için bir çözüm oluşturulur. Bu yapılandırılmış çözüm daha sonra yerel iyileştirme aşaması olan Faz II'de ilk çözüm olarak kullanılır. CC algoritması, oluşturulan çözümü daha da optimize etmek için kullanılır. Aşama II döngüsü, diğer alt problemlerin parametrelerini merkezi bir karatahta çözümüne sabit tutarken alt problemleri ayrı ayrı optimize etmeyi içerir. Bu her alt problem için yapıldığında, bulunan çözüm bir "işbirliği" adımı sırasında birleştirilir ve üretilen kombinasyonlar arasında en iyisi bir sonraki döngü için karatahta çözümü olur. Bir sonraki döngüde aynı şey tekrarlanır. Faz II ve dolayısıyla mevcut yineleme, CC algoritmasının aranması durduğunda ve önemli ölçüde daha iyi çözümler bulunamadığında sona erer. Ardından bir sonraki yineleme başlatılır. Bir sonraki yinelemenin başlangıcında, önceki yinelemelerin 1. Aşamasında bulunan çözümlerden yararlanılarak yeni bir uygulanabilir çözüm oluşturulur. Bu yapılandırılmış çözüm, daha sonra, ilk yinelemede olduğu gibi, Aşama II'de ilk çözüm olarak kullanılır. Optimizasyon için sonlandırma kriterlerinden birine ulaşılıncaya kadar bu tekrarlanır, örn. maksimum değerlendirme sayısı.

{SFaz 1} ← ∅süre sonlandırma kriterleri karşılanmadı yapmak    Eğer {SFaz 1} = ∅ sonra        {SFaz 1} ← SubOpt (∅, 1) eğer biterse    süre pFaz 1 tamamen inşa edilmemiş yapmak        pFaz 1 ← GetBest ({SFaz 1})        {SFaz 1} ← SubOpt (pFaz 1, bensonraki alt problem)    bitince    pFaz 2 ← GetBest ({SFaz 1})    süre durgun değil yapmak        {SFaz 2} ← ∅         her biri için alt problem i yapmak            {SFaz 2} ← SubOpt (pFaz 2,ben) sonu için        {SFaz 2} ← İşbirliği ({SFaz 2})        pFaz 2 ← GetBest ({SFaz 2})    bitincebitince

Çok amaçlı optimizasyon

C'nin çok amaçlı versiyonu3 algoritma [9] tek amaçlı C ile aynı böl ve yönet stratejisini kullanan Pareto tabanlı bir algoritmadır3 optimizasyon algoritması. Algoritma, artan bir alt problem alt kümesini göz önünde bulundurarak, alt popülasyonların gelişmiş yapıcı ilk optimizasyonları ile yeniden başlar. Alt küme, tüm alt problemlerin tamamı dahil edilene kadar artar. Bu ilk optimizasyonlar sırasında, en son dahil edilen alt problemin alt popülasyonu, çok amaçlı bir evrimsel algoritma tarafından geliştirilir. Alt popülasyon üyelerinin uygunluk hesaplamaları için, önceden optimize edilmiş alt popülasyonların her birinden ortak çalışan bir çözümle birleştirilirler. Tüm alt problemlerin alt popülasyonları başlangıçta optimize edildiğinde, çok amaçlı C3 optimizasyon algoritması, her bir alt problemi bir yuvarlak robin modası, ancak şimdi diğer tüm alt problemlerin alt gruplarından ortak çalışan çözümleri, değerlendirilmekte olan alt popülasyonun üyesiyle birleştirilir. Ortak çalışan çözümü, alt popülasyonun Pareto-optimal cephesini oluşturan çözümlerden rastgele seçilir. Ortak çalışan çözümlerine uygunluk ataması iyimser bir şekilde yapılır (yani "eski" bir uygunluk değeri, yenisi daha iyi olduğunda değiştirilir).

Başvurular

Yapıcı işbirlikçi birlikte evrim algoritması, farklı problem türlerine uygulanmıştır, örn. bir dizi standart karşılaştırma işlevi,[4][6] sac levha pres hatlarının optimizasyonu[4][5] ve etkileşimli üretim istasyonları.[5] C3 algoritması, diğerlerinin yanı sıra, diferansiyel evrim algoritması[10] ve parçacık sürüsü iyileştirici[11] alt problem optimizasyonları için.

Ayrıca bakınız

Referanslar

  1. ^ T.A. Feo ve M.G.C. Resende (1989) "Hesaplama açısından zor bir küme kapsayan problem için olasılıksal bir buluşsal yöntem". Yöneylem Araştırma Mektupları, 8:67–71, 1989.
  2. ^ T.A. Feo ve M.G.C. Resende (1995) "Açgözlü randomize uyarlamalı arama prosedürleri". Küresel Optimizasyon Dergisi, 6:109–133, 1995.
  3. ^ M.A. Potter ve K.A. D. Jong, "İşlev optimizasyonuna ortak evrimsel bir yaklaşım", içinde PPSN III: Uluslararası Evrimsel Hesaplama Konferansı Bildirileri. Doğadan Paralel Problem Çözme Konulu Üçüncü Konferans Londra, İngiltere: Springer-Verlag, 1994, s. 249–257.
  4. ^ a b c d Glorieux E., Danielsson F., Svensson B., Lennartson B., "Yapıcı İşbirliğine Dayalı Birlikte Devrimci yaklaşım kullanarak etkileşimli üretim istasyonlarının optimizasyonu", 2014 IEEE International Conference on Automation Science and Engineering (CASE), pp.322-327, Ağustos 2014, Taipei, Tayvan
  5. ^ a b c Glorieux E., Svensson B., Danielsson F., Lennartson B., "Pres Hattı Optimizasyonuna Uygulanan Yapıcı Bir Birlikte Evrimsel Algoritma", 24. Uluslararası Esnek Otomasyon ve Akıllı Üretim Konferansı Bildirileri (FAIM), s. 909-917, Mayıs 2014, San Antonio, Teksas, ABD
  6. ^ a b Glorieux E., Svensson B., Danielsson F., Lennartson B .: "Büyük ölçekli küresel optimizasyon için yapıcı ortak evrim", Journal of Heuristics, 2017.
  7. ^ Glorieux E., Danielsson F., Svensson B., Lennartson B .: "Etkileşimli üretim istasyonları için yapıcı işbirliğine dayalı birlikte evrimsel optimizasyon", International Journal of Advanced Manufacturing Technology, 2015.
  8. ^ Glorieux E., Svensson B., Danielsson F., Lennartson B., "Büyük Ölçekli Optimizasyon için Geliştirilmiş Yapıcı İşbirlikçi Birlikte Evrimsel Diferansiyel Evrim", 2015 IEEE Sempozyum Serisi Hesaplamalı Zeka, Aralık 2015
  9. ^ a b Glorieux E., Svensson B., Danielsson F., Lennartson B., "Robotik baskı hattı eğiliminin çok amaçlı yapıcı işbirliğine dayalı birlikte evrimsel optimizasyonu", Engineering Optimization, Cilt. 49, Sayı. 10, 2017, s. 1685-1703
  10. ^ Storn, Rainer ve Kenneth Price. "Diferansiyel evrim - sürekli alanlar üzerinde küresel optimizasyon için basit ve verimli bir buluşsal yöntem" Journal of global optimization 11.4 (1997): 341-359.
  11. ^ Eberhart, Russ C. ve James Kennedy. "Parçacık sürüsü teorisini kullanan yeni bir optimize edici", Mikro makine ve insan bilimi konulu altıncı uluslararası sempozyum bildirileri. Cilt 1. 1995.