Utilizarea AG pentru rezolvarea problemelor de optimizare ... · Tehnici de inteligenţă...

Tehnici de inteligenţă computaţională în electronică, G. Oltean

ALGORITMI GENETICI

Utilizarea AG

pentru rezolvarea

problemelor de optimizare

cu un singur obiectiv


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)(


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


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


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


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 )


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)


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:

http://www.mathworks.com/help/gads/genetic-algorithm-options.html#f14223


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


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


ALGORITMI GENETICI

4. Rularea algoritmului Interfata grafica

>> optimtool

>> optimtool(‘ga’)


ALGORITMI GENETICI


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


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


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


ALGORITMI GENETICI


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.


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


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


ALGORITMI GENETICI

20 /17

-5

0

5

-2-1

01

2-1000

0

1000

2000

3000

4000

5000

x1

sixmin(x,y)

x2

-2-1

01

2

-1

-0.5

0

0.5

1

-2

0

2

4

6

x1

f(x)

x2

Utilizarea AG pentru rezolvarea problemelor de optimizare ... · Tehnici de inteligenţă...

Documents

Transcript of Utilizarea AG pentru rezolvarea problemelor de optimizare ... · Tehnici de inteligenţă...