Algoritmos Inteligentes en Optimización de Carteras

Patricio Gálvez G pgalvez@ubiobbio.cl Mauricio Gutiérrez U mauricio.g@ubiobio.cl

Erick Torres M erick@moosoolwon.cl

Resumen

En este trabajo se hace una presentación del modelo Markowitz ,como un modelo de Programación Multiobjetivo, incorporando nuevas restricciones propuestas para representar mejor el problema a modelar , luego se propone como como diversas propuestas de Algoritmos Evolutivos, pueden ser utilizadas para resolver este problema. Se propone como este puede ser usado en el caso del modelo provisional chileno un trabajo actualmente en ejecución.

Palabra clave: Optimización en Finanzas, Modelo de Markowitz, Programación Multiobjetivo, Algoritmos Evolutivos, Algoritmos Genéticos 1.- Introducción En el campo de la teoría de selección de carteras, ocupa un lugar destacado Harry Markowitz [13] [14] que en 1952 publico en la revista Journal of Finance el articulo “Portafolio Selection”. El modelo planteado es considerado como un gran aporte a nivel teórico, sin embargo su utilización en la práctica entre los gestores de carteras no es comparable con su éxito teórico. Una de las causas radicaba en la complejidad matemática del modelo por ser este un modelo cuadrático, parametrico y con un el elevado numero de estimaciones de rentabilidades esperadas, varianzas y covarianzas, de ahí que generalmente se usen las simplicaciones planteadas por F Sharpe que dan una gran simplicacion en el calculo. Sin embargo , hoy en día las Tecnologías de Información y nuevos enfoques algorítmicos permiten no solo resolver el modelo planteado inicialmente , sino además que incorporar nuevas propuestas de mejoramiento del modelo , que exprese en forma mas fidedigna la realidad en el problema de selección de carteras que contribuirá a suplir los inconvenientes para su utilización En el articulo, exponemos una nueva forma de plantear el Modelo de Markowitz que es a través de la Programación Multiobjetivo y cuya solución sea realiza con técnicas de optimización evolutiva multiobjetivo[3][4], que hace uso de variaciones de la meta heurística de algoritmos genéticos especializados con el objetivo de encontrar una buena aproximación del frente de Pareto En el articulo se presenta primeramente el modelo de Markwitz planteado originalmente, posteriormente se muestran los elementos básicos de Programación Multiobjetivo, para después dar una visión de los que se denominan

Algoritmos Inteligentes y como bajo estos nuevos enfoques se puede replantear el modelo de Markowitz y las ventajas de esta forma de resolución 2.-El Modelo de Markowitz El origen de los conceptos de la teoría de cartera asocia riesgo y rendimiento e introduce conceptos como rendimientos esperados y medidas de dispersión en la distribución de los mismos, así como la covarianza entre los rendimientos esperados de dos títulos. Markowitz desarrolla su modelo sobre la base del comportamiento racional del inversor .Es decir, el inversor desea la rentabilidad y rechaza el riesgo. Así una cartera será eficiente si proporciona la máxima rentabilidad posible para un riesgo dado, o de forma equivalente, si presenta el menor riesgo posible para un nivel determinado de rentabilidad [15]. Lo anterior se puede expresar en el siguiente modelo matemático

1 1

1

1

2min

[ ] ( ) *

1

0

n n

i ji i

n

p i ii

n

ii

i

w wp

sa

E R w E R R

w

w

ijσ σ= =

=

=

= ×

= =

=

≥

∑ ∑

∑

∑

×

Donde es la proporción del ,presupuesto del inversor destinado al activo financiero i, la varianza de la cartera p,

iw2 ( )pRσ ijσ la covarianza entre los

rendimientos de los valores i y j, E( pR ) es la rentabilidad o rendimiento esperado de la cartera p, de tal forma que al variar el parámetro V* obtendremos en cada caso , al resolver el programa , el conjunto de proporciones wi que minimizan el riesgo de la cartera . De esta manera el conjunto de pares [ ] o combinaciones rentabilidad-riesgo de todas las carteras eficientes es denominado “ frontera eficiente”. Una vez conocida esta, de acuerdo con sus preferencias, elegirá su cartera óptima.

