Historical Development of Evolutionary Computing (M1.1)

Evolutionary computation is an area of computer science that uses ideas from biological evolution to solve computational problems. 

In the 1950s and the 1960s, several computer scientists independently invented different evolutionary computation methods. 

In the 1960s, Rechenberg introduced evolution strategies, a method he used to optimize real-valued parameters for devices such as airfoils. 

A “population” consisted of two individuals, a parent and a child mutated from the parent—each encoding a set of real-valued parameters to be optimized. The fitter of the two was selected to be the parent for the next generation. Mutation consisted of incrementing or decrementing a real value according to a given distribution. The parameters of this distribution were themselves encoded as part of each individual and thus coevolved with the parameters to be optimized. This idea was further developed by Schwefel, and the theory and application of evolution strategies have remained an active area of research.

Fogel, Owens, & Walsh developed evolutionary programming, a technique in which candidate solutions to given tasks were represented as finite-state machines and were evolved by randomly mutating their state-transition diagrams and selecting the fittest. As in evolution strategies, a random mutation was the only source of variation. 

The techniques called genetic algorithms (GAs) were first invented by Holland in the 1960s. GAs are population-based algorithms in which mutation and crossover are sources of random variation. GAs typically worked on strings of bits rather than real-valued parameters. The simple GA given above is close to the algorithm proposed by Holland. Holland’s original proposal also included an “inversion” operator for the reordering of bits on a chromosome. 

In contrast with evolution strategies and evolutionary programming, Holland’s goal was not to design algorithms to solve specific problems, but rather to formally study the phenomenon of adaptation as it occurs in nature and to develop ways in which the mechanisms of natural adaptation might be imported into computer systems.

Several other people working in the 1950s and 1960s developed evolution-inspired algorithms for optimization and machine learning for discussions of this history.

In the last several years there has been widespread interaction among researchers studying various evolutionary computation methods, and the boundaries between evolution strategies, evolutionary programming, genetic algorithms, and other evolutionary computation methods have broken down to some extent.

First Generation 

• Evolutionary Programming (Fogel)

• Genetic Algorithm (Holland)

• Evolutionary Strategies (Rechenberg, Schwefel)

Second Generation

• Genetic Evolution of Data Structures (Michalewicz)

• Genetic Evolution of Programs (Koza)

• Hybrid Genetic Search (Davis)

• Tabu Search (Glover)

Third Generation EC

• Artificial Immune Systems (Forrest)

• Cultural Algorithms (Reynolds)

• DNA Computing (Adleman)

• Ant Colony Optimization (Dorigo)

• Particle Swarm Optimization (Kennedy & Eberhart)

• Memetic Algorithms

• Estimation of Distribution Algorithms

Evolutionary Computation (M1.2)

Evolutionary computation is an area of computer science that uses ideas from biological evolution to solve computational problems.

There are several approaches that have been followed in the field of evolutionary computation. The general term for such approaches is evolutionary algorithms. 

Genetic Algorithms (GA),

Evolutionary Strategies (ES)

Evolutionary Programming (EP)

Genetic Programming (GP)

Among this, The most widely used form of evolutionary algorithms are genetic algorithms (GAs),

Genetic algorithms (GAs), mainly operates on binary strings and uses a recombination operator with mutation as a background operator.

Evolution strategies (ESs) were developed as a method to solve parameter optimization problems.

Evolutionary programming (EP) techniques aimed at evolution of artificial intelligence, and finite state machines (FSM) were selected as a chromosomal representation of individuals.

Genetic programming (GP) techniques provide a way to run a search of the space of possible computer programs for the best one.

#Representing the different types of EAs

Historically different flavors of EAs have been associated with different representations,

Binary strings : Genetic Algorithms

Real-valued vectors : Evolution Strategies

Finite state Machines: Evolutionary Programming

LISP trees: Genetic Programming

Multiple business benefits are associated with evolutionary algorithms, including:

