Ant colony optimisation (ACO) has demonstrated good performance on a number of combinatorial optimisation tasks. A recent advance demonstrated the successful addition of a grouping heuristic used information from the objective function to prioritise solutions with full bins. This method increased performance further and established grouping-ACO among the state-of-the-art approaches to bin packing. In this paper, we develop a method to learn and apply decision variable groupings during the ACO algorithm run with no additional information from the objective function. This enables the approach to be generalised to any combinatorial problems for which an ACO representation can be formulated. Experimentation is conducted on a number of instances of the bin packing, knapsack and travelling salesman problems and shows improved performance over standard ACO in all cases, and performance approaching grouping-ACO on the bin packing problem.

In this paper, we present an ensemble hybrid pheromone Ant-Miner based algorithm, eAnt-MinerPB+HMA, which benefits from a new hybrid pheromone model to improve the computational and execution time of the algorithm, along with ensemble methods to boost predictive performance. Ant Colony Optimization (ACO) based rule induction algorithms have proven to be successful in producing classification rules. Ensemble methods have also been shown to boost the predictive performance of individual learners, leading to better models. eAnt-MinerPB+HMA creates multiple colonies to build a set of classifiers through feature and instance bagging. eAnt-MinerPB+HMA shows competitive accuracy compared to traditional Ant-Miner variants, while also improving its execution speed—more noticeably in larger data sets.

Ensemble methods are among the best performing in the machine learning literature, often outperforming single methods in training accuracy and the prevention of overfitting. This work builds on the previously successful phased genetic programming (GP) approach to build ensembles of GP trees to create ensemble phased GP (EPGP). The method is tested in a real-world transportation modelling problem, the roundabout (traffic circle, rotary) turn restriction problem using data from OpenStreetMap, an important and time-consuming element of the traffic modelling process. EPGP is compared with standard and phased GP formulations and representative algorithms from the machine learning literature and is found to outperform them on this task.

Provenance is a standardised record that describes how entities, activities, and agents have influenced a piece of data; it is commonly represented as graphs with relevant labels on both their nodes and edges. With the growing adoption of provenance in a wide range of application domains, users are increasingly confronted with an abundance of graph data, which may prove challenging to process. Graph kernels, on the other hand, have been successfully used to efficiently analyse graphs. In this paper, we introduce a novel graph kernel calledprovenance kernel, which is inspired by and tailored for provenance data. We employ provenance kernels to classify provenance graphs from three application domains. Our evaluation shows that they perform well in terms of classification accuracy and yield competitive results when compared against existing graph kernel methods and the provenance network analytics method while more efficient in computing time. Moreover, the provenance types used by provenance kernels are a symbolic representation of a tree pattern which can, in turn, be described using the domain-agnostic vocabulary of provenance. Therefore, provenance types thus allow for the creation of explanations of predictive models built on them.

The bin packing problem (BPP) is a well-researched and important NP-hard problem with many contemporary applications (e.g. stock cutting, machine scheduling), which requires a set of items with variable sizes to be packed into a set of fixed-capacity containers. Many metaheuristic approaches have been successfully trialled on this problem, including evolutionary algorithms, ant colony optimization and local search techniques. The most successful variants of these approaches use grouping techniques whereby the algorithm considers sets of items together rather than as separate decision variables. This paper presents an Ant Colony Optimization integrated with a grouping technique and a novel differential pheromone procedure for bin packing. The proposed differential pheromone grouping ACO shows state-of-the-art results for ACO approaches in BPP and approaches the performance of the best evolutionary methods.

Data stream mining has recently emerged in response to the rapidly increasing continuous data generation. While the majority of Ant Colony Optimisation (ACO) rule induction algorithms have proved to be successful in producing both accurate and comprehensive classification models in nonstreaming (batch) settings, currently ACO-based algorithms for classification problems are not suited to be applied to data stream mining. One of the main challenges is the iterative nature of ACO algorithms, where many procedures—for example, heuristic calculation, selection of continuous attributes, pruning—require multiple passes through the data to create a model. In this paper, we present a new ACO-based algorithm for data stream classification. The proposed algorithm, called Stream Ant-Miner (sAnt-Miner), uses a novel hybrid pheromone model combining both a traditional construction graph and solution archives models to efficiently handle a large number of mixed-type (nominal and continuous) attributes directly without the need for additional procedures, reducing the computational time required to complete an iteration of the algorithm. Our results show that sAnt-Miner produces statistically significant concise models compared with state-of-the-art rule induction data stream algorithms, without negative effects on their predictive accuracy.

