introducci´on a la computaci´on...

Introduccion a la Computacion Evolutiva Dr. Carlos A. Coello Coello

Introduccion a la Computacion Evolutiva

Dr. Carlos A. Coello Coello

Departamento de Computacion

CINVESTAV-IPN

Av. IPN No. 2508

Col. San Pedro Zacatenco

Mexico, D.F. 07300

email: [email protected]

http: //delta.cs.cinvestav.mx/~ccoello

Clase No. 10 2016


Software para Computacion Evolutiva

En general, podemos clasificar el software para computacionevolutiva en 3 grandes grupos:

Orientado a las aplicaciones

Orientado a los algoritmos

Cajas de herramientas

Clase No. 10 2016



Orientado a las aplicaciones : Son “cajas negras” disenadaspara ocultar detalles de los AGs y ayudar al usuario adesarrollar aplicaciones para dominios especıficos tales como lasfinanzas, la programacion de horarios, etc.

Clase No. 10 2016



Orientado a los algoritmos : Se basan en modelos de AGsespecıficos y pueden subdividirse en 2 grupos:

1) Sistemas Especıficos: Contienen un solo algoritmo.

2) Bibliotecas: Contienen una gama de algoritmos y operadoresgeneticos que pueden estar disponibles solo de manerapre-compilada.

Clase No. 10 2016



Cajas de herramientas (tool kits) : Sistemas deprogramacion que proporcionan muchas utilerıas, algoritmos yoperadores geneticos que pueden usarse para cualquier tipo deaplicacion y que normalmente se proporcionan en forma decodigo fuente (al menos de manera parcial).

Clase No. 10 2016



Se pueden subdividir en 2 grupos:

1) Sistemas Educativos : Su objetivo es ayudar a los usuariosnovatos a practicar los conceptos de computacion evolutivarecien aprendidos. Normalmente estos sistemas tienen unnumero relativamente pequeno de opciones para configurar uncierto algoritmo.

2) Sistemas de proposito general : Proporcionan un rico conjuntode herramientas para programar cualquier tipo de AG yaplicarlo a lo que se desee. En algunos casos, incluso permitenque el usuario experto modifique partes del codigo de acuerdo asus propias necesidades.

Clase No. 10 2016


Software de Dominio Publico

Nombre: BUGS (Better to Use Genetic Systems)

Descripcion: Programa interactivo para demostrar el uso de unalgoritmo genetico. El usuario desempena el papel de la funcion deaptitud y trata de evolucionar una cierta forma de vida artificial(curvas).

Clase No. 10 2016



El uso de este programa suele facilitar la comprension de lo que sonlos AGs y como funcionan para aquellos novatos en el area. Ademasde demostrar los operadores geneticos fundamentales (seleccion,cruza y mutacion), BUGS permite visualizar el “desvıo genetico”(genetic drift) y la convergencia prematura.

Clase No. 10 2016



Lenguaje: C bajo X Windows.

Autor: Joshua Smith ([email protected])

Disponibilidad:http://www.aic.nrl.navy.mil/pub/galist/src/BUGS.tar.Z

Clase No. 10 2016



Nombre: Genesis

Descripcion: Implementacion de un AG que tiene gran valorhistorico por haber sido el primer programa de su tipo liberado enel dominio publico.

Clase No. 10 2016



Lenguaje: C para Unix.

Autor: John J. Grefenstette ([email protected])

Disponibilidad:http://www.aic.nrl.navy.mil/pub/galist/src/genesis.tar.Z

Clase No. 10 2016



Nombre: GENEsYs

Descripcion: Implementacion de un AG basada en GENESISque incluye extensiones y nuevas funciones para propositosexperimentales. Por ejemplo, cuenta con seleccion mediantejerarquıas lineales, seleccion de Boltzmann, seleccion (+), cruzauniforme, recombinacion discreta e intermedia, auto-adaptacion deporcentajes de mutacion, etc.

Clase No. 10 2016



Tambien cuenta con una serie de funciones objetivo, incluyendo lasfunciones de De Jong, funciones continuas de alto grado decomplejidad, una instancia del problema del viajero, funcionesbinarias y una funcion fractal. Finalmente, tiene tambien utilerıaspara monitorear resultados tales como vaciados de mapas de bit dela poblacion, varianza de las variables objeto y de los porcentajesde mutacion, etc.

Clase No. 10 2016




Autor: Thomas Back ([email protected])

