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. 12 2017


AGs Paralelos

Precision de la respuesta obtenida: ¿Que tan buena es lasolucion con respecto a la obtenida con otras tecnicas?

Diversidad: El grado en el cual los organismos (de una sola ode varias poblaciones) permanecen diferentes.

Clase No. 12 2017


AGs Paralelos

Sin embargo, hay al menos una metrica adicional que es exclusivade los AGs paralelos:

Velocidad de propagacion de los esquemas: ¿que tan biendistribuidos estan los esquemas “aptos”? O sea, ¿que tan utilresulta la migracion?

Clase No. 12 2017


AGs Paralelos

Existen expresiones estandar para medir la diversidad de un AG(serial o paralelo). Consideremos por ejemplo la siguiente:

l = Longitud cromosomicam = numero de demes

n = tamano de cada demebit (·) = Valor del i-esimo bit en el k-esimo

miembro del j-esimo demeδ = diversidad

Clase No. 12 2017


AGs Paralelos

En esta formula,δ ∈ [0, 1] representa la diversidad de una poblacion(o conjunto de poblaciones).

Si las cadenas consisten de puros ceros, δ = 0.Si las cadenas consisten de puros unos, δ = 0.Si las cadenas son del tipo 101010...10, δ = 0.

Clase No. 12 2017


AGs Paralelos

¿A que se refiere la velocidad de propagacion de esquemas?

Se refiere no solo al porcentaje de demes en los que un ciertoesquema esta presente, sino tambien al porcentaje en el cualdicho esquema esta presente en un deme vecino.

Clase No. 12 2017


AGs Paralelos

¿Como medimos la propagacion de esquemas?

Idealmente, deberıamos conocer de antemano cuales son losbuenos esquemas.

Esto, sin embargo, es imposible en la practica.

Clase No. 12 2017


AGs Paralelos

Una alternativa viable es:

Escoger varios esquemas de antemano.

Hacer que la propagacion de esquemas sea la fraccion maximade demes en la cual aparece un esquema.

Clase No. 12 2017


AGs Paralelos

Ejemplo del calculo de la propagacion de esquemas (SP):

Esquemas seleccionados % de demes en los que aparecen

*1*10* 3/9

*110** 4/9

*10*0* 5/9

En este caso: SP = 5/9

Clase No. 12 2017


Uso de GPUs

En anos recientes, el uso de Graphics Processing Units (GPUs)para acelerar el procesamiento de algoritmos evolutivos muycostosos, se ha vuelto relativamente popular. Las GPUs se hanusado mucho, por ejemplo, en programacion genetica:

W.B. Langdon, “Graphics processing units and geneticprogramming: an overview”, Soft Computing, Vol. 15, No. 8,pp. 1657–1669, August 2011.

Clase No. 12 2017


Uso de FPGAs

Tambien se han usado Field Programmable Gate Arrays (FPGAs)para acelerar la ejecucion de algoritmos evolutivoscomputacionalmente costosos. Ver por ejemplo:

Pei-Yin Chen, Ren-Der Chen, Yu-Pin Chang, Leang-San Shieh andHeidar A. Malki, “Hardware implementation for a geneticalgorithm”, IEEE Transactions on Instrumentation andMeasurement, Vol. 57, No. 4, pp. 699–705, April 2008.

Clase No. 12 2017


Aplicaciones Exitosas de la Computacion

Evolutiva

Un equipo de Unilever Research ha usado algoritmos geneticoscombinados con redes neuronales para disenar nuevos peptidosbactericidas para usarse en limpiadores anti-bacterianos ypreservativos de alimentos.

Clase No. 12 2017



Evolutiva

Las redes neuronales se utilizaron para predecir la actividadbactericida en los peptidos, y posteriormente se combinaron conalgoritmos geneticos para optimizar peptidos virtuales. El resultadofue la generacion de mas de 400 bactericidas virtualespotencialmente activos, de los cuales 5 fueron sintetizados.

Clase No. 12 2017



Evolutiva

La empresa de software escocesa Quadstone, uso algoritmosgeneticos para resolver un problema de optimizacion de estrategiasde produccion de British Petrol. El objetivo era maximizar elretorno financiero de un grupo de campos petrolıferos y de gasinterdependientes. El problema es bastante complejo debido a losmuchos compromisos posibles entre beneficios y penalizaciones.

Clase No. 12 2017



Evolutiva

