基于差别矩阵的蚁群系统约简方法

针对粗糙集属性约简的结果容易出现局部最优问题,本文引入差别矩阵,将相对和绝对属性约简统一为差别列表上的集合操作,提出基于蚁群系统的启发式数据约简算法,将蚁群算法的启发信息建立在差别矩阵的核度和必要度上。实验仿真表明此算法可以较好的克服普通约简算法的局部最优问题,说明此算法具有较好约简性能。     

A novel multiple rule sets data classification algorithm based on ant colony algorithm

Ant colony optimization (ACO) algorithms have been successfully applied in data classification, which aim at discovering a list of classification rules. However, due to the essentially random search in ACO algorithms, the lists of classification rules constructed by ACO-based classification algorithms are not fixed and may be distinctly different even using the same training set. Those differences are generally ignored and some beneficial information cannot be dug from the different data sets, which may lower the predictive accuracy. To overcome this shortcoming, this paper proposes a novel classification rule discovery algorithm based on ACO, named AntMiner_mbc, in which a new model of multiple rule sets is presented to produce multiple lists of rules. Multiple base classifiers are built in AntMiner_mbc, and each base classifier is expected to remedy the weakness of other base classifiers, which can improve the predictive accuracy by exploiting the useful information from various base classifiers. A new heuristic function for ACO is also designed in our algorithm, which considers both of the correlation and coverage for the purpose to avoid deceptive high accuracy. The performance of our algorithm is studied experimentally on 19 publicly available data sets and further compared to several state-of-the-art classification approaches. The experimental results show that the predictive accuracy obtained by our algorithm is statistically higher than that of the compared targets.     

TACO-miner: An ant colony based algorithm for rule extraction from trained neural networks

Extracting classification rules from data is an important task of data mining and gaining considerable more attention in recent years. In this paper, a new meta-heuristic algorithm which is called as TACO-miner is proposed for rule extraction from artificial neural networks (ANN). The proposed rule extraction algorithm actually works on the trained ANNs in order to discover the hidden knowledge which is available in the form of connection weights within ANN structure. The proposed algorithm is mainly based on a meta-heuristic which is known as touring ant colony optimization (TACO) and consists of two-step hierarchical structure. The proposed algorithm is experimentally evaluated on six binary and n-ary classification benchmark data sets. Results of the comparative study show that TACO-miner is able to discover accurate and concise classification rules.     

Mining network data for intrusion detection through combining SVMs with ant colony networks

In this paper, we introduce a new machine-learning-based data classification algorithm that is applied to network intrusion detection. The basic task is to classify network activities (in the network log as connection records) as normal or abnormal while minimizing misclassification. Although different classification models have been developed for network intrusion detection, each of them has its strengths and weaknesses, including the most commonly applied Support Vector Machine (SVM) method and the Clustering based on Self-Organized Ant Colony Network (CSOACN). Our new approach combines the SVM method with CSOACNs to take the advantages of both while avoiding their weaknesses. Our algorithm is implemented and evaluated using a standard benchmark KDD99 data set. Experiments show that CSVAC (Combining Support Vectors with Ant Colony) outperforms SVM alone or CSOACN alone in terms of both classification rate and run-time efficiency.     

Inducing decision trees with an ant colony optimization algorithm

Decision trees have been widely used in data mining and machine learning as a comprehensible knowledge representation. While ant colony optimization (ACO) algorithms have been successfully applied to extract classification rules, decision tree induction with ACO algorithms remains an almost unexplored research area. In this paper we propose a novel ACO algorithm to induce decision trees, combining commonly used strategies from both traditional decision tree induction algorithms and ACO. The proposed algorithm is compared against three decision tree induction algorithms, namely C4.5, CART and cACDT, in 22 publicly available data sets. The results show that the predictive accuracy of the proposed algorithm is statistically significantly higher than the accuracy of both C4.5 and CART, which are well-known conventional algorithms for decision tree induction, and the accuracy of the ACO-based cACDT decision tree algorithm.     

Generating prediction rules for liquefaction through data mining

Prediction of liquefaction is an important subject in geotechnical engineering. Prediction of liquefaction is also a complex problem as it depends on many different physical factors, and the relations between these factors are highly non-linear and complex. Several approaches have been proposed in the literature for modeling and prediction of liquefaction. Most of these approaches are based on classical statistical approaches and neural networks. In this paper a new approach which is based on classification data mining is proposed first time in the literature for liquefaction prediction. The proposed approach is based on extracting accurate classification rules from neural networks via ant colony optimization. The extracted classification rules are in the form of IF–THEN rules which can be easily understood by human. The proposed algorithm is also compared with several other data mining algorithms. It is shown that the proposed algorithm is very effective and accurate in prediction of liquefaction.     

Data aggregation in wireless sensor networks using ant colony algorithm

