A rough set approach to feature selection based on ant colony optimization

Rough set theory is one of the effective methods to feature selection, which can preserve the meaning of the features. The essence of rough set approach to feature selection is to find a subset of the original features. Since finding a minimal subset of the features is a NP-hard problem, it is necessary to investigate effective and efficient heuristic algorithms. Ant colony optimization (ACO) has been successfully applied to many difficult combinatorial problems like quadratic assignment, traveling salesman, scheduling, etc. It is particularly attractive for feature selection since there is no heuristic information that can guide search to the optimal minimal subset every time. However, ants can discover the best feature combinations as they traverse the graph. In this paper, we propose a new rough set approach to feature selection based on ACO, which adopts mutual information based feature significance as heuristic information. A novel feature selection algorithm is also given. Jensen and Shen proposed a ACO-based feature selection approach which starts from a random feature. Our approach starts from the feature core, which changes the complete graph to a smaller one. To verify the efficiency of our algorithm, experiments are carried out on some standard UCI datasets. The results demonstrate that our algorithm can provide efficient solution to find a minimal subset of the features.     

Multi-objective feature subset selection using mRMR based enhanced ant colony optimization algorithm (mRMR-EACO)

In this research, we propose a novel method to find the relevant feature subset by using ant colony optimisation minimum-redundancy–maximum-relevance. The proposed approach considers the significance of each feature while reducing the dimensionality. The performance of proposed algorithm has been compared with existing biologically inspired feature subset selection algorithms. Eight datasets have been selected from UCI machine learning repository for experimentation. The experimental results indicate that the presented algorithm out performs the other algorithms in terms of the classification accuracy and feature reduction.     

A link prediction algorithm based on ant colony optimization

The problem of link prediction has attracted considerable recent attention from various domains such as sociology, anthropology, information science, and computer sciences. In this paper, we propose a link prediction algorithm based on ant colony optimization. By exploiting the swarm intelligence, the algorithm employs artificial ants to travel on a logical graph. Pheromone and heuristic information are assigned in the edges of the logical graph. Each ant chooses its path according to the value of the pheromone and heuristic information on the edges. The paths the ants traveled are evaluated, and the pheromone information on each edge is updated according to the quality of the path it located. The pheromone on each edge is used as the final score of the similarity between the nodes. Experimental results on a number of real networks show that the algorithm improves the prediction accuracy while maintaining low time complexity. We also extend the method to solve the link prediction problem in networks with node attributes, and the extended method also can detect the missing or incomplete attributes of data. Our experimental results show that it can obtain higher quality results on the networks with node attributes than other algorithms.     

基于选路优化的改进蚁群算法

蚁群算法在处理大规模优化问题时效率很低。为此对蚁群算法提出了基于选路优化的两点改进:(1)引入选路优化策略,减少了算法中蚁群的选路次数,显著提高了算法的执行效率。(2)在选路操作中,只根据当前城市的前C个距离最近的且未经过城市为候选城市计算选择概率,从而减少单个蚂蚁选路的计算量。尤其对于以往较难处理的大规模TSP问题,改进算法在执行效率上有明显的优势。模拟实验结果表明改进算法较之基本蚁群算法在收敛速度有明显提高。     

基于蚁群优化算法的立体匹配

立体匹配技术使得通过像点获取景物的距离信息,实现三维立体再现成为可能,是计算机视觉研究中最基本的关键问题之一.本文选择图像的边缘点作为匹配基元.以边缘特征点处的灰度值、梯度的大小和方向、拉普拉斯值作为其属性值,依据立体匹配的约束条件,建立能量函数.在进行图像的立体匹配的过程中,运用蚁群优化算法找寻使能量函数达到最小的路径,从而实现立体匹配.实验证明,该方法具有较强的稳定性,能得到较高精度的匹配结果.     

A feature cluster taxonomy based feature selection technique

