Monthly Newsletter | 3rd October 2016

IN THIS ISSUE

  • Current Article
  • News
  • Quote
  • Previous Issue
  • Facebook Posts
  • Contact us
Write to Us at contactus@aimumbai.org

Genetic Algorithms: An Introduction With Example

1. Concept of “Evolution”:
Do you know how old the earth is? Well, the earth is about 4.54 billion years old and the first life dates to at least 3.5 billion years ago. The first primates did not appear until around 50-55 million years ago. That was 10-15 million years after the dinosaurs had become extinct. Take a moment to remember our ancestors - the monkeys. Can you imagine them being able to operate a computer or a smartphone ? or play chess ? or read like us humans ? or prepare a cup of coffee ? or drive a car ? (which may be true in a crazy scene of an Indian movie. If you know which movie I am talking about :P). Let me add wings to your imagination with the help of Figure 1:


Figure 1

Ok, too much, is it ? Let me stop now and get to the point. We are talking about a simple concept here called ‘Evolution’. We all have evolved from our ancestors. The ability of the ‘homo erectus’ to light fire was a turning point in the history of evolution that helped him provide protection for himself from animals and also to cook food and to keep himself warm. So where did all this intelligence come from in an ape ? This is nothing but biological intelligence. It comes when two fit parents combine together to form a better offspring. Consider for example, you put a mosquito repellent in your room. The mosquito may die the first time. But after a few months, you will find that the offspring is already immune to the repellent and is sitting on top of it ! This is, in lay man’s term - survival of the fittest. That is the magic of evolution.

2. Applications of the ‘Evolution’ concept in Engineering:
Reproduction involves combination of genes from two individuals. A gene is responsible for determining certain features of an individual, example eye colour. All these genes are contained within the chromosomes. The fitness of an organism is how much it can reproduce before it dies. Evolution based on ‘survival of the fittest’. Now why am I talking about these concepts ? It is because, there are a few search algorithms, called ‘Evolutionary Algorithms’ that are based on the concept of evolution. Basically, these search algorithms are inspired from naturally inspired biological phenomenon which is evolution. These are termed as evolutionary algorithms. Evolutionary algorithms are extremely accurate when it comes to solving optimization problems. It is basically a metaheuristic optimization technique. It mimics techniques that are inspired from naturally occurring biological evolution, for example, reproduction. There is a fitness function that decides the value of the so formed solutions. This helps it decide whether to accept the solution or to discard it. Evolutionary algorithm types include genetic algorithm, genetic programming, evolutionary programming, gene expression programming, evolution strategy, differential evolution, neuroevolution and learning classifier system.
Following are the classification of the search techniques based on evolution in Artificial Intelligence:


Figure 2

3. Genetic Algorithms:
One of the most important search algorithms today is the Genetic Algorithm (GA). GAs are popular tools that aid in finding an optimal solution. They are widely used recently to solve a wide variety of problems. They can be used in searching for the most optimal designs in robotics. They are also used in aeronautical problems involving parametric and conceptual design of aircraft, design of turbines, wings and also for aerodynamic optimization. Also, they are widely used in optimizing automotive design as well as engineering design. Researchers conclude that the GAs are a promise for the future to be a useful tool for optimization.

Genetic algorithms are very useful search algorithms because of the following reasons:

  • Avoids getting stuck in local optima. Local optima basically means the best or optimal value, but only within its neighbourhood. Meaning it does not search for the entire
  • It can search the entire search space in parallel
  • The time required for computation is also much lesser compared to other algorithms like Simulated Annealing or Ant Colony Optimization
  • It gives accurate and reliable results in a reasonably lesser time

4. Example with Simulation:
The following example was simulated in MATLAB 7.0. As an example, consider the following objective function which we need to minimize:

Minimize:
f (x) = -exp (-(x/20)2) ……………....for x<=20
           -exp (-1) + (x-20)/(x-22)........for x > 20

The Figure 3 shows a plot of the function:


Figure 3: Simulation in MATLAB 7.0

The function has two local minima, one at x = 0, where the function value is –1, and the other at x = 21, where the function value is (–1 – 1/e). Since the latter value is smaller, the global minimum occurs at x = 21.

The genetic algorithm returns a point very close to the local minimum at x = 0 after 51 iterations, as shown in Figure 4.


Figure 4: Simulation in MATLAB 7.0

