Trabajo De Aplicacion De Ag

Algoritmos Gen€ticos

UNIVERSIDAD CATOLICA DE SANTIAGO DEL ESTERO FACULTAD DE MATEMATICA APLICADA INGENIERIA EN COMPUTACION INTELIGENCIA ARTIFICIAL Dra. Rosanna Costaguta Ing. Mariela Gola

Trabajo de Aplicaci€n: Algoritmos Gen•ticos

Dutto, Evelina

- Noviembre 2008 -

Evelina E. Dutto

P•gina 0

Algoritmos Gen€ticos

1. IntroducciÄn Los Algoritmos Gen€ticos son m€todos adaptativos que pueden usarse para resolver problemas de b•squeda y optimizaci‚n. Estƒn basados en el proceso gen€tico de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selecci‚n natural y la supervivencia de los mƒs fuertes, postulados por Darwin (1859). Por imitaci‚n de este proceso, los Algoritmos Gen€ticos son capaces de ir creando soluciones para problemas del mundo real. La evoluci‚n de dichas soluciones hacia valores ‚ptimos del problema depende en buena medida de una adecuada codificaci‚n de las mismas. En la naturaleza los individuos de una poblaci‚n compiten entre s„ en la b•squeda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la b•squeda de un compa…ero. Aquellos individuos que tienen mƒs €xito en sobrevivir y en atraer compa…eros tienen mayor probabilidad de generar un gran n•mero de descendientes. Por el contrario individuos poco dotados producirƒn un menor n•mero de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagaran en sucesivas generaciones hacia un n•mero de individuos creciente. La combinaci‚n de buenas caracter„sticas provenientes de diferentes ancestros, puede a veces producir descendientes “s•per individuos", cuya adaptaci‚n es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas caracter„sticas cada vez mejor adaptadas al entorno en el que viven. Los

Algoritmos

Gen€ticos

usan

una

analog„a

directa

con

el

comportamiento natural. Trabajan con una poblaci‚n de individuos, cada uno de los cuales representa una soluci‚n factible a un problema dado. A cada individuo se le asigna un valor o puntuaci‚n, relacionado con la bondad de dicha soluci‚n. En la naturaleza esto equivaldr„a al gradote efectividad de un organismo para competir por determinados recursos. Cuanto mayor sea la Evelina E. Dutto

P•gina 1

Algoritmos Gen€ticos

adaptaci‚n de un organismo al problema, mayor serƒ la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material gen€tico con otro individuo seleccionado de igual forma. Este cruce producirƒ nuevos individuos, los cuales comparten algunas caracter„sticas de sus padres. Cuanto menor sea la adaptaci‚n de un individuo, menor serƒ la probabilidad de que dicho individuo sea seleccionado para la reproducci‚n, y por lo tanto de que su material gen€tico se propague en sucesivas generaciones. De esta manera se produce una nueva poblaci‚n de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporci‚n de buenas caracter„sticas en comparaci‚n con la poblaci‚n anterior. As„ a lo largo de las generaciones las buenas caracter„sticas se propagan a trav€s de la poblaci‚n. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las ƒreas mƒs prometedoras del espacio de b•squeda. Si el Algoritmo Gen€tico ha sido bien dise…ado, la poblaci‚n convergerƒ hacia una soluci‚n ‚ptima del problema. El poder de los Algoritmos Gen€ticos proviene del hecho de que se trata de una t€cnica robusta, y pueden tratar con €xito una gran variedad de problemas provenientes de diferentes ƒreas, incluyendo aquellos en los que otros m€todos encuentran dificultades. Si bien no se garantiza que el Algoritmo Gen€tico encuentre la soluci‚n ‚ptima del problema, existe evidencia emp„rica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimizaci‚n combinatoria. El gran campo de aplicaci‚n de los Algoritmos Gen€ticos se relaciona con aquellos problemas para los cuales no existen t€cnicas especializadas. Incluso en el caso en que dichas t€cnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas combinƒndolas con los Algoritmos Gen€ticos. La estructura de este trabajo es como sigue: en la siguiente secci‚n se introduce por medio de pseudoc‚digo, el denominado Algoritmo Gen€tico Simple, tambi€n conocido como Algoritmo Gen€tico Can‚nico.