Feature subset selection is basically an optimization problem for choosing the most important features from various alternatives in order to facilitate classification or mining problems. Though lots of algorithms have been developed so far, none is considered to be the best for all situations and researchers are still trying to come up with better solutions. In this work, a flexible and user-guided feature subset selection algorithm, named as FCTFS (Feature Cluster Taxonomy based Feature Selection) has been proposed for selecting suitable feature subset from a large feature set. The proposed algorithm falls under the genre of clustering based feature selection techniques in which features are initially clustered according to their intrinsic characteristics following the filter approach. In the second step the most suitable feature is selected from each cluster to form the final subset following a wrapper approach. The two stage hybrid process lowers the computational cost of subset selection, especially for large feature data sets. One of the main novelty of the proposed approach lies in the process of determining optimal number of feature clusters. Unlike currently available methods, which mostly employ a trial and error approach, the proposed method characterises and quantifies the feature clusters according to the quality of the features inside the clusters and defines a taxonomy of the feature clusters. The selection of individual features from a feature cluster can be done judiciously considering both the relevancy and redundancy according to user’s intention and requirement. The algorithm has been verified by simulation experiments with different bench mark data set containing features ranging from 10 to more than 800 and compared with other currently used feature selection algorithms. The simulation results prove the superiority of our proposal in terms of model performance, flexibility of use in practical problems and extendibility to large feature sets. Though the current proposal is verified in the domain of unsupervised classification, it can be easily used in case of supervised classification.     

基于蚂蚁优化算法的分层强化学习

自主系统中,agent通过与环境交互来执行分配给他们的任务,采用分层强化学习技术有助于agent在大型、复杂的环境中提高学习效率。提出一种新方法,利用蚂蚁系统优化算法来识别分层边界发现子目标状态,蚂蚁遍历过程中留下信息素,利用信息素的变化率定义了粗糙度,用粗糙度界定子目标;agent使用发现的子目标创建抽象,能够更有效地探索。在出租车环境下验证算法的性能,实验结果表明该方法可以显著提高agent的学习效率。     

Improved ant colony optimization algorithm based on RNA computing

RNA computing is a new intelligent optimization algorithm, which combines computer science and molecular biology. Aiming at the weakness of slow convergence rate and poor global search ability in the basic ant colony optimization algorithm due to the unreasonable selection of parameters, this paper utilizes the combination of RNA computing and basic ant colony optimization algorithm to overcome the defects. An improved ant colony optimization algorithm based on RNA computing is proposed. In the iterative process of ant colony optimization algorithm, transformation operation, recombination operation and permutation operation in RNA computing are introduced to optimize the initial parameters including importance factor of pheromone trail α, importance factor of heuristic function β and pheromone evaporation rate ρ to improve the convergence efficiency and global search ability. The performance of the algorithm is evaluated on five instances of the library of traveling salesman problems (TSPLIB) and six typical test functions. The experimental results demonstrate that the proposed RNA-ant colony optimization algorithm is superior than basic ant colony optimization algorithm in optimization ability, reliability, convergence efficiency, stability and robustness.     

Multi-satellite control resource scheduling based on ant colony optimization

The multi-satellite control resource scheduling problem (MSCRSP) is a kind of large-scale combinatorial optimization problem. As the solution space of the problem is sparse, the optimization process is very complicated. Ant colony optimization as one of heuristic method is wildly used by other researchers to solve many practical problems. An algorithm of multi-satellite control resource scheduling problem based on ant colony optimization (MSCRSP–ACO) is presented in this paper. The main idea of MSCRSP–ACO is that pheromone trail update by two stages to avoid algorithm trapping into local optima. The main procedures of this algorithm contain three processes. Firstly, the data get by satellite control center should be preprocessed according to visible arcs. Secondly, aiming to minimize the working burden as optimization objective, the optimization model of MSCRSP, called complex independent set model (CISM), is developed based on visible arcs and working periods. Ant colony algorithm can be used directly to solve CISM. Lastly, a novel ant colony algorithm, called MSCRSP–ACO, is applied to CISM. From the definition of pheromone and heuristic information to the updating strategy of pheromone is described detailed. The effect of parameters on the algorithm performance is also studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the MSCRSP–ACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and max–min ant system.     

Hardware-oriented ant colony optimization

A new kind of ant colony optimization (ACO) algorithm is proposed that is suitable for an implementation in hardware. The new algorithm – called Counter-based ACO – allows to systolically pipe artificial ants through a grid of processing cells. Various features of this algorithm have been designed so that it can be mapped easily to field-programmable gate arrays (FPGAs). Examples are a new encoding of pheromone information and a new method to define the decision sequence of ants. Experimental results that are based on simulations for the traveling salesperson problem and the quadratic assignment problem are presented to evaluate the proposed techniques.     

