Success in Evolutionary Computation

Fundamental research into Genetic Algorithms (GA) has led to one of the biggest successes in the design of stochastic optimization algorithms: Estimation-of-Distribution Algorithms (EDAs). These principled algorithms identify and exploit structural features of a problems structure during optimization. EDA design has so far been limited to classical solution representations such as binary strings or vectors of real values. In this chapter we adapt the EDA approach for use in optimizing problems with tree representations and thereby attempt to expand the boundaries of successful evolutionary algorithms. To do so, we propose a probability distribution for the space of trees, based on a grammar. To introduce dependencies into the distribution, grammar transformations are performed that facilitate the description of specific subfunctions. The results of performing experiments on two benchmark problems demonstrate the feasibility of the approach.

Neuroevolution refers to the design of arti.cial neural networks using evolutionary algorithms. It has been one of the promising application areas for evolutionary computation, as neural network design is still being done by human experts and automating the design process by evolutionary approaches will benefit developing intelligent systems and understanding "real” neural networks. The core issue in neuroevolution is to build an efficient, problem-independent encoding scheme to represent repetitive and recurrent modules in networks. In this chapter, we have presented our descriptive encoding language based on genetic programming and showed experimental results supporting our argument that high-level descriptive languages are a viable and efficient method for development of effective neural network applications.

A core element of modern engineering is optimization with computationally expensive ‘black-box’ functions. We identify three open critical issues in optimization of such functions: (a) how to generate accurate surrogate-models (b) how to handle points where the simulation fails to converge and (c) how to balance exploration vs. exploitation.

In this work we propose a novel surrogate-assisted memetic algorithm which addresses these issues and analyze its performance. The proposed algorithm contains four novelties: (a) it autonomously generates an accurate surrogate-models using multiple cross-validation tests (b) it uses interpolation to generate a global penalty function which biases the global search away from points where the simulation did not converge (c) it uses a method based on the Metropolis criterion from statistical physics to manage exploration vs. exploitation and (d) it combines an EA with the trust-region derivative-free algorithm. The proposed algorithm generates global surrogate-models of the expensive objective function and searches for an optimum using an EA; it then uses a trust-region local-search which combines local quadratic surrogate-models and sequential quadratic programming with the trust-region framework, and converges to an accurate optimum of the true objective function. While the global-local search approach has been studied previously, the improved performance in our algorithm is due to the four novelties just mentioned.

We present a detailed performance analysis, in which the proposed algorithm significantly outperformed four variants of a real-coded EA on three difficult optimization problems which include mathematical test functions with a complicated landscape, discontinuities and a tight limit of only 100 function evaluations. The proposed algorithm was also benchmarked against a recent memetic algorithm and a recent EA and significantly outperformed both, showing it is competitive with some of the best available algorithms.

Lastly, the proposed algorithm was also applied to a difficult real-world engineering problem of airfoil shape optimization; also in this experiment it consistently performed well, and in spite of a many points where the simulation did not converge, and the tight limit on function evaluations it obtained an airfoil which satisfies the requirements very well.

Overall, the proposed algorithm offers a solution to important open issues in optimization of computationally-expensive black-box functions: generating accurate surrogate-models, handling points where the simulation does not converge and managing exploration-exploitation to improve the optimization search when only a small number of function evaluations are allowed, and it efficiently obtains a good approximation to an optimum of such functions in difficult real-world optimization problems.

In recent years there has been a rapid growth in the successful use of advanced data mining and knowledge discovery systems in many diverse areas such as science, medicine and commerce. The main contribution factor for the development of such systems in medicine has been the extra demands for more powerful yet flexible and transparent techniques to cope with the extensive amount of data and knowledge stored in clinical databases. Many of these techniques are currently under active development for use in the practice of clinical medicine. This chapter will consider a long standing problem of clinical knowledge discovery and decision making process, which is concerned with intelligently processing large amounts of clinical and medical data for knowledge discovery and decision support. The primary aim of this chapter will be to outline some of the potential and common challenges and expectations of intelligent knowledge discovery and data mining systems in medical sectors.

This chapter describes a computational intelligence system for portfolio management and provides a comparison of the relative performance of portfolios of managed by the system using stocks selected from the ASX (Australian Stock Exchange). The core of the system is the development of trading rules to guide portfolio management. The rules the system develops are adapted to dynamic market conditions.

An integrated process for stock selection and portfolio management enables a search specification that produces highly adaptive and dynamic rule bases. Rule base solutions are represented using fuzzy logic and an evolutionary process facilitates a search for high performing fuzzy rule bases. Performance is defined using a novel evaluation function involving simulated trading on a recent historical data window.