En este problema, aun una mejora relativamente pequena puedetraer enormes ahorros a la larga, ya que su impacto es acumulativo.El uso de algoritmos geneticos en este problema produjo retornosnetos substancialmente mejores que los producidos previamente porcualquier planeador humano o por cualquier otra tecnica deoptimizacion.

Clase No. 12 2017



Evolutiva

La empresa holandesa Cap Gemini y la empresa britanica KiQLtd han desarrollado de forma conjunta un sistema llamadoOmega, el cual usa algoritmos geneticos para resolver problemasde mercadotecnia, credito y aplicaciones financieras relacionadas.

Clase No. 12 2017



Evolutiva

Omega usa como punto de partida un portafolio de comportamientoprevio de un cliente, ya partir de el genera un modelo matematicoque puede usarse posteriormente para predecir comportamientos declientes que se encuentren fuera de los portafolios conocidos. Estesoftware puede utilizarse para evaluar solicitudes de credito,generar listas de correo (para publicidad), modelar lealtad de losclientes a un producto, y para detectar fraudes.

Clase No. 12 2017



Evolutiva

Un banco holandes comparo Omega contra su sistema deasignacion de credito tradicional (basado en sistemas expertos),encontrando que Omega era substancialmente superior tanto encantidad (ofrecıa mas prestamos) como en calidad (se reducıa elriesgo en los creditos) de los prestamos evaluados.

Clase No. 12 2017



Evolutiva

Investigadores del Kanpur Genetic Algorithms Laboratory(KanGAL), en la India, han utilizado algoritmos geneticos paradisenar un sistema de suspension para un automovil que es mascomodo que el previamente utilizado por una empresa automotrizreconocida mundialmente.

Clase No. 12 2017



Evolutiva

Utilizando un modelo tridimensional de un automovil, optimizaronel diseno de los amortiguadores y los resortes de rigidez delvehıculo. Las simulaciones efectuadas mostraron que el sistemagenerado por el algoritmo genetico hace que los pasajeros sufranmenor aceleracion vertical, de manera que se disfruta de un mayorconfort que con los sistemas utilizados previamente por elfabricante de automoviles en cuestion.

Clase No. 12 2017



Evolutiva

Un grupo de investigadores del Jozef Stefan Institute, enEslovenia, desarrollaron un sistema de programacion de horariosbasado en tecnicas evolutivas. El sistema ha reducidosustancialmente los costos de energıa en la planta de prensado deuna fabrica de automoviles.

Clase No. 12 2017



Evolutiva

El sistema utiliza una heurıstica “avariciosa” (greedy) para disenarhorarios iniciales que luego son utilizados como punto de partidapor una tecnica evolutiva que minimiza el consumo de energıadurante las horas pico.

Clase No. 12 2017



Evolutiva

Descripcion del Problema:

Extender y reforzar la infraestructura de suministro de aguapara la region de York, en Ontario, Canada.

La poblacion de la region se duplicara en el perıodo de 1996 a2031.

Clase No. 12 2017



Evolutiva

Complejidad del Problema:

Para la nueva red se requieren 300 nuevos tipos de tubos, cadauno de los cuales puede adoptar uno de 14 diametroscomerciales disponibles (de 300 mm a 2100 mm)

Combinando las demas variantes del problema (p.ej. ubicacionde las estaciones de bombeo, etc.) se estimo que el tamano delespacio de busqueda era de aproximadamente

10357

Clase No. 12 2017



Evolutiva

Analisis Previo:

Estudios de campo extensivos de la red y de las estaciones debombeo.

Se construyo un modelo de todos los cauces principales de laregion, usando StruMap, que es un sistema de informaciongeografica que tiene un modulo integrado para resolver redeshidraulicas.

Clase No. 12 2017



Evolutiva

Analisis realizado por humanos:

Solo disponible hasta el ano 2011, se extrapolo para el 2031.

Costo estimado: $156 millones de dolares

Clase No. 12 2017



Evolutiva

Uso de Computacion Evolutiva:

GAnet: una biblioteca de clases para desarrollar algoritmosgeneticos.

Incluye rutinas para simular redes hidraulicas.

Maneja restricciones duras y blandas.

Clase No. 12 2017



Evolutiva

Resultados de GAnet:

Agregar 85 tuberıas principales a las 750 ya existentes.

Se propusieron 6 nuevas estaciones de bombeo y sesugirio expandir 3 de las ya existentes, totalizando 42 nuevasbombas.

Clase No. 12 2017



Evolutiva


Se propuso sacar de circulacion a 3 estaciones de bombeo.

