Investigaciones del proyecto
TRACER
Universidad Carlos III de Madrid
Investigadores:
Pedro Isasi Viñuela
Julio César Hernández
Cristóbal Luque del Arco-Calderón
José María Valls
Líneas de Investigación



Distribución de cargas en una esfera
mediante estrategias evolutivas.
Predicciones de la marea mediante
algoritmos genéticos.
Búsqueda de funciones HASH
mediante programación genética.
Distribución de cargas en una
esfera
Introducción:



Problema: distribuir N cargas iguales en
la superficie de una esfera.
Las cargas tienden a repelerse hasta
quedar en una posición de equilibrio.
El problema se conoce en física como
“el problema de Thomson”.
Ejemplos
Métodos para el cálculo:




Clásico: descenso del gradiente.
Simulated annealing.
Algoritmos genéticos.
El descenso de gradiente puede quedar
atrapado en mínimos locales.
Aplicaciones






Este problema clásico tiene aplicaciones en física,
química y biología.
Cristalización de iones o "bubblons" cerca de la superficie
de un aglomerado de helio líquido.
Cristalización de electrones en el contorno de un punto
semiconductor esférico.
Cálculo de poliedros regulares.
Búsqueda de moleculas estables.
Analisis del entrelazado de los granos de polen y las
cadenas de ADN .
Dificultades del problema



Numerosos mínimos locales.
El número de mínimos locales aumenta
exponencialmente con el número de
electrones.
Para N ~ 200 electrones hay alrededor
de 8000 mínimos locales.
Preliminares

Usaremos estrategias evolutivas de tipo
(+), es decir,  padres producen  
 hijos, y entre la población total de
+ individuos se seleccionan los 
mejores, que pasan a ser los padres de
la siguiente generación.
Preliminares

La función fitness será el potencial electrostático:
» f(N)= i<j 1/d(xi,xj)

Esquema estándar:
inicializar();
while condicion
{
engendrar();
evaluar();
generación+ + ;
}
Preliminares




inicializar() da los valores iniciales.
engendrar() produce los  hijos a partir de los 
padres mediante mutación.
evaluar() selecciona los  mejores individuos de la
población de padres e hijos.
La condición de parada puede ser, o bien un número
determinado de generaciones, o bien que la función
fitness no haya variado en las últimas 5000
generaciones.
Método I

Para la primera implementación los padres
portan las coordenadas de los electrones en
polares:
typ ed ef stru ct
{
rea l x,y,ex,ey;
}T electro n ;
typ ed ef stru ct {
rea l fitn ess;
T electro n electro n [n _ e] ;
}T p a d re;
Método I




Declaramos un vector de  elementos de tipo
Tpadre.
El tipo real puede ser tanto double, como long
double, dependiendo de la precisión que queramos.
La constante n_e es el número de electrones.
Cada electrón lleva su posición en coordenadas
polares (x,y), además de las varianzas de la
mutación (ex para la coordenada x, ey para la
coordenada y).
Método I

Así pues la mutación (observemos que no sólo
mutan las coordenadas polares, también mutan las
varianzas) seguirá las siguientes distribuciones
normales:
x’ = N (x,ex )
y’ = N (y,ey )
ex’ = N (ex,1 )
ey’ = N (ey,1 )
Método II

Para hacer el algoritmo más eficiente se pensó en
reducir la cantidad de memoria que ocupaba cada
padre, y para ello se extrajeron las varianzas de cada
electrón para hacer una única común a todos los
electrones de cada padre.
typ ed ef stru ct {
rea l x,y;
}T electro n ;
typ ed ef stru ct {
rea l fitn ess;
T electro n electro n [n _ e] ;
rea l ex,ey;
}T p a d re
Método II



Ahora el tipo Tpadre ocuparía la mitad de lo que ocupaba
anteriormente.
El algoritmo saldría perjudicado en cuanto a que,
teóricamente, un electrón bien colocado en una
generación podría no estarlo en la siguiente por ser la
varianza igual para todos; así pues no distingue entre los
mejor colocados para la configuración mínima
Sin embargo según los resultados al final de la memoria
podemos ver que el segundo método produce mejores
resultados, en contra de lo que la intuición nos dice.
Método III

Para la posición del electrón, en este método
trabajaremos con las tres coordenadas cartesianas
(x,y,z), en vez de las dos polares (,).
x = co s  co s 
y = sen  co s 
z = sen 
Método III

