Transcript Introduction To Learnable Evolution Model

Advisor: Dr. Mirzaei
MohammadTaghi Moein
Isfahan University of Technology
The Scheme of Evolution Model
New
Individuals
Current
Population
New
Population
Generating New Individuals in
Darwinian-Type Evolution Model
Current
Population
Candidate
Parents
Generate New
Individuals by
mutation and
recombination
Generating New Individuals in
LEM
H-group
High
Performance
Individuals
Generate
hypothesis for
H-group
Generate New
Individuals by
Instantiating
the hypothesis
Current
Population
L-group
Low
Performance
Individuals
Generate
hypothesis for
L-group
Extrema Generation
 fitness-based
 according to two thresholds, called HFT and LFT
Extrema Generation Cont.
 population-based
 according to two parameters, called HPT and LPT
Extrema Generation Cont.
 The fitness-based and population-based methods can also be used in
combination.
 a global approach applies one of the above methods to the entire
population.
 a local approach applies one of the above methods in parallel to
different subsets of the population.
 The above methods can be enhanced by employing elitism.
Extrema Generation Cont.
 In the above methods, the H-group and L-group were
selected only from the current population.
 H-group description that does not take into consideration
past L-groups is likely to be too general.
 L-group description that does not take into consideration
past L-groups is likely to be too specific.
Considering History of Evolution
 Population-lookback
 union of the past L-groups plus the L-group in the current
population is the actual L-group.
 The number of past L-groups is specified by the p-lookback
parameter.
 High-group description-lookback
 current H-group description is used to generate new candidate
individuals.
 past H-group descriptions serve as preconditions for accepting a
candidate.
 The number of H-group descriptions is specified by the dlookback parameter.
Considering History of Evolution
Cont.
 Low-group description-lookback
 maintains a collection of descriptions of L-groups.
 uses them as constraints when generating H-group
descriptions.
 Incremental specialization
 uses incremental learning algorithm to maintain one updated
description of the H-group.
 input to such an algorithm is a description of the previous
H-group.
Generating Description(AQ)
Seed Selection
Star Generation
Rule Selection
Coverage Update
any
positive
example
Finish
No
Yes
Description instantiation
 New individuals should satisfy all H-group descriptions.
 A description instantiation is done by assigning different
combinations of values to variables in the rules of a ruleset.
 Each assignment must satisfy all conditions in at least one
of the rules.
LEM Algorithm
1. Generate a population
2. Execute machine learning mode
a) Derive extrema
b) Create a hypothsis
c) Generate new individuals
d) Go to step (2-a) and continue until termination condition is
met, if termination condition is met do:
i.
ii.
iii.
If the LEM termination condition is met , end the evolution.
Repeate the process from step 1, this is called start-over .
Go to step 3
LEM Algorithm Cont.
3. Execute Darvinian Evolution mode
4. Alternate: Go to step 2, and continue alternating between
step 2 and step 3 until the LEM termination condition is
met.
Generating start-over population
A. Select-elite
B. Avoid-past-failures
C. Use-recommendatoins
D. Generate-a-variant
Any Questions?
Thanks for your attention