基于数据挖掘技术的全局优化算法

在过程系统综合中,许多问题属于非线性规划(NLP)和混合整数非线性规划(MINLP)范畴.它们大都具有奇异、多峰、刚性等特性.人们很难有效地得到它们稳定的全局最优解.而知识性、经验性约束使基于梯度方向的Newton方法无法有效地获取该类问题的全局最优解.通常只能得到该类问题的局部最优解.遗传算法的随机性虽为求取NLP和MINLP问题的全局最优解提供了可能,但是随机过程中的盲目性及"伪穷举"性却又限制了该算法的搜索效率.针对过程系统综合问题的特殊性,在信息提取技术对搜索空间进行充分数据挖掘的基础上,用遗传算法的随机扰动来跳出局部极值陷井,获得全局最优解.对反应器网络综合问题的求解,显示了信息提取技术与遗传算法相结合求取全局最优解的能力.     

二次约束二次规划问题的二元均值松弛定界算法

二次约束二次规划(quadratically constrained quadratic programming,QQP)问题目标函数和约束条件均是非凸的,是一类NP难问题,目前还没有通用的全局收敛准则,从而使得求该问题的全局最优解面临着严峻挑战。文章通过引入辅助乘积变量,将QQP问题等价地转化为带有乘积等式约束的非线性规划(nonlinear programming,NLP)问题;进而在NLP问题中利用二元均值不等式结合函数的性质松弛乘积等式约束后,产生QQP问题的带有辅助变量的松弛线性规划(relaxation linear programming,RLP)问题,由此确定QQP问题的全局最优值的下界,利用超矩形基于线性函数的缩减策略,以增强子超矩形的紧致删除能力;最后给出了该算法的收敛性分析,数值实验结果表明所提出的算法是可行且有效的。     

应用全场景可行安全约束机组组合的风电最优消纳模型及解法

针对含风电电力系统的安全约束机组组合(SCUC)问题,目前广泛采用的鲁棒优化方法在求解时不能满足调度解的非预期约束并存在严重缺陷,且各种模型和算法中均未考虑最大消纳和最优经济消纳的区别。为克服以上困难,提出了满足非预期约束条件的风电最大消纳和最优消纳模型,并给出对应求解方法。该模型及对应求解方法为容纳可能的弃风决策以扩大调度解空间,引入了风电可变不确定集来替代广泛采用的固定不确定集;为满足调度解的非预期性,引入了一组规模极小的强非预期约束,避免了传统建模方式导致的大量非预期约束难题;为克服鲁棒优化中复杂极小极大结构带来的求解困难,引入了基于可变不确定集顶点场景的全场景可行调度模型,该模型具有单层混合整数线性规划(MILP)问题结构,求解可得调度问题的最优解。实验及测试结果表明:该算法在IEEE118节点系统中取得了良好效果,显示了最大消纳和最优消纳的区别,可以实现含风电SCUC问题的快速求解,并使风电消纳的经济性得到提高。     

带有非线性隶属函数的FLP问题的求解

带有非线性隶属函数(NLMF)的模糊线性规划(FLP)问题。通常是一个非线性规划(NLP)问题。本文利用“较大”、“较小”型隶属函数的特点,把求解原FLP问题最优解的过程化为求解一个参数线性规划(LP)问题及修正参数的交替迭代过程。通过构造不同的参数LP问题及修正参数的方法,得到了求解原问题的“试点法”和“收缩法”,在此基础上,综合得出兼有两法优点的“加速算法”,理论分析及实例都证明这些算法尤其是加速算法在求解带有非线性隶属函数的FLP问题时是有效的.     

两级选址--路径问题的大规模邻域搜索模拟退火算法

针对目前越来越普遍的多级配送模式,建立以总成本最小为目标函数的两级选址-路径问题模型,并提出了大规模邻域搜索模拟退火算法进行求解.在模拟退火算法框架中,嵌入大规模邻域搜索过程,包含破坏、重组和局部搜索方法,从而进一步提高算法在解空间中构建邻域的范围.采用两级选址-路径问题标准算例对算法求解效果进行验证,并与标准模拟退火算法和国际已知最优解进行对比.结果显示,所建模型和算法正确有效,并且在求解大规模问题时算法能够取得相对更好的优化结果.     

面向节能的阻塞混合流水车间调度问题建模

