Moslashuvchan koordinata tushishi

Moslashuvchan koordinata tushishi – moslashtirilgan kodlash texnikasidan foydalangan holda ajralmas holda optimallashtirish uchun koordinata tushishi algoritmining yangilangan versiyasi. Moslashuvchan koordinata tushishi koordinata tizimining oʻzgarishlarini ketma-ket ravishda tuzadi hamda shunda yangi koordinatalar maqsad funktsiyasiga nisbatan maksimal darajada bogʻlanadi. Moslashuvchan koordinata tushishi hozirgi evolyutsiya algoritmlari bilan raqobatbardosh ekanligi hamda quyidagi oʻzgarmaslik xususiyatlariga ega ekanligi koʻrsatilgan yaʼni:

• Funktsiyaning monotonik oʻzgarishida oʻzgarmaslik (masshtablash)
• qidiruv maydonining ortogonal oʻzgarishlarida oʻzgarmaslik (aylanish).

CMA ga oʻxshash adaptiv kodlash (b), asosan asosiy komponent tahliliga (a) iqtisoslashgan, ajralmas optimallashtirish muammolarini (d) hal qilish uchun koordinatalarni tushirish usulini (c) kengaytirish uchun ishlatiladi(d).

Qabul qilinadigan koordinatalar tizimini qulaylashtirish adaptiv koordinatalarni tushirish usulini ajralmas funktsiyalar boʻyicha koordinata tushishidan avzalroq qilish imkonini beradi. Quyidagi rasmda ikki oʻlchovli Rosenbrok funksiyasi uchun ikkala algoritmning funksiyaning maqsadli qiymatiga yaqinlashishi koʻrsatilgan. $10^{-10}$ nuqtadan boshlab $x_{0}=(-3,-4)$ ga teng.

Moslashuvchan koordinata tushishi atigi 325 funktsiyani baholashda maqsadli qiymatga etadi (koordinata tushishidan taxmin boʻyicha 70 baravar tez boʻladi), buni asosan gradientga asoslangan usullar bilan solishtirish mumkin. Agar koordinatalar tizimi har D iteratsiyada yangilanib borsa, algoritm chiziqli vaqt murakkabligiga ega boʻladi va katta chiziqli boʻlmagan optimallashtirish muammolari uchun mos keladi (D>>100).

Tegishli yondashuvlar

Koordinatalar tizimini moslashtirishdan foydalangan holda birinchi optimallashtiruvchi yondashuvlar 1960-yillarda taklif qilingan hisoblanadi (masalan , Rosenbrok usullari). Asosiy oʻq (PRAXIS) algoritmi, yana shuningdek, Brent algoritmi sifatida ham tanilgan, lotinsiz algoritm boʻlib, optimallashtirilayotgan funksiyaning kvadratik shaklini qabul qiladi va unda qidiruv yoʻnalishlari toʻplamini vaqti-vaqti bilan yangilab turadi. Algoritm maqsad funksiyasini masshtablashda invariant emas va baʼzi darajani saqlaydigan oʻzgarishlarda muvaffaqiyatsiz boʻlishi mumkin.

Statik koʻpburchak toʻsiqlari boʻlgan uch oʻlchovli fazoda robot manipulyatorining yoʻlini rejalashtirish uchun qadam moslashuvi hamda mahalliy koordinata aylanishi bilan adaptiv koordinata tushishidan foydalanish misoli tasvirlangan.

Adabiyotlar

• Loshchilov I., Schoenauer M., Sebag M. Adaptive Coordinate Descent // Genetic and Evolutionary Computation Conference (GECCO). – ACM Press, 2011. – P. 885–892.
• Nikolaus Hansen. Adaptive Encoding: How to Render Search Coordinate System Invariant // Parallel Problem Solving from Nature – PPSN X / G. Rudolph, T. Jansen, S. Lucas, C. Poloni, N. Beume (Eds.). – Dortmund, Germany, 2008. – T. 5199. – (LNCS).
• Brent R. P. Algorithms for minimization without derivatives. – Prentice-Hall, 1972.
• Ali U., Kickmeier-Rust M. D. Implementation and Applications of a Three-Round User Strategy for Improved Principal Axis Minimization // Journal of Applied Quantitative Methods. – 2008.
• Pavlov D. Manipulator path planning in 3-dimensional space // Computer Science--Theory and Applications. – Springer, 2006.

Havolalar

• Manba kodi ACD ACD adaptiv koordinata tushishi uchun MATLAB manba kodi