多项式0-1规划中隐枚举算法的改进及应用

提出了一个求解多项式0-1规划问题的隐枚举算法.通过应用p次范数约束划归,多项式0-1规划问题的多个约束可以被一单一等价约束来替代.利用这一显著特性,新算法在搜寻最优解过程中,能改进探寻(fathoming)和折返(backtrack)策略以提高隐枚举法的计算效率.通过一个算例说明这个新算法的计算步骤并对随机产生的问题进行了测试,得到了较好的结果.     

不确定信息QoS路由的概率遗传算法的研究

QoS路由是保证网络服务质量的重要组件。但网络状态信息具有固有的不确定性,因此有必要研究不确定信息对QoS路由的影响。通过假设网络带宽和时延的分布符合某种随机变量的特点,分别用概率方法表示出带宽和时延的不确定性,然后求出路径满足给定QoS约束的概率,最后在遗传算法的计算过程中,选择合理的适应度函数,找出满足QoS约束的最大概率解。仿真结果表明该方法能够保证得到满意解的同时缩短搜索时间。     

广义离散时滞复杂动态网络的同步控制

讨论了一类广义离散时滞复杂动态网络的同步稳定性和牵制控制问题.针对此类系统,首先得到了弱保守性的离散时滞复杂动态网络系统的同步稳定性条件.其次,通过对部分节点设计牵制控制器,使得整个复杂动态网络系统达到同步,从而保证了整个系统的同步稳定性.随后,将控制器的设计问题转化为求解线性矩阵不等式(LM I)的凸优化问题,便于利用现有的优化软件求解.同时,大大降低了问题求解的复杂性.仿真结果验证了方法的有效性.     

非线性约束最短路问题的启发式算法

多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题。它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法。然而这些方法只能求解一些带有线性约束的RSP。对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性。本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP。主要思想是将非线性约束作为检验条件来使用。当每得到一个解时,检查解是否满足非线性约束。如满足,则得到最终解;否则在原问题中添加一个线性约束。该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解。仿真算例说明了算法的有效性。     

基于时间槽的敏捷供应链集成调度模型及优化

针对市场需求出现后敏捷供应链需要选择各级部件供应商并安排对应的生产运输调度问题,以准时满足市场需求为基本约束,以供应链库存、生产和运输总成本最小为目标函数,建立了基于供应商可用时段时间槽表示方式下的敏捷供应链集成调度INLP模型;基于该模型具有大量的时间和数量约束,设计了以时间槽实数编码作为基因编码的混合遗传算法,在解码过程中引入贪婪-序的解码方法保证产生满足约束的解,加速算法收敛和寻优; 最后以算例验证模型和算法的有效性和稳健性.     

约束规划求解集装箱装卸系统集成调度问题

集装箱码头装卸系统中的岸桥、集卡和场桥的集成调度问题本质上是有阻塞、准备时间可分离并且依赖操作顺序的三阶段混合流水车间调度问题,现有文献多采用启发式算法求解该问题.本文先建立了一个紧凑的混合整数规划模型,然后从约束规划的角度建模求解该问题,提出了一个约束规划模型,以区间变量作为决策变量,并采用"扩展操作任务"的概念来定义区间决策变量以提升求解效率.为了展示约束规划的建模灵活性,还扩展了模型以考虑机器效率不同的因素.数值实验显示约束规划模型能够在很短的时间内对大规模算例求出高质量的解.     

变动补偿的多模糊选址-路径机会约束模型及算法

针对同时具有模糊需求和模糊旅行时间,且有车辆容量、配送中心容量和时间窗约束的选址-路径问题,基于预优化和实时调整的两阶段策略,引入变动成本的概念,建立变动补偿的机会约束预优化模型.在实时调整阶段,考虑多模糊参数的联合影响,定义变动成本为因车辆剩余容量不足返回配送中心卸载的额外配送成本和因车辆实际到达时间超出客户时间窗的时间惩罚成本总和.鉴于多模糊参数影响的时间窗可信度计算复杂,且已将时间惩罚成本作为变动成本的一部分修正目标函数,去掉时间窗机会约束,设计一阶段模拟退火算法求解,贪婪聚类构建初始解,随机模拟法估算变动成本.测试算例验证了模型和算法的有效性.得出,该模型可弱化偏好值的影响,生成实时调整变动幅度小且整体最优的预优化方案,提高对不确定环境的风险抵抗力,且求解简单;该算法是求解此类问题的较好算法;研究成果为多模糊选址-路径问题提供新的求解思路.     

含取整约束规划问题的一种实用算法