La nueva implementación será:
typedef struct {
real x,y,z;
}T electron;
typedef struct {
real fitness;
T electron electron[n_e];
real e;
}T padre;
Método III


Al igual que en el caso anterior, seguimos
manteniendo una sola varianza para todos
los electrones del mismo padre.
El proceso de mutación usado es:
x’ =
y’ =
z’ =
e’ =
N (x,e )
N (y,e )
N (z,e)
N (e,1 )
Método III


Tras llevar a cabo algunas pruebas, se
comprobó que, efectivamente, esta nueva
implementación era más rápida.
Aunque el algoritmo había ganado cierta
rapidez seguía siendo lento para casos de
mas de 50 electrones, y ello era debido a
que la función fitness dependía al
cuadrado del numero de electrones.
Método III

Para cada electrón debe evaluar N2/2
distancias:
f(N )=  i< j 1/d(x i,x j)
d(x 1 ,x 2 ), d(x 1 ,x 3 ), d(x 1 ,x 4 ), ... , d(x 1 ,x N -1 ), d(x 1 ,x N )
d(x 2 ,x 3 ), d(x 2 ,x 4 ), ..., d(x 2 ,x N -1 ), d(x 2 ,x N )
d(x 3 ,x 4 ), ..., d(x 3 ,x N -1 ), d(x 3 ,x N )
...
d(x N -2 ,x N -1 ), d(x N -2 ,x N )
d(x N -1 ,x N )
Método IV




Para la nueva implementación los padres mantienen
la información sobre la inversa de las distancias
entre los electrones.
Muta un solo electrón de cada padre en el hijo.
A la hora de calcular el fitness del hijo sólo
tendríemos que recalcular las inversas de las
distancias del electrón mutado con los demás,
permaneciendo sin variar las inversas de las
distancias entre los electrones no mutados.
Ahora sólo hay que evaluar N-1 distancias en vez de
N2/2.
Método IV

La nueva implementación será:
typedef struct {
real x,y,z,e;
}T electron;
typedef struct {
real fitness;
T electron electron[n_e];
real inv_d[n_e][n_e];
int ind;
}T padre;
Método IV

En la tabla inv_d[n_e][n_e] guarda las
inversas de las distancias de los
electrones.
inv_d[i] [j] = 1/ d(x i,x i), con i > j
Método IV



El indicador ind señala cual es el electrón
que muta.
Este indicador pasa sin variar al hijo con una
probabilidad del 90%; el 10% restante muta y
pasa a señalar a otro electrón
aleatoriamente.
Así, por una parte busca la mejor posición
para ese electrón, y aleatoriamente pasa a
buscar otro que colocar mejor, en vez de
seguir explotando esa solución.
Método IV