Evelina E. Dutto

P•gina 2

Algoritmos Gen€ticos

En la posterior secci‚n nos preguntamos como saber si es posible la utilizaci‚n de algoritmos gen€ticos

frente a determinadas situaciones. A

continuaci‚n se redacta la aplicaci‚n dise…ada, la problemƒtica de origen, la descripci‚n de los elementos utilizados en el desarrollo del algoritmo, se presentan las diferentes pantallas dise…adas. Finalizo el trabajo con la demostraci‚n del c‚digo fuente.

2. Algoritmo GenÅtico Simple BEGIN Generar Poblaci‚n Inicial Computar Funci‚n de evaluaci‚n (Fitness) para cada individuo WHILE NOT Fin DO Seleccionar dos individuos de la anterior generaci‚n, para el cruce (probabilidad

de selecci‚n

proporcional a la

funci‚n de

evaluaci‚n del individuo). Reproducir con cierta probabilidad los dos individuos obteniendo dos descendientes. Mutar los descendientes con cierta probabilidad. Definir nueva generaci‚n Computar Fitness para cada individuo IF Poblaci‚n convergi‚ THEN Fin IS TRUE ENDWHILE END

3. ÇCÄmo saber si es posible usar el Algoritmo GenÅtico? La aplicaci‚n mƒs com•n de los algoritmos gen€ticos ha sido la soluci‚n de problemas de optimizaci‚n, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pueden ser apropiados para la

Evelina E. Dutto

P•gina 3

Algoritmos Gen€ticos

t€cnica, y se recomienda en general tomar en cuenta las siguientes caracter„sticas del mismo antes de intentar usarla:  Su espacio de b•squeda debe estar delimitado dentro de un cierto rango. Lo mƒs recomendable es intentar resolver problemas que tengan espacios de b•squeda discretos -aunque €stos sean muy grandes-.  Debe poderse definir una funci‚n de aptitud que nos indique qu€ tan buena o mala es una cierta respuesta. La funci‚n de aptitud no es mƒs que la funci‚n objetivo de nuestro problema de optimizaci‚n.  Las soluciones deben codificarse de una forma que resulte relativamente fƒcil de implementar en la computadora. La codificaci‚n mƒs com•n de las respuestas es a trav€s de cadenas binarias, aunque se han utilizado tambi€n n•meros reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que se propuso originalmente, y ademƒs porque resulta muy sencillo de implementar.

4. AplicaciÄn 4.1 ProblemÉtica La realidad en la que nos vemos inmersos, esta totalmente tecnificada y demanda a diario nuevas tecnolog„as de desarrollo. As„ la informƒtica, en todos sus ƒmbitos tanto de dise…o, desarrollo y programaci‚n de software, como de dise…o e implementaci‚n de hardware y redes, se abre camino y se vuelve cada vez mƒs indispensable para el ‚ptimo crecimiento y funcionamiento de las distintas organizaciones de la comunidad. Frente a esta situaci‚n, hay numerosas personas que se han dedicado al estudio de esta rama de la ciencia y han adquirido seg•n sus preferencias, diferentes

perfeccionamientos

en

diversas

ƒreas

de

la

misma,

perfeccionamientos que les permiten el acceso a niveles de vida mas exitosos, ya que es una actividad por que la que se reciben importantes remuneraciones.

Evelina E. Dutto

P•gina 4

Algoritmos Gen€ticos

Al mismo tiempo, la creciente demanda de aplicaciones de software, exige la creaci‚n de organizaciones o empresas dedicadas al dise…o, desarrollo e implementaci‚n de aplicaciones de escritorio y de aplicaciones web. En base a esta situaci‚n, surge la necesidad de la creaci‚n de esta aplicaci‚n respaldada por las bondades de los Algoritmos Gen€ticos. La aplicaci‚n mencionada, viene a ayudar a las distintas organizaciones, en la selecci‚n del

mejor programador, seg•n las aptitudes que de €l se