针对能耗目标的阻塞混合流水车间调度问题(HFSP-B),分别构建了考虑调整时间及不考虑调整时间的阻塞混合流水车间调度问题(MILP)模型.为了减少机床待机能耗,在MILP模型中考虑关机/重启节能策略.针对MILP模型,从目标函数、目标函数的线性化过程、决策变量和约束方程进行介绍.最后,通过对具体实例的求解,验证了所提MILP模型的有效性.通过对MILP所得最优解的分析,挖掘了阻塞因素对能耗目标的影响规律,有助于今后设计基于元启发式算法的近似算法.     

求解VRPBTW的变邻域搜索算法

以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.     

一类混合整数双层线性规划的枚举法

通过对上层变量为0-1型变量和下层变量为连续型变量的混合整数双层线性规划问题的,根据分支定界法原理,给出了一种定界函数和寻找问题最优解的搜索准则,由此提出了一个求解混合整数双层线性规划问题的有效枚举方法。提出的算法能求得问题的全局最优解,并通过算例说明了算法的求解过程。     

基于VNS-EM混合算法的两阶段装配流水车间调度

针对以最小化工件提前期和拖期惩罚费用加权和为目标的两阶段装配流水车间调度问题,证明了工件之间的最优排序性质,并将其嵌入优化算法中.由于该问题的NP难性,提出了一种变邻域类电磁机制(VNS-EM)混合算法.该混合算法在类电磁机制(EM)算法的每一次迭代过程中嵌入改进的变邻域搜索(VNS)算法,利用其较好的局部搜索能力对每代最优个体的邻域进行精细搜索,从而提高解的质量.仿真结果表明了算法的有效性.与VNS算法和EM算法相比较,提出的VNS-EM混合算法能更好地兼顾算法的精度和求解速度.     

柔性作业车间调度的动态禁忌粒子群优化算法

针对复杂的多目标柔性作业车间调度问题(FJSP),提出一种基于全知型粒子群优化(FIPS)和动态禁忌搜索(TS)的混合Pareto算法,它在利用FIPS的全局搜索能力确定搜索方向后,通过TS进行有效的局部搜索以提高算法的搜索性能.该算法采用基于强度的适应度函数来评价粒子,以使非劣解均匀分布于Pareto前沿;采用基于公共关键块的多种邻域结构,既保持了种群的多样性,避免算法陷入局部最优,又有效提高了算法的收敛速度.算法中还引入了基于变异的自适应扰动策略来进一步增加解的多样性.对不同规模实例的比较实验表明,文中所提出的算法具有较好的搜索性能,是一种求解大、小规模多目标FJSP的有效算法.     

基于二阶锥规划的无功补偿器选址定容策略

针对动态无功补偿装置选址和定容策略存在求解速度慢、参数选择困难等问题，提出了基于混合整数二阶锥规划（mixed integer second order cone programming，MISOCP）的动态无功补偿器选址和定容策略。首先,以配电网优化周期内的有功功率损耗最小和节点电压偏差最小为目标函数建立混合整数非线性规划（mixed integer nonlinear programming，MINLP）优化模型；其次,通过相角松弛和二阶锥松弛两步松弛法，将MINLP模型转化为MISOCP模型；然后,通过ε-松弛的方法将MISOCP模型转化为混合整数线性规划（mixed integer linear programming，MILP）模型，调用商业求解器求解；最后,在IEEE 33节点和IEEE 69节点的配电系统中进行测试，将模型求解时间、有功功率损耗量和节点电压偏差值作为评价指标，与运用求解器求解MISOCP模型、粒子群算法（PSO）和模拟退火粒子群算法（SA-PSO）求解MINLP模型的方法进行比较。结果表明,所提方法的模型求解时间和求解效果明显优于其他方法，验证了所提方法的可行性和有效性。所提出的多部松弛方法在保证得到最优解的同时简化了模型求解难度，缩短了模型求解时间，为配电系统的无功补偿提供了有效依据。     

弧搜索内点算法

利用弧搜索内点算法对线性规划问题进行求解, 得到该算法的多项式复杂度为O(n^3/4L). 该算法在中心路径的一个宽邻域内, 沿椭圆近似寻找线性规划的最优解. 数值实验表明了该算法的有效性.     

线性规划基于修正牛顿方向的宽邻域内点算法

通过修正经典宽邻域算法的搜索方向, 提出一种新的求解线性规划问题的宽邻域内点算法, 并对算法进行收敛性分析, 证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL). 数值实验表明算法是有效的.     

基于多目标量子粒子群算法的环境/经济调度

