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

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

启发式算法设计中的骨架分析与应用

骨架是指一个NP-难解问题实例的所有全局最优解的相同部分, 因其在启发式算法设计中的重要作用而成为该领域的研究热点. 本文对目前骨架及相关概念的研究成果进行了全面综述, 将骨架本身的研究工作归纳为三个层面: 理论基础层面主要考虑骨架与计算复杂性的关系问题; 应用基础层面主要考虑如何高效地获取骨架; 应用层面主要考虑如何利用骨架进行高效启发式算法设计. 在此基础上, 本文详细讨论了骨架研究亟待解决的难题, 并指出了解决这些问题的努力方向.     

黑白二次分配问题

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>O).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.     

求解大规模TSP问题的自适应归约免疫算法

从理论上分析了影响多级算法性能的因素,并以此为依据构造了求解TSP问题的自适应归约免疫算法.该算法借助归约集的进化使归约集规模自适应增长,归约边的预测精度不断提高,从而提高了算法在归约后找到全局最优解的概率.实验结果表明,该算法比其他算法获得了质量更高的解.     

求解TSP问题的多级归约算法

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.     

基于目标增量的无等待流水调度快速迭代贪婪算法

最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PHlp,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PHlp.     

求解QAP问题的近似骨架导向快速蚁群算法

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.     

基于禁忌表的定位算法求解TSP问题

本文提出了一种基于禁忌表的定位算法求解TSP问题的快速、高效近似算法。这种算法结合了禁忌搜索算法中禁忌表及大规模构造算法和定位改进算法求解规模较大的TSP问题。计算机实例仿真证明,算法在求解质量和求解速度两方面高于著名的启发式算法的解。该算法针对TSP问题提出,是非常有效的。     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题，调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点，首先构造了的一种启发式算法，该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降，结合遗传算法的全局搜索能力，提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点，能够在较短的时间内求解较大规模的调度问题，算法的计算量小，鲁棒性好。     

Backbone analysis and algorithm design for the quadratic assignment problem

As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.     

Purposive discovery of operators

This paper introduces theGenerate, Prune and Prove (GPP) methodology for discovering definitions of mathematical operators. GPP is a task within the IL exploration discovery system. We developed GPP for use in the discovery of mathematical operators with a wider class of representations than was possible with the previous methods by Lenat and by Shen. GPP utilizes thepurpose for which an operator is created to prune the possible definitions. The relevant search spaces are immense and there exists insufficient information for a complete evaluation of the purpose constraint, so it is necessary to perform a partial evaluation of the purpose (i.e., pruning) constraint. The constraint is first transformed so that it is operational with respect to the partial information, and then it is applied to examples in order to test the generated candidates for an operator's definition. In the GPP process, once a candidate definition survives this empirical prune, it is passed on to a theorem prover for formal verification. In this paper, we describe the application of this methodology to the (re)discovery of the definition of multiplication for Conway numbers, a discovery which is difficult for human mathematicians. We successfully model this discovery process utilizing information which was reasonably available at the time of Conway's original discovery. As part of this discovery process, we reduce the size of the search space from a computationally intractable size to 3468 elements.     

Comparison of MODIS, eddy covariance determined and physiologically modelled gross primary production (GPP) in a Douglas-fir forest stand

Quantification of the magnitude of net terrestrial carbon (C) uptake, and how it varies inter-annually, is an important question with future potential sequestration influenced by both increased atmospheric CO₂ and changing climate. However the assessment of differences in measured and modeled C accumulation is a challenging task due to the significant fine scale variation occurring in terrestrial productivity due to soil, climate and vegetation characteristics as well as difficulties in measuring carbon accumulation over large spatial areas. The Moderate Resolution Imaging Spectroradiometer (MODIS) offers a means of monitoring gross primary production (GPP), both spatially and temporally, routinely from space. However it is critical to compare and contrast the temporal dynamics of the C and water fluxes with those measured from ground-based networks, or estimated using physiological models. In this paper, using a number of approaches, our objective is to determine if any systematic biases exists in either the MODIS, or the modeled estimates of fluxes, relative to the measurements made over an evergreen, needleleaf temperate rainforest on Vancouver Island, Canada. Results indicate that 8-day GPP as predicted with a simple physiological model (3PGS), forced using local meteorology and canopy characteristics, matched measured fluxes very well (r² = 0.86, p < 0.001) with no significant difference between eddy covariance (EC) and modeled GPP (p < 0.001). In addition, modeled water supply closely matched measured relative available soil water content at the site. Using canopy characteristics from the MODIS fraction of photosynthetically active radiation (fPAR) algorithm, slightly reduced the correspondence of the predictions due to a large number of unsuccessful retrievals (83%) due to sun angle, snow and cloud. Predictions of GPP based on the MODIS GPP algorithm, forced using local meteorology and canopy characteristics, were also highly correlated with EC measurements (r² = 0.89, p < 0.001) however these estimates were biased under predicting GPP. Estimates of GPP based on the most recent MODIS reprocessing (collection 4.5) remained highly correlated (r² = 0.88, p < 0.001) yet were also the most biased with the estimates being 30% less than the EC-measured GPP. Most of the variance in GPP at the site was explained by the absorbed photosynthetically active radiation. We also compared the nighttime respiration as measured over 2 years at the site with the minimum 8-day MODIS land surface temperature and found a significant relationship (r² = 0.57), similar to other studies.     

