Variants of Evolutionary Algorithms for Real-World Applications ‒ Preface

Authors

Abstract

Started as a mere academic curiosity, Evolutionary Algorithms (EAs) first came into sight back in the 1960s. However, it was not until the 1980s that the research on EAs became less theoretical and more practical. As a manifestation of population-based, stochastic search algorithms that mimic natural evolution, EAs use genetic operators such as crossover and mutation for the search process to generate new solutions through a repeated application of variation and selection.
Due to their ability to find excellent solutions for conventionally hard and dynamic problems within acceptable time, EAs have attracted interest from many researchers and practitioners in recent years. The general-purpose, black-box character of EAs makes them suitable for a wide range of realworld applications. Standard EAs such as Genetic Algorithms (GAs) and Genetic Programming (GP) are becoming more and more accepted in the industry and commercial sectors. With the dramatic increase in computational power today, an incredible diversification of new application areas of these techniques can be observed. At the same time, variants and other classes of evolutionary optimisation methods such as Differential Evolution, Estimation of Distribution Algorithms, Co-evolutionary Algorithms and Multi-Objective Evolutionary Algorithms (MOEAs) have been developed.
When applications or systems utilising EAs reach the production stage, off-the-shelf versions of these methods are typically replaced by dedicated algorithm variants. These specialised EAs often use tailored reproduction operators, search spaces differing significantly from the well-known binary or tree-based encodings, non-trivial genotype-phenotype mappings, or are hybridised with other optimisation algorithms. This book aims to promote the practitioner’s view on EAs by giving a comprehensive discussion of how EAs can be adapted to the requirements of various applications in the real-world domains. It comprises 14 chapters, which can be categorised into the following four sections:
• Section I: Introduction
• Section II: Planning & Scheduling
• Section III: Engineering
• Section IV: Data Collection, Retrieval & Mining
The first section contains only one single chapter – the introductory chapter. In this chapter, Blum et al. re-visit the fundamental question of “what is an EA?” in an attempt to clearly define the scope of this book. In this regard, they systematically explore and discuss both the traditional and the modern views on this question by relating it to other areas in the field. That is, apart from discussing the main characteristics of conventional EAs they also extend their discussion to Memetic Algorithms (MAs) and the Swarm Intelligence algorithms. It appears that establishing semantic borders between the different algorithm families is never easy, nor necessarily useful. In this book, however, the focus will be on the traditional set of EAs like GAs, GP, and their variants.
The second section of the book deals with planning and scheduling problems. Planning and scheduling activities are among the most important tasks in Business and Industry. Once orders are placed by a customer, it is necessary to schedule the purchase of raw materials and to decide which machines are going to be used in order to create the ordered product in the desired quality. Often, multiple different client requests need to be facilitated at the same time and the goal is to satisfy all of them in a timely and cost-effective manner. However, it is not only the production steps that need to be scheduled. In fact, the whole behaviour of a supply chain as well as the work assignments for employees can be subject to planning. This section contains six chapters, with different groups of researchers presenting efficient EA approaches to a variety of real-world planning and scheduling problems.
The first chapter in this section by Mohais et al. introduces a tailor-made EA for the process of bottling wine in a mass-production environment. Timevarying (dynamic) constraints are the focus of this chapter. That is, scheduling for job shop problems rarely starts with a blank sheet of paper. Instead, some production processes will already be in progress. Hence, there is typically a set of scheduled operations that are fixed and cannot be modified by optimisation, yet will influence the efficiency and feasibility of new plans. Mohais et al. successfully approach the wine bottling problem with their tailor-made evolutionary method.
Following which, Toledo et al. present a similar real-world problem for soft-drink manufacturing plants known as the synchronised and integrated two-level lot sizing and scheduling problem. Here, the first production level has tanks storing the soft drink flavours and the second level corresponds to the bottling lines. The problem involves capacity limits, different costs and production times depending on the raw materials involved as well as the inventory costs. In order to derive production schedules with low associated costs in this scenario, Toledo et al. propose the use of an MA. This algorithm has a population structured as tree of clusters. It uses either Threshold Accepting or Tabu Search as local search, and utilises different operators. These variants have shown to outperform both the GA and a Relax approach based on some real-world data sets. In particular, the Tabu Search variant has turned out to be very efficient and robust.
The third chapter of the section by Lässig et al. considers simulation-based optimisation of hub-and-spoke inventory systems and multi-location inventory systems with lateral transshipments. Such systems are very common in the industry, but it is extremely challenging to find the optimal order and transshipment policies for them in an analytical way. Lässig et al. therefore suggest a simulation-based evolutionary approach, where the utility of rules is estimated by simulating the behaviour of the system applying them. This simulation process is used to compute the fitness of the policies. Lässig et al. show that Threshold Accepting, Particle Swarm Optimisation, and especially GAs can effectively tackle the resulting optimisation problems.
Subsequently, Schellenberg et al. present a fuzzy-evolutionary approach for optimising the behaviour of a multi-echelon supply chain network of an Australian ASX Top 50 company. They use an EA for synthesising fuzzy rules for each link of the supply chain in order to satisfy all demands while adhering to system constraints (such as silo capacity limits which must not be exceeded due to overproduction further down the chain). Their experimental studies show that the evolution of behaviour rules that can issue commands based on the current situation is much more efficient than trying to generate complete plans scheduling each single supply and production event.
The following chapter by Dasgupta et al. provides a new solution to the task-based sailor assignment problem faced by the US Navy. That is, a sailor in active duty is usually reassigned to a different job around every three years. Here, the goal is to pick new jobs for the sailors currently scheduled for reassignment in a way that is most satisfying for them as well as the commanders. In the work presented by Dasgupta et al., these assignments have been broken further down to different tasks for different timeslots per sailor. For this purpose, Dasgupta et al. use a parallel implementation of a hybrid MOEA which combines the NSGA-II and some intelligent search operations. The experimental results show that the proposed solution is promising. In the final chapter of the section, Ma and Zhang discuss how a production planning process can be optimised with a GA using the example of CNC-based work piece construction. A customisable job shop environment is presented, which can easily be adapted by the users. The optimisation approach then simultaneously selects the right machines, tools, commands for the tools, and operation sequences to manufacture a desired product. The applied GA minimises a compound of the machine costs, the tool costs and the machine, setup, and tool change cost. It is embedded into a commercial computer-aided design system and its utility is demonstrated through a case study. The work of Ma and Zhang leads us to the third section of this book, addressing another crucial division of any industrial company: R & D (Research and Development) and Engineering. In this area, EA-based approaches again have shown huge potential for supporting the human operators in creating novel and more efficient products. However, there are two challenges. On one hand, the evaluation of an engineering design usually involves complex simulations and hence, takes quite a long time to complete. This decreases the utility of common EAs that often require numerous fitness evaluations. On the other hand, many engineering problems have a high-dimensional search space, i.e., they involve many decision variables. In this section, three chapters showcase how these challenges can be overcome and how EAs are able to deliver excellent solutions for hard, real-world engineering problems. In mechanical design problems, the goal is to find structures with specific physical properties. The Finite Element Method (FEM) can for example be used to assess the robustness of composite beams, trusses, airplane wings, and piezoelectric actuators. If such structures are to be optimised, as is the case in the chapter presented by Davarynejad et al., the FEM represents an indispensable tool for assessing the utility of the possible designs. However, each of its invocations requires a great amount of runtime and thus slows down the optimisation process considerably. To this end, Davarynejad et al. propose an adaptive fuzzy fitness granulation approach – a method which allows approximating the fitness of new designs based on previously tested ones. The proposed approach is shown to be able to reduce the amount of FEM invocations and speed up the optimisation process for these engineering problems significantly.
In the next chapter, Turan and Cui introduce a hybrid evolutionary approach for ship stability design, with a particular focus on roll on/roll off passenger ships. Since the evaluation of each ship design costs much runtime, the MOEA (i.e., NSGA-II) utilised by Turan and Cui is hybridised with Q-learning to guide the search directions. The proposed approach provides reasonably good results, where Turan and Cui are able to discover ship designs that represent significant improvements from the original design. The chapter by Rempis and Pasemann presents a new evolutionary method, which they called the Interactively Constrained Neuro-Evolution (ICONE) approach. ICONE uses an EA for synthesising the walking behaviour of humanoid robots. While bio-inspired neural control techniques have been highly promising for robot control, in the case when many sensor inputs have to be processed and many actuators need to be controlled the search space size may increase rapidly. Rempis and Pasemann therefore propose the use of both domain knowledge and restrictions of the possible network structures in their approach. As the name suggests, ICONE is interactive, thus allows the experimenter to bias the search towards the desired structures. This leads to excellent results in the walking-behaviour synthesis experiments.
The final section of the book concerns data collection, retrieval, and mining. The gathering, storage, retrieval and analysis of data is yet another essential area not just in the industry but also the public sectors, or even military. Database systems are the backbone of virtually every enterprise computing environment. The extraction of information from data such as images has many important applications, e.g., in medicine. The ideal coverage of an area with mobile sensors in order to gather data can be indispensible for, e.g., disaster recovery operations. This section covers four chapters dealing with this line of real-world applications from diverse fields.
A common means to reduce cost in the civil construction industry is to stabilise soil by mixing lime, cement, asphalt or any combination of these chemicals into it. The resulting changes in soil features such as strength, porosity, and permeability can then ease road constructions and foundation. In the chapter presented by Alavi et al., a Linear GP (LGP) approach is used to estimate the properties of stabilised soil. GP evolves program-like structures, and its linear version represents programs as a sequential list of instructions. Alavi et al. apply LGP in its original (purely evolutionary) version as well as a version hybridised with Simulated Annealing. Their experimental studies confirm that the accuracy of the proposed approach is satisfactory. The next chapter by Bilotta et al. discusses the segmentation of MRI images for (multiple sclerosis) lesion detection and lesion tissue volume estimation. In their work, Bilotta et al. present an innovative approach based on Cellular Neural Networks (CNNs), which they synthesise with a GA. This way, CNNs can be generated for both 2D and 3D lesion detection, which provides new perspectives for diagnostics and is a stark improvement compared to the currently used manual lesion delineation approach. Databases are among the most important elements of all enterprise software architectures. Most of them can be queried by using Structured Query Language (SQL). Skyline extends SQL by allowing queries for trade-off curves concerning two or more attributes over datasets, similar to Pareto frontiers. Before executing such a query, it is typically optimised via equivalence transformations for the purpose of minimising its runtime. In the penultimate chapter of this section (also of this book), Goncalves et al. introduce an alternative approach for Skyline Query Optimisation based on an EA. They show that the variants of their proposed approach are able to outperform the commonly-used dynamic programming, especially as the number of tables increases.
Distributing the nodes of Mobile Ad-hoc Networks (MANETs) as uniformly as possible over a given terrain is an important problem across a variety of real-world applications, ranging from those for civil to military purposes. The final chapter by Sahin et al. shows how a Force-based GA (FGA) can provide the node executing it with movement instructions which accomplish this objective. Here, one instance of the FGA is executed on each node of the MANET, and only local knowledge obtained from within the limited sensor and communication range of a node is utilised. The simulation experiments confirm that the FGA can be an effective mechanism for deploying mobile nodes with restrained communication capabilities in MANETs operating in unknown areas. To sum up, we would like to extend our gratitude to all the authors for their excellent contributions to this book. We also wish to thank all the reviewers involved in the review process for their constructive and useful review comments. Without their help, this book project could not have been satisfactorily completed. A special note of thanks goes to Dr. Thomas Ditzinger (Engineering Senior Editor, Springer-Verlag) and Ms Heather King (Engineering Editorial, Springer-Verlag) for their editorial assistance and professional support. Finally, we hope that readers would enjoy reading this book as much as we have enjoyed putting it together!
June 2011 Raymond Chiong
Thomas Weise
Zbigniew Michalewicz

Keywords

Evolutionary Algorithms, EAs, Real-World Problems

BibTeX

@misc{CWM2011VOEAFRWAP,
  author                    = {Raymond Chiong and Thomas Weise and Zbigniew Michalewicz},
  title                     = {{Variants of Evolutionary Algorithms for Real-World Applications {--} Preface}},
  booktitle                 = {Variants of Evolutionary Algorithms for Real-World Applications},
  editor                    = {Raymond Chiong and Thomas Weise and Zbigniew Michalewicz},
  publisher                 = {{Springer-Verlag: {Berlin/Heidelberg}}},
  pages                     = {I--XIV},
  year                      = {2011},
  key                       = {CWM2011VOEAFRWAP},
},

Links