一种求解混合整数规划的混合进化算法

提出一种基于正交试验设计的混合进化算法,用于求解混合整数规划问题.进化算法中采用一种混合启发式的变异算子,将正交试验设计作为杂交算子.为了增加种群的多样性,引入一种迁移算子.仿真实验结果表明,与已有的一些算法相比,所提出的求解混合整数规划的混合进化算法能快速收敛到问题的最优解,并且算法的计算量小,解的精度高.     

Resolution of pattern recognition problems using a hybrid Genetic/Random Neural Network learning algorithm

Gelenbe has proposed a neural network, called a Random Neural Network, which calculates the probability of activation of the neurons in the network. In this paper, we propose to solve the patterns recognition problem using a hybrid Genetic/Random Neural Network learning algorithm. The hybrid algorithm trains the Random Neural Network by integrating a genetic algorithm with the gradient descent rule-based learning algorithm of the Random Neural Network. This hybrid learning algorithm optimises the Random Neural Network on the basis of its topology and its weights distribution. We apply the hybrid Genetic/Random Neural Network learning algorithm to two pattern recognition problems. The first one recognises or categorises alphabetic characters, and the second recognises geometric figures. We show that this model can efficiently work as associative memory. We can recognise pattern arbitrary images with this algorithm, but the processing time increases rapidly.     

Genetic optimization of GRNN for pattern recognition without feature extraction

This paper describes an approach for pattern recognition using genetic algorithm and general regression neural network (GRNN). The designed system can be used for both 3D object recognition from 2D poses of the object and handwritten digit recognition applications. The system does not require any preprocessing and feature extraction stage before the recognition. In GRNN, placement of centers has significant effect on the performance of the network. The centers and widths of the hidden layer neuron basis functions are coded in a chromosome and these two critical parameters are determined by the optimization using genetic algorithms. Experimental results show that the optimized GRNN provides higher recognition ability compared with that of unoptimized GRNN.     

Backward-chaining evolutionary algorithms

Starting from some simple observations on a popular selection method in Evolutionary Algorithms (EAs)—tournament selection—we highlight a previously-unknown source of inefficiency. This leads us to rethink the order in which operations are performed within EAs, and to suggest an algorithm—the EA with efficient macro-selection—that avoids the inefficiencies associated with tournament selection. This algorithm has the same expected behaviour as the standard EA but yields considerable savings in terms of fitness evaluations. Since fitness evaluation typically dominates the resources needed to solve any non-trivial problem, these savings translate into a reduction in computer time. Noting the connection between the algorithm and rule-based systems, we then further modify the order of operations in the EA, effectively turning the evolutionary search into an inference process operating in backward-chaining mode. The resulting backward-chaining EA creates and evaluates individuals recursively, backward from the last generation to the first, using depth-first search and backtracking. It is even more powerful than the EA with efficient macro-selection in that it shares all its benefits, but it also provably finds fitter solutions sooner, i.e., it is a faster algorithm. These algorithms can be applied to any form of population based search, any representation, fitness function, crossover and mutation, provided they use tournament selection. We analyse their behaviour and benefits both theoretically, using Markov chain theory and space/time complexity analysis, and empirically, by performing a variety of experiments with standard and back-ward chaining versions of genetic algorithms and genetic programming.     

User-system cooperative evolutionary computation for both quantitative and qualitative objective optimization in image processing filter design

This study proposes a cooperative evolutionary optimization method between a user and system (CEUS) for problems involving quantitative and qualitative optimization criteria. In a general interactive evolutionary computation (IEC) model, both the system and user have their own role in the evolution, such as individual reproduction or evaluation. In contrast, the proposed CEUS allows the user to dynamically change the allocation of search roles between the system and user, resulting in simultaneous optimization of qualitative and quantitative objective functions without increasing user fatigue. This is achieved by a combination of user evaluation prediction and the integration of interactive and non-interactive EC. For instance, the system performs a global search at the beginning, the user then intensifies the search area, and finally the system conducts a local search in the intensified search area. This study applies CEUS to an image processing filter design problem that involves both quantitative (filter output accuracy) and qualitative (filter behavior) criteria. Experiments have shown that the proposed CEUS can design image filters in accordance with user preferences, and CEUS interacting with a non-naive user enhanced the initial global search so that it converged and found a reasonable solution more than four times faster than a non-interactive search.     

