Download ThemeGallery PowerTemplate

L/O/G/O
Freddy Alexander Posada
Nohora Esperanza Rozo
Juan Carlos Lezama
Alfredo Velandia
Norma Idarraga
Eliana Ortegón
Juan Bernardo
495983
415851
416065
415706
415114
415188
416289
Universidad Nacional de Colombia


La vida de los seres en la tierra
ha podido evolucionar y ser lo
que es a través de los procesos
de
selección
natural,
recombinación y mutación.
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
análisis
bastante interesantes.
www.themegallery.com
Cada uno de los organismos vivos
está
diseñado
naturalmente
siguiéndose un conjunto de reglas
Las reglas son los genes de un
organismo
Cada gen representa un
específico del organismo
Este rasgo tiene una
opciones diferentes
www.themegallery.com
rasgo
serie
de

Los procesos de selección
natural, la supervivencia
del más fuerte y la
mutación de los genes
desarrollan un papel muy
importante para generar
la
evolución
de
un
organismo.
SELECCIÓN
MUTACIÓN
Esquema
de los
seres vivos
www.themegallery.com
RECOMBINACIÓN
Esquema
de la
cosas.


Un algoritmo es simplemente
una serie de pasos que están
organizados, por lo tanto se
encuentran describiendo un
proceso que se debe seguir
en la búsqueda de solución a
determinado problema.
Los algoritmos genéticos se
definen así dado que son
inspirados en la evolución
biológica y su base genético
molecular
www.themegallery.com

La representación
sea
cual
sea,
debe ser capaz
de identificar las
características
constituyentes de
un conjunto de
soluciones.
Debe darse de forma que
distintas representaciones
permitan distintas perspectivas
y así mismo distintas
soluciones.
Binaria
www.themegallery.com
Entera
Real



Los
algoritmos
genéticos
requieren que el conjunto se
codifique en un cromosoma, un
cromosoma tiene varios genes,
que corresponden a parámetros
del problema.
Para poder trabajar estos genes
en
una
computadora
se
codifican en una cadena.
El número de bits que se usen
para cada parámetro dependerá
entonces de la precisión que se
busque o del número de
opciones que se tengan como
posibles.
www.themegallery.com


www.themegallery.com
Al principio y tratándose de
una población grande, los
cromosomas se crean al azar.
Una
solución
que
busquemos, por ejemplo 23,
representada por 6+5*4/2+1
se representaría así:
PRUEBA
Se le asigna una puntuación
Se prueba el cromosoma en
por ello
solución al problema
SELECCIÓN
Tomar dos miembros de la
Método de la ruleta
población actual
CRUCE
Tasa de cruce depende del número de bits del cromosoma
MUTACIÓN
La tasa de mutación depende del paso
www.themegallery.com


Es un método para elegir
a los miembros de la
población
de
los
cromosomas
de
una
manera
que
sea
proporcional a su aptitud.
Ello no garantiza que el
miembro más fuerte pase
a la siguiente generación,
pero tiene una buena
oportunidad de hacerlo.
www.themegallery.com


Corresponde
a
la
posibilidad de que
dos cromosomas se
intercambien sus bits.
El cruce se realiza
mediante la selección
de un gen al azar a lo
largo
de
los
cromosomas
y
el
intercambio de todos
los genes después de
ese punto.
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-.
Tratándose
de
genes
codificados con números
binarios el valor de la
tasa de mutación suele
ser bajo
www.themegallery.com
0
1
1
0
PRUEBA
MUTACIÓN
SELECCIÓN
CRUCE
www.themegallery.com
Los pasos b,c,d se repiten
hasta que una nueva
población de los miembros
de n se ha creado.
Cada
uno
de
los
algoritmos
genéticos
representa una posible
solución al problema que
se desea resolver. Todo
individuo tiene asociado
un ajuste de acuerdo a la
bondad con respecto al
problema de la solución
que representa, a ese
ajuste de cada individuo
se le llama Algoritmo
principal.
www.themegallery.com
La reproducción de
los algoritmos se
puede hacer a
través de:
 Cruce: Trata de una
reproducción de
tipo sexual
 Copia: Trata de una
reproducción de
tipo asexual.
www.themegallery.com
Del algoritmo principal
desarrollado por Holland
se han propuesta
distintas variaciones
para reemplazar una
población temporal,
esas variaciones son:
 Reemplazo de padres.
 Reemplazo de
individuos similares.
 Reemplazo de los
peores individuos.
 Reemplazo aleatorio.
 También denominado canónico es un tipo de
algoritmo, el cuál necesita una codificación o
representación del problema que resulte
conveniente para este, además requiere una
función de ajuste la cuál asigna un número real a
cada solución codificada.
 El resultado de la combinación de las anteriores
