Skip to content
Back to search results

Multi-Objective Simulated Annealing (MOSA)

Introduced by
Serafini, P.; Czyzak, P. and Jaszkiewicz, A.
Year
1992–1998
Type
Metaheuristic / Pareto-based optimizer
Family
Simulation / optimization
Font size

What does it do?

Multi-Objective Simulated Annealing (MOSA) extends the classical simulated annealing metaheuristic to problems with two or more conflicting objective functions.

Instead of converging to a single optimum, MOSA explores the solution space stochastically and maintains an archive of non-dominated (Pareto-optimal) solutions, offering decision-makers a diverse trade-off front rather than one prescribed answer.

The intuition behind the method

Classical simulated annealing mimics the controlled cooling of metals to escape local optima — occasionally accepting worse solutions at high temperature, then becoming more selective as temperature drops. MOSA applies this same probabilistic escape mechanism across multiple objectives simultaneously. When a candidate solution worsens some objectives but improves others, dominance logic determines whether it enters the Pareto archive. The cooling schedule gradually reduces randomness, focusing the search near the Pareto frontier. The result is an approximation of the true Pareto front reached without requiring gradient information or convexity assumptions.

History

Simulated annealing was introduced by Kirkpatrick et al. in 1983. Serafini (1992) was among the first to formally propose its extension to multiple objectives. Czyzak and Jaszkiewicz (1998) developed Pareto Simulated Annealing (PSA), which established the Pareto archive as the central output structure and provided the acceptance criterion formulation widely adopted today. MOSA has since been applied in engineering design, scheduling, and logistics.

When to use it

Use MOSA when you face an optimization problem with two or more conflicting objectives and either continuous or combinatorial decision variables, particularly when the objective landscape is non-convex, multimodal, or gradient-free. It is well-suited to scheduling, routing, engineering design, and resource allocation problems where an explicit trade-off front is more useful than a single weighted aggregate. Prefer MOSA over purely stochastic Monte Carlo when you need optimization rather than uncertainty quantification. Do NOT use MOSA when the problem has a single objective (classical SA suffices), when the Pareto front must be found exactly (exact algorithms are better for small problems), when the number of objectives exceeds roughly five (hypervolume-based methods scale better), or when evaluation of objectives is extremely expensive per call (surrogate-based methods are preferable).

Limitations and considerations

  • Solution quality and Pareto front coverage are sensitive to the choice of initial temperature, cooling rate, and neighborhood operator, requiring problem-specific tuning.
  • Convergence to a high-quality Pareto front can require many objective evaluations, making it slow for expensive black-box simulations.
  • Maintaining and updating the Pareto archive introduces overhead and the archive may grow large, increasing memory and comparison costs.
  • Unlike population-based methods (e.g., NSGA-II), the single-trajectory nature of basic MOSA can produce uneven coverage of the Pareto front.
  • Theoretical convergence guarantees require an infinitely slow cooling schedule, which is impractical; finite schedules sacrifice optimality assurance.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Requires no gradient information and handles non-convex, discontinuous, and multimodal objective landscapes.
  • Probabilistic acceptance of inferior solutions allows escape from local Pareto fronts that trap purely greedy approaches.
  • Produces a diverse approximation of the full Pareto front in a single run, giving decision-makers explicit trade-off options.
  • Implementation is straightforward and the cooling schedule provides an intuitive parameter to tune exploration–exploitation balance.
  • Applicable to both continuous and combinatorial optimization problems with minimal reformulation.

Applications

  • Multi-objective job-shop and flow-shop scheduling (minimizing makespan and tardiness simultaneously)
  • Network design and routing problems with cost and reliability objectives
  • Engineering design optimization (e.g., minimizing weight and stress in structural components)
  • Portfolio optimization balancing expected return and risk
  • Land-use and spatial planning with competing economic and environmental objectives
  • Healthcare resource allocation balancing cost, coverage, and quality of service

How it works

How it works

1

Generate an initial solution (random or heuristic), set a starting temperature T_0 sufficiently high to allow broad exploration, initialize the Pareto archive with any non-dominated solutions found, and define stopping criteria (maximum iterations or a minimum temperature threshold).

