Evolutionary design of Evolutionary Algorithms

Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility (which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

Evolutionary model trees for handling continuous classes in machine learning

Model trees are a particular case of decision trees employed to solve regression problems. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is an NP-Complete problem, traditional model tree induction algorithms make use of a greedy top-down divide-and-conquer strategy, which may not converge to the global optimal solution. In this paper, we propose a novel algorithm based on the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to globally near-optimal solutions. We call our new approach evolutionary model tree induction (E-Motion). We test its predictive performance using public UCI data sets, and we compare the results to traditional greedy regression/model trees induction algorithms, as well as to other evolutionary approaches. Results show that our method presents a good trade-off between predictive performance and model comprehensibility, which may be crucial in many machine learning applications.     

A review of procedures to evolve quantum algorithms

There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attributed to the non-intuitive nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into evolving quantum algorithms has shown promise. This paper provides an introduction into quantum and evolutionary algorithms for the computer scientist not familiar with these fields. The exciting field of using evolutionary algorithms to evolve quantum algorithms is then reviewed.

Inexact graph matching by means of estimation of distribution algorithms

Estimation of distribution algorithms (EDAs) are a quite recent topic in optimization techniques. They combine two technical disciplines of soft computing methodologies: probabilistic reasoning and evolutionary computing. Several algorithms and approaches have already been proposed by different authors, but up to now there are very few papers showing their potential and comparing them to other evolutionary computational methods and algorithms such as genetic algorithms (GAs). This paper focuses on the problem of inexact graph matching which is NP-hard and requires techniques to find an approximate acceptable solution. This problem arises when a nonbijective correspondence is searched between two graphs. A typical instance of this problem corresponds to the case where graphs are used for structural pattern recognition in images. EDA algorithms are well suited for this type of problems.

This paper proposes to use EDA algorithms as a new approach for inexact graph matching. Also, two adaptations of the EDA approach to problems with constraints are described as two techniques to control the generation of individuals, and the performance of EDAs for inexact graph matching is compared with the one of GAs.     

Genetic algorithms to solve the cover printing problem

Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms.     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

多表达式程序设计的新型评估方法

多表达式程序设计(MEP)是应用十分广泛的自动程序设计方法。从MEP的染色体表示规则及种群演化方式来看,每个染色体中的任何基因都有可能多次被当前或其它后续种群中的其他基因引用,从而造成重复计算,耗费大量时空资源。由此提出并实现了一种新型评估方法,该新型评估方法在不改变传统MEP的染色体表示规则和种群演化方式的情况下,能够准确有效地识别演化过程中所有被重复引用的基因,从而避免了大量重复计算,显著提高了演化效率。     

Study on IAC networks models: learning and stability

This paper presents a methodology that uses evolutionary learning in training ‘A’ model networks, a topology based on Interactive Activation and Competition (IAC) neural networks. IAC networks show local knowledge and processing units clustered in pools. The connections among units may assume only 1, 0 or −1. On the other hand, ‘A’ model network uses values in interval [−1, 1]. This feature provides a wider range of applications for this network, including problems which do not show mutually exclusive concepts. However, there is no algorithm to adjust the network weights and still preserve the desired characteristics of the original network. Accordingly, we propose the use of genetic algorithms in a new methodology to obtain the correct weight set for this network. Two examples are used to illustrate the proposed method. Findings are considered consistent and generic enough to allow further applications on similar classes of problems suitable for ‘A’ model IAC Networks.     

Hybrid evolutionary learning for synthesizing multi-class pattern recognition systems

This paper describes one aspect of a machine-learning system called HELPR that blends the best aspects of different evolutionary techniques to bootstrap-up a complete recognition system from primitive input data. HELPR uses a multi-faceted representation consisting of a growing sequence of non-linear mathematical expressions. Individual features are represented as tree structures and manipulated using the techniques of genetic programming. Sets of features are represented as list structures that are manipulated using genetic algorithms and evolutionary programming. Complete recognition systems are formed in this version of HELPR by attaching the evolved features to multiple perceptron discriminators. Experiments on datasets from the University of California at Irvine (UCI) machine-learning repository show that HELPR’s performance meets or exceeds accuracies previously published.     

A tribe competition-based genetic algorithm for feature selection in pattern classification

Feature selection has always been a critical step in pattern recognition, in which evolutionary algorithms, such as the genetic algorithm (GA), are most commonly used. However, the individual encoding scheme used in various GAs would either pose a bias on the solution or require a pre-specified number of features, and hence may lead to less accurate results. In this paper, a tribe competition-based genetic algorithm (TCbGA) is proposed for feature selection in pattern classification. The population of individuals is divided into multiple tribes, and the initialization and evolutionary operations are modified to ensure that the number of selected features in each tribe follows a Gaussian distribution. Thus each tribe focuses on exploring a specific part of the solution space. Meanwhile, tribe competition is introduced to the evolution process, which allows the winning tribes, which produce better individuals, to enlarge their sizes, i.e. having more individuals to search their parts of the solution space. This algorithm, therefore, avoids the bias on solutions and requirement of a pre-specified number of features. We have evaluated our algorithm against several state-of-the-art feature selection approaches on 20 benchmark datasets. Our results suggest that the proposed TCbGA algorithm can identify the optimal feature subset more effectively and produce more accurate pattern classification.     

Genetic approaches for topological active nets optimization

The topological active nets (TANs) model is a deformable model used for image segmentation. It integrates features of region-based and edge-based segmentation techniques so it is able to fit the contours of the objects and model their inner topology. Also, topological changes in its structure allow the detection of concave and convex contours, holes, and several objects in the scene. Since the model deformation is based on the minimization of an energy functional, the adjustment depends on the minimization algorithm. This paper presents two evolutionary approaches to the energy minimization problem in the TAN model. The first proposal is a genetic algorithm with ad hoc operators whereas the second approach is a hybrid model that combines genetic and greedy algorithms. Both evolutionary approaches improve the accuracy of the segmentation even though only the hybrid model allows topological changes in the model structure.     

A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

This study applies a genetic algorithm embedded with mathematical programming techniques to solve a synchronized and integrated two-level lot sizing and scheduling problem motivated by a real-world problem that arises in soft drink production. The problem considers a production process compounded by raw material preparation/storage and soft drink bottling. The lot sizing and scheduling decisions should be made simultaneously for raw material preparation/storage in tanks and soft drink bottling in several production lines minimizing inventory, shortage and setup costs. The literature provides mixed-integer programming models for this problem, as well as solution methods based on evolutionary algorithms and relax-and-fix approaches. The method applied by this paper uses a new approach which combines a genetic algorithm (GA) with mathematical programming techniques. The GA deals with sequencing decisions for production lots, so that an exact method can solve a simplified linear programming model, responsible for lot sizing decisions. The computational results show that this evolutionary/mathematical programming approach outperforms the literature methods in terms of production costs and run times when applied to a set of real-world problem instances provided by a soft drink company.     

Scaling Up Inductive Logic Programming: An Evolutionary Wrapper Approach

Inductive logic programming (ILP) algorithms are classification algorithms that construct classifiers represented as logic programs. ILP algorithms have a number of attractive features, notably the ability to make use of declarative background (user-supplied) knowledge. However, ILP algorithms deal poorly with large data sets (>10⁴ examples) and their widespread use of the greedy set-covering algorithm renders them susceptible to local maxima in the space of logic programs.This paper presents a novel approach to address these problems based on combining the local search properties of an inductive logic programming algorithm with the global search properties of an evolutionary algorithm. The proposed algorithm may be viewed as an evolutionary wrapper around a population of ILP algorithms.The evolutionary wrapper approach is evaluated on two domains. The chess-endgame (KRK) problem is an artificial domain that is a widely used benchmark in inductive logic programming, and Part-of-Speech Tagging is a real-world problem from the field of Natural Language Processing. In the latter domain, data originates from excerpts of the Wall Street Journal. Results indicate that significant improvements in predictive accuracy can be achieved over a conventional ILP approach when data is plentiful and noisy.     

Evolutionary neural network modeling for forecasting the field failure data of repairable systems

An accurate product reliability prediction model can not only learn and track the product’s reliability and operational performance, but also offer useful information for managers to take follow-up actions to improve the product’ quality and cost. This study proposes a new method for predicting the reliability for repairable systems. The novel method constructs a predictive model by employing evolutionary neural network modeling approach. Genetic algorithms are used to globally optimize the number of neurons in the hidden layer and learning parameters of the neural network architecture. Moreover, two case studies are presented to illustrate the proposed method. The prediction accuracy of the novel method is compared with that of other methods to illustrate the feasibility and effectiveness of the proposed method.     

基于生态竞争模型的遗传强化学习

未成熟收敛和收敛速度慢是目前遗传算法的明显缺点.借鉴生物在环境生态系统中的生长模式,文章提出一种生态竞争模型.该模型认为,竞争行为在生物的成长中占有十分重要的地位,在子群内实现了个体层次的先天遗传进化和后天竞争学习,在种群层次实现进一步的竞争强化学习.实验结果显示了该模型在解决收敛性问题时的有效性.     

A multiple minima genetic algorithm for protein structure prediction

Protein structure prediction (PSP) has a large potential for valuable biotechnological applications. However the prediction itself encompasses a difficult optimization problem with thousands of degrees of freedom and is associated with extremely complex energy landscapes. In this work a simplified three-dimensional protein model (hydrophobic-polar model, HP in a cubic lattice) was used in order to allow for the fast development of a robust and efficient genetic algorithm based methodology. The new methodology employs a phenotype based crowding mechanism for the maintenance of useful diversity within the populations, which resulted in increased performance and granted the algorithm multiple solutions capabilities. Tests against several benchmark HP sequences and comparative results showed that the proposed genetic algorithm is superior to other evolutionary algorithms. The proposed algorithm was then successfully adapted to an all-atom protein model and tested on poly-alanines. The native structure, an alpha helix, was found in all test cases as a local or a global minimum, in addition to other conformations with similar energies. The results showed that optimization strategies with multiple solutions capability present two advantages for PSP applications. The first one is a more efficient investigation of complex energy landscapes; the second one is an increase in the probability of finding native structures, even when they are not at the global optimum.     

Resilience-oriented design for complex MEP systems in BIM

Normal operation of a Mechanical, Electrical, and Plumbing (MEP) system under random and intentional attacks is important to a building. A systematic research framework is proposed to analyze the resilience of an MEP system and optimize its design. The resilience magnitude in this research measures the ability of the MEP system to keep standard operation when component failures appear. First, the MEP model in Building Information Modelling (BIM) environment is extracted to a graph database by using Revit API, which represents the complex network of an MEP system. Second, the importance of the components and the resilience of the MEP system is analyzed based on the network theory and topological metrics. Third, the failure simulation is carried out by attacking the node of the system randomly and intentionally. Finally, the genetic algorithm is used to optimize the design of the MEP system by adding new edges. The results show that: (i) the graph database is a good representation of the MEP system, and it can convert the 3D model to a format that can be analyzed by data analysis measures, (ii) the same component in the MEP system could have different importance from different perspectives, (iii) the proposed network is more resilient with bridge ratio index and average path length improved by 6.16% and 40.58%, respectively, and (iv) the proposed intentional attack strategy is more conform to reality, and it can cause more severe results to a system. The research can contribute to the implementation of the resilience design theory in the MEP discipline, and create a bond between the 3D model and data analysis.     

一种新的进化计算算法模型--种群竞争消亡算法

为克服进化计算自身的早熟收敛缺陷,受自然界和人类社会进化现象的启发,文中研究得到了一种新的进化计算算法模型——种群竞争消亡算法。本文将该模型应用于温室作物生长模型的参数优化,并将试验结果与基本进化计算相比较,结果说明种群竞争消亡算法在稳定性和收敛性上确实比基本进化计算优越。     

基于生态种群捕获竞争模型的进化遗传算法

将协同进化的思想运用到遗传算法,是对遗传算法的一大改进和拓展,借鉴此思想,提出了一种生态种群捕获竞争的协同进化模型和基于此模型的改进的进化遗传算法(PCGA)。实验结果表明,该算法在改善未成熟收敛和提高收敛速度方面都具有良好的性能。     

文化算法研究综述

文化算法模拟文化进化过程,在实现个体进化的种群空间基础上,构建信度空间,用于对进化过程中有效隐含信息的挖掘和利用。该双层进化机制为进化计算中的知识引导提供了通用框架,已证明能有效提高算法性能,并被成功用于解决诸多实际复杂优化问题。文章介绍了文化算法基本原理,从提取知识类型角度详细阐述了算法研究进展,总结了其在不同领域的应用,并展望了算法未来可能的研究方向。