2( ), (pE R Rσ )p

De forma análoga, el conjunto de portafolios eficiente puede ser obtenido solucionando el problema dual

1

2

1

( ) ( )

*

1

0

n

p ii

p

n

ii

i

iMaxE R w E R

saV cte

w

w

σ

=

=

= ×

= =

=

≥

∑

∑

3.- Optimización Multiobjetivo La programación Multiobjetivo, según Osczka se define como [17] “El problema de encontrar un vector de variables de decisión que satisfaga ciertas restricciones y optimice una función vectorial cuyos elementos representen las funciones objetivo. Estas funciones forman una descripción matemática de los criterios de desempeño que usualmente están en conflicto entre si y que se suelen medir en unidades diferentes. Por lo tanto, el termino optimizar significa encontrar una solución tal que proporcione valores para todos los objetivos que resulten aceptables para el diseñador” El problema de optimización multiobjetivo (POM) se define formalmente como: Encontrar el vector * * * *

1 2, ,........,T

nx x x x⎡ ⎤= ⎣ ⎦uur

que satisfaga las m restricciones de desigualdad: ig ( ) 0x ≤

r 1, 2,..........i m=

que satisfaga las p restricciones de igualdad ( ) 0ih x =

r 1, 2,.......i p=

y optimice la función vectorial 1 2( ) [ ( ), ( ),....... ( )]T

kf x f x f x f x=ur r uur r r

donde: [ 1 2, ,......... Tn ]x x x x=

r es el vector de variables de decisión.

Las restricciones definen la región factible F y cualquier punto en F forma parte de la solución factible

Optimizar varias funciones objetivos a la vez, no se traduce en encontrar un optimo para cada función, sino en proponer un conjuntos de puntos en lo que cada

función objetivo contribuya en alcanzar una buena aptitud global, la cual será establecida y evaluada por el diseñador, un inversionista en nuestro caso Por simplicidad en la implementación normalmente todas las funciones son convertidas una misma forma, a fin de minimizar o maximizar todas las funciones del problema. Así el concepto de óptimo que se maneja en PMO es distinto al de una sola función objetivo y es el de un buen compromiso entre toda las variables que sastifacen las restricciones, es una solución global de la optimización. Esta noción de “optimo” fue propuesta originalmente por Francis Isidro Edgeworth en 1881 y luego generalizada por Wilfredo Pareto in 1986 y conocida como el óptimo de Pareto y su definición formal es la siguiente Definición 1 (Optimo de Pareto) Dadas k funciones objetivo del problema decimos que un punto *x F∈

uur es un optimo

de Pareto si para toda x F∈r

, tal que para toda i=1,2…. k *( ) ( )i if x f x≤

uur r

y, al menos existe una i tal que ( )if x

r < ( )if x

r

Esta definición dice que *x

uur es un optimo de Pareto si no existe dentro del espacio de

búsqueda F un vector factible xr

que mejoraría algún criterio sin hacer que empeore en al menos otro de ellos, es decir que lo domine, por lo que se le conoce a *x

uur como una

solución no dominada. Otras importantes definiciones asociadas al óptimo de Pareto son las siguientes Definición 2 Dominancia de Pareto Un vector 1( ,........ )Ku u u=

r se dice que domina al vector

denotado por u si y solamente si es parcialmente menor que v, es decir 1( ,.......... )kv v v=

r

vr rp

{ }{1,......... }, 1,...., :i i ii k u v i k u v∀ ∈ ≤ ∧∃ ∈ < i El óptimo de Pareto casi siempre produce no una, sino un conjunto de soluciones a las que se llama no dominadas Definición 3 Conjunto de Óptimos de Pareto Dado un PMO ( )f x

ur r, el conjunto de óptimos de Pareto se define como: trueP

{ }´: : ( ´) (trueP x F x F f x f x= ∈ ¬∃ ∈ )urr ur u

