Inteligencia Artificial

Sistemas Neuro-Difusos

Boletín de Prácticas: 1

Tema: Diseño de un sistema de optimización

basado en Algoritmos Genéticos

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:

Σ2j=0 (Σ2k=0 Matriz [k+jx3]) / 15 + Σ2j=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.

0

5

10

15

20

25

30

35

Iteracion 180

Iteracion 182

Iteracion 184

Iteracion 186

Iteracion 188

Iteracion 190

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.

...