一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

求解多旅行商问题的新混合遗传算法:以应急物资配送为例

为优化生物反恐条件下的应急物资配送过程,将该环境下的应急物资配送问题构造为一多旅行商问题(MTSP),并从理论上分析了该旅行商回路为最短Hamilton路径。以此问题为背景,针对应用传统遗传算法求解多旅行商问题时存在收敛速度缓慢等问题,提出并设计了一类新的混合遗传算法。该类新遗传算法与传统遗传算法的最主要区别在于,针对多旅行商问题专门设计了一种新的染色体编码规则、排序算子和交叉算子。仿真结果表明,该算法能够快速收敛到问题的近似最优解,并能很好地维持种群的多样性。     

基于递阶遗传算法的一类多旅行商问题优化

针对最小化单个旅行商路程的多旅行商问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性.     

基于改进蚁群算法的钢铁企业合同计划方法

基于钢铁企业的合同计划管理要求,建立了以产能平衡和最小化拖期提前总惩罚为目标的多目标数学规划模型,综合考虑了工序的前序关系、工序的产能和库存的约束.将生产合同与生产工序转换为节点图,从而将合同计划问题抽象成一种改进的旅行商问题.根据模型和问题的特点设计了带交货期启发信息的蚁群算法,并以钢厂实际合同数据为例进行实验.结果表明,改进蚁群算法获得的最好解和计算成本都比较令人满意,模型和算法是有效的.     

基于差分进化算法的多旅行商问题优化

针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的.     

可折叠集装箱接驳运输问题的建模与优化

对一类带时间窗的可折叠箱接驳运输问题进行了研究,其中使用可折叠箱在堆场与客户之间集散货物,一辆集卡可装载一个满箱或多个空箱,目标为集卡总工作时间的最小化.借鉴确定的活动在顶点上的图的思想,将该问题分解为满箱子问题和空箱子问题,其中满箱子问题类似于带时间窗的多旅行商问题,空箱子问题因客户的货物量可为负值而显著区别于车辆路径问题,且两个子问题之间存在访问时间耦合等关联.进而建立了问题的数学描述,设计了问题的主动禁忌搜索(reactive tabu search,RTS)求解算法,并基于随机生成的大量算例验证了算法的有效性.结果表明,相比于使用CPLEX等优化软件,RTS算法可以在更短的时间内求得问题的更优解;相比于使用标准箱的情形,使用可折叠箱可节省约13%的接驳成本.     

基于粘贴系统求解TSP问题

旅行商问题，简称为TSP问题，是困难的NP完全问题，在工程实践中具有广泛的应用。利用常规的计算方法求解这个问题，计算所需的时间是随着问题规模的增大以指数形式增加的，因而无法有效的解决此类问题。DNA计算是一种新兴的计算方式，粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型。通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈，利用粘贴系统模型的巨大并行性，可以有效的求解旅行商问题。     

基于偏好信息的多目标旅行商问题Pareto优化求解

多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性.     

基因重组算法设计及多目标旅行商问题求解

遗传算法等启发式算法在求解旅行商问题时,存在收敛速度较慢、容易出现过早收敛及算法计算效率较低的问题。在模式理论基础上,提出一种新的基因重组算法。根据优良基因模式,设计模式重组算子,运用重构及进化规划的思想设计算法的个体重构算子和个体选择算子。建立一个多目标旅行商问题模型,分析每一轮计算旅行路线适应度值的差异性,采用熵值法确定路程和费用权重。系列实验表明,基因重组算法在求解多目标旅行商问题时,计算效率远高于比较的算法,收敛速度和求解精度也较一般启发式算法有明显改善。     

基于路径QoS加权分解的工作流调度算法

采用有向无环图DAG(Directed Acyclic Graph)描述的工作流在QoS约束下的调度问题是一类典型的NP难问题。分析了DAG工作流调度问题的调度目标,提出了一种基于路径QoS加权分解的工作流调度算法,通过将工作流的全局QoS约束分解为单个任务的局部QoS约束,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。在对整个DAG工作流的QoS约束进行分解时,算法对工作流的每条路径的QoS约束进行分解,并以任务可选能力服务间的单位QoS增益之和作为权值,将单条路径的QoS约束分解到组成路径的每个任务。仿真结果表明,与其他基于QoS分解的DTL、DBL等算法相比,该算法具有更高的调度效率,能够找到更好的调度方案。     

一种应用于Web服务器集群系统的URL分配算法

基于内容的Web服务请求调度算法有利于均衡服务器集群系统的负载。已有的请求分配算法大多先运用Hash方法对请求的URL进行散列,在此基础上再按一定规则对请求内容进行负载均衡调度。在分析了Web服务流量分布不均衡及已有URL散列方法存在不足的基础上,提出了一种基于URL词典排序及内容等分的URL分配算法LOCEP。该算法通过对URL进行词典序排序,按内容等分,依访问流量排序及分段互补等一系列方法将Web负载尽可能均匀地分布到多个后端服务器中。仿真实验结果表明,该算法比现有的URL散列方法具有更好的负载均衡能力。     

基于重叠型区域分解的时域积分方程法

