L/O/G/O Universidad Nacional de Colombia Freddy Alexander Posada 495983 Nohora Esperanza Rozo 415851...
Preview:
Citation preview
- Diapositiva 1
- L/O/G/O Universidad Nacional de Colombia Freddy Alexander
Posada 495983 Nohora Esperanza Rozo 415851 Juan Carlos Lezama
416065 Alfredo Velandia 415706 Norma Idarraga 415114 Eliana Ortegn
415188 Juan Bernardo 416289
- Diapositiva 2
- www.themegallery.com La vida de los seres en la tierra ha
podido evolucionar y ser lo que es a travs de los procesos de
seleccin natural, recombinacin y mutacin. Ilustrar como estos
procesos naturales han trabajado en conjunto para llegar a producir
una amplia gama de flora y fauna es algo bastante complejo, pero
que es susceptible de anlisis bastante interesantes.
- Diapositiva 3
- www.themegallery.com Cada uno de los organismos vivos est
diseado naturalmente siguindose un conjunto de reglas Las reglas
son los genes de un organismo Cada gen representa un rasgo
especfico del organismo Este rasgo tiene una serie de opciones
diferentes
- Diapositiva 4
- www.themegallery.com Los procesos de seleccin natural, la
supervivencia del ms fuerte y la mutacin de los genes desarrollan
un papel muy importante para generar la evolucin de un organismo.
Esquema de los seres vivos Esquema de la cosas.
SELECCINRECOMBINACIN MUTACIN
- Diapositiva 5
- www.themegallery.com Un algoritmo es simplemente una serie de
pasos que estn organizados, por lo tanto se encuentran describiendo
un proceso que se debe seguir en la bsqueda de solucin a
determinado problema. Los algoritmos genticos se definen as dado
que son inspirados en la evolucin biolgica y su base gentico
molecular
- Diapositiva 6
- www.themegallery.com La representacin sea cual sea, debe ser
capaz de identificar las caractersticas constituyentes de un
conjunto de soluciones. BinariaEnteraReal Debe darse de forma que
distintas representaciones permitan distintas perspectivas y as
mismo distintas soluciones.
- Diapositiva 7
- www.themegallery.com Los algoritmos genticos requieren que el
conjunto se codifique en un cromosoma, un cromosoma tiene varios
genes, que corresponden a parmetros del problema. Para poder
trabajar estos genes en una computadora se codifican en una cadena.
El nmero de bits que se usen para cada parmetro depender entonces
de la precisin que se busque o del nmero de opciones que se tengan
como posibles. El nmero de bits que se usen para cada parmetro
depender entonces de la precisin que se busque o del nmero de
opciones que se tengan como posibles.
- Diapositiva 8
- www.themegallery.com Al principio y tratndose de una poblacin
grande, los cromosomas se crean al azar. Una solucin que busquemos,
por ejemplo 23, representada por 6+5*4/2+1 se representara as:
- Diapositiva 9
- www.themegallery.comMUTACIN La tasa de mutacin depende del paso
CRUCE Tasa de cruce depende del nmero de bits del cromosoma
SELECCIN Tomar dos miembros de la poblacin actual Mtodo de la
ruleta PRUEBA Se prueba el cromosoma en solucin al problema Se le
asigna una puntuacin por ello
- Diapositiva 10
- www.themegallery.com Es un mtodo para elegir a los miembros de
la poblacin de los cromosomas de una manera que sea proporcional a
su aptitud. Ello no garantiza que el miembro ms fuerte pase a la
siguiente generacin, pero tiene una buena oportunidad de
hacerlo.
- Diapositiva 11
- www.themegallery.com Corresponde a la posibilidad de que dos
cromosomas se intercambien sus bits. El cruce se realiza mediante
la seleccin de un gen al azar a lo largo de los cromosomas y el
intercambio de todos los genes despus de ese punto.
- Diapositiva 12
- www.themegallery.com Esta corresponde a la posibilidad de que
algo dentro del cromosoma se cambie, - un cero se convierta en 1 o
un 1 en cero-. Tratndose de genes codificados con nmeros binarios
el valor de la tasa de mutacin suele ser bajo 0110
- Diapositiva 13
- www.themegallery.com PRUEBA SELECCIN CRUCE MUTACIN Los pasos
b,c,d se repiten hasta que una nueva poblacin de los miembros de n
se ha creado.
- Diapositiva 14
- www.themegallery.com Cada uno de los algoritmos genticos
representa una posible solucin al problema que se desea resolver.
Todo individuo tiene asociado un ajuste de acuerdo a la bondad con
respecto al problema de la solucin que representa, a ese ajuste de
cada individuo se le llama Algoritmo principal.
- Diapositiva 15
- www.themegallery.com La reproduccin de los algoritmos se puede
hacer a travs de: Cruce: Trata de una reproduccin de tipo sexual
Copia: Trata de una reproduccin de tipo asexual. Del algoritmo
principal desarrollado por Holland se han propuesta distintas
variaciones para reemplazar una poblacin temporal, esas variaciones
son: Reemplazo de padres. Reemplazo de individuos similares.
Reemplazo de los peores individuos. Reemplazo aleatorio.
- Diapositiva 16
- www.themegallery.com Tambin denominado cannico es un tipo de
algoritmo, el cul necesita una codificacin o representacin del
problema que resulte conveniente para este, adems requiere una
funcin de ajuste la cul asigna un nmero real a cada solucin
codificada. El resultado de la combinacin de las anteriores
funciones ser un conjunto de individuos (posibles soluciones al
problema), los cuales en la evolucin del Algoritmo Gentico formarn
parte de la siguiente poblacin.
- Diapositiva 17
- www.themegallery.com Representacin binaria en la que el valor
de cada gen es 0 o 1. Representacin entera en la que cada gen toma
un valor numrico dentro del rango de nmeros enteros. Representacin
real en la que cada gen es un valor real.
- Diapositiva 18
- www.themegallery.com Se intuye que el trabajo con poblaciones
pequeas es riesgoso al no cubrir al 100% el espacio de bsqueda,
mientras que en poblaciones grandes, el riesgo es tener un excesivo
costo computacional. Goldberg concluy que un tipo de poblacin de
tamao L crece exponencialmente con codificacin binaria, pero, no
sera muy aplicable a las codificaciones de valor real. Alander
sugiere una poblacin ideal entre 1 y 21 tipos, y cree que este
rango es suficiente para solucionar los problemas por l
planteados.
- Diapositiva 19
- www.themegallery.com Habitualmente la poblacin inicial se
escoge generando ristras al azar, pudiendo contener cada gen uno de
los posibles valores del alfabeto con probabilidad uniforme. Si los
individuos de la poblacin inicial se obtienen por optimizacin
local, puede acelerar la convergencia del Algoritmo Gentico.
- Diapositiva 20
- www.themegallery.com Existen dos aspectos que resultan
cruciales en el comportamiento de los Algoritmos Genticos y son una
adecuada funcin de adaptacin o funcin objetivo as como la
codificacin utilizada.
- Diapositiva 21
- www.themegallery.com En un algoritmo gentico tras parametrizar
el problema bajo una serie (Xi,..., Xn), se codifican en un
cromosoma. Todos los operadores utilizados por un algoritmo gentico
se aplicarn a estos cromosomas, o sobre poblaciones de ellos. Las
soluciones codificadas en un cromosoma compiten entre s para ver
cual constituye la mejor solucin al problema entre todas las
alternativas creadas.
- Diapositiva 22
- www.themegallery.com El algoritmo gentico se usar para
solucionar solo una funcin y no solucionar diversas funciones
relacionadas entre s simultneamente, a lo que se le llama
optimizacin multimodal. Los algoritmos genticos son programas
computacionales cuyo fin es imitar el proceso de "seleccin natural"
que, segn la Teora de Darwin, rige el curso de la evolucin.
- Diapositiva 23
- www.themegallery.com Se tiene una poblacin, Esa poblacin se
multiplica por medio del intercambio de genes De la nueva generacin
solo sobrevivirn aquellos capaces de adaptarse al medio ambiente, y
por consiguiente, as estos nuevos individuos capaces, sern una
nueva poblacin "mejore" que la anterior. Este ciclo de creacin de
las poblaciones a lo podemos evidenciar generacin tras
generacin
- Diapositiva 24
- www.themegallery.com OPERACIONES DE SELECCIN Es el encargado de
transmitir y conservar aquellas caractersticas de las soluciones
que se consideran valiosas a lo largo de las generaciones. Es el
encargado de transmitir y conservar aquellas caractersticas de las
soluciones que se consideran valiosas a lo largo de las
generaciones. La probabilidad que tiene un individuo de
reproducirse es proporcional a la diferencia entre su aptitud y la
de sus competidores. Se eligen subgrupos de individuos de la
poblacin, y los miembros de cada subgrupo compiten entre ellos
Seleccin por ruleta Seleccin por ruleta Seleccin escalada Seleccin
escalada Seleccin por torneo Seleccin por torneo Al incrementarse
la aptitud media de la poblacin, la fuerza de la presin selectiva
tambin aumenta y la funcin de aptitud se hace ms
discriminadora.
- Diapositiva 25
- www.themegallery.com OPERACIONES DE CRUCE Es una estrategia de
reproduccin sexual. Es una estrategia de reproduccin sexual. Se
establece 1 punto de intercambio en un lugar aleatorio del genoma
Los genes de los padres son intercambiados de forma aleatoria. Se
establecen 2 puntos de intercambio en un lugar aleatorio del
genoma
- Diapositiva 26
- www.themegallery.com OPERACIONES DE REEMPLAZO Cuando se trabaja
con una sola poblacin, sobre la que se realizan las selecciones e
inserciones, deber tenerse en cuenta que para insertar un nuevo
individuo deber de eliminarse previamente otro de la poblacin:
Aleatorio. Reemplazo de padres. Reemplazo de similares. Reemplazo
de los peores
- Diapositiva 27
- www.themegallery.com OPERACIONES DE COPIA Se trata de una
estrategia de reproduccin asexual OPERACIONES DE MUTACIN Provoca
que alguno de sus genes, generalmente uno slo, vare su valor de
forma aleatoria.
- Diapositiva 28
- www.themegallery.com No necesitan tener un conocimiento previo
para resolver un problema Los algoritmos genticos explotan un
sinnmero de soluciones Poseen habilidad para manipular muchos
parmetros simultneamente Los algoritmos genticos estn ntimamente
relacionados, pues operan de forma simultnea con varias
soluciones.
- Diapositiva 29
- www.themegallery.com Pueden converger prematuramente debido a
una serie de problemas. (Este problema se presenta en poblaciones
pequeas, donde una variacin aleatoria en el ritmo de reproduccin
provoca que un genotipo se haga dominante sobre los otros.) El
lenguaje que se debe utilizar debe tener la capacidad de tolerar
cambios aleatorios Puede demorarse bastante en converger o no en
absoluto
- Diapositiva 30
- www.themegallery.com El desarrollo de los Algoritmos Genticos
se debe en gran medida a John Holland, investigador de la
Universidad de Michigan. A finales de la dcada de los 60 desarroll
una tcnica que imitaba en su funcionamiento a la seleccin natural.
Aunque originalmente esta tcnica recibi el nombre de planes
reproductivos, a raz de la publicacin en 1975 de su libro
``Adaptation in Natural and Artificial Systems se conoce
principalmente con el nombre de Algoritmos Genticos.El desarrollo
de los Algoritmos Genticos se debe en gran medida a John Holland,
investigador de la Universidad de Michigan. A finales de la dcada
de los 60 desarroll una tcnica que imitaba en su funcionamiento a
la seleccin natural. Aunque originalmente esta tcnica recibi el
nombre de planes reproductivos, a raz de la publicacin en 1975 de
su libro ``Adaptation in Natural and Artificial Systems se conoce
principalmente con el nombre de Algoritmos Genticos.
- Diapositiva 31
- www.themegallery.com
- Diapositiva 32
- La Ruleta : Es el usado por Goldberg en su libro [4]. Este
mtodo es muy simple, y consiste en crear una ruleta en la que cada
cromosoma tiene asignada una fraccin proporcional a su aptitud. Sin
que nos refiramos a una funcin de aptitud en particular, supongamos
que se tiene una poblacin de 5 cromosomas cuyas aptitudes estn
dadas por los valores mostrados en la Tabla 1. Cromosoma No.
CadenaAptitud % del Total 11101011025424.5 210100111474.5
30011011045744.1 40111001019418.7 511110010858.2
TOTAL1037100.0
- Diapositiva 33
- www.themegallery.com Con los porcentajes mostrados en la cuarta
columna de la Tabla 1 podemos elaborar la ruleta de la Figura 1.
Esta ruleta se gira 5 veces para determinar qu individuos se
seleccionarn. Debido a que a los individuos ms aptos se les asign
un rea mayor de la ruleta, se espera que sean seleccionados ms
veces que los menos aptos.
- Diapositiva 34
- www.themegallery.com Un grupo de financieros mexicanos ha
resuelto invertir 10 millones de pesos en la nueva marca de vino
"Carta Nueva. As pues, en 4 ciudades de las principales de Mxico se
decide iniciar una vigorosa campaa comercial: Mxico en el centro,
Monterrey en el noroeste, Guadalajara en el occidente y Veracruz en
el oriente. A esas 4 ciudades van a corresponder las zonas
comerciales I, II, III y IV. Un estudio de mercado ha sido
realizado en cada una de las zonas citadas y han sido establecidas
curvas de ganancias medias en funcin de las inversiones totales
(almacenes, tiendas de venta, representantes, publicidad, etc.)
Estos datos se ilustran en la Tabla 2 y en la Figura 5. Para
simplificar los clculos, supondremos que las asignaciones de
crditos o de inversiones deben hacerse por unidades de 1 milln de
pesos. La pregunta es: en dnde se deben de asignar los 10 millones
de pesos de los que se dispone para que la ganancia total sea
mxima?
- Diapositiva 35
- www.themegallery.com
- Diapositiva 36
- Inversin (en millones)
BeneficioIBeneficioIIBeneficioIIIBeneficioIV00000 10.280.250.150.20
20.450.410.250.33 30.650.550.400.42 40.780.650.500.48
50.900.750.620.53 61.020.800.730.56 71.130.850.820.58
81.230.880.900.60 91.320.900.960.60 101.380.901.000.60
- Diapositiva 37
- www.themegallery.com 2) Funcin de Aptitud : Dado que el
objetivo es obtener las inversiones que sumen 10, y que tengan un
beneficio mximo, podemos usar la siguiente funcin de aptitud
penalizada: F(x) =c1+ c2 + c3 + c4 500 * v +1 donde c1, c2, c3 y c4
son las ganancias por zona, que se calculan de acuerdo a los
valores de la Tabla 2, y v es el valor absoluto de la diferencia
entre la suma obtenida y 10. Ntese que cuando no se viole ninguna
restriccin (i.e., cuando la suma de inversiones sea exactamente 10)
la funcin de aptitud no ser "castigada.
- Diapositiva 38
- www.themegallery.com 3) Operadores : Se usar una cruza de 2
puntos, la cual se efecta de la forma que se indica en la Figura 3.
La probabilidad que se dar a la misma ser del 80%. En cuanto a la
mutacin, se le asignar una probabilidad baja, tal y como sugiere
Goldberg [4], por lo que ser del orden del 1%. El tamao de poblacin
manejado para este ejemplo ser de 50 cromosomas, y se correr el
algoritmo gentico durante 20 generaciones.
- Diapositiva 39
- www.themegallery.com 4) Resultados : El resultado obtenido en
una corrida tpica es de $1.81 (en millones de pesos),
correspondiente a los valores de C1=4 millones, C2=3 millones, C3=1
milln y C4=2 millones. Esta es la solucin ptima, la cual se obtuvo
originalmente mediante programacin dinmica [13]. El tiempo que le
tom al algoritmo gentico encontrar este valor fue de slo 13
segundos3. Debe hacerse notar que, en este caso, si deseramos
analizar inversiones que sumen otra cantidad, y en unidades menores
al milln, el algoritmo gentico tendra que modificarse de manera
mnima, mientras que la programacin dinmica requerira una cantidad
tal de trabajo que prcticamente se volvera inoperante.
- Diapositiva 40
- www.themegallery.com
- Diapositiva 41
- Diapositiva 42
- Diapositiva 43
- L/O/G/O