Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    Transportation and Logistics Optimization

    Uploaded by

    mehdi
    Genetic algorithms are population-based search algorithms inspired by biological evolution. They use selection, crossover, and mutation operators to evolve solutions to optimization and search problems. A genetic algorithm first encodes potential solutions as chromosomes, then evaluates them and selects the fittest to undergo genetic operators to produce new offspring for the next generation. This process is repeated until an optimal solution is found.

    Copyright:

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

    Transportation and Logistics Optimization

    Uploaded by

    mehdi
    32 views17 pages
    Genetic algorithms are population-based search algorithms inspired by biological evolution. They use selection, crossover, and mutation operators to evolve solutions to optimization and search problems. A genetic algorithm first encodes potential solutions as chromosomes, then evaluates them and selects the fittest to undergo genetic operators to produce new offspring for the next generation. This process is repeated until an optimal solution is found.

    Original Title

    TLO8.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Genetic algorithms are population-based search algorithms inspired by biological evolution. They use selection, crossover, and mutation operators to evolve solutions to optimization and search problems. A genetic algorithm first encodes potential solutions as chromosomes, then evaluates them and selects the fittest to undergo genetic operators to produce new offspring for the next generation. This process is repeated until an optimal solution is found.

    Copyright:

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

    Transportation and Logistics Optimization

    Uploaded by

    mehdi
    Genetic algorithms are population-based search algorithms inspired by biological evolution. They use selection, crossover, and mutation operators to evolve solutions to optimization and search problems. A genetic algorithm first encodes potential solutions as chromosomes, then evaluates them and selects the fittest to undergo genetic operators to produce new offspring for the next generation. This process is repeated until an optimal 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 17

    Transportation and Logistics

    Optimization
    Genetic Algorithm (GA)
    Directed search algorithms based on the mechanics of
    biological evolution

    Developed by John Holland and David Goldberg (Late 70s


    ~Early 80s)

    Population-based approach

    Widely-used today in business, scientific and engineering


    fields

    See : Genetic Algorithms in Search, Optimization, and


    Machine Learning (1989) by David Goldberg

    Demo
    Terminology
    Chromosome
    Gene
    Parents
    Children
    Siblings
    Generation
    Components
    Encoding Scheme
    Fitness Function
    Genetic Operators
    Parameter Setting
    Encoding Scheme
    Bit strings (Binary encoding)
    e.g.) 1 1 0 0 1 1 1 1

    Real numbers
    e.g.) 1.2 5.3 0.4 2.3 5 3.1 06 7.2

    A B D J E D I B

    Permutations of element
    e.g.) 1 5 3 2 6 8 4 7

    Program elements
    ... any data structure ...
    Fitness Function
    Evaluate how good is each candidate
    chromosome.
    Find the fitness value
    ex) Obj. function value in Max problems
    Fitness
    Chromosome
    Value

    0 1 1 0 1 64
    1 1 0 0 0 361
    0 1 0 0 0 169
    1 0 0 1 1 576
    Genetic Operators
    Selection
    Crossover
    Mutation
    Substitution
    Selection
    Roulette Wheel Selection
    Chromosome Fitness % of total
    A 01000 64 5.5
    B 10011 361 30.9
    C 01101 169 14.4
    D 11000 576 49.2

    Tournament Selection
    Expected-value selection
    Ranking Selection
    Elite Preserving Method
    Crossover
    Single Point Crossover
    1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1

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

    Two Point Crossover


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

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

    Uniform Crossover
    Calculate crossover rate for every bit
    Arithmetic Crossover
    Use average value
    Mutation
    Change a bit
    1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1

    Causes movement in the search space


    (local or global)
    Restores lost information to the
    population
    Substitution
    Generational GA:
    Entire populations replaced with each
    iteration

    Steady-state GA:
    A few members replaced each generation

    Elitism
    Parameter Setting
    Population size
    How many chromosomes are in population
    Too few chromosome small part of search space
    Too many chromosome GA slow down
    Recommendation : 20-30, 50-100

    Probability of Crossover
    How often will be crossover performed
    Recommendation : 60% -90%

    Probability of Mutation
    How often will be parts of chromosome mutated
    Recommendation : 0.5% - 1%
    Hybrid Genetic Algorithm
    What is Hybrid GA?
    GA+ Local Search
    Find local optimal solution from a given chromosome
    Replace that chromosome with the local optimal solutions
    Key : How to find a local optimum?

    High accuracy in TSP or other Routing Problems

    GA Chromosomes

    New Chromosomes Local Search


    :Local Optima Process
    A Simple Example

    The Traveling Salesman Problem:

    Find a tour of a given set of cities so that


    each city is visited only once
    the total distance traveled is minimized
    Representation
    Representation is an ordered list of city
    numbers known as an order-based GA.
    1) London 3) Dunedin 5) Beijing 7) Tokyo
    2) Venice 4) Singapore 6) Phoenix 8) Victoria

    CityList1 (3 5 7 2 1 6 4 8)
    CityList2 (2 5 7 6 8 1 3 4)
    Crossover
    Order1 Crossover

    * *
    Parent1 (3 5 7 2 1 6 4 8)
    Parent2 (2 5 7 6 8 1 3 4)

    Child (5 8 7 2 1 6 3 4)
    Mutation
    Mutation involves reordering of the list:

    * *
    Before: (5 8 7 2 1 6 3 4)

    After: (5 8 6 2 1 7 3 4)

    You might also like