Aula_Particle_Swarm

Prévia do material em texto

Particle Swarm Optimization
Análise, Simulação e Controle de Processos 
LUCAS LIMA PROVENSI
MÉTODOS DE OTIMIZAÇÃO
O que são métodos de otimização ?
MÉTODOS DE OTIMIZAÇÃO
O que são métodos de otimização ?
Métodos de otimização são um atalho que garantem um resultado ótimo do problema proposto, sem ter que testar todos os resultados possíveis
COMPUTAÇÃO NATURAL
De acordo com Ballard (1999):
Todos os sistemas computacionais desenvolvidos com inspiração ou utilização de algum mecanismo natural ou biológico de processamento de informação.
COMPUTAÇÃO NATURAL
Computação
Natural
Computação inspirada na natureza
Simulação ou Emulação de Fenômenos Naturais
Computação utilizando meios naturais
- Computação Evolutiva
- Inteligência Coletiva
- Redes Neurais
- Geometrias Fractais
- Computação Quântica
COMPUTAÇÃO NATURAL
Computação
Natural
Computação inspirada na natureza
Simulação ou Emulação de Fenômenos Naturais
Computação utilizando meios naturais
- Computação Evolutiva
- Inteligência Coletiva
- Redes Neurais
- Geometrias Fractais
- Computação Quântica
EXEMPLO
Vamos supor um problema genérico de mercado financeiro, vamos supor que tenho alguns países no mundo para fazer investimentos, dentre desses países existem várias opções de investimentos, e dentre essas opções de investimentos, há várias taxas de juros diferentes e formas diferentes de investimento. Além disso vamos supor que temos dinheiro para fazer alguns investimentos e queremos ter o melhor lucro possível, ou seja, o melhor retorno financeiro possível. Como que os algoritmos de evolução e de inteligência coletiva vão se comportar para resolver este problema?
EXEMPLO
Computação Evolutiva
EXEMPLO
Computação Evolutiva
EXEMPLO
Inteligência Coletiva
EXEMPLO
Inteligência Coletiva
COMENTÁRIO
Tese de doutorado do Prof. Dr. Rafael Krummenauer do DEQ utilizando Redes Neurais.
Otimização Computacional
Computação Natural
Inspirada na Natureza
Inteligência Coletiva
Particle Swarm
RESUMO
PARTICLE SWARM
Aplicações
Esse método possuí aplicações nas mais diversas áreas como por exemplo, pode ser utilizado para simulação de módulos fotovoltaicos, pode ser utilizado como ferramenta para fazer imageamento sísmico do solo, pode ser utilizado para problemas de mercado financeiro e etc.
PARTICLE SWARM
O que é o Particle Swarm Optimization?
É um método de otimização computacional criado por KENNEDY e EBERHART em 1995.
Engenheiro Eletricista
Psicólogo Social
PARTICLE SWARM
Qual a ideia por traz do Particle Swarm?
Alguns benefícios da vida em grupo sociais:
Aumenta probabilidade de acasalamento;
Facilita	 a caça e coleta de alimentos;
Reduz a probabilidade de ataque de predadores;
Permite a divisão do trabalho;
PARTICLE SWARM
Propriedades da inteligência coletiva:
Proximidade: Os agentes devem ser capazes de interagir entre si;
Qualidade: Os agentes devem ser capazes de avaliar seus comportamentos;
Diversidade: Permite ao sistema reagir a situações inesperadas;
Estabilidade: Nem todas as variações ambientais devem afetar o comportamento do agente;
Adaptabilidade: Capacidade de se adequar a variações ambientais.
PARTICLE SWARM
PARTICLE SWARM
De acordo com White e Pagurek (1998):
	O termo inteligência de enxame (swarm intelligence) refere-se a uma propriedade de sistemas compostos por agentes não (ou pouco) inteligentes e com capacidade individual limitada, capazes de apresentar comportamentos coletivos inteligentes.
PARTICLE SWARM
O que é o Particle Swarm Optimization?
	A ideia do método é reproduzir no computador a forma pelas quais as sociedades processam o conhecimento, ou seja em outras palavras é uma meta-heurística populacional que baseia-se na interação social e adaptação.