In this paper we introduce a new algorithm, called Ant-Miner-RegMAto tackle the regression problem using an archive-based pheromone model. Existing regression algorithms handle continuous attribute using a discretisation procedure, either in a preprocessing stage or during rule creation. Using an archive as a pheromone model, inspired by the ACO for Mixed-Variable (ACOMV), we eliminate the need for a discretisation procedure. We compare the proposed Ant-Miner-RegMAagainst Ant-Miner-Reg, an ACO-based regression algorithm that uses a dynamic discretisation procedure, inspired on M5 algorithm, during rule construction process. Our results show that Ant-Miner-RegMAachieved a significant improvement in the relative root mean square error of the models created, overcoming the limitations of the dynamic discretisation procedure.

Ant-Miner Mixed Attributes (Ant-MinerMA) was inspired and built based on ACOMV. which uses an archive-based pheromone model to cope with mixed attribute types. On the one hand, the use of an archive-based pheromone model improved significantly the runtime of Ant-MinerMA and helped to eliminate the need for discretisation procedure when dealing with continuous attributes. On the other hand, the graph-based pheromone model showed superiority when dealing with datasets containing a large size of attributes, as the graph helps the algorithm to easily identify good attributes. In this paper, we propose an automatic design framework to incorporate the graph-based model along with the archive-based model in the rule creation process. We compared the automatically designed hybrid algorithm against existing ACO-based algorithms: one using a graph-based pheromone model and one using an archive-based pheromone model. Our results show that the hybrid algorithm improves the predictive quality over both the base archive-based and graph-based algorithms.

Instance-based learning (IBL) methods predict the class label of a new instance based directly on the distance between the new unlabeled instance and each labeled instance in the training set, without constructing a classification model in the training phase. In this paper, we introduce a novel cla ss-based feature weighting technique, in the context of instance-based distance methods, using the Ant Colony Optimization meta-heuristic. We address three different approaches of instance-based classification: k-Nearest Neighbours, distance-based Nearest Neighbours, and Gaussian Kernel Estimator. We present a multi-archive adaptation of the ACOℝ algorithm and apply it to the optimization of the key parameter in each IBL algorithm and of the class-based feature weights. We also propose an ensemble of classifiers approach that makes use of the archived populations of the ACOℝ algorithm. We empirically evaluate the performance of our proposed algorithms on 36 benchmark datasets, and compare them with conventional instance-based classification algorithms, using various parameter settings, as well as with a state-of-the-art coevolutionary algorithm for instance selection and feature weighting for Nearest Neighbours classifiers.

In this paper, we introduce Ant-MinerMA to tackle mixed-attribute classification problems. Most classification problems involve continuous, ordinal and categorical attributes. The majority of Ant Colony Optimization (ACO) classification algorithms have the limitation of being able to handle categorical attributes only, with few exceptions that use a discretisation procedure when handling continuous attributes either in a preprocessing stage or during the rule creation. Using a solution archive as a pheromone model, inspired by the ACO for mixed-variable optimization (ACO-MV), we eliminate the need for a discretisation procedure and attributes can be treated directly as continuous, ordinal, or categorical. We compared the proposed Ant-MinerMA against cAnt-Miner, an ACO-based classification algorithm that uses a discretisation procedure in the rule construction process. Our results show that Ant-MinerMA achieved significant improvements on computational time due to the elimination of the discretisation procedure without affecting the predictive performance.

Previous work introduced an approach called TBHPSO, which combines Hierarchical Particle Swarm Optimization (HPSO) with Tabu Local Search and a heuristic bias term, to the Quadratic Assignment Problem (QAP). Specifically, in TBHPSO, a Robust Tabu Local Search is applied to the top particle in the hierarchy in each PSO iteration; in addition, a heuristic “goodness” function, similar to that used in Ant Colony Optimization, is used to bias the PSO velocity update equation. In previous work, TBHPSO was found to perform significantly better than Diversified-Restart Robust Tabu Search (DivTS), a state-of-the-art technique for the QAP. In this paper, we introduce three variations to TBHPSO. The first variation (RTBHPSO) aims to increase search diversity by applying Tabu Local Search to a randomly chosen particle rather than always applying it to the root of the HPSO hierarchy. The second variation (DTBHPSO) applies DivTS (instead of RTS) to the top particle in the hierarchy, while the third variation first selects a random particle and then probabilistically selects either DivTS or RTS to apply to it. The performance of our proposed variations is compared against the original TBHPSO, keeping the CPU time fixed for both methods in each comparison, using 31 problem instances from the QAPLib instance library.