Algoritmos genéticos (Matlab)
MATLAB Optimization Toolbox
Iury Steiner de Oliveira Bezerra
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Tópicos
• Introdução
• Otimização de funções
• Optimization Toolbox
• Rotinas / Algoritmos Disponíveis
• Problemas de minimização
• Sem restrições
• Com Restrições
• Exemplos
• Descrição do algoritmo
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Otimização de Funções
Otimização se refere basicamente a maximização ou
minimização de funções
Problema típico de otimização:
min f x
x
~
~
Subject to:
hi x 0 Restrições de igualdade
~
g x 0
j Restrições de desigualdade
~
x L k xk xU k Restrições de fronteira
Where:
f x
~
é a função objetivo, o que medir e avaliar o desempenho de um sistema.
Em um problema padrão, estamos minimizando a função. Para
maximização, é equivalente à minimização função objetivo multiplicada por
-1.
x é um vetor coluna de variáveis consideradas, que pode
~ afetar o desempenho da otimização.
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Function Optimization (Cont.)
Restrições – Delimitação do espaço de soluções viávies .
Podem ser basicamente lineares e não lineares
hi x 0
~
Restrições de igualdade
g x 0
j
Restrições de desigualdades
~
Muitos algoritmos necessitam dessa condição
x L k xk xU k Restrições de fronteira ou domínio
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Optimization Toolbox
É uma coleção de funções que estendem a capacidade de MATLAB.
As rotinas incluem:
•Otimização sem restrições
•Otimização com restrições lineares e não-lineares.
• Programação Quadrática e programação linear
• Nonlinear least squares and curve fitting
• Nonlinear systems of equations solving
• Constrained linear least squares
•Algoritmos para large scale problems
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Algoritmos de minimização
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Algoritmos de minimização
(Cont.)
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Algoritmos para resolver
equações
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Algoritmos de mínimimos
quadrados
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Trabalhando com o Opt.
Toolbox
A maioria destas rotinas de otimização exigem a definição de um
M- arquivo que contém a função , f, a ser minimizada.
A maxização de funções é conseguida minimizando –f.
Opções de otimização são passadas para os algoritmos do Opt.
Toolbox.
Os parâmetros default da otimização podem ser mudados em uma
estrutura propria .
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Unconstrained Minimization
Considere o problema de encontrar um conjunto de valores [x1 x2]T que
resolva
x
~
min f x e x1 4 x12 2 x22 4 x1 x2 2 x2 1
~
x x1 x2
T
Passos:
• Criar um M-file que retorna o valor da função(Objective
Function). Chame-a de objfun.m
• Então chamar a rotina de minimização. Use fminunc,
fminsearch, etc…
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Passo 1 – Obj. Function
x x1 x2
T
~
function f = objfun(x)
f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
Objective function
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Passo 2 – a rotina
Ponto Inicial
x0 = [-1,1]; Configuração de parametros na variável option
options = optimset(‘LargeScale’,’off’);
[xmin,feval,exitflag,output]=
fminunc(‘objfun’,x0,options);
Argumentos de Sáida
Argumentos de entrada
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Resultados
xmin =
0.5000 -1.0000 Minimum point of design variables
feval =
1.3028e-010 Objective function value
exitflag =
1 Exitflag tells if the algorithm is converged.
If exitflag > 0, then local minimum is found
output =
iterations: 7
funcCount: 40
stepsize: 1 Some other information
firstorderopt: 8.1998e-004
algorithm: 'medium-scale: Quasi-Newton line search'
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Mais sobre a entrada da fminunc
[xmin,feval,exitflag,output,grad,hessian]=
fminunc(fun,x0,options,P1,P2,…)
fun : A função objetivo.
x0 : Um ponto de partida. Deve ser um vetor que possuí o
mesmo número de variaveis consideradas na otimização.
Option : Configura a otmização
P1,P2,… :Passando a parâmetros adicionais.
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
More on fminunc – Output
[xmin,feval,exitflag,output,grad,hessian]=
fminunc(fun,x0,options,P1,P2,…)
xmin : Vector of the minimum point (optimal point). The size
is the number of design variables.
feval : The objective function value of at the optimal point.
exitflag : A value shows whether the optimization routine is
terminated successfully. (converged if >0)
Output : This structure gives more details about the optimization
grad : The gradient value at the optimal point.
hessian : The hessian value of at the optimal point
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Options Setting – optimset
Options =
optimset(‘param1’,value1, ‘param2’,value2,…)
The routines in Optimization Toolbox has a set of default
optimization parameters.
However, the toolbox allows you to alter some of those
parameters, for example: the tolerance, the step size, the gradient
or hessian values, the max. number of iterations etc.
There are also a list of features available, for example: displaying
the values at each iterations, compare the user supply gradient or
hessian, etc.
You can also choose the algorithm you wish to use.
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Options Setting (Cont.)
Options =
optimset(‘param1’,value1, ‘param2’,value2,…)
Type help optimset in command window, a list of options
setting available will be displayed.
How to read? For example:
LargeScale - Use large-scale algorithm if
possible [ {on} | off ]
The default is with { }
Value (value1)
Parameter (param1)
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Options Setting (Cont.)
Options =
optimset(‘param1’,value1, ‘param2’,value2,…)
LargeScale - Use large-scale algorithm if
possible [ {on} | off ]
• Since the default is on, if we would like to turn off, we just type:
Options = optimset(‘LargeScale’, ‘off’)
Agora as entradas da fminuc.
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Useful Option Settings
Highly recommended to use!!!
Display - Level of display [ off | iter | notify | final ]
MaxIter - Maximum number of iterations allowed [ positive integer ]
TolCon - Termination tolerance on the constraint violation [
positive scalar ]
TolFun - Termination tolerance on the function value [ positive
scalar ]
TolX - Termination tolerance on X [ positive scalar ]
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
fminunc and fminsearch
fminunc uses algorithm with gradient and hessian information.
Two modes:
• Large-Scale: interior-reflective Newton
• Medium-Scale: quasi-Newton (BFGS)
Not preferred in solving highly discontinuous functions.
This function may only give local solutions..
fminsearch is generally less efficient than fminunc for
problems of order greater than two. However, when the problem
is highly discontinuous, fminsearch may be more robust.
This is a direct search method that does not use numerical or
analytic gradients as in fminunc.
This function may only give local solutions.
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Minimização com restrições Multiplicadores de
Lagrange
[xmin,feval,exitflag,output,lambda,grad,hessian]
=
fmincon(fun,x0,A,B,Aeq,Beq,LB,UB,NONLCON,options,
P1,P2,…)
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Exemplo
function f = myfun(x)
x
~
min f x x1 x2 x3
~
f=-x(1)*x(2)*x(3);
Sujeito à: 2 x12 x2 0
x1 2 x2 2 x3 0
x1 2 x2 2 x3 72
0 x1 , x2 , x3 30
0 30
1 2 2 0
A , B LB 0 , UB 30
1 2 2 72
0 30
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Example (Cont.)
Para
2 x12 x2 0
Crie um função nonlcon que retorna dois vetores [C,Ceq]
function [C,Ceq]=nonlcon(x)
C=2*x(1)^2+x(2); Remember to return a null
Ceq=[]; Matrix if the constraint does
not apply
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Example (Cont.)
Initial guess (3 design variables)
1 2 2 0
x0=[10;10;10]; A , B
1 2 2 72
A=[-1 -2 -2;1 2 2];
0 30
B=[0 72]';
LB = [0 0 0]';
LB 0 , UB 30
UB = [30 30 30]'; 0 30
[x,feval]=fmincon(@myfun,x0,A,B,[],[],LB,UB,@nonlcon)
CAREFUL!!!
fmincon(fun,x0,A,B,Aeq,Beq,LB,UB,NONLCON,options,P1,P2,…)
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Exemplo(Cont.)
Warning: Large-scale (trust region) method does not currently solve this type of problem, switching to
medium-scale (line search).
>
Optimization terminated successfully:
Magnitude of directional derivative in search direction less than 2*[Link] and maximum constraint
violation is less than [Link]
x1 2 x2 2 x3 0 Const. 1
Active Constraints:
2 x1 2 x2 2 x3 72 Const. 2
9
x=
Const. 3 0 x1 30 Const. 5
0.00050378663220
0.00000000000000
Const. 4 0 x2 30 Const. 6
Const. 7
30.00000000000000
0 x3 30 Const. 8
feval = 2 x12 x2 0 Const. 9
-4.657237250542452e-035
Sequence: A,B,Aeq,Beq,LB,UB,C,Ceq
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Set Fitness function to @rastriginsfcn.
Set Number of variables to 2.
Select Best fitness in the Plot functions
pane.
Select Distance in the Plot functions pane.
Set Initial range to [1; 1.1].
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
A = [1,1;-1,2;2,1]; b = [2;2;3]; lb =
zeros(2,1);
options = gaoptimset('PlotFcns',@gaplotshowpopulation2);
[x,fval] = ga(@lincontest6,2,A,b,[],[],lb,[],[],options);
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved
Optimization Toolbox
Fim.
© 2008 Solutions 4U Sdn Bhd. All Rights Reserved