GA-MATLAB-Algoritmos Geneticos

Transcrição

Algoritmos genéticos (Matlab)
MATLAB Optimization Toolbox
Iury Steiner de Oliveira Bezerra
Msc. Iury Steiner
© 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
• Algoritmos Genéticos
Problemas de minimização
• Sem restrições
• Com Restrições
•
•
Msc. Iury Steiner
Exemplos
Descrição do algoritmo
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:

g  x  0
~
~
hi x  0 Restrições de igualdade
~
j
~
Restrições de desigualdade
x L k  xk  xU k Restrições de fronteira
Where:

f x
~
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.
é um vetor coluna de variáveis consideradas, que pode
afetar o desempenho da otimização.
Function Optimization (Cont.)
 Restrições – Delimitação do espaço de soluções viávies .
Podem ser basicamente lineares e não lineares

g  x  0
hi x  0
Restrições de igualdade
~
j
Restrições de desigualdades
~
Muitos algoritmos necessitam dessa condição
x L k  xk  xU k
Msc. Iury Steiner
Restrições de fronteira ou domínio
 É 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 e curve fitting
• Nonlinear systems of equations solving
• Constrained linear least squares
•Algoritmos para problemas em larga escala
Algoritmos de minimização
Msc. Iury Steiner
Algoritmos de minimização
(Cont.)
Msc. Iury Steiner
Algoritmos para resolver
equações
Algoritmos de mínimimos
quadrados
Msc. Iury Steiner
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 .
Msc. Iury Steiner
Unconstrained Minimization
 Considere o problema de encontrar um conjunto de valores [x1 x2]T que
resolva

min f x  e x1  4 x12  2 x22  4 x1 x2  2 x2  1
x
~
~
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…
Msc. Iury Steiner
Passo 1 – Obj. Function
x   x1
function f = objfun(x)
~
x2 
T
f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
Objective function
Msc. Iury Steiner
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
Msc. Iury Steiner
Argumentos de entrada
Resultados
xmin =
0.5000
-1.0000
Minimum point of design variables
feval =
1.3028e-010
Objective function value
exitflag =
Exitflag tells if the algorithm is converged.
If exitflag > 0, then local minimum is found
1
output =
iterations: 7
funcCount: 40
stepsize: 1
Some other information
firstorderopt: 8.1998e-004
algorithm: 'medium-scale: Quasi-Newton line search'
Msc. Iury Steiner
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.
Mais sobre fminunc – Output
[xmin,feval,exitflag,output,grad,hessian]=
fminunc(fun,x0,options,P1,P2,…)
xmin
:O vetor é o vetor ponto de mínimo.
feval
:O valor da função objetivo no ponto de minimo.
exitflag
:Esse flag mostra se ocorreu tudo bem.
Output
: É uma estrutura que mostra detalhes sobre a otimização
grad
: O valor do gradient no ponto de ótimo.
hessian
: A matriz hessiana no ponto de mínimo.
Msc. Iury Steiner
Options Setting – optimset
Options =
optimset(‘param1’,value1, ‘param2’,value2,…)
 As rotinas no Optimization tem um conjunto de parametros
default;
 Mas, é permitido que o usuário altere alguns desses parametros;
 É possível consultar uma lista desses parametros com o Help;
 É possível escolher o algortimo a ser utilizado.
Msc. Iury Steiner
Options Setting (Cont.)
Options =
 Digite help optimset no command window, uma lista de opções
será mostrada.
 Por exemplo:
LargeScale - Use large-scale algorithm if
possible [ {on} | off ]
The default is with { }
Value (value1)
Parameter (param1)
Options Setting (Cont.)
Options =
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.
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 ]
Msc. Iury Steiner
fminunc and fminsearch
 fminunc usa algoritmos com informação de gradiente e
hessiana.
 Dois modos:
• Large-Scale: interior-reflective Newton
• Medium-Scale: quasi-Newton (BFGS)
 Não são preferiveis quando a função é descontinua em alguns