requieran, por ejemplo, dise…o de interfaces, capacidad anal„tica, capacidad de observaci‚n,

esp„ritu autodidacta, creatividad, originalidad, entre otras.

Ademƒs, el algoritmo, a partir del sueldo base que se le asigna al programador que tenga todas las aptitudes consideradas para esta aplicaci‚n, mostrarƒ el porcentaje de ese sueldo base a resarcirle al programador seleccionado, y el correspondiente importe.

4.2 DescripciÄn A continuaci‚n se describen cada uno de los elementos usados en la construcci‚n del algoritmo: 

SelecciÄn de la variable de entrada.

En este caso la variable de entrada o cromosoma estƒ conformada por diez caracter„sticas (ci) consideradas en un programador tipo, estas son:  Experiencia con el uso de la herramienta  Conocimientos en Bases de Datos  Dise…o de Interfaz  Capacidad Anal„tica  Capacidad de Comprensi‚n  Creatividad  Originalidad  Conocimiento de Servidores  Ingl€s T€cnico Evelina E. Dutto

P•gina 5

Algoritmos Gen€ticos

 Autodidacta Al iniciar el algoritmo el usuario deberƒ asignar una prioridad a estas caracter„sticas seg•n el puesto en el que ese desarrollarƒ, as„, la que se encuentre en la parte superior de la lista obtendrƒ un ponderador (wi) de valor mayor (10), y la que se encuentre al final de la lista, tendrƒ el ponderador de menor valor (1). Un programador que re•na la totalidad de las caracter„sticas en el mercado laboral actual recibe $4000 mensuales. Por cada caracter„stica, se paga un determinado porcentaje de los $4000 antes mencionados, de esta manera:

Experiencia con el uso de la herramienta 20 % Conocimientos en Bases de Datos

15 %

Dise‚o de Interfaz

13 %

Capacidad Analƒtica

11 %

Capacidad de Comprensi„n

6%

Creatividad

8%

Originalidad

6%

Conocimiento de Servidores

8%

Ingl€s T€cnico

8%

Autodidacta

5%

Al finalizar la ejecuci‚n, el algoritmo devolverƒ las caracter„sticas que posee el programador seleccionado, el porcentaje del sueldo que le corresponde recibir por las caracter„sticas que posee, y el importe del mismo. Por lo tanto, el cromosoma es un vector fila con diez elementos: Cromosoma= [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10]

Evelina E. Dutto

P•gina 6

Algoritmos Gen€ticos



CodificaciÄn de la variable de entrada.

El cromosoma de entrada se inicializa aleatoriamente, mediante codificaci‚n binaria. El valor representa la existencia o no de la caracter„stica, as„, 1 – posee caracter„stica, 0 – no posee caracter„stica. 

TamaÑo de la poblaciÄn.

Una cuesti‚n que uno puede plantearse es la relacionada con el tama…o id‚neo de la poblaci‚n. Parece intuitivo que las poblaciones peque…as corren el riesgo de no cubrir adecuadamente el espacio de b•squeda, mientras que el trabajar con poblaciones de gran tama…o puede acarrear

problemas

relacionados con el excesivo costo computacional. Se efectuaron estudios te‚ricos, y se obtuvo como conclusi‚n que el tama…o ‚ptimo de la poblaci‚n para

cromosomas

de

longitud

l,

con

codificaci‚n

binaria,

crece

exponencialmente con el tama…o del cromosoma. Posteriormente, basƒndose en evidencia emp„rica se sugiri‚ que un tama…o de poblaci‚n comprendida entre l y 2l es suficiente para la definici‚n del problema. En base a esto, decid„ inicializar la poblaci‚n con un a valor de veinte individuos, para el caso, veinte programadores aspirantes al puesto. Dado que la longitud del cromosoma utilizado es diez. 

FunciÄn de aptitud o de adaptaciÄn (Fitness).

