Clasificación de algoritmos de algoritmos inteligentes.
La solución del recocido simulado ya no se basa en el punto inicial como resultado final de la búsqueda local. Introduce una probabilidad de aceptación p. Si la función objetivo f (pn) del nuevo punto (establecida en pn) es mejor, entonces p = 1, lo que significa que se selecciona un nuevo punto, de lo contrario, la probabilidad de aceptación p es el objetivo de; el punto actual f (pc) (sea pc), la función objetivo f (pn) del nuevo punto y otra función del parámetro de control "temperatura" t. En otras palabras, el recocido simulado no busca mejores puntos cada vez como la búsqueda local, y se pueden aceptar puntos con funciones objetivas deficientes. A medida que se ejecuta el algoritmo, la temperatura del sistema t disminuye gradualmente y finalmente termina en una temperatura baja, momento en el que el sistema ya no acepta cambios.
La característica típica del recocido simulado es que no solo acepta la mejora de la función objetivo, sino que también acepta un límite de decadencia. Cuando t es mayor, acepta una atenuación mayor, cuando t disminuye gradualmente, acepta una atenuación menor y cuando t es 0, ya no acepta atenuación. Esta característica significa que el recocido simulado es lo opuesto a la búsqueda local, que puede evitar mínimos locales y mantener la universalidad y simplicidad de la búsqueda local.
Físicamente, si primero se calientan las moléculas para que colisionen entre sí, la energía interna aumentará, y luego se baja la temperatura, de modo que las moléculas finales estarán más ordenadas y la energía interna será menor. que antes del calentamiento. Al igual que ese conejo, hizo la vista gorda ante los picos cercanos cuando estaba borracho. Saltó en un gran círculo aturdido, pero era más probable que encontrara el Monte Everest.
Vale la pena señalar que cuando t es 0, el recocido simulado se convierte en un caso especial de búsqueda local.
Expresión de pseudocódigo de recocido simulado;
Programa de recocido simulado
Inicio
t:= 0;
Temperatura de inicialización T
Seleccionar aleatoriamente la cadena actual VC;
Evaluar VC;
Repetir
Repetir
Seleccione una nueva cadena VN en la vecindad de vc (1)
if f(VC)<VND
Entonces VC:= VN;
if f(VC)<VND
Entonces VC:= VN;
p>de lo contrario, si es aleatorio [0, 1]<exp ((f (vn)-f (vc ))/T) (2)
Entonces VC:= VN;
Hasta (condición de terminación)(3)
T:=g(T, T); (4)
t:= t+1;
Hasta (criterio de parada) (5)
Fin;
En el programa anterior, el enfoque es (1) función de generación de nuevo estado, (2) función de aceptación de nuevo estado, (3) criterio de estabilidad de muestreo, (4) función de recocido, (5) criterio de fin de recocido (denominado tres funciones y dos criterios), son los principales vínculos que afectan directamente a los resultados de optimización. Aunque los resultados experimentales muestran que el valor inicial no tiene efecto sobre el resultado final, cuanto mayor sea la temperatura inicial, mayor será la probabilidad de obtener una solución de alta calidad. Intente elegir una temperatura inicial más alta.
Estrategia de selección para los enlaces clave anteriores:
(1) Función de generación de estado: la solución candidata está determinada por la función de vecindad de la solución actual y se puede generar mediante operaciones como intercambio, inserción y orden inverso. Luego seleccione una nueva solución de acuerdo con el método de distribución de probabilidad. La probabilidad puede ser distribución uniforme, distribución normal, distribución gaussiana, distribución de Cauchy, etc.
(2) Función de aceptación del estado: este vínculo es el más crítico, pero los experimentos muestran que el tipo de función de aceptación tiene poco impacto en el resultado final. Por lo tanto, generalmente elija min [1, exp ((f (VN)-f (VC))/t)].
(3) Criterios de estabilidad del muestreo: los más utilizados incluyen: probar si el valor promedio de la función objetivo es estable; el valor objetivo de varios pasos consecutivos cambia muy poco;
(4) Función de enfriamiento: si se requiere que la temperatura baje a un cierto ritmo, se puede usar el algoritmo SA, pero el enfriamiento es muy lento en SA rápido, generalmente se usa; Actualmente se utiliza comúnmente un valor que cambia constantemente.
(5) Criterios de terminación de recocido: generalmente incluyen: establecer la temperatura de terminación; establecer el número de iteraciones; el valor óptimo buscado permanece sin cambios durante muchas veces consecutivas; verificar si la entropía del sistema es estable;
Para garantizar una mejor solución, el algoritmo a menudo utiliza enfriamiento lento, muestreo múltiple y establece la "temperatura de terminación" más baja, lo que resulta en un tiempo de ejecución más prolongado del algoritmo, que también es el mayor desventaja del recocido simulado. ¿Los borrachos no son buenos para nada y mucho menos para un conejo? "Selección natural, supervivencia del más fuerte" es la idea básica de la teoría de la evolución. Los algoritmos genéticos simulan lo que la naturaleza quiere hacer. Los algoritmos genéticos pueden usarse bien en problemas de optimización si se los considera como una simulación altamente idealizada de procesos naturales, pueden mostrar su elegancia, aunque la competencia por la supervivencia es cruel.
El algoritmo genético se dirige a todos los individuos de una población y utiliza tecnología de aleatorización para guiar la búsqueda eficiente de un espacio de parámetros de codificación. Entre ellos, la selección, el cruce y la mutación constituyen las operaciones genéticas del algoritmo genético, la configuración de la población inicial, el diseño de la función de aptitud, el diseño de la operación genética y la configuración de los parámetros de control constituyen el contenido central del algoritmo genético. Como nuevo algoritmo de búsqueda de optimización global, el algoritmo genético se ha utilizado ampliamente en diversos campos y ha logrado buenos resultados debido a sus características notables como simplicidad, universalidad, robustez, adecuado para procesamiento paralelo, alta eficiencia y practicidad, etc., y tiene Conviértete gradualmente en uno importante de los algoritmos inteligentes.
Pseudocódigo del algoritmo genético;
Algoritmo genético procesal
Iniciar
Inicializar un grupo y evaluar el valor de aptitud (1)
Aunque no converge (2)
Inicio
Seleccione (3)
if random[0, 1]& lt; Entonces vamos a PC
Transfronterizo (4)
Si es aleatorio (0, 1)<Buenas tardes
Mutación (5)< / p>
Fin;
Fin
Hay cinco enlaces importantes en el programa anterior:
(1) Codificación y generación de población inicial: GA en Antes de la búsqueda, los datos de solución del espacio de solución se representan como datos de estructura de cadena de genotipo del espacio genético. Diferentes combinaciones de estos datos de estructura de cadena constituyen puntos diferentes. Luego, se generan aleatoriamente n datos iniciales de estructura de cadena, cada dato de estructura de cadena se denomina individuo y n individuos forman un grupo. GA comienza la iteración con estos N datos de estructura de cadenas como punto inicial.
Por ejemplo, en el problema del viajante, se puede codificar el camino tomado por el hombre de negocios o se puede codificar toda la matriz gráfica. El método de codificación depende de cómo se describe el problema. El grupo inicial también debe elegirse adecuadamente. Si la selección es demasiado pequeña, la ventaja híbrida no será obvia y el rendimiento del algoritmo será pobre (la rata dominante superará al tigre). Si la selección de población es demasiado grande, la cantidad de cálculo será demasiado grande.
(2) Verifique si se cumple el criterio de convergencia del algoritmo y controle si el algoritmo se completa. Esto se puede lograr juzgando la idoneidad de la solución óptima o estableciendo el número de iteraciones.
(3) Evaluación, detección y selección de valores de aptitud: La función de aptitud representa las ventajas y desventajas de un individuo o un programa. La aptitud también debe evaluarse al comienzo del programa para facilitar la comparación con. los posteriores. Para diferentes problemas, la definición de función de aptitud es diferente. Elija según su idoneidad. El propósito de la selección es seleccionar individuos destacados de la población actual para que tengan la oportunidad de engendrar a la próxima generación. Los algoritmos genéticos incorporan esta idea a través del proceso de selección. El principio de selección es que los individuos con gran adaptabilidad tienen una alta probabilidad de contribuir con uno o más descendientes a la siguiente generación. La selección implementa el principio de Darwin de la supervivencia del más apto.
(4) Hibridación: La hibridación se realiza en función de la probabilidad de hibridación (pc). La operación cruzada es la operación genética más importante en el algoritmo genético. Mediante el cruzamiento se puede producir una nueva generación de individuos que combine las características de ambos padres. La hibridación encarna la idea de intercambio de información.
Se puede seleccionar un punto para hibridar con la cadena de cromosomas mediante intercambio, inserción, secuencia inversa, etc. , también puedes seleccionar aleatoriamente varios puntos para la hibridación. Si la probabilidad de hibridación es demasiado alta, la población se actualizará rápidamente, pero los individuos altamente adaptables se verán fácilmente abrumados. Si la probabilidad es pequeña, la búsqueda se estancará.
(5) Mutación: Mutación basada en la probabilidad de mutación (pm). La mutación primero selecciona aleatoriamente a un individuo de la población y cambia aleatoriamente el valor de una determinada cadena en los datos de la estructura de cadenas para el individuo seleccionado con una cierta probabilidad. Como en biología, la probabilidad de mutaciones en GA es muy baja. La mutación brinda oportunidades para la creación de nuevos individuos.
La mutación previene la parada evolutiva provocada por defectos en genes eficientes. Una probabilidad de mutación baja permite que los genes cambien continuamente y, si es demasiado grande, caerá en una búsqueda aleatoria.
Piénselo, cada generación en el mundo biológico está muy lejos de la generación anterior. Qué situación tan terrible sería.
Así como la variación en la naturaleza se aplica a cualquier especie, los algoritmos genéticos que codifican variables no consideran si la función en sí es diferenciable o continua, por lo que tiene una gran aplicabilidad. Además, operar sobre una población desde el principio implica paralelismo y facilita encontrar la "solución óptima global". Para encontrar la "solución óptima global", no debemos limitarnos a un área específica. La desventaja de la búsqueda local es que busca en un área local y su vecindario con demasiada avidez, lo que resulta en hacer la vista gorda y no ver a Taishan. La búsqueda tabú consiste en evitar conscientemente parte de la solución óptima local encontrada (pero no completamente aislada), obteniendo así más intervalos de búsqueda. Cuando los conejos encuentren a Tarzán, uno de ellos se quedará aquí y los demás irán a buscar a otra parte. De esta manera, después de hacer un gran círculo y comparar los distintos picos encontrados, destacó el Monte Everest.
Cuando el conejo lo busca de nuevo, generalmente evitará a Taishan conscientemente, porque sabe que hay un conejo observando aquí antes. Esto es lo que significa "lista tabú" en la búsqueda tabú. Los conejos que han pasado tiempo en Tarzán generalmente no viven allí. Volverá a las tropas buscando el pico más alto después de un cierto período de tiempo, porque ya hay muchas novedades en este momento. Después de todo, es necesario reconsiderar la altura del monte Tai. Este tiempo de retorno se denomina "longitud tabú" en la búsqueda tabú. Si durante la búsqueda, los conejos que quedaron en el Monte Tai no han regresado, pero los lugares que encontraron están en áreas bajas como la llanura del norte de China, los conejos tendrán que considerar elegir el Monte Tai nuevamente. En otras palabras, cuando la superioridad de un lugar con conejos es demasiado prominente y excede el estado de "mejor estar lejos", pueden tomar este lugar en consideración independientemente de si los conejos se quedan atrás. Este es el llamado "estándar de amnistía". Estos tres conceptos son la mayor diferencia entre la búsqueda tabú y los criterios de búsqueda generales, y la optimización del algoritmo también es la clave aquí.
Expresión de pseudocódigo:
Búsqueda tabú del programa;
Iniciar
Inicializa aleatoriamente una cadena vc y borra la lista tabú;
cur:= VC;
Repetir
Seleccione una nueva cadena VN en el vecindario de vc;
Si va & gtbest_to_far entonces {va es una cadena en la lista tabú}
Inicio
cur:= va;
Dejemos que va reemplace la cadena más antigua en la lista tabú;
mejor _ a _ lejos:= va;
Fin más
Inicio
cur:= VN;
Deje que vn reemplace la cadena más antigua en la lista tabú;
Fin;
Hasta (condición de terminación);
Fin;
Hay varias claves puntos en el programa anterior:
(1) objeto tabú: puede elegir el valor actual (cur) como objeto tabú y ponerlo en la lista Tabú, o puede poner todo en la lista Tabú Activado el mismo "contorno" que el valor natural.
(2) Para reducir la cantidad de cálculo, el conjunto de longitud tabú y tabla tabú no debe ser demasiado grande. Sin embargo, si la longitud tabú es demasiado pequeña, es fácil realizar un bucle en la búsqueda. Y si la lista tabú es demasiado pequeña, es fácil caer en la "solución óptima local".
(3) La operación de best_to_far en el segmento de programa anterior se asigna directamente a la "solución candidata desbloqueada" óptima, pero a veces habrá un estado de "punto muerto" en el que todas las soluciones candidatas se desbloquean si no son mayores que best_to_far. En este momento, es necesario eliminar la mejor solución candidata y continuar.
(4) Criterio de terminación: similar a los algoritmos genéticos y de recocido simulado, los más utilizados son: dada una cantidad de iteraciones, cuando la distancia entre el conjunto y la solución óptima estimada es menor que un cierto rango; terminar la búsqueda cuando la distancia La búsqueda termina cuando la distancia a la solución óptima permanece sin cambios durante varios pasos consecutivos;
La búsqueda tabú es una simulación del proceso de pensamiento humano en sí. Puede salirse de la búsqueda local tabú (o memorizando) algunas soluciones óptimas locales y aceptando algunas soluciones diferenciales. Red neuronal artificial
Como su nombre indica, la red neuronal es una simulación del cerebro humano. Su estructura neuronal, su composición y su modo de acción imitan al cerebro humano, pero es sólo una imitación aproximada, lejos de ser perfecta. A diferencia de las máquinas de von Neumann, las redes neuronales no son numéricas, son imprecisas, muy paralelas y tienen capacidades de autoaprendizaje.
En las ciencias de la vida, las células nerviosas generalmente se denominan neuronas, que son las unidades más básicas de toda la estructura neuronal. Cada célula nerviosa es como un brazo. La parte en forma de palma contiene el núcleo celular, llamado cuerpo celular. Las dendritas, como los dedos, son la vía de entrada de información. Los axones del brazo son la vía de salida de información. están intrincadamente conectados entre sí y transmiten señales, y las señales transmitidas pueden provocar cambios en el potencial de las neuronas. Una vez que el potencial supera un cierto valor, la neurona se excitará y enviará una señal eléctrica a través del axón.
Si queremos utilizar computadoras para simular nervios biológicos, necesitamos una red neuronal artificial, que tiene tres elementos: (1) definir formalmente las neuronas artificiales (2) proporcionar el método de conexión de las neuronas artificiales, o se da la estructura de la red; (3) se da la definición de intensidad de la señal entre neuronas artificiales.
El primer modelo de red neuronal artificial de la historia se llama modelo M-P, que es muy simple:
Entre ellos, representa el estado de la neurona I en el tiempo t, 1 representa la excitada estado, y 0 representa el estado inhibidor; es la fuerza de conexión entre las neuronas I y J representa el umbral de la neurona I, por encima del cual la neurona puede activarse.
Este modelo es el modelo de neurona más simple. Pero ya es increíblemente poderoso: McCulloch y Pitts, los inventores del modelo, han demostrado que puede realizar cualquier trabajo que las computadoras digitales actuales, independientemente de la velocidad y complejidad de la implementación.
El modelo M-P anterior es solo una capa de red. Si consideramos la división de planos, la red M-P solo puede dividir un plano en semiplanos, pero no puede seleccionar partes específicas. La solución es una "red directa multicapa".
Para que este tipo de red tenga ponderaciones adecuadas, es necesario darle algunos incentivos para que pueda aprender y adaptarse por sí sola. Un método se llama "Retropropagación (BP)". La idea básica es examinar la diferencia entre la solución de salida final y la solución ideal, ajustar los pesos y deducir a la inversa este ajuste desde la capa de salida, a través de la capa intermedia, hasta la capa de entrada.
Se puede observar que las redes neuronales logran el propósito de resolver problemas a través del aprendizaje. El aprendizaje no cambia la estructura y el modo de funcionamiento de una sola neurona, y las características de una sola neurona no están directamente relacionadas con el problema a resolver. La función del aprendizaje aquí es cambiar la intensidad de las acciones de las neuronas en función de las relaciones excitadoras e inhibidoras entre ellas. La información de cualquier muestra de la muestra de aprendizaje se incluye en cada peso de la red.
En el algoritmo BP, hay un proceso de examinar la diferencia entre la solución de salida y la solución ideal. Suponiendo que la diferencia es W, el propósito de ajustar el peso es minimizar W, lo que incluye el problema del "mínimo" mencionado anteriormente. Los algoritmos generales de BP utilizan búsqueda local, como el método de descenso más pronunciado, el método de Newton, etc. Por supuesto, si desea obtener la solución óptima global, puede utilizar algoritmos genéticos y de recocido simulados. Cuando la red directa utiliza el algoritmo de recocido simulado como método de aprendizaje, generalmente se denomina "red de Boltzmann" y es una red neuronal estocástica.
En el proceso de aprendizaje del algoritmo BP, es necesario que existan algunos valores determinados como resultado ideal, al igual que los estudiantes de secundaria supervisados por sus profesores cuando están aprendiendo. ¿Cómo pueden aprender las redes neuronales artificiales sin supervisión?
Así como no existe un macrocontrol y el libre mercado introduce la competencia, existe un método de aprendizaje llamado "aprendizaje de competencia no supervisada". Varias neuronas ingresan a la neurona que compito entre sí. Después de la competencia, solo una neurona es 1 y las demás son 0. Para una neurona que falla, si ajusta su movimiento en una dirección que favorezca la competencia, puede terminar ganando la competencia.
También existen redes de retroalimentación, como la red de Hopfield. La dirección de transmisión de la señal de las neuronas es bidireccional y se introduce una función energética. A través de la interacción continua entre neuronas, el valor de la función energética continúa disminuyendo y finalmente se puede dar una solución con menor energía. La idea es similar al recocido simulado.
Cuando las redes neuronales artificiales se aplican a los algoritmos, su precisión y velocidad tienen poco que ver con la implementación del software. La clave es su propio aprendizaje continuo. Esta idea es muy diferente del modelo de von Neumann. El algoritmo de optimización del enjambre de partículas es una tecnología informática evolutiva propuesta por el Dr. Eberhart y el Dr. Kennedy en 1995. Se originó a partir del estudio del comportamiento depredador de las aves. El algoritmo se inspiró inicialmente en los patrones de actividad de grupos de aves y luego utilizó inteligencia de enjambre para construir un modelo simplificado.
Sobre la base de observar el comportamiento de grupos de animales, el algoritmo de enjambre de partículas utiliza el * * * disfrute de la información por parte de los individuos del grupo para hacer que el movimiento de todo el grupo evolucione del desorden al orden en el espacio de resolución de problemas, obteniendo así el solución óptima.
Al igual que el algoritmo genético, el algoritmo de enjambre de partículas es un algoritmo de optimización iterativo. El sistema se inicializa como un conjunto de soluciones aleatorias y se busca el valor óptimo de forma iterativa. Sin embargo, no tiene el cruce y la mutación utilizados por los algoritmos genéticos, sino que las partículas siguen la partícula óptima en el espacio de solución para buscar. En comparación con el algoritmo genético, el algoritmo de enjambre de partículas es simple y fácil de implementar, y no hay muchos parámetros que deban ajustarse. En la actualidad, se ha utilizado ampliamente en campos de aplicación como la optimización de funciones de algoritmos genéticos, el entrenamiento de redes neuronales y el control de sistemas difusos.
El algoritmo de enjambre de partículas simula el comportamiento depredador de las aves. Imagine una escena en la que una bandada de pájaros busca comida al azar. En esta zona sólo existe un tipo de comida. Todos los pájaros no saben dónde está la comida. Pero saben lo lejos que están de su comida. Entonces, ¿cuáles son las mejores estrategias para encontrar comida? El método más simple y efectivo es buscar el área alrededor del ave que actualmente está más cerca de la comida.
La optimización del enjambre de partículas se inspira en este modelo y lo utiliza para resolver problemas de optimización. En PSO, la solución a cada problema de optimización es un pájaro en el espacio de búsqueda. Las llamamos partículas. Todas las partículas tienen un valor de aptitud determinado por la función de optimización, y cada partícula también tiene una velocidad que determina la dirección y la distancia de su vuelo. Luego, las partículas buscan en el espacio de solución siguiendo la partícula óptima actual.
PSO se inicializa a un conjunto de partículas aleatorias (soluciones aleatorias). Luego encuentre la solución óptima mediante iteración. En cada iteración, la partícula se actualiza siguiendo dos extremos. La primera es la solución óptima encontrada por la propia partícula, que se denomina valor extremo individual pBest. El otro valor extremo es la solución óptima que se encuentra actualmente a nivel mundial, y este valor extremo es el valor extremo global gBest. Además, también es posible considerar solo una parte de toda la población como vecina de la partícula, entonces el valor extremo entre todos los vecinos es el valor extremo local. El recocido simulado, los algoritmos genéticos, la búsqueda tabú y las redes neuronales tienen ventajas únicas para resolver soluciones óptimas globales. Todos tienen una característica común: todos simulan procesos naturales. La idea del recocido simulado tiene su origen en el proceso de recocido de la materia sólida en física. Los algoritmos genéticos se basan en la idea evolutiva de la supervivencia del más apto en la naturaleza. La búsqueda tabú utiliza el proceso de la memoria para simular el proceso intelectual humano y la red neuronal simula directamente el cerebro humano.
También están estrechamente relacionados, como el recocido simulado y los algoritmos genéticos, que proporcionan ideas para mejorar los algoritmos de aprendizaje para redes neuronales. Combínelos orgánicamente y aprenda de las fortalezas de cada uno para lograr un mejor desempeño.
Estos algoritmos inteligentes se diferencian de los programas que generalmente calculan con precisión según las máquinas de Turing, especialmente las redes neuronales artificiales. Son una nueva interpretación de los modelos informáticos que van más allá de los límites de las máquinas de von Neumann. Los ordenadores diseñados según esta idea tienen amplias perspectivas de desarrollo.