optima-cityu Multi-objective Evolution of Heuristics (MEoH) Skill
Paper: Yao et al., "Multi-objective evolution of heuristic using large language model", AAAI 2025.
1. Method Essence
MEoH extends EOH's evolutionary operators (E1/E2/M1/M2) to multi-objective scenarios: individuals are evaluated with multiple objective vectors, Pareto non-dominated sorting determines selection pressure, and a non-dominated archive maintains the historical best front. The LLM sees multiple representative individuals from the front during generation, accommodating different objective preferences.
Key differences from single-objective EOH:
- Selection is based on domination + crowding, not a single score
- Front diversity must be maintained: both ends and the middle of the front must have representatives
- Archive individuals can be "resurrected" for crossover (even if not in the current population)
2. Recommended Parameters
See params.yaml in this directory for the recommended parameter configuration.
Note: The number of objectives is determined by the length of objective_metrics, not a separate num_objs parameter.
What Happens During Evolution
- Population initialized; evaluate all individuals
- Each generation:
- Identify non-dominated front (Pareto front)
- Archive front members
- Generate offspring via LLM operators, using front members as parents
- Evaluate offspring
- Merge offspring into population
- Non-dominated sorting + crowding distance truncation
- Archive grows as better front members are found
- Final archive contains the best Pareto front discovered
Common Pitfalls
- Front not diverse → increase
population_sizeor force exploration at front ends - Archive too large → increase crowding pressure; archive pruning is automatic
- Convergence slow → check if objectives are truly conflicting; some problems may be easier with single-objective
- Front biased toward one objective → manually set extreme weight vectors as seeds
4. Acceptance Criteria
- Non-dominated front identified and archived
- Front covers both objective extremes and balanced trade-offs
- Archive members used as parents for crossover (not just current population)
- Crowding distance prevents front collapse
- Final archive represents the full Pareto front