Debe ser dise…ada para cada problema de manera espec„fica. Dado un cromosoma particular, la funci‚n de adaptaci‚n le asigna un n•mero real, que se supone refleja el nivel de adaptaci‚n al problema del individuo representado por el cromosoma. La funci‚n de aptitud utilizada es: F(x) = ∑ ci * wi , … donde wi 1 ≤ i ≤ 10, para i=1 toma valor 10, para i=10 toma valor 1 y ci representa el valor de la caracter„stica (0/1).

Evelina E. Dutto

P•gina 7

Algoritmos Gen€ticos



SelecciÄn.

Una vez calificados todos los individuos de una generaci‚n, el algoritmo debe, al igual que lo hacen la naturaleza y el hombre, seleccionar a los individuos mƒs calificados, mejor adaptados al medio, para que tengan mayor oportunidad de re-producci‚n. De esta forma se incrementa la probabilidad de tener individuos “buenos” (con alta calificaci‚n) en el futuro. En esta aplicaci‚n, los individuos se reproducen mediante la estrategia de selecci‚n directa, despu€s de la calificaci‚n se ordenan los individuos de mayor a menor, seg•n el fitness obtenido, y se reproducirƒn de a pares, el de mayor valor, con el de valor inmediatamente inferior. 

Cruce.

El c‚digo gen€tico de los padres de un individuo se mezcla para producir hijos con caracter„sticas de ambos padres, as„ la operaci‚n de cruce en esta aplicaci‚n se realiza mediante la estrategia destructiva, es decir, los hijos se insertan en la nueva poblaci‚n aunque tengan un fitness menor que el de sus padres. Los bits elegidos para el cruce son el bits 2 y el bits 7…

Padres

Hijos

Puntos de Cruce Bits 2 Bits 7

Evelina E. Dutto

P•gina 8

Algoritmos Gen€ticos



MutaciÄn.

Ocasionalmente algunos elementos del c‚digo de ciertos individuos de un

algoritmo

gen€tico

se

alteran

a

prop‚sito.

Šstos

se

seleccionan

aleatoriamente en lo que constituye el s„mil de una mutaci„n. El objetivo es generar nuevos individuos, que exploren regiones del dominio del problema que probablemente no se han visitado a•n. La mutaci‚n, produce una variaci‚n en la informaci‚n gen€tica contenida en un cromosoma. Generalmente se efect•a a trav€s del cambio de valor de un gen de 1 por 0, o viceversa, luego de la operaci‚n de reproducci‚n, y con una probabilidad de ocurrencia muy baja. Para esta aplicaci‚n especifica, la probabilidad de ocurrencia es de 0.03, solo mutarƒ un bit del primer hijo, y el bit a mutar serƒ seleccionado aleatoriamente. 

Criterio de fin.

La condici‚n de fin establecida para este algoritmo gen€tico, esta especificada en diez generaciones.

Evelina E. Dutto

P•gina 9

Algoritmos Gen€ticos

4.3 PresentaciÄn de Pantallas Pantalla Principal

Pantalla Acerca De

Evelina E. Dutto

P•gina 10

Algoritmos Gen€ticos

Pantalla Algoritmo Gen€tico

Pantalla de Resultados

Evelina E. Dutto

P•gina 11

Algoritmos Gen€ticos

4.4 CÄdigo Fuente using using using using using using using

System; System.Collections.Generic; System.ComponentModel; System.Data; System.Drawing; System.Text; System.Windows.Forms;

