Wrapper–Filter Feature Selection Algorithm Using a Memetic Framework

This correspondence presents a novel hybrid wrapper and filter feature selection algorithm for a classification problem using a memetic framework. It incorporates a filter ranking method in the traditional genetic algorithm to improve classification performance and accelerate the search in identifying the core feature subsets. Particularly, the method adds or deletes a feature from a candidate feature subset based on the univariate feature ranking information. This empirical study on commonly used data sets from the University of California, Irvine repository and microarray data sets shows that the proposed method outperforms existing methods in terms of classification accuracy, number of selected features, and computational efficiency. Furthermore, we investigate several major issues of memetic algorithm (MA) to identify a good balance between local search and genetic search so as to maximize search quality and efficiency in the hybrid filter and wrapper MA     

Wrapper-filter feature selection algorithm using a memetic framework.

This correspondence presents a novel hybrid wrapper and filter feature selection algorithm for a classification problem using a memetic framework. It incorporates a filter ranking method in the traditional genetic algorithm to improve classification performance and accelerate the search in identifying the core feature subsets. Particularly, the method adds or deletes a feature from a candidate feature subset based on the univariate feature ranking information. This empirical study on commonly used data sets from the University of California, Irvine repository and microarray data sets shows that the proposed method outperforms existing methods in terms of classification accuracy, number of selected features, and computational efficiency. Furthermore, we investigate several major issues of memetic algorithm (MA) to identify a good balance between local search and genetic search so as to maximize search quality and efficiency in the hybrid filter and wrapper MA.     

Coloring large graphs based on independent set extraction

This paper presents an effective approach (EXTRACOL) to coloring large graphs. The proposed approach uses a preprocessing method to extract large independent sets from the graph and a memetic algorithm to color the residual graph. Each preprocessing application identifies, with a dedicated tabu search algorithm, a number of pairwise disjoint independent sets of a given size in order to maximize the vertices removed from the graph. We evaluate EXTRACOL on the 11 largest graphs (with 1000 to 4000 vertices) of the DIMACS challenge benchmarks and show improved results for four very difficult graphs (DSJC1000.9, C2000.5, C2000.9, C4000.5). The behavior of the proposed algorithm is also analyzed.     

Balancing exploration and exploitation in memetic algorithms: A learning automata approach

One of the problems with traditional genetic algorithms (GAs) is premature convergence, which makes them incapable of finding good solutions to the problem. The memetic algorithm (MA) is an extension of the GA. It uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, we introduce a new algorithm based on learning automata (LAs) and an MA, and we refer to it as LA‐MA. This algorithm is composed of 2 parts: a genetic section and a memetic section. Evolution is performed in the genetic section, and local search is performed in the memetic section. The basic idea of LA‐MA is to use LAs during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. For this purpose, we present a criterion for the estimation of success of the local search at each generation. This criterion is used to calculate the probability of applying the local search to each chromosome. We show that in practice, the proposed probabilistic measure can be estimated reliably. On the basis of the relationship between the genetic section and the memetic section, 3 versions of LA‐MA are introduced. LLA‐MA behaves according to the Lamarckian learning model, BLA‐MA behaves according to the Baldwinian learning model, and HLA‐MA behaves according to both the Baldwinian and Lamarckian learning models. To evaluate the efficiency of these algorithms, they have been used to solve the graph isomorphism problem. The results of computer experimentations have shown that all the proposed algorithms outperform the existing algorithms in terms of quality of solution and rate of convergence.     

Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.     

Mapping stream programs onto multicore platforms by local search and genetic algorithm

This paper presents a number of novel metaheuristic approaches that can efficiently map stream graphs on multicores. A stream graph consists of a set of actors performing different functions communicating through edges. Orchestrating stream graphs on multicores can be formulated as an Integer Linear Programming (ILP) problem but ILP solver takes exponential time to provide an optimal solution. We propose metaheuristic algorithms to achieve near optimal solutions within a reasonable amount of time. We employ six different variants of the Hill-Climbing (HC) algorithm employing different tweak operators that produce excellent result extremely quickly. We also propose six different variants of Genetic Algorithm (GA) to examine how effective these variants can be in escaping the local optima. We finally combine HC and GA techniques (which is also known as ‘memetic algorithm’) to produce hybrid techniques that outperform the individual performance of HC and GA techniques. We compare our results with the results generated by the CPLEX optimization tool. Our best technique has achieved a geometric mean speedup of 7.42× across a range of StreamIt benchmarks on an eight-core processor.     

A memetic algorithm for the cyclic antibandwidth maximization problem

