常见的运筹优化类问题及常用的优化算法
文章目录1、常见问题介绍2、常用算法3、DeepMind用神经网络求解MIP 之前的研究的是有关多目标优化的方向，期间涉及到二次规划问题最优求解，以及kkt条件相关的知识。在研究启发式方法的同时也涉及到与传统优化方法的比较。因此在这里总结一些运筹向常见的问题。如旅行商问题TSP、车辆路径规划VRP、设施选址问题、网络优化、物流调度等。 然后介绍优化领域内的常用算法如遗传算法、粒子群算法、分支定界法、动态规划法、贪心算法。 最后介绍谷歌DeepMind用神经网络求解MIP的方法。1、常见问题介绍（1）TSP旅行商问题：一个商人从一点出发，经过所有点后返回原点。它需要满足：除起点和终点外，所有点当且仅当经过一次；起点与终点重合；所有点构成一个连通图。要求：得到这个商人经过所有点的最短路程。 （2）VRP车辆路径规划问题：对一系列装卸货点进行适当的路径规划，在满足约束条件（客户需求、车辆载重和容积、车型、车辆行驶里程、配送时间窗、配送中心数量等限制）和目标最优化（路程最短、成本最低、使用车辆数最少、配送时间最快等）下，将客户的配送需求从配送中心送达客户点，或从客户点送回配送中心。 （3）设施选址问题：自20世纪60年代初期以来，在运筹学中一直占据着中心位置。它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题。 （4）网络最优化问题：是一类特殊的组合最优化问题。应用图论理论，通过网络的拓扑结构及其性质，对网络进行研究，并且以计算机算法寻求网络中的最短路、最大流等。 （5）物流调度：物流调度是指车辆分配情况的掌控及司机及车上货物跟踪。物流调度主要是指在物流过程中,物流公司根据待发货物的重量,去向,规格，加急程度等对所属的车辆和人员进行合理的安排调度。
2、常用算法（1）遗传算法：该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。 （2）粒子群算法：PSO中优化问题的每个解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 （3）分支定界法：基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。 （4）动态规划法：基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 （5）贪心算法：贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。
3、DeepMind用神经网络求解MIP混合整数规划（MIP）是一类NP困难问题，来自DeepMind、谷歌的一项研究表明，用神经网络与机器学习方法可以解决混合整数规划问题。 混合整数规划（MixedIntegerProgram,MIP）是一类NP困难问题，旨在最小化受限于线性约束的线性目标，其中部分或所有变量被约束为整数值。混合整数规划的形式如下： MIP已经在产能规划、资源分配和装箱等一系列问题中得到广泛应用。人们在研究和工程上的大量努力也研发出了SCIP、CPLEX、Gurobi和Xpress等实用的求解器。这些求解器使用复杂的启发式算法来指导求解MIP的搜索过程，并且给定应用上求解器的性能主要依赖于启发式算法适配应用的程度。 DeepMind、谷歌的研究者展示了机器学习可以用于从MIP实例数据集自动构建有效的启发式算法。该研究证明，机器学习可以构建针对给定数据集的启发式算法，其性能显著优于MIP求解器中使用的经典算法，特别是具有SOTA性能的非商业求解器SCIP7.0.1。该研究将机器学习应用于MIP求解器的两个关键子任务：（1）输出对满足约束的所有变量的赋值（如果存在此类赋值）（2）证明变量赋值与最优赋值之间的目标值差距边界。 源代码并未公开，论文可自行在以下地址查看。
五种典型启发式算法对比总结
说明：
1.五种启发式算法包括：遗传算法，粒子群算法，蚁群算法，禁忌搜索，模拟退火之前的博文中已经写了五种启发式算法的偏应用的总结，避开背景知识和代码，已经尝试从问题和解的角度去总结五种算法的流程和思路其中：遗传算法，粒子群算法，模拟退火附带的示例是求解函数极值蚁群算法，禁忌搜索附带的示例是求解TSP
遗传算法（GA）： 遗传算法（GA）总结：算法流程，实例，思路粒子群算法（PSO）：粒子群算法（PSO）总结：算法流程，实例，思路蚁群算法（ACO）： 蚁群算法（ACO）总结：算法流程，实例，思路禁忌搜索（TS）： 禁忌搜索（TS）总结：算法流程，实例，思路模拟退火（SA）： 模拟退火（SA）总结：算法流程，实例，思路
2.不同的启发式算法原本就是针对不同的问题而发明的，各种方法有各自的适用范围，原则上应该是根据具体问题选择算法，脱离具体问题而单独对比算法不太合理。但是对比总结有助于理清各个算法的思路，所以本文还是给出简要对比
3.各种启发式方法都存在各种改进版，都在不断的更新完善，这里只是根据个人的理解，总结基础版的五种启发式方法
以下是根据个人理解的对比总结
注意：各种算法里的每种操作都可以自由设计，而且设计方式不固定，所以对比总结里的某些方面不一定完全准确，这里仍然是尝试从问题和解的角度去总结
1.遗传算法
2.粒子群算法
3.蚁群算法
4.禁忌搜索
5.模拟退火
群体/单体
群体
群体
群体
单体
单体
使用问题范围
离散优化
连续优化
连续优化
离散优化
离散优化
离散优化
连续优化
新解的产生方式
（选择）
交叉
变异
速度更新公式产生增量，增量添加到当前解上
依据信息素和城市间距，以概率产生新解
构造邻域，邻域中选取
构造偏移量，偏移量加到当前解上
逐步靠近优解
（优解对于新解的产生过程的引导性）
选择过程中的轮盘赌，更优的解保留的几率更大
群体最优解、单体最优解都影响每个解的更新过程
信息素越浓、城市间距越短的路径被选中的概率越大
选用最优解产生领域
更优的解一定接受
劣解概率接受
（跳出局部最优）
交叉变异都会产生新解，种群更新时采用轮盘赌，劣解有几率保留
解的更新过程中产生的新解会覆盖群体最优解、单体最优解的周边解空间
信息素不浓、城市间距不短的路径也有概率被选中
只能取和禁忌表中保存的解不相同的解，有几率取到次优解或劣解
Metropolis准则，以概率接受劣解
算法中的随机性
1.初始解
2.选择环节
某个解是否保留
3.交叉环节
某个基因是否用于交叉，交叉位置
4.变异环节
某个基因是否变异，变异位置
1.初始解
2.初始速度
3.速度更新公式里的随机权重
蚂蚁在某城市选择下一个要去的城市的概率
初始解
1.初始解
2.产生的新解
3.接受劣解时概率
核心思路
（思想内涵）
（算法特色）
选择环节保留优解，交叉变异环节产生新解
解的更新同时利用全局最优解和局部最优解信息
反馈机制，且搜索机制深入到具体问题层面
通过禁忌表避开已经搜索到的最优解，迫使算法搜索新的最优解
搜索到的更好的解一定接受，搜索到的更差的解以概率接受