funciones será un conjunto de individuos (posibles
soluciones al problema), los cuales en la
evolución del Algoritmo Genético formarán parte
de la siguiente población.
www.themegallery.com
Representación binaria en la que el valor
de cada gen es 0 o 1.
Representación entera en la que cada gen
toma un valor numérico dentro del rango
de números enteros.
Representación real en la que cada gen
es un valor real.
www.themegallery.com
Se intuye que el trabajo
con poblaciones
pequeñas es riesgoso
al no cubrir al 100% el
espacio de búsqueda,
mientras que en
poblaciones grandes,
el riesgo es tener un
excesivo costo
computacional.
www.themegallery.com
 Goldberg concluyó que un
tipo de población de
tamaño L crece
exponencialmente con
codificación binaria, pero,
no sería muy aplicable a las
codificaciones de valor real.
 Alander sugiere una
población ideal entre 1 y 21
tipos, y cree que este rango
es suficiente para
solucionar los problemas
por él planteados.
Habitualmente la
población inicial se escoge
generando ristras al azar,
pudiendo contener cada
gen uno de los posibles
valores del alfabeto con
probabilidad uniforme.
www.themegallery.com
Si los individuos de la
población inicial se
obtienen por optimización
local, puede acelerar la
convergencia del
Algoritmo Genético.
Existen dos aspectos que resultan cruciales
en el comportamiento de los Algoritmos
Genéticos y son una adecuada función de
adaptación o función objetivo así como la
codificación utilizada.
www.themegallery.com
En un algoritmo genético tras parametrizar el
problema bajo una serie (Xi,..., Xn), se
codifican en un cromosoma. Todos los
operadores utilizados por un algoritmo genético
se aplicarán a estos cromosomas, o sobre
poblaciones de ellos.
Las soluciones codificadas en un cromosoma
compiten entre sí para ver cual constituye la
mejor solución al problema entre todas las
alternativas creadas.
www.themegallery.com
El algoritmo genético se usará para solucionar
solo una función y no solucionar diversas
funciones relacionadas entre sí
simultáneamente, a lo que se le
llama optimización multimodal.
Los algoritmos genéticos son programas
computacionales cuyo fin es imitar el proceso
de "selección natural" que, según la Teoría de
Darwin, rige el curso de la evolución.
www.themegallery.com
Este ciclo de creación
de las poblaciones a
lo podemos
evidenciar
generación tras
generación
Se tiene una
población,
y por consiguiente,
así estos nuevos
individuos capaces,
serán una nueva
población "mejore"
que la anterior.
www.themegallery.com
Esa población se
multiplica por medio
del intercambio de
genes
De la nueva
generación solo
sobrevivirán aquellos
capaces de adaptarse
al medio ambiente,
OPERACIONES DE SELECCIÓN

Es el encargado de transmitir y conservar aquellas características de
las soluciones que se consideran valiosas a lo largo de las
generaciones.
Selección
por ruleta
Selección
escalada
Selección
por torneo
www.themegallery.com
• La probabilidad que tiene un individuo de
reproducirse es proporcional a la diferencia
entre su aptitud y la de sus competidores.
• Al incrementarse la aptitud media de la
población, la fuerza de la presión selectiva
también aumenta y la función de aptitud se
hace más discriminadora.
• Se eligen subgrupos de individuos de
la población, y los miembros de cada
subgrupo compiten entre ellos
OPERACIONES DE CRUCE

Es una estrategia de reproducción sexual.
Los genes de los
padres son
intercambiados de
forma aleatoria.
Se establece 1
punto de
intercambio en un
lugar aleatorio del
genoma
www.themegallery.com
Se establecen 2
puntos de
intercambio en un
lugar aleatorio del
genoma
OPERACIONES DE REEMPLAZO
Cuando se trabaja con una sola población, 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 población:

Aleatorio.

Reemplazo de padres.

Reemplazo de similares.

