关键路径法
type
status
date
slug
summary
tags
category
icon
password
Property

关键路径法简介

一个大型工程或项目包括很多活动,关键路径是项目中时间最长的活动顺序,决定着可能的项目最短工期。
关键路径法(Critical path method,CPM) 是一种基于进度网络模型的方法,用网络图表示各项活动之间的相互关系,获得在一定工期、成本、资源约束条件下的最优进度安排。
关键路径法源于美国杜邦公司对于项目管理控制成本、减少工期的研究。1959年,Kelly 和 Walker 在论文 Critical Path Planning and Scheduling 中提出了关键路径法的基本原理和方法:计算所有活动的工期,确定其最早开始 ES 和最早结束 EF、最晚开始 LS 和最晚结束 LF 的时间,按照活动的相互关系形成顺序的网络逻辑 图,找到必须的最长路径即为关键路径。
关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始-结束)将活动连接。首先使用正推法(Forward pass),从起点开始向后计算,依次计算每个顶点(事件)的最早开始时间 ES;然后再使用逆推法(Backward pass),从终点开始向前计算,依次计算每个顶点(事件)的最迟结束时间 LF。进而可以求出每条边(工序)的最早结束时间 EF 和最迟开始时间 LS。最早开始时间 ES 和最晚开始时间 LS 相等的边,就是关键路径上的边,对应的工序是关键工序。
  • ES:最早开始时间(Earliest Start),指某项活动能够开始的最早时间,取决于该项活动的所有紧前工作的结束时间,由顺推法计算 ES = max{EF(preceding activities)}。
  • EF:最早结束时间(Earliest Finish),指某项活动能够完成的最早时间。EF = ES+DU, DU为该活动的持续时间。
  • LF:最迟结束时间(Latest Finish),指为了保证整个项目按期完成的某项活动必须完成的最晚时间,取决于该项活动的所有紧后工作的最迟开始时间,由逆推法计算 LF = min{LS(successor activities)}。
  • LS:最迟开始时间(Latest Start),指为了保证整个项目按期完成的某项活动必须开始的最迟时间。LS = LF -DU,DU为该活动的持续时间。
  • TF:总时差(Total float time),指在不影响总工期的条件下,一个活动可以利用的机动时间。TF = LF - EF。
  • FF:自由时差(Free float time),指在不影响紧后工作最早开始时间的条件下,一个活动可能被延迟的时间。FF = min{ES(successor activities)} - EF。
由关键路径法得到的最早/最晚的开始/结束时间并不一定就是项目进度计划,而是把既定的参数(活动持续时间、逻辑关系、提前量、滞后量和其它制约条件)输入进度模型后所得到的结果,表明活动可以在该时段内实施。
🐸 PuLP
type
status
date
slug
summary
tags
category
icon
password
Property
解决线性规划问题有很多数学方法,例如:
  • 图解法, 用几何作图的方法并求出其最优解,中学就讲过这种方法,在经济学研究中十分常用;
  • 矩阵法, 引进松弛变量将线性规划问题转换成增广矩阵形式后逐次求解, 是单纯性法之前的典型方法;
  • 单纯性法, 利用多面体在可行域内逐步构造新的顶点来不断逼近最优解,是线性规划研究的里程碑,至今仍然是最重要的方法之一;
  • 内点法,通过选取可行域内部点沿下降方向不断迭代来达到最优解,是目前理论上最好的线性规划问题求解方法;内点法的基本算法不能处理等式约束
  • 启发式方法,依靠经验准则不断迭代改进来搜索最优解 ,如贪心法、模拟退火、遗传算法、神经网络。
对于线性规划问题,什么算法是最快的呢?答案是:猜。
佐治亚理工学院彭泱教授在 2021年计算机理论顶会 SODA2021 获得最佳论文(Best paper award at ACM-SIAM symposium on discrete algorithms 2021),正是研究线性规划问题的求解——“Solving sparse linear systems faster than matrix multiplication”,所用的全新思路是:猜,反复猜,迭代猜。
当然,猜起来比较快只是在某些特殊条件下才有效的,至于在什么条件下猜,怎么猜,这不是我们所要关心,所能理解的问题了
 
一般线性规划问题的标准形式为:
🐸 解线性规划
type
status
date
slug
summary
tags
category
icon
password
Property
notion image
🐸 解整数规划
type
status
date
slug
summary
tags
category
icon
password
Property

为什么会有整数规划?

