algorithm - tiempo - graficas en python matplotlib

Algoritmo genético para dibujar un gráfico? Problema de asignación de posición

Question

Tengo un problema de asignación a la mano y me pregunto qué conveniente sería aplicar técnicas de búsqueda locales para llegar a una solución deseable (el espacio de búsqueda es bastante grande).

Tengo un gráfico dirigido (un diagrama de flujo) que me gustaría visualizar en el plano 2-D de una manera que sea muy claro, comprensible y fácil de leer por ojo humano. Por lo tanto; Asignaré (x, y) posiciones a cada vértice. Estoy pensando en resolver este problema utilizando recocido simulado, algoritmos genéticos o cualquier otro método que pueda sugerir

Entrada: un grafo G = (V, E)
Salida: un conjunto de asignaciones, {(xi, yi) for each vi in V} . En otras palabras, a cada vértice se le asignará una posición (x, y) donde las coordenadas son todas enteros y> = 0.

Estos son los criterios que utilizaré para juzgar una solución (acepto cualquier sugerencia):

• El número de bordes que se cruzan debe ser mínimo,
• Todos los bordes fluyen en una dirección (es decir, de izquierda a derecha),
• Alta resolución angular (el ángulo más pequeño formado por dos bordes incidentes en el mismo vértice),
• Área pequeña: menos importante.

Además; Tengo una configuración inicial (asignación de posiciones a vértices), hecha a mano. Es muy complicado y es por eso que estoy tratando de automatizar el proceso.

Mis preguntas son,

• ¿Qué tan sabio sería ir con las técnicas de búsqueda locales? ¿Qué tan probable es que produzca un resultado deseado?

• ¿Y con qué debería empezar? Recocido simulado, algoritmos genéticos o algo más?

• ¿Debería sembrar al azar al comienzo o usar la configuración inicial para comenzar?

• O bien, si ya conoce una implementación / pseudo-código / cosa similar, indíquemela.

Cualquier ayuda será apreciada. Gracias.

EDITAR: No necesita ser rápido, no en tiempo real. Además; | V | = ~ 200 y cada vértice tiene aproximadamente 1.5 bordes salientes en promedio. El gráfico no tiene componentes desconectados. Implica ciclos.

Answer 1

Para responder a tu primera pregunta, debo decir que depende. Depende de una serie de factores diferentes, tales como:

• ¿Qué tan rápido debe ser (debe hacerse en tiempo real?)
• Cuantos vértices hay
• ¿Cuántos bordes hay en comparación con el número de vértices (es decir, es un gráfico denso o disperso?)

Si debe hacerse en tiempo real, entonces las técnicas de búsqueda locales no serían las mejores ya que podrían demorar un poco antes de obtener un buen resultado. Solo serían lo suficientemente rápidos si el tamaño del gráfico fuera pequeño. Y si es pequeño para empezar, no debería tener que usar la búsqueda local para comenzar.

Ya existen algoritmos para representar gráficos como usted describe. La pregunta es, ¿en qué punto el problema crece demasiado para que sean efectivos? No sé la respuesta a esa pregunta, pero estoy seguro de que podría investigar un poco para averiguarlo.

Ahora vamos a sus preguntas sobre la implementación de una búsqueda local.

Desde mi experiencia personal, el recocido simulado es más fácil de implementar que un algoritmo genético. Sin embargo, creo que este problema se traduce muy bien en ambas configuraciones. Empezaría con SA sin embargo.

Para el recocido simulado, comenzarías con una configuración aleatoria. Entonces puede perturbar la configuración al azar moviendo uno o más vértices en una distancia aleatoria. Estoy seguro de que puede completar los detalles del algoritmo.

Para un enfoque de algoritmo genético, también puede comenzar con una población aleatoria (cada gráfico tiene coordenadas aleatorias para los vértices). Una mutación puede ser como la perturbación en el algoritmo SA que describí. La recombinación simplemente puede tomar vértices aleatorios de los padres y usarlos en el gráfico secundario. De nuevo, estoy seguro de que puedes completar los espacios en blanco.

El resumen: utilice la búsqueda local solo si su gráfica es lo suficientemente grande como para garantizarla y si no necesita hacerlo súper rápido (digamos, en menos de unos pocos segundos). De lo contrario, use un algoritmo diferente.

EDITAR: a la luz de los parámetros de tu gráfica, creo que puedes usar cualquier algoritmo que sea más fácil de codificar. Con V = 200, incluso un algoritmo O (V ^ 3) sería suficiente. Personalmente siento que el recocido simulado sería más fácil y la mejor ruta.

Answer 2

Sugeriría mirar http://www.graphviz.org/Theory.php ya que graphviz es uno de los principales visualizadores gráficos de código abierto.

Dependiendo de la tarea, tal vez tenga sentido usar graphviz para la visualización.

Answer 3

http://oreilly.com/catalog/9780596529321 - En este libro, puede encontrar la implementación del algoritmo genético para la visualización precisa del gráfico 2D.

En situaciones similares, prefiero usar un algoritmo genético. También puede comenzar con población inicializada aleatoriamente: de acuerdo con mi experiencia después de algunas iteraciones, encontrará una solución bastante buena (pero tampoco la mejor).

Además, usando java, puedes poner en paralelo este algoritmo (estrategia de islas aisladas): es una mejora bastante eficiente.

También me gustaría aconsejarte Algoritmo de evolución diferencial . Según mi experiencia, encuentra la solución mucho más rápidamente que la optimización genética.

Answer 4

Este documento es una muy buena visión general de los diversos enfoques. El libro de Roberto Tomassia también es una buena apuesta.

Answer 5

function String generateGenetic()
String genetic = "";
for each vertex in your graph
    Generate random x and y;
    String xy = Transform x and y to a fixed-length bit string;
    genetic + = xy;
endfor
return genetic;

escriba una función de doble evaluación (cadena genética) que le dará un nivel de estatificación. (probablemente en función de la cantidad de bordes que se cruzan y los bordes de dirección).

tu programa:

int population = 1000;
int max_iterations = 1000;
double satisfaction = 0;
String[] genetics = new String[population]; //this is ur population;
while((satisfaction<0.8)&&(count<max_iterations)){
    for (int i=0;i<population;i++){
        if(evaluate(genetics[i])>satisfaction)
            satisfaction = evaluate(genetics[i]);
        else
            manipulate(genetics[i]);
    }
}

funciton manipular puede voltear un poco de la cadena o varios bits o una porción que codifica xey de un vértice o tal vez generar completamente una nueva cadena genética o tratar de resolver un problema dentro de ella (dirigir un borde).