Adaptiv koordinata tushishi - Adaptive coordinate descent

Adaptiv koordinata tushishi[1] ning yaxshilanishi koordinatali tushish algoritm ajratib bo'lmaydigan optimallashtirish yordamida moslashuvchan kodlash.[2] Moslashuvchan koordinatali tushish yondashuvi asta-sekin koordinata tizimining o'zgarishini yaratadi, shunday qilib yangi koordinatalar ob'ektiv funktsiyaga nisbatan iloji boricha bog'langan. Moslashuvchan koordinatali tushish zamonaviy texnologiyalar bilan raqobatbardosh ekanligi ko'rsatildi evolyutsion algoritmlar va quyidagi invariantlik xususiyatlariga ega:

  1. Funktsiyaning bir xil o'zgarishiga nisbatan o'zgarmaslik (miqyosi)
  2. Ga nisbatan o'zgarmaslik ortogonal transformatsiyalar qidirish maydonining (aylanish).

CMA - shunga o'xshash Adaptiv kodlashni yangilash (b) asosan asoslangan asosiy tarkibiy qismlarni tahlil qilish (a) koordinatali tushish usulini (c) ajratib bo'lmaydigan muammolarni optimallashtirishgacha kengaytirish uchun ishlatiladi (d).

Adaptiv koordinatali tushish illust.png

Tegishli koordinatalar tizimining moslashuvi, ajratib bo'lmaydigan funktsiyalar bo'yicha koordinatalar tushishidan ustun bo'lish uchun adaptiv koordinat tushishini ta'minlaydi. Quyidagi rasm ikkala algoritmning 2 o'lchovli yaqinlashishini aks ettiradi Rozenbrok funktsiyasi maqsad funktsiya qiymatiga qadar , dastlabki nuqtadan boshlab .

Rosenbrock2D.png

Moslashuvchan koordinatali tushish usuli maqsadga 325 ta funktsiyani baholashdan so'ng erishiladi (koordinataga tushishdan 70 baravar tezroq), bu bilan taqqoslanadigan gradyanga asoslangan usullar. Algoritm har bir D takrorlanishida koordinatalar tizimini yangilab turadigan bo'lsa, u chiziqli vaqt murakkabligiga ega, u katta (D >> 100) chiziqli bo'lmagan optimallashtirish uchun ham javob beradi.

Tegishli yondashuvlar

Moslashuvchan koordinatalar tizimidan foydalangan holda optimallashtirishga birinchi yondashuvlar 1960 yillarda taklif qilingan edi (qarang, masalan, Rozenbrokning usuli ). Brent algoritmi deb ham ataladigan asosiy eksa (PRAXIS) algoritmi - bu optimallashtirilgan funktsiyaning kvadratik shaklini qabul qiladigan va konjuge qidiruv yo'nalishlari to'plamini bir necha bor yangilaydigan lotinsiz algoritm.[3]Algoritm, ammo maqsad funktsiyasini masshtablash uchun o'zgarmas emas va uning ma'lum darajadagi saqlovchi konversiyalarida ishlamay qolishi mumkin (masalan, maqsad funktsiyasining kvadratik bo'lmagan shakliga olib keladi). Yaqinda PRAKSIS tahlilini topish mumkin.[4]Amaliy dasturlar uchun qarang:[5] bu erda statik ko'pburchak to'siqlar bilan 3D kosmosda robot-manipulyator yo'lini rejalashtirish uchun qadam ko'lamini moslashtirish va mahalliy koordinatalar tizimining aylanishi bilan koordinatali tushishning adaptiv yondashuvi taklif qilingan.

Shuningdek qarang

Adabiyotlar

  1. ^ Loshchilov, I .; M. Shoenauer; M. Sebag (2011). "Moslashuvchan koordinatali tushish" (PDF). Genetik va evolyutsion hisoblash konferentsiyasi (GECCO). ACM tugmachasini bosing. 885-892 betlar.
  2. ^ Nikolaus Xansen. "Adaptiv kodlash: Qanday qilib qidiruv koordinatalari tizimining o'zgarmasligini ko'rsatish ". Tabiatdan parallel masalalar echish - PPSN X, 2008 yil sentyabr, Dortmund, Germaniya. 205-214 betlar, 2008 yil.
  3. ^ Brent, RP (1972). Hosilsiz minimallashtirish algoritmlari. Prentice-Hall.
  4. ^ Ali, U .; Kickmeier-Rust, MD (2008). "Asosiy eksa minimallashtirishni takomillashtirish bo'yicha uch bosqichli foydalanuvchi strategiyasini amalga oshirish va qo'llash". Amaliy miqdoriy usullar jurnali. 505-513 betlar.
  5. ^ Pavlov, D. (2006). "Uch o'lchovli kosmosda manipulyator yo'lini rejalashtirish". Informatika - nazariya va ilovalar. Springer. 505-513 betlar.

Tashqi havolalar

  • SOURCE CODE ACD ACD - moslashuvchan koordinatali tushish uchun MATLAB manba kodi