• Increased flexibility. Evolutionary algorithm concepts can be modified and adapted to solve the most complex problems humans face and meet target objectives.
• Better optimization. The vast “population” of all possible solutions is taken into consideration. This means the algorithm is not restricted to a particular solution.
• Unlimited solutions. Unlike classical methods that present and attempt to maintain a single best solution, evolutionary algorithms include and can present multiple potential solutions to a problem.
  

 

 Genetic Algorithms (GA)

• Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. 
• Genetic algorithms are a type of optimization algorithm, meaning they are used to find the optimal solution(s) to a given computational problem that maximizes or minimizes a particular function. 
• Genetic algorithms represent one branch of the field of study called evolutionary computation, in that they imitate the biological processes of reproduction and natural selection to solve for the ‘fittest’ solution.

The simplest version of a genetic algorithm consists of the following components:

#Population (Set Of Chromosomes)

 It is a subset of all the possible (encoded) solutions to the given problem.

• Chromosomes − A chromosome is one such solution to the given problem.

• Gene − A gene is one element position of a chromosome.

• Allele − It is the value a gene takes for a particular chromosome.

 

#Fitness function 

Assigns a numerical value to each chromosome in the population measuring its quality as a candidate solution to the problem at hand.

#Genetic operators 

• Operators to be applied to the chromosomes to create a new population.
• These typically include selection, in which the fittest chromosomes are chosen to produce offspring; 
• crossover, in which two parent chromosomes recombine their genes to produce one or more offspring chromosomes; and 
• mutation, in which one or more genes in an offspring are modified in some random fashion.

A typical GA carries out the following steps:

1. Initialize the  population of n chromosomes randomly.
2. Calculate the fitness f (x) of each chromosome x in the population.
3. Repeat the following steps until n offspring have been created:
4. Select a pair of parent chromosomes from the current population. 
5. Perform Crossover & Mutation (typically replaces the current value of a locus (eg: 0) with another value (eg: 1)).
6. Replace the current population with the new population.
7. Repeat steps from 2  until the criteria is achieved.

Each iteration of this process is called a generation. 

Evolutionary Strategies (ES)

• An evolution strategy (ES) is an optimization technique based on ideas of evolution. 
• The 'evolution strategy' optimization technique was created in the early 1960s and developed further in the 1970s and later by Ingo Rechenberg, Hans-Paul Schwefel and their co-workers. 
• Evolution strategies use natural problem-dependent representations, and primarily mutation and selection, as search operators.
•  In common with evolutionary algorithms, the operators are applied in a loop. 
• An iteration of the loop is called a generation. The sequence of generations is continued until a termination criterion is met.  

Evolutionary Programming (EP) 

• Evolutionary programming is one of the four major evolutionary algorithm paradigms. 
• It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve.
• It was first used by Lawrence J. Fogel in the US in 1960 in order to use simulated evolution as a learning process aiming to generate artificial intelligence. 
• Fogel used finite-state machines as predictors and evolved them. Currently evolutionary programming is a wide evolutionary computing dialect with no fixed structure or (representation), in contrast with some of the other dialects. It is becoming harder to distinguish from evolutionary strategies.
• Its main variation operator is mutation; members of the population are viewed as part of a specific species rather than members of the same species therefore each parent generates an offspring, using a survivor selection.

 

Genetic Programming (GP)

• Genetic programming is indeed a special type of genetic algorithm. The difference lies in their representations. Genetic programming adopts trees as genotypes to represent  programs or expressions. 
• The typical selection schemes of evolutionary algorithms can still be used as parent selection and survival selection in genetic programming. 
• The distinct features of genetic programming are their crossover and mutation operators. 
• For instance, swapping sub-trees between two trees and random generation of sub-trees.  

 GP can be used to discover a functional relationship between features in data (symbolic regression), to group data into categories (classification), and to assist in the design of electrical circuits, antennae, and quantum algorithms. GP is applied to software engineering through code synthesis, genetic improvement, automatic bug-fixing, and in developing game-playing strategies, … and more.

 

