Multi-class pattern classification using single, multi-dimensional feature-space feature extraction evolved by multi-objective genetic programming and its application to network intrusion detection

In this paper we investigate using multi-objective genetic programming to evolve a feature extraction stage for multiple-class classifiers. We find mappings which transform the input space into a new, multi-dimensional decision space to increase the discrimination between all classes; the number of dimensions of this decision space is optimized as part of the evolutionary process. A simple and fast multi-class classifier is then implemented in this multi-dimensional decision space. Mapping to a single decision space has significant computational advantages compared to k-class-to-2-class decompositions; a key design requirement in this work has been the ability to incorporate changing priors and/or costs associated with mislabeling without retraining. We have employed multi-objective optimization in a Pareto framework incorporating solution complexity as an independent objective to be minimized in addition to the main objective of the misclassification error. We thus give preference to simpler solutions which tend to generalize well on unseen data, in accordance with Occam’s Razor. We obtain classification results on a series of benchmark problems which are essentially identical to previous, more complex decomposition approaches. Our solutions are much simpler and computationally attractive as well as able to readily incorporate changing priors/costs. In addition, we have also applied our approach to the KDD-99 intrusion detection dataset and obtained results which are highly competitive with the KDD-99 Cup winner but with a significantly simpler classification framework.     

Breast cancer diagnosis using genetic programming generated feature

This paper proposes a novel method for breast cancer diagnosis using the feature generated by genetic programming (GP). We developed a new feature extraction measure (modified Fisher linear discriminant analysis (MFLDA)) to overcome the limitation of Fisher criterion. GP as an evolutionary mechanism provides a training structure to generate features. A modified Fisher criterion is developed to help GP optimize features that allow pattern vectors belonging to different categories to distribute compactly and disjoint regions. First, the MFLDA is experimentally compared with some classical feature extraction methods (principal component analysis, Fisher linear discriminant analysis, alternative Fisher linear discriminant analysis). Second, the feature generated by GP based on the modified Fisher criterion is compared with the features generated by GP using Fisher criterion and an alternative Fisher criterion in terms of the classification performance. The classification is carried out by a simple classifier (minimum distance classifier). Finally, the same feature generated by GP is compared with a original feature set as the inputs to multi-layer perceptrons and support vector machine. Results demonstrate the capability of this method to transform information from high-dimensional feature space into one-dimensional space and automatically discover the relationship among data, to improve classification accuracy.     

Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems

We solve the multi-objective flexible job-shop problems by using dispatching rules discovered through genetic programming. While Simple Priority Rules have been widely applied in practice, their efficacy remains poor due to lack of a global view. Composite dispatching rules have been shown to be more effective as they are constructed through human experience. In this paper, we evaluate and employ suitable parameter and operator spaces for evolving composite dispatching rules using genetic programming, with an aim towards greater scalability and flexibility. Experimental results show that composite dispatching rules generated by our genetic programming framework outperforms the single dispatching rules and composite dispatching rules selected from literature over five large validation sets with respect to minimum makespan, mean tardiness, and mean flow time objectives. Further results on sensitivity to changes (in coefficient values and terminals among the evolved rules) indicate that their designs are robust.     

Termite tunneling feature extraction using genetic algorithm

Path design uses information about termite reproduction and the termite environment necessary for tunneling. Features are extracted by analyzing relevance of this information, and the fitness and relevance of these features are evaluated. The proposed method is demonstrated and is capable of finding various optimal termite tunneling paths.     

解非线性约束规划问题的新型多目标遗传算法

给出非线性约束规划问题的一种新解法。把带约束的非线性规划问题转化成为两个目标的多目标优化问题,并为转化后的多目标优化模型设计了一种新型多目标遗传算法,数据实验表明该算法对带约束的非线性规划问题求解是非常有效的。     

Modelling and prediction of complex non-linear processes by using Pareto multi-objective genetic programming

In this paper, a new multi-objective genetic programming (GP) with a diversity preserving mechanism and a real number alteration operator is presented and successfully used for Pareto optimal modelling of some complex non-linear systems using some input–output data. In this study, two different input–output data-sets of a non-linear mathematical model and of an explosive cutting process are considered separately in three-objective optimisation processes. The pertinent conflicting objective functions that have been considered for such Pareto optimisations are namely, training error (TE), prediction error (PE), and the length of tree (complexity of the network) (TL) of the GP models. Such three-objective optimisation implementations leads to some non-dominated choices of GP-type models for both cases representing the trade-offs among those objective functions. Therefore, optimal Pareto fronts of such GP models exhibit the trade-off among the corresponding conflicting objectives and, thus, provide different non-dominated optimal choices of GP-type models. Moreover, the results show that no significant optimality in TE and PE may occur when the TL of the corresponding GP model exceeds some values.     

