algoritmos genéticos

INTELIGENCIA ARTIFICIAL

Trabajo Práctico nº 4

Profesores:

� Ing. Mario Figueroa � Ing. Pablo Rovarini

Alumnos:

� José Daniel Muccela

Comisión: 5 k 2

Año 2008

Facultad Regional Tucumán

Universidad Tecnológica Nacional

Algoritmos Genéticos Optimización

Mezcla Motores Nafteros

Inteligencia Artificial 2008 - TPNº4 - Alg. Genéticos - Muccela José Daniel

UTN FRT 1

TP Nº4 – Algoritmos Genéticos Problema: Optimización Mezcla para Motores Nafter os

Desarrollo

En la resolución del presente problema se tratará de encontrar la mejor

solución, esto es, encontrar los mejores valores para las variables que intervienen en el problema: Aire, Combustible y NOS. Estos valores representarán las partes de los componentes en la mezcla que se usará en el motor para obtener una mayor potencia.

Se necesitan 3 variables que son los parámetros a considerar para el

desarrollo del modelo. Estas variables son:

� Aire � Combustible � NOS

Para resolverlo utilizaremos el software comercial Matlab versión 7. Para ello seguimos los siguientes pasos: • Abrimos la herramienta Matlab. • Creamos un nuevo archivo *.mat en el directorio que deseemos. En nuestro caso los archivos se crearon en el Current Directory (‘C:\MATLAB7\work’). • Se abre la ventana de programación de Matlab. En ella escribimos en la primera línea la definición de la función fitness, que vamos a maximizar y en una segunda línea la función misma. -Línea 1 function F = tp4Mezcla (X) -Línea 2 F = ((0.8*X(1))/(0.1*X(2))) + (0.1 * ((0.36*X(3))/(0.64*X(3))))

AIRE

Biela

Válvula

Bujía

Esquema de Motor a

combustión


UTN FRT 2

Para la función fitness consideramos que en la mezcla interviene por un lado el aire con un porcentaje del 80 % de la mezcla y el combustible con un porcentaje del 10 % (variables X1 y X2, respectivamente) y por otro lado interviene el NOS, otorgando a la mezcla inicial su parte de aire (oxígeno) y nitrógeno (variable X3) las cuales están representadas por su respectivo porcentaje en que intervienen en la mezcla. O sea le corresponde el 10 % restante de la mezcla. De ese 10 %, 0.36 corresponden al aporte de aire que tiene el NOS; el 0.64 que queda es Nitrógeno, que se agrega al Combustible.

El cociente indica la relación entre el aire y el combustible de la mezcla. Procedemos a guardar el archivo; por defecto se guarda con el mismo

nombre especificado en la definición de la función. En nuestro caso mantuvimos el nombre por defecto de la función: tp4Mezcla.mat.

• Ahora nos dirigimos a la ventana principal del Matlab y en la ventana de comandos escribimos gatool para abrir la caja de herramientas para resolver problemas de Algoritmos Genéticos que ofrece el programa.

>> gatool • Se nos abre una ventana que contiene múltiples opciones para la configuración y la inicialización de nuestro problema:

En ella comenzaremos a escribir los parámetros que usará Matlab para resolver el problema.


UTN FRT 3

En el primer cuadro de texto escribimos la directiva @nombredefunción. Esto significa que llama a la función que previamente creamos en el archivo *.mat (tp4Mezcla). En el siguiente cuadro especificamos el número de variables de la función de aptitud (fitness) del problema que como dijimos son X1, X2 y X3. (Aire, Combustible y NOS, respectivamente). En el grupo Plots, se encuentran las opciones de gráfico, esto es, cuáles serán las salidas que el sistema representará gráficamente para el algoritmo genético. Las más importante son Best fitness, Best individual, Selection.

Ahora configuramos las opciones para nuestro problema. En la sección Population especificamos nuestro tipo de población que

será un Double Vector (número decimal) ya que usaremos cantidades reales.

Especificamos cuantos individuos hay en cada generación en Population

size. Indicamos la función de creación: La creación predefinida function

Uniform crea una población inicial al azar con una distribución uniforme. Dejamos en blanco Inicial Population para que la función predefinida la cree.

Dejamos en blanco Inicial scores para que el algoritmo compute los puntajes de acuerdo a la función de aptitud (fitness).

A continuación vamos a especificar cuales serán las opciones para las funciones de Selección, Mutación, Reproducción, etc.