namespace WindowsApplication1 { public partial class Form1 : Form { //TamaÄo de poblacion private int POP = 20; //habilidades private int LEN = 10; //Probabilidad de mutacion //Generaciones private double END = 10; //vector de porcentajes p/c caracteristica private int[] porcentajes = new int[10] { 20, 15, 13, 11, 6, 8, 6, 8, 8, 5 }; //genes de 20 programadores por 10 habilidades private int[,] genes = new int[20, 11]; //ramdom para seleccionar los genes Random rnd = new Random(); //Constructor del programa Array myArr = Array.CreateInstance(typeof(Int32), 2, 3); private string[] arre = new String[10] { "Experiencia con el Uso de la Herramienta", "Conocimiento en Bases de Datos", "DiseÄo de Interfaz", "Capacidad Analitica", "Capacidad de Compresion", "Creatividad", "Originalidad", "Conocimiento de Servidores", "Ingles Tecnico", "Autodidacta" }; public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { enlazarlist(); } private void enlazarlist() { this.listBox1.DataSource = arre; } private void button3_Click(object sender, EventArgs e) { run(); }

public void run() { //******comienza el algoritmo******** //inicializamos la poblacion init_pop(); //comienzan las generaciones for (int generaciones = 0; generaciones < END; generaciones++) { //tomamos dos miembro de la poblacion, los dos mayores fitness(); reproduccion(); } fitness();

Evelina E. Dutto

P•gina 12

Algoritmos Gen€ticos

verfinal(); //******Termina el algoritmo******** } //*****FITNESS***** private void fitness() { for (byte i = 0; i < POP; i++) { for (byte j = 0; j < LEN; j++) { genes[i, 10] += genes[i, j] * (10 - j); } } //terminamos de calcular el fitnes de cada programador //ordenamos segun fitness mayor int arre = 0; for (byte i = 0; i < POP; i++) { for (int k = i + 1; k < POP; k++) { //int k = (i + 1); if (genes[i, 10] < genes[k, 10]) { for (byte j = 0; j < LEN + 1; j++) { arre = genes[i, j]; genes[i, j] = genes[k, j]; genes[k, j] = arre; } } } } } private void reproduccion() { // bits 2 y 7 de cruce int a, b, k; int arre; for (int i = 0; i < POP; i = i + 2) { k = i + 1; //genero los hijos for (int j = 2; j < LEN - 2 + 1; j++) { arre = genes[i, j]; genes[i, j] = genes[k, j]; genes[k, j] = arre; } mutacion(i); } } private void mutacion(int hijo1) { int genmuta; double a; genmuta = rnd.Next(9); a = rnd.NextDouble(); if (a <= 0.03) { genes[hijo1, genmuta] = 1 - genes[hijo1, genmuta]; } }

private void init_pop() { //Recorro los programadores - filas for (int i = 0; i < POP; i++) {

Evelina E. Dutto

P•gina 13

Algoritmos Gen€ticos

//recorro las habilidades - columnas for (int j = 0; j < LEN; j++) { //creo valores 0 1 para las habilidees if (rnd.NextDouble() < 0.5) { genes[i, j] = 0; } else { genes[i, j] = 1; } } } } private void button1_Click(object sender, EventArgs e) { if (this.listBox1.SelectedIndex != 0) { string aux = this.listBox1.Text ; arre[this.listBox1.SelectedIndex] = arre[listBox1.SelectedIndex - 1]; arre[listBox1.SelectedIndex - 1]= aux; int aux2 = porcentajes[listBox1.SelectedIndex]; porcentajes[listBox1.SelectedIndex] = porcentajes[listBox1.SelectedIndex - 1]; porcentajes[listBox1.SelectedIndex - 1]= aux2; listBox1.DataSource = null; enlazarlist(); listBox1.SetSelected(listBox1.SelectedIndex - 1, true); listBox1.Refresh(); } } private void button2_Click(object sender, EventArgs e) { if (this.listBox1.SelectedIndex < 9) { string aux = this.listBox1.Text; arre[this.listBox1.SelectedIndex] = arre[listBox1.SelectedIndex + 1]; arre[listBox1.SelectedIndex + 1] = aux; int aux2 = porcentajes[listBox1.SelectedIndex]; porcentajes[listBox1.SelectedIndex] = porcentajes[listBox1.SelectedIndex + 1]; porcentajes[listBox1.SelectedIndex + 1] = aux2; listBox1.DataSource = null; enlazarlist(); listBox1.SetSelected(listBox1.SelectedIndex + 1,true); } } private void verfinal() { LimpiarCheck(); int sueldo = 0; for (byte j = 0; j < LEN ; j++) { if (genes[0, j] ==1) { switch(arre[j]) { case "Experiencia con el Uso de la Herramienta": chkExperiencia.Checked = true; break; case "Conocimiento en Bases de Datos": chkBaseDatos.Checked=true; break; case "DiseÄo de Interfaz": chkDiseÄoInterfaz.Checked = true; break; case "Capacidad Analitica": chkCapacAnalitica.Checked = true; break; case "Capacidad de Compresion": chkCapacComp.Checked = true; break; case "Creatividad":

Evelina E. Dutto

P•gina 14

Algoritmos Gen€ticos

this.chkCreatividad.Checked = true; break; case "Originalidad": this.chkOriginalidad.Checked = true; break; case "Conocimiento de Servidores": this.chkServidores.Checked = true; break; case "Ingles Tecnico": chkIngles.Checked = true; break; case "Autodidacta": this.chkAutodidacta.Checked = true; break; } sueldo += porcentajes[j]; } } this.txtporcentaje.Text = sueldo.ToString() + " %"; sueldo = (int)Math.Ceiling( 4000 * sueldo * 0.01); this.txtSueldo.Text = "$ " + sueldo.ToString(); MessageBox.Show("El Algoritmo ha finalizado", "Resultados Listos", MessageBoxButtons.OK, MessageBoxIcon.Information); }