一种基于GPU加速的细粒度并行蚁群算法

为改善蚁群算法对大规模旅行商问题的求解性能,提出一种基于图形处理器(GPU)加速的细粒度并行蚁群算法.将并行蚁群算法求解过程转化为统一计算设备架构的线程块并行执行过程,使得蚁群算法在GPU中加速执行.实验结果表明,该算法能提高全局搜索能力,增大细粒度并行蚁群算法的蚂蚁规模,从而提高了算法的运算速度.     

基于群集智能的蚁群优化算法研究

群集智能是近年来人工智能领域研究的一个新的热点课题。介绍了这一研究的思想方法和数学模型,以蚂蚁群体的智能行为研究对象,阐述了基于群集智能的蚁群优化算法,并介绍了该算法的工程应用。     

一种基于蚁群算法的呼叫中心人力需求计算方法

针对呼叫中心人力需求优化这一离散约束问题,基于Dantzig提出的集合覆盖模型,建立了单技能呼叫中心的人力需求计算线性规划模型,并提出一种基于改进蚁群算法的求解方法.在该方法中,对算法的信息素更新规则进行了修改,并基于MATLAB编程针对实例进行仿真分析.选取统计学指标将算法的仿真结果与遗传算法进行对比,结果表明:基于蚁群算法的方法计算复杂度可行;能够节约人力,且话务员匹配度可满足实际运营需求;为智能算法在呼叫中心人力需求计算问题上的应用研究提供了一种新的解决思路.     

基于资源状态蚁群算法的云计算任务分配

针对云计算中的任务分配问题,分析任务资源之间的数学模型,提出一种基于资源状态蚁群算法,相对一般蚁群算法,加入虚拟机实时状态,更精确地表达云计算任务分配的问题.通过CloudSim工具设计仿真实验,实验结果表明,与最近Cristian Mateos提出的蚁群改进算法相比,该算法在任务完成时间、算法稳定收敛方面取得了较好表现,以RR算法为基准,该算法提高后的时间比例稳定在RR算法任务完成时间的60％～65％,稳定性提高4.7倍.     

A multi-objective feature selection method based on bacterial foraging optimization

Feature selection plays an important role in data preprocessing. The aim of feature selection is to recognize and remove redundant or irrelevant features. The key issue is to use as few features as possible to achieve the lowest classification error rate. This paper formulates feature selection as a multi-objective problem. In order to address feature selection problem, this paper uses the multi-objective bacterial foraging optimization algorithm to select the feature subsets and k-nearest neighbor algorithm as the evaluation algorithm. The wheel roulette mechanism is further introduced to remove duplicated features. Four information exchange mechanisms are integrated into the bacteria-inspired algorithm to avoid the individuals getting trapped into the local optima so as to achieve better results in solving high-dimensional feature selection problem. On six small datasets and ten high-dimensional datasets, comparative experiments with different conventional wrapper methods and several evolutionary algorithms demonstrate the superiority of the proposed bacteria-inspired based feature selection method.

     

基于蚁群优化算法的瓦斯预测模型研究

针对瓦斯煤尘爆炸和煤与瓦斯突出给煤炭矿山企业带来的危害极大的问题,将蚁群优化算法和BP神经网络技术结合应用到瓦斯涌出量预测,建立比较准确的预测模型。重点研究了BP网络模型的选择与优化训练,通过蚁群算法优化解决了BP神经网络易陷入局部收敛的问题。仿真与实际数据验证表明：改进的神经网络算法对瓦斯涌出量预测能达到良好的效果。     

基于粗糙集的蚁群算法不确定性分析

蚁群算法中的信息素更新对整个算法的性能起到决定性的作用.在时蚁群算法进行系统仿真实验过程中,发现存在多种不确定因素影响信息素的更新.粗糙集是一种处理不确定和模糊知识的工具,本文利用粗糙集对试验结果进行了分析,给出了不确定因素之间的关系,并根据分析结果对信息素更新策略作了相应的改进,提高了算法的性能.