Hybrid evolutionary algorithm and application to structural optimization

This paper introduces a new evolutionary algorithm with a globally stochastic but locally heuristic search strategy. It is implemented by incorporating a modified micro-genetic algorithm with two local optimization operators. Performance tests using two benchmarking functions demonstrate that the new algorithm has excellent convergence performance when applied to multimodal optimization problems. The number of objective function evaluations required to obtain global optima is only 3.5–3.7% of that of using the conventional micro-genetic algorithm. The new algorithm is used to optimize the design of an 18-bar truss, with the aim of minimizing its weight while meeting the stress, section area, and geometry constraints. The corresponding optimal design is obtained with considerably fewer computational operations than required for the existing algorithms.     

Increasing pattern recognition accuracy for chemical sensing by evolutionary based drift compensation

Artificial olfaction systems, which mimic human olfaction by using arrays of gas chemical sensors combined with pattern recognition methods, represent a potentially low-cost tool in many areas of industry such as perfumery, food and drink production, clinical diagnosis, health and safety, environmental monitoring and process control. However, successful applications of these systems are still largely limited to specialized laboratories. Sensor drift, i.e., the lack of a sensor’s stability over time, still limits real industrial setups. This paper presents and discusses an evolutionary based adaptive drift-correction method designed to work with state-of-the-art classification systems. The proposed approach exploits a cutting-edge evolutionary strategy to iteratively tweak the coefficients of a linear transformation which can transparently correct raw sensors’ measures thus mitigating the negative effects of the drift. The method learns the optimal correction strategy without the use of models or other hypotheses on the behavior of the physical chemical sensors.     

A cooperative constructive method for neural networks for pattern recognition

In this paper, we propose a new constructive method, based on cooperative coevolution, for designing automatically the structure of a neural network for classification. Our approach is based on a modular construction of the neural network by means of a cooperative evolutionary process. This process benefits from the advantages of coevolutionary computation as well as the advantages of constructive methods. The proposed methodology can be easily extended to work with almost any kind of classifier.The evaluation of each module that constitutes the network is made using a multiobjective method. So, each new module can be evaluated in a comprehensive way, considering different aspects, such as performance, complexity, or degree of cooperation with the previous modules of the network. In this way, the method has the advantage of considering not only the performance of the networks, but also other features.The method is tested on 40 classification problems from the UCI machine learning repository with very good performance. The method is thoroughly compared with two other constructive methods, cascade correlation and GMDH networks, and other classification methods, namely, SVM, C4.5, and k nearest-neighbours, and an ensemble of neural networks constructed using four different methods.     

Hybrid evolutionary neuro-fuzzy approach based on mutual adaptation for human gesture recognition

One of the most important techniques in human-robot communication is gesture recognition. If robots can read intentions from human gestures, the communication process will be smoother and more natural. Processing for gesture recognition typically consists of two parts: feature extraction and gesture classification. In most works, these are independently designed and evaluated by their own criteria. This paper proposes a hybrid approach based on mutual adaptation for human gesture recognition. We use a neuro-fuzzy system (NFS) for the classification of human gesture and apply an evolution strategy for parameter tuning and pruning of membership functions. Experimental results indicate the effectiveness of mutual adaptation in terms of the generalization.     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

Hybrid evolutionary method for obstacle location-allocation

In this paper we propose a hybrid evolutionary method for Obstacle Location-allocation problem. This problem can be described as a tri-level mixed integer programming problem. Since this problem is very complex and with many local solutions, no direct method is effective to solve it. Heuristic methods were proposed to it, but optimality is not guaranteed yet. Our hybrid evolutionary method adopts the main structure of Genetic Algorithms (GA) absorbing ideas from Evolutionary Strategy (ES) and combines with some traditional optimization techniques. In this way we can pursue global optimization maintaining a good efficiency of our method. A case study shows the effectiveness of this method.     

Hybrid evolutionary method for capacitated location-allocation problem

Location-allocation model is widely applied for facility location design in practice. In this paper, we discuss an extension of location-allocation model which has capacity constraints and propose a hybrid evolutionary method to solve it which absorbs ideas from both genetic algorithms (GAs) and evolutionary strategy (ES) as well as combined with efficient traditional optimization techniques. It is shown that the proposed method is effective in finding global or near global solutions by numerical simulations.     

Barcode design by evolutionary computation

