¿Cuáles son las diferencias entre el recocido simulado y algoritmos genéticos?

Question

¿Cuáles son las diferencias pertinentes, en términos de rendimiento y los casos de uso, entre recocido simulado (con búsqueda de frijol) y los algoritmos genéticos?

Sé que SA puede ser pensado como GA donde el tamaño de la población es único, pero no sé la diferencia clave entre los dos.

Además, yo estoy tratando de pensar en una situación en la que SA superará GA GA o superará SA. Sólo un ejemplo simple que le ayudará a entender será suficiente.

Answer 1

Bueno, estrictamente hablando, estas dos cosas -. recocido simulado (SA) y algoritmos genéticos son ni algoritmos ni es su propósito 'minería de datos'

Ambos son meta-heurística - un par de niveles por encima de 'algoritmo' en la escala de abstracción. En otras palabras, ambos términos se refieren a las metáforas de alto nivel - uno tomado de la metalurgia y la otra de la biología evolutiva. En la taxonomía meta-heurística, SA es un método de un solo estado y GA es un método población (en una sub-clase junto con PSO, ACO, et al, por lo general referido como biológicamente inspirados meta-heurística ).

Estos dos meta-heurística se utilizan para resolver problemas de optimización, especialmente (aunque no exclusivamente) en combinatoria optimización (también conocido como programación de satisfacción de restricciones ). 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 ninguna función continua para reducir al mínimo. El problema de la mochila, problema del vendedor ambulante, cortando problema stock - son todos los problemas de optimización combinatoria

.

La conexión a la minería de datos es que el núcleo de muchos (la mayoría?) Algoritmos de aprendizaje de máquina (ML) supervisado es la solución de un problema de optimización -. (Perceptrón Multicapa y máquinas de soporte vectorial, por ejemplo)

Cualquier técnica solución para resolver los problemas de capitalización, independientemente del algoritmo, consistirá esencialmente de estos pasos (que típicamente se codifican como un solo bloque dentro de un bucle recursivo):

1. codificar los detalles específicos de dominio en una función de coste (es el minimización gradual del valor regresar de esta función que constituye una 'solución' a la c / o problema);

2. evaluar el paso función de coste en una 'conjetura' inicial (para empezar iteración);

3. basado en el valor devuelto por el función de coste, generar una subsiguiente solución candidato (o más de uno, dependiendo de la meta-heurística) al costo función;

4. evaluar cada solución candidato pasándolo en un conjunto de argumentos, a la función de coste;

5. repetir las etapas (iii) y (iv) hasta o bien algún criterio de convergencia es satisfecho o un número máximo de iteraciones se alcanza.

meta-heurística se dirigen a la etapa (iii) anterior; por lo tanto, SA y GA difieren en la forma en que generan soluciones candidatas para la evaluación de la función de coste. En otras palabras, ese es el lugar para buscar a entender cómo difieren estas dos meta-heurísticas.

De manera informal, la esencia de un algoritmo dirigido a la solución de optimización combinatoria es cómo se maneja una solución candidato cuyo valor devuelto por la función de costo es peor que el actual mejor solución candidato (el que devuelve el valor más bajo de la función de coste). La manera más simple de un algoritmo de optimización para manejar una solución de este tipo es candidato a rechazar de plano - que es lo que hace el algoritmo de subida de pendientes. Pero al hacer esto, simple subida de pendientes siempre se perderá una mejor solución separada de la solución actual por una colina. Dicho de otra manera, un algoritmo de optimización sofisticada tiene que incluir una técnica para (temporalmente) la aceptación de una solución candidato peor que (es decir, cuesta arriba de) la mejor solución actual debido a una solución aún mejor que la actual podría estar a lo largo de un camino a través de ese peor solución.

---

Entonces, ¿cómo SA y GA generan soluciones candidatas?

