一种新的MPLS流量工程最小干涉算法

优化网络资源利用是Internet流量工程的重要目标之一.MIRA等著名算法通过绕开关键链路而最小化不同源一目的节点对之间的干涉,但是,有些情况下,这些算法可能导致选择过长的路径,或在寻找关键路径时判断不准确,并且关键路径的计算非常复杂,路由建立的时间较长.针对MPLS流量工程路由算法存在的不足,提出了一种新的用于MPLS网络流量工程的路由算法MICA-K,该算法综合考虑了链路带宽平均利用率、冲突度和竞争度三个网络参数,在K最短路径中选择一条最小化资源占用和负载平衡的路径.本算法在提高网络资源利用率的同时,降低了算法的计算复杂度.模拟结果证明算法在网络吞吐量和负载均衡方面达到了更好的性能.     

一种基于相似度的新型粒子群算法

分析了基本粒子群算法（PSO）全局搜索能力与收敛速度的矛盾,提出了粒子群相似度的概念.根据每个粒子与全局最优粒子的不同相似度,对基本PSO算法的惯性权重进行动态调整.同时提出一种根据相似度计算聚集度的方法,并根据聚集度的大小随机地对粒子重新赋值,控制粒子群的多样性,提高了全局搜索能力.典型优化问题的实例仿真验证了该算法的有效性.     

基于改进的FCM算法的入侵检测研究

随着计算机网络的不断发展,网络信息安全成为人们越来越关注的一个方面.入侵检测是提高网络信息安全的一个重要手段.为了提高入侵检测的效率,文中在提出了一种基于隶属关系不确定的模糊聚类算法.该算法在迭代过程中为目标函数创建了一个不确定性隶属度和一个相对性隶属度,使样本中的元素不仅仅局限于一个聚类.通过在数据集上的实验,验证了该算法在数据挖掘入侵检测中的检测率高于一般的K均值算法和模糊聚类算法.证明该方法在模糊事件的情况下,会提高正确的聚类结果.     

FCM-VKNN聚类算法的研究

提出了一种新的K值可以变化的FCM-VKNN(Fuzzy C-Means Variable K-Nearest Neighbor)聚类算法.FCM-VKNN聚类算法充分吸取了FCM算法和KNN准则的长处,使本 算法不受初始值的影响和固定值K的束缚.新的目标准则函数考虑了数据集样本的模糊隶属 关系和样本几何分布两个方面的因素,使算法的鲁棒性和分类的正确性大大加强.最后给出了 几组具有代表性数据的聚类结果.实验结果表明了这种算法的有效性.     

基于模糊集隶属度特征和贴近度的徽标识别

模糊信息理论是一种基于模糊集理论的信息科学,模糊集理论在模式识别中表现出很好的性能,两者相结合形成了模糊模式识别.针对图像智能处理中对徽标识别的应用需求,提出了一种基于模糊集隶属度特征和贴近度的徽标识别算法.该算法通过把徽标网格特征映射转化成模糊集的隶属度特征并根据贴近度进行识别,显著增强了对质量不佳图像的适应性和抗干扰性,有效提高了徽标识别系统的柔性处理能力.实验表明,使用该徽标识别算法的识别率能达到94.5%.     

基于CTID序列模式的一种改进算法

提高序列模式挖掘算法效率的关键在于减少发现频繁序列的时间.文中基于CTID概念提出了一种改进的频繁序列模式挖掘算法--SPM,它充分利用频繁项集和中间挖掘结果,得到更多有效的序列模式,并简化了剪枝步骤,从而提高了算法效率.实验证明该算法可行.     

一种基于关键点的SAX改进算法

SAX(symbolic aggregate approximation)是一种符号化的时间序列相似性度量方法,该方法在对时间序列划分时,采用了PAA算法的均值划分,但均分点无法有效描述序列的形态变化,导致序列间对应分段均值相似的情况下,SAX无法有效区分序列之间的相似度.在SAX算法的基础上,提出了基于关键点的SAX改进算法(KP_SAX),该算法的相似性度量公式既可描述时间序列自身数值变化的统计规律,又可描述时间序列形态变化.实验结果表明:KP_SAX虽然部分提高了算法的复杂度,但可在SAX算法无法计算序列相似度的情况下,有效计算各序列间的相似度距离,达到了改进的目的.     

无监督的差分鉴别特征提取以及在人脸识别上的应用

局部保持投影(LPP)只考虑了投影后的局部性,而忽视了非局部性.针对这个问题,引入非局部散布矩阵,提出无监督的差分鉴别特征提取算法,通过最大化非局部和局部之间的散度差来寻找最优变换矩阵,并将其成功地应用于人脸识别.该算法同时引入非局部和局部的信息,揭示隐含在高维图像空间中的非线性结构;采用差分的形式求解最优变换矩阵,以避免"小样本"问题;对LPP中的邻接矩阵进行了修正,以更准确地描述样本之间的邻近关系.在Yale和AR标准人脸库上的实验结果验证了文中算法的有效性.     

一种基于个体中心论的局部优化社区发现算法

