Imagina que estás subiendo una colina por la noche. Es completamente negro, por lo que solo puede ver hasta donde la linterna en su mano está brillando (no muy lejos). Has estado caminando por una pendiente por un tiempo, pero luego notas que el suelo comienza a estabilizarse. Después de dar unos pasos más y detenerse en lo que parece una tierra plana, concluye que ha llegado a la cima de la colina.
Hay dos opciones: quedarse en la cima de la colina o seguir caminando.
Eliges este último, y al instante te encuentras cayendo por una pendiente. Una vez que la pendiente toca fondo, decides seguir en la misma dirección. De repente notas que el suelo comienza a inclinarse hacia arriba nuevamente. Sigue caminando, pero esta vez el esfuerzo es más largo (y quizás más empinado) que en la pendiente ascendente anterior. Después de un período de tiempo, llegas a tierra plana de nuevo, y concluyes que has llegado a la cima de otra colina. pero como sabes que la segunda subida fue más larga y empinada que la primera, puedes concluir que has alcanzado una cumbre más alta.
- Algoritmos: ¿Cómo decide si usar BFS o DFS para un problema en particular?
- Tengo conocimiento de estructuras de datos y algoritmos, pero me falta programación competitiva, ¿cómo debo mejorar? ¿Puedo sobrevivir a la competencia de hoy?
- ¿Crees que la programación no es para mí?
- ¿Cuáles son algunos libros que debe leer un experto en algoritmos?
- ¿Qué debe saber todo programador sobre tablas hash y funciones hash?
Podrías haberte quedado donde estabas. Después de todo, estabas en un punto óptimo en este paisaje montañoso, un punto localmente óptimo.
¿Qué pasa si hay algo mejor?
Un algoritmo genético, como cualquier algoritmo metaheurístico, explora las laderas, caminando hacia arriba y hacia abajo. Pero a diferencia del algoritmo tradicional de escalada de montaña con fuerza bruta, el algoritmo genético puede explotar sus hallazgos en las colinas para producir soluciones más evolucionadas y de mayor altitud (cruce) y escalar las colinas de manera más eficiente. Desafortunadamente, hay rendimientos decrecientes en este enfoque (los resultados de cruzar repetidamente las mejores soluciones en una generación se estabilizarán en una solución localmente óptima) si no intenta algo nuevo de manera aleatoria y riesgosa. Es por eso que un algoritmo genético al azar muta mutaciones al azar para producir algo no necesariamente mejor, sino nuevo. La mutación podría proporcionar una solución aún mejor que se puede cruzar con otras soluciones de gran altitud y gran ajuste. Con la analogía de la colina, si el algoritmo permaneció en la primera cumbre de la colina (cruzando solo), nunca habría sufrido la caída (mutado una solución) y, finalmente, descubrió una nueva solución que AÚN es mejor (tal vez no sea óptima a nivel mundial, pero mejor ) en la cima de la colina más alta. Por lo tanto, para responder a su pregunta, se puede implementar un algoritmo genético sin mutación, pero el algoritmo se atascará constantemente en soluciones óptimas localmente porque se adhiere a la recombinación de soluciones muy buenas en lugar de dar un salto de fe y mutar una solución en algo que podría incluso mejor.
En términos más generales, un buen algoritmo genético explota las buenas soluciones que ha encontrado en el espacio de búsqueda con crossover, y explora otras soluciones en el espacio de búsqueda con mutación.
Si aún no lo ha hecho, intente implementar este algoritmo para aproximar una función matemática óptima o para aproximar soluciones al problema del vendedor ambulante, e intente apagar y encender su función de mutación. Encontrará una diferencia notable en los resultados.
