基于混合整数线性规划的MORUS初始化阶段的差分分析

认证加密算法MORUS是凯撒(CAESAR)竞赛的优胜算法,抗差分分析性能是衡量认证加密算法安全性的重要指标之一。该文研究了MORUS算法初始化阶段的差分性质,首先给出了一个差分推导规则,可以快速获得一条概率较大的差分链。在此基础上利用混合整数线性规划(MILP)自动搜索技术求解更优的差分链。为了提高搜索速度,结合MORUS初始化阶段的结构特点给出了分而治之策略。根据ΔIV的重量、取值将MILP模型划分为多个子模型并证明了部分子模型的等价性,大大缩减了模型的求解时间,得到了MORUS初始化阶段1~6步状态更新的最优差分链。最后给出了简化版MORUS的差分-区分攻击,该文的结果较之前的工作有较大的提升。

基于并查集搜索的卫星任务规划方法

根据观测任务需求和遥感卫星能力进行快速的遥感任务规划,能够大幅提升遥感任务的观测时效性.针对传统方法应用在大规模任务规划问题求解效率低的问题,建立了离散化的任务规划图模型,提出了基于并查集搜索的卫星遥感任务规划方法.通过并查集搜索的方式将大规模任务规划问题拆分为若干个可解的子问题,在保证求解质量的同时降低计算复杂度,提升求解效率.仿真结果表明,与传统的混合整数线性规划方法相比,基于并查集搜索的方法在中低任务密度的情况下表现出良好的实用性和优化效果,能够将模型求解时间缩短28%~45%.

自动化立体仓库中环形2-RGV系统入库调度模型与求解算法

确定合理的货物运送序列,实现穿梭车(RGV)与堆垛机协同作业是提升自动化立体仓库中环形2-RGV系统搬运效率的重要手段。通过对RGV在环形轨道运作环境下的碰撞情况进行分析,以货物总入库时间最小化为目标,考虑了同一辆RGV运送、两RGV碰撞避免以及RGV与堆垛机协同运作等约束,构建了环形2-RGV系统入库调度问题的混合整数规划模型,设计了可快速求解问题的混合变邻域禁忌搜索(HVNTS)算法。为验证算法的有效性,设计了25组不同规模的算例,并将HVNTS算法的求解结果与CPLEX和禁忌搜索算法的求解结果相比较,算例实验结果表明:货物的平均入库时间分别节省了0.36%和8.67%,且HVNTS算法的求解时间均在3 min内,证明所提算法能快速有效地求解该问题。

求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法

针对带有阻塞限制的不相关并行机混合流水车间调度问题,以最小化最长完工时间为目标,依据不同的建模思想,建立了求解该问题的4个混合整数线性规划(MILP)模型;鉴于混合整数线性规划不适合求解中大规模问题,提出了一种改进的回溯搜索算法以求解中大规模问题,在该算法中,引入了轮盘赌选择策略以及变邻域搜索算法,以提高算法的收敛速度以及局部搜索能力。最后,对所提MILP模型以及算法进行了对比分析,通过对具体实例的求解验证了所提MILP模型以及算法的有效性及优越性。

基于MILP对轻量级密码算法FBC-128的差分分析

FBC(Feistel-based Block Cipher)是入围全国密码算法设计竞赛第二轮的轻量级分组密码.由于它具备算法结构简洁、安全性高及软硬件实现性能卓越等优点,备受业界广泛关注.FBC密码算法的数据分组长度和密钥长度至少为128比特,记为FBC-128.目前对FBC-128算法差分攻击的最好结果是12轮,时间复杂度为293.41次加密,数据复杂度为2122个选择明文对.然而,FBC算法是否存在更长的差分区分器,能否对其进行更高轮数的密钥恢复攻击仍有待解决.本文基于混合整数线性规划(MILP)的自动化搜索方法,提出了“分段统计法”来求解FBC-128的差分特征.实验测试结果表明:FBC-128存在15轮差分区分器,其概率为2-121.然后将其向后扩展1轮,对16轮FBC-128算法发起密钥恢复攻击,其数据复杂度为2121个选择明文数据量,时间复杂度为292.68次加密.与已有结果相比,差分区分器和密钥恢复攻击都提升了4轮,并且所需的数据复杂度和时间复杂度更低.

