Advances in Swarm Intelligence for Optimizing Problems in Computer Science

Anand Nayyar, Dac-Nhuong Le, Nhu Gia Nguyen

• Publisher: Chapman and Hall/CRC
• Year: 2018
• ISBN:
  9780429820151
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming Games
• Index: Computer Science

This book provides comprehensive details of all Swarm Intelligence based Techniques available till date in a comprehensive manner along with their mathematical proofs. It will act as a foundation for authors, researchers and industry professionals. This monograph will present the latest state of the art research being done on varied Intelligent Technologies like sensor networks, machine learning, optical fiber communications, digital signal processing, image processing and many more.

1

Evolutionary Computation

Theory and Algorithms

Anand Nayyar, Surbhi Garg, Deepak Gupta and Ashish Khanna

CONTENTS

1.1 History of Evolutionary Computation

1.2 Motivation via Biological Evidence

1.2.1 Darwinian Evolution

1.2.2 Genetics

1.3 Why Evolutionary Computing?

1.4 Concept of Evolutionary Algorithms

1.5 Components of Evolutionary Algorithms

1.5.1 Representation

1.5.2 Fitness Function

1.5.3 Parents’ Selection

1.5.4 Population

1.5.5 Crossover Operators or Recombination Operators

1.5.6 Mutation Operators

1.5.7 Survivor Selection

1.5.8 Termination Condition

1.6 Working of Evolutionary Algorithms

1.7 Evolutionary Computation Techniques and Paradigms

1.7.1 Genetic Algorithms

1.7.2 Evolution Strategies

1.7.3 Evolutionary Programming

1.7.4 Genetic Programming

1.7.5 Swarm Intelligence

1.8 Applications of Evolutionary Computing

1.8.1 Problems in Distributed and Connected Networks, Internetworks, and Intranetworks

1.8.2 Interaction with Complex Systems

1.8.3 Finance and Economics

1.8.4 Computational Intelligence for Games

1.8.5 Electronic Sign Automation

1.8.6 Image Analysis and Signal Processing

1.8.7 Art, Music, Architecture, and Design

1.8.8 Search and Optimization in Transportation and Logistics

1.9 Conclusion

1.1 History of Evolutionary Computation

As said earlier, history is always accountable for the present or the current developments. Hence, this necessitates us knowing and appreciating the precious contributions of the researchers from the past in the field of evolutionary computation. Evolutionary computation is a thrilling field of computer science that focuses on Darwin’s principle of natural selection for building, studying, and implementing algorithms to solve various research problems. The concept of implementing the Darwin Principle to solve automated problems evolved from the late 1940s, way before the succession of computers (Fogel, 1998). Darwin’s theory states ‘the fittest individuals reproduce and survive’. In year 1948, ‘genetic and evolutionary search’ was initiated by Turing in his PhD thesis, where he developed the concept of an automatic machine, presently known as ‘Turing Machine’, which was then an unorganized machine to execute certain experiments that later gained popularity as the ‘Genetic Algorithm.’ It was practically executed as computer experiments on ‘optimization through evolution and recombination’ by Bremermann in 1962. Apart from this, three variations of this basic idea were proposed during the 1960s. Fogel, Owens, and Walsh further extended it toward evolutionary programing and named it genetic algorithms (De Jong, 1975; Holland, 1973) in Holland, whereas Rechenberg and Schwefel contributed the invention of evolutionary strategies (Rechenberg, 1973; Schwefel, 1995) in Germany. These areas evolved separately for a period of 15 years in their respective countries until the early 1990s, after which they all together were named evolutionary computation (EC) (Bäck, 1996; Bäck, Fogel, & Michalewicz, 2000). In the early 1990s the genetic programing concept came up as a fourth stream, following the general ideas upheld by Koza (Banzhaf, Nordin, Keller, & Francone, 1998; Koza, 1992). The scientific forums declared EC to keep a record of the past as well as future events conducted. The International Conference on Genetic Algorithms (ICGA) was first conducted in 1985 and was repeated every second year until 1997; it merged with the annual Conference on Genetic Programming in 1999 and was renamed the Genetic and Evolutionary Computation Conference (GECCO). The Annual Conference on Evolutionary Programming (EP), which has been held since 1992, merged with the IEEE Congress of Evolutionary Computation (CEC) conference, held annually since 1994. The first European event to address all the streams, named Parallel Problem Solving from Nature (PPSN), was held in 1990. Evolutionary Computing, said to be the first scientific journal, launched in 1993. In 1997, the European Commission implemented the European Research Network in Evolutionary Computing, named it EVONET, and funded it until 2003. Three major conferences, CEC, GECCO, PPSN, and many small conferences were held dedicated to theoretical analysis and development. The Foundation of Genetic Algorithms has existed since 1990 along with EVONET, the annual conference. Roughly over 2000 evolutionary computation publications were done by 2014, which includes journals as well as conference proceedings related to specific applications.

1.2 Motivation via Biological Evidence

