Categorías
Articulos Desarrollo de software

Introducción a los algoritmos evolutivos: Dale Click

Los algoritmos evolutivos son un enfoque basado en la heurística para resolver problemas que no se pueden resolver fácilmente en el tiempo polinómico, como los problemas clásicos NP-Hard, y cualquier otra cosa que tomaría demasiado tiempo procesar exhaustivamente.

Siguenos en INSTAGRAM La comunidad de los verdaderos programadores.

Cuando se usan solos, generalmente se aplican a problemas combinatorios; sin embargo, los algoritmos genéticos a menudo se usan junto con otros métodos, actuando como una forma rápida de encontrar un punto de partida óptimo para que funcione otro algoritmo.

La premisa de un algoritmo evolutivo (para ser más conocido como EA ) es bastante simple dado que está familiarizado con el proceso de selección natural. Un EA contiene cuatro pasos generales: inicialización, selección, operadores genéticos y terminación.

Estos pasos corresponden, aproximadamente, a una faceta particular de la selección natural, y proporcionan formas fáciles de modularizar las implementaciones de esta categoría de algoritmo.

En pocas palabras, en un EA, los miembros más en forma sobrevivirán y proliferarán, mientras que los miembros no aptos morirán y no contribuirán al acervo genético de otras generaciones, como en la selección natural.

Contexto

En el alcance de este artículo, generalmente definiremos el problema como tal: deseamos encontrar la mejor combinación de elementos que maximice alguna función de aptitud física, y aceptaremos una solución final una vez que hayamos ejecutado el algoritmo para un número máximo de iteraciones, o hemos alcanzado algún umbral de aptitud.

Claramente, este escenario no es la única forma de utilizar un EA, pero abarca muchas aplicaciones comunes en el caso discreto.

Inicialización

Para comenzar nuestro algoritmo, primero debemos crear una población inicial de soluciones. La población contendrá un número arbitrario de posibles soluciones al problema, a menudo llamadas miembros .

A menudo se creará al azar (dentro de las limitaciones del problema) o, si se conoce algún conocimiento previo de la tarea, se centrará en torno a lo que se cree que es ideal.

Es importante que la población abarque una amplia gama de soluciones, porque esencialmente representa un conjunto de genes; ergo, si deseamos explorar muchas posibilidades diferentes a lo largo del algoritmo, debemos aspirar a tener muchos genes diferentes presentes.

Selección

Una vez que se crea una población, los miembros de la población ahora deben ser evaluados de acuerdo con una función de aptitud . Una función de aptitud es una función que toma en cuenta las características de un miembro y genera una representación numérica de cuán viable es una solución.

Crear la función de aptitud física a menudo puede ser muy difícil, y es importante encontrar una buena función que represente con precisión los datos; Es muy específico del problema. Ahora, calculamos la idoneidad de todos los miembros y seleccionamos una parte de los miembros con mayor puntaje.

Múltiples funciones objetivas

Los EA también se pueden extender para usar múltiples funciones de acondicionamiento físico. Esto complica un poco el proceso, porque en lugar de poder identificar un solo punto óptimo, en su lugar terminamos con un conjunto de puntos óptimos cuando utilizamos múltiples funciones de acondicionamiento físico.

El conjunto de soluciones óptimas se llama frontera de Pareto y contiene elementos que son igualmente óptimos en el sentido de que ninguna solución domina a ninguna otra solución en la frontera. Luego se usa un decisor para limitar el conjunto de una solución única, basada en el contexto del problema o alguna otra métrica.

Operadores Genéticos

Este paso realmente incluye dos subpasos: cruce y mutación . Después de seleccionar los miembros principales (generalmente los 2 principales, pero este número puede variar), estos miembros ahora se utilizan para crear la próxima generación en el algoritmo.

Usando las características de los padres seleccionados, se crean nuevos hijos que son una mezcla de las cualidades de los padres. Hacer esto a menudo puede ser difícil dependiendo del tipo de datos, pero típicamente en problemas combinatorios, es posible mezclar combinaciones y generar combinaciones válidas de estas entradas.

Ahora, debemos introducir nuevo material genético.en la generación. Si no hacemos este paso crucial, nos quedaremos atrapados en los extremos locales muy rápidamente y no obtendremos resultados óptimos.

Este paso es la mutación, y lo hacemos, simplemente, cambiando una pequeña porción de los niños de modo que ya no reflejen perfectamente subconjuntos de los genes de los padres.

La mutación generalmente ocurre de manera probabilística, ya que la probabilidad de que un niño reciba una mutación, así como la gravedad de la mutación, se rige por una distribución de probabilidad.

Terminación

Finalmente, el algoritmo debe terminar. Hay dos casos en los que esto suele ocurrir: o el algoritmo ha alcanzado un tiempo de ejecución máximo o el algoritmo ha alcanzado algún umbral de rendimiento . En este punto, se selecciona una solución final y se devuelve.

Entradas relacionadas

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

5 × cinco =