Algoritmo genético en un optiproblema similar a la mochila

Question

Tengo un problema de optimización que intento resolver usando un algoritmo genético. Básicamente, hay una lista de 10 variables con valores reales encuadernados (-1 < = x < = 1), y necesito maximizar alguna función de esa lista. La trampa es que solo hasta 4 variables en la lista pueden ser! = 0 (condición de subconjunto).

Matemáticamente hablando: para alguna función f: [-1, 1]^10 -> R min f (X) S.T. | {var en X con var! = 0} | < = 4

Algunos antecedentes en f: La función NO es similar a ningún tipo de función objetivo de la mochila, como Suma x * peso o algo por el estilo.

Lo que he intentado hasta ahora:

Sólo un algoritmo genético básico sobre el genoma [-1, 1]^10 con 1 punto de cruce y mutación alguna gaussiana de las variables. Traté de codificar la condición del subconjunto en la función de acondicionamiento físico utilizando solo los primeros 4 valores distintos de cero (cero como en lo suficientemente cerca de 0). Este enfoque no funciona tan bien y el algoritmo está atascado en las 4 primeras variables y nunca usa valores más allá de eso. Vi algún tipo de GA para el problema 01-mochila donde este enfoque funcionó bien, pero aparentemente esto funciona solo con variables binarias.

¿Qué me recomendarías probar ahora?

Answer 1

Usted podría intentar un "giro" al estilo de paso: elegir uno de los valores distintos de cero a convertirse en cero, y reemplazarlo mediante el establecimiento de uno de los valores cero existentes a ser distinto de cero. (Mi término "pivote" proviene de la programación lineal, en la cual un pivote es el paso básico en el método simplex).

caso más simple sería ser equitativamente al azar en la selección de cada uno de estos valores; puede elegir un valor aleatorio, o valores múltiples, para la nueva variable distinta de cero. Un tipo de paso más local sería usar un paso Gaussiano solo en las variables distintas de cero existentes, pero si una de esas variables cruza cero, genera variaciones que pivotan a uno de los valores cero. (Tenga en cuenta que estos no son mutuamente exclusivos, ya que puede agregar fácilmente ambos tipos de pasos).

Si usted tiene alguna información sobre el comportamiento local de su puntaje de aptitud, se puede tratar de utilizar eso para guiar a su elección. El hecho de que la evolución real no se fija en la función de aptitud, no significa que no se puede ...

Answer 2

Si su función de adecuación es rápido y sucio para evaluar entonces es barato para aumentar su tamaño total de la población.

El problema está ejecutando en es que usted está tratando de seleccionar dos cosas completamente diferentes al mismo tiempo. Desea seleccionar qué 4 genomas le interesan y, a continuación, qué valores son óptimos.

Veo dos formas de hacerlo.

1. Creas 210 diferentes "especies". Cada especie está definida por 4 de los 10 genomas que pueden usar. Luego puede ejecutar un algoritmo genético en cada especie por separado (ya sea en serie o en paralelo dentro de un clúster).

2. cada organismo tiene sólo 4 valores del genoma (al crear descendencia azar elegir qué genomas al azar). Cuando dos organismos se aparean, solo se cruzan con genomas que coinciden.Si su par de organismos contiene 3 genomas comunes, entonces podría elegir aleatoriamente cuál del genoma puede preferir como el cuarto. También podría, como heurística, evitar el apareamiento de organismos que parecen ser demasiado genéticamente diferentes (es decir, un par que comparte dos o menos genomas puede representar una mala descendencia).

Espero que le de algunas ideas para trabajar.

Answer 3

¿Su GA resuelve bien el problema sin la restricción del subconjunto? Si no, es posible que desee abordar eso primero.

En segundo lugar, puede hacer que su restricción sea suave en lugar de dura: sancione la aptitud de una solución para cada variable de valor cero que tenga, más allá de 4. (Puede comenzar aflojando aún más la restricción, permitiendo 9 variables de 0 valores; luego 8, etc., y asegurándose de que el GA sea capaz de manejar esas variantes de problema antes de dificultar el problema).

En tercer lugar, intente con un cruce de 2 puntos o multipunto en lugar de 1 punto.

Espero que ayude.

-Ted