Ajustando el Algoritmo al
problema
Oscar Lozano
Universidad Nacional
Temario
• Introducción
• Control de Parámetros en A. Evolutivos.
• Ilustrando el caso con un NLP
• Taxonomía de las técnicas de control.
• Posibilidades para los parámetros de control.
– Representación.
– Función de Evaluación
– Operadores de mutación y sus posibilidades.
– Operadores de cruce y sus posibilidades.
– Selección de padres.
– Población.
• Formas de combinar parámetros de control.
Introducción
• En general, todos los algoritmos son
controlados por algún conjunto de parámetros.
Ej: Simulated Annealing  Temperatura.
Cronograma de
Reduc. de la T.
Hill Climbing  Control del tamaño de la Pobla.
Tabu Search  Reglas para la memoria.
• Los algoritmos evolutivos tienen aún más
parámetros que es necesario controlar.
Introducción (2)
Se deben considerar muchas otras cosas:
•
La representación.
•
La función de evaluación.
•
Los operadores de evaluación.
•
Tamaño de la población.
•
El criterio de parada.
“Es necesario hacer un gran esfuerzo”
Introducción (3)
• El método de ensayo y error para encontrar
valores a los parámetros es una aventura
tediosa y costosa en tiempo.
• Lo ideal es que exista teoría que guie el
proceso, pero desafortunadamente la que existe
solo funciona para algunos casos específicos.
• Buscar formas automatizadas para optimizar los
parámetros.
Ej: Evolución de la evolución.
Parámetros de control en
AE(Algoritmos Evolutivos)
El reto:
Una vez tendido el puente entre el problema y
el algoritmo (Función de Evaluación).
¿Qué puede seguir?
Los operadores de variación a usar (Generar los
hijos (offspring)).
¿Mutación, y/ó, Combinación?
Si usamos combinación (CrossOver(One-Point,
Two-Point, n-point, Uniform,Arithmetic) ó
Majority Logic).
Parámetros de control en
AE(2)
¿Cuál escoger?
Escoger Majority Logic(Comparar mínimo 3).
¿Cuántos Padres tomar para decidir?
Escogemos 20 de la población para decidir.
¿Voto mayoritario o Probabilidad?
Ej: (1,0,...,0,1) (1,1,...,0,1) (0,0,...,0,1)
...... (1,0,...,1,1) (1,0,...,1,0) 20 en total.
Parámetros de control en AE
(3)
• Cualquier decisión que se tome es muy
importante.
Malas deciciones  Resultados Pobres.
• Sea cual fuere el método hay que ajustar los
parámetros al problema particular.
¿Lo que funcionó bien para otros, funcionará
bien para mi problema?
Ej: De Jong – Grefenstette – Davis
5 Problemas NLP(s).
“El espacio de configuración de parámetros
“óptimos” es necesariamente reducido”
Parámetros de control en AE
Manualmente -Experimentación
• Una alternativa de ajustar parámetros
manualmente, ó, haciendo muchas pruebas:
Confiar en el análisis matemático.
• Ajustar los parámetros manualmente esta lleno
de problemas.
Solo un parámetro a la vez (Interacción
compleja).
• Ajustarlos simultaneamente implica realizar una
gran cantidad de experimentación.
Parámetros de control en AE
Manualmente -Experimentación
Desventajas de la experimentación:
 Los parámetros no son independientes, pero
tratar de hacer todas las posibles
combinaciones es imposible.
 El proceso de ajuste de los parámetros
requiere de muchos tiempo, aún si son
optimizados uno a la vez.
 Los resultados a menudo son malos, aún
cuando se ha hecho una gran gasto de tiempo.
“Se logra, ó, se «muere» en el intento.”
Parámetros de control en AE
Analogía - teoría
• Confiar en la aparente similitud(analogía) de el
problema con otro(s).
No es muy claro como medir la similitud entre
problemas.
• Se puede confiar en una teoría que ayuda en la
escogencia de parámetros, pero en la
actualidad esas teorías son muy escasas y con
un rango muy pequeño de problemas.
Parámetros de control en AE
Cambio en el tiempo
• Los algoritmos AE son dinámicos e involucran
procesos adaptativos.
Ej: En un principio se necesitan mutaciones
muy grandes(recorrer el espacio de búsqueda),
pero pequeñas mutaciones al final para refinar
o ajustar la búsqueda.
Solución:
 Cambiar P por una función p(t), donde t es
un contador de generaciones.
Parámetros de control en AE
Usándose a sí mismo
• Una última opción es hacer uso de un AE para
ajustar el algoritmo de un problema en
particular.
 Usar alguna regla heurística.
