TRABAJO PRACTICO EN PYTHON

SIMULACIÓN DE LA EVOLUCIÓN

AUTOR: Adiel Palominos F.

COMPETENCIA: Desarrollo de Software.

ASIGNATURA: Programación II.

Palabras claves: Programación, python, genética, simulación.

Descripción de la problemática.-

   La evolución de las especies presenta diversas formas de preservar sus características genéticas a través del tiempo. Una forma de hacerlo es representar un individuo mediante cadenas de genes. Una cadena de genes está constituida por un conjunto de genes de largo N. La presencia de un gen dentro de la cadena está indicada por un valor 1, en caso contrario un 0. Como se muestra en la figura 1.

La descendencia de generación en generación se logra por medio de combinación de cadenas genéticas (padres).  Dicha mezcla puede realizarse a través de los siguientes operadores genéticos.


Mutación: este operador se basa en el cambio de valor de un gen particular. En particular, se considera la mutación de M genes, los cuales son seleccionados de forma aleatoria. Como se muestra en la figura 2.

Cruzamiento: este operador consiste en el intercambio de material genético entre dos cadenas de genes. Se selecciona un punto de corte C y luego a partir de este se intercambian las colas entre dos cadenas. Como se muestra en la figura 3.

Teniendo en cuenta las descripciones anteriores, una población genética puede ser representada mediante una matriz, donde cada fila representa la información genética de un individuo particular dentro de la población.

La tarea consiste en simular la evolución de una población (cadenas genéticas) en el tiempo bajo las siguiente consideraciones empleando python como lenguaje de programación:

1.   Una población compuesta por 10 con diez individuos donde cada individuo posee 15 genes.
2.   La evolución debe estar entre 10 y 1000 generaciones.

3.   En cada iteración debe considerar que deben modificarse una cantidad aleatoria de individuos.

4.   Considere que los D individuos que deben modificarse en cada iteración, pueden ser conseguidos
aplicado mutación y cruzamiento de acuerdo a una probabilidad de selección, es decir, existe una probabilidad de   mutación y una probabilidad de cruzamiento, donde Así, en cada iteración por medio de una probabilidad (numero   aleatorio) se determina si se aplica mutación o cruzamiento. Por tanto, debe realizarse esto hasta completar el número de individuos D. Para la selección de esta probabilidad, considere lo siguiente:

1) Si probabilidad está en el intervalo [0,Pm]se aplicará un cruzamiento a dos individuo al azar, los cuales serán incorporados a la próxima generación.

2) Si probabilidad está en el intervalo[Pm,1]se aplicará una mutación a un individuo al azar.

5.En cada iteración debe mostrarse por pantalla la población completa, luego de haber realizar las modificaciones pertinentes de acuerdo al valor aleatorio D. Recuerde que la población original nunca varía, por lo que siempre habrán 10 individuos.

6.   Una correcta ejecución del programa es:

1) python ./ nombrealumno.py
2) Deben verificarse que los rangos de valores para cada parámetro sean correctos, en caso contrario, deberá indicarse cuál es el parámetro que se incorrecto y detener la ejecución del programa.

Solución.-

Para dar solución al problema planteado primeramente se analizaron todos los objetivos de la actividad planteada para así dar claridad al objetivo principal.

Creación de la población inicial.

   Determinada en el programa, una población  de 10 individuos, cada individuo fue representado por cadenas de genes.
   Para la creación de la población se creó una matriz con dos ciclos for, uno encargado de las filas y otro de las columnas.

        for i in range(f):
                Poblacion.append([])
                for x in range(c):
                    Poblacion[i].append(random.randint(0,1))

Cadena de genes.

   Una cadena de genes estaba constituida por un conjunto de genes de largo 15. La presencia de un gen dentro de la cadena está indicada por un valor 1, en caso contrario un 0.
   Para determinar los valores de la cadena genética, se utilizó un ‘for’ para poder crear sucesivamente de forma aleatoria cada cadena genética de numero 1 y 0.

Selección de individuo.

   Se programaron varios operadores que necesariamente necesitaban de una o dos cadenas genéticas para realizar su operación. Por ello la selección de una cadena genética es de forma aleatoria.
   Para llevar a cabo la selección aleatoria se utilizó ‘random’ que selecciono la posición de una o más cadenas genéticas según el operador que se usara, para posteriormente esa posición ser leída y obtener una cadena genética, posteriormente sería utilizada y procesada por el operador especifico.

Operador de mutación.

   Se realiza mutación sobre genes a los individuos seleccionados,      el individuo resultante de la mutación vuelve a la población mutado.
   Para llevar a cabo el operador de mutación se tomó el valor ‘M’ aleatoriamente, junto con la selección de genes. Se utilizó un ‘while’ para evitar la repetición de posiciones, la variable ‘M2’ determino la posición del número que sería invertido y así dar término a la mutación.

Operador de cruzamiento.

   Este operador consiste en el intercambio de material genético entre dos cadenas de genes. Se selecciona un punto de corte ‘C’ y luego a partir de este se intercambian las colas entre dos cadenas. Para llevar a cabo el operador de cruzamiento se tomó el punto de corte C aleatoriamente y luego se utilizó un for y 2 variables auxiliares para intercambiar las colas.


Descripción  de funcionalidad final.-

   La solución de este programa está estrictamente definido por números random, estos tenían la misión de dar distintos resultados en cada ejecución o iteración (W), así también los distintos operadores dependían de una probabilidad random la cual generaba distintos resultados en el programa.
   El ingreso estaba dado por paso de argumentos a través de la línea de comandos, esto fue posible con la ‘librería sys’, las condiciones de ingreso de datos fueron, que el usuario debía ingresar un numero entre 10 y 1000 para ‘W’, y así mismo una probabilidad de mutación (Pm) y cruzamiento (Pc) que sumaran 1 si no se respetaba una de estas condiciones el programa terminaría automáticamente.

Resultado final.

Como se puede ver en la imagen el resultado varía de acuerdo a una  probabilidad ‘N1’, este es mi número random, este decide sobre si se mutara o cruzara un cierto individuo aleatorio.

Matriz 1, generación 7

 Matriz 2, generación 8

Como se puede observar en la generación 7 la mutación y el cruzamiento aplicados sobre está, modifican sus individuos (Cruz: 5 y 6, Mut: 7) en los dos casos se puede apreciar el individuo en el que se trabajara y a continuación el resultado (Generación 8) en base a las distintos cambios que estos sufrirán.


Reflexión.-

   Los Algoritmos Genéticos si bien se ven complejo de realizar son una forma muy útil de poder ampliar el conocimiento de programación.

   Tras haber realizado el trabajo se puede destacar que resulta sumamente útil para comprender lo que realmente se puede lograr con un lenguaje de programación. Si bien para mi esta actividad me resulto un gran desafío ya que se tuvo que tener en cuenta varios conceptos aprendidos y complementarlos, sin embargo se logró realizar la actividad tras haber invertido un buen tiempo e investigando. Tras esto logre un conocimiento más amplio ya que se llevó a la práctica casi todo lo aprendido.

   Te invito a que compartas tus comentarios o consultas si requieres más información, o que profundice algún tema.