El estudio de los procesos naturales puede aplicarse al desarrollo de métodos computacionales que sirvan para resolver problemas.
Los métodos inspirados en la naturaleza buscan crear sistemas artificiales
con propiedades de sistemas naturales:
- Inteligencia
- Robustez
- Tolerancia a falla
- Degradación gradual
- Manejo de situaciones imprevistas
Es un método estocástico de búsqueda (diseño, optimización) basado en la mecánica de la selección natural y la idea darwiniana de la superviviencia de acuerdo a la aptitud.
En un algoritmo genético, las posibles soluciones a un problema son codificadas en forma de tiras de caracteres de un alfabeto reducido (generalmente binario) que asemejan los cromosomas de seres vivos.
El algoritmo genético evoluciona una población de estos individuos aplicando operadores genéticos como selección, cruce, y mutación.
A continuación se propone los siguiente para realizar un algoritmo genético
La codificación fue creado con el lenguaje de programación Python, el paradigma utilizado: programación orientada a objetos. Nuestro objeto será el individuo que posee un cromosoma, éste compuesto por una cantidad de genes (binarios), además de poseer una cualidad (variable booleana) indicadora de sí es seleccionado para cruzarse con otro individuo, por defecto es False; recurrimos a métodos de instancia para obtener los genes: getCromo; setSeleccion y getSeleccion, establece seleccionado para cruza y obtiene el valor para saber si fue seleccionado, respectivamente. Métodos estáticos: genX (mutación de genes), elmejor(busca al individuo con mejores cualidades), combinar(toma a dos individuos los cruza y se obtienen los nuevos cromosomas), aptitud(calcula las cualidades de cada individuo de acuerdo a sus genes).
Empezamos creando los cromosomas de la población inicial, y posteriormente los individuos o instancias de la clase. Se decide guardar los cromosomas en una lista, para posterior manejo; indicamos las cualidades para determinar el "valor de cada individuo", por tratarse del Problema de la mochila: los pesos y las ganancias. La ganancia total servirá para determinar la probabilidad de seleccionar un individuo de acuerdo a su valor en ganancia.
Calculamos a ganancia por cromosoma, una vez obtenidas las ganancias buscamos al mejor cromosoma
Procedemos a seleccionar los mejores individuos para posterior cruza, para esto usamos la ganancia total y calculamos la probabilidad de que cierto individuo sea seleccionado arrojando un número pseudoaleatorio del 1 - 100; se agregan a una lista de padres. Debemos procurar que dependiendo de la población un individuo puede seleccionarse n veces, en este caso 2 veces como máximo, ya que de lo contrario el resto no podría cruzarse.
Determinados los padres, creamos la generación siguiente. Como la población inicial fue de 4 individuos, de los cuales el mejor fue seleccionado 2 veces, y otros dos individuos que se cruzaran con el mejor. No olvidemos mutar un gen del cromosoma, con el método correspondiente, cuya probabilidad es relativamente baja.
Una vez generada la generación nueva, calculamos la ganancia que producen los cromosomas nuevos, y nuevamente buscamos al mejor de los individuos resultantes, mostramos al exitoso.
Video que muestra la ejecución del Algoritmo
Como podemos apreciar la programación de algoritmos genéticos resulta muy interesante, sobre todo a sabiendas de las aplicaciones que la vida ofrece a la programación. Este algoritmo no garantiza que el resultado obtenido sea el mejor, esto es porque solamente evalúa los datos que proporcionamos (arroja las mejores soluciones en base a estos solamente), más no todas las posibles combinaciones.









