Scribd Logo
Upload

Welcome to Scribd!

  • 35 views

    Chapter 4 - Genetic Algorithms

    Uploaded by

    Gia Khang Tạ
    The document discusses genetic algorithms, which are a type of machine learning algorithm inspired by Darwin's theory of evolution. A genetic algorithm uses operations like selection, crossover and mutation to evolve a population of potential solutions to a problem over many generations. It works by initializing a population of random solutions, evaluating their fitness, and creating new solutions by breeding and mutating the existing ones, keeping the best ones to form the next generation. This process is repeated until a satisfactory solution is found.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Chapter 4 - Genetic Algorithms

    Uploaded by

    Gia Khang Tạ
    35 views22 pages
    The document discusses genetic algorithms, which are a type of machine learning algorithm inspired by Darwin's theory of evolution. A genetic algorithm uses operations like selection, crossover and mutation to evolve a population of potential solutions to a problem over many generations. It works by initializing a population of random solutions, evaluating their fitness, and creating new solutions by breeding and mutating the existing ones, keeping the best ones to form the next generation. This process is repeated until a satisfactory solution is found.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses genetic algorithms, which are a type of machine learning algorithm inspired by Darwin's theory of evolution. A genetic algorithm uses operations like selection, crossover and mutation to evolve a population of potential solutions to a problem over many generations. It works by initializing a population of random solutions, evaluating their fitness, and creating new solutions by breeding and mutating the existing ones, keeping the best ones to form the next generation. This process is repeated until a satisfactory solution is found.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    35 views22 pages

    Chapter 4 - Genetic Algorithms

    Uploaded by

    Gia Khang Tạ
    The document discusses genetic algorithms, which are a type of machine learning algorithm inspired by Darwin's theory of evolution. A genetic algorithm uses operations like selection, crossover and mutation to evolve a population of potential solutions to a problem over many generations. It works by initializing a population of random solutions, evaluating their fitness, and creating new solutions by breeding and mutating the existing ones, keeping the best ones to form the next generation. This process is repeated until a satisfactory solution is found.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 22

    Machine Learning

    Genetic Algorithm

    Lecturer: Duc Dung Nguyen, PhD.


    Contact: nddung@hcmut.edu.vn

    Faculty of Computer Science and Engineering


    Hochiminh city University of Technology
    Contents

    A genetic algorithm is a search heuristic that is


    1. Introduction
    inspired by Charles Darwin's theory of natural
    evolution. This algorithm reflects the process of
    2. Genetic Algorithm natural selection where the fittest individuals
    are selected for reproduction in order to produce
    offspring of the next generation.

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 1 / 19


    Introduction
    Motivation

    • Evolution is known to be a successful, robust method of nature


    • How do we search the space of hypotheses containing complex interacting parts, where
    the impact of each part on overall hypothesis is hard to model.
    • Computer programs are evolved to certain fitness criteria.
    • Evolutionary computation = Genetic algorithms + genetic programming

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 2 / 19


    Genetic Algorithm

    • Learning as searching
    • Analogy to biological evolution
    • The best hypothesis is searched through several generations of hypotheses.
    • Next generation hypotheses are produced by mutating and recombining parts of the best
    current generation hypotheses
    • It is not recommended to search from general-to-specific or from simple-to-complex
    hypotheses.

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 3 / 19


    Five phases are considered
    in a genetic algorithm.

    Genetic Algorithm 1.Initial population


    2.Fitness function
    3.Selection
    4.Crossover
    5.Mutation
    GA Overview

    Step 1: initial

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 4 / 19


    A Prototypical GA

    • Initialize population: P = randomly generated p hypotheses.


    • Evaluate fitness: compute F itness(h), for each h ∈ P Step 2: Fitness function
    • While maxh∈P F itness(h) < F itnessthreshold do:
    • Create new generation
    • Evaluate fitness

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 5 / 19


    New Generation Creation

    • Selection
    • Crossover
    • Mutation

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 6 / 19


    New Generation Creation

    Select:

    • Selection:

    Probabilistically select (1 − r)p hypotheses of P to add to the new generation.


    The selection probability of a hypothesis

    F itness(hi )
    P r(hi ) = P
    h∈P F itness(h)

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 7 / 19


    New Generation Creation

    • Crossover:
    • Probabilistically select (r/2)p pairs of hypotheses from P according to P r(h)
    • For each pair (h1 , h2 ), produce two offsprings by applying a Crossover operator.
    • Add all offspring to the new generation.

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 8 / 19


    New Generation Creation

    • Mutation:
    • Choose m percent of the added hypotheses with uniform distribution.
    • For each, invert one randomly selected bit in its representation.

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 9 / 19


    Hypotheses Representation

    • A classification rule as a bit string:

    If expr(A1 ) ∧ ... ∧ expr(Ai ∧ ... ∧ expr(An ) Then C = c

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 10 / 19


    Hypothesis Representation

    • Example:

    If W ind = Strong Then P layT ennis = Y es

    ⇓
    1 1 1 1 0 1 0

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 11 / 19


    Hypothesis Representation

    • A set of rules as concatenated bit strings:

    1 1 1 1 0 1 0 1 0 0 0 1 0 1

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 12 / 19


    Crossover Operator

    • Single-point
    • Two-point
    • Uniform

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 13 / 19


    Crossover Operator

    • Single-point

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 14 / 19


    Crossover Operator

    • Two-point

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 15 / 19


    Crossover Operator

    • Uniform

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 16 / 19


    Crossover Operator

    • Variable-length bit strings

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 17 / 19


    Fitness Function

    • Example:

    F itness(h) = (correct(h))2
    correct(h) = percent of all training examples correctly classified by hypothesis h

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 18 / 19


    Inductive bias?

    • What is inductive bias?


    • Where is inductive bias in GA?

    Lecturer: Duc Dung Nguyen, PhD. Contact: nddung@hcmut.edu.vn Machine Learning 19 / 19

    You might also like