pr

A partir de la definición 3 se define el Frente de Pareto. que no es otra cosa que el contradominio del conjunto de puntos que forman el conjunto de óptimos de Pareto. Es decir el frente de Pareto son los valores de las funciones objetivo correspondientes a las soluciones que pertenecen al conjunto de óptimos de Pareto.

Resulta imposible determinar de manera analítica la expresión matemática que corresponden al frente de Pareto de un problema arbitrario. Aproximar dicho frente es precisamente el objetivo de la optimización multiobjetivo 4.- Optimización y Algoritmos Inteligentes La tendencia de las investigaciones en el área de la Inteligencia artificial han derivado en métodos de búsqueda de exploración que son un símil con modelos biológicos y físicos que permiten resolver problemas de optimización, a continuación haremos una reseña que puede ampliarse en [16] [10] [18] La Computación Evolutiva (CE) es un enfoque alternativo para abordar problemas de búsqueda y aprendizaje a través de modelos computacionales de procesos evolutivos implementado a través de algoritmos evolutivos ( AEs). El proceso genérico de los AEs consiste en guiar la búsqueda estocástica haciendo evolucionar a un conjunto de y seleccionar de modo iterativo las mas adecuadas: La CE forma parte a su vez de un conjunto de metodologías de resolución de problemas que remedan con mayor o menor exactitud, como las Redes Neuronales [8] la Solidificación Simulada o Simulated Anealing [10]: todas ellas se engloban bajo el termino Computación Natural. En general, se llama Algoritmo Evolutivo a cualquier procedimiento estocástico de búsqueda basado en el principio de evolución. Dicho principio tiene una doble vertiente: la finalidad última es la supervivencia del más apto, el modo de conseguirlo es por adaptación al entorno. Concretamente, al implementar un algoritmo a una población de individuos que representan un conjunto de candidatos a soluciones de un problema, esta es sometida a una serie de transformaciones con las que actualiza la búsqueda y después a un proceso de selección que favorece a los mejores individuos: Cada ciclo de transformación +selección constituye una generación. Se espera del AE que, tras cierto numero de generaciones (iteraciones) el mejor individuo este razonablemente próximo a la solución buscada. Para simular el proceso de evolución, un AE requiere de: 1:- Una población de posibles soluciones debidamente representadas a través de individuos 2.- Un procedimiento de selección basado en la aptitud de los individuos. 3:- Un procedimiento de transformación, esto es, de construcción de nuevas soluciones a partir de las disponibles actualmente. Los Algoritmos Genéticos que se han desarrollado bajo el esquema evolutivo, hace evolucionar una población inicial que esta codificada como enteros binarios sometiéndola a transformaciones unitarias y binarias genéricas y a un proceso de selección. Así dentro de la implantación de un algoritmo genético es crucial definir el proceso de selección (como muestrear de la población), el proceso de reproducción que hacen uso de lo operadores genéticos, los mas conocidos son el de cruce y la mutación y el proceso de reemplazo.

Existen otros algoritmos inteligente (también conocidos como Meta heurísticas) que han sido utilizados para resolver problemas de Optimización como Búsqueda Tabú [9][10] y MetaRaps [7 ] 5.- Tratamiento de Problemas Multiobjetivo con Técnicas Evolutivas El área de investigación nombrada optimización evolutiva multiobjetivo, se basa en la búsqueda de soluciones utilizando un AE como una forma alternativa para resolver problemas que presentan varios objetivos a la vez. La primera implementación de un algoritmo evolutivo multiobjetivo fue Vector Evaluated Genetic Algorithm (VEGA) [19]. Que corresponde a la primera generación de algoritmos de este tipo entre cuales se cuenta también NSGA [6], NPGA[9] y MOGA[10]. La implementación del mecanismo de elitismo en el contexto de optimización multiobjetivo, que normalmente es implementado a través de una población secundaria en la que se almacenan los individuos no dominados encontrados durante el proceso de búsqueda (esto es introducen historia). Dentro de los algoritmos de segunda generación nos interesan por su buen comportamiento y aplicaciones en el área de las Finanzas [ 1 ] el NSGA II [21 ] y Micro-AG [5] 6.- Modelo de Markowitz como Problema de Programación Multiobjetivo El modelo de Media- Varianza de Markowitz (MV) se define a partir de su formulación inicial presentadoa en el apartado 2 considerando la optimización simultánea de dos funciones objetivo Rendimiento del portafolio