3GPP认证与密钥协商协议安全性分析

通用移动通信系统采用3GPP认证与密钥协商协议作为其安全框架,该协议对GSM存在的安全隐患作了有效的改进.对3GPP认证与密钥协商协议进行安全性研究,分析其容易遭受4种类型攻击方式.为了解决上述存在的安全隐患,提出在位置更新与位置不变两种情况下的基于公钥密码学的认证与密钥协商协议,采用形式化的分析方式证明了所提出算法的安全性,并将该协议与已有协议在安全性方面进行了比较.结果显示,所提出的协议算法能够极大地增强3GPP认证与密钥协商协议的安全性.     

3GPP认证与密钥协商协议安全性分析

通用移动通信系统采用3GPP认证与密钥协商协议作为其安全框架,该协议对GSM存在的安全隐患作了有效的改进.对3GPP认证与密钥协商协议进行安全性研究,分析其容易遭受4种类型攻击方式.为了解决上述存在的安全隐患,提出在位置更新与位置不变两种情况下的基于公钥密码学的认证与密钥协商协议,采用形式化的分析方式证明了所提出算法的安全性,并将该协议与已有协议在安全性方面进行了比较.结果显示,所提出的协议算法能够极大地增强3GPP认证与密钥协商协议的安全性.     

0-1背包问题的两种扩展形式及其解法*

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析,然后提出01背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。     

新型增强3GPP认证密钥交换协议

3GPP认证密钥交换协议存在两大安全缺陷：（1）该协议假设在VLR和HLR间的通信信道必须是安全的，因而易遭受攻击者接入信道后的主动攻击；（2）该协议对于移动用户易遭受重定向攻击。该文提出了一种新型增强3GPP认证密钥交换协议，克服了原协议的安全缺陷，确保了在不安全的信道上实现安全的通信，同时很好地防止了对于用户的重定向攻击，并且该新型增强协议的实施无须改动3GPP的安全体系结构。     

TD-LTE系统中秩指示的编码及DSP实现

秩指示RI是3GPP LTE系统中一种重要的MIMO反馈信息.3GPP协议给出了RI的编码方法,是一种简单的线性分组码.采用TI TMS320C6455定点DSP,编程实现协议规定的编码,方法为循环查表法,采用的编程语言为汇编,仿真平台为CCS3.3.该方案算法简单、耗时少,已应用于TD-LTE无线综合测试仪表的开发中...     

基于涡度数据的东北草地光能利用率模型构建与验证

草地作为地球上分布最广的植被类型,在陆地碳循环中发挥着重要作用.草地生产力是估算产草量的基础,准确模拟生产力对草原资源合理利用及生态保护具有重要意义.以东北草地生产力为研究核心,利用涡度相关通量观测数据、遥感数据和气象数据,构建和检验东北草地光能利用率模型.东北草地光能利用率模型以归一化物候植被指数(NDPI)代表光合...     

基于C-W节约算法的TSP教学辅助系统研究与设计

旅行商问题(TSP,Traveling Salesman Problem)属于组合优化领域中一个典型的NP-Hard问题,在许多方面都有着广泛的运用,现已经有诸多的算法被提出以解决这个问题,但是其在教学演示上有较大的难度.为了提高教学质量,本文深入研究一种较为成熟的节约算法,同时设计该算法的教学软件系统,达到了对该问题的分步演示及可视化.改善了教学方法.