pontos.
 Apenas fornece soluções locais..
 fminsearch é menos eficiente do que fminunc. Mas, quando o
problema é descontínuo, fminsearch pode ser mais robusto.
 Esse é um método de busca direta que não usa gradintes nem
informações analíticas.
 Está função também fornece apenas soluções locais.
Msc. Iury Steiner
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,…)
Msc. Iury Steiner
Exemplo
function f = myfun(x)

min f x   x1 x2 x3
x
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
 1 2 2
0
A
, B 

1 2 2
72
0
30
LB  0 , UB  30
0
30
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);
Ceq=[];
Lembrar de sempre retornar
null para o Ceq.
Example (Cont.)
Ponto Inicial (3 parâmetros Livres)
x0=[10;10;10];
A=[-1 -2 -2;1 2 2];
B=[0 72]';
LB = [0 0 0]';
UB = [30 30 30]';
 1 2 2
0
A
, B 

1 2 2
72
0
30
LB  0 , UB  30
0
30
[x,feval]=fmincon(@myfun,x0,A,B,[],[],LB,UB,@nonlcon)
Cuidado com isso!!!
fmincon(fun,x0,A,B,Aeq,Beq,LB,UB,NONLCON,options,P1,P2,…)
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*options.TolFun and maximum constraint
violation is less than options.TolCon
Const. 1
 x1  2 x2  2 x3  0