2

Perturb the current solution using a neighborhood operator appropriate to the problem structure (e.g., swap, insert, or Gaussian perturbation for continuous variables) to produce one or more candidate neighbor solutions.

3

Evaluate all objective functions for the candidate neighbor. Determine whether it dominates, is dominated by, or is non-dominated relative to the current solution and the solutions in the Pareto archive. Non-dominated candidates are added to the archive; dominated archive members are removed.

4

Apply a multi-objective acceptance criterion. If the neighbor is non-dominated with respect to the current solution it is accepted. If it is dominated, it may still be accepted with probability P = exp(−ΔF / T) where ΔF aggregates objective deterioration, allowing escape from local Pareto fronts.

Formula
P(\text{accept}) = \exp\!\left(-\frac{\Delta f}{T}\right)
5

Reduce the temperature according to a cooling schedule, commonly geometric: T_{k+1} = α · T_k with α ∈ (0.8, 0.99). Lower temperatures narrow acceptance of inferior moves, progressively intensifying search near promising regions of the Pareto front.

Formula
T_{k+1} = \alpha \cdot T_k, \quad \alpha \in (0,1)
6

Return the final Pareto archive as the result. Post-process to prune dominated solutions that may have accumulated, and present the archive as a discrete approximation of the Pareto-optimal front for decision-maker selection.

Common pitfalls

  • Setting the initial temperature too low causes premature convergence to a local region of the Pareto front; always calibrate T_0 so the initial acceptance rate is around 70–90%.
  • Using a cooling rate α too close to 1.0 makes the run prohibitively long; too close to 0 causes rapid convergence before the Pareto front is adequately explored.
  • Defining ΔF for the acceptance probability with a naive sum of objective differences mixes incomparable scales — normalize each objective before aggregation.
  • Neglecting to remove dominated solutions from the archive periodically inflates it and degrades the quality of the final output.
  • Evaluating success on a single run is misleading given stochastic variation; always aggregate results over multiple independent runs.

Frequently asked questions

How does MOSA differ from NSGA-II?

NSGA-II is a population-based evolutionary algorithm that evolves a set of solutions simultaneously using crossover, mutation, and non-dominated sorting. MOSA is a trajectory-based method that explores one solution at a time using probabilistic moves. MOSA tends to be simpler to implement and works well for combinatorial problems, while NSGA-II generally provides better Pareto front coverage for continuous problems and scales more predictably.

How should I set the initial temperature T_0?

A common heuristic is to run a short preliminary phase and choose T_0 so that approximately 80% of random neighbor moves are accepted. This ensures broad exploration at the start. Problem-specific calibration is advisable because the appropriate temperature scale depends on the magnitude of objective function differences.

Can MOSA handle more than two objectives?

Yes, but performance degrades as the number of objectives grows. The Pareto archive management cost increases, and the fraction of non-dominated solutions grows rapidly, making the acceptance criterion less discriminating. For problems with more than four or five objectives, hypervolume-indicator-based or decomposition-based methods (e.g., MOEA/D) are generally preferred.

How do I know when to stop the algorithm?

Common stopping criteria include reaching a minimum temperature, exhausting a maximum iteration budget, or observing no improvement in the hypervolume indicator of the Pareto archive over a specified number of iterations. In practice, comparing archive quality across multiple runs at different iteration budgets is a reliable way to diagnose convergence.

Is MOSA suitable for expensive simulation models?

Generally not without modification. Each iteration requires at least one objective function evaluation, and MOSA typically needs thousands of iterations for good Pareto front approximation. When each evaluation involves a costly simulation, surrogate-assisted versions of MOSA (using metamodels to approximate objectives) are preferable.

Related methods

Sources

  1. Czyzak, P., Jaszkiewicz, A. (1998). Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7(1), 34–47.

    Open DOI reference
    Copied.
  2. Serafini, P. (1992). Simulated annealing for multi-objective optimization problems. In Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 87–96.

    Open publication reference
    Copied.