Para Fitness scaling nos basamos en posición de los individuos según el ranking (Rank) que obtengan por la adecuación a la función fitness.


UTN FRT 4

Para la selección elegimos el método de la ruleta, donde a cada

individuo se le asigna una porción de la torta. En este caso, a mayor tamaño de la porción mayor será su probabilidad de salir seleccionado.

Para la reproducción se considerará el método elitista, donde irán

conservándose los mejores a medida que surjan las nuevas generaciones. El porcentaje de cruza lo dejamos en 80 %. El restante es para la

mutación.

Para la mutación elegimos hacerlo de manera uniforme con una taza de

mutación de 1 %. A veces no se llega a realizar la mutación. Caso contrario sólo sería con una frecuencia del 1 %. La mutación permite modificar un gen del genoma de un individuo cualquiera con el fin de mejorarlo.

Por ej: Cadena de bits: representan un individuo.

0 1 1 0 1 1 1 0 0 1

Queremos mutar un gen del genoma, supongamos el tercero. De esta manera el genoma quedaría:

0 1 0 0 1 1 1 0 0 1

Para la opción de Cruza (crossover) elegimos Two point. Two point

selecciona dos enteros al azar m y n entre 1 y el Número de variables. El algoritmo selecciona genes numerados menores o iguales a m del primer padre, selecciona genes numerados m+1 a n del segundo padre, y selecciona


UTN FRT 5

genes numerados mayor que n del primer padre. El algoritmo procede a encadenar estos genes para formar un solo gen. Por ejemplo,

p1 = [a b c d e f g h] p2 = [1 2 3 4 5 6 7 8] Punto de cruza (al azar) = 3,6 El resultado es el siguiente: p3 = [a b c 4 5 6 g h]

Por lo tanto para nuestro caso seleccionamos dos puntos de cruza. Para el criterio de parada del algoritmo elegimos 100 generaciones. El resto de las opciones del criterio podemos dejarlas como están. Esto

producirá que en el caso de que no haya mejores soluciones que las que encontró en el proceso de cómputo del algoritmo parará antes de que se llegue a las 100 generaciones. De todas maneras si queremos probar las 100 tenemos que especificar Inf en Time limit, Fitness limit, Stall generations y Stall time limit.

Las configuraciones especificadas hasta aquí son suficientes para correr

el problema y analizar los resultados. Para ello nos dirigimos a la derecha de la caja de herramientas

En esta sección se visualizará el resultado del cómputo y el motivo porque se detuvo el algoritmo

Comenzar a correr el problema


UTN FRT 6

En el momento que se está ejecutando vemos que se abre una ventana mostrando los gráficos que se seleccionamos en la sección Plots. En el se puede ver como los gráficos van modificándose a medida que se realiza el cómputo. Al final del mismo, el resultado de la función fitness es mostrado en la imagen anterior. El mejor resultado encontrado para las variables se observará en la siguiente imagen:

Para conservar la configuración que establecimos podemos guardarla de

la siguiente manera:

Vamos al botón: Esto nos abre una pequeña ventana que nos pregunta qué es lo que

queremos exportar: Podemos seleccionar todas las opciones. Cabe mencionar que antes de

la ejecución del problema las opciones 2 y 4 están deshabilitadas porque el algoritmo todavía no computó el mismo.

Esto permitirá guardar las configuraciones, el problema y los resultados para posteriores ejecuciones y análisis.

problema

configuración

problema

configuración


UTN FRT 7

Resultados:

Puntos finales encontrados. Corresponden a los valores que toman las

variables del problema. Gráficos generados: • El primero de ellos muestra el mejor valor para la función fitness. • El segundo hace referencia al mejor individuo actual. • El tercero muestra la expectativa de adaptación de cada individuo. • El cuarto muestra la adaptación de cada individuo. • El quinto hace referencia a la selección de los individuos, de acuerdo al método de la ruleta que seleccionamos en la configuración. • El sexto muestra los criterios de parada de ejecución del problema. Como se ve aquí el problema se detuvo cuando finalizaron de computarse todas las generaciones (100 en este caso).

El objetivo es encontrar la mejor combinación de los componentes que

intervienen en la mezcla. De esta manera se obtiene un valor correspondiente al Aire, al Combustible y al NOS. Esta será la mejor solución.

algoritmos genéticos

Technology