Abstract
Multi-Objective Combinatorial Optimization (MOCO) problems are notoriously difficult due to the exponential growth of the Pareto set and the challenge of eliciting decision-maker (DM) preferences. This paper presents RIGA (Regret-based Interactive Genetic Algorithm), a novel approach that interleaves a genetic algorithm with an interactive query process. Unlike traditional methods, RIGA evolves a population of preference parameters rather than solutions. By utilizing minimax regret to guide the search and query process, RIGA efficiently identifies near-optimal solutions. Experimental results on the Multi-objective Traveling Salesman Problem (MTSP) demonstrate that RIGA scales to large instances with up to 7 objectives, maintaining low error rates with minimal user interaction.
Introduction
In many real-world scenarios, such as logistics and network design, decision-makers must balance multiple conflicting objectives. Finding a single "best" solution is challenging because the set of Pareto-optimal solutions—those where no objective can be improved without degrading another—can be overwhelmingly large. Furthermore, the precise weights a decision-maker assigns to different objectives are often unknown a priori.
Existing approaches typically separate the search for Pareto solutions from the elicitation of user preferences. This separation can lead to computational inefficiency or a high cognitive load on the user. RIGA addresses these issues by integrating preference learning directly into the optimization search.
Methodology: The RIGA Algorithm
RIGA introduces several key innovations to handle MOCO problems:
1. Evolving Preference Parameters
Standard Genetic Algorithms (GAs) evolve a population of solutions. In contrast, RIGA evolves a population of preference parameters ($\omega$). Each individual in the population is represented as a pair ($\omega, x_\omega$), where $x_\omega$ is the optimal solution for the specific weight vector $\omega$. This ensures that every solution considered is Pareto-optimal for some set of weights, avoiding the exploration of dominated solutions.
2. Regret-Based Selection and Queries
To guide the evolution, RIGA employs the Minimax Regret criterion. Regret measures the maximum possible loss a DM might experience by choosing a specific solution given the current uncertainty about their preferences. The algorithm selects "parents" for the next generation based on their ability to minimize this regret.
3. Incremental Elicitation
Periodically, RIGA pauses the search to ask the DM to compare two solutions. The DM's response provides a linear constraint on the possible values of $\omega$, effectively shrinking the search space to regions the user prefers.
Experimental Evaluation
The researchers evaluated RIGA using the Multi-objective Traveling Salesman Problem (MTSP) with 50 and 300 cities and 3 to 7 objectives. The performance was measured in terms of computation time, the number of user queries required, and the optimality gap (error).
Key Results
- Scalability: RIGA handles high-dimensional objective spaces effectively. For 7 objectives, it maintains an error rate around 1% while remaining computationally feasible.
- Efficiency: Compared to exact methods like IEEP, RIGA is significantly faster. While IEEP provides zero error, it fails to scale beyond 5 objectives due to exponential time complexity. RIGA, as a polynomial-time heuristic, provides a practical alternative for large-scale problems.
- Query Economy: The algorithm requires very few interactions to converge. For a 300-city problem with 7 objectives, only approximately 25 queries were needed to reach a near-optimal solution.
Conclusion
RIGA represents a significant step forward in interactive multi-objective optimization. By evolving preferences and using regret-based heuristics, it bridges the gap between exact preference elicitation and metaheuristic search. Future work will explore extending RIGA to non-linear scalarizing functions and more complex genetic operators to further enhance its robustness and accuracy.
Summary updated