军用自动测试设备更新决策研究

为了节约军用自动测试设备研制经费和全寿命周期费用,提升设备快速保障能力,达到效费比最大化目标,从测试保障整体角度,分析了被测对象需求、自动测试设备费用和测试设备服役寿命,对军用测试设备的更新问题建立了基于混合整数线性规划方法更新决策模型。针对某型军用飞机测试需求,分析不同基准费用条件下测试设备的更新决策问题,对比了更新决策结果对不同影响因素的灵敏度,得到了不同服役寿命设定条件下的更新决策结果,结果表明:5~7倍单台基准费是98%被测对象对应测试设备更新决策的临界点;更新决策结果对移植费用灵敏度最高;新设备使用寿命延长到20a时,可显著影响更新决策结果。

面向客流聚集风险防控的城轨列车实时调度模型与算法

“后疫情时代”下,我国城市轨道交通客流量快速反弹并进一步持续攀升。在此背景下,以缓解车站拥挤度为目标,研究面向客流聚集风险防控的列车实时调度问题具有重要的现实意义。在线路运营受到异常事件干扰条件下,结合列车跳停策略和运行图协同调整,以最小化线路车站拥挤度为目标函数,以车厢满载率为模型约束,建立列车实时调度混合整数线性规划模型。为提高模型求解效率,提出可变邻域搜索算法,首先基于线性规划松弛原理设计模型初始解的启发式计算规则,之后基于可变邻域搜索算法寻找初始解邻域内的近似最优解作为列车实时调度问题的最终解。使用北京地铁亦庄线实际数据进行了仿真实验,仿真结果表明:以标准“站站停”策略生成的运行图调整方案作为评价基准,采用可变邻域搜索算法计算得到的列车实时调度策略可降低线路拥挤度约67.56%,减少约38.28%的线路最大断面客流量,计算时间在1 min左右,可满足列车实时调度的需求,验证了本文提出的列车实时调度模型与求解算法能有效降低车站拥挤度、均衡线路客流的断面分布,对突发大客流带来的车站乘客聚集问题具有较好的调整效果。

柔性流水车间调度模型与混合引力算法

针对柔性流水车间调度问题,利用机器特定事件点来描述工件的机器选择,再以最小化最大完工为目标,考虑工艺约束和时间约束构建了柔性流水车间调度的混合整数线性规划模型,用GAMS/Cplex找到小规模问题的全局最优解。为快速求解大规模问题的近优解,提出了结合瓶颈启发式的引力搜索算法,利用瓶颈移动技术和John Son方法的解码机制,寻找最小化最大完工时间的最优调度方案。实验结果表明,所提出的模型及算法能高效地求解以最小化最大完工时间为目标的柔性流水车间调度问题。

求解安全约束机组组合问题的邻域搜索外逼近方法

提出一种求解安全约束机组组合(security constrained unit commitment,SCUC)问题的邻域搜索外逼近(outer approximation based on neighborhood search,NS-OA)法. OA将SCUC问题分解为一系列混合整数线性规划(mixed integer linear programming,MILP)主问题和非线性规划(nonlinear programming,NLP)子问题,通过MILP主问题和NLP子问题的最优解来逼近SCUC问题的最优解.为克服迭代过程中MILP主问题规模大的不足,利用SCUC问题对应UC问题的最优解为中心来构造邻域,然后在此邻域内搜索MILP主问题的最优解.数值结果表明,所提邻域搜索能有效减小搜索空间,大大提高了算法的计算效率,所提NS-OA算法能有效求解大规模SCUC问题,具有良好的应用前景.

随机行驶电动汽车禁忌搜索充电定位算法

在分析确定性流动充电定位问题的基础上,建立电动汽车期望流动充电定位模型解决电动汽车行驶范围随机性和不同充电需求带来的充电站选址问题。针对模型中电动汽车随机行驶问题,采用禁忌搜索算法进行启发式求解分析,以获取最佳定位解。实验数据表明,禁忌搜索算法可在较短计算时间内始终提供高质量的解,为充电站的规划定位提供理论支撑。

