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