Disponibilidad:http://www.aic.nrl.navy.mil/pub/galist/src/GENEsYs-1.0.tar.Z

Clase No. 10 2016



Nombre: DGenesis

Descripcion: Implementacion de un AG distribuido desarrollada apartir de GENESIS 5.0. Corre en una red de estaciones de trabajooperando con Unix. Cada subpoblacion es manejada por un procesoUnix y la comunicacion entre ellas se efectua usando sockets deBerkeley Unix.

Clase No. 10 2016




Autor: Erick Cantu Paz ([email protected])

Disponibilidad:http://www.aic.nrl.navy.mil/pub/galist/src/dgenesis-1.0.tar.Z

Clase No. 10 2016



Nombre: GECO (Genetic Evolution through Combination ofObjects)

Descripcion: Ambiente de trabajo orientado a objetos paraimplementar prototipos de algoritmos geneticos. Usa el CLOS(Common LISP Object System) y cuenta con abundantedocumentacion y algunos ejemplos de uso.

Clase No. 10 2016



Lenguaje: Common LISP para Macintosh o Unix.

Autor: George P. Williams, Jr. ([email protected])

Disponibilidad:http://www.aic.nrl.navy.mil/pub/galist/src/GECO-v2.0.tar.Z

Clase No. 10 2016



Nombre: GALOPPS (Genetic Algorithm Optimized for Portabilityand Parallelism)

Descripcion: Un sistema de AGs paralelos en el que usuario puedeescoger:

El tipo de problema (con valores numericos o permutaciones)

Clase No. 10 2016



El tipo de cruza (de entre 7 posibles) y mutacion (de entre 4posibles)

El tipo de seleccion (de entre 6 posibles)

Probabilidades de los operadores, escalamiento de la funcion deaptitud, frecuencia y patrones de migracion

Clase No. 10 2016



Criterios de detencion

Elitismo (opcional)

Uso de diferente representacion para cada subpoblacion, contransformacion de los migrantes

Clase No. 10 2016



Inversion al nivel de subpoblaciones

Control sobre el reemplazo poblacional, incluyendo “crowding”y reemplazo aleatorio

Seleccion de parejas, usando prevencion de incestos

Clase No. 10 2016



Seleccion de migrantes

El usuario puede definir una funcion objetivo (usando unaplantilla) y cualquier funcion auxiliar que necesite. El sistemapuede correr una o varias subpoblaciones, en una o varias PCs,estaciones de trabajo o Macs. El sistema corre de manerainteractiva (con una interfaz grafica o de texto) o desdearchivos.

Clase No. 10 2016



Puede interrumpirse y recomenzarse facilmente. Existe una versionen PVM que incluso mueve los procesos automaticamente cuandouna estacion de trabajo esta ocupada. Viene con 14 ejemplos queincluyen las funciones de De Jong, la carretera real, el viajero, etc.

Clase No. 10 2016




Autor: Erik D. Goodman ([email protected])

Disponibilidad: http://GARAGE.cps.msu.edu/

Clase No. 10 2016



Nombre: ESCaPaDE

Descripcion: Sofisticado sistema que permite correr experimentoscon algoritmos evolutivos tales como la estrategia evolutiva. Elsistema cuenta con 2 tablas internas: una de funciones objetivo yuna de monitores de datos, lo que permite una facil implementacionde funciones para monitorear todo tipo de informacion dentro delalgoritmo evolutivo.

Clase No. 10 2016



Lenguaje: C para Unix (con rutinas en FORTRAN)

Autor: Frank Hoffmeister([email protected])

Disponibilidad: Por e-mail a Hoffmeister

Clase No. 10 2016



Nombre: GANNET (Genetic Algorithm/Neural NETwork)

Descripcion: Paquete de software que permite evolucionar redesneuronales binarias. Ofrece toda una variedad de opciones deconfiguracion relacionadas con los valores de los operadoresgeneticos.

Clase No. 10 2016



La evolucion de las redes neuronales se basa en 3 funciones deaptitud: precision entre las entradas y salidas, “estabilidad” de lasalida y tamano de la red. Soporta redes con entradas y salidasbinarias, con neuronas de 2 o 4 entradas y pesos de entre -3 a +4,permitiendo hasta 250 neuronas en una red.

Clase No. 10 2016



Lenguaje: C para Unix (con rutinas en FORTRAN)

Autor: Jason Spofford

Disponibilidad: http://fame.gmu.edu/˜dduane/thesis