PARTICLE SWARM
Para computação este processo de adaptação e interação social consiste em duas componentes.
Uma de baixo nível de programação que é o comportamento real do individuo.
Outra de alto nível de programação que é devido a interação e comparação do individuo com a vizinhança.
As palavras chaves são Autoavaliação, comparação, imitação/interação.
PARTICLE SWARM
Em resumo cada partícula consegue aprender por suas experiências do passado e pelas experiências de outros indivíduos (vizinhança). 
PARTICLE SWARM
D é a dimensão do problema [número de variáveis];
Pop é população, que é o conjunto de candidatos para a solução;
Para o Particle Swarm, individuo = partícula;
Np é o número de indivíduos da população;
f é a função fitness, ou seja, o critério de avaliação dos indivíduos, pode ser chamada de função aptidão;
Nomenclaturas
PARTICLE SWARM
P é a posição que a partícula se encontra em relação ao melhor resultado;
V é a velocidade com que a partícula muda de posição;
Pi é a melhor posição já visitada pelo individuo ;
Pg é a melhor posição até o momento de qualquer um dos indivíduos da vizinhança.
Nomenclaturas
EXEMPLO NO QUADRO
X
Y
A
B
C
D
E
EXEMPLO NO QUADRO
Primeiro passo é gerar a população inicial, de forma aleatória;
EXEMPLO NO QUADRO
A partir desse momento entra em um looping até o critério de parada ser atingido.
Valendo um chocolate que critérios de paradas poderiam ser feitos neste problema?
EXEMPLO NO QUADRO
Agora o próximo passo é calcular a função fitness para cada um dos indivíduos.
Valendo um chocolate qual seria uma função fitness para este problema?
EXEMPLO NO QUADRO
Atualizar a melhor posição já visitada de cada partícula [Pi].
A cada iteração, a posição de cada individuo pode mudar, e pode acontecer que em uma próxima interação a partícula vá para uma posição mais longe do resultado ótimo. A longo prazo, na maioria das vezes, isso se auto corrige, pois o individuo se auto avalia nas iterações passadas e se baseia na sua melhor posição até o momento que é chamada de Pi.
EXEMPLO NO QUADRO
Atualizar a melhor posição até o momento entre todas as partículas que é chamada de Pg.
Agora o próximo passo é atualizar a velocidade de cada partícula da seguinte forma:
EXEMPLO NO QUADRO
Sejam ψ1 e ψ2 vetores aleatórios positivos cujos elementos são gerados a partir de uma distribuição uniforme com limitante superior pré-definido: ψ1 ∼ U(0, L1) e ψ2 ∼ U(0, L2), sendo que L1 e L2 são denominados constantes de aceleração.
Na literatura encontramos que L1 = L2 = 2,05, é uma boa constante para o método.
EXEMPLO NO QUADRO
A atulização da velocidade fica:
V(t + 1) = V(t) + ψ1⨀ (Pi(t) − P(t)) + ψ2 ⨀ (Pg(t) − P(t));
Podemos limitar a velocidade V(t+1) ~ [Vmin, Vmáx], ou utilizar um fator de constrição [R] que é responsável por não deixar a velocidade crescer muito, a atualização da velocidade utilizando esse fator fica:
V(t + 1) = R ∙[V(t) + ψ1⨀ (Pi(t) − P(t)) + ψ2 ⨀ (Pg(t) − P(t))];
Na literatura encontramos R = 0,729 como um bom fator de constrição;
EXEMPLO NO QUADRO
O próximo passo é atualizar a posição de cada partícula da seguinte forma:
P(t+1) = P(t)+ V(t+1)
Após isso salvar o melhor resultado já encontrado e repetir as iterações do looping até o critério de parada ser satisfeito.
PSEUDO CÓDIGO FICA
EXERCÍCIO
Utilizar o Particle Swarm para encontrar o ponto máximo da curva F(x,y) no intervalo de x ~[-1,2] e y~[-1,2], onde:
F(x,y) = x * sen(4 π x) - y* sen(4 π y + π) + 1;
Relacionar cada parte do algoritmo feito no Matlab com o Pseudo Código deste slide.
Avaliar o que acontece se aumentar o número de individuos da população no inicio do problema.