Advantages of EA

• Evolutionary algorithm optimizers are global optimization methods and scale well to higher dimensional problems. 
• They are robust with respect to noisy evaluation functions, and the handling of evaluation functions which do not yield a sensible result in given period of time is straightforward. 
• The algorithms can easily be adjusted to the problem at hand. 
• Almost any aspect of the algorithm may be changed and customized.
  

• EA can be efficiently used for highly complex problems with multi-objectivity, non-linearity etc  
• Provides not only a single best solution, but the 2 nd best, 3 rd best and so on as required.
•  Gives quick approximate solutions.
•  Can incorporate with other local search algorithms

Disadvantages

On the other hand, although lots of research has been done on which evolutionary algorithm is best suited for a given problem, this question has not been answered satisfactorily. While the standard values usually provide reasonably good performance, different configurations may give better results. Furthermore, premature convergence to a local extremum may result from adverse configuration and not yield (a point near) the global extremum. 

• Optimal solution cannot be ensured on using EA methods 
• Convergence of EA techniques are problem oriented  
• Sensitivity analysis should be carried out to find out the range in which the model is efficient   
• Implementation requires good programming skill
  

Applications of EA

• Clustering, using genetic algorithms to optimize a wide range of different fit-functions.
• Multidimensional systems.
• Multimodal Optimization.
• Multiple criteria production scheduling.
• Multiple population topologies and interchange methodologies.
• Mutation testing

 

 

Operating Systems- Introduction

 An Operating System (OS) is a system software that acts as an interface between computer hardware components and the user. 

Every computer system must have at least one operating system to run other programs. Applications like Browsers, MS Office, Notepad Games, etc., need some environment to run and perform its tasks. 

The OS helps you to communicate with the computer without knowing how to speak the computer's language.

Software is a collection or set of instructions and data (tested programs & documentation) that tell a computer how to work and to execute a specific task. The two main categories of software are application software and system software.

* application software: performs a specific task. example: media player, word processors, software development tools, image editor etc..

* system software: manages computer hardware, provide basic functionalities that are required by users, or for other software to run properly. System software is also designed for providing a platform for running application software. Example: OS, firmware, translators, system utilities.

 

Functions of Operating System

 

h-index, i10 index, Impact Factor

 h-index

• The h-index is an author-level metric that measures both the productivity(no. of papers) and citation impact( no. of times cited) of the publications of a scientist or scholar to provide “an estimate of the importance, significance, and broad impact of a scientist’s cumulative research contributions.

   

  A tool to measure an author's productivity and impact of published work. 

The h-index is defined as the maximum value of h such that the given author/journal has published h papers that have each been cited at least h times.

• Proposed by Jorge E. Hirsch in 2005

• Calculation is based on the researcher's most cited papers and the number of citations that they have received (were these two numbers meet)

   

  Example: If a researcher has 15 papers, each of which has at least 15 citations, their h-index is 15. 

   

Useful For

• Comparing researchers of similar career length.
   
• Comparing researchers in a similar field, subject, or Department, and who publish in the same journal categories.
   
• Obtaining a focused snapshot of a researcher’s performance.

Advantage of h-index

• Evaluates both qualitatively (impact factor or citations) and quantitatively (number of articles) and does not have the disadvantages of other ranking indices such as counting the total number of articles or the total number of citations.
• The Hirsch index provides a strong evaluation of the impact of a researcher’s scientific articles, meaning that it ignores low-citation or no-citation articles, or high-citation articles in computation.
• This index can be a good benchmark for evaluating researchers who have had a significant impact on scientific participation but their scientific work has not been given the opportunity using conventional scientometric channels.
• The data needed for computation of this index is easily accessible through the ISI, Scopus, and Google Scholar databases without the need for any information processing.

Disadvantages

• The number of authors of an article and the contribution each has to the research is not determined by this index.

• If a researcher has a limited number of papers but they are highly cited, the H-index will not be high