Clase No. 10 2016



Nombre: GENOCOP (Genetic Algorithm for NumericalOptimization for COnstrained Problems)

Descripcion: Paquete de optimizacion numerica para funcionescon cualquier cantidad de restricciones lineales (igualdades ydesigualdades).

Clase No. 10 2016




Autor: Zbigniew Michalewicz ([email protected])

Disponibilidad:http://www.aic.nrl.navy.mil/pub/galist/src/genocop.tar.Z

Clase No. 10 2016



Nombre: GPC++

Descripcion: Biblioteca de clases en C++ para desarrollaraplicaciones de programacion genetica. Esta biblioteca define unajerarquıa de clases y uno de sus componentes integrales es lacapacidad de producir funciones definidas automaticamente.

Clase No. 10 2016



Lenguaje: C++ para Unix/MSDOS.

Autor: Thomas Weinbrenner([email protected])

Disponibilidad:http://www.emk.e-technik.thdarmstadt.de/˜thomasw/gp.html

Clase No. 10 2016



Nombre: GPEIST (Genetic Programming Environment inSmallTalk)

Descripcion: Ambiente de programacion genetica en Smalltalkque puede correrse en HP/Sun/PC. Permite distribucion desubpoblaciones en varias estaciones de trabajo (con intercambiosentre ellas a ciertos intervalos)

Clase No. 10 2016



Lenguaje: Smalltalk

Autor: Tony White ([email protected])

Disponibilidad: ENCORE (The EvolutioNary COmputationREpository network)

URL: http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/

Clase No. 10 2016



Nombre: PGAPack

Descripcion: Biblioteca de proposito general para desarrollar AGsparalelos. Incluye:

Capacidad de invocacion desde FORTRAN o C.

Clase No. 10 2016



Soporte de redes de estaciones de trabajo, arquitecturas enparalelo y uniprocesadores.

Tipos de datos binarios, enteros, reales y caracteres (nativos).

Soporte de nuevos tipos de datos.

Clase No. 10 2016



Interfaz facil de usar.

Niveles multiples de acceso para usuarios expertos.

Facilidades extensivas de depuracion.

Clase No. 10 2016



Gran cantidad de ejemplos.

Detallada guıa del usuario.

Soporte de diferentes tipos de seleccion, cruza y mutacion.

Clase No. 10 2016




Autor: David Levine ([email protected])

Disponibilidad: http://www.mcs.anl.gov/pgapack.html

Clase No. 10 2016



Nombre: REGAL (RElational Genetic Algorithm Learner)

Descripcion: Sistema distribuido basado en AGs disenado paraaprender descripciones de conceptos en logica de primer orden apartir de ejemplos. Se basa en un operador llamado “SufragioUniversal” que permite la probable convergencia asintotica de lapoblacion a un estado de equilibrio en el que coexisten variasespecies.

Clase No. 10 2016



Lenguaje: C para Unix, usando PVM y Tcl/Tk

Autor: Attilio Giordana ([email protected])

Disponibilidad: ftp://ftp.di.unito.it/pub/MLprog/REGAL3.2

Clase No. 10 2016



Nombre: SCS-C (Simple Classifier System in C )

Descripcion: Version en C del Sistema Clasificador Simpleproporcionado en el libro de Goldberg.

Clase No. 10 2016



Lenguaje: C para Unix

Autor: Jorg Heitkoetter ([email protected])

Disponibilidad: ENCORE

Clase No. 10 2016


Software Comercial

Nombre: ActiveGA

Descripcion: Un OLE que usa un algoritmo genetico parasolucionar un problema dado. Algunas de sus funciones incluidasson:

Seleccion de torneo o ruleta.

Clase No. 10 2016


Software Comercial

Parametros del algoritmo genetico definidos por el usuario.

Invisible durante tiempo de ejecucion.

Ejemplos en Excel, Visual BASIC y Visual C++

Precio: $ 99 dolares

Clase No. 10 2016


Software Comercial

Nombre: Evolver

Descripcion: Paquete de algoritmos geneticos para Windows. Losprincipiantes pueden usar el modulo para Excel en sus problemas.

Clase No. 10 2016


Software Comercial

Los usuarios avanzados pueden usar el API incluido paradesarrollar sus propias aplicaciones, las cuales pueden sermonitoreadas en tiempo real usando el EvolverWatcher.


Clase No. 10 2016


Software Comercial

Nombre: PC-Beagle