This paper proposes a method for generating 2-dimensional barcode incorporated some illustrations inside of the code without detracting machine-readability and stored information. We formulate the task that finding appropriate positions, scales, and angles of illustrations, photographs, logos or other image items put in QR code as an optimization problem. By using evolutionary computation algorithm, the proposed system can find positions in which given image items can be merged without damaging machine-readability. QR code is trademarked by Denso Wave, inc. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

基于混合量子进化计算的混沌系统参数估计

混沌系统参数估计本质上是一多维参数优化问题.为精确估计混沌系统的未知参数,本文提出一种混合量子进化算法(HQEA)用于求解该优化问题,该方法采用实数量子角形式表示染色体,用量子比特的概率作为个体的当前位置信息;提出由差分进化计算更新量子位置状态的量子差分进化算法(QDE),并将其与实数编码量子进化算法(RQEA)相融合,以便令算法在解空间的全局探索和局部开发能力之间取得平衡.算法还引入量子非门算子,对当前最佳个体中按某个概率选中的量子比特位,进行变换操作,以便增强算法跳出局部最优解的能力.基准函数测试表明混合算法的全局搜索能力及可靠性都有很大改善.通过Lorenz混沌系统进行数值仿真,结果表明了该混合算法的有效性.     

A flexible sequence alignment approach on pattern mining and matching for human activity recognition

This paper proposes a flexible sequence alignment approach for pattern mining and matching in the recognition of human activities. During pattern mining, the proposed sequence alignment algorithm is invoked to extract out the representative patterns which denote specific activities of a person from the training patterns. It features high performance and robustness on pattern diversity. Besides, the algorithm evaluates the appearance probability of each pattern as weight and allows adapting pattern length to various human activities. Both of them are able to improve the accuracy of activity recognition. In pattern matching, the proposed algorithm adopts a dynamic programming based strategy to evaluate the correlation degree between each representative activity pattern and the observed activity sequence. It can avoid the trouble on segmenting the observed sequence. Moreover, we are able to obtain recognition results continuously. Besides, the proposed matching algorithm favors recognition of concurrent human activities with parallel matching. The experimental result confirms the high accuracy of human activity recognition by the proposed approach.     

GenTrust: A genetic trust management model for peer-to-peer systems

In recent years, peer-to-peer systems have attracted significant interest by offering diverse and easily accessible sharing environments to users. However, this flexibility of P2P systems introduces security vulnerabilities. Peers often interact with unknown or unfamiliar peers and become vulnerable to a wide variety of attacks. Therefore, having a robust trust management model is critical for such open environments in order to exclude unreliable peers from the system. In this study, a new trust model for peer-to-peer networks called GenTrust is proposed. GenTrust has evolved by using genetic programming. In this model, a peer calculates the trustworthiness of another peer based on the features extracted from past interactions and the recommendations. Since the proposed model does not rely on any central authority or global trust values, it suits the decentralized nature of P2P networks. Moreover, the experimental results show that the model is very effective against various attackers, namely individual, collaborative, and pseudospoofing attackers. An analysis on features is also carried out in order to explore their effects on the results. This is the first study which investigates the use of genetic programming on trust management.     

一种求解同等并行机调度的混合量子衍生进化规划算法

针对带顺序相关建立时间的同等并行机调度问题的求解,提出一种新的混合量子衍生进化规划算法.该算法通过定义新的量子个体来表示调度问题中的工件排序,并定义了针对调度问题的量子旋转角,使个体向更好的解靠近.同时,针对并行机问题本身,改进了个体的编码方式和新的变异方法.为了验证算法的有效性和收敛性,采用不同规模的算例进行仿真实验.结果表明,即使在小种群情况下,算法所得解均优于基本进化规划求得的解.     

A learning procedure for multisurface method of pattern separation

Mangasarian⁽⁵⁾ has proposed an interesting method of pattern separation, which is called “multisurface method”. In the method, linear programming problems are recursively solved, and the correct classification of any disjoint pattern sets is basically possible. However the fact that linear programming problems are recursively solved leads to the result that it takes long computation times and requires much memory space of computer in use. This paper describes a learning procedure for multi-surface method instead of linear programming to avoid drawbacks above. The proposed learning algorithm requires only repetitive simple calculations. Experimental results show that computation times required by learning procedure proposed are shorter than those by linear programming.