Max 1

( ) (n

p ii

)iE R w E=

= ×∑ R

j

Riesgo del Portafolio

2

1 1

1

.

1

0

n n

p i j ij ii j

n

ii

i

Min w w

s a

w

w

σ ρ ρ ρ= =

=

= × × ×

=

≥

∑∑

∑

×

donde se ha introducido la relación De una revisión de las referencias bibliograficas de la aplicación del enfoque del paradigma evolutivo se plantean las dificultades y ventajas y desventajas de este.

La primera pregunta que surge, es por que no diseñar tan solo un algoritmo que solucione el problema cuadrático propuesto inicialmente por Markowitz al respecto Vedejaran y otros [22] señala que para un portafolio de tamaño n, el conjunto de datos de entrada es (2*n)+(n*(n-1)/2), por lo que si n es grande puede ser laborioso seguir la pista de todos los coeficientes de correlación, y se pueden generar problemas por restricciones de almacenamiento de memoria. Además y mas restrictivo que lo anterior que para resolver el problema, es necesario que la matriz de covarianzas sea positiva y si existen discrepancias numéricas( por ejemplo imprecisión por redondeo), esta suposición podría ser violada y no se podría resolver .Esta no es improbable con datos reales particularmente cuando n es muy grande, dado que las covarianzas son estimaciones de series de tiempo de los precios de los instrumentos financieros reales , las cuales no necesariamente satisfacen las restricciones especificadas a priori . Por otro lado existen como se planteo en la introducción, que el escaso uso del modelo a que este no considera aspectos entre otros como el costo de transacción por cambios en el portafolio y una mayor diversificación del portafolio. Para incorporar la diversificación del portafolio es necesario agregar la restricción { } max1,2,.... : ii n w∀ ∈ ≤W donde es una cte maxw La variante que considera el costo de transacción por cambios en el portafolio (rebalanceo), causa problemas al algoritmo cuadrático, cuestión que puede ser resuelta en el enfoque multiobjetivo introduciendo una tercera función objetivo a ser minimizada

costf = * 2

1(

n

i i ii

c w w=

× −∑ ) 0 donde : *iw R+∈ es el peso inicial del instrumento

financiero i en el portafolio que va a ser potencialmente cambiado i debido a transacciones por rebalanceo y la constante ic R∈ es el costo de transacción del instrumento financiero i. 7.- Consideraciones Finales Las técnicas que actualmente están en uso para abordar en general para problema de Finanzas y en particular de predicción de valores bursátiles están basadas en Redes Neuronales. El uso de Algoritmos Evolutivos es mucho mas recientes al 2002 se habían reportado 3 artículos referentes a optimización de portafolios [9 ] [2 ] [20] según Coello [3 ]. Respecto en particular al Modelo de Markwotiz se usa Programación Cuadrática y Técnicas de Montecarlo, Sin embargo al agregar nuevas condiciones al modelo estas podrían no ser computacionalmente no factibles. En la actualidad los autores se encuentran trabajando en la aplicación del modelo de Markowitz (con tres objetivos a optimizar) para el caso de las

