Algoritmo Genetico

Análisis de Algoritmos
Taller 4
Algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Sebastián Luengo Sandoval Joaquín Morales Díaz 16 de junio de 2012

Universidad Tecnológica Metropolitana Facultad de Ingeniería Departamento de Informática

Contenido
Algoritmos Genéticos.......................................................................................................................... 2 Algoritmo genético 1 ....................................................................................................................... 2 Algoritmo genético 2 ....................................................................................................................... 5 Algoritmo genético 3....................................................................................................................... 8 Algoritmo genético 4 ..................................................................................................................... 11 Conclusión ......................................................................................................................................... 14

Universidad Tecnológica MetropolitanaFacultad de Ingeniería Departamento de Informática

Algoritmos Genéticos
Algoritmo genético 1
Algoritmo genético para encontrar solución aproximada a la ecuación no-lineal:

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace AlgoritmoGenetico1 { class Program { static void Main(string[] args) { Program p = new Program(); double x = 2; for (int i =0; i < 1000000; i++) { double newX = x; newX = p.mutar(newX);

double fN, fO; fO = p.fitness(x); fN = p.fitness(newX); if (Math.Abs(fN) < Math.Abs(fO)) { int iteracion = 1; Console.WriteLine(iteracion + "Resultado de la E. No-Lineal: " + fN + " con x: " + newX); iteracion += 1; } } Console.WriteLine(); Console.Read(); }

public double mutar(double newX) { double intervalo1 = (double)0; doubleintervalo2 = (double)4; Random r = new Random((int)DateTime.Now.Ticks); do { newX = newX * r.NextDouble() + r.Next(0,4); } while (newX < intervalo1 || newX > intervalo2); return newX; } public double fitness(double x) { return(Math.Pow(x, 3) - 2 * Math.Pow(x, 2) - 5); } } }

Universidad Tecnológica Metropolitana Facultad de Ingeniería Departamento de Informática

Descripción del algoritmoEl algoritmos cuenta con 2 funciones mutar y fitness, la primera retorna valores “Double” y nos permite realizar una modificación a un valor de entrada, esta alteración se realiza multiplicando el numero que queremos modificar por un valor aleatorio entre 0,0 y 1,0 además de adicionarle un numero entre 0 y 4; Controlando que el valor este dentro de los rangos que definamos, para este caso [0,4]. Lasegunda función recibe como parámetro un valor, con el que calcularemos el resultado de la ecuación no-lineal a resolver, devolviéndolo el resultado obtenido al programa principal que llamo a la función. Dentro del programa principal encontramos una sentencia “for()” para realizar las iteraciones necesarias que nos permitirá acércanos a la solución de la ecuación no-lineal. Cabe señalar que laaleatoriedad con las que necesitamos trabajar la realizamos con una clase del sistema llamada “Random” que produce una secuencia de números que cumplen determinados requisitos estadísticos de aleatoriedad. Para la generación de números de forma óptima se debe pasar como semilla “DateTime.Now.Ticks” cuyo uso nos asegura una aleatoriedad eficiente para trabajar este algoritmo.

Metodología depruebas
Para poder generar soluciones aproximadas, iniciamos las pruebas con un valor elegido indeterminadamente dentro del rango del problema, luego obtenemos un nuevo valor con la función mutar descrita anteriormente, permitiéndonos generar dos posibles soluciones, para determinar con cual de estas dos nos quedamos, comparamos el valor absoluto, estableciendo el menor como una aproximación al...