Descripcion: Programa que examina una base de datos conejemplos y usa tecnicas de aprendizaje de maquina para crear unconjunto de reglas de decision que clasifiquen los ejemplos.

Clase No. 10 2016


Software Comercial

El sistema contiene 6 componentes principales, de los cuales unousa algoritmos geneticos.

Precio: £69

Clase No. 10 2016


Software Comercial

Nombre: MicroGA

Descripcion: Herramienta que permite la integracion dealgoritmos geneticos en cualquier pieza de software. Se trata de unambiente de programacion en C++ que viene en codigo fuente condocumentacion y 3 ejemplos completos.

Clase No. 10 2016


Software Comercial

Tambien incluye un generador de codigo que permite crearaplicaciones completas de manera interactiva y sin escribir una solalınea de codigo. Soporte para Macintosh y MS Windows.


Clase No. 10 2016


Software Comercial

Nombre: GEATbx ( Genetic and Evolutionary Algorithm Toolbox )

Descripcion: Conjunto de funciones en MATLAB que permitenimplementar diferentes tipos de algoritmos geneticos paraoptimizacion con uno o varios objetivos.

Clase No. 10 2016


Software Comercial

Soporta diferentes tipos de seleccion (universal estocastica,torneo, jerarquıas lineales y no lineales, etc.).

Incorpora diferentes tecnicas de cruza (un punto, dos puntos,uniforme, intermedia, discreta, etc.).

Incluye mutacion para representacion entera, real y binaria.

Clase No. 10 2016


Software Comercial

Permite diferentes modelos poblacionales (globales, regionales ylocales).

Permite el monitoreo de almacenamiento de resultados (analisisen lınea y fuera de lınea).

Cuenta con diversas funciones de prueba.

Clase No. 10 2016


Software Comercial

Cuenta con documentacion y un tutorial (en HTML).

Permite la incorporacion de conocimiento especıfico deldominio.

Precio: 150− 250 euros.

Clase No. 10 2016


Operadores Avanzados

Diploides y Dominancia

Inversion

Micro-operadores

Clase No. 10 2016



En AGs, usamos normalmente cromosomas haploides.

En la naturaleza, sin embargo, los genotipos suelen serdiploides y contienen uno o mas pares de cromosomas (a losque se les llama homologos), cada uno de los cuales contieneinformacion (redundante) para las mismas funciones.

Clase No. 10 2016



Ejemplo de un cromosoma diploide:

AbCDefGhIjaBCdeFgHij

Si suponemos que los genes representados por letras mayusculasson los dominantes y los representados mediante letras minusculasson los recesivos, entonces el fenotipo correspondiente alcromosoma anterior serıa:

ABCDeFGHIj

Clase No. 10 2016



El operador utilizado en el ejemplo anterior se denominadominancia.

La idea es que un alelo (o un gen) dominante toma precedenciasobre uno recesivo (por ejemplo, los ojos negros son un alelodominante y los azules uno recesivo).

A un nivel mas abstracto, podemos concebir a la dominancia comoun mapeo reductor del genotipo hacia el fenotipo.

Clase No. 10 2016



¿Por que usa esta redundancia la naturaleza?

Realmente no se sabe.

Las teorıas biologicas mas aceptadas, sugieren que los diploidesson una especie de “registro historico” que protegen ciertosalelos (y combinaciones de ellos) del dano que puede causar laseleccion en un ambiente hostil.

Clase No. 10 2016



En AGs, los diploides suelen usarse para mantener solucionesmultiples (al mismo problema), las cuales pueden conservarse apesar de que se exprese solo una de ellas.

La idea es la misma que en Biologıa: preservar soluciones quefueron efectivas en el pasado, pero que elimino el mecanismo deseleccion del AG.

Clase No. 10 2016



Los diploides parecen ser particularmente utiles en problemas enlos que el ambiente cambia con el paso de las generaciones (porejemplo, optimizacion de funciones dinamicas).

Clase No. 10 2016



El siguiente ejemplo se debe a Hillis (1990, 1992):Padre 1 (diploide):

A: 10110101∣

∣

∣ 011110011110010010101001

B: 00000101∣

∣

∣ 001001110011110010101001

Padre 2 (diploide): ↓

C: 00000111000000111110∣

∣

∣ 000010101011

D: 11111111000010101101∣

∣

∣ 010111011100

Hijo (diploide): ↓

10110101001001110011110010101001

