Te recomendamos que pruebes esta resolución en un ambiente controlado antes de enviarlo a producción, un saludo.
Solución:
Bueno, estrictamente hablando, estas dos cosas …recocido simulado (SA) y algoritmos genéticos no son algoritmos ni su propósito es ‘minería de datos’.
Ambos son metaheurísticas– un par de niveles por encima del ‘algoritmo’ en la escala de abstracción. En otras palabras, ambos términos se refieren a metáforas de alto nivel, una tomada de la metalurgia y la otra de la biología evolutiva. En la taxonomía metaheurística, SA es un método de un solo estado y GA es un método de población (en una subclase junto con PSO, ACO, et al, generalmente denominada metaheurísticas de inspiración biológica).
Estas dos metaheurísticas se utilizan para resolver problemas de optimización, particularmente (aunque no exclusivamente) en optimización combinatoria (también conocido como programación de satisfacción de restricciones). La optimización combinatoria se refiere a la optimización mediante la selección de entre un conjunto de elementos discretos; en otras palabras, no hay una función continua para minimizar. El problema de la mochila, el problema del viajante de comercio, el problema de las existencias de corte, son todos problemas de optimización combinatoria.
La conexión con la minería de datos es que el núcleo de muchos (¿la mayoría?) De los algoritmos de aprendizaje automático supervisados (ML) es la solución de un problema de optimización (por ejemplo, las máquinas de vector de soporte y perceptrón multicapa).
Cualquier técnica de solución para resolver problemas de límites, independientemente del algoritmo, consistirá esencialmente en estos pasos (que generalmente se codifican como un solo bloque dentro de un ciclo recursivo):
-
codificar los detalles específicos del dominio en una función de costo (es la minimización paso a paso del valor devuelto por esta función lo que constituye una ‘solución’ al problema c / o);
-
evaluar la función de costo pasando una ‘suposición’ inicial (para comenzar la iteración);
-
en función del valor devuelto por la función de costo, generar una solución candidata posterior (o más de una, según la metaheurística) para la función de costo;
-
evalúe cada solución candidata pasándola en un conjunto de argumentos, a la función de costo;
-
repita los pasos (iii) y (iv) hasta que se satisfaga algún criterio de convergencia o se alcance un número máximo de iteraciones.
Las metaheurísticas se dirigen al paso (iii) anterior; por lo tanto, SA y GA difieren en cómo generan soluciones candidatas para su evaluación por la función de costos. En otras palabras, ese es el lugar para mirar para comprender cómo se diferencian estas dos metaheurísticas.
De manera informal, la esencia de un algoritmo dirigido a la solución de optimización combinatoria es cómo maneja una solución candidata cuyo valor devuelto por la función de costo es peor que la mejor solución candidata actual (la que devuelve el valor más bajo de la función de costo). La forma más sencilla de que un algoritmo de optimización maneje una solución candidata de este tipo es rechazarla por completo; eso es lo que hace el algoritmo de escalada. Pero al hacer esto, la escalada simple siempre perderá una mejor solución separada de la solución actual por una colina. Dicho de otra manera, un algoritmo de optimización sofisticado tiene que incluir una técnica para aceptar (temporalmente) una solución candidata peor que (es decir, cuesta arriba) la mejor solución actual porque una solución aún mejor que la actual podría encontrarse en un camino a través de esa peor solución.
Entonces, ¿cómo generan SA y GA soluciones candidatas?
La esencia de SA generalmente se expresa en términos de la probabilidad de que se acepte una solución candidata de mayor costo (la expresión completa dentro del doble paréntesis es un exponente:
p = e((-highCost - lowCost)/temperature)
O en python:
p = pow(math.e, (-hiCost - loCost) / T)
El término ‘temperatura’ es una variable cuyo valor decae durante el progreso de la optimización y, por lo tanto, la probabilidad de que SA acepte una solución peor disminuye a medida que aumenta el número de iteraciones.
Dicho de otra manera, cuando el algoritmo comienza a iterar, T es muy grande, lo que, como puede ver, hace que el algoritmo se mueva a cada solución candidata recién creada, ya sea mejor o peor que la mejor solución actual, es decir, está haciendo un Caminata aleatoria en el espacio de la solución. A medida que aumenta el número de iteraciones (es decir, a medida que se enfría la temperatura), la búsqueda del algoritmo del espacio de la solución se vuelve menos permisiva, hasta que en T = 0, el comportamiento es idéntico a un algoritmo simple de escalada de colinas (es decir, solo soluciones mejores que las mejores actuales se aceptan soluciones).
Algoritmos genéticos son muy diferentes. Por un lado, y esto es muy importante, no genera una única solución candidata, sino toda una “población de ellos”. Funciona así: GA llama a la función de costo en cada miembro (solución candidata) de la población. Luego los clasifica, de mejor a peor, ordenados por el valor devuelto por la función de costo (‘mejor’ tiene el valor más bajo). A partir de estos valores clasificados (y sus correspondientes soluciones candidatas) se crea la siguiente población. Los nuevos miembros de la población se crean esencialmente de una de tres maneras. El primero generalmente se conoce como ‘elitismo’ y en la práctica generalmente se refiere a simplemente tomar las soluciones candidatas mejor calificadas y pasarlas directamente, sin modificaciones, a la siguiente generación. Las otras dos formas en que los nuevos miembros de la población suelen denominarse “mutación” y “cruzamiento”. La mutación generalmente implica un cambio en un elemento en un vector de solución candidato de la población actual para crear un vector de solución en la nueva población, por ejemplo, [4, 5, 1, 0, 2] => [4, 5, 2, 0, 2]. El resultado de la operación de cruce es como lo que sucedería si los vectores pudieran tener sexo, es decir, un nuevo vector hijo cuyos elementos están compuestos por algunos de cada uno de los dos padres.
Entonces esas son las diferencias algorítmicas entre GA y SA. ¿Qué pasa con las diferencias en el rendimiento?
En la práctica: (mis observaciones se limitan a problemas de optimización combinatoria) GA casi siempre supera a SA (devuelve un valor de retorno ‘mejor’ más bajo de la función de costo, es decir, un valor cercano al mínimo global del espacio de solución), pero a un valor más alto costo de computación. Hasta donde yo sé, los libros de texto y las publicaciones técnicas recitan la misma conclusión sobre la resolución.
pero aquí está la cosa: GA es inherentemente paralelizable; Además, es trivial hacerlo porque los “agentes de búsqueda” individuales que componen cada población no necesitan intercambiar mensajes, es decir, trabajan de forma independiente entre sí. Obviamente eso significa El cálculo de GA se puede distribuir, lo que significa en la práctica, puede obtener resultados mucho mejores (más cercanos al mínimo global) y un mejor rendimiento (velocidad de ejecución).
¿En qué circunstancias SA podría superar a GA? Creo que el escenario general sería que aquellos problemas de optimización tengan un espacio de solución pequeño, de modo que el resultado de SA y GA sea prácticamente el mismo, pero el contexto de ejecución (por ejemplo, cientos de problemas similares se ejecutan en modo por lotes) favorece el algoritmo más rápido (que siempre debe ser SA).
Es realmente difícil comparar los dos ya que se inspiraron en dominios diferentes.
Un algoritmo genético mantiene una población de posibles soluciones y, en cada paso, selecciona pares de posibles soluciones, las combina (cruzamiento) y aplica algunos cambios aleatorios (mutación). El algoritmo se basa en la idea de “supervivencia del más apto” donde el proceso de selección se realiza de acuerdo con un criterio de aptitud (generalmente en problemas de optimización es simplemente el valor de la función objetivo evaluada usando la solución actual). El cruce se realiza con la esperanza de que dos buenas soluciones, cuando se combinen, puedan dar una solución aún mejor.
Por otro lado, Simulated Annealing solo rastrea una solución en el espacio de posibles soluciones, y en cada iteración considera si pasar a una solución vecina o permanecer en la actual de acuerdo con algunas probabilidades (que decae con el tiempo). Esto es diferente de una búsqueda heurística (digamos búsqueda codiciosa) en que no sufre los problemas del óptimo local, ya que puede despegarse de los casos en los que todas las soluciones vecinas son peores que la actual.
Estoy lejos de ser un experto en estos algoritmos, pero intentaré ayudar.
Creo que la mayor diferencia entre los dos es la idea de cruce en GA y, por lo tanto, cualquier ejemplo de una tarea de aprendizaje que se adapte mejor a GA que a SA dependerá de lo que significa el cruce en esa situación y cómo se implementa.
La idea del cruce es que puede combinar de manera significativa dos soluciones para producir una mejor. Creo que esto solo tiene sentido si las soluciones a un problema están estructuradas de alguna manera. Podría imaginarme, por ejemplo, en la clasificación de clases múltiples tomando dos (o muchos) clasificadores que son buenos para clasificar una clase en particular y combinándolos votando para hacer un clasificador mucho mejor. Otro ejemplo podría ser la programación genética, donde la solución se puede expresar como un árbol, pero me resulta difícil encontrar un buen ejemplo en el que se puedan combinar dos programas para crear uno mejor.
Creo que es difícil presentar un caso convincente para uno sobre el otro porque en realidad son algoritmos bastante similares, quizás desarrollados a partir de puntos de partida muy diferentes.
Eres capaz de añadir valor a nuestro contenido informacional colaborando tu experiencia en las referencias.