线性规划问题的最优解可能是分数或小数。整数规划是指变量的取值只能是整数的规划。
这在实际问题中很常见,例如车间人数、设备台数、行驶次数,这些变量显然必须取整数解。
整数规划并不一定是线性规划问题的变量取整限制,对于二次规划、非线性规划问题也有变量取整限制而引出的整数规划。这里所说的整数规划,通常是指整数线性规划。
根据对变量的不同情况,整数规划又可以分为:
  • 完全整数规划,全部变量都要求是整数;
  • 混合整数规划,部分变量要求是整数;
  • 0-1整数规划,变量的取值只能是 0 或 1;
  • 混合0-1规划,部分变量的取值只能是 0 或 1。
0-1整数规划是非常重要也非常特殊的整数规划

四舍五入就能得到整数解吗?

整数规划问题与线性规划问题的区别只是增加了整数约束。这看上去好像只要把线性规划得到的非整数解舍入化整,就可以得到整数解,并不是多么复杂的问题。
🐸 求0-1规划
type
status
date
slug
summary
tags
category
icon
password
Property

什么是 0-1 规划?

0-1 整数规划是一类特殊的整数规划,变量的取值只能是 0 或 1。
0-1 变量可以描述开关、取舍、有无等逻辑关系、顺序关系,可以处理背包问题、指派问题、选址问题 、计划安排、线路设计 、人员安排等各种决策规划问题。进而,任何整数都可以用二进制表达,整数变量就可以表示为多个 0-1 变量的组合,因此任何整数规划都可以转化为 0-1 规划问题来处理。0-1 规划问题与运筹学中的很多经典问题也都有紧密联系。
在数学建模学习中,0-1 规划主要用于求解互斥的决策问题、互斥的约束条件问题、固定费用问题和分派问题。
 

0-1 规划的分类及建模方法

规划问题的数学模型包括决策变量、约束条件和目标函数,围绕这三个要素都可能存在互斥的情况,从而导出不同类型的0-1规划问题,其建模方法也有差别。

互斥的决策问题

互斥的决策问题,是指决策方案、计划互斥,如决定投资项目、确定投资场所、选择投产产品等。
例如,双十一的促销活动,淘宝、京东、拼多多要求店铺二选一,最多只能选择参加一家平台,否则可能会被封杀,这是典型的互斥决策问题。
背包问题就是经典的互斥决策问题。给定一组 个物品,每种物品 的价值为 、重量/体积为 ,背包所能容纳的总重量/总容量为(B),如何选择其中若干种物品(每种物品选 0 个或 1 个),使得物品的总价值最高?
背包问题的建模方法如下:
🐼 Scikit-opt特性
type
status
date
slug
summary
tags
category
icon
password
Property

UDF(用户自定义算子)

 
 

断点继续运行

例如,先跑10代,然后在此基础上再跑20代,可以这么写:
 
 

4种加速方法

矢量化计算:vectorization
🐼 遗传算法GA
type
status
date
slug
summary
tags
category
icon
password
Property

原理

以求二元函数为例:

种群和个体的概念

遗传算法启发自进化理论,而我们知道进化是由种群为单位的,种群是什么呢?
维基百科上解释为:在生物学上,是在一定空间范围内同时生活着的同种生物的全部个体。
显然要想理解种群的概念,又先得理解个体的概念。 在遗传算法里,个体通常为某个问题的一个解,并且该解在计算机中被编码为一个向量表示!
我们的例子中要求3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)最大值,所以该问题的解为一组可能的( )的取值。比如( ),( ) . . .就是求最大值问题的一个可能解,也就是遗传算法里的个体,把这样的一组一组的可能解的集合就叫做种群,比如在这个问题中设置100个这样的 的可能的取值对,这100个个体就构成了种群。

编码、解码与染色体的概念

在上面个体概念里提到个体(也就是一组可能解)在计算机程序中被编码为一个向量表示,而在我们这个问题中,个体是 的取值,是两个实数,所以问题就可以转化为如何将实数编码为一个向量表示,可能有些朋友有疑惑,实数在计算机里不是可以直接存储吗,为什么需要编码呢?这里编码是为了后续操作(交叉和变异)的方便。
 

调库实现GA

🐼 差分进化算法DE
type
status
date
slug
summary
tags
category
icon
password
Property

原理