Reemplazo de los peores
www.themegallery.com
OPERACIONES DE COPIA
Se trata de una estrategia de reproducción asexual
OPERACIONES DE MUTACIÓN
Provoca que alguno de sus genes, generalmente uno sólo, varíe su valor
de forma aleatoria.
www.themegallery.com
Los algoritmos genéticos explotan un sinnúmero
de soluciones
Los algoritmos genéticos están íntimamente
relacionados,
pues
operan
de
forma
simultánea con varias soluciones.
Poseen habilidad para manipular
parámetros simultáneamente
muchos
No necesitan tener un conocimiento previo para
resolver un problema
www.themegallery.com
El lenguaje que se debe utilizar debe tener la
capacidad de tolerar cambios aleatorios
Puede demorarse bastante en converger o
no en absoluto
Pueden converger prematuramente debido
a una serie de problemas.
(Este problema se presenta en poblaciones
pequeñas, donde una variación aleatoria en el
ritmo de reproducción provoca que un genotipo
se haga dominante sobre los otros.)
www.themegallery.com
• El desarrollo de los Algoritmos
Genéticos se debe en gran
medida
a
John
Holland,
investigador de la Universidad de
Michigan. A finales de la década
de los 60 desarrolló una técnica
que imitaba en su funcionamiento
a la selección natural. Aunque
originalmente esta técnica recibió
el
nombre
de
planes
reproductivos, a raíz de la
publicación en 1975 de su libro
``Adaptation in Natural and
Artificial Systems” se conoce
principalmente con el nombre de
Algoritmos Genéticos.
www.themegallery.com
www.themegallery.com
La Ruleta : Es el usado por Goldberg en su libro [4]. Este método es muy simple, y
consiste en crear una ruleta en la que cada cromosoma tiene asignada una
fracción proporcional a su aptitud. Sin que nos refiramos a una función de aptitud
en particular, supongamos que se tiene una población de 5 cromosomas cuyas
aptitudes están dadas por los valores mostrados en la Tabla 1.
Cromosoma
No.
Cadena
Aptitud
% del Total
1
11010110
254
24.5
2
10100111
47
4.5
3
00110110
457
44.1
4
01110010
194
18.7
5
11110010
85
8.2
1037
100.0
TOTAL
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 seleccionarán. Debido a que a los individuos más aptos se les asignó
un área mayor de la ruleta, se espera que sean seleccionados más veces que los
menos aptos.
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 México se decide iniciar una vigorosa
campaña comercial: México 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 función 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
cálculos, supondremos que las asignaciones de créditos o de
inversiones deben hacerse por unidades de 1 millón de pesos. La
pregunta es: ¿en dónde se deben de asignar los 10 millones de pesos
de los que se dispone para que la ganancia total sea máxima?
www.themegallery.com
1) Representación : Lo primero que necesitamos determinar para poder
aplicar el algoritmo
genético, es cuál será el esquema a utilizarse para representar las posibles
soluciones del
problema. En este caso necesitamos 4 bits (24 = 16) para representar
cada solución, porque cada una admite 11 valores posibles (de 0 a 10).
Como existen 4 valores independientes (uno por cada zona de
estudio), se requieren entonces 16 bits (4 x 4) por cada cromosoma.
De tal forma, una cadena representativa de un cromosoma será como
se muestra en la Figura 4. Es importante hacer notar que se requiere
una función de codificación (i.e., que transforme el valor de la
inversión a binario) y una de decodificación (i.e., que realice el proceso
inverso). Debido a que en este caso los 4 bits utilizados para
representar una solución pueden producir más valores de los que se
necesitan, se usará una función de ajuste que haga que los resultados
producidos siempre se encuentren en el rango válido.
www.themegallery.com
Inversión
(en
millones)
Beneficio
I
Beneficio
II
Beneficio
III
Beneficio
IV
0
0
0
0
0
1
0.28
0.25
0.15
0.20
2
0.45
0.41
0.25
0.33
3
0.65
0.55
0.40
0.42
4
0.78
0.65
0.50
0.48
5
0.90
0.75
0.62
0.53
6
1.02
0.80
0.73
0.56
7
1.13
0.85
0.82
0.58
8
1.23
0.88
0.90
0.60
9
1.32
0.90
0.96
0.60
10
1.38
0.90
1.00
0.60
www.themegallery.com
2) Función de Aptitud : Dado que el objetivo es obtener
las inversiones que sumen 10, y que
tengan un beneficio máximo, podemos usar la
siguiente función 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. Nótese que cuando no
se viole ninguna restricción (i.e., cuando la suma de
inversiones sea exactamente 10) la función de aptitud
no será "castigada“.
www.themegallery.com
3) Operadores : Se usará una cruza de 2
puntos, la cual se efectúa 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
mutación, se le asignará una probabilidad
baja, tal y como sugiere Goldberg [4], por lo
que será del orden del 1%.
El tamaño de población manejado para este
ejemplo será de 50 cromosomas, y se
correrá el
algoritmo genético durante 20 generaciones.
www.themegallery.com
4) Resultados : El resultado obtenido en una corrida
típica es de $1.81 (en millones de pesos),
correspondiente a los valores de C1=4 millones, C2=3
millones, C3=1 millón y C4=2 millones. Esta es la
solución óptima, la cual se obtuvo originalmente
mediante programación dinámica [13]. El tiempo que
le tomó al algoritmo genético encontrar este valor fue
de sólo 13 segundos3. Debe hacerse notar que, en
este caso, si deseáramos analizar inversiones que
sumen otra cantidad, y en unidades menores al millón,
el algoritmo genético tendría que modificarse de
manera mínima, mientras que la programación
dinámica requeriría una cantidad tal de trabajo que
prácticamente se volvería inoperante.
www.themegallery.com
www.themegallery.com
www.themegallery.com
www.themegallery.com
L/O/G/O