00000111000000111110010111011100

Clase No. 10 2016



El genotipo de un individuo en este ejemplo consiste de 15 pares decromosomas (por claridad, solo un par por cada padre se muestraen esta figura). Se elige aleatoriamente un punto de cruza paracada par, y se forma un gameto tomando los alelos antes del puntode cruza en el primer cromosoma, y los alelos despues del punto decruza en el segundo. Los 15 gametos de un padre se unen con los 15gametos del otro padre para formar un nuevo individuo diploide(nuevamente por claridad solo un gameto se muestra en esta figura).

Clase No. 10 2016


Inversion

Holland (1975) propuso formas de adaptar la codificacion de sualgoritmo genetico original, pues advirtio que el uso de cruza de unpunto no trabajarıa correctamente en algunos casos.

Clase No. 10 2016


Inversion

El operador de inversion es un operador de reordenamientoinspirado en una operacion que existe en genetica. A diferencia delos AGs simples, en genetica la funcion de un gene esfrecuentemente independiente de su posicion en el cromosoma(aunque frecuentemente los genes en un area local trabajan juntosen una red regulatoria), de manera que invertir parte delcromosoma retendra mucha (o toda) la “semantica” del cromosomaoriginal.

Clase No. 10 2016


Inversion

Para usar inversion en los AGs, tenemos que encontrar la manerade hacer que la interpretacion de un alelo sea la misma sinimportar la posicion que guarde en una cadena. Holland propusoque a cada alelo se le diera un ındice que indicara su posicion“real” que se usarıa al evaluar su aptitud.

Clase No. 10 2016


Inversion

Por ejemplo, la cadena 00010101 se codificarıa como:

{ (1,0) (2,0) (3,0) (4,1) (5,0) (6,1) (7,0) (8,1) }

en donde el primer elemento de cada uno de estos paresproporciona la posicion “real” del alelo dado.

Clase No. 10 2016


Inversion

La inversion funciona tomando dos puntos (aleatoriamente) a lolargo de la cadena, e invirtiendo la posicion de los bits entre ellos.Por ejemplo, si usamos la cadena anterior, podrıamos escoger lospuntos 3 y 6 para realizar la inversion; el resultado serıa:

{ (1,0) (2,0) (6,1) (5,0) (4,1) (3,0) (7,0) (8,1) }

Clase No. 10 2016


Inversion

Esta nueva cadena tiene la misma aptitud que la anterior porquelos ındices siguen siendo los mismos. Sin embargo, se han cambiadolos enlaces alelicos. La idea de este operador es producirordenamientos en los cuales los esquemas beneficos puedansobrevivir con mayor facilidad.

Clase No. 10 2016


Inversion

Por ejemplo, supongamos que en el ordenamiento original elesquema 00**01** es muy importante. Tras usar este operador, elesquema nuevo sera 0010****.

Si este nuevo esquema tiene una aptitud mas alta, presumiblementela cruza de un punto lo preservara y esta permutacion tendera adiseminarse con el paso de las generaciones.

Clase No. 10 2016


Inversion

Debe advertirse que el uso de este operador introduce nuevosproblemas cuando se combina con la cruza de un punto.

Supongamos, por ejemplo, que se cruzan las cadenas:

{ (1,0) (2,0) (6,1) (5,0) (4,1) (3,0) (7,0) (8,1) }y

{ (5,1) (2,0) (3,1) (4,1) (1,1) (8,1) (6,0) (7,0) }

Clase No. 10 2016


Inversion

Si el punto de cruza es la tercera posicion, los hijos producidosseran:

{ (1, 0) (2, 0) (6, 1) (4, 1) (1, 1) (8, 1) (6, 0) (7, 0) }y

{ (5, 1) (2, 0) (3, 1) (5, 0) (4, 1) (3, 0) (7, 0) (8, 1) }

Clase No. 10 2016


Inversion

Estas nuevas cadenas tienen algo mal. La primera tiene 2 copias delos bits 1 y 6 y ninguna copia de los bits 3 y 5. La segunda tiene 2copias de los bits 3 y 5 y ninguna copia de los bits 1 y 6.

¿Como podemos asegurarnos de que este problema no se presente?

Clase No. 10 2016


Inversion

Holland propuso 2 soluciones posibles:

(1) Permitir que se realice la cruza solo entre cromosomas quetengan los ındices en el mismo orden. Esto funciona pero limitarıaseveramente la cruza.

