Mutación y cruzamiento genético
Autor : René Curín
Competencia : Desarrollo de software (nivel 1)
Asignatura: Programación 2
Palabras clave: Programación, Funciones, Python, Mutación, Cruzamiento
Palabras clave: Programación, Funciones, Python, Mutación, Cruzamiento
Descripción de la actividad
En esta actividad debimos crear un programa que fuera capaz
de realizar mutaciones y cruzamiento genéticos, esta tarea tiene que
implementar como mínimo el uso de funciones y el manejo de matrices bidimensionales.
Las mutaciones lo los cruzamientos se deben realizar mediante probabilidades es
decir, se debía ingresar como parámetros las probabilidades de cruzamiento y mutación
y de acuerdo a esta probabilidad se debía realizar una de las acciones a
nuestra población que contaba con 10 individuos los que tienen 5 genes cada
uno, esta acción de cruzamiento y mutación se debía realizar una cierta
cantidad de veces entre los valores de 10 a 1000.
Enunciado de la actividad:
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 de W(10 ∩ W ∩ 1000) generaciones de la población.
3. En cada iteración debe considerar que deben modificarse una cantidad aleatoria de individuos
D(1 ∩ D ∩ N -1).
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 Pm y una probabilidad de cruzamiento Pc, donde Pm + Pc = 1 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 W Pm Pc
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 de la actividad
Pseudocodigo
funcion p <- poblacion()
p <-[0] * 10
para i desde 0 hasta 10
p[i] <- [0] * 15;
FinPara
FinFuncion
funcion x <- genes(x)
para f desde 0 hasta 10
para c desde 0 hasta 15
x[f][c] <- random.randint(0,1);
FinPara
FinPara
FinFuncion
funcion x <- buscar(x,d)
bus <- 0
para i desde 0 hasta Longitud(d)
si x = d[i]
bus <- bus + 1
FinSI
FinPara
si bus = 0
retorna x
FinSi
FinFuncion
funcion p <- mutacion(p, D, N)
D.sort()
para K desde 0 hasta Longitu(D)
m <- D[K]
para i desde 0 hasta N
c <- random.randint(0, 14);
si p[m][c] = 0 entonces
p[m][c] <- 1;
sino
p[m][c] <- 0;
Finsi
FinFuncion
funcion p <- cruzamiento(p, D, C)
m1 = D[0]
m2 = D[1]
aux = ""
para c desde 14 hasta C, -1
aux <- p[m1][c]
p[m1][c] <- p[m2][c]
p[m2][c] <- aux
FinFuncion
Proceso sin_titulo
poblacion = genes(poblacion())
W <- int(sys.argv[1])
PM <- float(sys.argv[2])
PC <- float(sys.argv[3])
D <- [] //poblacion
N <- 0 //genes
p <- 0 //probabilidad
si W >= 10 and W <= 1000 entonces
num <- num + 1
sino
escribir "El primer argumento debe ser mayor o igual a 10 o menor igual a 1000"
finsi
si PM <= 1 and PM >=0 entonces
num <- num + 1
sino
escribir "El segundo argumento debe ser mayor igual 0 o menor igual 0"
finsi
si PC >= 0 and PC <= 1 entonces
num <- num + 1
sino
escribir "El tercer argumento debe ser mayor igual 0 o menor igual 0"
finsi
si num = 3
escribir "Poblacion inicial"
para k desde poblacion hasta poblacion
escribir k
escribir "\n"
finpara
si W >= 10 and W <= 1000
p <- random.uniform(0, 1)
si p > PM entonces
escribir "Mutacion"
sino
escribir "Cruzamiento"
mientras W > 0
si p > PM entonces
cont <- 0
mientras cont <= random.randint(1, 10)
r <- random.randint(0, 9)
x <- buscar(r, D)
si x != None
D.append(x)
cont <- cont + 1
finsi
finmientras
N = random.randint(1, 15)
mutacion(poblacion, D, N)
para k desde poblacion hasta poblacion
escribir k
finpara
escribir "\n"
D <- []
sino
cont <- 0
mientras cont <= 1
r <- random.randint(0, 9)
D.append(r)
cont <- cont + 1
finmientras
mientras D[0] = D[1]
del D[1]
r = random.randint(0, 9)
D.append(r)
finmientras
C = random.randint(0, 14)
cruzamiento(poblacion, D, C)
para k desde poblacion hasta poblacion
escribir k
escribir "\n"
D <- []
W <- W - 1
escribir "Poblacion Final"
para k desde poblacion hasta poblacion
escribir k
escribir "\n"
finpara
FinProceso
Código Fuente:
import random
import sys
def poblacion():
p = [0] * 10
for i in range(10):
p[i] = [0] * 15
return p
def genes(x):
for f in range(10):
for c in range(15):
x[f][c] = random.randint(0,1)
return x
def buscar (x,d):
bus = 0
for i in range(len(d)):
if x == d[i]:
bus += 1
if bus == 0:
return x
def mutacion(p, D, N):
D.sort()
for K in range(len(D)):
m = D[K]
for i in range(N):
c = random.randint(0, 14)
if p[m][c] == 0:
p[m][c] = 1
else:
p[m][c] = 0
return p
def cruzamiento(p, D, C):
m1 = D[0]
m2 = D[1]
aux = ""
for c in range(14,C,-1):
aux = p[m1][c]
p[m1][c] = p[m2][c]
p[m2][c] = aux
return p
poblacion = genes(poblacion())
W = int(sys.argv[1])
PM = float(sys.argv[2])
PC = float(sys.argv[3])
D = [] #poblacion
N = 0 #genes
p = 0 #probabilidad
num = 0
if W >= 10 and W <= 1000:
num += 1
else:
print "El primer argumento debe ser mayor o igual a 10 o menor igual a 1000"
if PM <= 1 and PM >=0:
num += 1
else:
print "El segundo argumento debe ser mayor igual 0 o menor igual 0"
if PC >= 0 and PC <= 1:
num += 1
else:
print "El tercer argumento debe ser mayor igual 0 o menor igual 0"
if num == 3:
print "Poblacion inicial"
for k in poblacion:
print k
print "\n"
if W >= 10 and W <= 1000:
p = random.uniform(0, 1)
if p > PM:
print "Mutacion"
else:
print "Cruzamiento"
while W > 0:
if p > PM:
cont = 0
while cont <= random.randint(1, 10): #Ciclo para guardar los individuos
r = random.randint(0, 9)
x = buscar(r, D)
if x != None:
D.append(x)
cont += 1
N = random.randint(1, 15)
mutacion(poblacion, D, N)
for k in poblacion:
print k
print "\n"
D = []
else:
cont = 0
while cont <= 1:
r = random.randint(0, 9)
D.append(r)
cont += 1
while D[0] == D[1]:
del D[1]
r = random.randint(0, 9)
D.append(r)
C = random.randint(0, 14)
cruzamiento(poblacion, D, C)
for k in poblacion:
print k
print "\n"
D = []
W -= 1
print "Poblacion Final"
for k in poblacion:
print k
print "\n"
El cuerpo de este programa es más que nada la búsqueda
y separación de los individuos, ya que para que se ejecutara la mutación se debían
seleccionar sujetos random y una cantidad de genes random para el cruzamiento
se necesitaban solo 2 sujetos random con una cantidad de genes random, por lo
cual la mayor parte del código es pura selección y búsqueda de sujetos random.
Lo curioso de este programa es que no pide los
valores por teclado, si no que se deben ingresar como argumentos, es decir la ejecución
de este programa se hace a través de una terminal de comandos.
Funcionando
De que me sirvió esta actividad
Gracias a esta actividad desarrolle una lógica
nueva y un poco más fluida en donde ya no escribía todo de forma consecutiva,
si no que he utilizado las funciones para realizar un código un poco más
legible y que al final quedara más corto, además adquirió un dominio mayor
sobre mas matrices bidimensionales, que esta tarea requería el uso exclusivo de
estas para su satisfactoria ejecución.
No hay comentarios:
Publicar un comentario