求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析

旅行商问题（Traveling Salesman Problem,TSP）是组合优化中最典型的NP难问题之一,长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题,并设计出许多高效实用的启发式和宏启发式算法,其中循环LK算法是性能最好和最具代表性的算法之一．作者研究了该算法的运行时间分布：通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合,发现求解TSP问题的循环LK算法的运行时间分布很好地服从Weibull分布,并进一步给出了该分布对求解TSP问题的物理意义．作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论．     

基于遗传算法的TSP问题求解算法及其系统

TSP问题为组合优化中的经典的NP完全问题。针对这一问题,首先设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,给出了基于遗传算法求解TSP问题的一般性流程,然后设计并实现了基于遗传算法的TSP问题求解系统,给出了求解系统的体系结构,并给出了求解系统基于Ja-va语言的实现机制,最后通过实验结果的分析,表明了算法具有较好的寻优性能,系统具有较好的实用性。     

TSP问题的脂肪计算复杂性与启发式算法设计

旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P(NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法--动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.     

求解TSP的人工萤火虫群优化算法

人工萤火虫群优化算法是一种新型群体智能算法,已在复杂多目标函数优化方面得到了成功的应用,并表现出良好的性能.为了充分发挥人工萤火虫群优化算法的优点,将该算法与C2Opt算子相结合,设计了求解旅行商问题(TSP)的一个新的高效人工萤火虫群优化算法,并用其求解TSP这一经典的NP难问题.通过对比TSP实例测试,所得结果表明,所提出算法在种群规模较小、迭代次数较少的情况下可以收敛到已知的最优解.     

一种Hopfield神经网络算法复杂性研究的新方法

首先分析了基于Hopfield神经网络的TSP问题求解方法,提出从研究能量函数、状态空间分布和可行解的关系来研究以Hopfield为代表的优化神经网络的计算复杂性的思想;并给出从状态空间到线性表的映射方法,引入状态-程序复杂性。分析结果表明,绝对状态一程序复杂性更为充分地反映能量函数的求解过程;相对状态-程序复杂性提供了一种在多项式时间内对NP问题算法的有效性进行衡量的尺度。     

一个具有平均复杂性的SAT问题

最坏复杂性到平均复杂性的归约已被研究很多年。很多NP困难问题是最坏复杂性的。distNP类是平均复杂性的NP类,且有完全问题。LIVEN N证明了所有自然的NP完全问题都有平均复杂性的形式,但是他给出的概率分布是不自然的。在格问题方面,AJTAI和REGEV O分别提出了平均复杂性的困难问题,即短整数解问题(Short Integer Solution,SIS)和带错误学习问题(Learning With Errors,LWE)。给出一个可以归约到判定对于一个NP完全问题是否存在多项式时间算法,对值为1的实例给出一个见证,并且对值为0的实例给出一个归结辩驳的具有平均复杂性的SAT问题。本文方法是将求解NP完全问题的多项式时间算法的存在性转化成SAT问题的一组实例。同时也给出了这个问题的一些变形问题。     

蚁群算法及其在TSP问题中的应用研究

TSP问题是一类典型的NP完全问题,蚁群算法是求解该问题的方法之一。该文在研究蚁群算法的基本优化原理的基础上,建立了求解TSP问题的数学模型,设计了一个求解TSP问题的蚁群算法程序,并通过仿真实验验证了算法的有效性,分析了蚂蚁规模、周游次数等因素对蚁群算法搜索结果所产生的影响。     

Ising图模型概率推理的计算复杂性

图模型概率推理的主要任务是通过对联合概率分布进行变量求和来计算配分函数、变量边缘概率分布、条件 概率分布等。图模型概率推理计算复杂性及近似概率推理的计算复杂性是一重要的理论问题,也是设计概率推理算 法和近似概率推理算法的理论基础。研究了Ising图模型概率推理的计算复杂性,包括概率推理的难解性及不可近似 性。具体地,通过构建#2 SA"I'问题到Icing图模型概率推理问题的多项式时间计数归约,证明在一般 Ising图模型上 计算配分函数、变量边缘概率分布、条件概率分布的概率推理问题是#P难的,同时证明Icing图模型近似概率推理问 题是NP难的,即一般Icing图模型上的概率推理问题是难解且不可近似的。     

用改进遗传算法求解影片投递问题(FDP)

影片投递问题是近十几年来研究相当活跃的旅行商问题(TSP)的拓展,是组合优化的新问题。FDP也是一个NP难问题,且一般比TSP要难解得多。本文采用改良点编码方案,运用惩罚函数、禁止相同基因段交叉和重置变异参数的技术以避免非可行解的干扰,通过测试发现：标准遗传算法的选择机制和FDP问题求解的常用交叉和变异方法,两者之间的简单撮合很难实现求解。经多次试验数据证明,改进后的算法大大提高了全局收敛性性能。     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

Cloud Computing System Management Under Flat Rate Pricing

Success of cloud computing service depends on an acceptable pricing mechanism both by users and the service provider. Piece rate pricing by counting work load should be favorable for the service provider due to the QoS control and finite resource, such as computing and, communication powers. Though the pricing mechanism based on counting work load is reasonable and fair, the experiences learned from ADSL, 3G and Wi-Fi show a different story. The flat rate pricing mechanism is the winner all the way. This study proposes a flat rate pricing mechanism with congestion control, called FRPCC. In the cloud computing system, allocation of resources can be formulated as an optimization problem seeking to maximize the sum of the utility function of each user under the constraints of fairness. The piece rate pricing mechanism is easy to achieve the social welfare but is not easy to be acceptable for customers. Consequently, we propose a congestion control scheme to reach the same goal with a flat rate pricing mechanism. The proposed FRPCC approach can achieve social welfare in the cloud computing environment. Performance evaluations show efficacy of, FRPCC approach in providing social welfare under fairness and preventing congestion.     

PCB数控钻孔最佳走刀路线的建模与求解

目前,采用PCB数控钻自动编程系统生成的钻孔路线并非最佳走刀路线。通过分析,将PCB数控钻孔最佳走刀路线问题归结为大型TSP问题,其目标函数定为钻头的总走刀时间最短。由于TSP问题在理论上属于NP完备问题,因此很难用一般的算法求解。文中详细介绍了用模拟退火方法求解该问题的具体算法,并以上继基础开发了PCB的最优化的自动编程系统。     

PCB数控钻孔最佳走刀路线的建模与求解

当前的印刷电路板（ＰＣＢ）数控钻自动编程系统生成的钻孔路线并非最佳走刀路线。本文通过分析,将ＰＣＢ数控钻孔最佳走刀路线问题归结为大型ＴＳＰ问题,其目标函数定为钻头的总走刀时间最短。由于ＴＳＰ问题在理论上属于ＮＰ完备问题,很难用一般的算法求解。本文详细介绍了用模拟退火方法求解该问题的具体算法,并以此为基础开发了ＰＣＢ最优化的自动编程系统。     

Dynamic task assignment and resource management in cloud services by using bargaining solution

Cloud computing provides infrastructure, platform and software as services to customers. For the purpose of providing reliable and truthful service, a fair and elastic resource allocation strategy is essential from the standpoint of service customers. In this paper, we propose a game theoretic mechanism for dynamic cloud service management, including task assignment and resource allocation to provide reliable and truthful cloud services. A user utility function is first devised considering the dynamic characteristics of cloud computing. The elementary stepwise system is then applied to efficiently assign tasks to cloud servers. A resource allocation mechanism based on bargaining game solution is also adopted for fair resource allocation in terms of quality of service of requested tasks. Through numerical experiments, it is shown that the proposed mechanism guarantees better system performance than several existing methods. The experimental results show that the mechanism completes the requested tasks earlier with relatively higher utility while providing a significant level of fairness compared with existing ones. The proposed mechanism is expected to support cloud service providers in elastically managing their limited resources in a cloud computing environment in terms of quality of service. Copyright © 2013 John Wiley & Sons, Ltd.     

基于多Agent的复合模型求解自适应QoS机制

在基于网络的分布式系统应用基础上,分析了大型复杂问题复合模型协作求解的过程特征描述,提出基于多Agent 的领域问题协作求解的主动控制策略,探讨了用户交互Agent、系统主控Agent、协作Agent以及模型Agent和数据Agent等复合模型协作求解的4种Agent类型。应用多Agent层次结构,提出一种复合模型协作求解的自适应QoS体系结构,通过实现复合模型协作求解的主动调度规划算法对其进行了验证,支持分布式网络环境下实现模型资源和数据资源的共享,以提高协同计算环境分布式问题协作求解的运行效率和服务质量。     

云计算环境下的数据挖掘服务模式

为了求解网络环境下分布式海量数据的分析处理、促进数据挖掘的开发集成和商业应用,提出了云计算环境下的数据挖掘解决方案,通过云环境计算能力和云计算服务模式,阐述了对数据挖掘服务问题的解决机理。云计算环境下的数据挖掘是一种网络环境下的信息资源服务模式。基于此,构建了数据挖掘服务的架构,设计了数据挖掘服务的创建流程,给出了数据挖掘服务模型的体系结构,并从生命周期的角度定义了数据挖掘的服务过程,从而形成了云计算环境下的数据挖掘服务模式。     

云计算时代对信息安全的影响及对策分析

云计算是一种基于Internet新兴的计算机应用技术。其远景是以互联网为基础,为广大互联网用户提供安全可靠、方便快捷的互联网服务和强大的计算能力。在云计算环境下,信息安全问题不但是云计算面临的首要问题,而且将成为决定云计算发展的规模和前景的决定性问题。通过从云计算的概念、特征和及目前已存在的问题出发,浅析云计算环境下的信息安全问题。     

基于Anytime算法的组合优化问题求解

介绍一种基于Ａｎｙｔｉｍｅ算法的组合优化问题求解框架,并报告了对ＴＳＰ问题进行求解的实验。实验结果表明,上述框架可以较好地协调２的复杂度与求解时间要求之间的冲突。