Descenso de coordenadas adaptativo
Descenso de coordenadas adaptativo [1] es una mejora del algoritmo de descenso de coordenadas a una optimización no separable mediante el uso de codificación adaptativa . [2] El enfoque de descenso de coordenadas adaptativo construye gradualmente una transformación del sistema de coordenadas de modo que las nuevas coordenadas estén lo más descorrelacionadas posible con respecto a la función objetivo. Se demostró que el descenso de coordenadas adaptativas es competitivo con los algoritmos evolutivos de última generación y tiene las siguientes propiedades de invariancia:
La actualización de codificación adaptativa similar a CMA (b) se basa principalmente en el análisis de componentes principales (a) se utiliza para extender el método de descenso de coordenadas (c) a la optimización de problemas no separables (d).
La adaptación de un sistema de coordenadas apropiado permite que el descenso de coordenadas adaptativo supere al descenso de coordenadas en funciones no separables. La siguiente figura ilustra la convergencia de ambos algoritmos en la función de Rosenbrock bidimensional hasta un valor de función objetivo , comenzando desde el punto inicial .
El método de descenso de coordenadas adaptativo alcanza el valor objetivo después de solo 325 evaluaciones de funciones (aproximadamente 70 veces más rápido que el descenso de coordenadas), que es comparable a los métodos basados en gradientes . El algoritmo tiene una complejidad de tiempo lineal si actualiza el sistema de coordenadas cada D iteraciones, también es adecuado para la optimización no lineal a gran escala (D >> 100).
Los primeros enfoques para la optimización utilizando un sistema de coordenadas adaptativo ya se propusieron en la década de 1960 (ver, por ejemplo, el método de Rosenbrock ). El algoritmo PRincipal Axis (PRAXIS), también conocido como algoritmo de Brent, es un algoritmo sin derivadas que asume la forma cuadrática de la función optimizada y actualiza repetidamente un conjunto de direcciones de búsqueda conjugadas. [3] El algoritmo, sin embargo, no es invariante al escalado de la función objetivo y puede fallar bajo ciertas transformaciones que preservan el rango (por ejemplo, conducirá a una forma no cuadrática de la función objetivo). Se puede encontrar un análisis reciente de PRAXIS en. [4] Para aplicaciones prácticas, ver [5] donde se propuso un enfoque de descenso de coordenadas adaptativo con adaptación de tamaño de paso y rotación del sistema de coordenadas local para la planificación de la ruta del robot-manipulador en un espacio 3D con obstáculos poligonales estáticos.