Se propusieron 7 nuevos tanques elevados y se sugirio sacar decirculacion a 2 de los existentes.

Clase No. 12 2017



Evolutiva


Costo: $102 millones de dolares.

Solucion 35 % mas economica que la propuesta por disenadoreshumanos.

Ahorro estimado: $54 millones de dolares.

Clase No. 12 2017



Evolutiva

GAnet es uno de los 3 productos principales de software de laempresa Optimal Solutions.

Los otros 2 son:

1) GAser: Genetic Algorithms Sewer Analysis, que se usapara optimizar redes de alcantarillado.

2) GAcal: Herramienta para calibrar modelos hidraulicos.

Clase No. 12 2017



Evolutiva

La empresa Optimal Solutions fue fundada en 1996:http://www.ewan.co.uk/os.html

Esta empresa surgio a partir de la investigacion del Dr. DraganSavic y sus colaboradores en la Universidad de Exeter (enInglaterra).

Clase No. 12 2017



Evolutiva

Actualmente, Optimal Solutions tiene varios contratos dentro yfuera del Reino Unido y se les considera la vanguardia en cuanto aoptimizacion hidraulica con tecnicas no convencionales. Estaempresa esta asociada con Ewan Associates en lo que constituye unejemplo a seguir de vinculacion entre una universidad y la industria.

Clase No. 12 2017



Evolutiva

Torsten Reil, un investigador de Oxford (en Inglaterra), utilizo unalgoritmo genetico para realizar animaciones de una figura humanaque aprende por sı sola a caminar.

Clase No. 12 2017



Evolutiva

Reil desarrollo un modelo corporal simple (figuras solidas con caraspoligonales y uniones que hacen las veces de articulaciones) yposteriormente lo doto de musculos virtuales y una red neuronalpara controlarlos.

Clase No. 12 2017



Evolutiva

De tal forma, habıa que controlar los movimientos de los musculosa traves de la red neuronal. Esto involucro la optimizacion de 700parametros distintos. Hubo que definir, tambien, reglas especialessobre como caminar correctamente (controlando la posicion delcentro de masa), a fin de evitar que la evolucion “hiciera trampa”.

Clase No. 12 2017



Evolutiva

Clase No. 12 2017



Evolutiva

Reil decidio crear la empresa Natural Motion paracomercializar el software creado, el cual permite crearanimaciones realistas de movimientos humanos en 3D usandoalgoritmos geneticos.

Clase No. 12 2017



Evolutiva

Descripcion del Problema:

La empresa britanica Redlands produce losas prefabricadas deconcreto.

El diseno de la topologıa de dichas losas ha sido optimizado pormatematicos usando tecnicas tradicionales.

Clase No. 12 2017



Evolutiva

Complejidad del Problema:

La losa se representa como una placa sujeta a cargas puntuales.

Alta dimensionalidad: unas 400 variables.

Una sola evaluacion de la funcion de aptitud toma alrededor de10 minutos en una estacion de trabajo Sun con 6 procesadores.

Clase No. 12 2017



Evolutiva

Analisis del Problema:

Uso de ANSYS para el analisis por medio del elemento finito

Enfasis en la eficiencia del metodo a desarrollarse

¿Podra disenarse un AG para este problema?

Clase No. 12 2017



Evolutiva

Uso de Computacion Evolutiva:

AG implementado en FORTRAN

Esquema distribuido para evaluar la funcion de aptitud

Representacion con cambio de granularidad

Clase No. 12 2017



Evolutiva

Resultados Obtenidos:

La solucion del AG resulto entre 3 y 5 % mejor que la mejorencontrada con tecnicas tradicionales

Los ahorros fueron de aproximadamente 1.3 millones de librasesterlinas por ano

La inversion: unas 50 mil libras esterlinas en total

Clase No. 12 2017


Motivation

Most problems in nature have several (possibly conflicting)objectives to be satisfied. Many of these problems are frequentlytreated as single-objective optimization problems by transformingall but one objective into constraints.

Clase No. 12 2017


A Formal Definition

The general Multiobjective Optimization Problem (MOP) can beformally defined as:

Find the vector ~x∗ = [x∗1, x∗2, . . . , x

∗n]T which will satisfy the m

inequality constraints:

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

the p equality constraints

hi(~x) = 0 i = 1, 2, . . . , p (2)

and will optimize the vector function

~f(~x) = [f1(~x), f2(~x), . . . , fk(~x)]T (3)

Clase No. 12 2017


What is the notion of optimum

in multiobjective optimization?

