面向分类的增量字典学习算法

针对面向分类的传统字典学习方法在大数据集上批量学习时计算代价较高的问题,提出一种类特定的增量式字典学习算法。该算法在初始训练集上进行类特定的字典学习得到初始字典,通过增量数据集选取增量字典原子初始值。根据不能在初始字典上稀疏表示且互信息最大的原则,从增量样本集中选取若干样本作为增量字典原子的初始值。在保持原有字典原子不变的情况下,迭代更新编码系数和增量字典原子,直至收敛得到新的字典。利用稀疏表示分类器,在Eclipse数据集和ORL人脸图像数据库上的实验结果验证了该算法的分类有效性和计算代价上的优越性。     

基于局部平滑性的通用增量流形学习算法

目前大多数流形学习算法无法获取高维输入空间到低维嵌入空间的映射,无法处理新增数据,因此无增量学习能力。而已有的增量流形学习算法大多是通过扩展某一特定的流形学习算法使其具备增量学习能力,不具有通用性。针对这一问题,提出了一种通用的增量流形学习(GIML)算法。该方法充分考虑流形的局部平滑性这一本质特征,利用局部主成分分析法来提取数据集的局部平滑结构,并寻找包含新增样本点的局部平滑结构到对应训练数据的低维嵌入坐标的最佳变换。最后GIML算法利用该变换计算新增样本点的低维嵌入坐标。在人工数据集和实际图像数据集上进行了系统而广泛的比较实验,实验结果表明GIML算法是一种高效通用的增量流形学习方法,且相比当前主要的增量算法,能更精确地获取增量数据的低维嵌入坐标。     

一种RBF网络结构调整的稳健增量学习方法

以实现RBF网络的增量学习能力和提高其增量学习的稳健性为目的,给出了一种RBF网络增量学习算法.算法首先对初始数据集进行聚类得到初始的RBF网络结构,然后采用GAP-RBF算法中的隐层节点调整策略动态调整网络结构实现RBF网络增量学习.RBF网络的初始化降低了初始数据集样本训练顺序对RBF网络性能的影响,增强了其增量学习的稳健性.IRIS数据集和雷达实测数据集仿真实验表明,算法具有较好的增量学习能力.     

一种基于信念修正思想的SVR 增量学习算法

针对实际应用中数据的批量到达,以及系统的存储压力和学习效率低等问题,提出一种基于信念修正思想的SVR增量学习算法。首先从历史样本信息中提取信念集,根据信念集和新增数据的特点选择相应的信念集建立支持向量回归模型并进行预测;然后对信念集进行修正,调整当前认知状态,使该算法对在线和批处理增量学习都有很好的适应性。在标准数据集上的测试验证了算法的良好性能;在某机场噪声实测数据上的对比实验也表明,该算法的性能明显优于传统学习算法和一般增量学习算法。     

基于推拉策略的文本分类增量学习研究

学习算法是否具有增量学习能力是衡量其是否适合于解决现实问题的一个重要方面。增量学习使学习算法的时间和空间资源消耗保持在可以管理和控制的水平,已被广泛应用于解决大规模数据集问题。针对文本分类问题,本文提出了增量学习算法的一般性问题。基于推拉策略的基本思想,本文提出了文本分类的增量学习算法ICCDP,并使用该算法对提出的一般性问题进行了分析。实验表明,该算法训练速度快,分类精度高,具有较高的实用价值。     

自适应的SVM增量算法

支持向量机(support vector machine,SVM)算法因其在小样本训练集上的优势和较好的鲁棒性,被广泛应用于处理分类问题。但是对于增量数据和大规模数据,传统的SVM分类算法不能满足需求,增量学习是解决这些问题的有效方法之一。基于数据分布的结构化描述,提出了一种自适应SVM增量学习算法。该算法根据原样本和新增样本与当前分类超平面之间的几何距离,建立了自适应的增量样本选择模型,该模型能够有效地筛选出参与增量训练的边界样本。为了平衡增量学习的速度和性能,模型分别为新增样本和原模型样本设置了基于空间分布相似性的调整系数。实验结果表明,该算法在加快分类速度的同时提高了模型性能。     

拟单层覆盖粗糙集中近似集的增量更新算法

拟单层覆盖粗糙集与集值信息系统之间存在一一对应的映射关系,当集值信息系统中的对象集动态添加或移除时,对应拟单层覆盖粗糙集中的信息单元也会随之改变,导致拟单层覆盖粗糙集中的近似集发生变化。针对拟单层覆盖粗糙集中近似集的动态更新问题,将拟单层覆盖粗糙集与增量学习相结合,提出近似集的增量更新算法。设计拟单层覆盖集中信息单元的更新算法,以分析信息单元的变化情况,分别构建近似集中可靠单元和争议单元的相关可靠单元集的更新算法。在此基础上,设计与可靠单元和争议单元更新算法相对应的增量更新算法,并且分析其时间复杂度。在UCI数据集上的实验结果表明,与静态算法相比,该算法在对象集发生添加和移除情况下的近似集更新效率分别提高21.5和29倍,能够有效提高近似集的计算效率。     

