About

Mixed Integer Distributed Ant Colony Optimization

 

Benchmarks Collection of Benchmark Problems solved with MIDACO
Applications Various (Real World) Applications optimized by MIDACO
Publications List of Publications on MIDACO and its Core Algorithm

 

MIDACO is a general-purpose solver for single- and multi-objective numerical optimization problems. Initially developed for Mixed Integer Nonlinear Programming (MINLP) problems arising from challenging space applications at the European Space Agency [3], [7] and Astrium (Airbus Group) [7], the software was extended and constructed as general as possible to fit a wide range of optimization problems. MIDACO handles problems where the objective functions f(x) depend on continuous, integer or both types (mixed integer case) of variables x. The problem might be further restricted to equality and/or inequality constraints g(x). Below is a sketch of the optimization problem considered by MIDACO.

Optimization Problem

 

As black-box optimizer, MIDACO does not require the objective f(x) and constraint g(x) functions to be given in explicit mathematical formula. For a given input of decision variables x, MIDACO requires only the returning numerical values of the objectives and constraints. How those objective and constraint values are calculated is completely independent from MIDACO and therefore considered to happen in a back-box. Such black-box concept gives the user the maximum possible freedom in representing and formulating the application. In particular MIDACO is able to solve problems with highly-nonlinear, non-smooth, non-convex and non-differentiable problem functions. Furthermore MIDACO can robustly solve problems with a moderate level of stochastic noise.

 

The Algorithm

MIDACO is based on an evolutionary algorithm known as Ant Colony Optimization (ACO). In particular MIDACO implements a continues ACO with an extension to mixed integer search domains (see [1] or Chapter 2 in [6]). Below figure illustrates how such mixed integer extended ACO samples the decision variable search space with a multi-kernel probability density function (PDF) for the continuous case (left) and the integer case (right):

Constraints are handled within MIDACO by the Oracle Penalty Method which is an advanced and self-adaptive method for evolutionary algorithms to reach the global optimal solution. Like all evolutionary algorithms MIDACO does not provide a guarantee to reach the global optimal solution, but extensive numerical tests on hundreds of benchmarks (see [5] and [17]) demonstrate its capability to obtain the global optimal solution fast and robustly on the majority of problems. In particular in [5] it was also demonstrated that MIDACO can outperform established classical MINLP algorithms (like branch & bound) in regard to global optimal capability and runtime performance. Note that in order to improve its overall performance, MIDACO implements many further heuristics and algorithms, including a back-tracking line search for fast local convergence on smooth problems.

 

The Software

Developed and constantly improved over years the MIDACO software represents the state-of-the-art for evolutionary computing on MINLP, constrained and large-scale optimization. The software is intended for stand-alone use as well as integration (embedding) into external algorithms and software. MIDACO aims on combining highest numerical efficiency with an easy-to-use interface. Available as complete self-sufficient ANSI-C and Fortran source code, MIDACO is portable and compiles/runs on all common platforms (Win/Mac/Linux). Ready-to-run gateways to popular languages such as Excel, C#, Java, R, Matlab and Python are provided additionally. The MIDACO software has been tested successfully to scale up to 100,000 variables and thousands of constraints.

A special feature of the MIDACO software is its parallelization option based on reverse-communication. Parallelization can significantly speed up the overall calculation time (wall-clock) to solve CPU-time intensive applications (see [17]). The MIDACO parallelization approach offers two distinctive advantages. The first advantage is that it is not limited to a single language and approach but can be realized with virtually any language and approach. Current parallelization templates are provided for example for OpenMP, MPI, GPGPU, Apache Spark, Fork/Join, multiprocessing and others. The second advantage is that the parallelization factor can be freely chosen, independently of MIDACO internal algorithmic components (like population size) or CPU hardware specifications. This enables MIDACO to be highly adaptive to any distributed CPU system and to exploit massive parallelization.

 

User and Applications

MIDACO software is licensed worldwide to hundreds of users at academic and commercial institutions. The MIDACO utilization covers a wide range of applications, including chemical engineering, telecommunication, robotics, civil engineering, electrical engineering, bio-technology, climate and finance. MIDACO is especially employed in (aero)space engineering and used for example by the European Space Agency (ESA), German Aerospace (DLR), Japanese Aerospace Exploration Agency (JAXA), Korean Aerospace Research Institute (KARI) and aerospace related industries such as Astos Solutions, MT-Aerospace, Pace Aerospace or Mitsubishi Heavy Industries. One of the most exciting application of MIDACO is the design of interplanetary space mission trajectories (see [7] and [14]) where MIDACO holds several record solutions.

 

Please see the User Manual for further reading 

  [*] See the publications section for literature references