基于最小成本的飞机着陆规划算法

在以往着陆规划中,较少考虑公司的成本。利用航班的成本函数,建立了满足着陆间隔、着陆时间段等约束的着陆规划模型,提出了一种使用局部搜索和线性规划的启发式算法。实例验算表明,所给模型及算法可以在合理的时间内求解大规模规划问题,有效地降低公司成本。

基于遗传算法的自动化集装箱码头多载AGV调度

为提升自动化集装箱码头的作业效率,减轻码头吞吐量增大带来的交通问题,降低自动化导引小车(Automated Guided Vehicle,AGV)的空载率,在自动化集装箱码头应用可以同时搬运不止一个集装箱的多载AGV,建立多载AGV调度问题的混合整数线性规划(Mixed-Integer Linear Programming,MILP)模型,应用遗传算法进行求解.借助算例,对比遗传算法与MILP算法的求解效果,分析交叉概率和变异概率对遗传算法的影响,比较多载AGV与单载AGV的作业时间,验证遗传算法的可靠性.该方法表明,遗传算法不仅求解效率高,而且对MILP算法不适用的大、中型多载AGV调度问题,也能给出值得信赖的近似最优解.

集装箱码头装卸运输路径轨迹规划研究

集装箱码头装卸运输路径轨迹规划研究的目的是为了实现AGV的无碰撞轨迹规划。能效调度是AGV在执行集装箱任务过程中不可忽略的重要因素,AGV的能效调度会影响AGV的实际作业轨迹,因此集装箱码头装卸运输路径轨迹规划研究的难点技术之一是如何协调AGV的能效调度与AGV的轨迹规划以实现AGV的无碰撞轨迹。针对上述问题,提出了一种实现AGV无碰撞轨迹规划的两阶能效法。在考虑静止障碍与移动障碍的情况下,采用分层控制结构来协调AGV的能效调度与AGV的轨迹规划,以最小化AGV作业加速度累积和为目标,建立AGV轨迹规划问题的混合整数线性规划模型。通过设计AGV的作业时间窗,得到了两个AGV的无碰撞作业轨迹。通过仿真,得到两个AGV作业的相对距离和各自的能耗。仿真结果验证了所提方法对协调AGV能效调度与AGV轨迹规划来实现AGV无碰撞轨迹规划的有效性。

一种改进的刻画S盒的球方法

近年来,混合整数线性规划(mixed integer linear programming,MILP)被广泛应用于密码分析中.MILP方法中的一个关键数学问题是,对于一个给定点集S■{0,1}n,寻找不等式个数尽可能少的线性整系数不等式组,使得其在{0,1}n上的解集恰好是S,称该问题为S的线性整系数不等式完全刻画(full linear integer inequality characterization,FLIIC)问题.本文针对FLIIC问题改进了Coggia和Boura在会议FSE 2020上提出的球方法.对于半径为2的球的一个子集,给出了一个充要条件,其可以用来判定该子集是否可以只用一个整系数线性不等式完全刻画.该充要条件完全涵盖了Coggia和Boura的球方法中半径为1和2以及合并3个半径为1的球的情况.此外,进一步将球的半径从2扩展到了3,该方法可以对较大规模的S盒进行快速求解,例如对AES中使用的S盒,获得了含有2740个不等式的完全刻画.

多无人平台持续作业调度问题

针对单无人平台因电池或燃料有限而不能完成持续时间超过其最大续航时间的问题,提出通过地理上分散的自动补给站支持的多无人平台持续作业,从而可完成长期或不间断任务的思想;提出混合整数线性规划模型形式化多无人平台系统的调度问题,使每个任务均有无人平台执行,而多无人平台的总距离及出行总成本最小化;最后,在Matlab 2014a下验证了模型的有效性,模型在优化目标目标函数的同时保证了无人平台的安全性。

ACE密码算法的积分分析

