Cómo determinar la posición de un punto
El algoritmo de colonia de hormigas (ACO), también conocido como algoritmo de hormigas, es una tecnología basada en el azar que se utiliza para encontrar rutas optimizadas en gráficos. Fue propuesto por Marco Dorigo en su tesis doctoral en 1992 y se inspiró en el comportamiento de búsqueda de caminos de las hormigas en busca de alimento.
El algoritmo de colonia de hormigas es un algoritmo evolutivo simulado. La investigación preliminar muestra que el algoritmo tiene muchas propiedades excelentes. Los resultados del algoritmo de colonia de hormigas se compararon con los del algoritmo genético en términos de diseño óptimo de los parámetros del controlador PID. Los resultados de la simulación numérica muestran que el algoritmo de colonia de hormigas es un nuevo método de optimización evolutiva simulada con efectividad y valor de aplicación.
El algoritmo de colonia de hormigas es un nuevo método heurístico general para resolver problemas de optimización combinatoria. Tiene las características de retroalimentación positiva, computación distribuida y búsqueda heurística codiciosa constructiva. Al establecer un modelo matemático apropiado, la localización de fallas en la red de distribución basada en la sobrecorriente de falla se convierte en un problema de búsqueda de optimización global no lineal. Creado por Liu Hongping.
Resultados esperados:
Una sola hormiga comienza a buscar comida sin ser informada de su ubicación con antelación. Cuando una hormiga encuentra comida, libera una feromona al ambiente que atrae a otras hormigas, ¡por lo que cada vez más hormigas encuentran comida! Algunas hormigas no siempre repiten el mismo camino que otras hormigas. Encontrarán otro camino si el camino que toman es más corto que otros caminos, entonces, gradualmente, más y más hormigas se sentirán atraídas por este camino más corto. Finalmente, después de un período de operación, la mayoría de las hormigas pueden recorrer repetidamente el camino más corto.
Principio:
¿Por qué las hormiguitas pueden encontrar comida? ¿Son inteligentes? Imagínense, si tuviéramos que diseñar un programa de inteligencia artificial para hormigas, ¿qué complejidad tendría que ser? Primero, debe programar a las hormigas para que den instrucciones de acuerdo con el terreno apropiado para evitar obstáculos de manera inteligente. En segundo lugar, para que las hormigas encuentren comida, debe dejarlas atravesar todos los puntos del espacio. En tercer lugar, si desea dejar que las hormigas; para encontrar la ruta más corta, debe calcular todas las rutas posibles y comparar sus tamaños. Más importante aún, debe programar con cuidado, porque un error en el programa puede causar un error en el programa. ¡Qué programa tan increíble! Es tan complicado que me temo que nadie puede completar un procedimiento tan largo y engorroso.
Sin embargo, en realidad no es tan complicado como crees. ¡En el programa anterior, el código del programa principal de cada hormiga tiene solo más de 100 líneas! ¿Por qué un programa tan simple puede hacer que las hormigas hagan cosas tan complicadas? La respuesta es: la aparición de reglas simples. De hecho, cada hormiga no necesita entender el mundo entero como imaginamos, en realidad solo se preocupan por la información inmediata dentro de un rango pequeño y usan algunas reglas simples para tomar decisiones basadas en esta información local. De esta manera, se reduce la complejidad. Se destaca en el comportamiento colectivo de la colonia de hormigas. ¡Esta es la ley explicada por la vida artificial y la ciencia de la complejidad! Entonces, ¿cuáles son estas reglas simples? Los siguientes son los detalles:
1. Rango:
El rango que observa la hormiga es un mundo cuadrado. La hormiga tiene un parámetro de radio de velocidad (generalmente 3), entonces puede. observar El rango que alcanza es un mundo cuadrado de 3 * 3, y la distancia que puede moverse también está dentro de este rango.
2. Entorno:
El entorno donde se ubican las hormigas es un mundo virtual, en el que hay obstáculos, otras hormigas y feromonas. Hay dos tipos de feromonas, una es. encontrar comida Feromonas alimenticias que arrojan las hormigas, una es la feromona del nido que arrojan las hormigas que han encontrado su nido. Cada hormiga sólo puede percibir información ambiental dentro de su propio rango. El entorno hace que las feromonas desaparezcan a un cierto ritmo.
3. Reglas de búsqueda de alimento:
Busca comida dentro del rango que cada hormiga puede sentir, si hay alguna, ve directamente allí. De lo contrario, depende de si hay feromona y compara qué punto tiene más feromona dentro del rango que se puede detectar, para ir al lugar con más feromona. Cada hormiga cometerá un error con una pequeña probabilidad cuando la haya. más feromona, por lo que no irá al lugar donde está la feromona. Vaya a donde hay más feromonas.
Las reglas de la hormiga para encontrar un nido son las mismas que las anteriores, excepto que responde a las feromonas del nido pero no a las feromonas del alimento.
4. Reglas de movimiento:
Cada hormiga se moverá en la dirección con más feromonas. Cuando no haya feromonas alrededor para guiarla, las hormigas se moverán en la dirección original. inercia El movimiento también tiene una pequeña perturbación aleatoria en la dirección del movimiento. Para evitar que la hormiga deambule por el lugar, recordará el punto por el que acaba de caminar recientemente. Si descubre que el siguiente punto al que quiere ir ha sido caminado recientemente, intentará evitarlo.
5. Reglas para evitar obstáculos:
Si hay un obstáculo en la dirección en la que la hormiga quiere moverse, elegirá aleatoriamente otra dirección, si hay una guía de feromonas, lo hará; sigue el camino que busca. Come según las reglas.
7. Reglas para difundir feromonas:
Cada hormiga difunde la mayor cantidad de feromonas cuando encuentra comida o un nido por primera vez. Cuanto más avanza, más feromonas difunde.
Según estas reglas, no existe una relación directa entre las hormigas, pero cada hormiga interactúa con el entorno que la rodea, y los vínculos de feromonas en realidad conectan a las hormigas entre sí. Por ejemplo, cuando una hormiga encuentra comida, no le dirá directamente a otras hormigas que hay comida aquí, sino que emitirá feromonas al ambiente, de modo que cuando otras hormigas pasen cerca de ella, sentirán la presencia de feromonas y luego responderán en consecuencia. Las feromonas encuentran alimento.
Pregunta:
En este caso, ¿cómo encuentran comida las hormigas?
Si no hay hormigas buscando comida, no hay feromonas útiles en el ambiente, entonces, ¿por qué las hormigas pueden encontrar comida de manera relativamente eficiente? Esto se debe a los patrones de movimiento de las hormigas, especialmente en ausencia de feromonas. Primero, debe mantener una cierta inercia tanto como sea posible, lo que permite que la hormiga avance tanto como sea posible (primero, el frente está fijo aleatoriamente en una dirección) en lugar de girar o vibrar en su lugar innecesariamente; Debe haber un cierto grado de aleatoriedad. Aunque la dirección es fija, no puede moverse en línea recta como las partículas, pero tiene perturbaciones aleatorias. Esto hace que el movimiento de la hormiga tenga un cierto propósito, tratando de mantener la dirección original, pero también tenga nuevos experimentos, especialmente cuando encuentre obstáculos, inmediatamente cambiará la dirección. Esto puede considerarse como un proceso de selección, es decir, el entorno. Los obstáculos en la hormiga hacen que una dirección de la hormiga sea correcta y la otra incorrecta. Esto explica por qué una hormiga todavía puede encontrar comida bien escondida en un mapa complejo como un laberinto.
Por supuesto, si una hormiga encuentra comida, otras hormigas seguirán las feromonas y encontrarán rápidamente la comida.
¿Cómo encuentran las hormigas el camino más corto? Esto se debe en parte a las feromonas y en parte al medio ambiente, específicamente al reloj de la computadora. Donde hay más feromonas, pasan más hormigas y se juntan más hormigas. Supongamos que hay dos caminos desde el hormiguero hasta la comida, e inicialmente hay la misma cantidad de hormigas en ambos caminos (o más hormigas en el camino largo, no importa). Cuando las hormigas caminan por un camino hasta el final, regresarán inmediatamente. De esta manera, las hormigas en cortocircuito pasan menos tiempo caminando de ida y vuelta. En otras palabras, la frecuencia de repetición es más rápida, por lo que recorren este camino por unidad. tiempo Cuantas más hormigas caminen por el camino, más feromonas se desbordarán naturalmente. Naturalmente, más hormigas se sentirán atraídas por este camino y más feromonas se desbordarán. ... y lo contrario ocurre con los caminos más largos, por lo que cada vez más hormigas se reúnen en el camino más corto, encontrando así aproximadamente el camino más corto. Algunas personas pueden preguntar sobre el camino más corto local y el camino más corto global. De hecho, las hormigas se acercarán gradualmente al camino más corto global. Esto se debe a que la hormiga cometerá errores, es decir, no irá a un lugar con altas feromonas y encontrará otro camino según una cierta probabilidad. Esto puede entenderse como una especie de innovación si este tipo de innovación puede acortar el tiempo. camino, entonces, de acuerdo con el principio que acabamos de mencionar, atraerá más hormigas.
Extensión
Siguiendo las huellas de las hormigas, ¿qué encontraste? A través de los principios y operaciones prácticas anteriores, no es difícil encontrar que la razón por la que las hormigas tienen un comportamiento inteligente se debe enteramente a sus reglas de comportamiento simples, y estas reglas se combinan con los dos aspectos siguientes:
1 . Diversidad Sexo
2. Retroalimentación positiva
La diversidad garantiza que las hormigas no caigan en callejones sin salida y bucles infinitos cuando buscan comida. Los mecanismos de retroalimentación positiva garantizan que se preserve información relativamente buena. Podemos pensar en la diversidad como capacidad creativa y la retroalimentación positiva como capacidad de aprendizaje. El poder de la retroalimentación positiva también se puede comparar con el poder de las opiniones autorizadas, mientras que la diversidad es la creatividad que rompe la autoridad. Es la combinación cuidadosa de estos dos puntos la que permite que surja un comportamiento inteligente.
Por extensión, la evolución natural, el progreso social y la innovación humana son inseparables de estos dos puntos: la diversidad asegura las capacidades innovadoras del sistema y la retroalimentación positiva asegura el fortalecimiento de las buenas características, la combinación de ambas. debería estar bien. Si hay demasiada diversidad, es decir, el sistema es demasiado activo, habrá demasiado movimiento aleatorio equivalente a las hormigas, y caerá en un estado de caos; por el contrario, si no hay suficiente diversidad, y lo positivo; El mecanismo de retroalimentación es demasiado fuerte, entonces el sistema será como un charco de agua estancada. Esto se manifiesta en las colonias de hormigas, es decir, el comportamiento de las hormigas es demasiado rígido y cuando el entorno cambia, las colonias de hormigas aún no pueden hacer los ajustes adecuados.
Dado que la complejidad y el comportamiento inteligente surgen de reglas básicas, y las reglas básicas se caracterizan por la diversidad y la retroalimentación positiva, usted puede preguntarse, ¿de dónde provienen estas reglas? ¿De dónde viene la diversidad y la retroalimentación positiva? Personalmente creo que las reglas provienen de la evolución natural. Según lo que acabo de decir, la evolución natural también se refleja en la inteligente combinación de diversidad y retroalimentación positiva. ¿Cuál es entonces el motivo de esta ingeniosa combinación? ¿Por qué el mundo parece tan vívido ante tus ojos? La respuesta es que el medio ambiente crea todo esto, y la razón por la que puedes ver un mundo realista es porque esas combinaciones de diversidad y retroalimentación positiva que no pueden adaptarse al medio ambiente han muerto y han sido eliminadas por el medio ambiente.
Descripción del parámetro:
Feromona máxima: cantidad total de feromona que tienen las hormigas al principio. Cuanto mayor sea la cantidad, más tiempo podrá almacenar la feromona el programa. Velocidad de eliminación de feromonas: Con el tiempo, se eliminarán las feromonas que ya existen en el mundo. Cuanto mayor sea este valor, más rápida será la tasa de eliminación.
La probabilidad de error indica la probabilidad de que la hormiga no vaya al área con la feromona más grande. Cuanto mayor sea el valor, mayor será la capacidad de innovación de la hormiga.
El radio de velocidad representa la longitud máxima que la hormiga puede recorrer a la vez y también representa el rango de detección de la hormiga.
La capacidad de memoria indica cuántas coordenadas de puntos por los que acaba de pasar la hormiga se pueden recordar. Este valor puede evitar que la hormiga gire localmente y se estanque. Cuanto mayor sea este valor, más lento funcionará todo el sistema. Cuanto más pequeño sea, más fácil será para las hormigas girar en su lugar.
En segundo lugar, puedes construir una estructura de datos gráfica y luego usar la búsqueda en amplitud o en profundidad para mejorar el algoritmo.
No lo dejaste claro, pero supongo esto es posible
Búsqueda primero en amplitud (BFS)
Búsqueda primero en amplitud (BFS)
Búsqueda primero en amplitud (también llamada búsqueda primero en amplitud) es el algoritmo más simple para buscar gráficos y el prototipo de muchos algoritmos de búsqueda de gráficos importantes. El algoritmo de ruta más corta de fuente única de Dijkstra y el algoritmo de árbol de expansión mínima de Prim utilizan ideas similares para la búsqueda en amplitud.
Después de conocer un gráfico G = (V, E) y un vértice fuente s, la búsqueda en amplitud explorará los bordes de G de forma sistemática para "descubrir" todos los vértices alcanzables por s y calcular la distancia (número mínimo de aristas) desde s hasta todos estos vértices. El algoritmo también genera un árbol de ancho con raíz en s que contiene todos los vértices alcanzables. Para cualquier vértice v alcanzable desde s, el camino de s a v en el árbol de anchura corresponde al camino más corto de s a v en el gráfico G, es decir, el camino que contiene el menor número de aristas.
Este algoritmo funciona igualmente bien en gráficos dirigidos y no dirigidos.
Se llama algoritmo de amplitud primero porque el algoritmo se expande hacia afuera desde el principio a través del límite entre el vértice descubierto y el último vértice descubierto, es decir, el algoritmo primero busca todos los vértices a una distancia. k entre sí, y luego busque los vértices restantes a una distancia k l de S.
Para mantener la búsqueda encaminada, la búsqueda en amplitud colorea cada vértice: blanco, gris o negro. Antes de que comience el algoritmo, todos los vértices son blancos. A medida que avanza la búsqueda, cada vértice se vuelve gris y luego negro. La primera vez que se encuentra un vértice durante la búsqueda, decimos que se encuentra, momento en el que se convierte en un vértice no blanco. Por lo tanto, se encuentran tanto el vértice gris como el vértice negro, pero el algoritmo de búsqueda en amplitud los diferencia para garantizar que la búsqueda se realice en amplitud. Si (u, v)∈E y el vértice u es negro, entonces el vértice v es gris o negro, es decir, se han descubierto todos los vértices adyacentes al vértice negro. Los vértices grises pueden estar adyacentes a algunos vértices blancos, que representan el límite entre los vértices descubiertos y no descubiertos.
En el proceso de búsqueda en amplitud, se construye un árbol en amplitud comenzando solo desde el nodo raíz de los vértices de origen. En un árbol de amplitud, decimos que el nodo u es el predecesor o padre del nodo v. Dado que un nodo sólo se puede descubrir una vez como máximo, puede tener como máximo un padre. Las relaciones de antepasado y descendiente relativas al nodo raíz se definen como de costumbre: si u se encuentra en un camino en el árbol desde la raíz s hasta el nodo v, entonces u se llama antepasado de v, y v es descendiente de u.
El siguiente proceso de búsqueda en amplitud BFS supone que el gráfico de entrada G = (V, E) se representa mediante una lista de adyacencia y utiliza varias estructuras de datos adicionales para cada vértice del gráfico para cada color; del vértice u∈V se almacena en la variable color[u], y el nodo padre del nodo u se almacena en la variable π[u]. Si u no tiene padre (por ejemplo, u = s o u aún no se ha recuperado), entonces π[u] = NIL y la distancia entre el punto fuente s y el vértice u calculado por el algoritmo se almacena en la variable d[u ]. El algoritmo utiliza una cola Q de primero en entrar, primero en salir para almacenar el conjunto de nodos grises. Entre ellos, head[Q] representa el elemento principal de la cola Q, Enqueue(Q, v) representa colocar el elemento v en la cola, Dequeue(Q) representa sacar el elemento de la cola Adj[u] representa el elemento correspondiente; a u en el conjunto de nodos vecinos.
procedimiento BFS(G, S);
comenzar
1 para cada nodo u ∈ V[G]- hacer
. comenzar
2. color[u]←Blanco;
3.d[u]←∞;
4. /p>
fin;
5. color[s]←Gris;
6. d[s]←0;
7.π [s]←NIL;
8. Q←
9 mientras que Q≠φ
comienza
10.para cada uno. nodo v∈ Adj[u] hacer
12. Si color[v]=Blanco entonces
comenzar
13.π [v]←u;
16. poner en cola(Q, v);
fin;
17. ]←Negro;
end;
end;
end;
17. El valor dentro de cada nodo u es d[u], y la cola Q que se muestra en la figura es la cola al comienzo de cada iteración del ciclo while en las líneas 9-18. Debajo de cada nodo en la cola está la distancia entre ese nodo y el nodo de origen.
Figura 1 Ejecución de BFS en un gráfico no dirigido
El proceso de ejecución del proceso BFS es el siguiente: las líneas 1 a 4 configuran cada nodo en blanco y configuran d[u] en infinito. establezca el nodo principal de cada nodo en NIL y establezca el nodo de origen S en gris en la línea 5, lo que significa que el nodo de origen se encontró al comienzo del proceso. La línea 6 inicializa d[s] en 0, la línea 7 establece el padre del nodo de origen en NIL y la línea 8 inicializa la cola 0 para que contenga solo los nodos de origen.
El bucle principal del programa está en las líneas 9-18, y el bucle continúa mientras todavía haya nodos grises en la cola Q, es decir, nodos que se han encontrado pero que aún no se han encontrado por completo. buscado en la lista de adyacencia. La línea 10 identifica el nodo gris al principio de la cola como u. El bucle de las líneas 11 a 16 comprueba cada vértice v en la lista de adyacencia de u. Si v es un nodo blanco, significa que el nodo aún no ha sido descubierto y el algoritmo lo descubrirá ejecutando las líneas 13-16. Primero, se establece en gris, la distancia d[v] se establece en d[u] 1, luego se registra u como padre del nodo y, finalmente, se coloca al final de la cola Q. Cuando se han recuperado todos los nodos en la lista de adyacencia del nodo u, en las líneas 17-18, u sale de la cola y se pone en negro.
Análisis
Antes de probar las diversas propiedades de la búsqueda en amplitud, primero hacemos algo relativamente simple: analizar el algoritmo en el gráfico G = (V, E) del tiempo de ejecución. . Después de la inicialización, no se establecerán más nodos en blanco. Por lo tanto, la prueba en la línea 12 garantiza que cada nodo puede ingresar a la cola como máximo una vez y, por lo tanto, puede saltar de la cola como máximo una vez. Las operaciones de entrada y salida de la cola toman O (1), por lo que el tiempo total de la operación de la cola es O (V). Dado que cada vértice solo buscará su tabla vecina al saltar de la cola, cada vértice tiene la mayor cantidad. tablas vecinas escaneadas una vez. Dado que la suma de las longitudes de todas las listas de adyacencia es Q(E), escanear todas las listas de adyacencia lleva como máximo un tiempo O(E). La operación de inicialización tiene una sobrecarga de O (V), por lo que el tiempo de ejecución general del proceso BFS es O (V E), lo que muestra que el tiempo de ejecución de la búsqueda en amplitud es una función lineal del tamaño de la lista de adyacencia del gráfico. .