针对传统的粒子群优化算法在求解环境/经济调度中存在控制参数多和局部搜索精度低等问题,提出一种基于多目标量子粒子群优化算法的环境/经济调度问题的求解方法.该算法利用具有量子行为特性的粒子搜索解空间,引入改变作用区间的变异算子增强全局搜索能力,并采用基于粒子多样性的方法更新全局最优的领导粒子.仿真结果表明,该算法是有效的,所求Pareto解集能逼近真实的Pareto解集且具有良好的分布性.     

一种求解双层过道布置问题的离散花授粉算法

结合布局活动中设施布置在多层空间的实际情况,对过道布置问题在双层空间中的布置优化进行研究,构建了一种新的混合整数非线性规划模型.基于可行解的离散性和问题求解的复杂性,提出一种花授粉算法离散方法.通过重新定义授粉过程,将以问题规模为搜索深度的随机搜索过程作为全局搜索,而在局部寻优阶段,个体以交换对的形式跟随最优解更新自身.为进一步提高算法性能,在全局搜索阶段引入临界值,通过变异陷入局部最优的个体实现变邻域搜索,并设置阈值以提高求解效率.通过对比改进前后两算法求解38个测试算例的运算结果,验证了算法改进的有效性.最后,应用改进离散花授粉算法求解原过道布置问题,并与不同算法的实验结果进行对比,发现所提算法在求解质量和效率方面更具优势.     

考虑翻箱作业的铁路集装箱中心站起重机调度

为了保证铁路集装箱中心站高效地完成站内转运,利用阶梯恶化函数表示翻箱作业过程,并以此构建轨道式集装箱起重机调度优化模型。由于精确算法难以在合适的时间内获得大规模问题的最优解,在此提出自适应邻域搜索规划算法。该方法采用自适应大规模邻域搜索框架,并采用标准求解器求解产生的子问题。研究结果表明:本文方法在处理高达100个作业任务的算例时也能在较短的时间内给出较优解,可为站场转运作业过程中资源调度问题提供决策支持。     

混合候鸟迁徙优化算法求解柔性作业车间调度问题

将基本候鸟迁徙优化(Migrating birds optimization, MBO)算法与变邻域搜索策略相结合,提出了一种混合候鸟迁徙优化(Hybrid migrating birds optimization, HMBO)算法求解以最小化最大完工时间为目标的柔性作业车间调度问题(Flexible job shop scheduling problem, FJSP).首先,给出了两段式编码/解码方式.为了保证初始解的质量和多样性,设计了一种两阶段种群初始化方法;其次,引入了一种个体重置机制,以避免算法陷入局部最优解.根据FJSP问题的特点,采用3种邻域结构用于构造个体邻域解,并以此为基础设计了一种变邻域搜索算法,增强算法的局部搜索能力.最后,通过基准算例测试了算法的性能,实验数据验证了本文算法在求解FJSP问题方面的有效性.     

一种求解机组组合问题的改进优先顺序法

提出一种求解机组组合(unit commitment,UC)问题的改进优先顺序法.利用机组的最小平均煤耗成本,建立UC问题一个新的整数线性规划模型(integer linear programming,ILP),从而将UC问题分解为一个仅含0、1变量的ILP问题和一个二次规划问题,减小了UC问题的规模和求解难度.利用ILP连续松弛问题的最优解,提出一种求解UC问题的改进优先顺序法.数值结果表明,所建ILP模型合理有效,所提方法具有良好的收敛性,和其他优先顺序法相比,获得了更好的数值结果.     

基于文化基因算法的集成工艺规划与调度研究

建立了与工艺规划集成的调度问题的数学模型.以最大完工时间为目标,设计一种混合文化基因算法求解该问题.在提出算法中,设计了新型编码和主动解码方案,使用变邻域搜索(VNS)算法进行局部搜索,引入了高效的邻域结构以强化算法的局部搜索能力,并提出了一种个体扰动方法,以避免群体多样性趋于单一,使得提出算法在分散搜索和集中搜索之间达到更合理的平衡.为测试算法的性能,对现有的基准问题进行了测试,有21个实例达到了下界或得到改进,成为当前新的最优解.对比已有的最优结果可见:提出的算法可高效地求解工艺规划与车间调度集成问题且优于其他算法.     

求解二次分配问题的预处理快速蚂蚁系统

分析了快速蚂蚁系统(FANT)跳出迭代最优解的策略,指出算法易发生停滞现象的原因,并通过改进算法解的构建步,引入一个变动的参数,提出了求解二次分配问题的一种新算法———预处理快速蚂蚁系统(PFANT).新算法改进了FANT算法易发生停滞的现象,拓宽了迭代最优解邻域的搜索范围,提高了二次分配问题解的质量.