Retroalimentación.
 Incorporar parámetros a la estructura que
representa la solución (Evolucionar los
parámetros).
Ilustrando el caso con un NLP
Ejemplo:
Optimizar f(x) = f(x1,……..,Xn).
Sujeto a:
gi(x) <= 0 (i=1,2,….,q) y
hj(x) = 0(j=q+1,….,m).
Dominio de las variables:li<=xi<=ui para
1<=i<=n.
Cada individuo se representa como un vector de
valores de punto flotante:
x=(x1,……..,Xn).
Ilustrando el caso con un NLP
Mutación
Se usa una mutación aleatoria Gausiana N(0,)
(0 = Media  = desviación estandar)
Mutación (Para cada componente):
x’i = xi + N(0,1)
Variar , puede ser beneficioso:
Primero: Remplazar el parámetro  por una
función (t).
Ej: (t) = 1-0.9(t\T).
Ilustrando el caso con un NLP
Mutación
Segundo: Incorporando retroalimentación:
if (t mod n =0) then
(t) 
else
 (t-n)/c, si ps > 1/5
 (t-n)*c, si ps < 1/5
 (t-n),
si ps = 1/5
 (t)   (t-1)
n = un número de generaciones.
ps = frecuencia relativa de mutación exitosa.
Ilustrando el caso con un NLP
Mutación
Tercero: Asignar una mutación específica para
cada vector.
x=(x1,…..xn, ).
 rige como los valores de xi pueden mutar y
esta sujeta a si misma a variación.
’ =  * eN(0, 0),
 = 1/(n)1/2
0
x’i= xi + N(0, ’)
Ilustrando el caso con un NLP
Mutación
Ahora podemos aplicar variaciones a cada uno de
los componentes del individio(no al individuo
como tal).
x=(x1,…..xn,1,…, n).
Usando la misma variación que la anterior.
Taxonomía de las Técnicas de
Control.
• Aspectos a considerar:
1. Qué es exactamente lo que está siendo
modificado(representación, función de evaluación,
operadores, proceso de selección, rata de
mutación)?
2. Comó es que estos cambios se están
haciendo(heurística determinística, heurística
basada en retroalimentación, ó, autoadaptativos)?
3. Cuál es el alcance o nivel del cambio(Poblacional,
Individual)?
4. Qué estadística o evidencia se usa para afectar los
cambios(monitoreo del rendimiento de los
operadores, la diversidad de población)?
Taxonomia de las Técnicas de
Control. (Que es lo que cambia)
• Un lista de todos los componentes del AE.
– Representación de individuos.
– La función de evaluación.
– Los operadores de evaluación y sus
probabilidades asociadas.
– El operador de selección (o remplazo) y las
reglas asociadas.
– La población en términos del tamaño,
topología, etc.
Taxonomia de las Técnicas de
Control. (Que es lo que cambia)
• Cada componente puede ser parametrizado.
Ej: Combinación aritmética.
V = (1x1,…..,nxn).
Tamaño y número de subpoblaciones.
Ratas de migración entre subpoblaciones.
Etc..
Taxonomía de las Técnicas de
Control. (Que es lo que cambia)
• “Manteniendo la atención en lo que cambia,
podemos localizar donde un específico
mecanismo tuvo efecto directo”
Taxonomía de las Técnicas de
Control. (Qué es lo que cambia)
Clasificación de métodos para el cambio de valores
• Determinístico: El valor de los parámetros varía con
una regla determinística.
• Adaptativos: Cuando se utiliza alguna forma de
retroalimentación de la búsqueda, para determinar
la dirección y/o la magnitud del cambio.
• Autoadaptativos: La idea de la evolución de la
evolución. Los parámetros son codificados y
colocados en la estructura de datos, y los mejores
son usados en el algoritmo.
Taxonomía Global
Configuración de parámetros
offline
online
Ajuste de Parámetros
Parámetros de Control
Determinístico
Adaptativos
Auto-adaptativos
Taxonomía de las Técnicas de
Control. (Espacio o nivel de
adaptación)
• Cualquier cambio puede afectar un
componente, un individuo, a toda la población
,ó, a la función de evaluación.
Ej: Un cambio en la desviación estandar puede
afectar todo.
Posibilidades para los parámetros
de control - Representación
• Los mayores esfuerzsos se han concentrado en
estructuras binarias.
Ej: Hamming Clift. Ej: 7 y 8 en binarios es 0111
y 1000).
• Hay manera de hacer la representación de
forma adaptativa.
Ej: Usando parámetros de control adaptativos.
Posibilidades para los parámetros
de control – Función de Evaluación
• Incorporar funciones de castigo dentro de la
evaluación de una solución, permite adaptar la
función durante la búsqueda evolutiva.
• Variar los castigos de acuerdo a un programa
predefinido determinístico.
Ej:
eval(X,)=f(X) + 1/(2 )*f2j(x)
 se disminuye cada vez que el algoritmo