Clase No. 10 2016


Inversion

(2) Emplear un enfoque “amo/esclavo”:

Escoger un padre como el amo, y reordenar temporalmente al otropadre para que tenga el mismo ordenamiento que su amo. Usandoeste tipo de ordenamiento se produciran cadenas que no tendranredundancia ni posiciones faltantes.

Clase No. 10 2016


Inversion

La inversion se uso en algunos trabajos iniciales con AGs, peronunca mejoro dramaticamente el desempeno de un AG. Masrecientemente se ha usado con un exito limitado en problemas de“ordenamiento” tales como el del viajero.

Clase No. 10 2016


Inversion

Sin embargo, no hay todavıa un veredicto final en torno a losbeneficios que este operador produce y se necesitan masexperimentos sistematicos y estudios teoricos para determinarlos.

Clase No. 10 2016


Inversion

Adicionalmente, cualquier beneficio que produzca este operadordebe sopesarse con el espacio extra (para almacenar los ındices decada bit) y el tiempo extra (para reordenar un padre antes deefectuar la cruza) que se requiere.

Clase No. 10 2016


Micro-Operadores

En la Naturaleza, muchos organismos tienen genotipos conmultiples cromosomas. Por ejemplo, los seres humanos tenemos 23pares de cromosomas diploides. Para adoptar una estructurasimilar en los algoritmos geneticos necesitamos extender larepresentacion a fin de permitir que un genotipo sea una lista de kpares de cadenas (asumiendo que son diploides).

Clase No. 10 2016


Micro-Operadores

Pero, ¿para que tomarnos estas molestias? Holland (1975)sugirio que los genotipos con multiples cromosomas podrıan serutiles para extender el poder de los algoritmos geneticos cuando seusan en combinacion con 2 operadores: la segregacion y latraslocacion.

Clase No. 10 2016


Micro-Operadores

Segregacion : Para entender como funciona este operador,imaginemos el proceso de formacion de gametos cuandotenemos mas de un par cromosomico en el genotipo. La cruzase efectua igual que como vimos antes, pero cuando formamosun gameto, tenemos que seleccionar aleatoriamente uno de loscromosomas haploides.

Clase No. 10 2016


Micro-Operadores

A este proceso de seleccion aleatoria se le conoce como segregacion.Este proceso rompe cualquier enlace que pueda existir entre losgenes dentro de un cromosoma, y es util cuando existen genesrelativamente independientes en cromosomas diferentes.

Clase No. 10 2016


Micro-Operadores

Traslocacion : Puede verse como un operador de cruzaintercromosomico. Para implementar este operador en unalgoritmo genetico necesitamos asociar los alelos con su“nombre genetico” (su posicion), de manera que podamosidentificar su significado cuando se cambien de posicion de uncromosoma a otro mediante la traslocacion.

Clase No. 10 2016


Micro-Operadores

El uso de este operador permite mantener la organizacion de loscromosomas de manera que la segregacion pueda explotar talorganizacion.

Clase No. 10 2016


Micro-Operadores

La segregacion y la traslocacion no se han usado mucho en lapractica, excepto por algunas aplicaciones de aprendizaje demaquina (e.g., Schaffer, 1984 y Smith, 1980).

Clase No. 10 2016


Micro-Operadores

Duplicacion y Borrado : Son un par de operadores de bajonivel sugeridos para la busqueda artificial efectuada por el AG.La duplicacion intracromosomica produce duplicados de un genen particular y lo coloca junto con su progenitor en elcromosoma. El borrado actua a la inversa, removiendo un genduplicado del cromosoma.

Clase No. 10 2016


Micro-Operadores

Holland (1975) ha sugerido que estos operadores pueden sermetodos efectivos de controlar adaptativamente el porcentaje demutacion. Si el porcentaje de mutacion permanece constante y laduplicacion ocasiona k copias de un gen en particular, laprobabilidad de mutacion efectiva para este gen se multiplica por k.Por otra parte, cuando ocurre el borrado de un gen, el porcentajeefectivo de mutacion se decrementa.

Clase No. 10 2016


Micro-Operadores

Cabe mencionar que una vez que ha ocurrido una mutacion en unode los nuevos genes, debemos decidir cual de las alternativas sera laque se exprese, en un proceso similar al que enfrentamos con losdiploides.

Clase No. 10 2016


Micro-Operadores