A multi-objective genetic algorithm approach for solving feature addition problem in feature fatigue analysis

Feature fatigue (FF) is used to represent the phenomenon of customer’s inconsistent satisfaction with products: customers prefer to choose products with more features and capabilities initially, but after having worked with a product, they become frustrated or dissatisfied with the usability problems caused by too many features. To “defeat” FF, it is essential for designers to decide what features should be added when developing a product to make the product attractive enough and not too hard to use at the same time. In this paper, a feature fatigue multi-objective genetic algorithm (FFMOGA) method is reported for solving the feature addition problem. In the proposed method, fitness functions are established based on Bayesian networks, which can represent the uncertain customer preferences and reflect the relationships among features. The computational experiments on a smart phone case show that the FFMOGA approach can find multiple solutions along the Pareto-optimal frontier for designers to select from, and these obtained solutions have good performance in convergence.     

Evolving rule induction algorithms with multi-objective grammar-based genetic programming

Multi-objective optimization has played a major role in solving problems where two or more conflicting objectives need to be simultaneously optimized. This paper presents a Multi-Objective grammar-based genetic programming (MOGGP) system that automatically evolves complete rule induction algorithms, which in turn produce both accurate and compact rule models. The system was compared with a single objective GGP and three other rule induction algorithms. In total, 20 UCI data sets were used to generate and test generic rule induction algorithms, which can be now applied to any classification data set. Experiments showed that, in general, the proposed MOGGP finds rule induction algorithms with competitive predictive accuracies and more compact models than the algorithms it was compared with.

Efficient multi-objective higher order mutation testing with genetic programming

It is said 90% of faults that survive manufacturer’s testing procedures are complex. That is, the corresponding bug fix contains multiple changes. Higher order mutation testing is used to study defect interactions and their impact on software testing for fault finding. We adopt a multi-objective Pareto optimal approach using Monte Carlo sampling, genetic algorithms and genetic programming to search for higher order mutants which are both hard-to-kill and realistic. The space of complex faults (higher order mutants) is much larger than that of traditional first order mutations which correspond to simple faults, nevertheless search based approaches make this scalable. The problems of non-determinism and efficiency are overcome. Easy to detect faults may become harder to detect when they interact and impossible to detect single faults may be brought to light when code contains two such faults. We use strong typing and BNF grammars in search based mutation testing to find examples of both in ancient heavily optimised every day C code.     

Model-based space planning for temporary structures using simulation-based multi-objective programming

Construction trades need to share temporary structures to increase the output of direct work while controlling the labor input of indirect work. The purpose of this research is to develop a framework to determine the optimal location of temporary structures in a computerized practical manner for piping construction projects. Based on the spatial relationship between work envelope and scaffolding placement requirements, this paper presents the optimization model in two phases: the simulation-based optimization model and a multi-attribute utility (MAU) based alternative selection model. A multi-objective optimization model is established to improve scaffolding availability among multiple activities while maximizing piping crew productivity. The multi-attribute utility model is employed to handle the uncertainty of the assessment weights on the attributes to illustrate the preference of decision makers among different scaffolding placement alternatives obtained from the first phase. The approach was validated in a piping module, which provided superintendents and space planners with an effective decision-making tool among possible scaffolding alternatives in piping construction. The proposed optimization technique is an alternative methodology for solving the productivity-tasks-scaffolding trade-off problem, which further revolutionizes the spatial coordination process of workspace management and temporary structure planning.     

Classification using adaptive wavelets for feature extraction

A major concern arising from the classification of spectral data is that the number of variables or dimensionality often exceeds the number of available spectra. This leads to a substantial deterioration in performance of traditionally favoured classifiers. It becomes necessary to decrease the number of variables to a manageable size, whilst, at the same time, retaining as much discriminatory information as possible. A new and innovative technique based on adaptive wavelets, which aims to reduce the dimensionality and optimize the discriminatory information is presented. The discrete wavelet transform is utilized to produce wavelet coefficients which are used for classification. Rather than using one of the standard wavelet bases, we generate the wavelet which optimizes specified discriminant criteria     

A multi-objective genetic algorithm for simultaneous model and feature selection for support vector machines