La esencia de la SA se expresa generalmente en términos de la probabilidad de que una solución candidato de mayor costo será aceptada (toda la expresión dentro de la 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 desintegraciones valor durante el progreso de la optimización - y por lo tanto, la probabilidad de que ac SA voluntadCEPT una solución peor disminuye a medida que número de iteración aumenta.

Dicho de otra manera, cuando el algoritmo comienza la iteración, T es muy grande, que como se puede ver, hace que el algoritmo para mover a cada candidato solución de nueva creación, ya sea mejor o peor que la mejor solución actual - es decir, está haciendo un paseo aleatorio en el espacio de soluciones. Como número de iteración se incrementa (es decir, como los Cools temperatura) de búsqueda del algoritmo del espacio de soluciones se vuelve menos permisivo, hasta que a T = 0, el comportamiento es idéntico a un simple algoritmo de escalada (es decir, sólo las soluciones mejor que la corriente mejor solución se aceptan).

Algoritmos Genéticos son muy diferentes. Por un lado - y esto es una gran cosa - no genera una solución única, sino un candidato 'población de ellos' entero. Funciona así: GA llama a la función de coste en cada miembro (solución candidato) de la población. A continuación, los clasifica, de mejor a peor, ordenada por el valor devuelto por la función de costo ( 'mejor' tiene el valor más bajo). A partir de estos valores calificados (y sus correspondientes soluciones del candidato) se crea la siguiente población. Los nuevos miembros de la población se crean esencialmente en una de tres maneras. La primera por lo general se conoce como 'elitismo' y en la práctica por lo general se refiere a limitarse a tomar las soluciones candidatas de más alto rango y pasarlas directamente a través de - sin modificar - a la siguiente generación. Las otras dos formas de que los nuevos miembros de la población se refieren generalmente como 'mutación' y 'crossover'. Mutación por lo general implica un cambio en un elemento de un vector solución candidato de la población actual para crear un vector 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 parecido a lo que sucedería si los vectores podrían tener relaciones sexuales -.. Es decir, un nuevo vector niño cuyos elementos están compuestos por algunos de cada uno de los dos padres

Así que 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 late SA (devuelve un valor de retorno inferior 'mejor' de la función de costo - es decir, un valor cercano al mínimo global del espacio de soluciones), pero a un coste de cálculo superior. Por lo que yo sé, los libros de texto y publicaciones técnicas recitan la misma conclusión sobre la resolución.

pero aquí está la cosa: GA es inherentemente paralelizable; lo que es más, es trivial para hacerlo porque el individuo que comprenden cada población no necesitan intercambiar mensajes "agentes de búsqueda" - es decir, que trabajan de forma independiente el uno del otro. Obviamente que los medios GA cómputo se pueden distribuir , que significa en la práctica, puede obtener resultados mucho mejores (más cerca del mínimo global) y un mejor rendimiento (velocidad de ejecución).

¿En qué circunstancias podría superar SA GA? El escenario general, creo que sería esos problemas de optimización que tienen un pequeño espacio de soluciones para que el resultado de la SA y GA son prácticamente los mismos, sin embargo, el contexto de ejecución (por ejemplo, cientos de problemas similares se ejecutan en modo batch) favorece el algoritmo más rápido (que debe ser siempre SA).

Answer 2

Es muy difícil comparar los dos desde que se inspiran en diferentes dominios ..

un algoritmo genético mantiene una población de posibles soluciones, y en cada paso, selecciona pares de posible solución, ellos (cruzado) combina, y aplica algunos cambios aleatorios (mutación). El algoritmo se basa la idea de la "supervivencia del más apto", donde el proceso de selección se realiza de acuerdo con los criterios de aptitud (por lo general en problemas de optimización es simplemente el valor de la función objetivo evaluada usando la solución actual). El cruce se realiza en la esperanza de que dos buenas soluciones, al combinarse, pueden dar aún mejor solución.

Por otro lado, Simulated Annealing sólo controla una solución en el espacio de posibles soluciones, y en cada iteración considera si para moverse a una solución o estancia vecina en la actual según algunas probabilidades (que decae con el tiempo). Esto es diferente de una búsqueda heurística (dicen búsqueda codiciosa), ya que no sufre de los problemas de óptimo local, ya que puede salir del atasco de casos en los que todas las soluciones vecinas están peor a la actual.

Answer 3

Estoy lejos de ser un experto en estos algoritmos, pero voy a tratar de ayudar a cabo.

Creo que la mayor diferencia entre los dos es la idea de cruce en GA y por lo que cualquier ejemplo de una tarea de aprendizaje que se adapta mejor a GA de SA va a depender de lo que cruce medios en esa situación y cómo se implementa .

La idea de cruce es que se pueden combinar de manera significativa dos soluciones para producir una mejor. Creo que esto sólo tiene sentido si las soluciones a un problema se estructuran de alguna manera. Me podía imaginar, por ejemplo, en la clasificación multiclase toma dos (o muchos) clasificadores que son buenos en la clasificación de una clase particular y la combinación de ellos por medio del voto para hacer una mucho mejor clasificador. Otro ejemplo podría ser Programación Genética, donde la solución se puede expresar como un árbol, pero me resulta difícil llegar a un buen ejemplo donde se puede combinar dos programas para crear una mejor.

Creo que es difícil llegar a un caso convincente para una sobre la otra, ya que en realidad son algoritmos bastante similares, tal vez después de haber sido desarrollados a partir de distintos puntos de partida.