The system is readily extensible in terms of the information set used to construct rules, however to produce the results given in this chapter information derived only from price and volume history of stock prices was used. The approach is essentially referred to as technical analysis - as opposed to using information from outside the market such as fundamental accounting and macroeconomic data. A set of possible technical indicators commonly used by traders forms the basis for rule construction.

The fuzzy rule base representation enables intuitive natural language interpretation of trading signals and implies a search space of possible rules that corresponds to trading rules a human trader could construct. An example of a typical technical trading rule such as "buy when the price of a stock X´s price becomes higher than the single moving average of the stock X´s price for the last, say, 20 days" (indicating a possible upward trend) could be encoded using a fuzzy logic rule such as "if single moving average buy signal is High then rating is 1"; conversely we could have a trading rule such as "sell stocks with high volatility when the portfolio value is relatively low" encoded by a fuzzy rule: "if Price Change is High and Portfolio Value is Extremely Low then rating is 0.1".

The fuzzy rule bases undergo an evolutionary process. An initial population of rule bases (genotypes) is selected at random and may be seeded with some rule bases that correspond to accepted technical trading strategies. Further generations are then evolved by evaluating the rule bases comprising the initial population and then taking offspring of the best performing rule bases from the previous generation.

Fuzzy rule base performance is evaluated through analysis of the results of applying a particular rule base to simulated trading. In the simulated scenario an initial capital is allocated to construct an initial portfolio at the beginning of the simulation period. This initial portfolio is managed over the rest of a data window.

The empirical results from testing the system on historical data show that the system can produce quite impressive results over the test period with respect to a range of portfolio evaluation tools. Particularly given that we impose both costs to trading and restrictions on how trades can occur and limit the information set used to information derived only from price and volume data.

Proteins perform vital functions in all living beings and their function is determined by their tri-dimensional structure. Predicting how a protein will fold into its native structure is of great importance, and is one of the challenges of modern Computational Biology. Due to the complexity of the problem, simplified computational models were proposed, such as the 2-dimensional Hydrophobic-Polar (2D-HP) model. We proposed a hybrid genetic algorithm (GA) for the problem, with the following features: a fitness function based on the concept of radius of gyration, two biologically inspired genetic operators, and directed local search for improvement of solutions. Computational experiments include a detailed parameter analysis, tests with a data set of nine synthetic amino acid chains (from 20 to 85 residues long), and six real-world proteins translated to the 2D-HP model (from 96 to 330 residues long). The performance of the GA for the first data set was better than other approaches in the recent literature. For the second data set, the analysis considered both the quality of the folding and the processing time. Overall results were very promising and suggest the suitability of the hybrid GA.

To remain competitive, many agricultural systems are now being run along business lines. Systems methodologies are being incorporated, and here evolutionary computation is a valuable tool for identifying more profitable or sustainable solutions. However, agricultural models typically pose some of the more challenging problems for optimisation. This chapter outlines these problems, and then presents a series of three case studies demonstrating how they can be overcome in practice. Firstly, increasingly complex models of Australian livestock enterprises show that evolutionary computation is the only viable optimisation method for these large and difficult problems. On-going research is taking a notably efficient and robust variant, differential evolution, out into real-world systems. Next, models of cropping systems in Australia demonstrate the challenge of dealing with competing objectives, namely maximising farm profit whilst minimising resource degradation. Pareto methods are used to illustrate this trade-off, and these results have proved to be most useful for farm managers in this industry. Finally, land-use planning in the Netherlands demonstrates the size and spatial complexity of real-world problems. Here, GISbased optimisation techniques are integrated with Pareto methods, producing better solutions which were acceptable to the competing organizations. These three studies all show that evolutionary computation remains the only feasible method for the optimisation of large, complex agricultural problems. An extra benefit is that the resultant population of candidate solutions illustrates trade-offs, and this leads to more informed discussions and better education of the industry decision-makers.

This paper introduces guidelines for the automatic synthesis of analog circuits by performing evolutionary operations. It is shown that the synthesis of unity-gain cells (UGCs) can be done from nullor-based descriptions. In this manner, UGCs such as: the voltage follower (VF), current follower (CF), voltage mirror (VM), and current mirror (CM), are described using a new genetic representation consisting of ordered genes. Furthermore, a genetic algorithm (GA) is introduced in order to search for the best UGC by performing crossover and mutation operations, and by selecting UGCs by elitism. On the other hand, since GAs operate on the principle of survival of the fittest, the proposed GA has the capability to generate new design solutions, i.e. new UGCs. Additionally, the synthesized UGCs are evolved to design more complex circuits, namely: current conveyors (CCs), inverting CCs (ICCs), and current-feedback amplifiers (CFOAs). Finally, some analog circuit evolution approaches are described to synthesize practical applications such as: active filters, single-resistance controlled oscillators (SRCOs), and chaotic oscillators, which are implemented using UGCs, CCs, and CFOAs.