The Darwinian theory of evolution and insight into genetics together explain the dynamics behind the emergence of life on Earth. This section covers Darwin’s theory of survival of the fittest and genetics in detail.

1.2.1 Darwinian Evolution

The origins of biological diversification and its underlying mechanisms have been well captured by Darwin’s theory of evolution (Darwin, 1859). The underlying principle states that natural selection is always positive toward the individual that challenges others to acquire a given resource most effectively. That is, who adapts best to the given environment. This phenomenon is widely known as survival of the fittest. The theory follows the concept of ‘The excellent will flourish, and the rest will perish’. Competition-based solution is the pillar on which evolutionary computation rests. The other primary force identified by Darwin is the phenotypic variations among the members of the population, which includes the behaviour and physical features of the individual that act as the force behind its reaction to the environment. Each individual contains a phenotypic trait that occurs in unique combinations, evaluated by environment. The individual has a higher chance of creating offspring if the combination provides favorable values; otherwise, it suffers rejection without producing any offspring. Moreover, inheritable favorable phenotypic traits might propagate from the individual through its offspring. Darwin’s insight includes random variation, or mutation, in phenotypic traits taking place from one generation to the next, which gives birth to new combinations of traits. Here, the best one survives for further reproduction, contributing to the process of evolution.

This process described in Darwin’s theory is captured in the adaptive landscape, called the ‘adaptive surface’ (Wright, 1932). The surface has a height dimension corresponding to the fitness, where high altitude shows high fitness. The other two or more dimensions correspond to the biological traits, where the x-y plane shows all combinations of traits possible, and z values correspond to the fitness. Each of the peak signifies the possible combination of traits. Hence, evolution can be considered as the gradual advance of the population to the high-altitude areas influenced by factors like variation and natural selection.

Our acquaintance with physical landscape takes us toward the concept of multimodal problems, where there are a number of points that are better in comparison to the existing neighbouring solutions. All these points are called as local optimal, whereas the highest point among them is the global optimum. Unimodal is the name given to a problem with a single local optimum. The population being a set, with random choices being made at selection, and variation operators, gives rise to genetic drift, whereby highly fit individuals may be lost, followed by loss in verity. This phenomenon is termed a ‘meltdown’ of the hill, entering the low-fitness valleys.

The combined effects of the drift and selection enable the population to move uphill as well as downhill.

1.2.2 Genetics

Molecular genetics provides a microscopic view of a natural evolution. It crosses the general visible phenotypic features, going deeper in the process. The key observation in genetics is the individual being a dual entity. The external feature is phenotypic properties, which are constructed at the level, i.e., internal construction. Genes here may be considered as the functional units of inheritance, encoding the phenotypic characters, i.e., the external factors visible, e.g., fur colour, trail length, etc. Genes may hold many properties from the possible alleles. An allele is one of the possible values a gene can have. Hence, an allele can be said to have a value that a variable can have mathematically. In a natural system, a single gene may affect many phenotypic traits, which is called pleiotropy. In turn, one phenotypic trait can be determined to be the result of a combination of many genes, termed ‘polygene.’ Hence, biologically the phenotypic variations are connected to the genotypic variations, which are actually an outcome of gene mutation, or the recombination of genes by sexual reproduction.

A genotype in general consists of all information required to build a specific phenotype. The genome contains the complete genetic information of any living organism with its total building plan. All the genes of an organism are arranged in several chromosomes. The human body contains 46 chromosomes; the other higher life forms like plants and animals also contain double complemented chromosomes in their cells. These cells are called diploid. The chromosomes in human diploid cells are organized into 23 chromosomal pairs. The gametes (i.e., sperm or egg cell) are haploid, containing only a single complement of a chromosome. The haploid sperm cell merges with egg cell, forming a diploid cell or a zygote. Within a zygote, the chromosome pair is formed out of the paternal and the maternal half. The new organism formed by the zygote is called as the ontogenesis and keeps intact the genetic information of the cell.

The combination of specific traits from two individuals into an offspring is called a crossover, which occurs during the process of meiosis.

As we know, all living organisms are based upon DNA, which is structurally composed of double helix of nucleotides encoding the characteristics of a whole organism. The triplets of nucleotides are called codons, each of which codes for a specific amino acid. Genes can be described as larger structures based upon DNA, containing many codons, carrying the codes of protein. The transformation of DNA to protein consists of two main steps: transcription, where...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• Editors
• Contributors
• 1. Evolutionary Computation Theory and Algorithms
• 2. Genetic Algorithms
• 3. Introduction to Swarm Intelligence
• 4. Ant Colony Optimization
• 5. Particle Swarm Optimization
• 6. Artificial Bee Colony, Firefly Swarm Optimization, and Bat Algorithms
• 7. Cuckoo Search Algorithm, Glowworm Algorithm, WASP, and Fish Swarm Optimization
• 8. Misc. Swarm Intelligence Techniques
• 9. Swarm Intelligence Techniques for Optimizing Problems
• Index