Data aggregation is important in energy constraint wireless sensor networks which exploits correlated sensing data and aggregates at the intermediate nodes to reduce the number of messages exchanged network. This paper considers the problem of constructing data aggregation tree in a wireless sensor network for a group of source nodes to send sensory data to a single sink node. The ant colony system provides a natural and intrinsic way of exploring search space in determining data aggregation. Moreover, we propose an ant colony algorithm for data aggregation in wireless sensor networks. Every ant will explore all possible paths from the source node to the sink node. The data aggregation tree is constructed by the accumulated pheromone. Simulations have shown that our algorithm can reduce significant energy costs.     

挖掘最大频繁项集的改进蚁群算法

最大频繁项集挖掘用于发现频繁地出现在数据集中的最大子集,目前已经有许多有效的算法。应用蚁群算法挖掘最大频繁项集是一种新的方法,但是该算法往往迭代次数多,提取率低。结合频繁项集关联图和最大最小蚂蚁系统,提出一种新的蚁群算法。算法构造蚁群路径图,蚁群在动态的信息素和启发式因子指导下构造局部最大频繁项集,通过新的局部更新和全局更新机制发现全局最大频繁项集。对比实验表明,算法挖掘速度快,提取率高。     

A robust ant colony optimization-based algorithm for community mining in large scale oriented social graphs

Community detection plays a key role in such important fields as biology, sociology and computer science. For example, detecting the communities in protein–protein interactions networks helps in understanding their functionalities. Most existing approaches were devoted to community mining in undirected social networks (either weighted or not). In fact, despite their ubiquity, few proposals were interested in community detection in oriented social networks. For example, in a friendship network, the influence between individuals could be asymmetric; in a networked environment, the flow of information could be unidirectional. In this paper, we propose an algorithm, called ACODIG, for community detection in oriented social networks. ACODIG uses an objective function based on measures of density and purity and incorporates the information about edge orientations in the social graph. ACODIG uses ant colony for its optimization. Simulation results on real-world as well as power law artificial benchmark networks reveal a good robustness of ACODIG and an efficiency in computing the real structure of the network.     

Developing a diagnostic system through integration of fuzzy case-based reasoning and fuzzy ant colony system

This study intends to propose a hybrid Case-Based Reasoning (CBR) system with the integration of fuzzy sets theory and Ant System-based Clustering Algorithm (ASCA) in order to enhance the accuracy and speed in case matching. The cases in the case base are fuzzified in advance, and then grouped into several clusters by their own similarity with fuzzified ASCA. When a new case occurs, the system will find the closest group for the new case. Then the new case is matched using the fuzzy matching technique only by cases in the closest group. Through these two steps, if the number of cases is very large for the case base, the searching time will be dramatically saved. In the practical application, there is a diagnostic system for vehicle maintaining and repairing, and the results show a dramatic increase in searching efficiency.     

Application of ant colony, genetic algorithm and data mining-based techniques for scheduling

In this paper, we have proposed a novel use of data mining algorithms for the extraction of knowledge from a large set of flow shop schedules. The purposes of this work is to apply data mining methodologies to explore the patterns in data generated by an ant colony algorithm performing a scheduling operation and to develop a rule set scheduler which approximates the ant colony algorithm's scheduler. Ant colony optimization (ACO) is a paradigm for designing metaheuristic algorithms for combinatorial optimization problems. The natural metaphor on which ant algorithms are based is that of ant colonies. Fascinated by the ability of the almost blind ants to establish the shortest route from their nests to the food source and back, researchers found out that these ants secrete a substance called ‘pheromone’ and use its trails as a medium for communicating information among each other. The ant algorithm is simple to implement and results of the case studies show its ability to provide speedy and accurate solutions. Further, we employed the genetic algorithm operators such as crossover and mutation to generate the new regions of solution. The data mining tool we have used is Decision Tree, which is produced by the See5 software after the instances are classified. The data mining is for mining the knowledge of job scheduling about the objective of minimization of makespan in a flow shop environment. Data mining systems typically uses conditional relationships represented by IF-THEN rules and allowing the production managers to easily take the decisions regarding the flow shop scheduling based on various objective functions and the constraints.     

Using a style-based ant colony system for adaptive learning

Adaptive learning provides an alternative to the traditional “one size fits all” approach and has driven the development of teaching and learning towards a dynamic learning process for learning. Therefore, exploring the adaptive paths to suit learners personalized needs is an interesting issue. This paper proposes an extended approach of ant colony optimization, which is based on a recent metaheuristic method for discovering group patterns that is designed to help learners advance their on-line learning along an adaptive learning path. The investigation emphasizes the relationship of learning content to the learning style of each participant in adaptive learning. An adaptive learning rule was developed to identify how learners of different learning styles may associate those contents which have the higher probability of being useful to form an optimal learning path. A style-based ant colony system is implemented and its algorithm parameters are optimized to conform to the actual pedagogical process. A survey was also conducted to evaluate the validity and efficiency of the system in producing adaptive paths to different learners. The results reveal that both the learners and the lecturers agree that the style-based ant colony system is able to provide useful supplementary learning paths.     

An ACS-based framework for fuzzy data mining