Applying multi-objective optimization algorithms to practical optimization problems, a high number of multi-dimensional data has to be handled: data of the genotype and phenotype as well as additional information of the optimization problem. This chapter gives an overview of several methods for visualization and analysis which are combined with regard to the characteristics of solution sets generated by evolutionary algorithms in order to get an intuitive instrument for decision making and gaining insight into both - the problem and the algorithm. They are discussed by means of two current production engineering problems providing a high economic potential: the optimization of the five-axis milling process and the design of cooling duct layouts.

In this chapter we describe some of the most important privacy problems that the Information Society has to face in a variety of fields, namely ecommerce, health care, etc. We next propose a solution based on data aggregation, which is known to be NP-hard when applied to multivariate data. Due to this computational complexity, it is necessary to use heuristics to solve the problem. We propose the use of a Genetic Algorithm (GA) conveniently tuned up for tackling the problem properly.

This chapter consists of two parts. Firstly, a revision of the state-ofthe- art is presented for the application of EC techniques to several problems arising in telecommunications. The revision includes wired based networks, wireless networks considering both planning and operation stages. Secondly, an evolutionary computation approach is proposed to solve the very complex telecommunications network global planning problem. The model is based on a hubbing topology that considers two hierarchical levels for low and high speed telecommunication networks. EC results are compared with industry heuristic solutions showing a much better behaviour, outperforming it in all the analysed ranges.

In this chapter, a novel evolutionary approach to survivable network design is presented when considering both economics and reliability. It is based on a combinatorial variant of the evolution strategy and clearly outperforms existing benchmark results by genetic algorithms. The integration of domain-specific knowledge in the mutation operator and a repair heuristic raises the performance of an otherwise broadly applicable but less effective metaheuristic. Moreover, the results underline the important but so far often neglected potential of evolution strategies in combinatorial optimization.

Evolutionary Computation (EC) mimics the process of natural evolution, and particularly its versions known as Genetic Algorithms (GAs) and Differential Evolution (DE) help engineers and researchers to optimize their designs using the Darwin's principle of “survival of the fittest”. These optimization principles are very frequently used in electronics for design of complex electronic systems such as VLSI circuit design and for their automated test. The present chapter of the book should intimate the reader with the optimization requirements in VLSI circuit design and testing and also demonstrate how the optimization could be achieved using evolutionary computation methodology. This will also be demonstrated on some specific application examples of design optimization and post-production test automation of VLSI circuit.

This chapter seeks to follow Axelrod's research of computer simulations on the Iterated Prisoner's Dilemma (IPD) game to investigate the use of Genetic Algorithms (GA) in evolving cooperation within a competitive market environment. We use an agent-based economy model as the basis of our experiments to examine how well GA could perform against the IPD game strategies. We also explore the strategic interactions among the agents that represent firms in a coevolving population, and study the influence of the genetic operators on GA to evolve cooperative agents.

Evolutionary algorithms have been studied in the context of optimization problems for decades. These nature-inspired methods have lately received increasing amount of attention especially among demanding practical optimization tasks. This Chapter describes how evolutionary algorithms can be used to increase the speed and robustness of the design process of a digital filter used in power systems instrumentation. Designing such filters is a challenging optimization problem due to a discrete and exhaustive search space and time-consuming evaluation of the objective function. This chapter introduces new approaches to evolutionary computation using adaptive parameters, hierarchical populations, and the fusion of neural networks and evolutionary algorithms to tackle the bottlenecks of this challenging design process.

This chapter is to present a successful industry case applying Genetic Algorithms (GAs). The case has applied GAs for the purpose of optimizing the total cost of a multiple sourcing supply chain system. The system is characterized by a multiple sourcing model with stochastic demand. A mathematical model is adopted to describe the stochastic inventory with the many-to-many demandsupplier network problem and it simultaneously constitutes the inventory control and transportation parameters as well as price uncertainty factors. Genetic Algorithms are applied to derive optimal solutions through the optimization process. A numerical example and its solution demonstrate the detail solution procedure based on Genetic Algorithms and shows that GAs are able to solve such a di.cult problem e.ciently and easily. Further research is also discussed.