converge.
Posibilidades para los parámetros
de control – Función de Evaluación
• Resolver problemas de satisfacer restricciones,
que cambian la función de evaluación del
rendimiento en una ejecución.
Ej: Aumentar los pesos a las restricciones que
viola el mejor individio.
Posibilidades para los parámetros
de control – Mutación
• Una opción es determinar la rata de mutación.
Ej: Con base en datos experimentales,
determinarla (Funciona solo para ejemplos
específicos).
• Han determinado que la rata de mutación para
funciones binarias de problemas de
optimización que son linealmente separable
por: 1/L (L número de var. Binarias.)
Posibilidades para los parámetros
de control – Mutación
• Cambio de los parámetros de mutación para el
problema de counting-ones problem.
Pm(t) = (/)1/2 * ((exp(-t/2)/(*L1/2))),
Donde , y  son constantes,  es tamaño de la
población y t el tiempo(contador de generaciones).
Posibilidades para los parámetros
de control – Mutación
• Bäck and Schútz restringieron una función
para el control de la probabilidad de la
mutación inciando desde Pm(0)= 0.5 y
usando Pm(T)= 1/L como un máximo valor
de T evaluaciones:
Pm= (2+((L-2/T)*t)-1, si 0<= t <= T.
• Uso de mutaciones no uniformes.
Ej: Buscar uniformemente al principio y muy
localmente al final.
• Auto adaptación
Posibilidades para los parámetros
de control – Operadores de Combina.
• Determinar ratas combinación con base en
trabajos previos realizados.
Ej: Entre 0.6 y 0.95 (Para representaciones
binarias).
• Premiando a los que más éxito tengan en la
optención de hijos.
• Autoadaptativas, agregando un bit extra a cada
individuo, que indica que tipo de combinación
usar para cada uno(Dos diferentes opciones).
Posibilidades para los parámetros
de control – Operadores de Combina.
• Determinar el número y localización de puntos de
combinación. Introduciendo marcas en la
representación indicando donde debe ocurrir la
combinación.
• Aplicar combinación a diferentes padres(más de dos).
- Se divide la población en subpoblaciones
- Cada una con diferentes tipos de combinación.
- Migración.
Posibilidades para los parámetros
de control – Selección de padres.
• El criterio de Metrópolis para definir la presión de
selección ( Cronograma de “Enfriamiento”).
p[aceptada j] = exp(Ei – Ej/kb * T)
Ei y Ej = niveles de energía.
Kb = Kte. de Boltzmann.
T = temperatura.
• Ranking Lineal (proprocional a cada individuo)
p(i)= [((2- b + 2i(b-1)/ t. población))/ t. población]
b = Número de hijos esperados.
Posibilidades para los parámetros
de control – Población.
• Definida desde un principio.
• Usando experimentación.
• Variando en función de la calidad(modificar el
tamaño).
• «Etiquetando» a los individuos («esperanza» de
vida basado en la calidad.)
Formas de combinar parámetros de
control.
• La gran mayoría se basan en controlar un solo
aspecto a la vez.
- Se realizó experimentalmente.
- Es más fácil obtener resultados.
• Es muy difícil.
- No se entiende aún como puede afectar.
• La mayoría de estudios empíricos tratan de
entender la interación entre varios parámetros.
- Modelos estocásticos (Cadenas de Markov)
Formas de combinar parámetros de
control(2).
• El más común es el relacionado con mutación.
- Nivel global.
- Para cada solución
- Un componente dentro de una soluc.
• Combinar la adaptación a diferentes parámetros
de mutación.
- Gaussiana, Cauchy con la desviación estandar.
• La combinación de adaptar múltiples
parámetros de control que gobiernen diferentes
componentes en AE.
Formas de combinar parámetros de
control(3).
Mientras la adaptación de parámetros estáticos
para varios componentes de un AE es compleja,
lo es mucho mas la adaptación dinámica de los
mismos. La autoadaptación parece ser la forma
más prometedora de hacerlo.
CONCLUSIÓN
Los algoritmos evolutivos son una herramienta
nueva para la búsqueda de soluciones, donde
mucho está por hacer.
Descargar

Heuristicas para la optimizacion