Active Constraints:
2
9
x=
0.00050378663220
0.00000000000000
30.00000000000000
feval =
-4.657237250542452e-035
Const. 3
x1  2 x2  2 x3  72 Const. 2
Const. 5
0  x1  30
Const. 4
0  x2  30
Const. 7
0  x3  30
2 x12  x2  0
Const. 6
Const. 8
Const. 9
Sequence: A,B,Aeq,Beq,LB,UB,C,Ceq
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].
Usando o gaToolbox no Matlab
Para usar o Algoritmo Genético do Optimtool,
deve-se selecionar GA – na caixa de solver.
(proximo slide slide)
Para usar o Algoritmo Genético do Optimtool
por linha de comando
X = GA(FITNESSFCN,NVARS)
X = GA(FITNESSFCN,NVARS,A,b)
X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq)
X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub)
X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON)
X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON,options)
options = gaoptimset('PlotFcns',...
{@gaplotbestf});
[x,fval,exitflag,output] = ga(@rastriginsfcn,2,[],[],[],[],[],[],[],options)
[x,y]=meshgrid(-10:0.05:10,-10:0.05:10);
f6=@(x,y)0.5-((sin(sqrt(x.^2+y.^2)).^2)- 0.5)./((1+0.001.*(x.^2+y.^2)).^2);
z=f6(x,y);
figure,mesh(x,y,z)
Restrições lineares para o Algoritmo Genético
A = [1,1;-1,2;2,1]; b = [2;2;3]; lb =
zeros(2,1);
[x,fval] = ga(@lincontest6,2,A,b,[],[],lb,[],[],options);
Restrições não-lineares para o Algoritmo
Genético por linha de comando
Restrições não-lineares
function y = funcao_fitness(x)
y = 100*(x(1)^2 - x(2))^2 + (1 - x(1))^2;
end
function [c, ceq] = funcao_restricoes(x)
c = [1.5 + x(1)*x(2) + x(1) - x(2);...
-x(1)*x(2) + 10];
ceq = [];
end
ObjectiveFunction = @ funcao_fitness ;
nvars = 2; % Numero de Variáveis
LB = [0 0]; % mínimo do espaço de busca
UB = [1 13]; % maximo do espaço de busca
ConstraintFunction = @ funcao_restricoes;
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction)
Acessando os parâmetros do Algoritmo Genético
options = gaoptimset('MutationFcn',@mutationadaptfeasible);
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction,options)
Um estudo de caso
Nosso exemplo
•
•
É estudado em programação matemática
•
•
É um problema de otimização.
É um dos modelos utilizados em pesquisa
operacional.
Tem como objetivo:
•
"Alocar recursos escassos (ou limitados) a atividades
em concorrência (em competição)"
Msc. Iury Steiner
Uma empresa pode fabricar dois produtos (1 e 2).
•
Na fabricação do produto 1 a empresa gasta nove horashomem e três horas-máquina (a tecnologia utilizada é
intensiva em mão-de-obra).
•
Na fabricação do produto 2 a empresa gasta uma horahomem e uma hora-máquina (a tecnologia é intensiva em
capital).
•
A empresa dispõe de 18 horas-homem e 12 horas-máquina
para um período de produção.
•
Sabe-se que os lucros líquidos dos produtos são $4 e $1
respectivamente.
Msc. Iury Steiner
Pergunta-se
• Quanto
a empresa deve fabricar de
cada produto para ter o maior lucro?
• Caso
se obtenha algum recurso
financeiro externo, para investimento
em expansão, em quais dos recursos a
empresa deveria aplicá-lo ?
• Qual seria o impacto no lucro se alguns
trabalhadores faltassem ao trabalho
limitando as horas homens disponíveis
em 15 horas?
Msc. Iury Steiner
Pergunta-se
• Sabendo-se
que 4 máquinas são
responsáveis pela produção no período
em análise até quanto se deveria pagar
pelo aluguel de uma máquina se
eventualmente
uma
das
quatro
máquinas quebrassem?
• Qual
deveria ser o lucro líquido
fornecido para viabilizar a fabricação
um novo produto que utiliza 5 horas de
cada recurso?
Msc. Iury Steiner
Resolvendo Intuitivamente
• Que modelo mental poderia ser usado?
• Como se poderia utilizar a intuição para
responder as perguntas?
• Tente resolver o problema sem utilizar um
modelo formal.
Msc. Iury Steiner
Transformando os dados em
expressões matemáticas
•
A função lucro
•
•
•
Não havendo economia de escala
É claro que o lucro máximo seria ilimitado se não
fosse a escassez de recursos.
Em outros problemas a demanda do mercado
também é um fator limitador.
L  4 x1  x2
Transformando os dados em
expressões matemáticas
•
As restrições
•
•
•
Não se pode utilizar o que não se tem!
A quantidade utilizada deve ser menor ou igual a
quantidade disponível.
As quantidades de fabricação devem ser não
negativas
H .H . 9 x1  x2  18
H .M . 3x1  x2  12
x1  0 x2  0
O modelo do problema
Função Objetivo
L  4 x1  x2
Max
x1 ,x2
Matriz
Tecnológica
Variáveis de Decisão
H .H .
H .M .
Conjunto das
Possibilidades de
Produção
9 x1  x2  18
3x1  x2  12
x1  0
Limitações
x2  0
Solução Gráfica: Construindo o
conjunto de possibilidades
x2
Valores Possíveis quando
x1  0
0
x2  0
x1
18
x2
9 x1  x2  18
9 x1  x2  18
2
0
x1
x2
12
3x1  x2  12
3x1  x2  12
4
0
x1
x2
12
Conjunto
de Possibilidades
0
2
x1
Solução Gráfica: Definindo as Curvas
de Níveis do Objetivo
• Para cada valor de L tem-se uma reta no
plano (x2 vs x1).
• Dado um valor de L é possível traçar um
lugar geométrico (uma reta) onde as várias
combinações de produção dão o mesmo
lucro, essas curvas são conhecidas como
isolucros.
4 x1  x2  L  x2  4 x1  L
Retas com inclinações negativas
Solução Gráfica: Desenhando as
Curvas de Níveis do Objetivo
x2
L9
L7
L5
0
Direção de
Crescimento do Lucro
x1
Solução Gráfica: Reunindo os
componentes e resolvendo
x2
12
L  13
9
Conjunto
de Possibilidades
0
1
2
x1
A solução
•
Que características permitiram a solução?
•
•
•
•
O conjunto de possibilidades era convexo.
Um conjunto é convexo quando toda combinação
convexa de dois elementos dele pertence a ele.
Uma combinação convexa de dois elementos, x e y é
um terceiro elemento z tal que: z=a.x+(1-a).y onde 0
 a  1.