差分进化算法是基于群体智能理论的优化算法,是通过群体内个体间的合作与竞争而产生的智能优化搜索算法。但相比于进化计算,它保留了基于种群的全局搜索策略,采用实数编码、基于差分的简单变异操作和“一对一”的竞争生存策略,降低了进化计算操作的复杂性。同时,差分进化算法特有的记忆能力使其可以动态跟踪当前的搜索情况,以调整其搜索策略,它具有较强的全局收敛能力和稳健性,且不需要借助问题的特征信息,适用于求解–些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。因此,差分进化算法作为一种高效的并行搜索算法,对其进行理论和应用研究具有重要的学术意义和工程价值。 差分进化算法是一种自组织最小化方法,用户只需很少的输入。它的关键思想与传统进化方法不同:传统方法是用预先确定的概率分布函数决定向量扰动;而差分进化算法的自组织程序利用种群中两个随机选择的不同向量来干扰一个现有向量,种群中的每一个向量都要进行干扰。差分进化算法利用一个向量种群,其中种群向量的随机扰动可独立进行,因此是并行的。如果新向量对应函数值的代价比它们的前辈代价小,它们将取代前辈向量。同其他进化算法一样,差分进化算法也是对候选解的种群进行操作,但其种群繁殖方案与其他进化算法不同:它通过把种群中两个成员之间的加权差向量加到第三个成员上来产生新的参数向量,该操作称为“变异”;然后将变异向量的参数与另外预先确定的目标向量参数按一定规则混合来产生试验向量,该操作称为“交叉”;最后,若试验向量的代价函数比目标向量的代价函数低,试验向量就在下一代中代替目标向量,该操作称为“选择”。种群中所有成员必须当作目标向量进行一次这样的操作,以便在下一代中出现相同个数竞争者。在进化过程中对每一代的最佳参数向量都进行评价,以记录最小化过程。这样利用随机偏差扰动产生新个体的方式,可以获得一个收敛性非常好的结果,引导搜索过程向全局最优解逼近。

差分进化引入的意义

遗传算法的变异操作,就是对个体的某个或某段基因进行随机变换,得到新的个体,也就是新的一组解。它的目的是通过生成新的解,来试图找到更优的选择。
但是,直观上能想到的是,经过变异之后,新的那段基因,可能是和原先种群中所有的个体中,所对应的所有基因中,有重合的。这就意味着,这次变异是没有意义的变异,并没有产生新的解,还是和原来的有的解一样。
造成的后果也不难想到。当到了优化的后期,整个种群有可能陷入了局部最优。这时候,就需要让解能够跑出那个局部最优的圈圈中,而“无效”的变异,并不能达成目的。因此,我们希望,变异操作后的解,是能够“与众不同”的,和当前的所有解区分开来,从而有可能碰上全局最优。
实现方法的核心公式如下:
个个体, 是缩放因子, 是新生成的解, 表示第几代
 

调库实现DE

 
🐼 粒子群算法PSO
type
status
date
slug
summary
tags
category
icon
password
Property

原理

notion image
粒子群算法的思想源于对鸟类捕食行为的研究,模拟鸟集群飞行觅食的行为,鸟之间通过集体的协作使群体达到最优目的。 设想这样的一个场景,一群鸟在随机的搜索食物,在某块区域里有一块食物,所有的鸟都不知道食物在哪里,但是他们可以感受到当前的位置离食物还有多远,此时找到食物的最优策略是什么?答案是:搜寻目前离食物最近的鸟的周围区域,根据自己的飞行经验判断食物的所在。
PSO正是从这种模型中得到了启发:
  • 1.每个寻优问题的解都被想象成一只鸟,称为‘粒子’,所有的粒子都在一个D维空间进行搜索。
  • 2.所有的粒子都由一个fitness function确定适应值以判断目前位置的好坏。
  • 3.每个粒子都被赋予记忆功能,能记住所搜寻到的最佳位置
  • 4.每个粒子还有一个速度以决定飞行的距离和方向,这个速度根据本身的飞行经验及同伴的飞行经验进行动态调整
可以看出粒子群算法的基础在于信息的社会共享
 

调库实现PSO

 
🐼 模拟退火SA
type
status
date
slug
summary
tags
category
icon
password
Property

原理

退火这个词,其实是铁匠发明的。它的意思很简单,就是将铁匠炉烧热后,再把下边的火撤掉,让金属在炉子里边慢慢冷却。人们发现,这个缓慢的降温过程能消除金属内部的各种缺陷,使得其恢复能量最低的状态。后来,受到退火工艺的启发,研究人员把将退火的缓慢的降温思路推广开来,用于寻找复杂函数的全局最优值。举个简单的例子,氦原子在金属中空位附近运动时,其势能函数大概长这样:
notion image
notion image
把势能函数看成一个轨道,再把氦看成一个小球放到这个轨道上。那么,小球的高度就是它的重力势能。求这个函数的全局最小值,其实就是让小球滚到最深那个坑过程:
notion image
由于函数中存在非常多局域极小值(浅坑),常见的贪心算法(如梯度下降法,就是闭着眼睛沿坡往下滚)会陷入最近的局域极小值,错过到全局最小值(深坑)。 那么,怎么才能让滚进深坑呢? 我们先晃一晃整个体系,让小球随机动起来。我们把晃动的剧烈程度称为温度。在足够长的时间内。小球出现在点的概率呈玻尔兹曼分布,与点的高度(势能)和温度密切相关:
温度为0时,小球出现在全局最小值的概率为100%
那么,把温度设为0不就行了? 当然不行。上面的概率成立的前提是提供无穷长的时间,使得小球能够遍历整个函数。 实际中,无穷长的时间当然是不现实的。小球从低概率区向高概率区转移,这个过程是需要消耗时间的。 高温下,转移速度快。但另一方面,高温下,小球落在各个坑里的概率差别比较小。 为了让小球能够尽快的转移到最低点,我们可以采取一个降温策略:
  • 先设定一个较高的温度 ,使得小球有足够的能量越过能垒,小球到处乱跑的概率比较大。
  • 随机移动小球的位置,检查其移动前后的能量差 。 若 ,小球能量降低,则接受此次移动。 若 ,小球能量升高,有一定概率接受此次移动,概率为: (k为一个随机数) 。这个判定方法称为Metropolis判据。