De hecho, podemos considerar la presencia de multiples copias deun gen como una dominancia intracromosomica, en contraposicioncon la dominancia intercromosomica que resulta mas tradicional enlos diploides.

Clase No. 10 2016


Micro-Operadores

Holland ha sugerido el uso de un esquema de arbitraje para hacer laeleccion necesaria entre las diferentes alternativas presentes, aunqueno se han publicado estudios sobre este mecanismo hasta la fecha.

La duplicacion puede permitir cosas mas interesantes en un AG,como por ejemplo cadenas de longitud variable (AGs desordenadoso mGAs).

Clase No. 10 2016


Motivation

Traditional mathematical programming techniques used to solveconstrained optimization problems have several limitations whendealing with the general nonlinear programming problem:

Min f(~x) (1)

subject to:

gi(~x) ≤ 0, i = 1, . . . ,m (2)

hj(~x) = 0, j = 1, . . . , p (3)

where ~x is the vector of decision variables ~x = [x1, x2, . . . , xn]T , mis the number of inequality constraints and p is the number ofequality constraints (in both cases, constraints can be either linearor nonlinear).

Clase No. 10 2016


Motivation

Evolutionary Algorithms (EAs) have been found successful in thesolution of a wide variety of optimization problems. However, EAsare unconstrained search techniques. Thus, incorporatingconstraints into the fitness function of an EA is an open researcharea.

There is a considerable amount of research regarding mechanismsthat allow EAs to deal with equality and inequality constraints;both type of constraints can be linear or nonlinear. Such work isprecisely the scope of this tutorial.

Clase No. 10 2016


Search Space

F

FF

S

Clase No. 10 2016


A Taxonomy of Constraint-Handling Approaches

Penalty Functions

Special representations and operators

Repair algorithms

Separation of constraints and objectives

Hybrid Methods

Clase No. 10 2016


Penalty Functions

The most common approach in the EA community to handle constraints

(particularly, inequality constraints) is to use penalties. Penalty

functions were originally proposed by Richard Courant in the 1940s and

were later expanded by Carroll and Fiacco & McCormick.

Clase No. 10 2016


Penalty Functions

The idea of penalty functions is to transform a constrainedoptimization problem into an uncontrained one by adding (orsubtracting) a certain value to/from the objective function basedon the amount of constraint violation present in a certain solution.

Clase No. 10 2016


Penalty Functions

In mathematical programming, two kinds of penalty functions areconsidered: exterior and interior. In the case of exterior methods,we start with an infeasible solution and from there we movetowards the feasible region.

Clase No. 10 2016


Penalty Functions

In the case of interior methods, the penalty term is chosen suchthat its value will be small at points away from the constraintboundaries and will tend to infinity as the constraint boundariesare approached. Then, if we start from a feasible point, thesubsequent points generated will always lie within the feasibleregion since the constraint boundaries act as barriers during theoptimization process.

Clase No. 10 2016


Penalty Functions

EAs normally adopt external penalty functions of the form:

φ(~x) = f(~x)±

n∑

i=1

ri ×Gi +p∑

j=1

cj × Lj

(4)

where φ(~x) is the new (expanded) objective function to beoptimized, Gi and Lj are functions of the constraints gi(~x) andhj(~x), respectively, and ri and cj are positive constants normallycalled “penalty factors”.

Clase No. 10 2016


Penalty Functions

The most common form of Gi and Lj is:

Gi = max[0, gi(~x)]β (5)

Lj = |hj(~x)|γ (6)

where β and γ are normally 1 or 2.

Clase No. 10 2016


Penalty Functions

Penalty functions can deal both with equality and inequalityconstraints, and the normal approach is to transform an equality toan inequality of the form:

|hj(~x)| − ε ≤ 0 (7)

where ε is the tolerance allowed (a very small value).

Clase No. 10 2016


Types of Penalty Functions used with EAs

Death Penalty

Static Penalty

Dynamic Penalty

Adaptive Penalty

Other Approaches

• Self-Adaptive Fitness Formulation

• ASCHEA

• Stochastic Ranking

Clase No. 10 2016


Death Penalty

The rejection of infeasible individuals (also called “death penalty”)is probably the easiest way to handle constraints and it is alsocomputationally efficient, because when a certain solution violatesa constraint, it is rejected and generated again. Thus, no furthercalculations are necessary to estimate the degree of infeasibility ofsuch a solution.

Clase No. 10 2016


Criticism to Death Penalty

Not advisable, except in the case of problems in which thefeasible region is fairly large.