GPU的并行支持向量机算法(英文)

提出了一种新的并行增量式支持向量机算法来解决图形处理单元(GPU)中大规模数据集的分类问题。SVM以及核相关方法可以用来创建精确分类模型,但学习过程需要大量内存和很长时间。扩展了Suykens和Vandewalle提出的最少次方SVM(LS-SVM)方法来建立增量和并行算法。新算法使用图形处理器以低代价获得高系统性能。实现表明,在UCI和Delve数据集上,基于GPU并行增量算法较CPU实现方法快130倍,而且比现行算法,如LibSVM、SVM-perf和CB-SVM等快的多(超过2500倍)。     

基于核密度估计的集成剪枝和增量学习时间序列预测方法

时间序列预测(TSP)在机器学习中是一个重要问题.论文提出了一种基于核密度估计(KDE)的集成增量学习方法,用于时间序列的预测问题.算法首先根据集成学习的原理产生基学习器池.然后用基学习器池对预测样本的输出值得到核密度估计,并用得到的核密度估计来剪枝基学习器池.得到最终的剪枝集成系统后,用该剪枝集成系统来预测样本的输出.最后,算法根据样本在动态选择集上筛选出的最近邻集合进行增量学习.在数据集IAP,ICS,MCD上的试验结果表明,提出的时间序列预测算法和当前流行的算法相比效果有一定程度的提高.     

基于遗传算法的多旅行商问题研究

针对所有旅行商路径总和最小为优化标准的多旅行商一类问题,用遗传算法优化,并提出了矩阵解码方法。对距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。结果表明,该算法是有效的,适用于距离对称和非对称的多旅行商问题求解。     

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

旅行商问题是一个经典的NP问题,对多人旅行商问题的求解则更具有意义。为了解决所有旅行商路径总和最小为优化标准的多旅行商一类问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题无须设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

基于GA的最小旅行时间的多旅行商问题研究*

以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较,适于距离对称和非对称的多旅行商问题求解。     

基于遗传算法的一类多旅行商问题研究

旅行商问题是一个经典的NP完全问题,对多人旅行商问题的求解则更具有意义。以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对所有旅行商路径最大值最小的多旅行商一类问题研究的相对较少。针对所有旅行商路径最大值最小的多旅行商一类问题,用遗传算法优化,并且提出了矩阵解码方法。该方法适于距离对称和非对称的多旅行商问题求解。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。     

A new and efficient ant-based heuristic method for solving the traveling salesman problem

Abstract: In this paper, we present an efficient metaheuristic approach for solving the problem of the traveling salesman. We introduce the multiple ant clans concept from parallel genetic algorithms to search solution space using different islands to avoid local minima in order to obtain a global minimum for solving the traveling salesman problem. Our simulation results indicate that the proposed novel traveling salesman problem method (called the ACOMAC algorithm) performs better than a promising approach named the ant colony system. This investigation is concerned with a real life logistics system design which optimizes the performance of a logistics system subject to a required service level in the vehicle routing problem. In this work, we also concentrate on developing a vehicle routing model by improving the ant colony system and using the multiple ant clans concept. The simulation results reveal that the proposed method is very effective and potentially useful in solving vehicle routing problems.     

A memetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.     

基于HGA的最小旅行时间多旅行商问题研究

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

The symmetric travelling salesman problem II. New low bounds

The branch-and-bound method is adduced for the symmetric salesman problem where two lower bounds are proposed as bounds. The first bound is a solution to the problem of optimal 2-matching; the second one, to the problem of minimum spanning 1-tree. The last bound is enhanced by applying the problem of optimal 2-matching. Both these bounds considerably improve the symmetric traveling salesman problem as compared to the asymmetric problem.     

A new genetic algorithm for the asymmetric traveling salesman problem

The asymmetric traveling salesman problem (ATSP) is one of the most important combinatorial optimization problems. It allows us to solve, either directly or through a transformation, many real-world problems. We present in this paper a new competitive genetic algorithm to solve this problem. This algorithm has been checked on a set of 153 benchmark instances with known optimal solution and it outperforms the results obtained with previous ATSP heuristic methods.     

一种基于归零矩阵的TSP求解算法

利用传统贪心算法的基本思路针对旅行商问题,提出了一种基于归零矩阵的验证算法.该算法以归零矩阵为输入规避矩阵陷阱,以完全贪心算法为求解思路来获得最短汉密尔顿回路.通过对若干TSP-LIB中问题的求解,结果表明所提算法能够以较快速度求得较好的满意解.