Técnicas de optimización discretas y de alta dimensión

Question

Supongamos que tenemos un vector binario de longitud 1000 en el que podemos activar o desactivar cada elemento. Cada uno de los $2^{1000}$ diferentes escenarios revela una recompensa. El objetivo es encontrar la configuración con la máxima recompensa en un tiempo finito.

Obviamente, una búsqueda aleatoria será completamente inútil porque el espacio a explorar es sencillamente demasiado grande. ¿Existen técnicas de optimización (bayesianas o no bayesianas) que muestren un buen rendimiento empírico en este tipo de problemas? Agradecería que alguien me indicara alguna bibliografía al respecto.

Answer 1

Algo que me viene a la mente al instante son algoritmos genéticos (véase algoritmos-genéticos ), ya que operaciones como las mutaciones y los cruces son triviales para los bits (operaciones lógicas NOT, AND, OR, XOR). No tienen por qué ser los más rápidos, pero tienen la ventaja de explorar con bastante eficacia el panorama de soluciones (por lo que están ligeramente sesgados hacia la exploración en la exploración frente a la explotación). Se sabe que los algoritmos genéticos funcionan con este tipo de problemas, aunque no tengo mucha experiencia con este tipo de problemas de optimización, por lo que no afirmaré que sea el mejor enfoque posible.