private void LimpiarCheck() { chkCreatividad.Checked = false; chkAutodidacta.Checked = false; chkBaseDatos.Checked = false; chkCapacAnalitica.Checked = false; chkCapacComp.Checked = false; chkDiseÄoInterfaz.Checked = false; chkExperiencia.Checked = false; chkIngles.Checked = false; chkOriginalidad.Checked = false; chkServidores.Checked = false;

}

private void button1_MouseMove(object sender, MouseEventArgs e) { this.button1.Size = new System.Drawing.Size(61, 56); } private void button1_MouseLeave(object sender, EventArgs e) { this.button1.Size = new System.Drawing.Size(51, 46); } private void button2_MouseLeave(object sender, EventArgs e) { this.button2.Size = new System.Drawing.Size(51, 46); } private void button2_MouseMove(object sender, MouseEventArgs e) { this.button2.Size = new System.Drawing.Size(61, 56); } private void button3_MouseLeave(object sender, EventArgs e) { this.button3.Size = new System.Drawing.Size(59, 53); } private void button3_MouseMove(object sender, MouseEventArgs e) { this.button3.Size = new System.Drawing.Size(69, 63); } private void panel1_Paint(object sender, PaintEventArgs e) {

Evelina E. Dutto

P•gina 15

Algoritmos Gen€ticos

} private void acercaDeToolStripMenuItem_Click(object sender, EventArgs e) { Form acerca = new FrmAcerca(); acerca.ShowDialog(); } private void algoritmoToolStripMenuItem_Click(object sender, EventArgs e) { Form algoritmo = new FrmAlgoritmo(); algoritmo.ShowDialog(); } }

}

5. Conclusiones  Los Algoritmos Gen€ticos son t€cnicas de gran utilidad en la optimizaci‚n de funciones que son dif„ciles de tratar haciendo uso de las t€cnicas de optimizaci‚n clƒsica.  El Algoritmo Gen€tico desarrollado permiti‚ encontrar el programador con fitness mƒs alto, devolvi‚ como respuesta las caracter„sticas que el “ganador” posee, y el sueldo a abonarle.  Personalmente, el desarrollo de este trabajo me brindo una grata experiencia, ya que obtuve conocimientos mƒs espec„ficos y concretos sobre los algoritmos gen€ticos. En este trabajo se introdujo por medio de pseudoc‚digo, el denominado Algoritmo Gen€tico Simple, tambi€n conocido como Algoritmo Gen€tico Can‚nico. En la posterior secci‚n se respondi‚ sobre como saber si es posible la utilizaci‚n de algoritmos gen€ticos

frente a determinadas situaciones. A

continuaci‚n se redact‚ la aplicaci‚n dise…ada, la problemƒtica de origen, la descripci‚n de los elementos utilizados en el desarrollo del algoritmo, se presentaron las diferentes pantallas dise…adas. Finaliz‚ el trabajo con la demostraci‚n del c‚digo fuente.

Evelina E. Dutto

P•gina 16