The cyclic antibandwidth problem is to embed the vertices of a graph G of n vertices on a cycle C _n such that the minimum distance (measured in the cycle) of adjacent vertices is maximized. Exact results/conjectures for this problem exist in the literature for some standard graphs, such as paths, cycles, two-dimensional meshes, and tori, but no algorithm has been proposed for the general graphs in the literature reviewed by us so far. In this paper, we propose a memetic algorithm for the cyclic antibandwidth problem (MACAB) that can be applied on arbitrary graphs. An important feature of this algorithm is the use of breadth first search generated level structures of a graph to explore a variety of solutions. A novel greedy heuristic is designed which explores these level structures to label the vertices of the graph. The algorithm achieves the exact cyclic antibandwidth of all the standard graphs with known optimal values. Based on our experiments we conjecture the cyclic antibandwidth of three-dimensional meshes, hypercubes, and double stars. Experiments show that results obtained by MACAB are substantially better than those given by genetic algorithm.     

带时间窗车辆路径问题的文化基因算法

针对物流配送中带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）,建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。     

基于正余弦算法的文本特征选择

为获取文本中的较优特征子集,剔除干扰和冗余特征,提出了一种结合过滤式算法和群智能算法的混合特征寻优算法。首先计算每个特征词的信息增益值,选取较优的特征作为预选特征集合,再利用正余弦算法对预选特征进行寻优,获取精选特征集合。为较好地平衡正余弦算法中的全局搜索和局部开发能力,加入了自适应惯性权重;为更精确地评价特征子集,引入以特征数量和准确率进行加权的适应度函数,并提出了新的位置更新机制。在KNN和贝叶斯分类器上的实验结果表明,该特征选择算法与其它特征选择算法及改进前的算法相比,分类准确率得到了一定的提升。     

Probabilistic frequent subtrees for efficient graph classification and retrieval

Frequent subgraphs proved to be powerful features for graph classification and prediction tasks. Their practical use is, however, limited by the computational intractability of pattern enumeration and that of graph embedding into frequent subgraph feature spaces. We propose a simple probabilistic technique that resolves both limitations. In particular, we restrict the pattern language to trees and relax the demand on the completeness of the mining algorithm, as well as on the correctness of the pattern matching operator by replacing transaction and query graphs with small random samples of their spanning trees. In this way we consider only a random subset of frequent subtrees, called probabilistic frequent subtrees, that can be enumerated efficiently. Our extensive empirical evaluation on artificial and benchmark molecular graph datasets shows that probabilistic frequent subtrees can be listed in practically feasible time and that their predictive and retrieval performance is very close even to those of complete sets of frequent subgraphs. We also present different fast techniques for computing the embedding of unseen graphs into (probabilistic frequent) subtree feature spaces. These algorithms utilize the partial order on tree patterns induced by subgraph isomorphism and, as we show empirically, require much less evaluations of subtree isomorphism than the standard brute-force algorithm. We also consider partial embeddings, i.e., when only a part of the feature vector has to be calculated. In particular, we propose a highly effective practical algorithm that significantly reduces the number of pattern matching evaluations required by the classical min-hashing algorithm approximating Jaccard-similarities.     

A novel hybrid algorithm for feature selection

Feature selection is an important filtering method for data analysis, pattern classification, data mining, and so on. Feature selection reduces the number of features by removing irrelevant and redundant data. In this paper, we propose a hybrid filter–wrapper feature subset selection algorithm called the maximum Spearman minimum covariance cuckoo search (MSMCCS). First, based on Spearman and covariance, a filter algorithm is proposed called maximum Spearman minimum covariance (MSMC). Second, three parameters are proposed in MSMC to adjust the weights of the correlation and redundancy, improve the relevance of feature subsets, and reduce the redundancy. Third, in the improved cuckoo search algorithm, a weighted combination strategy is used to select candidate feature subsets, a crossover mutation concept is used to adjust the candidate feature subsets, and finally, the filtered features are selected into optimal feature subsets. Therefore, the MSMCCS combines the efficiency of filters with the greater accuracy of wrappers. Experimental results on eight common data sets from the University of California at Irvine Machine Learning Repository showed that the MSMCCS algorithm had better classification accuracy than the seven wrapper methods, the one filter method, and the two hybrid methods. Furthermore, the proposed algorithm achieved preferable performance on the Wilcoxon signed-rank test and the sensitivity–specificity test.     

基于自适应Memetic算法的多目标复杂网络社区检测

