Post on 19-Feb-2015
transcript
Caratula
Agenda
• Definición de Problema
• Definición de Solución
• Soluciones Propuestas– Algoritmo Voraz– Algoritmo Grasp– Algoritmo Genético
• Comparación de soluciones
• Conclusiones
Definición de Problema
“Evaluación y Selección de proyectos de inversión para entidades financieras”
Definición de Solución
Soluciones Propuestas
Algoritmo Voraz
Algoritmo Grasp
Algoritmo Genético
Portfolio Selection Problem
Algoritmo Genético
Inicio
Creación de Población
Selección
Criterio de Parada?
Cruzamiento
Mutación
No
Evaluación
Resultados
Si
Flujo de Genético
Algoritmo Genético
Población inicial = Población inicial de POSIBLES SOLUCIONES
Cromosoma1 Cromosoma2
Cromosoma3 Cromosoma4
Cromosoma5Cromosoma..
CromosomaX
Forma de generación:
- Aleatorio
- Grasp
Paso 1: Generar Población Inicial
Algoritmo Genético¿Cómo representa el cromosoma nuestro resultado?
1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 0
Consideraciones:
- Cartera de 5 proyectos
- Presupuesto total M
P1 P2 P3 P4 P5
000
001
010
011
100
111
110
101
1 1 1 0
1: Incluido
0: NO incluido110 = 6 en binario
001
010
011
100
111
110
101
Algoritmo GenéticoCada posición expresa el inicio de la porción que le
corresponde al proyecto en la circunferencia
000
P4
P1 P2
P3P5
Porción P4 : 1
Porción P1 : 1
Porción P2 : 2
Porción P3 : 1
Porción P5 : 3
Del Total = 8
Pesos
0.125 = 12.5% de M
0.125 = 12.5% de M
0.25 = 25% de M
0.125 = 12.5% de M
0.375 = 37.5% de M
100% = M
Cada peso expresa cuanto dinero del presupuesto esta asignado a un proyecto.
Algoritmo Genético
Paso 2: Selección
Se eligen los individuos aleatoriamente para realizar las recombinaciones y generar la siguiente generación.
Algoritmo Genético
Paso 3: Operadores de Recombinación
Algoritmo Genético
Paso 4: Supervivencia o Evaluación
La selección de los mejores requiere de una evaluación de la bondad o adaptabilidad del cromosoma.
Esto se realiza usando la función de Fitness, que para este caso es planteada de la siguiente forma.
( )( ) ( * )
rE r E r
pp p2
Factores del usuario:Ƴ : Factor de fitnessα : Factor de aversión al riesgo δ : Factor de retorno
Algoritmo GenéticoEnfoque Markowitz del problema:
“Teoría Media-Varianza”
- Flujo de Caja
- Ingresos y Egresos
- Monto Requerido
Escenarios (5)Proyecto
o
Acción
0%
25%
50%
75%
100%
Rendimiento
-TIR-VAE-PRI-BC
-TIR-VAE-PRI-BC
-TIR-VAE-PRI-BC
-TIR-VAE-PRI-BC
-TIR-VAE-PRI-BC
b1
b2
b3
b4
b5
Media
Varianza
r1 = 1/5 * ∑ bi Donde i= 1..5
s1^2 = 1/5* ∑(bi-r1) ^2Donde i= 1..5
Mayor
Ganancias
Menor
Riesgo
Algoritmo Genético
Proyectos 1 2 3 4 5 … n
ri r1 r2 r3 r4 r5 … rn
si s1 s2 s3 s4 s5 ... sn
Covarianza entre proyectos 1 2 3 … n
1 c11
2 c21 c22
3 c31 c23 c33
… … … …. …
n cn1 cn2 cn3 … cnn
Para una Cartera de Proyectos:
Algoritmo GenéticoUna población:
Datos Cartera:
…
Por cromosoma tendremos los siguientes indicadores:
( )( ) ( * )
rE r E r
pp p2
Algoritmo Genético
Paso 3: Eliminando Aberraciones
- Un hijo generado debe ser diferente de su padre.
- No deben existir clones.- No debe de existir dos proyectos con la
misma dirección incluidos en la cartera.
Comparaciones
Conclusiones