Observaciones hechas sobre la ejecució ndel A.G. simple y que deben mejorarse
i) Perdida, en las etapas posteriores de la corrida, de la mejorsolución alcanzada
ii) Rápida perdida de la diversidad de la población bien porconvergencia prematura o por que algún super-individuo logra dominarla población.
iii) Pobre
convergencia del algoritmo a la solución en las etapas posteriores
de la corrida. Poblaciones finales muy homogéneas o de muchos individuos
idénticos.
Comomedir la ejecuci
óndel A.G.
El a.g.es un método de búsqueda estocástico por ende cualquier medida de interés tiene que ser en forma de un promedio sobre varias corridas. dos observables adecuados para calibrar la ejecución deun a.g. son:
-- La adaptación delmejor
individuo de la población.
-- El promedio de las adaptaciones
de los individuos en la población.
Ambosobservables
han de medirse en diversas etapas de la corrida (medida dinámica).
i) Fijar los parámetros del a.g. (numero de población, probabilidades de operadores y numero máximo de iteraciones).
ii) Fijar la función de adaptación cuidando que se disponga desuficiente resolución en relación a la precisión dela representación.
iii) Correr el a.g. 20 veces y registrar durante tiempos adecuados ambos observables.
iv) Graficar
los promedios de las medidas realizadas sobre todas las corridas.
La gráfica
en cuestión puede hacerse en función del numero de iteraciones
(generaciones) pero lo mejor es graficar los observables en función
del numero de individuos que se han introducido en la población.
Esto es,considerar cuantos nuevos cromosomas se han evaluado. En general el pasomas costoso en el a.g. es la evaluación de los cromosomas.
Introducci
ónde renormalizaci
ón
Una primera mejora consiste en renormalizar la adaptación de los individuos,y luego proceder a la selección con los valores de adaptación renormalizados.
De estaforma se introduce un mecanismo que alivia los efectos nefastos de la convergencia prematura y/o de la presencia de super-individuos.
Se consideran dos tipos de renormalizaciones: lineal y por ventanas.
Ejemplosde renormalizaci
ónde la
funció
nde adaptació
n
F.adapt:
1.135 1.025 0.987
0.805 0.532 0.222
Renorm. por ventana:
min. 0.3:
0.835 0.725 0.687
0.505 0.3
0.3
min. 0.2:
0.935 0.825 0.787
0.605 0.332 0.2
Renorm. lineal (max.: 100dec.: 5):
100 95 90 85 80 75
Renorm. lineal (max.: 100dec.:20):
100 80
60 40
20 00
Otrosdos mecanismos
de renormalización (David Goldberg)
Renormalizaciónpor truncamiento
s
i) Aplicable para adaptaciones
positivas.
ii) Se evalúa:
iii) La renormalizaciónprocede
de la forma:
Siendo c un múltiplorazonable
de s
(1 a 3)
iv) Si f’< 0
se coloca f’ =0.
Renormalizaciónpor
ley de potencias
Cambioen el esquema de sustitución de la población
Una manera sencilla de conservar la mejor estructura alcanzada durante la corrida consiste en heredar siempre el mejor individuo de la generación anterior en la siguiente. Este método de substitución de la población se denomina elitismo.
Esta estrategia significa substituir n-1 individuos de la población segúnel esquema corriente y completar el enésimo con el mejor individuoanterior. Tiene sus “bemoles” pero mejora la eficiencia.
Sustitución con gap generacional (denominada por Davis reproducción de estado estacionario) consiste en substituir en cada generación una fracción de la población anterior por nuevos individuos.Es claro que lafracción de individuos substituida es aquella constituida por losde peor adaptación .
En generalla fracción
a substituir es un parámetro del A.G. pero losvalores que han resultado
ser mejores están por debajo del 10% deltamaño de la población.
El nombrede reproducción
de estado estacionario se justifica en el caso deun gap generacional muy
pequeño (substitución de uno o dosindividuos nuevos por generación).
Sea elgap generacional m individuos:
i) Reproducir m hijos a partir
de individuos seleccionados en la población.
ii) Borrar los m peoresmiembros
de la población (los de menor adaptación).
iii) Evaluar e insertarlos nuevos
hijos en la población.
La substitución
con gap generacional permite aun otra variante que mejora la ejecución
del a.g. la técnica consiste en descartar aquellos nuevos hijosidénticos
a cromosomas ya presentes enla población.
En la literatura se conoce como reproducciónde estado estacionario
sin duplicados. La consecuencia de usar estatécnica será
que todos los individuos de la poblaciónserán diferentes.
Este método
agrega un “overhead” computacional al tener que comparar cada
hijo conlos “sobrevivientes “ de la población.
Mejoresvalores para los parametros de los operadores gen éticos
Los valores canónicos de los parámetros que hemos venido utilizando correspondan a valores robustos sobre una variedad de problemas determinados por la practica con el a.g. simple.
Al modificar
el algoritmo es útil revisar estos valores ya que se podría
mejorar la ejecución del a.g. con ligeros cambios.
Mutación:el a.g. simple
debe ser cuidadoso con la aplicación de la mutaciónPm
~ 0.001 ya que es un operador muy destructivo de información
genética. Puede ocasionar perdida irreversible de buenos individuos
en razón de la estrategia de substitución total de la población.
Por otro lado es útil poseer una amplia diversidad en la población.
al introducir la substitución parcial de la población yano
se corre el riesgo de perder el buen material genético por loque es
bueno aumentar la tasa de aplicación de la mutaciónpor lo menos
en un orden de magnitud a Pm ~ 0.01
Cruce: la probabilidadde
aplicación del operador de cruce Pc ~ 0.8 estees un
valor alto pero en general en muchas aplicaciones del a.g. simplees mejor
emplear Pc ~ 0.6. La razón de bajar Pc tieneque ver
con la posibilidad de convergencia prematura por homogeneizaciónde
la población. En las estrategias de reproducción parcialsin
duplicados la homogeneización de la población es imposiblepor
lo que es bueno conservar esta alta rata de cruce o incrementarla a~0.9
. es decir es importante recombinar la información cromosomica.
Lo que hace eficiente la búsqueda
Algoritmogen éticomodificado
Al implementar sobre un A.G. simple las modificaciones anteriores se obtiene un programa evolutivo que constituye una poderosa maquinaria para resolver problemas :
Representación:
Binaria
Población:
Constante n
Inicialización:
Aleatoria
Renormalización:
Lineal (o por ventana)
Selección:
Rueda de ruleta
Operadores:
Cruce un punto + mutación
Substitución:
Parcial (sin duplicados)
Parámetros:
n(~100) , pm(~0.01), pc(~0.9) y gap(5-10%)
Algoritmogené
ticomodificado virtudes y defectos
Metodología de muy amplia aplicación sobre todo a problemas de la vida real.
Fácil
implantación.
Algunosaspectos
de este programa evolutivo requieren ser estudiados con mas profundidad.
Relativamentefácil
de entonar a un problema particular.
Operadores
genéticos simples y de muy fácil comprensión.
Pocosparámetros
(pc, pm, n, gap y de renorm.).
Acción
conjunta de los operadores evolutivos no es natural y puede no ser lo más
conveniente.
Representación binaria de la información tampoco puede ser lo más naturalpara el problema considerado.
La entonación del algoritmo tiene que realizarse por ensayo y error para cada problema.
Aun pueden hacérsele mejoras.
La substitución parcial de la población es muy sensible a funciones de adaptación no-deterministicas o ruidosas.
Con funciones de adaptación ruidosas, la substitución total de la población es más recomendable.
En este sentido el a.g. simple es un método más robusto queel a.g. modificado.
No obstante
el a.g. modificado al entonarse para un problema particular con función
de adaptación determinista es mas eficiente.
Modificacionesadicionales programas evolutivos m
ásconplejos
El A.G.modificado emplea esencialmente un operador de reproducciónconformado por la aplicación sucesiva de los operadores de crucey mutación sobre los hijos.
Hemosvenido argumentando que esto no es lo más natural y puede no serlo más conveniente como lo muestran diversos estudios.
En laliteratura
se presenta una gran variedad de operadores genéticosespecíficos
de representaciones o problemas particularesque podría ser
provechoso considerar en búsqueda de mayoreficiencia.
El primer
paso que debemos tomar tiene que ver con independizar la acciónde
los operadores genéticos. Es decir que durante el evento de reproducción
uno solo de los operadores (cruce o mutación) actuara.
Se implementara
lo que Davis denomina reproducción basada en los operadores
es decir que durante cualquier evento de reproducción se ha de seleccionar
aleatoriamente el operador a aplicar para luego seleccionar de la población
el/los cromosomas a reproducir.
Estaestrategia
reproductiva requiere de la introducción de nuevos parámetros,
uno por operador, representando la probabilidad de selecciónde
cada operador.
Una vez fijadas las probabilidades a priori el proceso de selección deloperador procede según el mecanismo de rueda de ruleta.
Davispor
ejemplo trata estos parámetros de selección como números
normalizados a 100, (suma de ellos = 100) de tal forma que el parámetro
es directamente la tasa porcentual de selección