É possível definir combinação convexa de n
elementos.
Casos onde a solução não existe
•
•
•
Conjunto de Possibilidades é vazio
Não há solução compatível
Exemplo:
x2
Valores p/
Restrição 1
Valores p/
Restrição 2
0
x1
Casos onde a solução não existe
•
•
•
A solução é ilimitada
Não há como definir a decisão
Exemplo:
x2
Direção de
Crescimento
do Lucro
Conjunto de
Possibilidades
0
x1
Caso de Infinitas Soluções
x2
As soluções
são
combinações
lineares dos
pontos
extremos
0
Conjunto
de Possibilidades
Isolucro
x1
Exercícios: Resolva
1.
Maximize o lucro
Sujeito a:
L  2 x1  3x2
 x1  x2  4
x1  2 x2  6
x1  3 x2  9
x1  0; x2  0
Exercícios: Resolva
2.
Maximize a receita
Sujeito a:
R  0,3x1  0,5x2
2 x1  x2  2
x1  3x2  3
x1  0; x2  0
Exercícios: Resolva Graficamente
3.
Maximize o lucro
Sujeito a:
L  2 x1  3x2
 x1  2 x2  4
x1  x2  6
x1  3 x2  9
x1  0; x2  0
4.
Duas fábricas produzem três tipos de papel. A
companhia que controla as fábricas tem um
contrato para produzir 16 toneladas de papel fino,
6 toneladas de papel médio e 28 toneladas de
papel grosso. Existe uma demanda para cada tipo
de papel . O custo de produção na 1ª fábrica é de
R$1.000,00 e o da 2ª é de R$2.000,00, por dia. A
primeira fábrica produz 8 toneladas de papel fino, 1
tonelada de papel médio e 2 toneladas de papel
grosso por dia, enquanto a segunda produz 2
toneladas de papel fino, 1tonelada de papel médio
e 7 toneladas de papel grosso. Quantos dias cada
fábrica deve operar para suprir os pedidos com o
menor custo?
5.
Uma companhia de transporte tem dois tipos de
caminhões: O tipo A tem 2m3 de espaço
refrigerado e 3m3 de espaço não refrigerado; o
tipo B tem 2m3 de espaço refrigerado e 1m3 de
não refrigerado. O cliente quer transportar
produtos que necessitarão de 16m3 de espaço
refrigerado e 12m3 de área não refrigerada. A
companhia calcula que são necessários em
1.100 litros de combustível para uma viagem com
o caminhão A e 750 litros para o caminhão B.
Quantas viagens deverão ser feitas de cada tipo
de caminhão para que se tenha o menor custo de
combustível?
Msc. Iury Steiner
Voltando ao Primeiro Problema
Max
x1 ,x2
H .H .
H .M .
L  4 x1  x2
9 x1  x2  18
3x1  x2  12
x1  0
x2  0
Lembrando que foi resolvido graficamente,
analise.......
Msc. Iury Steiner
Fim.

GA-MATLAB-Algoritmos Geneticos

Transcrição

Documentos relacionados

production central new york san francisco woody woodpecker`s

PDF Texas Instruments

PDF Texas Instruments

Jacarta Doeloe ritmo

Como enfrentar a crise com soluções Inteligentes

Prefácio .......................................................... vii Assim

Kalahari

3M - Sementes da Inovação

click here to the PDF file. - SRF Bookstore

Redes Sem Fio e SDN Áreas de Atuação