本文以纺织厂的生产过程为实际背景,建立了含取整约束的规划模型。鉴于用传统方法求解时所遇到的困难,本文提出了一种收缩-放松算法。这一算法具有计算量小、程序简单等特点,能较快地求得含取整约束规划问题的次优解(也许是最优解),在实际使用中已取得良好效果。     

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优. 该问题是一个NP-完全问题. 提出了一种新的基于整数线性规划模型选择路由的方法. 思路是将复杂约束引入到目标函数作为罚项, 得到一个松弛整数线性规划问题. 因为约束系数矩阵是全幺模矩阵, 松弛问题可以通过线性规划很快地求解. 拉格朗日乘子的调整用罚函数的方法很容易计算. 数值实验表明提出的方法是有效的.     

大规模Job Shop调度的多级邻域变量排序算法

在基于约束满足的Job Shop调度问题求解过程中,变量赋值顺序是影响搜索效率的关键因素.根据问题的约束拓扑关系,提出了变量的多级邻域结构模型,在此基础上构造了一种新的变量排序算法,通过引导当前搜索介入临界区域来提高计算效率.数值实验表明该算法能够有效地改善大规模Job Shop调度问题的求解效率.     

基于线性近似和神经网络逼近的模型预测控制

针对非线性系统的模型预测控制问题,提出了一种基于线性近似和神经网络逼近的控制算法。用Taylor级数展开法对非线性系统进行线性近似时,要求对象系统中的非线性函数必须连续可微。为了突破这一限制,引入了Stirling插值公式线性近似法,拓展了可处理的非线性系统范围。通过对线性化过程中产生的非线性高阶项进行径向基函数(radial basis function, RBF)神经网络逼近,显著提高了对象系统模型精确度。为了降低数值计算复杂度,将控制性能指标函数重构为易于处理的二次型最优化问题,通过对该二次型最优化问题的求解得到了最优控制序列。控制过程考虑了约束条件的影响以模拟真实的工业生产过程。仿真结果证明了所提出预测控制方案的有效性。     

Distributed sampling measurement method of network traffic in high-speed IPv6 networks

With the advent of large-scale and high-speed IPv6 network technology, an effective multi-point traffic sampling is becoming a necessity. A distributed multi-point traffic sampling method that provides an accurate and efficient solution to measure IPv6 traffic is proposed. The proposed method is to sample IPv6 traffic based on the analysis of bit randomness of each byte in the packet header. It offers a way to consistently select the same subset of packets at each measurement point, which satisfies the requirement of the distributed multi-point measurement. Finally, using real IPv6 traffic traces, the conclusion that the sampled traffic data have a good uniformity that satisfies the requirement of sampling randomness and can correctly reect the packet size distribution of full packet trace is proved.     

针对多星多任务仿真调度的关键路径遗传算法

卫星任务规划问题的求解空间随卫星数量和目标数量的增多而快速增大,针对大规模多星多任务规划问题,提出一种基于关键路径-遗传算法的卫星任务规划分层优化方法。该方法将卫星任务规划问题分解成任务分配和单星任务处理2个子问题,其中,任务分配通过遗传算法实现,一个分配结果对应种群中的一个个体,在单星任务处理子问题中引入关键路径法,用于求解每个个体的适应度,在提高优化效率的同时,确保得到当前任务分配条件下的最大观测效益,提高算法的全局优化能力。仿真结果表明,对于给定的6组大规模卫星任务规划算例,平均任务完成率均超过了99.7%,证明了该方法具有良好的稳定性和全局搜索能力;同时,相比于已有方法,该方法在优化效率上也有大幅提高,且任务规模越大,优化效率提升越大。     

改进的模糊网络关键路径法

提出一种改进的模糊取最大运算和模糊减运算以确定模糊网络中的模糊时间参数. 改进的基于区间数距离测度的模糊取最大运算,通过枚举不同α-cut值,计算活动的模糊最早开始时间并确定项目可能变化的关键路径,从而解决了现有的研究中忽视了在活动工期模糊的情况下关键路径可能会发生变化的问题. 用改进的模糊减运算来计算活动的模糊最晚开始时间,有效避免了在传统的逆向递推计算中可能出现负的或者不可行解的情况. 通过一个实例验证了所提出的方法求解模糊网络时间参数的有效性和优越性. 所提出的方法不仅可用于模糊网络时间参数计算,也可以用于模糊资源受限项目调度问题.     

基于深度强化学习的网络路由优化方法

针对同一网络拓扑下不同网络负载的路由优化问题, 在深度强化学习方法的基础上, 提出了两种依据当前网络流量状态进行路由分配的优化方法。通过网络仿真系统与深度强化学习模型的迭代交互, 实现了对于流量关系分布的网络路由持续训练与优化。在利用深度确定性策略梯度(deep deterministec policy gradient, DDPG)算法解决路由优化问题上进行了提升和改进, 使得该优化方法更适合解决网络路由优化的问题。同时, 设计了一种全新的链路权重构造策略, 利用网络流量构造出用于神经网络输入状态元素, 通过对原始数据的预处理加强了神经网络的学习效率, 大大提升了训练模型的稳定性。并针对高纬度大规模网络的连续动作空间进行了动作空间离散化处理, 有效降低了其动作空间的复杂度, 加快了模型收敛速度。实验结果表明, 所提优化方法可以适应不断变化的流量和链路状态, 增强模型训练的稳定性并提升网络性能。     