The following custom plot shows why the algorithm finds the local minimum rather than the global minimum. The plot shows the range of individuals in each generation and the best individual.The following custom plot shows why the algorithm finds the local minimum rather than the global minimum. The plot shows the range of individuals in each generation and the best individual.


Figure 5: Simulation in MATLAB 7.0

Note that all individuals are between -2 and 2.5. While this range is larger than the default initial range of [0;1], due to mutation, it is not large enough to explore points near the global minimum at x = 21.

One way to make the genetic algorithm explore a wider range of points—that is, to increase the diversity of the populations—is to increase the Initial range. The initial range does not have to include the point x = 21, but it must be large enough so that the algorithm generates individuals near x = 21. So if you set initial range to [0;15] as shown in the following figure.


Figure 6: Simulation in MATLAB 7.0

Then click Start. The genetic algorithm returns a point very close to 21.


Figure 7: Simulation in MATLAB 7.0

This time, the custom plot shows a much wider range of individuals. By the second generation there are individuals greater than 21, and by generation 12, the algorithm finds a best individual that is approximately equal to 21. This shows that the GA does not get stuck in local optima.


Figure 8: Simulation in MATLAB 7.0

To summarize With the above example, we can conclude that:
The advantages of GA mentioned in section are absolutely true. From the example we find that:

  • It does not get stuck in local optima
  • It keeps searching for solution until global optima is found
  • The time required for performing this task is very less, about 20 seconds
  • It is a very reliable search algorithm

Figure 8: Simulation in MATLAB 7.0

References:
http://www.livescience.com/43875-human-chimpanzee-determination-face.html
http://www.encyclopedia.com/topic/human_evolution.aspx
http://www.relatably.com/q/evolution-quotes
https://in.mathworks.com/products/matlab/
http://in.mathworks.com/discovery/genetic-algorithm.html
https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications
https://en.wikipedia.org/wiki/Control_of_fire_by_early_humans

News

Orchestra music created with the help of artificial intelligence:
You wouldn’t think that articles on business and tech topics would make for the most beautiful music, but believe it or not, they were used by an artificial intelligence system and human composers to create an original symphony.
Google Image Captioning Artificial Intelligence System Has 94 Percent Accuracy:
Google has just released the latest version of its image captioning system as an open source model in TensorFlow. The new iteration is capable of providing image captions that are 93.9 percent accurate.
How artificial intelligence will transform your smartphone:
In the future there's no reason why Google Now couldn't use what it knows about you, how you use your phone, and past behaviour to work out when you're going to call home, or launch a maps app, or even take a photo (if you're near a famous landmark, say).
Quote

“The question of whether a computer can think is no more interesting than the question of whether a submarine can swim”

“Raise your quality standards as high as you can live with, avoid wasting your time on routine problems, and always try to work as closely as possible at the boundary of your abilities. Do this, because it is the only way of discovering how that boundary should be moved forward.”

― Edsger W. Dijkstra (A computer scientist. Receiver of the 1972 Turing Award for fundamental contributions to developing programming languages 1968 Paper written on : A Case against the GO TO Statement)

Previous Issues

Social Networking and Artificial Intelligence

Dated: 1 September 2016

A World of Chatbots

Dated: 1 August 2016

Spreading Awareness on the Importance of Technology Vision

Dated: 1 July 2016

While you were away
A.I. earbuds (#AIearbud), a very smart virtual assistant :
This A.I. will talk to us -- and we'll talk back. It will know everything about us, understand our current situation at all times and provide helpful guidance and information.
A World of Chatbots :
The major challenge for #AI (#ArtificialIntelligence) experts to cater to is create question answering systems. #Chatbots such as #Cortana will use this technology to give us a feeling that we are talking to a human. The ultimate test of such a bot will be to pass the Turing Test, which is the final frontier to prove that it has reached human intelligence
Sony has been working on using #AI for artistic work. It has now released two songs composed by an AI system build by its researchers. The results are amazing! :
Researchers at Sony have been working on AI-generated music for years, and has previously used AI to create impressive jazz tracks. But this is the first time the Sony CSL Research Laboratory has released pop music composed by AI, and the results are impressive.
Contact Us

Your reviews are valuable. Help us to improve.
Give your feedback on contactus@aimumbai.org
www.aimumbai.org

Address: 10, Jamanadas Industrial Estate, Phase -1, Dr. R.P. Road, Mulund (West),, Mumbai, Maharashtra 400080


© Copyright Artificial Intelligence Mumbai. All Rights Reserved.