• A researcher can cite his or her previous research many times (self-citation) and this can influence his or her H-index and lead to a false result.

   

  i10 index

  Created by Google Scholar and used in Google's My Citations feature. 

  i10-Index = the number of publications with at least 10 citations.  

  This very simple measure is only used by Google Scholar, and is another way to help gauge the productivity of a scholar.  

  Advantages 

• Very simple and straightforward to calculate

• My Citations in Google Scholar is free and easy to use

Disadvantages 

Used only in Google Scholar

Impact factor (IF) 

Impact factor (IF) is a measure of the number of times an average paper in a journal is cited, during a year. Clarivate Analytics releases the Journal Impact Factors annually as part of the Web of Science Journal Citation Reports®. Only journals listed in the Science Citation Index Expanded® (SCIE) and Social Sciences Citation Index® (SSCI) receive an Impact Factor.

Impact Factors are used to measure the importance of a journal by calculating the number of times selected articles are cited within a particular year. Hence, the higher the number of citations or articles coming from a particular journal or, impact factor or,  the higher it is ranked.

IF is also a powerful tool if you want to compare journals in the subject category.

 How Impact Factor is Calculated?

The calculation is based on a two-year period and involves dividing the number of times articles were cited by the number of articles that are citable.

The Impact Factor is reported in Journal Citation Reports (JCR)

CiteScore, which is similar to the IF but is based on a 4-year period.

Measuring a Journal Impact Factor:

• Use journal metrics to understand the impact of a journal:
  • CiteScore metrics – helps to measure journal citation impact. Free, comprehensive, transparent and current metrics calculated using data from Scopus®, the largest abstract and citation database of peer-reviewed literature.
  • SJR – or SCImago Journal Rank, is based on the concept of a transfer of prestige between journals via their citation links.
  • SNIP – or Source Normalized Impact per Paper, is a sophisticated metric that accounts for field-specific differences in citation practices.
  • JIF – or Journal Impact Factor is calculated by Clarivate Analytics as the average of the sum of the citations received in a given year to a journal’s previous two years of publications, divided by the sum of “citable” publications in the previous two years.
  • H-index – Although originally conceived as an author-level metric, the H-index has been being applied to higher-order aggregations of research publications, including journals.

Binary Search Tree (M1.3)

A binary search tree is a organized data structure that quickly allows us to maintain a sorted list of numbers.

• It is called a binary tree because each tree node has a maximum of two children.
• It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. 
•  The search tree data structure supports many dynamic-set operations, including SEARCH, MINIMUM, MAXIMUM , PREDECESSOR , SUCCESSOR , INSERT , and DELETE . Thus, we can use a search tree both as a dictionary and as a priority queue.
• In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively.
• The keys in a binary search tree are always stored in such a way as to satisfy the
  binary-search-tree property: 
  

 

The properties that separate a binary search tree from a regular binary tree is.

 

1. All nodes of the left sub-tree are less than the root node
2. All nodes of the right sub-tree are more than the root node
3. Both sub-trees of each node are also BST's i.e. they have the above two properties.

The binary-search-tree property allows us to print out all the keys in a binary
search tree in sorted order by a simple recursive algorithm, called an inorder tree
walk. (Similarly, a preorder tree walk prints the root before the values in either subtree,
and a postorder tree walk prints the root after the values in its subtrees.)

 

 

Advantages of using a BST

 

1. Searching become very efficient in a binary search tree since, we get a hint at each step, about which sub-tree contains the desired element.
2. The binary search tree is considered an efficient data structure in comparison to arrays and linked lists. In the searching process, it removes half sub-tree at every step. Searching for an element in a binary search tree takes o(log2n) time. In the worst case, the time it takes to search an element is 0(n).
3. It also speeds up the insertion and deletion operations as compared to that in the array and linked list. 

 

 Disadvantages

 

1. The degree of the tree will always increase, resulting in low efficiency of search.

 

Quick Recap