Adaptacyjne zejście współrzędnych

Adaptacyjne zejście ze współrzędnych to ulepszenie algorytmu zejścia ze współrzędnymi do nierozdzielnej optymalizacji poprzez zastosowanie kodowania adaptacyjnego. Adaptacyjne podejście ze spadkiem współrzędnych stopniowo buduje transformację układu współrzędnych, tak aby nowe współrzędne były jak najbardziej zderelowane w odniesieniu do funkcji celu. Wykazano, że adaptacyjne zejście współrzędnych jest konkurencyjne w stosunku do najnowocześniejszych algorytmów ewolucyjnych i ma następujące właściwości niezmienności:

Niezmienność względem monotonicznych przekształceń funkcji (skalowanie)
Niezmienniczość względem przekształceń ortogonalnych przestrzeni poszukiwań (obrót).

CMA (b) oparta głównie na analizie głównych składowych (a) służy do rozszerzenia metody zejścia współrzędnych (c) na optymalizację nierozdzielnych problemów (d).

Adaptacja odpowiedniego układu współrzędnych umożliwia adaptacyjne zejście współrzędnych przewyższające zejście współrzędnych w przypadku funkcji nierozdzielnych. Poniższy $\displaystyle x_{0}=(-3,-4)}$ zbieżność obu algorytmów na dwuwymiarowej $funkcji$ Rosenbrocka do wartości funkcji docelowej , $)$ od punktu początkowego .

Adaptacyjna metoda zejścia ze współrzędnych osiąga wartość docelową już po 325 ocenach funkcji (około 70 razy szybciej niż zejście ze współrzędnych), co jest porównywalne z metodami opartymi na gradiencie . Algorytm ma liniową złożoność czasową, jeśli aktualizuje układ współrzędnych co D iteracje, nadaje się również do wielkoskalowej (D>>100) optymalizacji nieliniowej.

Odpowiednie podejścia

Pierwsze podejścia do optymalizacji z wykorzystaniem adaptacyjnego układu współrzędnych zaproponowano już w latach 60-tych (patrz np. metoda Rosenbrocka ). Algorytm PRincipal Axis (PRAXIS), zwany także algorytmem Brenta, jest algorytmem pozbawionym pochodnych, który przyjmuje postać kwadratową optymalizowanej funkcji i wielokrotnie aktualizuje zbiór sprzężonych kierunków poszukiwań. Algorytm nie jest jednak niezmienny w stosunku do skalowania funkcji celu i może zawieść przy pewnych przekształceniach zachowujących rangę (np. doprowadzi do niekwadratowego kształtu funkcji celu). Najnowszą analizę PRAXIS można znaleźć w . Aby zapoznać się z praktycznymi zastosowaniami, zobacz, gdzie zaproponowano adaptacyjne podejście do opadania współrzędnych z adaptacją wielkości skoku i rotacją lokalnego układu współrzędnych do planowania ścieżki robota-manipulatora w przestrzeni 3D ze statycznymi przeszkodami wielokątnymi.

Zobacz też

Linki zewnętrzne

KOD ŹRÓDŁOWY ACD ACD jest kodem źródłowym MATLAB-a dla Adaptive Coordinate Descent