Algoritmos Bioinspirados.
Departamento de Matem´ aticas, Estad´ıstica y Computaci´ on Universidad de Cantabria
13 de abril de 2011
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
1/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
2/87
Problemas de optimizaci´on. Descripci´on. Dado un problema, se trata de encontrar la mejor soluci´on que cumpla ciertas restricciones.
Problema. (Optimizaci´on) m´ın
f (x)
sujeto a g (x) = 0 h(x) ≤ 0
En las siguientes trasnparencias presentamos diversos m´etodos para tratar de resolver este tipo de problemas. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
3/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
4/87
M´ etodos Anal´ıticos[Varios, b]. Descripci´on. La principal caracter´ıstica de este m´etodo es que lidia con problemas cuya descripci´on se realiza mediante Funciones Anal´ıticas. Para resolver este tipo de problemas es necesario recurrir a las potentes herramientas del An´alisis Matem´atico.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
5/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
6/87
M´etodo de los Multiplicadores de Lagrange[Varios, f]. Descripci´on. Transforma el resolver un problema de optimizaci´ on en hallar las soluciones de un sistema de ecuaciones.
Problema. (Optimizaci´on) m´ın
f (x)
Problema. (Algebraico) =⇒
sujeto a g (x) = 0
C.E. Borges, J.L. Monta˜ na
encontrar
x
tal que F (x) = 0
Universidad de Cantabria
7/87
M´etodo de los Multiplicadores de Lagrange. Problemas a los que se aplica.
En general, aparece en muchos procesos de Ingenier´ıa. Entre ellos cabe destacar aquellos relacionados con la ingenier´ıa de materiales y el c´alculo de estructuras.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
8/87
Ventajas y Desventajas.
S´olo es se puede usar cuando las restricciones que deben cumplir las soluciones son del tipo cumplir una ecuaci´ on. Es necesario conocer la expresi´ on algebraica tanto de la funci´on a optimizar como la ecuaci´ on que deben cumplir las soluciones. Adem´as, ambas deben cumplir ciertas condiciones matem´aticas bastante estrictas. Se obtiene m´aximos y m´ınimos, globales y locales. Desgraciadamente, NO se puede resolver sistemas de ecuaciones (no lineales) de forma eficiente.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
9/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
10/87
M´etodo del Descenso de Gradiente[Varios, e]. Descripci´on. Transforma un problema de optimizaci´ on en un proceso iterativo en el que, a partir de una aproximaci´ on inicial, se calcula en qu´e direcci´on se encuentra una soluci´on mejor y la longitud a la que se encuentra. Iteraci´on tras iteraci´ on, la soluci´on inicial se aproxima hacia el o´ptimo.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
11/87
M´etodo del Descenso de Gradiente Problemas a los que se aplica.
En general se usa en los mismos casos en los que se usa el M´etodo de los Multiplicadores de Langrange. Adem´as, tambi´en es u ´til en los siguientes problemas: C´alculo de Equilibrios de Nash. ´ Resoluci´on de problemas de Control Optimo.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
12/87
M´etodo del Descenso de Gradiente Ventajas y Desventajas.
S´olo es se puede usar cuando las restricciones que deben cumplir las soluciones son del tipo cumplir una ecuaci´ on. Es necesario conocer la expresi´ on algebraica tanto de la funci´on a optimizar como la ecuaci´ on que deben cumplir las soluciones. Adem´as, ambas deben cumplir ciertas condiciones matem´aticas. Dado un buen candidato inicial se garantiza la convergencia a un m´ınimo local. Desgraciadamente NO sabemos como encontrar buenos candidatos iniciales. El n´ umero de iteraciones puede ser muy alto.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
13/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
14/87
Programaci´ on Lineal[Varios, g].
Descripci´on. Transforma un problema de optimizaci´ on en un proceso iterativo en el que a partir de una soluci´on factible inicial se van generando otras posibles soluciones hasta encontrar el ´ optimo.
Problema. (Programaci´on Lineal) m´ın
c·x
sujeto a Ax ≤ b
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
15/87
Programaci´ on Lineal Problemas a los que se aplica.
Optimizar mezclas qu´ımicas. Gesti´on de inventarios y carteras financieras. Asignaci´on de recursos humanos y maquinaria. Flujos en redes de telecomunicaciones y transporte de mercanc´ıas.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
16/87
Programaci´ on Lineal Ventajas y Desventajas.
Funciona r´apido incluso con problemas muy grandes. Tanto la condici´on de ser soluci´ on como la funci´ on a optimizar son muy restrictivas pues ambas tienen que ser lineales.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
17/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
18/87
M´ etodos Combinatorios[Varios, b]. Descripci´on. La principal caracter´ıstica de este m´etodo es que lidia con problemas cuyo espacio de soluciones es finito. La diversidad de problemas y posibles soluciones es tan amplia que es imposible dar una idea general.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
19/87
M´ etodos Combinatorios. Problemas a los que se aplica.
Problema de la Mochila. ´ Arbol m´ınimo. Flujo m´aximo. Problema de emparejamientos.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
20/87
M´ etodos Combinatorios. Ventajas y Desventajas.
Hay multitud de estrategias para cada problema. Generalmente son problemas muy dif´ıciles pues el n´ umero de candidatos a soluci´on, aunque finito, es inmenso. La estrategia m´as simple es la fuerza bruta. Esto es, probar con todos los candidatos. Existen mejoras a esta aproximaci´ on como son las estrategias voraces, ramificaciones y podas y similares. Otra estrategia simple es la b´ usqueda aleatoria. Esto es, probar con candidatos seleccionados al azar. Muchos m´etodos son simplemente mejoras sobre la b´ usqueda aleatoria aunque pueden llegar a ser muy sofisticadas y obtener unos resultados mucho mejores. Entre ellos se encuentran todos los M´etodos Bioinspirados. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
21/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
22/87
Algoritmos Bioinspirados[Varios, a]. Descripci´on. Replican la forma en que la naturaleza se enfrenta a problema de optimizaci´on. Principalmente se trata de emular la evoluci´on natural de las especies y la respuesta de los sistemas sociales ante desaf´ıos.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
23/87
Algoritmos Bioinspirados. Problemas a los que se aplica I.
Dise˜ no de rutas de escape y t´acticas militares. Dise˜ no de estructuras como: alas de un avi´ on, salas de concierto, antenas de telecomunicaciones, gr´ uas, . . . Dise˜ no de f´armacos, compuesto qu´ımicos y materiales. Reconocimiento de patolog´ıas en test cl´ınicos de diversos tipos.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
24/87
Algoritmos Bioinspirados. Problemas a los que se aplica II.
Predicciones sobre mercados financieros. Software de control de equipos de robots y inteligencia artificial de robots o agentes virtuales. Reconocimiento de patrones y miner´ıa de datos. Problemas matem´aticos como: regresiones simb´ olicas, resoluci´on simb´olica de ecuaciones en derivadas parciales, resoluci´on de sistemas de ecuaciones no lineales, . . .
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
25/87
Algoritmos Bioinspirados. Ventajas.
Relativamente gen´ericos y con muy pocas restricciones de uso. Ofrecen poblaciones de soluciones, no respuestas u ´nicas. Son intr´ınsecamente paralelos, lo cual los hace particularmente u ´tiles en las infraestructuras actuales. No parten de ideas preconcebidas, con lo cual sus resultados suelen ser sorprendentemente originales y muy eficientes.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
26/87
Algoritmos Bioinspirados. Desventajas.
Tiene naturaleza aleatoria. Usualmente dependen de muchos par´ametros que a´ un no se sabe optimizar de forma sistem´atica. Suelen tener problemas de convergencia prematura. Esto es, si por casualidad se encuentra una buena soluci´ on, es posible que en sucesivas iteraciones no se mejore. Para evitar esto u ´ltimo hay que garantizar la diversidad en la poblaci´on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
27/87
Partes de un Algoritmo Bioinspirado. Procedimientos a definir. Poblaci´on: Conjunto de candidatos a ser soluci´ on que pueden o no cumplir las restricciones del problema. Mecanismo de Evoluci´on: Conjunto de procedimientos por los cuales se modifica la poblaci´ on. Mecanismo de Calificaci´on: Conjunto de procedimientos por los cuales se asigna una calificaci´ on a cada elemento de la poblaci´on. Usualmente es la funci´ on a optimizar. Condiciones de Parada: Mecanismo que controla si se ha encontrado una soluci´on o n´ umero de operaciones aceptable. Usualmente, la condici´ on de parada, la poblaci´ on y el mecanismo de calificaci´on vienen determinados por el problema a resolver. Sin embargo, el mecanismo de evoluci´ on es caracter´ıstico de cada m´etodo. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
28/87
Pseudoc´odigo de un Algoritmo Bioinspirado. Input Crear Poblaciones Calificar Poblaciones generaciones
Output
Mientras no Fin Reemplazar Poblaciones
Validar Resultado Cruzo o Muto Individuos
Calificar Nueva Poblaci´ on
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
29/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
30/87
Enjambres de Part´ıculas[Varios, h]. Descripci´on. Se genera un enjambre de candidatos que van recorriendo el espacio de b´ usqueda. Cada candidato guarda el historial de soluciones encontradas y puede intercambiar informaci´ on con otros candidatos pr´oximos. El mecanismo de memoria esta relacionado con la calificaci´on de las soluciones encontradas mientras que el movimiento de las part´ıculas con el de evoluci´on. Se inspira en el comportamiento social de las colonias de hormigas, abejas, etc. a la hora de buscar comida as´ı como con el sistema inmunol´ogico cuando fabrica anticuerpos.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
31/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
32/87
Algoritmos Evolutivos[Varios, c]. Se genera una poblaci´ on inicial aleatoria. Esta poblaci´on se modifica usando los operadores gen´eticos: Selecci´on: Selecciona individuos de la poblaci´ on. Cruce: Generan dos individuos nuevos a partir de otros dos al intercambiar sus componentes. Mutaci´on: Modifica un individuo para crear otro nuevo. Reemplazamiento: Seleccionan los individuos que pasar´an a la siguiente generaci´ on. Est´a basado en la evoluci´ on natural de las especies, la gen´etica y la epigen´etica.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
33/87
Algoritmos Evolutivos.
Cruce vs. Mutaci´on. Usualmente, el cruce realiza una funci´ on de b´ usqueda local explotando las mejores propiedades de cada elemento. Sin embargo, la mutaci´ on explora todo el espacio de b´ usqueda evitando la convergencia prematura hacia m´ınimos locales. Suponiendo que guardamos el mejor elemento de la poblaci´on, el operador de mutaci´on nos garantiza que encontraremos la mejor soluci´on siempre y cuando permitamos realizar un n´ umero suficientemente grande de iteraciones.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
34/87
Algoritmos Evolutivos.
Selecci´on y Reemplazamiento. El operador de selecci´ on debe asegurar un balance entre los favorecer operar sobre los mejores elementos y permitir las operaciones entre los peores. El operador de re emplazamiento se encarga de mantener la biodiversidad en la poblaci´ on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
35/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
36/87
Programaci´ on Gen´ etica[Varios, d].
Descripci´on. En este caso los individuos de la poblaci´ on a evolucionar por un algoritmo gen´eticos est´an fijados de antemano. Usaremos programas inform´aticos. La idea es construir un programa que resuelva el problema, no buscar una soluci´on ´optima. La estructura natural que se evoluciona son ´arboles de instrucciones. Nosotros usamos una estructura mucho m´as general y eficiente: grafos dirigidos ac´ıclicos[Alonso et al., 2009b]a . a
En adelante slp
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
37/87
´ Arbol vs slp’s I. Ejemplo. Representaci´on como ´arbol (a la derecha) y como slp (a la izquierda) de un programa que calcula la funci´ on f1 = x4 + x3 + x2 + x. f1 ≡
f1 ≡
+
∗ ∗
+ ∗
+ +
+ +
∗
∗
∗ ∗
∗
∗
x Figura: slp.
x ´ Figura: Arbol. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
38/87
´ Arboles vs slp’s II.
Diferencias apreciables en el ejemplo anterior. Los ´arboles generalmente contienen m´as nodos pero son estructuras cuya ejecuci´on se puede paralelizar. Por contra, los slp suelen ser m´as compactos pero pierden la estructura que hace posible paralelizar su ejecuci´ on. Esto NO es un problema puesto que al ser una estructura mucho m´as compacta conseguimos resolver dos grandes problemas a la vez: 1
2
Evaluamos muchos menos nodos gastando muchos menos recursos (tanto en tiempo como en espacio). Reducimos la cantidad de informaci´ on que se debe obtener en la fase de aprendizaje.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
39/87
Ejecuci´on. La ejecuci´on de este tipo de programas es bastante simple. S´olo hay que tener en cuenta que estas estructuras se codifican como una lista de operaciones. Simplemente hay que ejecutar todos los comandos de la lista consecutivamente y ya hemos finalizado. u1 := x ∗ x u 2 := x ∗ x u1 := x ∗ x u3 := u1 ∗ u2 u2 := u1 ∗ u1 u4 := x ∗ x u3 := u1 ∗ x u5 := u4 ∗ x f1 ≡ f1 ≡ u 4 := u3 + x u6 := x ∗ x u := u4 + u1 5 u := u6 + x 7 u6 := u5 + u4 u := u5 + u3 8 Figura: slp. u9 := u8 ∗ u7 ´ Figura: Arbol. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
40/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
41/87
Algunos ejemplos de problemas.
Presentamos ahora una lista de problemas de optimizaci´on que han sido resueltos mediante M´etodos Bioinspirados. En general han mostrado un desempe˜ no igual o superior a las t´ecnicas cl´asicas. En muchos casos han podido abordar problemas imposibles con otros m´etodos. En muchos casos los resultados obtenidos se han llevado a la pr´actica con muy buenos resultados.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
42/87
Antenas de Telecomunicaciones I. Problema. (Dise˜no de una antena de Telecomunicaciones.) Construir una antena de comunicaciones con las siguientes restricciones: Rendimiento m´ınimo determinado a priori. 7 alambres interconectados. Volumen m´aximo determinado a priori.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
43/87
Antenas de Telecomunicaciones II.
Resultados[Altshuler and Linden, 1997]. “El resultado no se parece a las antenas tradicionales y carece de una simetr´ıa obvia, como inusualmente extra˜ na y anti-intuitiva, aunque ten´ıa un patr´ on de radiaci´ on casi uniforme y con un gran ancho de banda tanto en la simulaci´ on como en la prueba experimental’.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
44/87
FPGA’s I.
Problema. (Reconocimiento de Voz.) Construir una placa FPGA que: Reconozca las palabras go y stop. Circuito m´as peque˜ no posible.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
45/87
FPGA’s II.
Resultados[Davidson, 1997]. “El resultado fue un circuito reconocedor de voz utilizando s´olo 37 puertas l´ogicas de las cuales cinco de ellas ni siquiera est´an conectadas al resto del circuito aunque si se les retira la alimentaci´on el´ectrica, el circuito deja de funcionar. El funcionamiento exacto de la compleja e intrincada estructura es un misterio”.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
46/87
Salas de Conciertos I. Problema. (Dise˜no de una sala de conciertos.) Construir sala de conciertos que maximice la calidad del sonido simult´aneamente para: La audiencia. El director. Los m´ usicos.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
47/87
Salas de Conciertos II.
Resultados[Sato et al., 2002]. “El resultado fueron dos soluciones no dominadas, ambas descritas como con forma de hoja que tienen proporciones similares al Grosser Musikvereinsaal de Viena, el cual est´a considerado generalmente como una de las mejores salas de conciertos”.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
48/87
Alas de Aviones I. Problema. (Dise˜no de alas de aviones.) Dise˜ nar el ala de un avi´on supers´ onico que simult´aneamente minimice: La resistencia a velocidades subs´ onicas. La resistencia a velocidades supers´ onicas. La carga aerodin´amica. Minimizar el momento de torsi´ on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
49/87
Alas de Aviones II.
Resultados[Obayashi et al., 2000]. “Los resultados fueron seis dise˜ nos en ala flecha, con valores de resistencia y carga aproximadamente iguales o menores a los del ala dise˜ nada por humanos. En particular, una de las soluciones super´o al dise˜ no humano en todos los objetivos”.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
50/87
´ Orbitas de Sat´elites I. Problema. (Planificar las o´rbitas de una constelaci´on de sat´elites.) Planificar las ´orbitas de una constelaci´ on de sat´elites en ´orbita baja que: Minimice el tiempo muerto medio para todos los receptores. Minimice el tiempo muerto m´aximo para cada receptor. Minimice el n´ umero de sat´elites.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
51/87
´ Orbitas de Sat´elites II.
Resultados[Williams et al., 2001]. “El resultado fueron configuraciones orbitales muy asim´etricas, con los sat´elites colocados alternando huecos grandes y peque˜ nos, en lugar de huecos de igual tama˜ no como habr´ıan hecho las t´ecnicas convencionales. Sin embargo, esta soluci´on redujo significativamente los tiempos medio y m´aximo de apag´on, en algunos casos hasta en 90 minutos”.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
52/87
T´acticas Militares I. Problema. (Dise˜no de planes t´acticos militares.) Planificar una operaci´on militar que: Sea generada r´apidamente. Minimice las bajas amigas. Maximice las bajas enemigas. Mejorar el control del terreno conquistado. Minimizar el gasto de recursos. Minimizar los da˜ nos colaterales.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
53/87
T´acticas Militares II.
Resultados[Kewley and Embrechts, 2002]. “Los resultados superaron los planes de expertos militares. Ten´ıa sentido t´actico y propiedades emergentes. Adem´as, al no sufrir presi´on, pueden tomar decisiones acertadas en periodos estresantes’.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
54/87
Planificador de Rutas I. Problema. (Rutas en redes de telecomunicaciones.) Hallar la ruta de un paquete en una red de telecomunicaciones que: Minimice el tiempo de respuesta. Minimice el n´ umero de saltos. Tenga en cuenta la congesti´ on de la red. Tenga en cuenta los cortes de suministro.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
55/87
Planificador de Rutas II.
Resultados[He and Mort, 2000]. “El resultado era capaz de redirigir enlaces rotos o congestionados, equilibrar la carga de tr´afico y maximizar el caudal total de la red”.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
56/87
Planificador de L´ıneas de Montaje I. Problema. (Planificar la l´ınea de montaje.) Crear y gestionar en tiempo real una l´ınea de montaje que tenga en cuenta: Minimice el coste de generar una pieza. Maximice el rendimiento de la l´ınea de montaje. Se adapte a: aver´ıas, ausencias de empleados y materias primas, cambios en las prioridades de producci´ on. . .
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
57/87
Planificador de L´ıneas de Montaje II.
Resultados[Jensen, 2003]. “La planificaci´on resultante aument´ o la producci´ on mensual un 50 por ciento, el tiempo extra casi desapareci´ o. El tiempo para producir la planificaci´ on descendi´ o de cuatro d´ıas a solo uno”.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
58/87
Dise˜no de Estructuras. Problema. (Mejorar estructuras conocidas.) Algunos ejemplos: Dise˜ no molinos de e´ olicos m´as eficientes[Benini and Toffolo, 2002]. Mejora de los sistemas ABS[Lee and Zak, 2002]. Dise˜ no de motores di´esel m´as eficientes[Schechter, 2000].
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
59/87
Colocar Piezas. Problema. (Colocar Piezas en una Matriz.) Dise˜ nar un algoritmo que gestione eficientemente la colocaci´on de piezas en un tablero. Este problema es muy similar a generar un algoritmo que juegue correctamente al videojuego TetrisTM . En [Llima, ] se describe un algoritmo que en media realizar entre 20.000 y 50.000 l´ıneas.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
60/87
Miner´ıa de datos.
Problema. (Descubrir patrones en grandes conjuntos de datos.) Algunos ejemplos: Caracter´ısticas de los clientes que cambian de proveedor de alg´ un servicio[Wai Ho Au et al., 2003]. Detecci´on de objetos por sus patrones de radar[Rizki et al., 2002]. Reconocimiento ´optico de caracteres[Rizki et al., 2002]. An´alisis m´edico de im´agenes[Rizki et al., 2002]. En la secci´ on Problemas desarrollamos en m´as profundidad t´ecnicas para enfrentarse con estos problemas.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
61/87
Dos ejemplos con m´as detalle. Ahora presentamos con m´as detalle dos problemas muy complicados de resolver mediante M´etodos Cl´asicos pero que se ha demostrado emp´ıricamente que son resolubles mediante Algoritmos Bioinspirados. Regresi´ on Simb´olica.
Ecuaciones de Palabras. 1 10xy
= 001xy 01
xy 111 = y 00111xx 0x00y 01 = 1xy 0
0,5
0y 11 = yxy 01 xx100y x?
= 001x0y ,
y?
C.E. Borges, J.L. Monta˜ na
0 0
0,5
Universidad de Cantabria
1 62/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
63/87
Un ejemplo: Sistemas de ecuaciones de palabras[Alonso et al., 2004]. Problema. Dado dos patrones que contengan s´ımbolos fijos y valores variables, encontrar una asignaci´on de s´ımbolos a las variables que haga iguales a ambos patrones.
Ejemplo. Encontrar x, y en el conjunto de palabras sobre el alfabeto {0, 1} que satisfaga la siguiente ecuaci´ on: x01y = 0yxy . Una soluci´on podr´ıa ser: x = 01, y = 1 En nuestro caso buscaremos soluciones acotadas. Es decir, que el n´ umero de s´ımbolos sea menor o igual a d, una cota dada a priori. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
64/87
Sistemas de ecuaciones de palabras. ¿Por qu´e es importante?
Aplicaciones en: Teor´ıa de la Unificaci´ on (Prolog 3). Pattern-Matching. Dise˜ no y verificaci´on de circuitos el´ectricos.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
65/87
Sistemas de ecuaciones de palabras. ¿C´ omo obtenemos una soluci´ on? I
Usaremos un Algoritmo Evolutivo H´ıbrido. 1
Generamos una poblaci´ on de candidatos a soluci´ on de forma aleatoria. Como la longitud de la soluciones est´a acotada, completamos la longitud de estos candidatos con el s´ımbolo ε que denota el s´ımbolo vac´ıo.
2
La funci´on de calificaci´ on ser´a la suma de la cantidad de s´ımbolos distintos en cada ecuaci´ on del sistema teniendo en cuenta que si una palabra es mayor que la otra, cada s´ımbolo de m´as representa un error.
3
La selecci´on se realizar´a mediante el m´etodo de la ruleta. Es decir, tendr´an m´as probabilidad de cruzar o mutar los candidatos con mejor calificaci´on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
66/87
Sistemas de ecuaciones de palabras. ¿C´ omo obtenemos una soluci´ on? II 4
La selecci´on se realizar´a mediante el m´etodo de la ruleta. Es decir, tendr´an m´as probabilidad de cruzar o mutar los candidatos con mejor calificaci´on. ind2
ind3
12 % 10 %
ind1 17 %
45 %
16 % ind5
ind4 C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
67/87
Sistemas de ecuaciones de palabras. ¿C´ omo obtenemos una soluci´ on? III 5
La operaci´on de mutaci´ on cambia, con probabilidad 1/d, cada uno de los s´ımbolos. padre = 00000εε =⇒ hijo = 0110εεε
6
La operaci´on de cruce intercambia, con probabilidad 1/2 cada uno de los s´ımbolos del padre de menor longitud. Luego completa con algunos s´ımbolos del otro padre.
padre1 = 01εεεεε
hijo1 = 11 + 00 + εεε = 1100εεε =⇒
padre2 = 100011ε C.E. Borges, J.L. Monta˜ na
hijo2 = 00 + 0011 + ε = 000011ε Universidad de Cantabria
68/87
Sistemas de ecuaciones de palabras. ¿C´ omo obtenemos una soluci´ on? IV 7
Los operadores de cruce y mutaci´ on tienen en cuenta que los s´ımbolos ε siempre se encuentran al final de la palabra.
8
Despu´es de realizar un cruce o una mutaci´ on realizaremos una b´ usqueda local con el fin de encontrar mejoras en la calificaci´on del candidato.
9
Finalmente, la condici´ on de parada ser´a encontrar una soluci´on o realizar un n´ umero prefijado de iteraciones.
0010εεε 00100εε 0000εεε ⇒ 0010εεε si mejora calificaci´ on probar con 00101εε 001εεεε C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
69/87
Sistemas de ecuaciones de palabras. Resultados
Conclusiones. Realizar s´olo la b´ usqueda local o s´ olo el algoritmo evolutivo es peora que realizar ambos. De hecho, en problemas en el que el espacio de b´ usqueda es muy grande las diferencias son dram´aticas[Alonso et al., 2004]. Los mejores par´ametros parecen ser tener una poblaci´on muy peque˜ na junto con una probabilidad de mutaci´ on muy grande. Sin embargo, NO se puede eliminar el cruce, pues en ese caso se observa un comportamiento similar a la b´ usqueda local pura[Alonso et al., 2004]. Estos resultados son coherentes con los obtenidos para otros problemas similares, por ejemplo 3SAT [Alonso et al., 2004]. a
Entendemos por peor que la probabilidad emp´ırica de encontrar una soluci´ on es menor.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
70/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
71/87
Un ejemplo: Regresi´ on Simb´ olica[Alonso et al., 2009b]. Problema. Dada una muestra de puntos encontrar la funci´ on que mejor los aproxima dentro de un conjunto de funciones dado. x4 + x3 + x2 + x 1
0,5
0 0 C.E. Borges, J.L. Monta˜ na
0,5 Universidad de Cantabria
1 72/87
Un ejemplo: Regresi´ on Simb´ olica.
Ejemplo. La interpolaci´on y el m´etodo de m´ınimos cuadrados son dos aproximaciones muy restrictivas a este problema pues solo tratan con polinomiosa . El m´etodo que proponemos nos permite buscar con pr´acticamente cualquier familia de funciones. a Para ser m´ as precisos lo que requieren estos m´ etodos es que el espacio de funciones sea un espacio vectorial de dimensi´ on finita.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
73/87
Regresi´ on Simb´ olica. ¿Por qu´e es importante?
Este es uno de los problemas fundamentales en la teor´ıa del aprendizaje tanto autom´atica como natural. Es dif´ıcil pensar en alguna rama de la ciencia aplicada que no tenga que resolver alg´ un problema de esta ´ındole. Citamos a continuaci´on algunos ejemplos: Predicciones en cualquier tipo de serie temporal. Predicciones epidemiol´ ogicas. Estimaciones de tendencias. En general, es el problema t´ıpico cuando se tiene gran cantidad de datos de ´ındole num´erico que se sospecha que siguen alguna regla. Hay que tener en cuenta que este problema est´a muy relacionado con el problema de clasificaci´on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
74/87
Regresi´ on Simb´ olica. ¿C´ omo obtenemos una soluci´ on? I
Usaremos Programaci´on Gen´etica con operador epigen´etico. 1
La poblaci´on estar´a compuesta de programas que generar´an la funci´on que mejor aproxima la muestra.
2
Estos programas los representamos mediante ´arboles o slp.
3
La calificaci´on es la composici´ on del error cuadr´atico medio con una penalizaci´on para evitar el sobre ajuste a la muestra. Esta penalizaci´on se basa en la capacidad de clasificaci´on de la estructura de datos[Monta˜ na et al., 2009b].
4
No se realiza selecci´ on de candidatos. Simplemente se itera a lo largo de la poblaci´on y se realiza el operador gen´etico correspondiente.
5
Mediante estas dos t´ecnicas conseguimos mantener la diversidad en la poblaci´on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
75/87
Regresi´ on Simb´ olica. ¿C´ omo obtenemos una soluci´ on? II 6
El cruce intercambiar´a sub´arboles (subgrafos, respectivamente). padre2 ≡ +
padre1 ≡ + +
+ ∗
∗
∗
∗ ∗
+
+
∗
∗
hijo2 ≡
+
+
+
∗
∗
∗
x
x
hijo1 ≡
∗ ∗
∗
+
+ ∗
x
+
∗ ∗
∗ ∗
∗
∗
∗ ∗
∗
∗
x
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
76/87
Regresi´ on Simb´ olica. ¿C´ omo obtenemos una soluci´ on? III
7
Mientras que el operador de mutaci´ on simplemente modificar´a un nodo o uno de los enlaces. padre ≡
hijo ≡
+ +
+ ∗
−
+
∗
∗ ∗
∗
∗
∗
∗
∗ ∗
x
C.E. Borges, J.L. Monta˜ na
+
∗
∗
x
Universidad de Cantabria
77/87
Regresi´ on Simb´ olica. ¿C´ omo obtenemos una soluci´ on? IV
8
El operador de reemplazo elegir´a el mejor elemento, en el caso de la mutaci´ on, o los dos mejores elementos (distintosa ) en el caso del cruce.
9
En este caso usamos un Operador Elitista que se encarga de guardar entre generaciones el mejor individuo de la poblaci´on.
10
En ciertos momentos de la evoluci´ on entrar´a en juego el Operador Epigen´etico que ajustar´a los valores num´ericos de las constantes presentes en la estructura de datos.
11
Finalmente, la condici´ on de parada ser´a encontrar una soluci´on o realizar un n´ umero prefijado de iteraciones.
a
Por distintos entendemos que tengan distinta calificaci´ on.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
78/87
Regresi´ on Simb´ olica. Resultados
Conclusiones. Usar slp como codificaci´ on de los programas conduce a mejores soluciones usando menos recursos[Alonso et al., 2009b]. El hecho de penalizar la calificaci´ on da lugar a mejores soluciones tanto cuando la muestra presenta ruido como en el caso contrario[Monta˜ na et al., 2009b]. Nuestra manera de penalizar la calificaci´ on obtienen resultados mucho mejores que las estrategias cl´asicas de penalizaci´on[Monta˜ na et al., 2009a]. El uso del operador epigen´etico da lugar a mejoras sustanciales en la calidad de las soluciones usando el mismo n´ umero de operaciones[Alonso et al., 2009a].
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
79/87
´Indice 1
Problemas de optimizaci´ on.
2
M´etodos Anal´ıticos. Multiplicadores de Lagrange. Descenso de Gradiente. Programaci´on Lineal.
3
M´etodos Combinatorios. M´etodos Bioinspirados. Programaci´on Gen´etica.
4
Problemas. Sistemas de Ecuaciones de Palabras. Regresi´on Simb´olica.
5
Bibliograf´ıa. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
80/87
Alonso, C., Drubi, F., and Monta˜ na, J. (2004). An Evolutionary Algorithm for Solving Word Equation Systems. In Current Topics in Artificial Intelligence, 10th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2003, and 5th Conference on Technology Transfer, TTIA 2003, San Sebastian, Spain, November 12-14, 2003. Revised Selected Papers, volume 3040 of Lecture Notes in Computer Science. Springer. Alonso, C., Monta˜ na, J., and Borges, C. (2009a). Evolution Strategies for Constants Optimization in Genetic Programming. In ICTAI 2009: 21st IEEE International Conference on Tools with Artificial Intelligence, pages 702–707. IEEE Computer Society. Alonso, C., Monta˜ na, J., Puente, J., and Borges, C. (2009b). A New Linear Genetic Programming Aproach Based on Straight Line Programs: Some Theoretical and Exeperimental Aspects. International Journal on Artificial Intelligence Tools, 18(5):757–781. Altshuler, E. and Linden, D. (1997). C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
81/87
Design of a Wire Antenna Using a Genetic Algorithm. Journal of Electronic Defense, pages 50–52. Benini, E. and Toffolo, A. (2002). Optimal Design of Horizontal-axis Wind Turbines Using Blade-element Theory and Evolutionary Computation. Journal of Solar Energy Engineering, pages 357–363. Davidson, C. (1997). Creatures from Primordial Silicon. New Scientist, pages 30–35. He, L. and Mort, N. (2000). Hybrid Genetic Algorithms for Telecommunications Network Back-up Routeing. BT Technology Journal, pages 42–50. Jensen, M. (2003). Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms. IEEE Transactions on Evolutionary Computation, pages 275–288. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
82/87
Kewley, R. and Embrechts, M. (2002). Computational Military Tactical Planning System. IEEE Transactions on Systems, Man and Cybernetics, Part C Applications and Reviews, pages 161–171. Lee, Y. and Zak, S. (2002). Designing a Genetic Neural Fuzzy Antilock-brake-system Controller. IEEE Transactions on Evolutionary Computation, pages 198–211. Llima, R. Xtris Readme. http://www.iagora.com/espel/xtris/README. Monta˜ na, J., Alonso, C., and Borges, C. (2009a). Learning GP-trees from Noisy Data. Manuscript. Monta˜ na, J., Alonso, C., Borges, C., and Crespo, J. (2009b). Adaptation, Performance and Vapnik-Chervonenkis Dimension of Straight Line Programs. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
83/87
In Genetic Programming, 12th European Conference, EuroGP 2009, T¨ ubingen, Germany, April 15-17, 2009, Proceedings, volume 5481 of Lecture Notes in Computer Science, pages 315–326. EuroGP, Springer. Obayashi, S., Sasaki, D., Takeguchi, Y., and Naoki, H. (2000). Multiobjective Evolutionary Computation for Supersonic Wing-shape Optimization. IEEE Transactions on Evolutionary Computation, pages 182–187. Rizki, M., Zmuda, M., and Tamburino, L. (2002). Evolving Pattern Recognition Systems. IEEE Transactions on Evolutionary Computation, pages 594–609. Sato, S., Otori, K., Takizawa, A., Sakai, H., Ando, Y., and Kawamura, H. (2002). Applying Genetic Algorithms to the Optimum Design of a Concert Hall. Journal of Sound and Vibration, pages 517–526. Schechter, B. (19 de septiembre de 2000). Putting a Darwinian Spin on the Diesel Engine. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
84/87
The New York Times, page F3. Varios. Biologically Inspired Computing. http: //en.wikipedia.org/wiki/Biologically_inspired_computing. Varios. Combinatorial Optimization. http://en.wikipedia.org/wiki/Combinatorial_optimization. Varios. Evolutionary Algorithm. http://en.wikipedia.org/wiki/Evolutionary_algorithm. Varios. Genetic Programming. http://en.wikipedia.org/wiki/Genetic_programming. Varios. Gradient Descent. C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
85/87
http://en.wikipedia.org/wiki/Gradient_descent. Varios. Lagrange Multipliers. http://en.wikipedia.org/wiki/Lagrange_multipliers. Varios. Linear Programming. http://en.wikipedia.org/wiki/Linear_programming. Varios. Particle Swarm Optimization. http: //en.wikipedia.org/wiki/Particle_swarm_optimization. Wai Ho Au, Chan, K., and Xin Yao (2003). A Novel Evolutionary Data Mining Algorithm with Applications to Churn Prediction. IEEE Transactions on Evolutionary Computation, pages 532–545. Williams, E., Crossley, W., and Lang, T. (2001). C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
86/87
Average and Maximum Revisit Time Trade Studies for Satellite Constellations Using a Multiobjective Genetic Algorithm. Journal of the Astronautical Sciences, pages 385–400.
C.E. Borges, J.L. Monta˜ na
Universidad de Cantabria
87/87