La ventaja de este método es su
velocidad, siendo mucho más rápido
que todos los anteriores.
La desventaja es que tiene más
posibilidades de quedar atascado en un
mínimo local.
8 electro nes, 1 0 0 00 generacio nes, 5 p ad res y
5 hijo s
4 7 electro nes, 1 0 00 0 generacio nes, 1 p ad re y
1 hijo
M éto d o
F itne ss
T iem p o
(seg und o s)
M éto d o
F itne ss
T iem p o
(seg und o s)
I
I
I
I
I
1 9 .6 75 2 91 3 24 5
1 9 .6 75 2 91 4 57 5
1 9 .6 75 2 99 3 07 0
1 9 .6 75 4 35 7 56 5
1 9 .6 79 7 71 3 54 3
1 2 .3 62 6 37
1 2 .0 32 9 67
1 1 .9 78 0 22
1 2 .0 87 9 12
1 2 .1 42 8 57
I
I
I
I
I
9 7 3 .19 7 38 3 99 1 1
9 7 4 .97 9 77 1 46 2 7
9 7 6 .86 5 22 2 21 3 4
9 8 1 .35 3 31 9 12 2 3
9 8 1 .82 0 80 4 18 9 3
4 9 .5 60 4 40
4 8 .1 86 8 13
4 9 .2 85 7 14
4 8 .2 96 7 03
4 9 .1 20 8 79
II
II
II
II
II
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 6
1 9 .6 75 2 87 8 80 0
1 9 .7 00 9 29 8 91 0
2 0 .2 26 5 76 9 41 5
8 .6 8 13 1 9
8 .6 8 13 1 9
8 .5 7 14 2 9
8 .4 6 15 3 8
8 .3 5 16 4 8
II
II
II
II
II
9 2 7 .54 3 92 1 50 9 6
9 2 8 .07 7 99 3 46 6 7
9 2 8 .10 3 36 3 77 2 1
9 2 8 .21 5 68 3 68 5 3
9 2 8 .71 1 71 9 52 7 9
4 9 .6 70 3 30
4 9 .6 70 3 30
4 9 .7 25 2 75
4 8 .3 51 6 48
5 0 .0 00 0 00
III
III
III
III
III
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
7 .6 3 73 6 3
7 .5 2 74 7 3
7 .5 2 74 7 3
7 .7 4 72 5 3
7 .6 9 23 0 8
III
III
III
III
III
9 2 8 .31 7 49 1 66 9 5
9 2 8 .56 8 99 1 31 2 6
9 2 8 .61 8 43 5 52 6 1
9 2 8 .86 2 29 1 41 4 3
9 3 0 .01 6 22 0 27 0 9
2 8 .4 06 5 93
2 8 .2 96 7 03
2 7 .8 02 1 98
2 8 .6 81 3 19
2 7 .9 67 0 33
IV
IV
IV
IV
IV
1 9 .6 76 6 10 0 03 1
1 9 .6 79 1 42 6 37 5
1 9 .6 80 0 67 4 62 9
1 9 .6 82 0 20 3 18 7
1 9 .6 95 3 51 9 32 9
2 .2 5 27 4 7
2 .0 8 79 1 2
2 .1 9 78 0 2
2 .1 9 78 0 2
2 .0 8 79 1 2
IV
IV
IV
IV
IV
9 3 0 .42 0 23 9 47 2 3
9 3 1 .74 9 90 7 75 1 5
9 3 2 .17 4 74 4 21 3 3
9 3 2 .22 1 97 5 32 2 6
9 3 3 .59 0 30 3 28 3 4
3 .6 8 13 1 9
3 .6 2 63 7 4
3 .7 9 12 0 9
3 .5 7 14 2 9
3 .6 2 63 7 4
1 0 0 electro nes,
p ad res y 1 0 hijo s
1 00 0 0
generacio nes,
10
M éto d o
F itne ss
T iem p o
(seg und o s)
I
I
I
I
I
4 6 4 3 .1 8 33 1 32 4 90
4 6 4 7 .9 4 26 8 90 0 93
4 6 6 1 .1 7 28 2 04 1 85
4 6 8 1 .3 0 37 7 23 8 16
4 6 8 5 .7 3 38 3 67 1 98
2 8 2 9 .4 4 00 0 0
2 2 8 6 .0 0 00 0 0
2 2 8 7 .0 4 00 0 0
2 2 6 9 .2 5 00 0 0
2 2 6 3 .2 6 00 0 0
II
II
II
II
II
4 4 4 9 .3 8 78 0 48 3 53
4 4 4 9 .6 7 30 8 62 7 07
4 4 5 0 .1 5 89 1 41 1 28
4 4 5 0 .2 4 35 0 19 3 93
4 4 5 0 .2 6 76 0 95 0 84
2 3 0 6 .1 5 00 0 0
2 3 0 6 .6 0 00 0 0
2 3 0 8 .3 5 00 0 0
2 3 0 7 .1 5 00 0 0
2 3 1 1 .3 7 00 0 0
III
III
III
III
III
4 4 4 9 .4 5 52 3 16 5 33
4 4 4 9 .6 5 83 1 87 2 98
4 4 4 9 .9 0 76 5 68 5 16
4 4 4 9 .9 5 17 0 13 6 83
4 4 4 9 .9 8 20 3 78 0 41
1 5 1 7 .7 5 00 0 0
1 5 1 7 .2 0 00 0 0
1 5 1 2 .4 3 00 0 0
1 5 1 5 .9 4 00 0 0
1 5 0 9 .9 0 00 0 0
IV
IV
IV
IV
IV
4 4 5 8 .2 0 06 5 57 8 01
4 4 5 9 .0 0 92 0 23 9 84
4 4 5 9 .1 9 35 6 07 2 46
4 4 6 0 .2 6 60 3 05 0 58
4 4 6 1 .0 3 09 1 03 0 91
1 4 6 6 .8 9 00 0 0
1 4 5 4 .8 7 00 0 0
1 4 5 7 .5 0 00 0 0
1 4 4 6 .9 5 00 0 0
1 4 9 0 .3 5 00 0 0
8 electro nes, 1 0 0 00 generacio nes, 5 p ad res y
5 hijo s
4 7 electro nes, 1 0 00 0 generacio nes, 1 p ad re y
1 hijo
M éto d o
F itne ss
T iem p o
(seg und o s)
M éto d o
F itne ss
T iem p o
(seg und o s)
III
III
III
III
III
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
1 9 .6 75 2 87 8 61 2
7 .6 3 73 6 3
7 .5 2 74 7 3
7 .5 2 74 7 3
7 .7 4 72 5 3
7 .6 9 23 0 8
III
III
III
III
III
9 2 8 .31 7 49 1 66 9 5
9 2 8 .56 8 99 1 31 2 6
9 2 8 .61 8 43 5 52 6 1
9 2 8 .86 2 29 1 41 4 3
9 3 0 .01 6 22 0 27 0 9
2 8 .4 06 5 93
2 8 .2 96 7 03
2 7 .8 02 1 98
2 8 .6 81 3 19
2 7 .9 67 0 33
3 5 0 00 generacio nes e n el m éto d o IV
IV
IV
IV
IV
IV
1 9 .6 75 2 87 8 64 5
1 9 .6 75 5 62 5 44 4
1 9 .6 76 6 63 5 06 0
1 9 .6 77 6 19 7 32 8
1 9 .6 80 2 41 2 15 1
7 .7 4 72 5 3
7 .7 4 72 5 3
7 .3 0 76 9 2
7 .0 8 79 1 2
8 .0 2 19 7 8
7 0 0 00 generacio nes e n el m éto d o IV
IV
IV
IV
IV
IV
9 2 8 .10 9 41 6 05 6 4
9 2 8 .80 0 78 8 47 5 0
9 2 8 .89 3 22 2 26 0 4
9 2 9 .08 2 08 0 41 5 5
9 2 9 .22 2 05 8 64 3 4
2 9 .9 45 0 55
2 9 .2 85 7 14
2 8 .6 26 3 74
2 7 .8 02 1 98
2 8 .4 61 5 38
Nuevo Enfoque