随着社会网络网站的流行,虚拟社会网络中的社区发现成为一个热门研究领域.针对虚拟网络中总是以一个或多个个体为中心特点,提出了一个针对大规模社区网络的局部优化社区发现的算法,在一定程度上弥补了传统算法无法适应大规模网络的不足.实验表明与我们直观想象不同,虚拟网络中那些度最大的点并不一定适合于作为社区中心.     

基于蕴涵度的模糊多层关联规则挖掘改进算法

针对模糊多层关联规则挖掘算法的不足,引入了蕴涵度的方法,实现了基于蕴涵度的模糊多层关联规则挖掘算法.推导出了蕴涵度可以用支持度来表示,这样有效地缩短了程序的执行时间.实验结果证明了采用蕴涵度代替置信度的方法提高了模糊多层关联规则挖掘算法的效率.     

求解圆形Packing问题的一个启发式算法

求解NP难度问题一直是计算机科学技术中的一个瓶颈任务,自20世纪70年代以来的研究表明,求解NP难度问题不存在既完整严格又不大慢的求解算法,因此,近年来,启发式方法成为研究热点,圆形Packing问题是NP难的,具有很高的理论和实践价值,它的求解目标是录求多个圆在一个大圆内的一个优良布局,使得这些圆互不重叠地放置,基于拟物法以及适者生存启发式思想,为圆形Packing问题的快速求解提出了一个高效的启发式算法,算法的高效性通过计算实例得到了验证。     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

一种快速的有约束矩形件优化排样模型

为了有效地解决有约束的矩形件优化排样问题,提出一种快速的求解算法;通过比较待排样矩形件的不同排样模式,选择最优排样方案。算法完全基于解析计算,虽不能寻找理论最优解,但相比于各种启发式算法大大提高了排样速度。实验结果表明,算法能够在较短的计算时间内获得满意的排样效果,是一种效率较高的有约束矩形件排样算法。     

An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation

The best-fit heuristic by Burke et al. (2004) is a simple but effective approach for the 2D Strip Packing (2DSP) problem. In this paper, we propose an improved best-fit heuristic for the 2DSP. Instead of selecting the rectangle with the largest width, we use the fitness number to select the best rectangle fitting into the gap. An efficient implementation pattern with a time complexity of O(n log n) (n is the number of rectangles) is provided for the improved best-fit heuristic. A simple random local search is used to improve the results by trying different sequences. The experiment on the benchmark test sets shows that the final approach is both effective and efficient.     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

New heuristics for one-dimensional bin-packing

Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.Scope and purposePacking items into boxes or bins is a task that occurs frequently in distribution and production. A large variety of different packing problems can be distinguished, depending on the size and shape of the items, as well as on the form and capacity of the bins (H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin, 1992). Similar problems occur in minimising material wastage while cutting pieces into particular smaller ones and in the scheduling of identical processors in order to minimise total completion time. This work addresses the basic packing problem, known as the one-dimensional bin packing problem, where it is required to pack a number of items into the smallest possible number of bins of pre-specified equal capacity. Even though this problem is simple to state, it is NP hard, i.e., it is unlikely that there exists an algorithm that could solve every instance of it in polynomial time. Solution of more general realistic packing problems is probably contingent upon the availability of effective and computationally efficient solution procedures for the basic problem. In this work we present several heuristics capable of doing that. Extensive computational testing attests to the power of these heuristics, as well as to their computational efficiency.     

基于蚁群优化算法求解矩形件排样问题

布局问题来源于生产实际,优秀的布局可以提高原料利用率,降低成本,提高经济效益,对许多行业有重要意义。矩形件优化排样是一类具有NP完全难度的组合优化问题。人工蚁群算法是对蚂蚁群体行为的模拟抽象,该算法具有分布计算、信息正反馈和启发式搜索等特点。本文将蚁群算法和剩余矩形法结合用于解决矩形排样问题,首先用蚁群算法将矩形件排样问题转化为一个排列问题;然后通过剩余矩形排样算法排出每一个排列所对应的排样图;最后用算法对文献[9]中的两个算例进行了验证,表明了其有效性。     

集合覆盖问题的启发函数算法

本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-covering heuristic function),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的.     

求解圆形packing问题的一个快速拟物算法

求解NP难问题一直是计算机科学技术中的一个瓶颈任务。自20世纪70年代以来的研究表明,不存在求解此类问题的完整严格的有效算法。因此用启发式方法求解成为当今研究的一个热点。圆形packing问题是一个有着很高理论和实用价值的NP难问题。该文提出了一些有效的搜索策略,得到了一个求解它的快速有效启发式算法。最后用计算实例验证了此算法的有效性,计算结果表明此算法明显优于已有快速算法。     

求解矩形Packing问题的砌墙式启发式算法

为求解正交矩形Packing问题提出了一个新颖而有效的砌墙式启发式算法.该算法主要基于砌墙式启发式策略,其思想主要来源于砖匠在砌墙过程中所积累的经验:基于基准砖的砌墙规则.对国际上公认的大量的Bench-mark问题例的计算结果表明,该算法的计算速度不仅比著名的现代启发式算法快,而且获得更优的高度.