En este trabajo, se presenta bajo una perspectiva metaheurística el problema multiobjetivo para el portafolio de inversión, que debe minimizar el riesgo, y maximizar el rendimiento esperado. Considerando el modelo de Markowitz se resuelve el problema con dos objetivos describiendo la totalidad del frente de Pareto correspondiente. En este trabajo, se emplean cuatro técnicas metaheurísticas: SPO, NSGA-II, MOEA/D y VEGA y se efectúa un análisis comparativo sobre cinco instancias de investigación en mercados financieros de Hong Kong (Hang Sen31), Alemania (DAX85), Gran Bretaña (FTSE89), Estados Unidos de América (S&P98) y Japón (Nikkei225) empleando una base de datos de marzo de 1992 a septiembre de 1997.
In this paper, the multiobjective problem for the investment portfolio is presented under a metaheuristic perspective, which refers to minimize de risk and maximize the expected return. Considering the Markowitz model, the problem is solved with two objectives describing the whole of the corresponding Pareto front. Four metaheuristic techniques are used: SPO, NSGA-II, MOEA/D Y VEGA and a comparative analysis is carried out on 5 research instances in financial markets of Hong Kong (Hang Sen31), Germany (DAX85'),Great Britain (FTSE89), United States of America (S & P98) and Japan (Nikkei225)using a database from March 1992 to September 1997.
El problema del portafolio de inversión fue estudiado y formulado por
El presente artículo se organiza como se describe a continuación: en la siguiente sección se proporciona el marco teórico, relacionando el problema de inversión con el área de optimización muítiobjetivo. En la sección 2, se incluye el desarrollo de los métodos para la selección de poblaciones no dominadas, así como la descripción de las características y el modo operativo de las metaheurísticas manejadas. La sección 3 presenta la implementación del ajuste de parámetros, se presentan las métricas que se adoptaron. Finalmente, en la sección 4 se presentan la parte experimental de la implementación de los algoritmos con los parámetros ajustados, así como representaciones gráficas del desempeño que permiten interpretar rápidamente los resultados.
Para evaluar la confianza y eficiencia de las técnicas implementadas, existen varios bancos de instancias ya estudiados en la literatura especializada. En este proyecto, se propone trabajar con cinco mercados de capital propuestos en (
Para cada instancia se tiene la siguiente información de entrada: rendimiento promedio semanal de cada activo, desviación estándar del rendimiento semanal y matriz de correlación entre activos. Para evaluar las funciones objetivo solo faltan las covarianzas entre activos, las cuales serán calculadas de la siguiente manera:
ID
País
Instancia
Tamaño (N)
Hong Kong
Hang Seng31
31
Alemania
DAX85
85
UK
FTSE89
89
USA
S&P98
98
Japón
Nikkei225
225
Donde
Además se dispone de los frentes de Pareto reales de todas las instancias, lo cual es una ventaja para poder evaluar el desempeño de las técnicas de optimización probadas más adelante.
En la presente investigación el proceso de selección de activos para un portafolio será trabajado utilizando el modelo matemático propuesto por
En el marco de la presente investigación, estos valores establecidos serán denotados como metas y modificándolos, puede ser resuelto como un problema multiobjetivo o MOP (Multi Objective Problem).
El modelo de
Donde
Dado un MOP de la forma antes presentada, sea Ω ⊂ ℝn c Mn el espacio factible, decimos que una solución
Algunos autores llaman tales soluciones óptimo de Edgeworth-Pareto, pero es más común denominarla simplemente óptimo de Pareto, o soluciones Pareto-óptimas (
La presente investigación se concentrará en métodos para problemas continuos no lineales, los cuales, en el estado del arte, también son referidos como de optimización difícil, debido a que no existe algoritmo eficiente o método que pueda garantizar óptimos globales (
En esta sección se abordará una de las primeras propuestas para afrontar un problema de optimización muítiobjetivo. Se trata de una manera sencilla de plantear el problema desde la perspectiva monobjetivo e implementar una técnica clásica para resolverlo, en este caso un algoritmo genético (GA). Esta técnica constituye un buen punto de partida y de referencia para estudiar los alcances de otros métodos, médula de la presente investigación, los cuales fueron creados específicamente para atacar los problemas de interés en este proyecto.
Una función de agregación, suma lineal de pesos, combinación convexa o suma ponderada de objetivos (SPO), está definida por
Dado un vector de pesos
Donde Ω es el espacio factible, y
i) Para cada solución no dominada deseada, es necesario resolver un problema de optimización escalar, por lo que la aproximación del frente de Pareto aproximado requiere de múltiples ejecuciones del método de solución. ii) Debido a la reformulación del problema, no se pueden alcanzar regiones no convexas del frente de Pareto. iii) La selección adecuada de los vectores de pesos a utilizar es problemática, ya que, según la naturaleza (lineal o no) del problema, una distribución uniforme de dichos vectores no garantiza que las soluciones obtenidas se distribuyan uniformemente a lo largo del frente.
Una de las primeras propuestas hechas específicamente para MOPs es la estrategia Algoritmo Genético Evaluado por Vector-Objetivo (o VEGA, por las siglas en inglés de Vector Evaluated Genetic Algorithm), la cual fue presentada por
En la versión del algoritmo implementada en la presente investigación, es acertado destacar los siguientes dos puntos:
i) Se tiene como meta en un MOP determinar las soluciones no dominadas, en cada generación éstas tendrán la característica de que, por ser buenas en todos los objetivos, aparezcan en múltiples subpoblaciones y por ende tener mayor posibilidad de ser seleccionadas para cruza. ii) La etapa de creación de subpoblaciones permite especializar el proceso de optimización para objetivos aislados a continuación cuando las soluciones son combinadas, dado que hay un proceso de selección por medio de torneo binario, dentro de esta subetapa el elitismo por dominancia estará presente, lo cual le permitirá al algoritmo ser más dinámico.
El método Algoritmo Genético basado en Sorteo de Dominancia (o NSGA-II, por las siglas en inglés de Nondominated Sorting Genetic Algorithm)
fue propuesto por
El NSGA-II es una estrategia en la cual es crucial el concepto de dominancia de Pareto en la evolución de las poblaciones en el tiempo. De hecho, la clasificación de soluciones no dominadas implica un costo computacional relativamente muy alto. A grandes rasgos, las etapas que conforman esta estrategia se muestran en la
Esta métrica se usa en la estrategia NSGA-II para decidir, en el caso de que sea necesario, qué individuos del último frente capaz de completar una nueva generación deben ser seleccionados. La Crowding Distance (CD) es una aptitud asignada únicamente para los elementos del último frente que no fue posible añadir a la nueva generación, de acuerdo a la
Así pues, para el frente
El Algoritmo Evolutivo Multiobjetivo basado en Descomposición (MOEA/D, por las siglas en inglés de Multi-Objective Evolutionary Algorithm based on Decomposition) es una técnica propuesta por
Resolver problemas de optimización escalar en lugar de directamente el problema de optimización multiobjetivo (MOP por sus siglas en inglés) en su conjunto, puede implicar que, cuestiones tales como la asignación de la aptitud de las soluciones (también conocida como y el mantenimiento de la diversidad -que causan dificultades para otros MOEAs no basados en descomposición- podrían llegar a ser más fáciles de manejar en el marco de la técnica de este apartado.
MOEA/D tiene una menor complejidad computacional en cada generación que otras técnicas de optimización multiobjetivo, dado que no implica ningún proceso de clasificación de Pareto: usando una pequeña población es capaz de producir pocas soluciones finales muy uniformemente distribuidas. El ajuste de los vectores de pesos, representa sin embargo, una tarea difícil, particularmente para problemas de 3 o más objetivos.
Las etapas del algoritmo se enseñan en la
Existen distintas propuestas para efectuar la descomposición (o escalarización) necesaria para la implementación del MOEA/D. En la presente investigación se ha experimentado particularmente con una de las tres consideradas por (
Bajo ciertas condiciones de regularidad, el PF de un MOP (de maximiza-ción) continuo es parte de la frontera más alta a la derecha de un objetivo fijado a alcanzar. Geométricamente, estos enfoques BI tienen como objetivo, como su nombre lo indica, encontrar puntos de intersección entre el límite superior y un conjunto de líneas que emanan del punto ideal (denotado como z*). Si estas líneas están distribuidas de manera adecuada, se puede esperar que los puntos de intersección resultantes proporcionen una buena aproximación, uniforme, de la totalidad del PF. Cabe mencionar que este enfoque es capaz de aproximar FP no cóncavos (
Matemáticamente, se tienen los siguientes subproblemas de optimización escalar:
Donde el parámetro
Las relaciones de vecindad entre los sub-problemas se definen en función de las distancias entre vectores de pesos. Así pues, las soluciones óptimas a dos subproblemas vecinos deben ser similares. Cada subproblema (es decir, la función BI particular a un vector A) se optimiza en MOEA/D mediante el uso de la información sólo de sus subproblemas vecinos.
Es importante mencionar que la estrategia MOEA/D requiere además de un espacio de memoria o archivo de almacenamiento llamado
Particularmente, en la presente investigación se decidió considerar las siguientes métricas de desempeño, debido a que al tomarlas en cuenta se engloban las características necesarias para considerar una aproximación multiobjetivo de buena calidad.
La distancia generacional (
Donde
Llamada en inglés
Lo ideal, al igual que
Es definido como el área dominada por PFaprox, con respecto al espacio de los objetivos. Para dos objetivos, esto equivale a la sumatoria de todas las áreas rectangulares delimitadas por algún punto de referencia
Se intenta lograr que este valor sea el mayor posible para concluir que la aproximación es buena. La ventaja del uso del hipervolumen es que es una métrica compatible con la definición de optimalidad de Pareto (
En muchas aplicaciones (incluyendo la presente investigación) la magnitud en la que se mide la función objetivo suele variar en intervalos de reales numéricamente muy pequeños o muy grandes, lo cual dificulta el análisis comparativo y la observación de comportamientos para el hipervolumen. Para un mejor uso de tal métrica se definió una derivada de ésta a la cual se ha nombrado hipervolumen-percent y consiste en el porcentaje o proporción del hipervolumen del frente real que ocupa el hipervolumen aproximado usando el mismo punto de referencia para ambos frentes debido a que
Hasta este punto se han considerado dos métricas especializadas una en la convergencia, otra en la dispersión de forma uniforme, mientras que la tercera puede dar información sobre convergencia y dispersión. En este punto únicamente resta agregar que, para múltiples análisis, será importante conocer el número de puntos aproximados o cardinalidad del frente cercano.
Se decidió utilizar la configuración de parámetros, conocida como diseño factorial completo, el cual consiste en seleccionar un conjunto de valores potenciales para cada parámetro y probar todas las combinaciones de éstos (véase el ejemplo de la
Donde
Para realizar un análisis exhaustivo, es necesario hacer una delimitación del intervalo en el que varía cada parámetro. Dado que se debe seleccionar un número muy limitado de valores dentro de tales intervalos será necesario elegirlos de manera apropiada y, posteriormente profundizar la búsqueda en el intervalo para encontrar el valor más adecuado. Debido a esto, en la presente investigación se realizaron las etapas de calibración en dos fases llamadas: valores extremos y diseño factorial completo.
La etapa de experimentación para seleccionar el método de manejo de restricciones se realizó bajo las siguientes condiciones:
30 experimentos por técnica de manejo de restricciones, por meta-heurística y por instancia (instO = HangSeng31, instl = DAX85, inst2 = FTSE89, inst3 = S&P98, inst4 = Nikkei225). Análisis previo de ajuste de parámetros. Cruza y mutación en NSGA-II y MOEA/D se utiliza el método uniforme, mientras que a SPO y a VEGA les corresponde SBX. Criterio de paro: 1000 Archivo
En la etapa experimental de la selección de método de cruza y mutación se empezó a notar, a grandes rasgos, que los métodos de mejor eficiencia fueron NSGA-II y SPO. En la presente etapa experimental, antes de analizar los métodos de manejo de restricciones, será aprovechada la información obtenida, para hacer algunas conclusiones generales sobre la eficiencia de los algoritmos hasta este punto de la investigación. De acuerdo a la
Cada experimento realizado genera una aproximación del frente de Pareto de una instancia en particular, por lo cual no es posible presentarlos todos en el presente documento de forma gráfica. De modo que se enseñarán los frentes graficados correspondientes a la corrida mediana de cada estrategia en cada instancia de acuerdo a su desempeño en
Las métricas
De acuerdo a la métrica distancia generacional (
En las
estrategia
tiempo
hv_percent
moead
9.386440039
97.6147%
nsga2
10.27579498
96.5479%
spo
8.684428215
98.2979%
vega
9.466565847
89.2091%
estrategia
tiempo
hv_percent
moead
137.469667
95.8584%
nsga2
139.918093
97.0631%
spo
134.3552189
97.6835%
vega
137.5779932
87.5550%
estrategia
tiempo
hv_percent
moead
153.8806272
92.7641%
nsga2
150.2436111
94.9682%
spo
154.263298
97.2482%
vega
154.0000622
82.8718%
estrategia
tiempo
hv_percent
moead
201.986851
95.0938%
nsga2
198.9523768
95.7831%
spo
204.486424
98.1723%
vega
202.1144722
81.3964%
estrategia
tiempo
hv_percent
moead
2398.413085
91.4709%
nsga2
2289.414533
93.4996%
spo
2605.19272
98.4124%
Posición
estrategia
instancia
estrategia
instancia
estrategia
instancia
estrategia
instancia
1
SPO
inst4
SPO
inst4
SPO
inst4
SPO
instl
2
SPO
insto
SPO
instl
SPO
inst3
SPO
inst4
3
SPO
inst3
SPO
inst2
SPO
inst2
SPO
inst3
4
SPO
instl
SPO
inst3
SPO
instl
SPO
inst2
5
MOEA/D
insto
SPO
insto
SPO
insto
SPO
insto
6
SPO
inst2
NSGA-II
inst2
MOEA/D
insto
MOEA/D
insto
7
NSGA-II
instl
NSGA-II
instl
MOEA/D
inst2
MOEA/D
inst2
8
NSGA-II
insto
MOEA/D
inst2
MOEA/D
inst3
MOEA/D
inst3
9
MOEA/D
instl
MOEA/D
insto
NSGA-II
inst2
MOEA/D
instl
10
NSGA-II
inst3
MOEA/D
instl
NSGA-II
inst4
MOEA/D
inst4
11
MOEA/D
inst3
NSGA-II
inst4
MOEA/D
inst4
VEGA
insto
12
NSGA-II
inst2
MOEA/D
inst4
MOEA/D
instl
NSGA-II
inst2
13
NSGA-II
inst4
NSGA-II
insto
NSGA-II
inst3
NSGA-II
inst4
14
MOEA/D
inst2
NSGA-II
inst3
NSGA-II
instl
NSGA-II
inst3
15
MOEA/D
inst4
MOEA/D
inst3
NSGA-II
insto
NSGA-II
instl
16
VEGA
insto
VEGA
inst2
VEGA
inst4
NSGA-II
insto
17
VEGA
instl
VEGA
inst4
VEGA
inst2
VEGA
inst3
18
VEGA
inst4
VEGA
insto
VEGA
inst3
VEGA
instl
19
VEGA
inst2
VEGA
instl
VEGA
instl
VEGA
inst2
20
VEGA
inst3
VEGA
inst3
VEGA
insto
VEGA
inst4
Cabe mencionar que la métrica
Con respecto a los mejores resultados obtenidos, se logra superar a
Finalmente, para ilustrar lo que pueden ser unas de las soluciones no-dominadas identificadas por nuestros algoritmos, en el
En el presente artículo se estudió, adaptó e implemento un conjunto de metaheurísticas sofisticadas (
En el análisis de los métodos de selección de poblaciones no dominadas se logró destacar acerca de la relación entre comparaciones de dominancia y tiempo de ejecución, que no necesariamente guardan una relación directamente proporcional, es decir, un mayor uso de la operación de comparación, no implica necesariamente un mayor tiempo de ejecución (esto probablemente se debe a que, en el problema estudiado el número de objetivos es pequeño). En cuanto a la relación entre llamadas a la función objetivo para las metaheurísticas y el tiempo de ejecución, en la investigación fue ineludible tomar en cuenta la relación entre ambos factores. En el entorno multiobje-tivo las operaciones de clasificación de Pareto constituyen un elemento de gran relevancia, y son particularmente costosas aun tratándose de dos objetivos. Fue necesario mantener un límite de población bajo para el NSGA-II, para que el tiempo de ejecución no se elevara (
El método exhaustivo para el ajuste de parámetros, a pesar de tener un costo computacional elevado, fue posible implementarlo ejecutando un número relativamente bajo de pruebas para poder llegar a una configuración que garantizara buenos resultados. Analizar valores extremos para los parámetros fue interesante debido a que, no solo se delimitó un intervalo de búsqueda, sino que se examinaron valores poco convencionales en la práctica que, en algunos casos, fueron adecuados.
Se observó, en el transcurso de la investigación, que algunas veces es adecuado determinar si la heurística está utilizando tiempo innecesario (a partir de cierto tiempo ya no se puede mejorar, y no por la presencia de un óptimo local). Es decir, hay veces que el MOEA/D alcanza
No se esperaba que un Algoritmo Genético basado en una Suma Ponderada de Objetivos se mostrara como el de mayor eficiencia. Esto se debe, posiblemente a dos factores, el primero, el número de objetivos es bajo, y, por otro lado, los frentes reales son muy uniformes, sin discontinuidades y convexos.
Analizando la forma operativa de cada algoritmo, se abre pauta a concluir que hay factores dentro de éstos, que los deben hacen mejores al manejar las características particulares de cada instancia resuelta, la presente investigación abrió pauta al estudio a detalle de este aspecto como una perspectiva a futuro, inclusive cada estrategia que fue implementada, es sensible de diferente forma a cada uno de los parámetros calibrados. Aunque el tamaño de la instancia es crucial en la dificultad del problema, otras características del frente de Pareto también tendrán relevancia en la eficacia con la que particularmente cada estrategia resuelva el problema, y ese es un factor que no hay que perder de vista al elegir una técnica para resolver un MOP.
Cabe mencionar, que tampoco la diferencia de desempeño entre estrategias fue tan significativa. En general los resultados obtenidos son satisfactorios para MOEA/D, NSGA-II y SPO. La estrategia VEGA fue de las primeras propuestas para MOP, debido a esto, algoritmos más recientes logran superarla fácilmente. Sin considerar esta excepción, estas conclusiones validan la hipótesis de investigación del presente trabajo, es decir que los Algoritmos Evolutivos Multiobjetivo representan una opción viable para resolver el problema de Selección de Portafolios de Inversión. Se establece una clasificación de los algoritmos implementados en términos de la calidad de su desempeño, resultado de una etapa de calibración exhaustiva y realizada para las cuatro técnicas de interés.
1. Solución encontrada con la estrategia "NSGA-II" cerca de la "rodilla" del frente para la instancia 2 (FTSE89, Reino Unido). Nota: sólo se indican las variables estrictamente positivas.
0.073009922
0.016520877
0.183325563
0.423983624
0.009790336
0.191115913
0.038100786
0.016240054
0.047912925
Rendimiento esperado
0.00662809
Riesgo (varianza)
0.000572884
2. Solución encontrada con la estrategia "SPO", cerca de la "rodilla" del frente para la instancia 4 (Nikkei225, Japón). Nota: sólo se indican las variables estrictamente positivas.
0.29327773
0.12549203
0.34957127
0.03953417
0.1921248
Rendimiento esperado
0.003578485
Riesgo (varianza)
0.000682816