针对提高复杂网络社区检测准确度问题, 提出了一种自适应Memetic算法的多目标社区检测算法。在全局搜索中利用Logistic函数来设置与全局优化相应的交叉概率和变异概率,并将多目标优化问题转化成同时最小优化Kernel K-Means和Ratio Cut这两个目标函数;在局部搜索中利用权重将两个目标函数合并成一个局部优化目标,并采用爬山搜索来寻找个体最优。在虚拟和真实网络实验平台下,与五个基于遗传算法的方法以及Fast Modularity算法相比,结果表明算法能有效提高社区检测准确度,具有更好的寻优效果。     

动态环境中的Memetic算法

针对近几年在进化计算领域被广泛关注的动态优化问题,提出了一种基于粒子群优化(PSO)的Memetic算法.在一种环状拓扑结构的局部PSO模型中,利用模糊认知局域搜索策略来改善部分粒子的质量,同时引入一种自组织随机移民策略来保持算法的种群多样性.通过对一组标准动态测试问题的仿真实验,能够证明所提出的算法在动态环境中的有效性和适应能力.     

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem

This paper presents a new solver for the exactly one-in-a-set Generalized Traveling Salesman Problem (GTSP). In the GTSP, we are given as input a complete directed graph with edge weights, along with a partition of the vertices into disjoint sets. The objective is to find a cycle (or tour) in the graph that visits each set exactly once and has minimum length. In this paper we present an effective algorithm for the GTSP based on adaptive large neighborhood search. The algorithm operates by repeatedly removing from, and inserting vertices in, the tour. We propose a general insertion mechanism that contains as special cases the well-known nearest, farthest and random insertion mechanisms. We provide extensive benchmarking results for our solver in comparison to the state-of-the-art on a wide range of existing and new problem libraries. We show that on the GTSP-LIB library, the proposed algorithm is competitive with the best known algorithms. On several other libraries, we show that given the same amount of time, the proposed solver finds higher quality solutions than existing approaches, particularly on harder instances that are non-metric and/or whose sets are not clustered.     

Enhanced genetic algorithms for a bi‐objective bus driver rostering problem: a computational study

In this work, the bus driver rostering problem is considered in the context of a noncyclic rostering, with two objectives representing either the company or the drivers’ interests. A network model and a proof of the NP‐hardness of the problem are presented, along with a bi‐objective memetic algorithm that combines a specific decoder with a utopian/lexicographic elitism, a strength Pareto fitness evaluation, and a local search procedure. By taking real and benchmark instances the computational behavior of the memetic algorithm is compared with simpler versions to assess the effects of the embedded components. The developed algorithm is a valuable tool for bus companies’ planning departments insofar as it yields at low computing times a pool of good quality rosters that reconcile contradictory objectives. This study shows that simple enhancements in standard bi‐objective genetic algorithms may improve the results for this difficult combinatorial problem.     

Motorcycle graph enumeration from quadrilateral meshes for reverse engineering

Recently proposed quad-meshing techniques allow the generation of high-quality semi-regular quadrilateral meshes. This paper outlines the generation of quadrilateral segments using such meshes. Quadrilateral segments are advantageous in reverse engineering because they do not require surface trimming or surface parameterization. The motorcycle graph algorithm of Eppstein et al. produces the motorcycle graph of a given quadrilateral mesh consisting of quadrilateral segments. These graphs are preferable to base complexes, because the mesh can be represented with a smaller number of segments, as T-joints (where the intersection of two neighboring segments does not involve the whole edge or the vertex) are allowed in quadrilateral segmentation.The proposed approach in this study enumerates all motorcycle graphs of a given quadrilateral mesh and optimum graph for reverse engineering is then selected. Due to the high computational cost of enumerating all these graphs, the mesh is cut into several sub-meshes whose motorcycle graphs are enumerated separately. The optimum graph is then selected based on a cost function that produces low values for graphs whose edges trace a large number of highly curved regions in the model. By applying several successive enumeration steps for each sub-mesh, a motorcycle graph for the given mesh is found. We also outline a method for the extraction of feature curves (sets of highly curved edges) and their integration into the proposed algorithm. Quadrilateral segments generated using the proposed techniques are validated by B-spline surfaces.     

具有自适应趋向性和引导因子的人工蜂群算法

针对人工蜂群算法中存在的收敛速度慢、寻优精度低的问题,提出了一种改进的人工蜂群算法。该算法将自适应趋向性加入雇佣蜂的搜索方案中,同时在观察蜂的搜索方案中加入引导因子。通过雇佣蜂对优秀蜜源的动态趋向搜索以及观察蜂在引导因子引领下的协同搜索,显著提高了算法的局部搜索能力。基于八个标准测试函数的仿真结果表明,与基本人工蜂群算法相比,改进后的算法在寻优精度和收敛速度方面均有明显提升。     

Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.