Posteriormente se trató de afrontar el
problema con una estrategia (1+1).
1 padre produce 1 único hijo.
Dicho padre se sustituye sólo si el hijo
mejora el fitness del padre.
Método V

Se siguieron las los postulados de
Rechenberg: la regla de 1/5:
En una estrategia (1+1) la proporción de
descendientes que sustituyen al padre
debe ser 1/5. Si es mayor que 1/5
debemos incrementar la varianza, y si
es menor decrementarla.
Método V





Sea n el número de variables de la función:
La varianza se mantiene fija durante n generaciones
observamos la proporción de sustituciones del padre
que se han producido en las últimas 10n
generaciones
Si esta proporción es mayor que 1/5, la varianza se
multiplica por una constante de incremento ci=1/0.82
si es menor que 1/5 la varianza se multiplica por una
constante de decremento cd = 0.82
Método VI


Este último método es mucho más
sencillo.
Simplemente, cada generación
decrementa la varianza del padre
multiplicándola por 0’95, y la del hijo
se aumenta multiplicándola por 1’25.
Resultados

El método VI presenta una
convergencia más rápida.
Bibliografía






L. T. Wille, “Searching potential energy surfaces by simulated annealing”, Nature
v 324 n 6 (1984), p 46-48.
J. R. Morris, D. M. Deaven and K. M. Ho. “Genetic-algorithm energy
minimization for point charges on a sphere”. Physical Review B, 53(4): 1740-1743, 1996.
A. B. J. Kuijlaars and E. B. Saff, “Asymptotics for minimal discrete energy on the
sphere”, Trans. Amer. Math. Soc., to appear.
E. B. Saff, A. B. J. Kuijlaars, “Distributing many points on a sphere”,
Mathematical Intelligencer, v19 n1 (1997), p 5-11.
T. Erber, G. M. Hockney, “Equilibrium configurations of n equal charges on a
sphere”, J Phys A: Math, 1991
U. Depczynski and J. Stockler, “A differential geometric approach to
equidistribution on compact manifolds”, Approximation theory IX, Volume 1:
Theorical aspects 1998.
Investigadores



Pedro Isasi
Cristóbal Luque
Julio César Hernández
Resultados



Página web para el proyecto TRACER
http://tracer.lcc.uma.es/problems/thoms
on/thomson.html
Informe técnico.
Artículo aceptado para una conferencia
en la CAEPIA 2003.
Predicciones de series temporales
(mareas de Venecia) mediante
algoritmos genéticos.
Objetivo