inversiones de las AFP en Chile, para lo cual se implementara con el algoritmo micro AG [5] Otras posibles investigaciones es usar la Meta heurística de Simulated Annealing para problemas de Programación Multiobjetivo. Además es importante resaltar la convergencia de dos disciplinas como son las finanzas y los algoritmos, en una investigación intradiciplinaria. 8 Agradecimientos Este proyecto es financiado por un proyecto de investigación interna de la Universidad del Bio-Bio, lo cual ha permitido contar con los recursos y tiempo necesarios para desarrollar esta actividad académica. 9.- Referencias Bibliograficas [1] Castro S (Julio 2005) Creación de Portafolios de Inversión utilizando Algoritmos Evolutivos Mutiobjetivo. Tesis de Maestría en Ciencias Centro de Investigación y Estudios Avanzados del Instituto Politécnico Nacional México. [2] Chang T J;Meade N; Bealey J E (1998) Heuritcs for Cardinality Constrained Portfolios Optimization.Tecnical report, The Management School, Imperial College, London SW72A2 England. [3] Coello C; Van Veldhuizen D; Lamont G (2002) Evolutionary Algorithms for solving Multi-Objective Problems. Kluver Academic Publisher, New York ISBN 0-3064-6762-3 [4] Coello C; Lamont G editors (2004) Applications of Multi-Objective Evolutionary Algorithms Word Scientific Singapore [5] Coello C; Toscano G (2001) A Micro – Genetic Algorihm for Multiobjetive Optimizacion. First International Conference on Evolutionary Multi-Criterion Optimizacion .Springer –Verlag. Lecture notes in Computer Sciencies [6] Deb K; Amrit P; Agrawal S; Pratab A; Meyarivan (2002) A Fast and Elitist Multiobjetive Genetic Algorithm: NSGA II IEEE Transactions on Evolutionary Computation, 6(2) April 2002 [7] Depuy G W; Moraga R, Witehouse G E (2002)

Using the Meta-Raps Approach to solve Combinatorial Problems European Journal of Operational Research [8] Hertz J; Krogh R P; Palmer R (1991) Introduction to the Theory of Neural Computations Adisson Wesley [9] Horn J; Nafpliotis N;Goldberg D (1994) A Niched Pareto Genetic Algorithm for Multiobjetive Optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation [10] Fonseca C; Fleming P (1993) Genetic Algorithms for Multiobjetive Optimization: Formulation, Discussion and Generalization. IN Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms. University of Illinois at Urbana_Champaign,Morgan Kauffman Publishers. [11] Glover F; Laguna M (1997) Tabu Search Kluver Academic Pub [12] Pham D; Karaboga D (1998) Intelligent Optimization Techniques: Genetic Algorithms,Tabu Search, Simulated Annealing, and Neural Networks Springer Verlag [13] Markowitz H (1952) Portfolio Selection Journal of Finance Vol 7 N 1 Marzo [14] Markowitz H (1959) Porfolio Selection Efficient diversification of investments John Wiley & sons New York. [15] Mendizabal A; Meira L; Zubia M (2002) El modelo de Markowitz en la gestión de carteras Cuadernos de Gestión vol2 N 1 España [16] Michelwicz Z (1996) Genetic algorithms+ Data Structures= Evolutionary programs [17] Osyczka A (1984) Multicriterion optimization in engineering with Fortran Programs Ellis Horwood Limited [18] Torres E (Marzo 2005) Algoritmos Inteligentes Aplicados a Carteras de Inversión. Informe Proyecto de Titulo Ingeniería Civil Informática Departamento Sistemas de Información Universidad del Bio_Bio. [19] Shaffer J D (1985)

Multiobjetive Objetive Optimization with Vector Evaluated Genetic Algorithms.In Genetic Algorithms and their Applications: Proceedings of the First International Conference on Genetic Algorithms Lawrence Erbauln [20] Shoaf J S; Foster J A (1996) A Genetic Algorithms Solution to the Efficient Set Problem: A Technique for Portfolio Selection Based on the Markowitz Model. In Proceeding of the Decision Sciences Institute Annual Meeting Orlando Florida. [21] Srinivas N; Deb K (1994) Multiobjetive Optimization Using No dominated Sorting in Genetic Algorithms. Evolutionary Computation 2(3). [22] Vederajan G; Chi Chan L; Goldberg (1997) Investment portfolio optimization using genetic algorithms. In John R Koza, editor, Late Breaking Papers at the 1997 Genetic Programing Conference Sandford University, CA;USA