ACE是国际轻量级密码算法标准化征集竞赛第2轮候选算法之一。该算法具有结构简洁,软硬件实现快、适用于资源受限环境等特点,其安全性备受业界广泛关注。该文引入字传播轨迹新概念,构建了一个传播轨迹的描述模型,并给出一个可以自动化评估分组密码算法抵抗积分攻击能力的方法。基于ACE算法结构特点,将该自动化搜索方法应用于评估ACE算法的安全性。结果表明:ACE置换存在12步的积分区分器,需要的数据复杂度为2^(256),时间复杂度为2^(256)次12步的ACE置换运算,存储复杂度为8 Byte。相比于ACE算法设计者给出的积分区分器,该新区分器的步数提高了4步。

解决高维INLP和MINLP问题的混沌差分进化算法

为改进差分进化(Differential Evolution,DE)算法的搜索能力,提出一种新的混沌差分进化算法(CGLSDE).首先,该算法利用混沌序列替换DE参数并采用混沌全局搜索算法来改进DE的全局搜索能力;其次,CGLSDE算法还采用了单维和多维的混沌局部搜索来改进DE的局部搜索能力.仿真结果表明:CGLSDE算法在解决高维整数非线性规划(INLP)问题和高维混合整数非线性(MINLP)问题上,其性能要好于其它3种混沌差分进化算法.

互联网家装服务中的供应链优化模型

互联网家装行业日趋火爆,行业的不断完善使得企业竞争重心逐渐从营销端转移至供给端,物流与配送体系建设将成为未来互联网家装企业发展的重点。对互联网家装企业的建材供应链进行了深入研究,探索最优化的建材存储、配送以及补充方式。将互联网家装企业的线下业务流程转化成供应链优化问题,建立混合整数线性规划模型求解最优解。针对该供应链优化问题,设计了禁忌搜索算法进行近似求解,获得了逼近模型最优解的近似解,并通过计算实验评估了近似算法优化效果。

基于虚拟车队的自动交叉路口车辆时序优化模型

智能网联汽车可通过彼此交互协同安全地通过交叉路口,自动交叉路口控制已成为未来发展趋势。为解决现有基于预约的自动交叉路口控制模型未全局优化车辆通过顺序及模型非线性导致求解效率低等问题,提出一种基于虚拟车队的自动交叉路口车辆时序优化模型,实现车辆通过时序的高效全局优化。首先,为构建到达安全时间间隔约束,基于车辆冲突分析计算交叉口进口道停车线到各相互作用点的距离。其次,为便于建模和求解,基于时间维度构建虚拟车队并形成车辆索引序列。然后,以交叉口车辆总延误最小为优化目标,车辆通过控制区段的最小行程时间和到达冲突区域边界的安全间隔为约束条件,构建自动交叉路口车辆通过时序非线性优化模型。在此基础上,引入0-1变量将该模型转化为混合整数线性规划模型,并基于开源求解器CBC对模型进行求解。最后,设计数值仿真试验验证模型的有效性并进行了模型的参数敏感性分析。研究结果表明:所构建模型在不同交通需求下优化效果均优于基于“先到先服务”规则的模型,车均延误和最大单车延误能够减少61.50%和39.73%;当安全间距和优化周期较大时,构建模型的延误控制效果更为显著;模型和算法为未来智能网联环境下自动交叉路口控制提供了一种可选的方法。

基于滤波波束搜索算法的置换流水车间调度问题

【目的】研究解决置换流水车间中作业完成时间与常见到期日之间的绝对偏差最小化和中间库存最小化问题。【方法】首先,构建基于最小化绝对偏差和中间库存的混合整数线性规划模型,采用两阶段法对模型进行求解;其次,提出基于精英选择策略的滤波波束搜索算法(Filtered beam search algorithm,FBSA),将精英选择策略与FBSA融合,通过对有"希望"的迭代节点进行局部搜索和全局搜索,用以确定筛选出的最优解。【结果】通过实例仿真对基于精英选择策略的FBSA与其他智能优化算法在最优解偏差百分比、平均错误率、改进百分比等3个指标进行对比,结果显示该算法在求解所提问题时具有高效性和稳定性。【结论】基于精英搜索策略的FBSA对处理置换流水车间调度问题有着良好的效果与优势。