Optimización de Colonia de Hormigas o Algoritmo Genético para el problema basado en porcentaje

Question

Así que recientemente me he sentido realmente fascinado con los algoritmos en general. Y recientemente implementé un algoritmo de optimización de colonias de hormigas para resolver el TSP (muy divertido, obviamente). Ahora he estado buscando otros "problemas" para resolver. Ahora quería implementar un algoritmo para resolver un problema que implique cumplir un requisito de porcentaje y estar por debajo de un límite arbitrario.

Por ejemplo:

de entrada del usuario:

1) limitar -i.e. cantidad de energía disponible para gastar.

2) "cromosoma" tipos -i.e. azul (subtipos - índigo, etc.), rojo (subtipos - granate, etc.), amarillo (subtipos - amarillo claro, etc.) - cada atributo principal como azul tiene un "grupo" para elegir que consiste en diferentes subtipos como índigo, azul claro, azul marino lo que sea. : cada uno de los subtipos de color tiene un costo variable asociado.

3) porcentaje de tipos necesarios para la solución "ideal" (puede introducir un +/-% para permitir más variedad). -i.e. 10% rojo, 30% azul, 60% amarillo.

Salida:

1) posibles soluciones finales que cumplen los dos requisitos, siendo a continuación - pero cerca de la - coste requerido y el cumplimiento de los requisitos de porcentaje de supertipos.

Así, por ejemplo.

Este es un ejemplo super simple, obviamente sería más complejo que esto en realidad.

usuario especifica coste debe ser como sigue = costo < = 105.

El usuario elige el 25% de azul, 25% de amarillo, 50% de rojo. con +/- 5% de desviación

piscinas disponibles para cada color

Azul: Indigo: coste = 25; Azul marino: costo = 30; Azul marino: costo = 75;

Amarillo: Amarillo claro: costo = 20; Amarillo oscuro: costo = 30; Súper amarillo oscuro (lol): costo = 75;

Rojo: Maroon: costo = 20; Rojo sangre: costo = 45; Rojo brillante: costo = 55;

Para que el algoritmo funcione y devuelva diferentes combinaciones.

Combinación 1: índigo, amarillo oscuro, rojo sangre: costo = 100: azul = 25%, amarillo = 30%, rojo = 55%.

Combinación 2: mar azul, amarillo claro, de color rojo sangre: coste = 105: azul = ~ 30%, amarillo = ~ 20%, rojo = ~ 50%

Combinación 3: así sucesivamente y así sucesivamente.

EDIT: Segunda edición

salida consistiría en conjuntos de diferentes combinaciones.

Por ejemplo, un soluciones podrían consistir en combinaciones como:

Una solución estaría representado por la siguiente:

Combinación 1: Costo = 20; 50% azul, 25% amarillo, 25% rojo;

Combinación 2: costo = 30; 10% azul, 50% amarillo, 40% rojo;

Combinación 3: costo = 50; 25% azul, 25% amarillo, 50% rojo;

Solución: = (combinación 1, combinación 2, combinación 3) costo total = 100, y consiste en x% azul, y% amarillo, z% rojo;

compare la solución a los requisitos, si es así, consérvela, si no la deseche.

FIN EDITAR

Así que mi pregunta es. Sé que un algoritmo genético funcionaría. Pero, ¿funcionaría una implementación de ACO también? Por ejemplo, azul, amarillo y rojo equivaldrían a "ubicaciones", entonces sus subtipos representarían diferentes "caminos".

Solo me pregunto qué podría ser una solución más eficiente o tal vez algún algoritmo diferente por completo. Soy bastante nuevo en esto y comencé a leer sobre él hace poco más de una semana.

EDIT: Primera edición

quiero especificar que quiero tener 5 buenas soluciones únicas (5 siendo un número arbitrario, podría ser 3, podría ser 20).

Answer 1

Su problema de color parece bastante trivial para mí, incluso la fuerza bruta sería rápido, supongo .. por lo que su colonia de hormigas más probable es que puede resolver también :)

Answer 2

El único problema que veo con su representación para la ACO, es el +/- X%.

Con un porcentaje fijo de cada color, sólo podía proceder como usted ha dicho:

azul amarillo y rojo son los lugares Los diferentes subtipos representan carreteras, y su peso dependerá del costo y de la pourcentage necesario.

A continuación, sólo se aplica el método de AOC como para el TSP, pero cambiando un poco la forma en que las hormigas se mueven:

1. feromonas añadiendo a un camino sólo si quedan satisfechas por las limitaciones de costo
2. Selección la longitud del camino más cercano a la "longitud óptima" = N% de el coste óptimo (en el ejemplo anterior, para la ruta de amarillo, el uno más cercana a 25% * 95)

Si desea agregar la restricción porcentaje flotando a continuación:

digamos que estés mejor costo es:

Cost = X1*light yellow +X2*sea blue+X3*blood red for example. 

si este costo no es óptimo se puede trabajar con algunos pequeños varations sobre X2 X1 y X3, para optimizar su coste:

por ejemplo X1-e y X2 + e iba a cambiar su coste por e*(costseablue-costLightYellow)

por ejemplo, dada una pequeña epsilon, para cada Xi par, Xj tal que 01.(el costo del color vinculado a i y j) puede intentar agregar epsilon a Xi y eliminarlo de Xj hasta que no pueda mejorar el costo para todas las parejas de Xi, Xj.

Answer 3

Si su gráfica satisface la desigualdad del triángulo, le sugiero que pruebe un árbol de expansión mínimo y un algoritmo de coincidencia de peso perfecto no bipartito. Christofides et al. le garantiza una solución dentro de 3/2 del óptimo. Un AOC puede darle un resultado bueno y rápido, pero debe optimizarlo para muchos problemas. He escrito un algoritmo de Christofides en php (phpclasses.org). Eres bienvenido a probarlo. No estoy seguro de si está funcionando. Da resultados a veces extraños. Es tal vez mi implementación del algoritmo Fleury?