The Support Vector Machines (SVM) constitute a very powerful technique for pattern classification problems. However, its efficiency in practice depends highly on the selection of the kernel function type and relevant parameter values. Selecting relevant features is another factor that can also impact the performance of SVM. The identification of the best set of parameters values for a classification model such as SVM is considered as an optimization problem. Thus, in this paper, we aim to simultaneously optimize SVMs parameters and feature subset using different kernel functions. We cast this problem as a multi-objective optimization problem, where the classification accuracy, the number of support vectors, the margin and the number of selected features define our objective functions. To solve this optimization problem, a method based on multi-objective genetic algorithm NSGA-II is suggested. A multi-criteria selection operator for our NSGA-II is also introduced. The proposed method is tested on some benchmark data-sets. The experimental results show the efficiency of the proposed method where features were reduced and the classification accuracy has been improved.     

改进的多类支持向量机递归特征消除在癌症多分类中的应用

为处理癌症多分类问题,已经提出了多类支持向量机递归特征消除(MSVM-RFE)方法,但该方法考虑的是所有子分类器的权重融合,忽略了各子分类器自身挑选特征的能力。为提高多分类问题的识别率,提出了一种改进的多类支持向量机递归特征消除(MMSVM-RFE)方法。所提方法利用一对多策略把多类问题化解为多个两类问题,每个两类问题均采用支持向量机递归特征消除来逐渐剔除掉冗余特征,得到一个特征子集;然后将得到的多个特征子集合并得到最终的特征子集;最后用SVM分类器对获得的特征子集进行建模。在3个基因数据集上的实验结果表明,改进的算法整体识别率提高了大约2%,单个类别的精度有大幅度提升甚至100%。与随机森林、k近邻分类器以及主成分分析(PCA)降维方法的比较均验证了所提算法的优势。     

Precast production scheduling using multi-objective genetic algorithms

The goal of production scheduling is to achieve a profitable balance among on-time delivery, short customer lead time, and maximum utilization of resources. However, current practices in precast production scheduling are fairly basic, depending heavily on experience, thereby resulting in inefficient resource utilization and late delivery. Moreover, previous methods ignoring buffer size between stations typically induce unfeasible schedules. Certain computational techniques have been proven effective in scheduling. To enhance precast production scheduling, this research develops a multi-objective precast production scheduling model (MOPPSM). In the model, production resources and buffer size between stations are considered. A multi-objective genetic algorithm is then developed to search for optimum solutions with minimum makespan and tardiness penalties. The performance of the proposed model is validated by using five case studies. The experimental results show that the MOPPSM can successfully search for optimum precast production schedules. Furthermore, considering buffer sizes between stations is crucial for acquiring reasonable and feasible precast production schedules.     

Content-adaptive feature extraction using image variance

The problem of scale is of fundamental interest in image processing, as the features that we visually perceive and find meaningful vary significantly depending on their size and extent. It is well known that the strength of a feature in an image may depend on the scale at which the appropriate detection operator is applied. It is also the case that many features in images exist significantly over a limited range of scales, and, of particular interest here, that the most salient scale may vary spatially over the feature. Hence, when designing feature detection operators, it is necessary to consider the requirements for both the systematic development and adaptive application of such operators over scale- and image-domains.

We present a new approach to the design of scalable derivative edge detectors, based on the finite element method, that addresses the issues of method and scale adaptability. The finite element approach allows us to formulate scalable image derivative operators that can be implemented using a combination of piecewise-polynomial and Gaussian basis functions. The issue of scale is addressed by partitioning the image in order to identify local key scales at which significant edge points may exist. This is achieved by consideration of empirically designed functions of local image variance.     

求多目标优化问题的粒子群优化算法

将粒子群优化算法应用于求解多目标优化问题,提出一种双向搜索机制,指导粒子向着搜索空间中非劣目标区域以及粒子分布最为稀疏的区域这两个方向进行寻优,进而提出了求解多目标优化问题的基于粒子群优化算法的双向搜索法,该算法对粒子全局最优经验的选择策略以及粒子群的状态更新机制进行了改进。实验研究表明,该算法不仅能快速有效地获得多目标优化问题的非劣最优解集,而且求出的解集具有良好的分布性。     

Automatic mineral identification using genetic programming

Automatic mineral identification using evolutionary computation technology is discussed. Thin sections of mineral samples are photographed digitally using a computer-controlled rotating polarizer stage on a petrographic microscope. A suite of image processing functions is applied to the images. Filtered image data for identified mineral grains is then selected for use as training data for a genetic programming system, which automatically synthesizes computer programs that identify these grains. The evolved programs use a decision-tree structure that compares the mineral image values with one other, resulting in a thresholding analysis of the multi-dimensional colour and textural space of the mineral images. Received: 18 October 1999 / Accepted: 20 January 2001