Genetic Algorithms and Machine Learning




Prof. (Dr.) Hardeep S Rai

Guru Nanak Dev Engg College, Ludhiana

GA in action

Let us start with an interesting demo. See how car's design is being evolved generation over generation, using Genetic Algorithm:

To come back to this page, after seeing demo (from link below), you may use

Alt-[LeftArrow]

Car Design with GA

Machine Learning (ML)

a sub-field of AI

  • Web search

  • Face recongnition

  • e-mail filtering

  • so what is ML?

What is machine Learning?

  • It makes computers to learn without being explicitly programmed.

Machine Learning

  • It is buzz word now a day!

  • Is it a new word?

  • What do you think?

  • How old is this term?

  • Any guess?

Machine Learning

Term coined in 1959.

  • by Arthur Lee Samuel

  • Samuel Checkers-playing Program

  • among the world's first successful self-learning programs

  • senior member in the TeX community

Andrew Ng

  • Andrew Yan-Tak Ng is a Chinese American computer scientist.

  • Was chief scientist at Baidu

  • is adjunct professor at Stanford University.

  • Co-founder and chairman of Coursera.

Andrew Ng

  • Was Director of the Stanford Artificial Intelligence Lab.

  • Taught and undertook research related to data mining and machine learning.

Andrew Ng

  • Worked at Google (2011-12), founded and led the Google Brain Deep Learning Project.

  • Offered free online courses for everyone after over 1 Lac students registered for course on "Machine Learning. Today, several million people have taken the course.

Andrew Ng

  • At Baidu, carried out research related to big data and A.I.

  • Launched Deeplearning.ai, an online curriculum of classes.

  • Launched Landing.ai, bringing AI to manufacturing factories.

Andrew Ng

  • In 2018, Ng unveiled the AI Fund, raising $175 million to invest in new startups.

  • Chairman of Woebot and on the board of drive.ai.

Andrew Ng

  • Stanford Autonomous Helicopter project, which developed one of the most capable autonomous helicopters in the world

  • STAIR (STanford Artificial Intelligence Robot) project, which resulted in ROS, a widely used open-source robotics software platform.

Andrew Ng

  • Google Brain project, very large scale ANN

  • NN trained using deep learning on 16k CPU cores, learned to recognise higher-level concepts (cats) after watching only YouTube videos.

  • Currently used in the Android OS's speech recognition system.

GA in Machine Learning

In ML we create solutions by using data or examples. There are 2 ways to do this.

  1. Solution is constructed from the data (Decision tree induction by ID3 (Iterative Dichotomiser3) and nearest-neighbour classification) or

GA in Machine Learning

  1. Some search method (gradient-descent algorithm).

GA in ML

  • GAs are stochastic search algorithms which are often used in ML applications.

  • This distinction might not be strict; ID3 (Iterative Dichotomiser3) might include a search over different prunings, for example.

GA in ML

  • Nonetheless, algorithms like ID3 are fast and computationally simple.

  • In addition, there is usually an explicit simplifying assumption about the nature of the solutions. For example, in ID3 the bias is towards independent attributes;

GA in ML

  • in nearest neighbour methods it is towards similarity of outputs being reflected in input similarity.

GA in ML

Using search, however, a wide range of complex potential solutions can be tested against the examples, and thus, much more difficult problems can be tackled. The cost, of course, is in increased computational cost.

GA in ML

In addition, any inductive bias is embedded in the algorithm and is thereby more difficult to control, although introducing explicit controls or regularisers is becoming increasingly important.

GA in ML

In many respects, genetic algorithms are on the dumb and uncontrolled end of machine learning methods. They rely least on information and assumptions, and most on blind search to find solutions. However, they have been seen to be very effective in a range of problems.

GA in ML

Genetic algorithms are important in machine learning for three reasons.

  1. Act on discrete spaces, where gradient-based methods can't be used. Can be used to search rule sets, neural network architectures, cellular automata computers, and so forth.

GA in ML

  1. Are essentially reinforcement learning algorithms. The performance of a learning system is determined by a single number, the fitness.

  2. GAs involve a population. Learning in multi-agent systems.

GA in ML

  • In artificial intelligence, search is used in reasoning as well as learning, and genetic algorithms are used in this context as well. To make the distinction clear, consider a chess-playing program. Machine learning could be used to acquire the competence of chess-playing.

GA in ML

  • (Most chess-playing programs are not created that way; they are programmed.) However, when the program plays the game it also uses search to find a good move. Other examples include searching over a set of rules to evaluate a predicate.

GA in ML

  • Genetic algorithms have been used for problems which have been in the domain of artificial intelligence, such as finding an effective timetable or schedule within a set of constraints.

John H. Holland

  • Professor of psychology

  • Professor of electrical engineering and computer science

  • @ University of Michigan, Ann Arbor.

  • Pioneer in GAs, Father of Genetic Algorithm

John H. Holland

  • Researched in "complex adaptive systems".

  • Ground-breaking book on GAs, "Adaptation in Natural and Artificial Systems" (1975).

  • Developed Holland's schema theorem.

John H. Holland

  • Hidden Order: How Adaptation Builds Complexity (1995)

  • Emergence: From Chaos to Order (1998)

John H. Holland

  • Signals and Boundaries: Building Blocks for Complex Adaptive Systems (2012)

  • Complexity: A Very Short Introduction (2014)

David E. Goldberg

  • Computer scientist, Civil engineer

  • Professor at the department of Industrial and Enterprise Systems Engineering (IESE) at the University of Illinois at Urbana-Champaign

  • Most noted for his work in the field of GAs.

David E. Goldberg

  • Director of the Illinois Genetic Algorithms Laboratory (IlliGAL)

  • Chief scientist of Nextumi Inc.

  • He is the author of Genetic Algorithms in Search, Optimization and Machine Learning, one of the most cited books in computer science.

Genetic Algorithms

are search algorithms based on the mechanics of natral selection and natural genetics

  • combine Darwinian survival of the fittest with innovative flair.

  • new set of creatures is generated using bits and pieces of the fittest of the old, an occasional new part is tried.

Genetic Algorithms

  • randomised, but !(random walk).

  • efficiently exploit historical information to speculate new search points with expected improved performance.

Genetic Algorithms

a simple simulation by hand.

For selection by roulette wheel, click here.


Spreadsheet discussed

GA Operation

The steps of applying GA are:

  1. Choose an encoding

  2. Choose a fitness funtion

GA Operation

  1. Choose operators

  2. Choose parameters

  3. Choose initialisation and stopping criteria

GA Operators

  1. Selection (biased roulette wheel, tournament selection, elitism selection)

  2. Crossover

  3. Mutation

Implementation

  • it is an art and need experimentation and experience

  • Thank you!