Abstract
Several real-world applications could be modeled as Mixed-Integer Non-Linear Programming (MINLP) problems, and some prominent examples include portfolio optimization, remote sensing technology, and so on. Most of the models for these applications are non-convex and always involve some conflicting objectives. The mathematical and heuristic methods have their advantages in solving this category of problems. In this work, we turn to Multi-Objective Evolutionary Algorithms (MOEAs) for finding elegant solutions for such problems. In this framework, we investigate a multi-objective constrained portfolio optimization problem, which can be cast as a classical financial problem and can also be naturally modeled as an MINLP problem. Consequently, we point out one challenge, faced by a direct coding scheme for MOEAs, to this problem. It is that the dependence among variables, like the selection and weights for one same asset, will likely make the search difficult. We thus, propose a Compressed Coding Scheme (CCS), compressing the two dependent variables into one variable to utilize the dependence and thereby meeting this challenge. Subsequently, we carry out a detailed empirical study on two sets of instances. The first part consists of 5 instances from OR-Library, which is solvable for the general mathematical optimizer, like CPLEX, while the remaining 15 instances from NGINX are addressed only by MOEAs. The two benchmarks, involving the number of assets from 31 to 2235, consistently indicate that CCS is not only efficient but also robust for dealing with the constrained multi-objective portfolio optimization.
Introduction
Many real-world optimization problems require tuning both discrete (integer) and continuous variables simultaneously. A classic example is portfolio optimization: an investor must decide which stocks to buy (a binary yes/no decision) and what percentage of their capital to allocate to each (a continuous decision), all while balancing the conflicting objectives of maximizing return and minimizing risk.
When using Evolutionary Algorithms (EAs) to solve these problems, researchers typically use a "Direct Coding Scheme" (DCS). In DCS, a solution is represented by two separate vectors: a binary vector for asset selection and a real-valued vector for weights. However, this approach has two major flaws: it ignores variable dependence—where the optimal weight of an asset heavily depends on which other assets are selected—and it complicates search operators, which are usually designed for either purely continuous or purely discrete spaces.
The Compressed Coding Scheme (CCS)
To overcome the limitations of DCS, the authors propose a Compressed Coding Scheme (CCS). Instead of using a vector of length $2N$ (where $N$ is the total number of available assets), CCS uses a single real-valued vector of length $N$ with values between 0 and 1. This single vector handles both tasks simultaneously:
- Selection: The algorithm identifies the $K$ assets with the highest values in the vector.
- Weighting: It then takes those same $K$ values, normalizes them so they sum to 1, and assigns them as the portfolio weights.
By mapping a mixed-integer problem entirely into a continuous space, researchers can seamlessly apply decades of highly optimized continuous search operators (like Differential Evolution) without needing complex, custom-built hybrid operators. Furthermore, by grouping selection and weight into one "gene," the algorithm naturally preserves successful selection-weight pairings during the evolutionary process.
Experimental Setup
The algorithms were evaluated on 20 benchmark instances of varying sizes:
- OR-Library: 5 classic instances ranging from 31 to 225 assets (e.g., Hang Seng, DAX 100, S&P 500).
- NGINX: 15 recently established instances based on historical Yahoo Finance stock data, ranging from 91 up to a massive 2235 assets (e.g., NASDAQ, AMEX Composite).
CCS was integrated into three popular Multi-Objective Evolutionary Algorithm (MOEA) frameworks: MOEA/D, NSGA-II, and SMS-EMOA.
Results and Discussion
The empirical study yielded several key findings:
- Superior Accuracy and Robustness: CCS-enhanced MOEAs consistently outperformed Direct Coding Scheme (DCS) counterparts and the state-of-the-art baseline (MODEwAwL) in terms of Inverted Generational Distance (IGD) and Inverted Hypervolume (IH). They also showed significantly lower variance across multiple runs, indicating higher stability.
- Scalability: While exact mathematical solvers like CPLEX (using AUGMECON2) could solve small instances (<225 assets) quickly, they failed to process larger instances (up to 2235 assets), timing out after 7 days. In contrast, the CCS/MOEAs generated high-quality solutions for these massive instances in just 5 to 15 minutes.
Conclusion
The Compressed Coding Scheme demonstrates that treating variable dependence as a feature rather than a bug can significantly improve the performance of MOEAs on MINLP problems. While this study focused on portfolio optimization, the principles of CCS could potentially be applied to other mixed-variable domains such as drone path planning or satellite constellation scheduling. Future work will involve deeper theoretical analysis of how variable dependence affects search dynamics.
Summary updated