Transcript Evolutionary Computation

Hybrid Soft Computing:
Where Are We Going?
Piero P. Bonissone
GE Corporate Research & Development
[email protected]
Hybrid SC and EA - Outline
• Soft Computing Overview
- SC Components: PR, FL, NN, EA
• Modeling with FL and EA
• Hybrid SC Systems
- FLC Parameter Tuning by EA
- EA Parameter Setting
• Conclusions
August 24, 2000
ECAI 2000
2
Hybrid SC and EA - Outline
• Soft Computing Overview
- SC Components: PR, FL, NN, EA
• Modeling with FL and EA
• Hybrid SC Systems
- FLC Parameter Tuning by EA
- EA Parameter Setting
• Conclusions
August 24, 2000
ECAI 2000
3
Soft Computing
• Soft Computing (SC): the symbiotic use of
many emerging problem-solving disciplines.
• According to Prof. Zadeh:
"...in contrast to traditional hard computing, soft computing
exploits the tolerance for imprecision, uncertainty, and
partial truth to achieve tractability, robustness, low
solution-cost, and better rapport with reality”
• Soft Computing Main Components:
-Approximate Reasoning:
» Probabilistic Reasoning, Fuzzy Logic
-Search & Optimization:
» Neural Networks, Evolutionary Algorithms
August 24, 2000
ECAI 2000
4
Problem Solving Techniques
HARD COMPUTING
SOFT COMPUTING
Precise Models
Approximate Models
Symbolic
Logic
Reasoning
August 24, 2000
Traditional
Numerical
Modeling and
Search
ECAI 2000
Approximate
Reasoning
Functional
Approximation
and Randomized
Search
5
Soft Computing: Hybrid Probabilistic Systems
Approximate
Reasoning
Probabilistic
Models
Multivalued &
Fuzzy Logics
Functional Approximation/
Randomized Search
Neural
Networks
Evolutionary
Algorithms
Bayesian
Belief Nets
DempsterShafer
August 24, 2000
ECAI 2000
6
Soft Computing: Hybrid Probabilistic Systems
Approximate
Reasoning
Probabilistic
Models
Multivalued &
Fuzzy Logics
Functional Approximation/
Randomized Search
Neural
Networks
Evolutionary
Algorithms
Bayesian
Belief Nets
DempsterShafer
HYBRID PROBABILISTIC SYSTEMS
Probability of
Fuzzy Events
August 24, 2000
Belief of
Fuzzy Events
ECAI 2000
Fuzzy Influence
Diagrams
7
Soft Computing: Hybrid Probabilistic Systems
Approximate
Reasoning
Probabilistic
Models
Multivalued &
Fuzzy Logics
Functional Approximation/
Randomized Search
Neural
Networks
Evolutionary
Algorithms
Bayesian
Belief Nets
DempsterShafer
HYBRID PROBABILISTIC SYSTEMS
Probability of
Fuzzy Events
August 24, 2000
Belief of
Fuzzy Events
ECAI 2000
Fuzzy Influence
Diagrams
8
Soft Computing: Hybrid Probabilistic Systems
Approximate
Reasoning
Probabilistic
Models
Multivalued &
Fuzzy Logics
Functional Approximation/
Randomized Search
Neural
Networks
Evolutionary
Algorithms
Bayesian
Belief Nets
DempsterShafer
HYBRID PROBABILISTIC SYSTEMS
Probability of
Fuzzy Events
August 24, 2000
Belief of
Fuzzy Events
ECAI 2000
Fuzzy Influence
Diagrams
9
Soft Computing: Hybrid FL Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Fuzzy
Systems
Neural
Networks
Evolutionary
Algorithms
Multivalued
Algebras
Fuzzy Logic
Controllers
August 24, 2000
ECAI 2000
10
Soft Computing: Hybrid FL Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Fuzzy
Systems
Neural
Networks
Evolutionary
Algorithms
Multivalued
Algebras
Fuzzy Logic
Controllers
HYBRID FL SYSTEMS
NN modified by FS
(Fuzzy Neural
Systems)
August 24, 2000
FLC Tuned by NN
(Neural Fuzzy
Systems)
ECAI 2000
FLC Generated
and Tuned by EA
11
Soft Computing: Hybrid FL Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Fuzzy
Systems
Neural
Networks
Evolutionary
Algorithms
Multivalued
Algebras
Fuzzy Logic
Controllers
HYBRID FL SYSTEMS
NN modified by FS
(Fuzzy Neural
Systems)
August 24, 2000
FLC Tuned by NN
(Neural Fuzzy
Systems)
ECAI 2000
FLC Generated
and Tuned by EA
12
Soft Computing: Hybrid FL Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Fuzzy
Systems
Neural
Networks
Evolutionary
Algorithms
Multivalued
Algebras
Fuzzy Logic
Controllers
HYBRID FL SYSTEMS
NN modified by FS
(Fuzzy Neural
Systems)
August 24, 2000
FLC Tuned by NN
(Neural Fuzzy
Systems)
ECAI 2000
FLC Generated
and Tuned by EA
13
Soft Computing: Hybrid NN Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
RBF
August 24, 2000
Neural
Networks
Feedforward
NN
Recurrent
NN
Single/Multiple
Layer Perceptron
Hopfield
ECAI 2000
Evolutionary
Algorithms
SOM
ART
14
Soft Computing: Hybrid NN Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
RBF
Neural
Networks
Feedforward
NN
Recurrent
NN
Single/Multiple
Layer Perceptron
Hopfield
HYBRID NN SYSTEMS
NN parameters
(learning rate h
momentum a )
controlled by FLC
August 24, 2000
ECAI 2000
Evolutionary
Algorithms
SOM
ART
NN topology &/or
weights
generated by EAs
15
Soft Computing: Hybrid NN Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
RBF
Neural
Networks
Feedforward
NN
Recurrent
NN
Single/Multiple
Layer Perceptron
Hopfield
HYBRID NN SYSTEMS
NN parameters
(learning rate h
momentum a )
controlled by FLC
August 24, 2000
ECAI 2000
Evolutionary
Algorithms
SOM
ART
NN topology &/or
weights
generated by EAs
16
Soft Computing: Hybrid EA Systems
Approximate
Reasoning
Probabilistic Multivalued &
Fuzzy Logics
Models
Functional Approximation/
Randomized Search
Neural
Networks
Evolution
Strategies
Evolutionary
Programs
August 24, 2000
ECAI 2000
Evolutionary
Algorithms
Genetic
Algorithms
Genetic
Progr.
17
Soft Computing: Hybrid EA Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Neural
Networks
Evolution
Strategies
Evolutionary
Programs
Evolutionary
Algorithms
Genetic
Algorithms
Genetic
Progr.
HYBRID EA SYSTEMS
EA parameters
(N, Pcr, Pmu )
controlled by FLC
August 24, 2000
EA-based search
inter-twined with
EA parameters
(Pop size, select.)
hill-climbing
controlled by EA
ECAI 2000
18
Soft Computing: Hybrid EA Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Neural
Networks
Evolution
Strategies
Evolutionary
Programs
Evolutionary
Algorithms
Genetic
Algorithms
Genetic
Progr.
HYBRID EA SYSTEMS
EA parameters
(N, Pcr, Pmu )
controlled by FLC
August 24, 2000
EA-based search
inter-twined with
EA parameters
(Pop size, select.)
hill-climbing
controlled by EA
ECAI 2000
19
Soft Computing: Hybrid EA Systems
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Neural
Networks
Evolution
Strategies
Evolutionary
Programs
Evolutionary
Algorithms
Genetic
Algorithms
Genetic
Progr.
HYBRID EA SYSTEMS
EA parameters
(N, Pcr, Pmu )
controlled by FLC
August 24, 2000
EA-based search
inter-twined with
EA parameters
(Pop size, select.)
hill-climbing
controlled by EA
ECAI 2000
20
Hybrid SC and EA – Outline (2)
• Soft Computing Overview
- SC Components: PR, FL, NN, EA
• Modeling with FL and EA
• Hybrid SC Systems
- FLC Parameter Tuning by EA
- EA Parameter Setting
• Conclusions
August 24, 2000
ECAI 2000
21
Fuzzy Logic Genealogy
• Origins: MVL for treatment of imprecision
and vagueness
- 1930s: Post, Kleene, and Lukasiewicz
attempted to represent undetermined,
unknown, and other possible intermediate
truth-values.
- 1937: Max Black suggested the use of a
consistency profile to represent vague
(ambiguous) concepts
- 1965: Zadeh proposed a complete theory of
fuzzy sets (and its isomorphic fuzzy logic), to
represent and manipulate ill-defined concepts
August 24, 2000
ECAI 2000
22
Fuzzy Logic : Linguistic Variables
• Fuzzy logic give us a language (with syntax and
local semantics), in which we can translate our
qualitative domain knowledge.
• Linguistic variables to model dynamic systems
• These variables take linguistic values that are
characterized by:
- a label - a sentence generated from the syntax
- a meaning - a membership function
determined by a local semantic procedure
August 24, 2000
ECAI 2000
23
Fuzzy Logic : Reasoning Methods
• The meaning of a linguistic variable may be
interpreted as a elastic constraint on its value.
• These constraints are propagated by fuzzy
inference operations, based on the generalized
modus-ponens.
• A FL Controller (FLC) applies this reasoning
system to a Knowledge Base (KB) containing the
problem domain heuristics.
• The inference is the result of interpolating
among the outputs of all relevant rules.
• The outcome is a membership distribution on
the output space, which is defuzzified to produce
a crisp output.
August 24, 2000
ECAI 2000
24
Fuzzy Logic Control : Inference Method
State Variables
Rules
Output Variable
S
S
LN
S
L
SN
L
S
SP
L
L
LP
Interpolation
Defuzzification
August 24, 2000
Inputs ECAI 2000
25
FLC Inference Method (cont.)
• A FLC (KB + Reasoning Mechanism)
defines a deterministic response
surface in the cross product of state
and output spaces, which
approximates the original relationship.
• The FLC leverages the interpolation
properties of this reasoning
mechanism, to exhibit robustness with
respect to parameter variations,
disturbances, etc.
August 24, 2000
ECAI 2000
26
Example (MISO): Max-min Composition
with Centroid Defuzzification
•If X is SMALL and Y is SMALL then Z is NEG. LARGE
Rules
set
•If X is SMALL and Y is LARGE the Z is NEG. SMALL
•If X is LARGE and Y is SMALL the Z is POS. SMALL
•If X is LARGE and Y is LARGE then Z is POS. LARGE
Response
Surface
Term
set
August 24, 2000
ECAI 2000
27
Evolutionary Algorithms (EA)
EA are part of the Derivative-Free Optimization
and Search Methods:
- Evolutionary Algorithms
- Simulated annealing (SA)
- Random search
- Downhill simplex search
- Tabu search
EA consists of:
- Evolution Strategies (ES)
- Evolutionary Programming (EP)
- Genetic Algorithms (GA)
- Genetic Programming (GP)
August 24, 2000
ECAI 2000
28
Evolutionary Algorithms
Characteristics
• Most Evolutionary Algorithms can be
described by
x[t + 1] = s(v(x[t]))
- x[t] : the population at time t under
representation x
- v : is the variation operator(s)
- s : is the selection operator
August 24, 2000
ECAI 2000
29
Evolutionary Algorithms
Characteristics
• EA exhibit an adaptive behavior that allows
them to handle non-linear, high dimensional
problems without requiring differentiability or
explicit knowledge of the problem structure.
• EA are very robust to time-varying behavior,
even though they may exhibit low speed of
convergence.
August 24, 2000
ECAI 2000
30
Modeling
• Model =
Structure + Parameters + Search Method
• Classical control theory:
- Structure: order of the differential equations
- Parameters: coefficients of differential
equation.
- Search method: LMSE, Pole-placement, etc.
August 24, 2000
ECAI 2000
31
Modeling Using FLC
(Mamdani type)
• A Mamdani- type FLC approximates a
relationship between a state X and an
output Y by using a KB and a reasoning
mechanism (generalized modus-ponens).
• The Knowledge Base (KB) is defined by:
- Scaling factors (SF): ranges of values of state
and output variables
- Termset (TS): membership functions of values
- Ruleset (RS): a syntactic mapping of symbols
from X to Y
August 24, 2000
ECAI 2000
32
Modeling Using FLC
(Mamdani type)
• The structure of the model is the ruleset.
• The parameters of the model are the
scaling factors and termsets.
• The search method is initialized by
knowledge engineering and refined with
some other external methods (SOFC,
error minimization, etc.)
August 24, 2000
ECAI 2000
33
Modeling Using EA
• Similarly, for EA:
- The structure of the model is the
representation of an individual in the
population (e.g., binary string, vector, parse
tree, Finite State Machine).
- The parameters of the model are the
Population Size, Probability of Mutation, Prob.
of Recombination, Generation Gap, etc.
- The search method is a global search based
on maximization of population fitness function
August 24, 2000
ECAI 2000
34
Hybrid SC and EA – Outline (3a)
• Soft Computing Overview
- SC Components: PR, FL, NN, EA
• Modeling with FL and EA
• Hybrid SC Systems
- FLC Parameter Tuning by EA
- EA Parameter Setting
• Conclusions
August 24, 2000
ECAI 2000
35
Hybrid Soft Computing: FLC Tuned by EAs
Approximate
Reasoning
Functional Approximation/
Randomized Search
Probabilistic Multivalued &
Fuzzy Logics
Models
Fuzzy
Systems
Fuzzy Logic
Controllers
Neural
Networks
Multivalued
Algebras
Evolution
Strategies
Evolutionary
Programs
Evolutionary
Algorithms
Genetic
Algorithms
Genetic
Progr.
HYBRID FLC/EA SYSTEMS
FLC Generated
and Tuned by EA
August 24, 2000
ECAI 2000
36
FLC Tuned by EA - Outline
• Components & Historical Approaches
• Application to Automatic Train
Handling (ATH)
• Solution Architecture
• Analysis of Results
• Remarks
August 24, 2000
ECAI 2000
37
FL Controllers Tuned by EAs
• FLC
- FLC = KB + Inference Engine (with Defuzz.)
- KB parameters:
» Scaling factors (SF)
» Membership Functions (MF)
» Rule set (RS)
• EA
August 24, 2000
Encoding: binary or real-valued
Chromosome: string or table
Fitness function: Sum quadratic errors, entropy
Operators: one-point crossover, max-min
arithmetical crossover, point-radius crossover.
ECAI 2000
38
FL Controllers tuned by EAs (cont.)
• Historical Approaches:
- Karr 91-93:
» Chromosome = concatenation of all termsets.
» Each value in a termset was represented by 3 binaryencoded parameters.
- Lee & Takagi 93:
» Chromosome = 1 TSK rule (LHS: memb. fnct. RHS pol.)
» Binary encoding of 3-parameter repr. of each term
- Surman et al: 93:
» Fitness function with added entropy term describing
number of activated rules
August 24, 2000
ECAI 2000
39
SC in Train Handling: An Example
• Problem Description
- Develop an automated train handler to control a massive,
distributed system with little sensor information
- Freight trains consist of several hundred heavy railcars
connected by couplers (train length up to two miles)
- Each coupler typically has a dead zone and a
hydraulically damped spring
- Railcars can move relative to each other while in motion,
leading to a train that can change its length by 50 – 100 ft.
- The position of the cars and couplers cannot be
electronically sensed
August 24, 2000
ECAI 2000
40
SC in Train Handling: An Example
• Solution Requirements
• An automated system has to satisfy multiple goals:
- Tracking a velocity reference (defined over distance)
to enforce speed limits and respect the train schedule
- Providing a degree of train-handling uniformity across
all crews
- Operating the train in fuel-efficient regimes
- Maintaining a smooth ride by avoiding sudden
accelerations or brake applications (slack control)
Multi-body regulation problem,
subject to proper slack management,
without sensors for most of the state
August 24, 2000
ECAI 2000
41
SC in Train Handling: An Example
• Description of Our Approach
- Use a Velocity Profile externally generated
(using classical optimization or Evolutionary
Algorithms)
- Use a Fuzzy Logic Control (FLC) to track the
velocity reference (Fuzzy PI Control)
- Use an Evolutionary Algorithms to tune the
FLC parameters to minimize velocity tracking
error and number of throttle changes
- Implement control actions with fuzzy rule set
to maintain slack control
August 24, 2000
ECAI 2000
42
FLC tuned by EAs: Our Approach
• Chromosome (real-valued encoding)
- Chr. 1 = Scaling factors;
- Chr. 2 = Termsets;
- Chr. 3 = Rules (not used)
• Order of tuning (as in Zheng '92):
- Initialize rulebase with standard PI structure and
termsets with uniformly distributed terms
- Apply EAs to find best scaling factors
- Apply EAs to find best termsets
- Apply EAs to find best rule set (not used)
• Transition from large to small granularity
August 24, 2000
ECAI 2000
43
FLC Sensitivity to Parameter Changes
X1
Changing
a Scaling
Factor
Very Low
Very Low
PH
Low
PH
Medium
PM
High
PL
Very High
ZE
Low
PH
PM
PL
ZE
NL
X2
Medium
PM
PL
ZE
NL
NM
High
PL
ZE
NL
NM
NH
Very High
ZE
NL
NM
NH
NH
Low
PH
PM
PL
ZE
NL
X2
Medium
PM
PL
ZE
NL
NM
High
PL
ZE
NL
NM
NH
Very High
ZE
NL
NM
NH
NH
Low
PH
PM
PL
ZE
NL
X2
Medium
PM
PL
ZE
NL
NM
High
PL
ZE
NL
NM
NH
Very High
ZE
NL
NM
NH
NH
X1
Changing
a Term in
X1
Very Low
Very Low
PH
Low
PH
Medium
PM
High
PL
Very High
ZE
X1
Changing
a Rule
August 24, 2000
Very Low
Very Low
PH
Low
PH
Medium
PM
High
PL
Very High
ZE
ECAI 2000
44
Architecture: Modules, Fitness Funct.
• Architecture
-
EA: pop.size=50; P(cross)=.6; P(mut)=.001
Three Types of fitness functions
Train Simulator: NSTD (STD+TEM)
Fuzzy PI (Ke, Kedot, Ku)
• Fitness functions (f1, f2, f3)
f 1  min ( |notchi notch(i1) ||dynbrakei  dynbrake(i1) |)
i
f 2  min ( |vi  vid |)
i
f 3  min (w1
August 24, 2000
 |notchi notch(i1) |
i
K1
ECAI 2000
 w2
( |vi  vid |)
i
K2
45
FLC tuned by GAs
SF or MF
GA (GENESIS)
Fitness
Function
Train
Simulator
August 24, 2000
FLC (PI)
ECAI 2000
46
Experiment Design
• 12 test (4 for each fitness function)
-
Initial SF with initial MF;
EA tuned SF with Initial MF
Initial SF with EA tuned MF;
EA tuned SF with EA tuned MF
• Train Simulation:
- 14 miles long flat track
- 1 uniformly heavy train with 100 cars and 4
locomotives
- Analytically computed velocity profile
August 24, 2000
ECAI 2000
47
Experiment Design
• Representation:
- SF: 3 floating point values for Ke, Kedot, Ku
- MF (21-9) = 12 values
» 21 parameters: [(Lefti ,Centeri , Righti ) for i=1, ..., 7]
» 9 dependent values: [(Lefti = Right(i+1)) for i=1, ..., 6]
+ [Center1= Center7]+[Right1 = Left7 = 0]
- Constraints to maintain 0.5 terms overlap, for
best interpolation
August 24, 2000
ECAI 2000
48
Experiments Results
• Experiment Results with f1
Description
Time Journey Fuel Fitness Gen.
Initial SF; Initial MF
26.5
EA tuned SF; Initial MF 27.8
Initial SF; EA tuned MF 26.00
EA tuned SF; EA tuned MF 28.3
14.26
14.21
14.18
14.12
878
857
879
829
73.2
15.15
70.93
14.64
4
20
10
• Experiment Results with f3
Description
Initial SF; Initial MF
EA tuned SF; Initial MF
Initial SF; EA tuned MF
EA tuned SF; EA tuned MF
August 24, 2000
Time Journey Fuel Fitness Gen.
26.5
27.2
26.26
27.3
ECAI 2000
14.26
14.35
14.18
14.35
878
871
871
872
1
0.817
0.942
0.817
4
20
10
49
Tuning of FLC with EA: Remarks
• Verified tuning order proposed by Zheng (92)
» SF tuning: major impact
» MF tuning: minor impact
» RS tuning: almost no impact
• For both f1 and f3, fuel minimization is implicitly
derived from throttle jockeying minimization
• Complex fitness function (requiring simulation
run - 23 sec for each chromosome evaluation)
limited trials number - with no apparent impact
• Successfully tested on simulated 43 mile long
track with altitude excursions
» (Selkirk, NY->Framingham, MA)
August 24, 2000
ECAI 2000
50
Results of EA Tuned PI on 43 mile Track
MPH
60.00
50.00
40.00
30.00
20.00
10.00
0.00
NOTCH
POSITION
mile
NOTCH
POSITION
8
4
0
August 24, 2000
ECAI 2000
mile
51
Results of EA Tuned PI on 43 mile Track
MPH
60.00
50.00
40.00
30.00
20.00
10.00
0.00
NOTCH
POSITION
mile
NOTCH
POSITION
8
4
0
August 24, 2000
ECAI 2000
mile
52
Results of EA Tuned PI on 43 mile Track
MPH
60.00
50.00
40.00
30.00
20.00
10.00
0.00
NOTCH
POSITION
mile
NOTCH
POSITION
8
4
0
August 24, 2000
ECAI 2000
mile
53
Results of EA Tuned PI on 43 mile Track
MPH
60.00
50.00
40.00
30.00
20.00
10.00
0.00
NOTCH
POSITION
mile
NOTCH
POSITION
8
4
0
August 24, 2000
ECAI 2000
mile
54
Hybrid SC and EA – Outline (3b)
• Soft Computing Overview
- SC Components: PR, FL, NN, EA
• Modeling with FL and EA
• Hybrid SC Systems
- FLC Parameter Tuning by EA
- EA Parameter Setting
• Conclusions
August 24, 2000
ECAI 2000
55
EA Parameter Setting
• EA Model:
- Structure, Parameters
• EA Parameter Setting
- EA Parameter Tuning
- EA Parameter Control
• An Application to Agile Manufacturing
- Object-level Representation and Complexity
• Solution
- FLC KB
- Statistical Experiments
- Analysis and Summary of 1200 Experiments
• Remarks
August 24, 2000
ECAI 2000
56
EA Model
Object-level GA
Structure
&
Parameters
Object-level Problem
August 24, 2000
ECAI 2000
57
EA Structure
•GA Structural Design Selections:
- GA Type:
»{Simple, Steady-State, Niche,…}
- Chromosome Encoding:
»{Binary, Integer, Real,...}
- Constraints Representation:
»{Penalty function, data structure, filters, …}
- Fitness Function:
»{Scalar function, Weighted aggregation of
multiple functions, Vector-valued function, …}
August 24, 2000
ECAI 2000
58
EA Parameters
• Adjustable parameters for a GA
-N
-
August 24, 2000
= Population size
Large pop. prevent premature convergence
Pc = Crossover rate:
Pcr * N = # crossovers per generation
Pm = Mutation rate:
Pm * N * L = # mutations per generation
G = Generation Gap
Percentage of population to be replaced
W = Scaling Window Size =[1, 7]
S = Selection Strategy = {Elitist, Non-Elitist}
ECAI 2000
59
EA Parameter Setting - Outline
• EA Model:
- Structure, Parameters
• EA Parameter Setting
- EA Parameter Tuning
- EA Parameter Control
• An Application to Agile Manufacturing
- Object-level Representation and Complexity
• Solution
- FLC KB
- Statistical Experiments
- Analysis and Summary of 1200 Experiments
• Remarks
August 24, 2000
ECAI 2000
60
EAs Parameter Setting
Before
the run
Parameter
Setting
Parameter
Control
Parameter
Tuning
August 24, 2000
During
the run
ECAI 2000
61
EAs Parameter Setting
Before
the run
Parameter
Setting
Parameter
Control
Parameter
Tuning
Deterministic
August 24, 2000
During
the run
ECAI 2000
Adaptive
Self-Adaptive
62
EAs Parameter Setting:
Parameter Tuning
Before
the run
Parameter
Setting
Parameter
Control
Parameter
Tuning
Deterministic
August 24, 2000
During
the run
Adaptive
Self-Adaptive
ECAI 2000
- Off-line Tuning
- Determined before
running the GAs on
the object-level
problem by
»Studying a subset
of five diverse
problems
(DeJong, 1975)
»Running a MetaGenetic Algorithm
(Grefenstette, 1986)
63
Off Line Tuning of GA Parameters
(DeJong, 1975)
Object-level GA
Suite of 5 problems:
- Parabola
- Rosenbrock’s
saddle
- Step function
- Quartic Noise
- Shekel’s foxholes
Population Size:
Crossover Rate:
Mutation Rate:
Replacement
Scaling Window
Selection Strategy
50
0.6
0.001
100%
n=inf
Elitist
Object-level GA
Object-level Problem
August 24, 2000
ECAI 2000
64
SC Hybrid Systems: EA Tuning EA
Approximate Reasoning
Approaches
Probabilistic Multivalued &
Fuzzy Logics
Models
Search/Optimization
Approaches
Neural
Networks
Evolutionary
Algorithms
Evolution
Strategies
Evolutionary
Programs
Genetic
Algorithms
Genetic
Progr.
HYBRID EA
SYSTEMS EA parameters
(Pop size, select.)
controlled by EA
August 24, 2000
ECAI 2000
65
Off Line Tuning of GA Parameters
(Grefenstette, 1986)
Object GA
Performance
Meta- GA
Object-level GA
Suite of 5 problems:
- Parabola
- Rosenbrock’s
saddle
- Step function
- Quartic Noise
- Shekel’s foxholes
Object GA
Parameter
Set
Off-Line Performance
Population Size:
80
On-Line
Performance
Crossover
Rate:
0.45
MutationSize:
Rate:
Population
Replacement
Crossover
Rate:
Scaling
Window
Mutation Rate:
Selection Strategy
Replacement
Scaling Window
Selection Strategy
0.01
30
90%
0.96
n=1
0.01
NonElitist
100%
n = inf
Elitist
Object-level GA
Object-level Problem
August 24, 2000
ECAI 2000
66
GAs Parameter Setting: Deterministic Control
Before
the run
Parameter
Tuning
Deterministic
August 24, 2000
During
the run
Parameter
Setting
Parameter
Control
Adaptive
Self-Adaptive
ECAI 2000
- No feedback
information is used.
- A time-varying
schedule is used to
modify a GA
parameter p
- p is replaced by p(t)
- Correct design of p(t)
is very difficult
67
EAs Parameter Setting:
Deterministic Control - Example
Control of Population size
By decreasing Population Size toward the last part of the Evolution
we are trying to improve the solution refinement (e.g., more
generations with same number of trials)
PopSize
•Constant Population size: N = 338
•Number of trials = 338 * MaxGen
500
338
PopSize
150
30% 45%
80% CurrGen/Maxgen 500
• Variable Population size: N(t)
• Number of trials = 338 * MaxGen
300
150
30% 45%
August 24, 2000
ECAI 2000
80% CurrGen/Ma
xgen
68
EAs Parameter Setting:
Self-Adaptive Control
Before
the run
Parameter
Setting
During
the run
- Incorporate parameters
into chromosome making
them subject to evolution
- Typically used to
determine Mutation Step S:
[g1 g2 ... gn S]
Parameter
Control
Parameter
Tuning
Mutation Step for Entire Genome
Deterministic
Adaptive
or
SelfAdaptive
[g1 g2 ... gn S1 S2 ... Sn ]
Mutation Steps for Each
Genome Value
August 24, 2000
ECAI 2000
69
GAs Parameter Setting:
Adaptive Control
Before Parameter
the run
Setting
During
the run
Parameter
Control
Parameter
Tuning
Deterministic
Adaptive
- Feedback from the
search is used to
determine the direction
and/or magnitude of the
change in the parameter
value.
- A Fuzzy Logic Controller
is used to obtain
parameter changes in
Self-Adaptive
» Population Size
» Mutation Rate
as a function of
» Genotypic Diversity
» Percentage Completed
Trials
August 24, 2000
ECAI 2000
70
SC Hybrid Systems: FLC Tuning EA
Search/Optimization
Approaches
Approximate Reasoning
Approaches
Probabilistic Multivalued &
Fuzzy Logics
Models
MV-Algebras
Neural
Networks
Fuzzy
Logic
Fuzzy
Controller
Evolution
Strategies
Genetic
Algorithms
Evolutionary
Programs
Genetic
Progr.
HYBRID
SYSTEMS
August 24, 2000
Evolutionary
Algorithms
ECAI 2000
EA parameters
controlled
by FLC
71
Fuzzy Logic Controlled GA
(FLC-GA)
State Variables describing
the evolution stage
• Genotypic Diversity
• Percentage
Completed Trials
Controlled GA parameters
KB
Fuzzy Logic
Controller
 Population Size
 Mutation Rate
Object-level GA
Object-level Problem
August 24, 2000
ECAI 2000
72
EA Parameter Setting
• EA Model:
- Structure, Parameters
• EA Parameter Setting
- EA Parameter Tuning
- EA Parameter Control
• An Application to Agile Manufacturing
- Object-level Representation and Complexity
• Solution
- FLC KB
- Statistical Experiments
- Analysis and Summary of 1200 Experiments
• Remarks
August 24, 2000
ECAI 2000
73
EA Parameter Control:
An Application
Global optimization of design, manufacturing, supplier
planning decisions in a distributed manufacturing environment
Marketing
Customer
Tools
Data
Tools
Design
Data
Tools
Data
Supplier
Data
Tools
Data
Tools
Virtual Design
Environment
Manufacturing
August 24, 2000
ECAI 2000
74
Object-level Problem Representation
Parts, suppliers,
and design DB
Part P1
Part P2
Part Pk
Acceptable
Alternates
Gene Allele Sets
Design
8
6
3
3
2
2
1
1
Mfg. DB
Suppliers
P1 P2
Pk M
Genome
Manufacturing Facilities
min
i,j
J ij  CijT e
(TijT
10 ) 3
Object-level Optimization Problem
August 24, 2000
Offspring
Parents
Crossover Operation
ECAI 2000
Mutation
75
Object-level Problem Complexity
Search Space Size
• For EA Statistical Analysis:
O(107)
• For EA Performance Validation:
O(1018) and O(1021)
August 24, 2000
ECAI 2000
76
EA Parameter Setting - Outline
• EA Model:
- Structure, Parameters
• EA Parameter Setting
- EA Parameter Tuning
- EA Parameter Control
• An Application to Agile Manufacturing
- Object-level Representation and Complexity
• Solution
- FLC KB
- Statistical Experiments
- Analysis and Summary of 1200 Experiments
• Remarks
August 24, 2000
ECAI 2000
77
Solution Architecture
Fuzzy Logic
Controlled GA
(Online Control)
Fuzzy Logic
Controller
Untuned GA
Object-level GA
Object-level GA
Manufacturing Planning Module
August 24, 2000
ECAI 2000
78
Untuned GA (U-TGA)
Population Size:
Generations:
Crossover Rate:
Mutation Rate:
50
250
0.6
0.001
Object-level GA
Manufacturing Planning Module
August 24, 2000
ECAI 2000
79
Guidance for Experiments
•Minimize high-level search space size for FLC-EA by
- Identify primary drivers (influences) of EA search
DOE determined that the two main drivers were:
Population Size (N) and Mutation Rate (Pm )
- Control primary drivers by few simple heuristic rules
Built two FLC controllers with heuristic rule sets and SF
Changed on input (state variable) to capture evolution stage
• Determining FLC firing rate
- Take a control action every 10 generation
• Extensive & statistically significant empirical evidence
- Use t-test and F-tests to analyze m and s
improvements
August 24, 2000
ECAI 2000
80
Fuzzy Logic Controller for EAs:
Knowledge Base
I/O Scaling Factors
I/O Termsets
Rule Sets
KB
• Genotypic Diversity
• Percentage
Completed Trials
Fuzzy Logic
Controller
 Population Size
 Mutation Rate
Object-level EA
Object-level Problem
August 24, 2000
ECAI 2000
81
Fuzzy Controller for N and Pm: Inputs
• Inputs
GD = Genotypic Diversity:
Normalized Average Hamming Distance
d ij
n

GD 
n( n  1) i 1, j i 1 Genome Length
2
where dij is the Hamming Distance
GD range is [0, 1] == [Low, High]
PFE = Percentage Fitness Evaluations:
(Completed # Trials) / (Max Allocated # Trials)
PFE range is [0, 1] = [Low, High]
August 24, 2000
ECAI 2000
82
Fuzzy Logic Controller for EAs:
Knowledge Base
I/O Scaling Factors I/O Termsets
Rule Sets
KB
• Genotypic Diversity
• Percentage
Completed Trials
Fuzzy Logic
Controller
 Population Size
 Mutation Rate
Object-level EA
Object-level Problem
August 24, 2000
ECAI 2000
83
Fuzzy Controller for N and Pm:
Termsets
A
B
1
•Inputs:
•
•
0.8
GD: A(Very Low), B(Low), C(Medium), D(High), E(Very High)
PFE: A(Very Low), B(Low), C(Medium), D(High), E(Very High)
•Outputs (for both  N and  Pm):
0.6
•A(Neg. High), B(Neg. Medium), C(No Change), D(Pos. Medium),
High)
August 24,E(Pos.
2000
ECAI 2000
84
Fuzzy Logic Controller for EAs:
Knowledge Base
I/O Scaling Factors
I/O Termsets
Rule Sets
KB
• Genotypic Diversity
• Percentage
Completed Trials
Fuzzy Logic
Controller
 Population Size
 Mutation Rate
Object-level EA
Object-level Problem
August 24, 2000
ECAI 2000
85
Fuzzy Controller for Population Size:
Rule Set
GD, PFE>N
GD
= Genotypic Diversity:
Normalized Average Hamming Distance
PFE = Percentage Fitness Evaluations:
(Completed # Trials) / (Max Allocated # Trials)
N
= Change in Population Size
Genotypic
Percentage Fitness Evaluation (PFE)
Diversity (GD) Very Low
Low
Medium
High
Very High
Very Low
Pos High
Pos High
Pos High Pos Medium No Change
Low
Pos High
Pos High Pos Medium No Change Neg Medium
Medium
Pos High Pos Medium No Change Neg Medium Neg High
High
Pos Medium No Change Neg Medium Neg High
Neg High
Very High
No Change Neg Medium Neg High
Neg High
Neg High
August 24, 2000
Exploration Stage
Exploitation Stage
Increase population/ broaden search
Reduce population/ Refine best
ECAI 2000
86
Statistical Experiments: EA Structure
• Data Set for Experiments
- Seven part classes corresponding to a
complexity of O(107)
• EA Structure:
- Type:
{Simple, Steady-State}
- Chromosome Encoding:
Integer
- Fitness Function:
Three type of cost
- Selection Method:
- Crossover Operator:
- Mutation Operator:
August 24, 2000
ECAI 2000
functions
Proportional Roulette
Uniform
Exponentially
87
Statistical Experiments: Set-Up
• Set-Up for 1200 experiments:
- We defined 4 EA configurations
(a) Untuned Simple EA (U-SEA)
(b) FL Controlled Simple EA (FLC-SEA)
(c) Untuned Steady State EA (U-SSEA)
(d) FL Controlled Steady State EA (FLCSSEA)
August 24, 2000
ECAI 2000
88
Statistical Experiments: Set-Up (cont.)
• For each configuration we performed
300 experiments:
- 20 runs for each pair of (Cost function, Max
number of Trials)
- 15 different pairs of (Cost function, Max number
of Trials)
- Three types of cost functions:
(1) J = C*T; (2) J = C*T2; (3) J = C*e(T-10)/3
- Five values of maximum number of Trials (to
evaluate effect of different evolution lengths):
(i) 3,000; (ii) 5,000; (iii) 7,000; (iv) 9,000; (v) 11,000
August 24, 2000
ECAI 2000
89
Statistical Experiments: Measures
• For each of the four configurations (a-d) we
ran 20 experiments with the same
parameters
• Then we considered the following
measures:
= sample average over 20 experiments of
BˆB Best
score frequency (number of time cost
function J reached its minimal value known a priori for small size experiment)
mˆm = average of population best
sˆs = standard deviation of population best
August 24, 2000
ECAI 2000
90
Statistical Experiments: Analysis
• We performed an ANOVA test (both
t and F test - with p < 0.05 ) to see if:
Cost (U-SEA) >> cost ( FLCSEA)
Cost (U-SEA) >> cost ( U-SSEA)
Cost (U-SSEA) >> cost ( FLC-SSEA)
• We verified if the FLC caused the
controlled EA to perform worse than its
corresponding untuned EA, i.e.:
Cost (U-SEA) << cost ( FLC-SEA)
Cost (U-SSEA) << cost ( FLC-SSEA)
August 24, 2000
ECAI 2000
91
Statistical Experiments: Results
J = Cost
Function
C*T
C*T2
C*e(T-10)/3
Total
B
-
U-SEA
m
1
7%
s
-
FLC-SEA
B
m
s
4
3
2
3
3
47% 60%
Significant and
changes in m in s
U-SSEA
B
m
1
7%
s
-
FLC-SSEA
B
m
s
1
2
1
3
1
2
20% 47%
Significant
changes in s
• For each cost function we ran 400 experiments (100 x EA type)
• For each EA type we ran 20 experiments for 5 different pop. sizes
• The entry in each cell is the number of significant changes found in
the statistics of each of these five groups of experiments
August 24, 2000
ECAI 2000
92
EA Parameter Setting
• EA Model:
- Structure, Parameters
• EA Parameter Setting
- EA Parameter Tuning
- EA Parameter Control
• An Application to Agile Manufacturing
- Object-level Representation and Complexity
• Solution
- FLC KB
- Statistical Experiments
- Analysis and Summary of 1200 Experiments
• Remarks
August 24, 2000
ECAI 2000
93
Remarks
• FLC State Representation: [Evolution
Stage]
- Evolution time needs to be an explicit state
variable since we have different control goals
during the EA’s stages.
- Diversity measures the evolutionary stage:
» Percentage Fitness Evaluations (PFE)
» Genotypic Diversity (GD)
• FLC Control Variables: [EA Adaptable
Parameters]
 N = Change in Population Size
 Pm = Change in Mutation Rate
August 24, 2000
ECAI 2000
94
Remarks (cont.)
• Main Result
- By using the FLC with the above State and
Control variables, we achieved a good
improvement of the population average
and an even better improvement of the
population variance.
- No major negative effects on EA performance
using FLC
August 24, 2000
ECAI 2000
95
Hybrid SC and EA – Outline (4)
• Soft Computing Overview
- SC Components: PR, FL, NN, EA
• Modeling with FL and EA
• Hybrid SC Systems
- FLC Parameter Tuning by EA
- EA Parameter Setting
• Conclusions
August 24, 2000
ECAI 2000
96
Synergy in SC: Reasons & Approaches
• Hybrid Soft Computing
- Leverages tolerance for imprecision, uncertainty, and
incompleteness - intrinsic to the problems to be solved
- Generates tractable, low-cost, robust solutions to such
problems by integrating knowledge and data
• Tight Hybridization
- Data-driven Tuning of Knowledge-derived Models
» Translate domain knowledge into initial structure and parameters
» Use Global or local data search to tune parameters
- Knowledge-driven Search Control
» Use Global or local data search to derive models (Structure +
Parameters)
» Translate domain knowledge into an algorithm’s controller to
improve/manage solution convergence and quality
August 24, 2000
ECAI 2000
97
Synergy in SC: Reasons & Approaches
• Loose Hybridization (Model Fusion)
- Does not combine features of methodologies - only their
results
- Their outputs are compared, contrasted, and
aggregated, to increase reliability
• Hybrid Search Methods
- Intertwining local search within global search
- Embedding knowledge in operators for global search
• Future:
- Circle of SC's related technologies will probably widen
beyond its current constituents.
- Push for low-cost solutions and intelligent tools will result
in deployment of hybrid SC systems that efficiently
integrate reasoning and search techniques.
August 24, 2000
ECAI 2000
98
August 24, 2000
ECAI 2000
99
FL Controllers tuned by EAs (cont.)
• Historical Approaches (cont.):
- Kinzel et al. 94:
» Chromosome = Rule Table
» Point-radius crossover changing 3x3 rule window
(similar to a two-point crossover for string
representation)
» Order of tuning:
– Initialize rulebase according to heuristics
– Apply GAs to find best rule table
– Tune membership function of best rule set
- Herrera et al. 95:
» Chromosome = concatenation of all rules
» Real-valued encoding, Max-min arithmetical crossover
August 24, 2000
ECAI 2000
100
Evolutionary Algorithms: ES
•Evolutionary Strategies (ES)
- Originally proposed for the optimization of
continuous functions
- (m , l)-ES and (m + l)-ES
» A population of m parents generate l offspring
» Best m offspring are selected in the next generation
» (m , l)-ES: parents are excluded from selection
» (m + l)-ES: parents are included in selection
- Started as (1+1)-ES (Reschenberg) and evolved
to (m + l)-ES (Schwefel)
- Started with Mutation only (with individual
mutation operator) and later added a
recombination operator
- Focus on behavior of individuals
August 24, 2000
ECAI 2000
101
Evolutionary Algorithms: EP
•Evolutionary Programming (EP)
- Originally proposed for sequence predictiom
and optimal gaming strategies
- Currently focused on continuous parameter
optimization and training of NNs
- Could be considered a special case of (m + m)
-ES without recombination operator
- Focus on behavior of species (hence no
crossover)
- Proposed by Larry Fogel (1963)
August 24, 2000
ECAI 2000
102
Evolutionary Algorithms: GA
•Genetic Algorithms (GA)
- Perform a randomized search in solution space using a
genotypic rather than a phenotypic
- Each solution is encoded as a chromosome in a population (a
binary, integer, or real-valued string)
» Each string’s element represents a particular feature of the
solution
- The string is evaluated by a fitness function to determine the
solution’s quality
» Better-fit solutions survive and produce offspring
» Less-fit solutions are culled from the population
- Strings are evolved using mutation & recombination operators.
- New individuals created by these operators form next generation of
solutions
- Started by Holland (1962; 1975)
August 24, 2000
ECAI 2000
103
Evolutionary Algorithms: GP
•Genetic Programming (GP)
- A special case of Genetic Algorithms
»Chromosomes have a hierarchical rather than a linear
structure
»Their sizes are not predefined
»Individuals are tree-structured programs
»Modified operators are applied to sub-trees or single nodes
- Proposed by Koza (1992)
August 24, 2000
ECAI 2000
104
GA Structure (cont.)
•GA Structural Design Selections:
- Parent Selection Method:
»{Proportional Roulette, Tournament,
Rank, Uniform, ... }
- Crossover Operator:
»{Once-cut, Two-cuts, Uniform, BLX,
Parent Weighted, ...}
- Mutation Operator:
»Mutation Rate: {Exponentially Decreasing,
Uniform, ..}
»Value: {Exponentially Decreasing,
Uniform, Normally Distributed, …}
August 24, 2000
ECAI 2000
105
GA Parameters (cont.)
•Other possible parameters that could be
adjusted:
= Number of Trials = S Ni
where N is population size and
i= 1, Max_Gen
sm = Mutation step
s in Normally distributed Mutation value
- PS = Probability of Selection
Parametrized slope of probability distribut.
- AS = Arity of Parents
number of parents in recombination
-T
August 24, 2000
ECAI 2000
106
Fuzzy Controller for Mutation Rate: Rule Set
GD, PFE>Pm
GD
PFE
Pm
= Genotypic Diversity:
Normalized Average Hamming Distance
= Percentage Fitness Evaluations:
(Completed # Trials) / (Max Allocated # Trials)
= Change in Mutation Rate
Genotypic
Diversity (GD)
Very Low
Low
Medium
High
Very High
August 24, 2000
Percentage Fitness Evaluation (PFE)
Very Low
Low
Medium
High
Very High
Pos High
Pos High
Pos High
Pos Medium Pos Medium No Change
Pos Medium Pos Medium No Change No Change
Pos Medium Pos Medium No Change
No Change No Change
Pos Medium No Change
No Change
No Change No Change
No Change
No Change
No Change No Change
No Change
ECAI 2000
107
Statistical Experiments: Set-Up
(cont.)
• GA Parameters
-
N
Pc
Pm
G
= Base Population size:
= Crossover rate:
= Mutation rate:
= Generation Gap
- S = Selection Strategy:
August 24, 2000
ECAI 2000
50
0.600
0.005
100% replacement
- Simple GA (SGA)
25% replacement
- Steady State GA (SSGA)
Elitist
108
Summary of 1200 Experiments
Max Numb
Trials
B
U-SGA
m
s
s/m
3000
5000
7000
9000
11000
0%
5%
35%
20%
50%
1788.8
1767.9
1710.3
1748.8
1719.5
71
103
81
102
88
0.040
0.058
0.047
0.058
0.051
Max Numb
Trials
B
U-SGA
m
s
s/m
3000
5000
7000
9000
11000
5%
30%
20%
30%
65%
Max Numb
Trials
B
U-SGA
m
s
s/m
3000
5000
7000
9000
11000
0%
10%
20%
30%
25%
655.05
625.1
606.84
569.14
608.35
90.2
95.0
97.9
29.8
129.4
0.138
0.152
0.161
0.052
0.213
J = C*T
J = C*T2
2
JJ == C*T
C*e(T-10)/3
352.5 20.9
338.6 8.0
339.7 1.9
343.2 15.74
337.0 15.3
0.059
0.024
0.005
0.046
0.045
B
FLC-SGA
m
s
20%
35%
45%
50%
75%
B
81
74
41
46
40
FLC-SGA
m
s
15%
30%
30%
50%
60%
B
1729
1705
1680
1676
1668
0.047
0.043
0.025
0.027
0.024
s/m
341.3 12.0 0.035
337.7 7.9 0.023
338.8 1.7 0.005
333.9 5.0 0.015
331.7 3.5 0.010
B
U-SSGA
m
s
70%
75%
60%
80%
75%
B
1685
1682
1739
1695
1709
U-SSGA
m
s
50%
60%
70%
80%
65%
343.8
336.2
341.3
335.2
336.9
638.2
600.8
566.4
573.9
573.0
87.7
47.6
22.3
41.8
35.7
s/m
0.137
0.079
0.039
0.073
0.062
B
August 24, 2000
23.0
11.6
5.2
15.3
15.3
U-SSGA
m
s
15%
35%
70%
85%
60%
592.0
597.1
563.6
556.3
568.4
Significant change in m
7%
63
63
108
82
98
J = C*e(T-10)/3
FLC-SGA
m
s
5%
25%
20%
50%
40%
s/m
47% 60%
ECAI 2000
53.0
91.5
22.8
17.7
24.4
s/m
B
FLC-SSGA
m
s
0.037
0.037
0.062
0.048
0.058
80%
80%
95%
85%
95%
s/m
B
58
47
45
70
45
FLC-SSGA
m
s
0.067
0.034
0.015
0.046
0.045
75%
85%
70%
60%
65%
s/m
B
0.090
0.153
0.040
0.032
0.043
1677
1673
1665
1689
1665
332.4 4.6
331.8 4.1
336.3 3.4
334.6 5.6
336.9 15.3
FLC-SSGA
m
s
80%
55%
65%
50%
70%
554.3
570.8
566.0
573.2
563.6
14.9
24.7
23.7
24.9
22.7
s/m
0.034
0.028
0.027
0.041
0.027
s/m
0.014
0.012
0.010
0.017
0.045
s/m
0.027
0.043
0.042
0.043
0.040
Significant change in s
7%
20% 47%
109
Next Steps: Controlling Other Parameters
• Run-time Controlled GAs Parameters:
DONE
DONE
- Population size:
» larger size: increase parallel search in solution space
» smaller size: focus on current existing regions
- Probability mutation:
» Higher prob. of mutation disrupts current solutions - exploration
» Lower probability of mutation favors current solutions - exploitation
• Other Possible Run-time Controllable GAs Parameters:
- Customized mutation operators:
» Variable amount of changes
– smaller for good solutions, larger for bad ones
- Fitness function:
» Evolving fitness function (variable weights in multi-criteria
aggregating function)
August 24, 2000
ECAI 2000
110
GAs controlled by FL (cont.)
- Probability of Selection:
» Parametrized slope distribution ranging from:
– Uniform probability: ignore fitness function and perform random
selection of parents - extreme case of exploration, to
– Proportional selection with rescaling and other intermediate strategies compromise between exploration and exploitation cases, and
– Ranking: always select the best N and ignore the rest - extreme case of
exploitation
» Probability as function of fitness and genotypical distance with other
solutions - enforcing diversity and favoring exploration
- Probability of crossover:
» Constraints applicability to mostly good solutions
- Customized-crossover operators (for real-coded GAs):
» Selection of crossovers based on T-norms and T-conorms causes
offsprings to take more extreme values (exploration)
» Selection of crossovers based on aggregating operators causes
August 24, 2000
2000
111
offsprings to take averageECAI
values
(exploitation)
Fuzzy Controller for N and Pm:
Control Parameters
Frequency of Control Actions
Control Action:
mutation rate changed every 10 generations
population size change every generation
Mutation Rate
Mutation rates drops exponentially after a control action that
increases it
Inference Engine Parameters
Left Hand Side (LHS) evaluation:
Rule Firing:
Rule Output Aggregation:
Defuzzification:
August 24, 2000
ECAI 2000
Minimum operator
Minimum operator
Maximum operator
Center of Gravity (COG)
112
Fuzzy Controller for N and Pm: Outputs
• Outputs
N
= Change in Population Size (Mult. Factor)
 N range is [0.5, 1.5] == [Neg High, Pos High]
N range
is [0.5, 1.5]to==100%
[Neg High,
Pos High]Pop Size
so thatNC
corresponds
of previous
- so that NC corresponds to 100% of previous Pop Size
Population Size is clamped within [25, 150]
Pm = Change in Mutation Rate (Mult. Factor)
 Pm range is [0.5, 1.5] == [Neg High, Pos High]
so that NC corresponds to 100% of previous Pm
Mutation Rate is clamped within [0.005, 0.10]
August 24, 2000
ECAI 2000
113
Fusion of Reasoning Models
• Develop Collection of Quasi-independent Models
• Each Model Generates:
- Output Value (Vi ) - Prediction
- Confidence parameter (Ci ) derived from training stats. - Introspection
• Intelligent Fusion Rules
- Consider discrepancies among Output values (v)
- Consider dynamic confidence value (c) associated with each output
Example of Fusion for Mortgage Collateral Evaluation
Living Area
Address
(GeoCoded )
eL
Loc Val
eG
AIGEN
Lot Size
# Beds
# Baths, ...
Pool
Conditions
...
AICOMP
eC
FUSION
RULES
eF
ei = { V i , C i }
August 24, 2000
ECAI 2000
114
Synergy in SC: Reasons & Approaches
• SC Leverages Knowledge and Data to Derive the Model
• Model = Structure + Parameters (& Search)
• Data-driven Tuning of Knowledge-derived Models
-Translate domain knowledge to initial structure & parameters
-Use Global or local data search to tune parameters
• Knowledge-driven Search Control
-Use Global or local data search to derive models (Structure +
Parameters)
-Translate domain knowledge into an algorithm’s controller to
improve/manage solution convergence and quality
• Hybrid Search Methods
-Embedding local search within global search
-Embedding knowledge in operators for global search
-Fusion of models to increase
accuracy and reliability
August 24, 2000
ECAI 2000
115