No use of information from infeasible points.

Search may “stagnate” in the presence of very small feasibleregions.

A variation that assigns a zero fitness to infeasible solutionsmay work better in practice.

Clase No. 10 2016


Static Penalty

Under this category, we consider approaches in which the penaltyfactors do not depend on the current generation number in anyway, and therefore, remain constant during the entire evolutionaryprocess.

Clase No. 10 2016


Static Penalty

An example of this sort of approach is the following:

The approach proposed by Homaifar, Lai and Qi [1994] in which

they define levels of violation of the constraints (and penalty factors

associated to them):

fitness(~x) = f(~x) +

m∑

i=1

(

Rk,i × max [0, gi(~x)]2)

(8)

where Rk,i are the penalty coefficients used, m is total the number

of constraints, f(~x) is the unpenalized objective function, and

k = 1, 2, . . . , l, where l is the number of levels of violation defined by

the user.

Clase No. 10 2016


Criticism to Static Penalty

It may not be a good idea to keep the same penalty factorsalong the entire evolutionary process.

Penalty factors are, in general, problem-dependent.

Approach is simple, although in some cases (e.g., in theapproach by Homaifar, Lai and Qi [1994]), the user may needto set up a high number of penalty factors.

Clase No. 10 2016


Dynamic Penalty

Within this category, we will consider any penalty function inwhich the current generation number is involved in thecomputation of the corresponding penalty factors (normally thepenalty factors are defined in such a way that they increase overtime—i.e., generations).

Clase No. 10 2016


Dynamic Penalty

An example of this sort of approach is the following:

The approach from Joines and Houck [1994] in which individuals are

evaluated (at generation t) using:

fitness(~x) = f(~x) + (C × t)α × SV C(β, ~x) (9)

where C, α and β are constants defined by the user (the authors

used C = 0,5, α = 1 or 2, and β = 1 or 2).

Clase No. 10 2016


Dynamic Penalty

SV C(β, ~x) is defined as:

SV C(β, ~x) =

n∑

i=1

Dβi (~x) +

p∑

j=1

Dj(~x) (10)

and

Di(~x) =

{

0 gi(~x) ≤ 0

|gi(~x)| otherwise1 ≤ i ≤ n (11)

Dj(~x) =

{

0 −ε ≤ hj(~x) ≤ ε|hj(~x)| otherwise

1 ≤ j ≤ p (12)

This dynamic function increases the penalty as we progress through

generations.

Clase No. 10 2016


Criticism to Dynamic Penalty

Some researchers have argued that dynamic penalties workbetter than static penalties.

In fact, many EC researchers consider dynamic penalty as agood choice when dealing with an arbitrary constrainedoptimization problem.

Note however, that it is difficult to derive good dynamicpenalty functions in practice as it is difficult to produce goodpenalty factors for static functions.

Clase No. 10 2016


Adaptive Penalty

Bean and Hadj-Alouane [1992,1997] developed a method that usesa penalty function which takes a feedback from the search process.Each individual is evaluated by the formula:

fitness(~x) = f(~x) + λ(t)

n∑

i=1

g2i (~x) +

p∑

j=1

|hj(~x)|

(13)

where λ(t) is updated at every generation t.

Clase No. 10 2016


Adaptive Penalty

λ(t) is updated in the following way:

λ(t+ 1) =

(1/β1) · λ(t), if case #1

β2 · λ(t), if case #2

λ(t), otherwise,

(14)

where cases #1 and #2 denote situations where the best individual in

the last k generations was always (case #1) or was never (case #2)

feasible, β1, β2 > 1, β1 > β2, and β1 6= β2 (to avoid cycling).

Clase No. 10 2016


Adaptive Penalty

In other words, the penalty component λ(t+ 1) for the generationt+ 1 is decreased if all the best individuals in the last k generationswere feasible or is increased if they were all infeasible. If there aresome feasible and infeasible individuals tied as best in thepopulation, then the penalty does not change.

Clase No. 10 2016


Criticism to Adaptive Penalty

Setting the parameters of this type of approach may be difficult(e.g., what generational gap (k) is appropriate?).

This sort of approach regulates in a more “intelligent” way thepenalty factors.

An interesting aspect of this approach is that it tries to avoidhaving either an all-feasible or an all-infeasible population.Other constraint-handling approaches pay a lot of attention tothis issue.

Clase No. 10 2016

introducci´on a la computaci´on...

Documents