Publiqué esta pregunta anteriormente en stackoverflow, donde se cerró como fuera de tema. Espero que sobreviva aquí.
En nuestro gimnasio de escalada, las rutas deben volver a establecerse de vez en cuando. Se aplican las siguientes reglas:
- Tenemos presas de escalada con diferentes colores en diferentes cantidades. - Cuando se establece una ruta en un sector, no se debe establecer ninguna otra ruta con el mismo color en ese sector o en los sectores cercanos para evitar confusiones.
- Deben evitarse algunas combinaciones de colores en un sector, como blanco / gris o rojo / rosa.
- El objetivo es tener cuatro rutas en cada sector, menos está bien si cuatro rompen las reglas anteriores.
He probado dos enfoques diferentes por ahora. El primero fue el recocido simulado donde inicialicé la pared con un patrón aleatorio de colores (pero con un peso de color dado) y calculé una maldad para cada combinación de colores. Esta maldad también se calculó para combinaciones entre un sector y sus vecinos. En cada iteración, una ruta elegida aleatoriamente del peor sector se intercambió con una ruta de otro sector elegido aleatoriamente. Esto mostró algún tipo de convergencia, pero el resultado no era utilizable (es decir, el estado resultante contenía sectores con colores dobles o triples).
Luego abordé el problema desde el lado opuesto y comencé con una pared vacía. Esta vez, cada color tenía una concentración que decaía de un sector a los sectores adyacentes. También se aumentó la concentración de colores similares, es decir, una ruta roja aumentó la concentración de naranja en un sector y sus alrededores. Una fuente aleatoria ponderada de colores (el cubo) me dio el siguiente color para la pared, que se colocó en el sector con la concentración más baja de este color. Si una concentración estaba por encima de cierto umbral, el color no se agregaba (sino que se volvía a colocar en el cubo). Esto fue un éxito parcial porque el estado del resultado no contenía ningún color doble, pero algunos sectores estaban vacíos o solo contenían un color.
Entonces: ¿Cuál podría ser un algoritmo apropiado para resolver este problema, dadas las reglas anteriores? Con mucho gusto agregaré más información cuando sea necesario.
Edición 1 - Más información:
- mi caso de prueba tiene 15 sectores,
- cada sector debe contener 4 rutas
- El gimnasio real tiene 3 edificios con un promedio de 50 sectores cada uno.
- algunos sectores están dispuestos alrededor de pilares, algunos están conectados por techos
- tenemos alrededor de 10 colores de espera diferentes
- La altura de los sectores varía entre 6 (sección de principiante) y 20 metros (13 vertical + 7 techo), por lo que consumen diferentes cantidades de bodegas. Sin embargo, el promedio es de aproximadamente 12 y esto puede considerarse constante.
- hay una cantidad limitada de cada color, las cantidades no son iguales
- algunos colores son más fáciles, otros más difíciles (es decir, podemos crear una ruta amarilla de cualquier dificultad, mientras que crear una ruta naranja muy fácil para los niños será casi imposible)
- algunos sectores son "más fáciles", por lo que los colores fáciles deberían ir allí (esto es opcional, nuestros creadores de rutas pueden hacer las cosas más difíciles o más fáciles dentro de un amplio rango).
- podemos decir con seguridad qué colores combinan bien en un sector o en sectores vecinos y qué combinaciones no. Hay algunas sorpresas, como el blanco y el negro (mal combo): ambos se vuelven grises mientras les quedan goma (zapatos) o tiza (manos).
- algunos colores de retención son combinaciones como violeta / blanco (en un patrón de rayas).
Edición 2: Algunas preguntas sobre algoritmos genéticos
Ahora descargué y compilé ParadisEO e incluso obtuve mi IDE (estoy usando Code :: Blocks) para compilar el ejemplo QuickStart. ParadisEO ofrece algoritmos genéticos con un solo objetivo, así como GA multiabjetivo. GertVdE sugirió calcular la idoneidad de cada sector y maximizar la suma de las idoneidades de todos los sectores como un solo objetivo. ¿Podría también maximizar la idoneidad de cada sector con una AG multipropósito? Eso sería unos 50 objetivos.
Además, estoy luchando con la definición de una función de cruce sensible. Como la cantidad máxima de cada color es fija, el cruce puede conducir a estados ilegales. Si permito más que la cantidad máxima dada anteriormente, el patrón general podría converger en una repetición de combinaciones menos "difíciles" donde los colores problemáticos han sido desechados. Por otro lado, también puedo tirar el exceso de colores hasta alcanzar el máximo, haciendo que la función de cruce no sea conservadora.
(Soy completamente nuevo en algoritmos genéticos)
fuente
Respuestas:
Resolvería el problema mencionado anteriormente utilizando un enfoque de algoritmo genético. Codifica cada solución como un vector de enteros:
Luego, define una función de aptitud como una suma ponderada de la mínima diferencia de color en cada sector y la cantidad de rutas en un sector (la cantidad de ceros en el vector). Puede usar el framework Paradiseo o Inspyred para una implementación de Algoritmos Genéticos.
fuente
Aquí hay una breve descripción general de mi implementación actual, intentaré mantener los conceptos y no entrar en detalles del lenguaje. Utilicé el Marco ParadisEO, que es la biblioteca de plantillas C ++ para algoritmos genéticos y agregué algo de impulso aquí y allá.
Colores de asimiento de escalada
Los colores retenidos se almacenan en un archivo XML como un par de nombre y cantidad de color. Las cantidades encontradas en un archivo se suman y normalizan. Esto hace posible expresar una cantidad como un recuento total de rutas que se pueden establecer con este color o como un porcentaje. Se asigna una identificación a cada color, comenzando con 1. El cero está reservado para una ruta "vacía".
Penalizaciones de combinación de colores
Algunos colores no combinan bien en un sector o en sectores adyacentes. Cada combinación de colores no tan buena se describe mediante los dos nombres de colores (como en el archivo XML anterior, ver arriba) y una "maldad" arbitraria. Internamente, los valores de maldad se almacenan en una matriz que está indexada por ID de color.
La pared
The Wall es una clase que deriva de la clase de representación del genoma de ParadisEO para que ParadisEO pueda manipularla y evaluarla, pero se agrega más funcionalidad. Cada gen representa un color de ruta por ID (incluido cero o vacío). Los sectores están representados por un par de índices para los genes, de modo que cada sector tiene un principio y un final. Primero usé iteradores para los genes, pero el objeto Wall tiene que ser construible, lo que invalidaría los iteradores sin trabajo adicional. Actualmente, todos los sectores tienen 4 rutas, pero eso será configurable en el futuro.
El muro también tiene un cubo de color. Este depósito contiene un contador para cada color, distribuido como se describe en el archivo XML de color. Los recuentos de colores se suman al número total de rutas en el Muro. Se puede elegir un color del cubo, disminuyendo el contador, y también se puede volver a poner, aumentando el contador.
Un color solo se puede agregar a un sector si el sector aún no contiene ese color (el sector debe permanecer "legal" cuando se agrega el color).
Operador de evaluación
El operador de evaluación resume todos los valores de maldad en un sector utilizando la matriz de maldad descrita anteriormente. El valor de cada sector se almacena en el vector de condición física (que también forma parte de la clase Wall), por lo que se trata de una AG multipropósito. Podría cambiar eso si fuera necesario.
Operador cruzado de dos puntos
El operador de cruce toma dos padres, crea una copia de cada uno (los descendientes) y luego realiza un cruce de dos puntos mediante la recombinación de sectores completos . La ventaja de esto es que los sectores siguen siendo legales (sin colores dobles). La desventaja de cualquier operación cruzada (para este problema) es que las crías resultantes pueden contener colores en exceso si los colores se agrupan en los padres. Se agregó una función de reparación que elimina las rutas en exceso (color cero) al azar. Por lo tanto, los descendientes tienen menos rutas que los padres de la reparación cambiaron la descendencia.
Mutación 1: Agregar ruta
La posible disminución en las rutas en los descendientes se explica por un operador de "agregar ruta". Toma un color del cubo del Muro y lo agrega a alguna parte. Si esa no es una operación legal, no hace nada (a veces no hay lugar legal para un color restante).
Mutación 2: intercambio aleatorio
Se intercambian dos rutas aleatorias de dos sectores aleatorios. Este par de intercambio se genera hasta que los sectores resultantes sean legales, luego se ejecuta el intercambio.
Mutación 3: cambio
Varios sectores se desplazan un lugar a la izquierda.
Ya no tengo tiempo, pero podría agregar más información más adelante. Especialmente la evaluación es bastante simple como es, y los componentes se programaron como prueba de conecpt. El GA realmente optimiza el Muro hasta cierto punto, pero los resultados no están listos para un uso real. Estoy seguro de que esto mejorará cuando haya hablado con los creadores de rutas y haya más reglas de evaluación disponibles. Las fotos también vendrán cuando estén disponibles.
fuente