调库实现SA

🐼 蚁群算法ACA
type
status
date
slug
summary
tags
category
icon
password
Property

原理

蚁群算法是一种源于大自然生物世界的新的仿生进化算法,由意大利学者M. Dorigo, V. Maniezzo和A. Colorni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法"。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径,并且能随环境的变化,适应性地搜索新的路径,产生新的选择。其根本原因是蚂蚁在寻找食物时,能在其走过的路径.上释放一种特殊的分 泌物一信息素 (也称外激素),随着时间的推移该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时,其留下的信息素也越来越多,后来蚂蚁选择该路径的概率也就越高,从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制。通过这种正反馈机制,蚂蚁最终可以发现最短路径。 蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。 蚂蚁在运动过程中,能够在它所经过的路径.上留下信息素进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此来指导自己的运动方向。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。
若蚂蚁从A点出发,速度相同,食物在D点,则它可能随机选择路线ABD或ACD。假设初始时每条路线分配一只蚂蚁, 每个时间单位行走一步。 图所示为经过8个时间单位时的情形:走路线ABD的蚂蚁到达终点;而走路线ACD的蚂蚁刚好走到C点,为一半路程
notion image
 
图2表示从开始算起,经过16个时间单位时的情形:走路线ABD的蚂蚁到达终点后得到食物又返回了起点A,而走路线ACD的蚂蚁刚好走到D点。
notion image
 
  • 假设蚂蚁每经过一-处所留下的信息素为1个单位,则经过32个时间单位后,所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物。此时ABD的路线往返了2趟,每一处的信息素为4个单位:而ACD的路线往返了一趟,每一处的信息素为2个单位,其比值为2: 1
  • 寻找食物的过程继续进行,则按信息素的指导,蚁群在ABD路线上增派一只蚂蚁(共2只),而ACD路线上仍然为一只蚂蚁。再经过32个时间单位后,两条线路.上的信息素单位积累为12和4,比值为3: 1
  • 若按以上规则继续,蚁群在ABD路线上再增派-一只蚂蚁(共3只),而ACD路线.上仍然为一只蚂蚁。再经过32个时间单位后,两条线路上的信息素单位积累为24和6,比值为4: 1

调库实现ACA

🐼 免疫优化算法IA
type
status
date
slug
summary
tags
category
icon
password
Property

原理

生物免疫系统是-一个复杂的自适应系统。免疫系统能够识别出病原体,具有学习、记忆和模式识别能力,因此可以借鉴其信息处理机制来解决科学和工程问题。免疫算法正是基于生物免疫系统识别外部病原体并产生抗体对抗病原体的学习机制而提出的,由此诞生了基于免疫原理的智能优化方法研究这一新的研究方向。
  • 它具有一般免疫系统的特征,采用群体搜索策略,通过迭代计算,最终以较大的概率得到问题的最优解
  • 相比较于其他算法,免疫算法利用自身产生多样性和维持机制的特点,保证了种群的多样性,克服了一般寻优过程(特别是多峰值的寻优过程)中不可避免的“早熟”问题,可以求得全局最优解。
  • 免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点
根据上述的对应关系,模拟生物免疫应答的过程形成了用于优化计算的免疫算法。算法主要包含以下几大模块:
  • 抗原识别与初始抗体产生。根据待优化问题的特点设计合适的抗体编码规则,并在此编码规则下利用问题的先验知识产生初始抗体种群。
  • 抗体评价。对抗体的质量进行评价,评价准则主要为抗体亲和度和个体浓度,评价得出的优质抗体将进行进化免疫操作,劣质抗体将会被更新。
  • 免疫操作。利用免疫选择、克隆、变异、克隆抑制、种群刷新等算子模拟生物免疫应答中的各种免疫操作,形成基于生物免疫系统克隆选择原理的进化规则和方法,实现对各种最优化问题的寻优搜索

免疫算法算子

调库实现IA