Embed Size (px)
Citation preview
Sistemas Neuro-Difusos Boletín de Prácticas: 1
Tema: Diseño de un sistema de optimización
basado en Algoritmos Genéticos
Geovanny Paredes1, Pedro Urgiles
2
[email protected] [email protected]
I. INTRODUCCIÓN
En el presente boletín de práctica se ha desarrollado un
programa que implementa algoritmos genéticos, para la resolución de un cuadrado mágico de NxN, definiendo
como cuadrado mágico, aquella matriz en la que la suma
de sus filas sea igual a la suma de sus columnas.
II. PASOS A SEGUIR EN LA RESOLUCIÓN
Los pasos para desarrollar el programa son: - Creación de una población inicial
- Evaluación correspondiente a la primera
población
- Selección de una segunda población por torneo. - Generación de una tercera población utilizando
crossover
- Evaluación de la última población generada
Todos estos pasos tienen su propia función en nuestro
programa, los cuales se encuentran anidados en un bucle con la única condición de que si es que en el vector
de genotipos se encuentra con que se llegó a la
máxima evaluación, terminaría con el proceso.
III. FUNCIÓN DE FITNESS
Para la función de fitness, consideramos las
condiciones de evaluación para cada individuo de la
población. En nuestro programa, cada individuo está constituido por valores de 1 hasta NxN y en el que cada
N valores se lo considera como una fila nueva de la
matriz. Luego para evaluar al individuo sumaremos los valores correspondientes a las filas formadas al igual que
el de las columnas que entre éstas se forman.
La condición de suma para filas y columnas se basa en
la siguiente fórmula:
Suma=N(N2+1) / 2
Con todas éstas consideraciones llegamos a la siguiente
función de fitness:
∑2
j=0 (∑2k=0 Matriz [k+jx3]) / 15 + ∑2
j=0 (∑2k=0 Matriz [k x 3]) / 15
La función anterior aplicando al programa obtiene el
conteo de filas y columnas que cumplen con la suma requerida.
IV. ESTRUCTURA DE FENOTIPOS Y GENOTIPOS
La estructura de los fenotipos y genotipos para nuestro
programa es la siguiente:
Individuo =vector[1..9] con valores mezclados
Genotipo=suma de condiciones cumplidas para cada fila o
columna.
Para obtener el genotipo aplicamos la función de fitness
anteriormente indicada en la sección III. Como condición inicial se ha generado 24 individuos a
partir de los cuales se va generando nuevas poblaciones más
fuertes, hasta llegar a la solución deseada.
A continuación se indica la estructura de la población
inicial.
Población inicial
A continuación se muestra una gráfica de las iteraciones
y la evolución de los genotipos para individuo.
En la gráfica anterior se podrá observar la evolución de parte de las 190 iteraciones en las que convergió nuestro
algoritmo, teniendo en cuenta que para cada ejecución
del programa el número de iteraciones varia.
También podemos observar el comportamiento en estas
10 primeras iteraciones, de los valores correspondientes
a la suma de los genotipos y sus promedios para los 24 individuos.
05
101520253035
Itera
cion 1
80
Itera
cion 1
82
Itera
cion 1
84
Itera
cion 1
86
Itera
cion 1
88
Itera
cion 1
90
Este
Grafica de evolución del algoritmo y su aptitud
media
En la gráfica de la evolución hemos considerado los
últimos 10 datos para comprobar la convergencia. Para
fines de lograr un resultado se ha considerado cada 30 iteraciones, volver a generar una nueva población en
caso de no converger a una solución, ya que se ha
comprobado que pasado un cierto número de
repeticiones el resultado no cambia.
V. RESULTADOS FINALES
En la parte final de nuestro programa obtenemos un
vector lineal el cual lo acomodaremos en una matriz
cada N datos según el valor a calcular.
7 4 4
1 9 5
7 2 6
Matriz final
VI. CONCLUSIONES
En el proceso de la programación se probó con varias
poblaciones iniciales. Primero se probó con 6 individuos, los cuales no fueron suficientes para obtener el resultado
óptimo. Luego se incrementó la población al doble,
observándose que se llegaba a un resultado óptimo pero con un número bastante grande de iteraciones. Al final
se duplicó otra vez la población, mejorando el algoritmo.
El proceso carece de mutación por lo que se concluye que se podría mejorar aun más el trabajo si se aplicara
este método.
También pudimos observar que el número de
iteraciones para la ejecución del programa variaba notablemente por lo que al generar los individuos, se
utilizó una pila generada randómicamente la misma que
estaría basada en la probabilidad de generar números.