Having several objective functions, the notion of “optimum”changes, because in MOPs, we are really trying to find goodcompromises (or “trade-offs”) rather than a single solution as inglobal optimization. The notion of “optimum” that is mostcommonly adopted is that originally proposed by Francis YsidroEdgeworth in 1881.

Clase No. 12 2017


What is the notion of optimum

in multiobjective optimization?

This notion was later generalized by Vilfredo Pareto (in 1896).Although some authors call Edgeworth-Pareto optimum to thisnotion, we will use the most commonly accepted term: Paretooptimum.

Clase No. 12 2017


Definition of Pareto Optimality

We say that a vector of decision variables ~x∗ ∈ F is Pareto optimalif there does not exist another ~x ∈ F such that fi(~x) ≤ fi(~x∗) forall i = 1, . . . , k and fj(~x) < fj(~x∗) for at least one j.

Clase No. 12 2017


Definition of Pareto Optimality

In words, this definition says that ~x∗ is Pareto optimal if thereexists no feasible vector of decision variables ~x ∈ F which woulddecrease some criterion without causing a simultaneous increase inat least one other criterion. Unfortunately, this concept almostalways gives not a single solution, but rather a set of solutionscalled the Pareto optimal set. The vectors ~x∗ correspoding to thesolutions included in the Pareto optimal set are callednondominated. The plot of the objective functions whosenondominated vectors are in the Pareto optimal set is called thePareto front.

Clase No. 12 2017


Sample Pareto Front

Clase No. 12 2017


Some Historical Highlights

As early as 1944, John von Neumann and Oskar Morgensternmentioned that an optimization problem in the context of a socialexchange economy was “a peculiar and disconcerting mixture ofseveral conflicting problems” that was “nowhere dealt with inclassical mathematics”.

Clase No. 12 2017



In 1951 Tjalling C. Koopmans edited a book called ActivityAnalysis of Production and Allocation, where the concept of“efficient” vector was first used in a significant way.

Clase No. 12 2017



The origins of the mathematical foundations of multiobjectiveoptimization can be traced back to the period that goes from 1895to 1906. During that period, Georg Cantor and Felix Hausdorff laidthe foundations of infinite dimensional ordered spaces.

Clase No. 12 2017



Cantor also introduced equivalence classes and stated the firstsufficient conditions for the existence of a utility function.Hausdorff also gave the first example of a complete ordering.

Clase No. 12 2017



However, it was the concept of vector maximum problem introducedby Harold W. Kuhn and Albert W. Tucker (1951) which mademultiobjective optimization a mathematical discipline on its own.

Clase No. 12 2017



Nevertheless, multiobjective optimization theory remainedrelatively undeveloped during the 1950s. It was until the 1960s thatthe foundations of multiobjective optimization were consolidatedand taken seriously by pure mathematicians when Leonid Hurwiczgeneralized the results of Kuhn & Tucker to topological vectorspaces.

Clase No. 12 2017



The application of multiobjective optimization to domains outsideeconomics began with the work by Koopmans (1951) in productiontheory and with the work of Marglin (1967) in water resourcesplanning.

Clase No. 12 2017



The first engineering application reported in the literature was apaper by Zadeh in the early 1960s. However, the use ofmultiobjective optimization became generalized until the 1970s.

Clase No. 12 2017


Current State of the Area

Currently, there are over 30 mathematical programming techniquesfor multiobjective optimization. However, these techniques tend togenerate elements of the Pareto optimal set one at a time.Additionally, most of them are very sensitive to the shape of thePareto front (e.g., they do not work when the Pareto front isconcave or when the front is disconnected).

Clase No. 12 2017


Why Metaheuristics?

Metaheuristics seem particularly suitable to solve multiobjectiveoptimization problems, because they are less susceptible to theshape or continuity of the Pareto front (e.g., they can easily dealwith discontinuous or concave Pareto fronts), whereas this is a realconcern for mathematical programming techniques. Additionally,many current metaheuristics (e.g., evolutionary algorithms, particleswarm optimization, etc.) are population-based, which means thatwe can aim to generate several elements of the Pareto optimal setin a single run.

Clase No. 12 2017


Evolutionary Algorithms

EAs use a selection mechanism based on fitness. We can consider,in general, two main types of multi-objective evolutionaryalgorithms (MOEAs):

1. Algorithms that do not incorporate the concept of Paretodominance in their selection mechanism (e.g., approaches thatuse linear aggregating functions).

2. Algorithms that rank the population based on Paretodominance. For example, MOGA, NSGA, NPGA, etc.

