utilizarea ag pentru rezolvarea problemelor de optimizare ... · tehnici de inteligenţă...
TRANSCRIPT
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Utilizarea AG
pentru rezolvarea
problemelor de optimizare
cu un singur obiectiv
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Enuntarea problemei de optimizare
Problema de optimizare cu un singur obiectiv, cu constrangeri:
supusa la:
constrangeri de inegalitate
constrangeri de egalitate
constrangeri de marginire
Constrangerile de inegalitate sau egalitate pot fi liniare sau neliniare
za)(minimizeaaoptimizeazcare,...,,vectorulGaseste 21
T
Nxxxx
)(xf
Mixgi ...,,1,0)(
Nk
kubkxklb
...,,1
)()()(
Pjxh j ...,,1,0)(
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Formularea problemei pentrurezolvare cu AG in Matlab
Functia obiectiv f trebuie scrisa sub forma unei functii matlab (objfcn.m)
care primeste ca argument vectorul variabilelor x si returneaza o valoare
scalara (valoarea functiei obiectiv).
Se apeleaza sub forma “@objfcn”
Este necesara precizarea numarului de variabile independente a functiei
obiectiv
1. Definirea problemei
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Constrangerile liniare se pot exprima in format matricial:
0 bxA;bxA
0; beqxAeqbeqxAeq
2. Definirea constrangerilor
In aplicatie se utilizeaza matricile A, Aeq si vectorii coloana b si beq
De exemplu: o functie cu 3 variabile cu 2 constrangeri de inegalitate:
2323222121
1313212111
bxaxaxa
bxaxaxa
232221
131211
aaa
aaaA
2
1
b
bb
de inegalitate
de egalitate
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Constrangerile neliniare se scriu intr-o functie matlab (nonlcon.m)
ce primeste ca argument vectorul variabilelor x si returneaza vectorii
c si ceq.
2. Definirea constrangerilor – cont.
Constrangerile de marginire se definesc prin vectorii coloana
lb - valorile minime ale variabilelor
ub - valorile maxime ale variabilelor
Inegalitatile neliniare sunt de forma c 0
Egalitatile neliniare sunt de forma ceq = 0
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
3. Definirea optiunilor
Populatia - Population (tip, marime (subpopulatii), generare,
populatie initiala, scor populatie initiala domeniul initial)
Ierarhizarea indivizilor (in vederea selectiei) – Fitness scaling
(Rank, Proportional, Top scales, Shift linear)
Selectia – Selection (Stochastic uniform, Remainder, Roulette,
Tournament )
Reproducerea - Reproduction (Elite count, Crossover fraction)
Mutatia – Mutation (Constraint dependent, Gaussian, Uniform,
Adaptive feasible)
Incrucisarea – Crossover (Scattered, Single point, Two point,
Intermediate, Heuristic, Arithmetic )
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
3. Definirea optiunilor– cont.
Migratia - Migration (Direction, Fraction, Interval)
Parametrii constrangerilor neliniare – Constraint
parameters (Initial penalty, Penalty factor)
Functie de optimizare pentru optimizarea hibrida – Hybrid
function (None, fminsearch, patternsearch, fminunc, fmincon)
Criterii de terminare - Stopping criteria (Generations, Time
limit, Fitness limit, Stall generations, Stall time limit, Function
tolerance, Nonlinear constraint tolerance – nu este conditie de oprire)
Reprezentari grafice – Plot Functions (Plot interval, Best fitness,
Best individuals, Distance, Expectation, Genealogy, Range, Score
diversity, Scores, Selection, Stopping, Max constraints)
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
3. Definirea optiunilor– cont.
Functii de iesire – Output functions
Afisare in fereastra de comenzi – Display to command
window (off, Iterative, Diagnose, Final)
Modalitatea de evaluare a functiilor (obiectiv, constrangeri) –
User function evaluation (serial, vectorized, parallel)
http://www.mathworks.com/help/gads/genetic-algorithm-options.html#f14223
Explicatii detaliate despre optiuni si utilizarea lor:
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
4. Rularea algoritmului Din fereastra de comenzi (Command window)
>> X = ga(OBJFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON,options)
• Vizualizarea optiunilor >> options = gaoptimset
• Vizualizarea valorilor implicite a
optiunilor>> options = gaoptimset(@ga)
>> options = gaoptimset('param1',value1,'param2',value2,...)
• Modificarea optiunilor
>> help gaoptimset
• Vizualizarea valorilor posibile a optiunilor
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI PopulationType: 'doubleVector'
PopInitRange: [2x1 double]
PopulationSize: 20
EliteCount: 2
CrossoverFraction: 0.8000
ParetoFraction: []
MigrationDirection: 'forward'
MigrationInterval: 20
MigrationFraction: 0.2000
Generations: 100
TimeLimit: Inf
FitnessLimit: -Inf
StallGenLimit: 50
StallTimeLimit: Inf
TolFun: 1.0000e-06
TolCon: 1.0000e-06
InitialPopulation: []
InitialScores: []
InitialPenalty: 10
PenaltyFactor: 100
PlotInterval: 1
CreationFcn: @gacreationuniform
FitnessScalingFcn: @fitscalingrank
SelectionFcn: @selectionstochunif
CrossoverFcn: @crossoverscattered
MutationFcn: {[@mutationgaussian] [1] [1]}
DistanceMeasureFcn: []
HybridFcn: []
Display: 'final'
PlotFcns: []
OutputFcns: []
Vectorized: 'off'
UseParallel: 'never'
• Valorile implicite ale optiunilor
>> options = gaoptimset(@ga
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
4. Rularea algoritmului Interfata grafica
>> optimtool
>> optimtool(‘ga’)
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Studiul de caz Sa se minimizeze functia lui de Jong de 2 variabile
utilizand instrumentul de optimizare cu AG,
gatool din Matlab
13;13,),( 22 yxyxyxf
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Fitness Function
function y = jong2s(x)
% function y = jong2(x)
% functia lui De Jong pentru 2 variabile
% x este un vector de 2 variabile
% functia fitness pentru evaluare serie a fiecarui individ din populatie
% in cadrul unei generatii
y = x(1)^2 +x(2)^2;
jong2s.m
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Afisare in workspaceFereastra separata
-----------------------------
Optimization running.
Optimization terminated.
Objective function value: 4.593690546583323E-6
Optimization terminated: maximum number of
generations exceeded.
Fereastra de rezultate
a instrumenului de
optimizare
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Problema se poate exporta in workspace si mai
apoi salva pe harddisk
Ulterior problema se poate importa din workspace
Daca problema a fost exportata cu “Include information needed to resume
this run”, dupa realizarea importului optimizarea porneste din punctul in
care s-a oprit inainte de exportare.
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
Se poate genera o functie Matlab pentru a rula optimizarea de la consola
Matlab
Pentru rulare trebuie executata functia generata cu valorile parametrilor
specificate
Tehnici de inteligenţă computaţională în electronică, G. Oltean
ALGORITMI GENETICI
19 /17
Case study
Six-hump camel back function
Within the bounded region six local minima are located, two of
them are global minima:
(-0.0898,0.7126), (0.0898,-0.7126)
-3<=x1<=3, -2<=x
2<=2
-5
0
5
-2-1
01
2-1000
0
1000
2000
3000
4000
5000
x1
sixmin(x,y)
x2