Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 1 de 18
Pant. Completa
Cerrar
Salir
Resolviendo problemas con algoritmos geneticos
Mauro Parra Miranda
My brain is open.Paul Erdos
http://www.gnulinux.biz/mauro/
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 2 de 18
Pant. Completa
Cerrar
Salir
1. Algoritmo Genetico
Un algoritmo genetico es un metodo probabilıstico que mantieneuna poblacion de individuos Pt = {x1
t , . . . , xnt } para cada iteracion
t.
Cada individuo representa una solucion potencial del problemaque se este resolviendo. Cada solucion xi
t es evaluada de algunamanera para conocer su desempeno con respecto a la poblacionactual.
Una nueva poblacion (la t+1) es generada a traves de la seleccionde los individuos mejor adaptados (o sea, las mejores soluciones).Algunos individuos de la poblacion son alterados por algunos oper-adores, llamados operadores geneticos.
Los operadores geneticos mas usados son la cruza y mutacion. Lacruza consiste en combinar dos soluciones, mientras que la mutaciones alterar ligeramente una solucion de manera aleatoria.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 3 de 18
Pant. Completa
Cerrar
Salir
1. Generar poblacion Aleatoria (uniformemente distribuida, de pref-erencia).
2. Calificar a los individuos de la poblacion
3. Aplicar los operadores geneticos a la poblacion actual paragenerar una nueva poblacion, que sustituira a la actual.
4. Si el numero de generaciones (iteraciones) no es suficiente o nose ha llegado a la respuesta Regresar al paso 2.
5. Mostrar las mejores respuestas.
Los operadores geneticos son aquellas operaciones que nos permitengenerar a la nueva poblacion. Tradicionalmente, se aplican 3:
Elitismo. Un porcentaje de la poblacion actual se translada ala nueva poblacion. Al menos debe de estar el mejor individuoactual, ya que de esa manera no se pierde informacion.
Cruza. Con probabilidad pc se combina el genoma de dos indi-viduos previamente seleccionados.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 4 de 18
Pant. Completa
Cerrar
Salir
Mutacion. Con probabilidad pm se modifica el genoma de unindividuo, antes de anadirlo a la nueva poblacion.
Obviamente, es comun aplicar otros operadores, como por ejem-plo:
1. Generacion de algunos individuos nuevos de manera aleatoria.
2. Correccion de soluciones (usualmente en problemas de grafi-cas).
3. Migracion de individuos si es que esta corriendo de forma par-alela.
4. Obtencion de estadisticas.
5. Reconfiguracion automatica de los parametros.
6. ...y mas.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 5 de 18
Pant. Completa
Cerrar
Salir
2. Implementando un algoritmo genetico
La parte interesante de un algoritmo genetico es que solamentese requiere implementar una sola vez. Realmente lo unico que cam-bia es la codificacion del dominio del problema y como evaluarque solucion propuesta es mejor (normalmente, con respecto a lapoblacion).
Por ejemplo, un problema difıcil de resolver pero facil de enten-der es el problema de 3-SAT. El problema consiste en que tienesexpresiones como la siguiente:
e = (x1 ∨ ¬x3 ∨ x4) ∧ (x2 ∨ x6 ∨ x3) ∧ . . . ∧ (x12 ∨ x1 ∨ x3)
y tienes que generar una tabla de valores que satisfaga la expresion.En este caso, basta con:
x1 = true, x3 = true
y lo demas puede quedar como se desee.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 6 de 18
Pant. Completa
Cerrar
Salir
El tamano del espacio de busqueda de posibles soluciones estadado por 2n donde n es el numero de variables booleanas que in-tervienen en la expresion. Para n = 8, el espacio de busqueda esde tamano 256, mientras que para n = 32 es de 4, 294, 967, 296(n = 64; 18, 446, 700, 000, 000, 000, 000) .
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 7 de 18
Pant. Completa
Cerrar
Salir
En este problema, es sencillo generar soluciones:
public class Individuo{
BitSet genotype;
...
Individuo(int size){
Random rnd =
new Random(java.util.Calendar.getTimeInMillis());
genotype = new BitSet(size);
for(int i = 0; i < size; i++){
if(rnd.nextDouble() > 0.5)
genotype.set(i);
}
} ...
}
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 8 de 18
Pant. Completa
Cerrar
Salir
Cada bit corresponde al valor de cada variable booleana xi:
genotype.get(i) == xi
Una de las formas de evaluar la solucion es la siguiente:
counter = 1
Revisar si cada subexpresion de tipo:
(xi ∨ xj ∨ xk)
es verdadera segun el genotipo. En tal caso, counter + +.
Al terminar, obtener como medida de desempeno a
f =counter
total de subexpresiones
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 9 de 18
Pant. Completa
Cerrar
Salir
En tal caso, dara un valor de 0,5 cuando tengas la mitad de lassubexpresiones resueltas y un valor de 1 cuando hayas resuelto elproblema.
Seleccionamos un par de individuos de la poblacion, que seranen los que aplicaremos los operadores geneticos.
La forma clasica de seleccionar un par de individuos es la seleccionde ruleta, esto es, tal como en los concursos de la television, tenemosuna ruleta dividida acorde con el desempeno de cada individuo yluego le damos un par de vueltas para ver a quien escogeremos. Encodigo:
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 10 de 18
Pant. Completa
Cerrar
Salir
public class Poblation{
private Individuo population[];
...
public Individuo select(){
double sum = 0.0, tope=0.0, suma=0.0;
for(int i=0; i<population.length; i++)sum+=population[i].getFitness();
tope = rnd.nextDouble()*sum;
for(int i = 0; i<population.length; i++){
suma+=population[i].getFitness();
if (suma>=tope)
return population[i];
}
}
...
}
Lo cual nos regresa un individuo al azar. Cuando tengamos dos,
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 11 de 18
Pant. Completa
Cerrar
Salir
podemos aplicar los operadores geneticos. Tradicionalmente se apli-can tres: elitismo, cruza y mutacion.
public class Poblation{
...
public Individuo[] elitism(double percent){
int number = (int)(this.getSize()*percent);
Individuo arr[];
arr = new Individuo[number];
this.sort();
for(int i = 0; i<number; i++){
arr[i] = population[i];
}
return arr;
}
...
}
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 12 de 18
Pant. Completa
Cerrar
Salir
public class Individuo{
...
public Individuo crossover(Individuo e, double pc){
Individuo n;
BitSet nbs = this.getGenome();
BitSet obs = e.getGenome();
if(rnd.nextDouble()<pc){
for(int i = (nbs.length()/2); i<nbs.length(); i++){
nbs.set(i, obs.get(i));
}
}
n = new Individuo(nbs);
return n;
}
...
}
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 13 de 18
Pant. Completa
Cerrar
Salir
public class Individuo{
...
public Individuo mutate(double pm){
Individuo n;
BitSet bs = this.getGenome();
for(int i = 0; i<bs.length(); i++){
if (rnd.nextDouble()<pm){
bs.flip(i);
}
}
n = new Individuo(bs);
return n;
}
...
}
Notese que el plan aquı es explotar (elitismo, cruza) el conocimien-to adquirido y explorar (mutacion) el espacio de posibles soluciones.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 14 de 18
Pant. Completa
Cerrar
Salir
Un algoritmo genetico es facilmente paralelizable. En ocasiones,las funciones de evaluacion de desempeno podrıan requerir muchotiempo para ser evaluadas, por lo que se asigna un individuo porprocesador disponible.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 15 de 18
Pant. Completa
Cerrar
Salir
3. Aplicaciones en Software
1. Creacion de horarios (sin colisiones)
2. Analisis Financiero (Explotando el analisis tecnico)
3. Solucionar ecuaciones diferenciales ordinarias (¿sin dolor?)
4. Diseno de robots (Basilisc)
5. Descubrimiento de estrategias para Teorıa de juegos (El dilemadel prisionero, Oligopolios)
6. Adaptando lineas de produccion
7. Generar musica
8. Optimizando el diseno de PCBs (Printed Circuit Boards, usandoTSP)
9. Optimizando el diseno de procesadores (usando TSP: TravellingSalesman Problem)
10. Control de trafico aereo
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 16 de 18
Pant. Completa
Cerrar
Salir
11. Creacion de rutas de reparticion optimas (graficas planas!)
12. Creacion de algoritmos para mantener la consistencia del coloren retinas artificiales.
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 17 de 18
Pant. Completa
Cerrar
Salir
4. Recursos utiles
http://www.gnulinux.biz/mauro/
“Genetic Algorithms + Data Structures = Evolution Programs”.Zbigniew Michalewicz. Springer.
“Evolutionary Programming IV”. John R. McDonnell, et al.MIT Press.
“Evolutionary Programming V”. Lawrence J. Fogel, et al. MITPress.
“Applications of Evolutionary Computing”. Egbert Boers, et al.Springer.
“Genetic Programming”. Julian Miller, et al. Springer.
The Genetic Algorithms archive.http://www.aic.nrl.navy.mil/galist/
Basilisc.http://ganso5.fi-b.unam.mx/basilisc/basilisc.html
Optimizando
programas
con
algoritmos
geneticos
Algoritmo Genetico
Implementando . . .
Aplicaciones en . . .
Recursos utiles
Home Page
Tıtulo
JJ II
J I
Atras
Pagina 18 de 18
Pant. Completa
Cerrar
Salir
Genetic Algorithms Warehouse.http://geneticalgorithms.ai-depot.com/Applications.html
Adaptacion de lineas de produccion.http://www.ici.ro/ici/revista/sic2000 4/art01.htm
“A grammar based Genetic Programming technique applied tomusic generation”. Jeffrey Putnam. [email protected]
GaLibhttp://lancet.mit.edu/ga/
Genetic Programminghttp://www.genetic-programming.org/
“Software that writes software”. Alexis Willihnganz.http://www.genetic-programming.com/published/Salon081099.html