Clase No. 12 2017


Evolutionary Algorithms

Historically, we can consider the existence of two main generationsof MOEAs:

1. First Generation: Characterized by the use of Pareto rankingand niching (or fitness sharing). Relatively simple algorithms.Other (more rudimentary) approaches were also developed(e.g., linear aggregating functions). It is also worth mentioningVEGA, which is a population-based (not Pareto-based)approach.

2. Second Generation: The concept of elitism is introduced intwo main forms: using (µ+ λ) selection and using a secondary(external) population.

Clase No. 12 2017


Representative MOEAs (First Generation)

VEGA

MOGA

NSGA

NPGA

Clase No. 12 2017


Vector Evaluated Genetic Algorithm (VEGA)

Proposed by David Schaffer in the mid-1980s (1984,1985).

It uses subpopulations that optimize each objective separately.The concept of Pareto optimum is not directly incorporatedinto the selection mechanism of the GA.

Clase No. 12 2017


Vector Evaluated Genetic Algorithm (VEGA)

21 n. . .

gene performance

parentsGeneration(t) Generation(t+1)

select nsubgroupsusing eachdimension ofperformancein turn

popsize

1

shuffle apply geneticoperators

popsize

1

STEP STEP STEP1 2 3

.

.

.

.

.

.

1

.

.

.

2

n

Figura 1: Schematic of VEGA selection.

Clase No. 12 2017


Multi-Objective Genetic Algorithm (MOGA)

Proposed by Carlos Fonseca and Peter Fleming (1993).

The approach consists of a scheme in which the rank of acertain individual corresponds to the number of individuals inthe current population by which it is dominated.

It uses fitness sharing and mating restrictions.

Clase No. 12 2017


Nondominated Sorting Genetic Algorithm

(NSGA)

Proposed by N. Srinivas and Kalyanmoy Deb (1994).

It is based on several layers of classifications of the individuals.

Nondominated individuals get a certain dummy fitness value and

then are removed from the population. The process is repeated until

the entire population has been classified.

To maintain the diversity of the population, classified individuals are

shared (in decision variable space) with their dummy fitness values.

Clase No. 12 2017


Niched-Pareto Genetic Algorithm (NPGA)

Proposed by Jeffrey Horn et al. (1993,1994).

It uses a tournament selection scheme based on Pareto dominance.

Two individuals randomly chosen are compared against a subset

from the entire population (typically, around 10 % of the

population). When both competitors are either dominated or

nondominated (i.e., when there is a tie), the result of the tournament

is decided through fitness sharing in the objective domain (a

technique called equivalent class sharing is used in this case).

Clase No. 12 2017


Representative MOEAs (Second Generation)

SPEA and SPEA2

NSGA-II

PAES, PESA and PESA II

The microGA for multiobjective optimization and the µGA2

Clase No. 12 2017


The Strength Pareto

Evolutionary Algorithm (SPEA)

SPEA was introduced by Eckart Zitzler & Lothar Thiele (1999). It uses

an external archive containing nondominated solutions previously found.

It computes a strength value similar to the ranking value used by

MOGA. A clustering technique called “average linkage method” is used

to keep diversity.

Clase No. 12 2017


The Strength Pareto

Evolutionary Algorithm 2 (SPEA2)

A revised version of SPEA has been recently proposed: SPEA2(Zitzler, 2001). SPEA2 has three main differences with respect toits predecessor: (1) it incorporates a fine-grained fitness assignmentstrategy which takes into account for each individual the number ofindividuals that dominate it and the number of individuals bywhich it is dominated; (2) it uses a nearest neighbor densityestimation technique which guides the search more efficiently, and(3) it has an enhanced archive truncation method that guaranteesthe preservation of boundary solutions.

Clase No. 12 2017


The Nondominated Sorting

Genetic Algorithm II (NSGA-II)

Kalyanmoy Deb and co-workers (2000,2002) proposed a newversion of the Nondominated Sorting Genetic Algorithm (NSGA),called NSGA-II, which is more efficient (computationally speaking),it uses elitism and a crowded comparison operator that keepsdiversity without specifying any additional parameters.

Clase No. 12 2017


The Pareto Archived Evolution Strategy (PAES)

PAES was introduced by Joshua Knowles & David Corne (2000).

It uses a (1+1) evolution strategy together with an external archivethat records all the nondominated vectors previously found.

It uses an adaptive grid to maintain diversity.

Clase No. 12 2017

introducci´on a la computaci´on...

Documents