Dada una muestra consecutiva de
horas predecir la evolución de la marea.
Clásicamente se han usado RRNN para
la predicción de series temporales.
Nosotros hemos usado técnicas de
algoritmos genéticos.
Objetivo

Datos de entrada: 24 horas
consecutivas
x1, …, x24

Salida: predicción para la hora siguiente
(X25)
Algoritmo

Nuestros individuos serán vectores de 50
elementos:
( c_sup1, c_inf1,…, c_sup24, c_inf24, predicción, error )

Este patrón nos indica que para una muestra
de 24 horas consecutivas ( h1, …, h24 ) si
para todo i se cumple que c_infi <hi< c_supi
entonces la hora siguiente será predicción
con un error aproximado de error.
Algoritmo




Seleccionamos una gran cantidad de
valores consecutivos de medidas de la
marea (30.000).
El fitness de un individuo dependerá de:
El número de veces que 24 horas
consecutivas cumplen sus cotas
(aciertos).
La varianza de las medidas de la hora 25.
Algoritmo: Fitness

Función fitness: (aciertos*10) - varianza
Objetivos:
 Maximizar los aciertos.
 Minimizar la varianza.
Algoritmo



Reproducción sexual.
Intercambio de la información.
Selección de los individuos por torneos
de tres rondas.
Algoritmo: Descendencia


Un gen de un individuo es un par de cota superior y
cota inferior para una misma hora.
Para cada hora, el hijo hereda el gen
correspondiente a esa hora de uno de los padres con
una probabilidad del 50%.
Algoritmo: Descendencia
Padre 1:
( c_sup1, c_inf1, c_sup2, c_inf2,…,c_sup24, c_inf24)

Padre 2:
( c_sup1, c_inf1, c_sup2, c_inf2,…,c_sup24, c_inf24)

Hijo:
(c_sup1, c_inf1, c_sup2, c_inf2,…, c_sup24, c_inf24)

Algoritmo: Selección



No queremos un único individuo óptimo,
buscamos una población y que cada
individuo nos haga una predicción distinta.
Steady-Stay: Un nuevo individuo sustituye
al más cercano en distancia fenotípica, es
decir, al que haga una predicción
parecida.
Sólo sustituye si mejora el fitness del más
cercano en distancia fenotípica
Resultados


Tras cada ejecución se guardan los
individuos en un fichero.
Resultado final: 3500 individuos que
predicen sobre 30.000 datos de test (es
decir, la población de individuos no ha sido
entrenada con ellos) en el 99% de los
casos con un error medio de 5 cm sobre el
nivel de la marea (entre -50 y 150 cm)
Investigadores




Pedro Isasi
Cristóbal Luque
Julio César Hernández
José María valls
Resultados

Página web para el proyecto TRACER
http://tracer.lcc.uma.es/problems/tide/tid
e.html
Búsqueda de funciones HASH
mediante programación genética
Objetivo


Efecto Avalancha: ¿Cuánto cambia la
salida cuando cambiamos un bit de la
entrada?
Crearemos funciones HASH mediante
Programación Genética y
comprobaremos su robustez mediante
el efecto Avalancha.
Algoritmo



Nuestros individuos serán árboles.
En cada nodo habrá una operación de la
lista.
El fitness del individuo se calculará
generando 1024 vectores aleatorios de 64
bits. A continuación se permuta un bit del
vector y se calcula su distancia de Hamming
entre la salida del vector original y la salida
del permutado, y luego se calcula la media.
Operaciones




rotd (rotar a la
derecha)
roti (rotar a la
izquierda)
xor (suma mod 2)
or (bit or)





not (bit not)
and (bit and)
sum (suma mod 232)
mult (multiplicación
mod 232)
kte = 0x9e377969
Ejemplo de individuo



Profundidad del árbol: 5
fitness: 11.2148
Entradas: a0, a1
(mult (kte (rotd a0))
(rotd (sum (roti (xor a0 a1))
(xor a0 a1))))
Investigadores



Julio César Hernández
Pedro Isasi
Cristóbal Luque
Resultados



Página web para el proyecto TRACER
http://tracer.lcc.uma.es/problems/avalanche/a
valanche.html
Artículo aceptado para KES 2003, que tuvo
lugar en Oxford.
Aceptado en el CEC 2003, en Camberra, y
que será publicado en la revista
Computational Intelligence de Junio de 2004.
Descargar

Distribución de electrones en una esfera mediante