组合优化求解方法

1. 离散优化/整数规划

整数规划，或者离散优化（Discrete Optimization），是指数学规划问题中自变量存在整数。

混合整数规划（Mixed Integer Programming, MIP），即自变量既包含整数也有连续变量

求解复杂度

求解整数规划的精确解是NP难的，也就是指数级算法复杂度（Exponential Time Solvable）

假设这里的整数是0,1变量，那么我们可以简单地理解为算法复杂度是2^{n（需要解2}n个线性规划问题）。也就是说，每增加一个0，1变量，求解的速度就有可能要增加一倍！例如求解n=100的整数规划问题需要1小时，那么求解n=101的规模可能会需要2小时，n=102需要4小时，n=105需要32小时。。这就是指数爆炸！

其它解决方案

近似算法（Approximation Algorithms），启发式算法（Heuristic Algorithms），遗传算法（Evolution Algorithms, Meta-Heuristic）等等。它们虽然不能求得整数规划的最优解，但是却能在短时间（通常多项式时间）内给出一个较好的可行解

组合优化是整数规划的子集。的确，绝大多数组合优化问题都可以被建模成（混合）整数规划模型来求解

2. 组合优化求解方法：

• 精确方法——无法应用于大规模实例
• 近似算法——本质上都是贪心算法，而且通常都是多项式时间的算法
• 启发式方法——以问题为导向（通常依赖于人工选取 heuristics； –难以调整何时何地应用 heuristics； 般只能求得局部最优解；启发式算法的设计过程需要特殊的领域知识，并可能需要反复试验来调整算法。实际上，每当问题设置变化时，算法通常需要被重新修订，这需要我们重新优化系统，故而启发式算法在这时变得不切实际）
• 元启发算法——如遗传算法、蚁群算法、进化算法、智能算法；可以将它当作一个黑箱子对几乎任何问题适用；可以控制算法的迭代次数
• 神经网络
• RL方法

3. 元启发算法Meta-heuristic

也被称为智能优化算法(Intelligent optimization algorithm)

举例：

(1) 遗传算法；

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

• 种群——由经过基因（gene）编码的一定数目的个体(individual)组成
• 个体——是染色体(chromosome)；遗传物质的主要载体，即多个基因的集合
• 由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码
• 染色体长度为二进制编码的长度。chromosomes 每一条染色体是一个字典，该字典有两个内容，分别是包含基因的Gene类和适应度函数值fitness

初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

生物学术语

• 基因型(genotype)：性状染色体的内部表现；
• 表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；
• 进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
• 适应度(fitness)：度量某个物种对于生存环境的适应程度。
• 选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
• 复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
• 交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
• 变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
• 编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
• 解码(decoding)：基因型到表现型的映射。
• 个体（individual）：指染色体带有特征的实体；
• 种群（population）：个体的集合，该集合内个体数称为种群

遗传算法的一般步骤：

• 随机产生种群。
• 根据策略判断个体的适应度，是否符合优化准则，若符合，输出最佳个体及其最优解，结束。否则，进行下一步。
• 依据适应度选择父母，适应度高的个体被选中的概率高，适应度低的个体被淘汰。
• 用父母的染色体按照一定的方法进行交叉，生成子代。
• 对子代染色体进行变异。

选择算子

• 轮盘赌选择（Roulette Wheel Selection）
• 随机竞争选择（Stochastic Tournament）
• 最佳保留选择
• 无回放随机选择（也叫期望值选择Excepted Value Selection）
• 确定式选择
• ……

遗传算法的缺点

1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,

2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.

3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间。

4、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。

5、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。

常用混合遗传算法，合作型协同进化算法等来替代，这些算法都是GA的衍生算法。

(2) 粒子群算法PSO；

PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而GA除了连续问题之外，还可应用于离散问题，比如TSP问题、货郎担问题、工作车间调度等

(3) 禁忌搜索算法；

(4) 蚁群算法；

(5) 人工蜂群算法；

(6) 模拟退火算法；*

(7) 差分进化算法；

(8) 免疫算法；

(9) 蛙跳算法；

(10) 帝国竞争算法；

(11) 和声搜索算法；

(12) 分布估计算法；

(13) Memetic算法；

(14) 文化算法；