时域平面波算法可以降低时域积分方程的计算复杂度以及内存消耗,但是时域积分方程的阻抗矩阵的近场部分元素无法减少,内存消耗依然很大。提出了利用重叠型区域分解法降低时域积分方程的内存需求,通过采取划分子区域,利用特征基函数法降低阻抗矩阵规模的方法,降低了内存消耗。数值算例验证了重叠型区域分解法结合时域积分方程能有效地用于瞬态电磁散射问题的分析。     

基于决策类分割的动态数据环境下的归纳学习

深入分析了基于分辨矩阵和传统决策矩阵的归纳学习算法中存在的问题,提出了一种新的决策矩阵及基于它的归纳学习和动态数据环境下的递增式学习方法.其主要思想是基于决策类将决策系统分割为多个子系统,并构造其新的决策矩阵,然后将决策系统上的归纳学习转化为新决策矩阵下的递增式学习.这不仅解决了动态数据环境下归纳学习问题,而且能降低矩阵空间规模,避免了传统决策矩阵算法中的重复计算.实例分析和实验结果验证了基于分治策略算法的合理性和有效性.     

New judging model of fuzzy cluster optimal dividing based on rough sets theory

To investigate the judging problem of optimal dividing matrix among several fuzzy dividing matrices in fuzzy dividing space, correspondingly, which is determined by the various choices of cluster samples in the totality sample space, two algorithms are proposed on the basis of the data analysis method in rough sets theory: information system discrete algorithm (algorithm 1) and samples representatives judging algorithm (algorithm 2). On the principle of the farthest distance, algorithm i transforms continuous data into discrete form which could be transacted by rough sets theory. Taking the approximate precision as a criterion, algorithm 2 chooses the sample space with a good representative. Hence, the clustering sample set in inducing and computing optimal dividing matrix can be achieved. Several theorems are proposed to provide strict theoretic foundations for the execution of the algorithm model. An applied example based on the new algorithm model is given, whose result verifies the feasibility of this new algorithm model.     

Multiobjective evolutionary algorithm for dynamic nonlinear constrained optimization problems

A new method to solve dynamic nonlinear constrained optimization problems (DNCOP) is proposed. First, the time (environment) variable period of DNCOP is divided into several equal subperiods. In each subperiod, the DNCOP is approximated by a static nonlinear constrained optimization problem (SNCOP). Second, for each SNCOP, inspired by the idea of multiobjective optimization, it is transformed into a static bi-objective optimization problem. As a result, the original DNCOP is approximately transformed into several static bi-objective optimization problems. Third, a new multiobjective evolutionary algorithm is proposed based on a new selection operator and an improved nonuniformity mutation operator. The simulation results indicate that the proposed algorithm is effective for DNCOP.     

商品生产规模扩张的最优化决策方法

在偏尾分布的基础上,针对生产规模扩张时变动成本、固定成本和总成本摊薄3种不同情况,给出了普遍适用的商品生产规模扩张的基本条件及最优化扩张规模的分析模型与决策方法.实证分析结果表明:本方法不仅可以有效解决一般商品生产规模的最优化扩张问题,还可以解决股票股本的最优化扩张问题.     

体系作战效能评估与优化方法综述

分析了体系作战效能评估与优化的特点,基于“整体论”提出了将体系作战效能评估与优化划分为综合评估、分析、优化3个阶段的思路,针对3个阶段需要解决的实际问题,归纳总结了适用于解决各阶段问题的典型方法,并对比分析了不同方法的优缺点。针对“整体论”思想指导下体系作战效能评估与优化在实施中面临的实际困难,从综合应用框架设计、评估指标体系构建、试验推演模式创新等方面提出了下一步的研究方向,为体系作战效能评估与优化方法的有效落地提供了支撑。     

一种基于证据修正的一致性模糊Petri网模型

针对传统的基于模糊Petri网模型的形式化推理算法不能很好地求解含闭环结构的模糊Petri网,提出了一种基于证据修正的一致性模糊Petri网模型。该模型通过引入证据修正因子,把多规则情形退化为一定置信度的带复合证据的单规则情形进行处理,有效简化了模型中的闭环结构。该模型还充分利用模糊“与”规则和模糊“或”规则的内部逻辑关系,对产生式规则中逻辑“与”和逻辑“或”两种组合关系进行了区分,克服了传统的“累加型”加权模糊逻辑方法的缺点,降低了算法推理的复杂度。最后通过实例证明了该模型的有效性,而且易于编程实现,尤其适合应用于较复杂的模糊Petri网推理。     

机动平台俯冲大斜视SAR脉冲重复频率设计

在机动平台俯冲段大斜视合成孔径雷达(synthetic aperture radar, SAR)成像中,传统脉冲重复频率(pulse repetition frequency, PRF)设计方法存在下限值过高导致数据录取量增加,且PRF值无法根据高度变化实时调整的缺陷。针对上述问题,首先构建机动平台俯冲大斜视SAR成像模型;然后提出一种新的基于等距离环的方位带宽计算方法,得到考虑运动及系统误差情况下的PRF下限值;最后提出分高度段动态选取PRF的新方法,根据平台位置动态调整较少次数的PRF值即可实现波束覆盖区内回波数据录取,解决了PRF值无法随高度变化实时调整的难题。