考虑成本约束的复杂RFID网络线路仿真规划

运用仿真优化方法对复杂RFID网络设施间铺设线路整体规划问题进行了研究。规划目标是在RFID网络设施位置给定的前提下最小化线路铺设成本,通过分析RFID系统设施间的约束规则,将成本最小化问题转化为求网络中特定节点间的综合路径最短问题,构建了相应仿真规划数学模型,并利用改进Dijkstra算法对其进行辅助求解。仿真实验结果表明,通过线路仿真规划后的铺设成本明显减少,这为科学实施RFID系统提供了正确决策。     

Bilevel programming model and solution method for mixed transportation network design problem

By handling the travel cost function artfully, the authors formulate the transportation mixed network design problem (MNDP) as a mixed-integer, nonlinear bilevel programming problem, in which the lower-level problem, comparing with that of conventional bilevel DNDP models, is not a side constrained user equilibrium assignment problem, but a standard user equilibrium assignment problem. Then, the bilevel programming model for MNDP is reformulated as a continuous version of bilevel programming problem by the continuation method. By virtue of the optimal-value function, the lower-level assignment problem can be expressed as a nonlinear equality constraint. Therefore, the bilevel programming model for MNDP can be transformed into an equivalent single-level optimization problem. By exploring the inherent nature of the MNDP, the optimal-value function for the lower-level equilibrium assignment problem is proved to be continuously differentiable and its functional value and gradient can be obtained efficiently. Thus, a continuously differentiable but still nonconvex optimization formulation of the MNDP is created, and then a locally convergent algorithm is proposed by applying penalty function method. The inner loop of solving the subproblem is mainly to implement an all-or-nothing assignment. Finally, a small-scale transportation network and a large-scale network are presented to verify the proposed model and algorithm. This research is supported by the National Basic Research Program of China under Grant No. 2006CB705500, the National Natural Science Foundation of China under Grant No. 0631001, the Program for Changjiang Scholars and Innovative Research Team in University, and Volvo Research and Educational Foundations.     

多峰函数优化的免疫人工鱼群网络算法

针对人工鱼群算法(artificial fish swarm algorithm, AFSA)多峰寻优能力不足的问题,提出了一种免疫人工鱼群网络算法。应用改进的觅食行为,提升了算法的局部寻优能力;采用免疫网络调节机理,保持了人工鱼群多样性,不〖JP2〗断探寻新的局部峰值;执行模式搜索法（pattern search method, PSM）,完成精英人工鱼群的精细搜索。仿真实验结果表明,该算法具有较强全局优化能力和局部优化能力,且搜索到每个最优解都达到了理想值。     

随机游动法在环状河网计算中的应用研究

环状河网求解不同于树状河网,在采用三级解法进行环状河网非恒定流计算时常面临求解大型矩阵的难题.针对这一问题,从水流质点游动角度出发,研究将随机游动方法应用于环状河网水位计算,实现随机游动方法与三级解法相结合.在三级解法得到节点水位方程组基础上,给出节点水位的随机显式求解新方法,然后采用追赶法完成整个河网水位流量计算.与常规三级解法相比,该方法求解原理简单,避免了大型矩阵的直接求解.将新方法建立模型运用于西江下游河网计算,结果表明,该方法较常规方法在简化运算的同时提高了计算效率,并且与常规三级解法具有同样的精度.模型计算结果也量化了各节点水位之间的相对联系情况.     

基于堆栈式LSTM网络的通信辐射源个体识别

针对现有通信辐射源个体识别方法预处理过程复杂及特征提取较难的问题,提出了一种基于堆栈式长短期记忆(long short-term memory, LSTM)网络的辐射源个体识别算法。该算法直接使用IQ时间序列信号训练LSTM网络,即可实现对通信辐射源个体的高效识别,避免了复杂的信号预处理过程。为使LSTM网络能更好地适用于通信辐射源个体识别,利用3层LSTM网络提取辐射源深层特征,并通过实验优化了网络参数。然后对该算法的实际应用泛化性进行了实验探究,结果表明该算法在其他辐射源数据集上也取得了较好的效果。最后,通过实验对算法进行了验证,结果表明相比于传统算法,在样本数较多时,该算法的识别准确率可以达到98%,而且简单快速智能,便于工程化与实用化。