(15) 人工鱼群算法；

(16) 灰狼优化算法；

(17) 进化规划；

(18) 进化策略；

(19) 候鸟优化算法；

(20) 算法；

(21) 花朵授粉算法；

(22) 引力搜索算法；

(23) 化学反应优化算法；

3. 智能优化算法总结

蚁群算法，1991 年
粒子群算法，1994年
细菌觅食优化算法, Bacterial Foraging Optimization Algorithm，2002年
混合蛙跳算法， Shuffled Frog Leaping Algorithm，2003年
人工蜂群算法， Artificial Bee Algorithm，2005年
萤火虫算法，第一种 Glowworm Swarm Optimization Algorithm 2005年，第二种Firefly Algorithm 2009年
布谷鸟搜索， Cuckoo Search，2009年
果蝇优化算法，Fruit Fly Optimization Algorithm，2011年
头脑风暴优化算法，Brain Storm Optimization，2011年
蝙蝠算法， Bat Algorithm，2010 年
灰狼优化算法，Grey Wolf Algorithm，2014 年
蜻蜓算法，Dragonfly Algorithm，2015 年
鲸鱼优化算法，Whale Algorithm，2016 年
蝗虫优化算法,Grasshopper Algorithm，2017 年
麻雀搜索算法, Sparrow Algorithm ，2020 年

生物学术语

• 基因型(genotype)：性状染色体的内部表现；
• 表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；
• 进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
• 适应度(fitness)：度量某个物种对于生存环境的适应程度。
• 选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
• 复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
• 交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
• 变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
• 编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
• 解码(decoding)：基因型到表现型的映射。
• 个体（individual）：指染色体带有特征的实体；
• 种群（population）：个体的集合，该集合内个体数称为种群

遗传算法的一般步骤：

• 随机产生种群。
• 根据策略判断个体的适应度，是否符合优化准则，若符合，输出最佳个体及其最优解，结束。否则，进行下一步。
• 依据适应度选择父母，适应度高的个体被选中的概率高，适应度低的个体被淘汰。
• 用父母的染色体按照一定的方法进行交叉，生成子代。
• 对子代染色体进行变异。

选择算子

• 轮盘赌选择（Roulette Wheel Selection）
• 随机竞争选择（Stochastic Tournament）
• 最佳保留选择
• 无回放随机选择（也叫期望值选择Excepted Value Selection）
• 确定式选择
• ……

(2) 粒子群算法PSO；

PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而GA除了连续问题之外，还可应用于离散问题，比如TSP问题、货郎担问题、工作车间调度等

(3) 禁忌搜索算法；

(4) 蚁群算法；

(5) 人工蜂群算法；

(6) 模拟退火算法；*

(7) 差分进化算法；

(8) 免疫算法；

(9) 蛙跳算法；

(10) 帝国竞争算法；

(11) 和声搜索算法；*

(12) 分布估计算法；

(13) Memetic算法；

(14) 文化算法；

(15) 人工鱼群算法；

(16) 灰狼优化算法；

(17) 进化规划；

(18) 进化策略；

(19) 候鸟优化算法；

(20) 算法；

(21) 花朵授粉算法；

(22) 引力搜索算法；

(23) 化学反应优化算法；

4. 智能优化算法总结

蚁群算法，1991 年
粒子群算法，1994年
细菌觅食优化算法, Bacterial Foraging Optimization Algorithm，2002年
混合蛙跳算法， Shuffled Frog Leaping Algorithm，2003年
人工蜂群算法， Artificial Bee Algorithm，2005年
萤火虫算法，第一种 Glowworm Swarm Optimization Algorithm 2005年，第二种Firefly Algorithm 2009年
布谷鸟搜索， Cuckoo Search，2009年
果蝇优化算法，Fruit Fly Optimization Algorithm，2011年
头脑风暴优化算法，Brain Storm Optimization，2011年
蝙蝠算法， Bat Algorithm，2010 年
灰狼优化算法，Grey Wolf Algorithm，2014 年
蜻蜓算法，Dragonfly Algorithm，2015 年
鲸鱼优化算法，Whale Algorithm，2016 年
蝗虫优化算法,Grasshopper Algorithm，2017 年
麻雀搜索算法, Sparrow Algorithm ，2020 年