Descripción general del algoritmo genético
Las técnicas de optimización son las técnicas que se utilizan para descubrir la mejor solución de todas las posibles soluciones disponibles bajo las restricciones presentes. Por lo tanto, el algoritmo genético es uno de esos algoritmos de optimización que se basa en el proceso evolutivo natural de nuestra naturaleza. Aquí se usa la idea de Selección Natural y Herencia Genética. Utiliza la búsqueda aleatoria guiada, a diferencia de otros algoritmos, es decir, para encontrar la solución óptima al comenzar con una función de costo inicial aleatorio y luego buscar solo en el espacio que tuvo el menor costo (en la dirección guiada). Adecuado cuando trabaja con conjuntos de datos enormes y complejos.
¿Qué es un algoritmo genético?
El algoritmo genético se basa en la estructura genética y el comportamiento del cromosoma de la población. Las siguientes cosas son la base de los algoritmos genéticos.
- Cada cromosoma indica una posible solución. Así, la población es una colección de cromosomas.
- Cada individuo en la población se caracteriza por una función de aptitud. Una mejor forma física es la solución.
- De los individuos disponibles en la población, los mejores individuos se utilizan para la reproducción de los descendientes de la próxima generación.
- La descendencia producida tendrá características de ambos padres y es el resultado de una mutación. Una mutación es un pequeño cambio en la estructura del gen.
Fases del Algoritmo Genético
A continuación se muestran las diferentes fases del algoritmo genético:
1. Inicialización de la población (codificación)
- Cada gen representa un parámetro (variables) en la solución. Esta colección de parámetros que forma la solución es el cromosoma. La población es una colección de cromosomas.
- El orden de los genes en el cromosoma es importante.
- La mayoría de las veces los cromosomas se representan en binario como 0 y 1, pero también hay otras codificaciones posibles.
2. Función de aptitud
- De los cromosomas disponibles, tenemos que seleccionar los mejores para la reproducción de las crías, por lo que cada cromosoma tiene un valor de aptitud.
- El puntaje de condición física ayuda a seleccionar las personas que se utilizarán para la reproducción.
3. Selección
- El objetivo principal de esta fase es encontrar la región donde las posibilidades de obtener la mejor solución son mayores.
- La inspiración para esto es de la supervivencia del más apto.
- Debe haber un equilibrio entre la exploración y la explotación del espacio de búsqueda.
- GA intenta mover el genotipo a una mayor aptitud en el espacio de búsqueda.
- Un sesgo de selección de condición física demasiado fuerte puede conducir a soluciones subóptimas.
- Demasiada poca selección de sesgo de aptitud resulta en una búsqueda desenfocada.
- Por lo tanto, se utiliza la selección proporcional de Fitness, que también se conoce como selección de rueda de ruleta, es un operador genético utilizado en algoritmos genéticos para seleccionar soluciones potencialmente útiles para la recombinación.
4. Reproducción
La generación de descendientes ocurre de 2 maneras:
- Transversal
- Mutación
a) Crossover
El crossover es la etapa más vital en el algoritmo genético. Durante el cruce, se selecciona un punto aleatorio mientras se empareja un par de padres para generar descendientes.
Hay 3 tipos principales de crossover.
- Cruce de punto único: un punto en los cromosomas de ambos padres se selecciona al azar y se designa como un 'punto de cruce'. Los bits a la derecha de ese punto se intercambian entre los dos cromosomas principales.
- Cruce de dos puntos : dos puntos de cruce se seleccionan aleatoriamente de los cromosomas originales. Los bits entre los dos puntos se intercambian entre los organismos padres.
- Crossover uniforme: en un crossover uniforme, normalmente, cada bit se elige de cualquiera de los padres con la misma probabilidad.
Los nuevos descendientes se agregan a la población.
b) mutación
En algunos nuevos descendientes formados, algunos de sus genes pueden estar sujetos a una mutación con una baja probabilidad aleatoria. Esto indica que algunos de los bits en el cromosoma de bits se pueden voltear. La mutación se ocupa de la diversidad entre la población y detiene la convergencia prematura.
5. Convergencia (cuándo parar)
Pocas reglas que se siguen que indican cuándo detenerse son las siguientes:
- Cuando no hay mejora en la calidad de la solución después de completar un cierto número de generaciones establecidas de antemano.
- Cuando se alcanza un rango duro y rápido de generaciones y tiempo.
- Hasta que se obtenga una solución aceptable.
Aplicación del algoritmo genético
En esta sección, analizaremos algunas de las áreas en las que se aplica con frecuencia el Algoritmo genético.
1. Viajes y rutas de envío
El problema del vendedor ambulante es una de las principales aplicaciones del algoritmo genético. Por ejemplo, cuando se le pide a un planificador de viajes que planifique un viaje, él tomaría la ayuda de un algoritmo genético que no solo ayuda a reducir el costo general del viaje sino también a reducir el tiempo. GE también se usa para planificar la entrega de productos de un lugar a otro de la mejor manera eficiente.
2. Robótica
El algoritmo genético es ampliamente utilizado en el campo de la robótica. Los robots difieren entre sí por el propósito para el que están diseñados. Por ejemplo, pocos están diseñados para una tarea de cocina, pocos están diseñados para tareas de enseñanza, etc.
- Selección de características importantes en el conjunto de datos dado.
- En el método tradicional, las características importantes en el conjunto de datos se seleccionan utilizando el siguiente método. es decir, si observa la importancia de ese modelo, establecerá un valor de umbral para las características, y si la característica tiene un valor de importancia más que un umbral, se considera.
- Pero aquí usamos un método llamado problema de mochila.
- Comenzaremos nuevamente con la población de un cromosoma, donde cada cromosoma será una cadena binaria. 1 denotará la "inclusión" de la característica en el modelo y 0 denotará la "exclusión" de la característica en el modelo.
- La función de aptitud física aquí será nuestra métrica de precisión de la competencia. Cuanto más preciso sea nuestro conjunto de cromosomas para predecir el valor, más en forma será.
- Hay muchas otras aplicaciones de algoritmos genéticos como análisis de ADN, aplicaciones de programación, diseño de ingeniería.
Conclusión
En el escenario actual, GE se está utilizando en grandes empresas manufactureras como aviones, etc., para optimizar el tiempo y el uso de recursos. Otros científicos están trabajando para encontrar nuevas formas de combinar algoritmos genéticos con otras técnicas de optimización.
Artículos recomendados
Esta es una guía de ¿Qué es el algoritmo genético? Aquí discutimos la introducción, fases y aplicaciones del algoritmo genético. También puede consultar nuestros otros artículos sugeridos:
- Algoritmos de enrutamiento
- Tipos de algoritmos
- Algoritmos de red neuronal
- Algoritmos de minería de datos
- guía de ejemplos de algoritmos de C ++