Data mining is often used to find out interesting and meaningful patterns from huge databases. It may generate different kinds of knowledge such as classification rules, clusters, association rules, and among others. A lot of researches have been proposed about data mining and most of them focused on mining from binary-valued data. Fuzzy data mining was thus proposed to discover fuzzy knowledge from linguistic or quantitative data. Recently, ant colony systems (ACS) have been successfully applied to optimization problems. However, few works have been done on applying ACS to fuzzy data mining. This thesis thus attempts to propose an ACS-based framework for fuzzy data mining. In the framework, the membership functions are first encoded into binary-bits and then fed into the ACS to search for the optimal set of membership functions. The problem is then transformed into a multi-stage graph, with each route representing a possible set of membership functions. When the termination condition is reached, the best membership function set (with the highest fitness value) can then be used to mine fuzzy association rules from a database. At last, experiments are made to make a comparison with other approaches and show the performance of the proposed framework.     

A hybrid ant colony optimization algorithm for optimal multiuser detection in DS-UWB system

A hybrid ant colony optimization algorithm is proposed by introducing extremal optimization local-search algorithm to the ant colony optimization (ACO) algorithm, and is applied to multiuser detection in direct sequence ultra wideband (DS-UWB) communication system in this paper. ACO algorithms have already successfully been applied to combinatorial optimization; however, as the pheromone accumulates, we may not get a global optimum because it can get stuck in a local minimum resulting in a bad steady state. Extremal optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of optimization problems. Hence in this paper, a hybrid ACO algorithm, named ACO-EO algorithm, is proposed by introducing EO to ACO to improve the local-search ability of the algorithm. The ACO-EO algorithm is applied to multiuser detection in DS-UWB communication system, and via computer simulations it is shown that the proposed hybrid ACO algorithm has much better performance than other ACO algorithms and even equal to the optimal multiuser detector.     

Modeling and implementation of classification rule discovery by ant colony optimisation for spatial land-use suitability assessment

This paper presents an integrated modeling method for multi-criteria land-use suitability assessment (LSA) using classification rule discovery (CRD) by ant colony optimisation (ACO) in ArcGIS. This new attempt applies artificial intelligent algorithms to intelligentise LSA by discovering suitability classification rules. The methodology is implemented as a tool called ACO-LSA. The tool can generate rules which are straightforward and comprehensible for users with high classification accuracy and simple rule list in solving CRD problems. A case study in the Macintyre Brook Catchment of southern Queensland in Australia is proposed to demonstrate the feasibility of this new modeling technique. The results have addressed the major advantages of this novel approach.     

A new ant colony optimization algorithm for the multidimensional Knapsack problem

The paper proposes a new ant colony optimization (ACO) approach, called binary ant system (BAS), to multidimensional Knapsack problem (MKP). Different from other ACO-based algorithms applied to MKP, BAS uses a pheromone laying method specially designed for the binary solution structure, and allows the generation of infeasible solutions in the solution construction procedure. A problem specific repair operator is incorporated to repair the infeasible solutions generated in every iteration. Pheromone update rule is designed in such a way that pheromone on the paths can be directly regarded as selecting probability. To avoid premature convergence, the pheromone re-initialization and different pheromone intensification strategy depending on the convergence status of the algorithm are incorporated. Experimental results show the advantages of BAS over other ACO-based approaches for the benchmark problems selected from OR library.     

基于改进蚁群算法的乒乓球数据挖掘研究

在Ant-Miner算法框架中通过对信息素更新和路径选择概率等策略的改进,并结合乒乓球技战术分析的特点,建立了基于改进蚁群算法的乒乓球技战术分类挖掘模型,并进行了实例分析,与乒乓球技战术关联规则挖掘相比较,该算法在挖掘效果和规则质量方面有很大的优势,并已应用于国家乒乓球队比赛和训练中,效果良好。     

Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system

Due to its typical features, such as large-scale, multiple re-entrant flows, and hybrid machine types, the semiconductor wafer fabrication system (SWFS) is extremely difficult to schedule. In order to cope with this difficulty, the decomposition-based classified ant colony optimization (D-CACO) method is proposed and analyzed in this paper. The D-CACO method comprises decomposition procedure and classified ant colony optimization algorithm. In the decomposition procedure, a large and complicate scheduling problem is decomposed into several subproblems and these subproblems are scheduled in sequence. The classified ACO algorithm then groups all of the operations of the subproblems and schedules them according to machine type. To test the effect of the method, a set of simulations are conducted on a virtual fab simulation platform. The test results show that the proposed D-CACO algorithm works efficiently in scheduling SWFS.     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

蚁群决策算法在上下游短时交通流预测中的应用

根据上下游短时交通流的特性,在深入研究蚁群算法的基础上,利用蚁群思想及决策树思想构造了蚁群决策算法,描述了该算法用于城市道路上下游短时交通流建模预测以及与决策树算法进行了对比,论证了其可行性,最后利用Matlab进行仿真,给出了仿真结果。