Un generador de paisajes convexas multidimensionales de propósito general
Autores: Liu, Wenwen; Yuen, Shiu Yin; Chung, Kwok Wai; Sung, Chi Wan
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un generador de paisajes convexas multidimensionales de propósito general
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Heurística
Algoritmos evolutivos
Funciones convexas
Geometría computacional
Generador de paisajes convexos
Broyden-Fletcher-Goldfarb-Shanno
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
Los algoritmos heurísticos y evolutivos se proponen para resolver desafiantes problemas de optimización del mundo real. En la comunidad evolutiva, se han propuesto muchos problemas de referencia para evaluaciones empíricas de algoritmos. Una de las clases de problemas de prueba más importantes es la clase de funciones convexas, en particular la función de esfera de -dimensiones. Sin embargo, el tipo de función convexa es algo limitado. En principio, se puede seleccionar un conjunto de funciones de base convexas y utilizar operaciones que conserven la convexidad para generar una familia de funciones convexas. Este método introducirá inevitablemente un sesgo a favor de las funciones de base. En este artículo, el problema se resuelve empleando ideas de geometría computacional, lo que da como resultado el primer generador de paisajes convexas multidimensionales de propósito general. El nuevo generador propuesto tiene la ventaja de ser genérico, lo que significa que no tiene sesgo hacia una función analítica específica. Se genera un conjunto de puntos aleatorios de -dimensiones para la construcción de una envoltura convexa de -dimensiones. La parte superior de la envoltura convexa se elimina considerando la normal de los polígonos. La parte restante define una función convexa. Se muestra que la complejidad de construir la función es , donde es el número de polígonos de la función convexa. Para que el método funcione como una función de referencia, se generan consultas de una entrada dimensional arbitraria y el generador debe devolver el valor de la función convexa. La complejidad de responder a la consulta es . La convexidad de la función del generador se verifica con una prueba de razón no convexa. El rendimiento del generador también se evalúa utilizando el algoritmo de descenso de gradiente Broyden-Fletcher-Goldfarb-Shanno (BFGS). El código fuente del generador está disponible.
Descripción
Los algoritmos heurísticos y evolutivos se proponen para resolver desafiantes problemas de optimización del mundo real. En la comunidad evolutiva, se han propuesto muchos problemas de referencia para evaluaciones empíricas de algoritmos. Una de las clases de problemas de prueba más importantes es la clase de funciones convexas, en particular la función de esfera de -dimensiones. Sin embargo, el tipo de función convexa es algo limitado. En principio, se puede seleccionar un conjunto de funciones de base convexas y utilizar operaciones que conserven la convexidad para generar una familia de funciones convexas. Este método introducirá inevitablemente un sesgo a favor de las funciones de base. En este artículo, el problema se resuelve empleando ideas de geometría computacional, lo que da como resultado el primer generador de paisajes convexas multidimensionales de propósito general. El nuevo generador propuesto tiene la ventaja de ser genérico, lo que significa que no tiene sesgo hacia una función analítica específica. Se genera un conjunto de puntos aleatorios de -dimensiones para la construcción de una envoltura convexa de -dimensiones. La parte superior de la envoltura convexa se elimina considerando la normal de los polígonos. La parte restante define una función convexa. Se muestra que la complejidad de construir la función es , donde es el número de polígonos de la función convexa. Para que el método funcione como una función de referencia, se generan consultas de una entrada dimensional arbitraria y el generador debe devolver el valor de la función convexa. La complejidad de responder a la consulta es . La convexidad de la función del generador se verifica con una prueba de razón no convexa. El rendimiento del generador también se evalúa utilizando el algoritmo de descenso de gradiente Broyden-Fletcher-Goldfarb-Shanno (BFGS). El código fuente del generador está disponible.