Developing Custom Solutions to Complex Problems

δMOEA: Multi-Objective Grid Search Algorithm

What is δMOEA?

δMOEA is an optimization library that helps people make better decisions using computer models of a problem domain. δMOEA searches the model inputs for combinations that produce optimal model outputs with respect to multiple objectives. We call δMOEA a "Grid Search" algorithm because it samples the model inputs on a grid rather than attempting to optimize continuous values.

The Python implementation of δMOEA is available as an open-source (BSD licensed) application here. δMOEA is open source because we believe in multi-objective optimization and we want people to use it.

Computer Models

Computer models of a problem domain express value judgments about it. If nothing else, what the author has chosen to model is a statement about what is important. Deciding to use optimization, however, often implies an extra layer of value judgment on top of the domain model. We call this extra layer the "optimization model" to distinguish it from the domain model. We call the inputs to the optimization model "decisions" and the outputs "objectives", "constraints", and "tagalongs".

The following figure shows how an optimization model wraps around a domain model:

  1. Decisions are translated by the optimization model into inputs for the domain model.
  2. Some domain model inputs may be held constant and not subjected to optimization.
  3. Some domain model outputs are translated into objectives for optimization. Objectives are numbers that δMOEA will attempt to minimize or maximize.
  4. Other domain model outputs are translated into constraints for optimization. Constraints are numbers that δMOEA will preemptively try to drive to zero, before considering the objectives.
  5. Still other domain model outputs are captured as tagalongs. Tagalongs have no role in optimization but may be of use for decision-making. In addition, tagalongs may preserve domain model inputs and outputs so that old domain model evaluations may be reused with a new optimization model.
  6. Some domain model outputs may be ignored and discarded by the optimization model.

Optimization Model

Multi-Objective Optimization

Multi-Objective Optimization differs from conventional (single-objective) optimization in that it seeks to approximate a "Pareto Set" representing the trade-offs among multiple objectives, rather than to approximate a single optimal value. The figure below illustrates the difference between the progress of single-objective and multi-objective optimization.

Multi-Objective Optimization

Under single-objective optimization, the objective value is continually improved over time (in this example, it is minimized). This is the top plot in the figure. Multi-objective optimization, on the other hand, attempts to optimize two or more objectives at once (in this example, two objectives are minimized). The bottom left plot shows both objectives over time. Rather than a single value, both objectives develop a range of values that trade off against each other. The final trade-off is shown in the bottom right plot.

Why δMOEA?

Why δMOEA? Optimization is a powerful tool for understanding a problem. It pushes a domain model to its limits and identifies gaps in our conception of a problem. Multi-objective optimization is particularly powerful. Compared to single-objective optimization, adding even one more objective allows you to make significantly more nuanced decisions and avoid overlooking the point of diminishing returns.

Also, compared to simply sampling the entire decision space on a grid, δMOEA saves a vast amount of computer time. As an optimization algorithm, δMOEA focuses its sampling on the interesting part of the decision space, where interest is defined by the user in terms of objectives and constraints.

Compared with other multi-objective optimization algorithms, δMOEA scales well to large numbers of objectives. It has been tested with up to 20 objectives and makes more efficient use of expensive computational resources. Furthermore, δMOEA has been designed to integrate with existing parallel evaluation approaches, and although it is readily parallelized it does not impose any one approach on its users. δMOEA will work with anything from Python's multiprocessing library, to MPI, to homegrown ØMQ job queues.

Its design also makes δMOEA easy to use as a library rather than as an application. Where most optimization routines want to take control of your model, δMOEA decouples sampling and evaluation to put the user in control. This makes it possible to embed δMOEA in model code rather than shoehorning model code into an optimization program.

Finally, because δMOEA is already grid-oriented, it will avoid a great deal of unnecessary sampling on mixed-integer problems compared to other MOEAs.

About The Name

δMOEA uses an evolutionary optimization heuristic to improve its Pareto approximation. This is the origin of the "MOEA" in its name: it is a Multi-Objective Evolutionary Algorithm. The δ alludes to the sampling grid in the decision space, where δ is the grid spacing. The name δMOEA also pays homage to Deb et al.'s εMOEA, an influential algorithm that applies a grid on the objective space rather than the decision space.

Python Compatibility

δMOEA is compatible with both Python 2 and Python 3. In addition, δMOEA has no library dependencies beyond the Python standard library, so it should work on any platform and with any interpreter.

Advertisement

You might be interested in consulting with us to:

  • Train to use δMOEA
  • Support δMOEA
  • Translate δMOEA into the programming language of your choice
  • Integrate δMOEA into another program
  • Hook δMOEA up to your model of interest
  • Build a GUI frontend that ties δMOEA to your domain model
  • Build a web frontend that ties δMOEA to your domain model
  • Do end-to-end model integration, optimization, and analysis