About

Mixed Integer Distributed Ant Colony Optimization

MIDACO is a numerical high-performance software for solving single- and multi-objective 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-purpose solver 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 form. 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. 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. The motivation behind MIDACO is to provide a robust algorithm that can optimize complex real world applications in a reasonable time to a reasonably good solution. In order to improve its overall performance, MIDACO furthermore implements many heuristics and algorithms, including a pseudo-gradient based backtracking line-search for fast local convergence. MIDACO is therefore classified as an evolutionary hybrid algorithm.

The Software

Developed and constantly improved for over 10 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, super lightweight (~200kb) ANSI-C or Fortran source code, MIDACO is portable and compiles/runs on all platforms (Win/Mac/Linux), including web servers and microprocessors. Ready-to-run gateways to popular languages such as Excel, VBA, C#, Java, R, Matlab, Python and Julia are provided. The MIDACO software has been tested successfully to scale up to problems with 100,000 variables, thousands of constraints and hundreds of objectives.

A special feature of the MIDACO software is its parallelization option, where several solution candidates are evaluated in parallel. Parallelization can significantly speed up the overall calculation time (wall-clock) to solve CPU-time intensive applications, like numerical simulations (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 include for example OpenMP, MPI, GPGPU, Apache Spark, Fork/Join, multiprocessing, mpi4py and others. The second advantage is that the parallelization factor can freely be chosen, independently of MIDACO internal algorithmic components (like population size) or CPU hardware specifications. This enables MIDACO to be highly adaptive to any distributed HPC 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 automotive industry, chemical engineering, telecommunication, robotics, civil engineering, electrical engineering, bio-technology, climate, energy 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, Almatech, PACE Aerospace or Mitsubishi Heavy Industries. One of the most exciting application of MIDACO is the design of interplanetary space mission trajectories (see for example [7],  [12],  [13],  [14]  or [18]) where MIDACO holds several record solutions.

See the User Manual for further reading 

  [*] See the publications section for literature references