混合整数分布式蚁群优化算法- MIDACO数学规划求解器

混合整数分布式蚁群优化算法-MIDACO数学求解器

MIDACO是数值优化问题的商业求解器,她来自于日本北海道大学的创新技术。MIDACO可以应用于连续（NLP非线性规划）、离散/整数（IP整数规划）和混合整数非线性规划（MINLP）问题。MIDACO可用于单目标和多目标优化问题，问题进一步受限于等式和/或不等式约束。MIDACO实现了一种无导数的进化混合算法，该算法将问题视为黑盒，黑盒可能包含关键函数特性，如非凸性、非连续性或随机噪声。对于CPU时间昂贵的应用程序，MIDACO提供了一种高效的并行化策略。该数学优化软件可用于多种编程语言，包括而不限于Excel、VBA、Java、C#、MATLAB、Octave、Python、R、Julia、C/C++和FORTRAN。请联系MIDACO中国区独家合作伙伴无锡迅合信息科技有限公司工作人员获得midaco求解器的试用。

MIDACO是用于解决单目标和多目标优化问题的高性能数值分析和求解软件。该软件最初是针对欧洲航天局、Astrium（空客集团）的空间站应用的挑战性问题而研发的，后来被扩展并构建为通用型数学解算器，以适应更为广泛的优化问题。MIDACO处理目标函数f(x)依赖于变量x是连续、整数或两种类型（混合整数情况）的问题，该问题可能进一步受限于等式和/或不等式约束g(x)。简单来说，优化问题就是在给定的一个输入和输出关系的函数f，优化处理生成可行的替代方案集，和从中选择最佳解决方案的过程。通过系统地在一个允许集上选择输入值，计算输出值，记录过程中发现的最好输出值，运用MIDACO（混合整数分布式蚁群优化算法）的智能搜索方法找到下一个最好值的方向，不断迭代直至发现最好的一个或多个方案。许多实际问题都可以用这种方法建模，例如设计一个电机产品，输入可以是电机的多个设计参数，输出是它的功耗；或者输入可以是某种业务的选择，输出是每种选项可以获得的利润等等。以下为MIDACO数学求解器所考虑的优化问题的简图：

优化问题

作为黑盒优化器，MIDACO不要求目标f（x）和约束g（x）函数以明确的数学形式给出。对于给定的决策变量x的输入，MIDACO只需目标和约束的返回值。这些目标值和约束值的计算方式完全独立于MIDACO，因此被认为是在后台进行的。这样的黑盒概念为用户提供了表达和制定应用的最大自由度。特别地，MIDACO能够解决具有高度非线性、非光滑、非凸和不可微问题的函数。此外，MIDACO可以稳健地解决具有中等水平随机噪声的问题。

MIDACO核心算法

MIDACO基于一种称为蚁群优化（ACO）的进化算法。特别是MIDACO实现了一个扩展到混合整数搜索域的连续蚁群算法。下图说明了这种混合整数扩展蚁群算法如何使用多核概率密度函数（PDF）对连续情况（左）和整数情况（右）的决策变量搜索空间进行采样。

Mixed Integer Distributed Ant Colony Optimization algorithm

 在MIDACO数学求解优化器中，通过“Oracle惩罚方法”处理约束，“Oracle惩罚方法”是进化算法获得全局最优解的一种先进的自适应方法。像所有的进化算法(evolutionary algorithms)一样，MIDACO并不能保证获得全局最优解，但在数百个基准上进行的大量数值试验证明它能够快速而稳健地获得绝大多数问题的全局最优解。特别是在文献[A Numerical Study of MIDACO on 100 MINLP Benchmarks]中，我们还证明了MIDACO在全局最优性能和运行时性能方面优于已建立的经典MINLP算法（如分支界定法）。MIDACO背后的驱动是为大众提供一个健壮的优化算法，并可以在合理的时间段内优化复杂的实际应用程序，从而得到一个合理的、更好的解决方案。为了提高其整体性能，MIDACO算法进一步实现了多种启发式算法和其他算法，包括基于伪梯度回溯线搜索技术，以实现快速的局部收敛。MIDACO被归类为一种进化混合算法。

MIDACO软件开发历史

MIDACO数值求解器是日本Hokkaido University（北海道大学）在Schlueter博士的研发团队下经过10多年的开发和改进，成功发布的商业化数学求解器，它代表了“进化计算”这一领域最领先水平，解决MINLP、约束和大规模优化问题，线性或非线性问题。该软件旨在独立使用以及集成（嵌入）MIDACO到外部算法和软件中。MIDACO的目标是将最高的数值效率与易于使用的界面结合起来。她是一种完全自给自足的超轻量的ANSI-C或Fortran源代码，可移植，可在所有平台（Win/Mac/Linux）上编译/运行，包括web服务器和微处理器。它提供了到多种流行语言（如Excel、VBA、C#、Java、R、Matlab、Python和Julia）的现成运行接口。MIDACO软件已经成功地进行了实际问题压力测试，可以扩展到100000变量、数千个约束和数百个目标的优化问题(乃至更多)。

MIDACO软件的一个特殊特性是它的“并行化”计算选项，可并行地评估多个候选解决方案。并行化可以显著加快总体计算时间，以解决CPU时间密集型应用，如数值模拟。MIDACO并行化方法提供了两个独特的优点。第一个优点是，它不仅限于单一语言和方法，几乎可以用任何语言和方法来实现。当前的并行化模板包括：OpenMP、MPI、GPGPU、apache spark、Fork/Join、multiprocessing、mpi4py等。第二个优点是可以自由选择并行化因子，独立于MIDACO内部算法组件（如种群大小）或CPU硬件规格。这使得MIDACO能够高度适应任何分布式HPC系统(高性能计算系统)，并利用大规模并行化。

MIDACO软件目前在日本和全球范围内有数百名学术和商业机构用户。MIDACO数学求解器应用范围广泛，包括汽车工业、化工、电信、机器人、土木工程、电气工程、生物技术、气候、能源和金融。MIDACO特别用于（航空）航天工程，例如欧洲航天局（ESA）、德国航空航天局（DLR）、日本宇宙航空研究开发机构（JAXA）、韩国航空航天研究所（KARI）和航空航天相关行业,如Astos Solutions、MT Aerospace、Almatech，PACE航空或日本三菱重工。MIDACO最令人兴奋的应用之一是星际空间任务轨迹设计，这里MIDACO拥有多个创纪录的解决方案。MIDACO的开发得到了多家机构的赞助，被众多知名的企业采用，直接集成到他们自己的业务系统或产品之中。

MIDACO研发赞助方

MIDACO数学求解器系统集成案例