Nono Simpósio de Mecânica Computacional
26 a 28 de maio de 2010
Universidade Federal de São João Del-Rei – MG
Associação Brasileira de Métodos Computacionais em Engenharia
Solução de Problemas de Otimização com Restrições via um Algoritmo
Bio-inspirado utilizando uma Estratégia de Penalização Adaptativa
A.F. Silva1; B.S.L.P. Lima1; B.P. Jacob1; A.C.C. Lemonge2; H.J.C. Barbosa3
1
Programa de Engenharia Civil, COPPE/Universidade Federal do Rio de Janeiro
Cidade Universitária - Centro de Tecnologia - Bloco B, sala B 101
Ilha do Fundão, 21945-970, Rio de Janeiro - RJ - Brasil
e-mail: [email protected] , [email protected] , [email protected]
2
Departamento de Mecânica Aplicada e Computacional,
Universidade Federal de Juiz de Fora
Cidade Universitária – Faculdade de Engenharia, 36036-330, Juiz de Fora, MG, Brasil
e-mail: [email protected]
3
Laboratório Nacional de Computação Científica, LNCC
Av. Getúlio Vargas, 333, 25651-075, Petrópolis, RJ, Brasil
e-mail: [email protected]
Resumo. A utilização de algoritmos bio-inspirados vem se expandindo ao longo
dos anos, em especial a utilização da técnica de Enxame de Partículas conhecida como
PSO (Particle Swarm Optimization), para a solução de problemas de otimização. O PSO é
considerado um algoritmo robusto, eficiente e competitivo perante os demais algoritmos
populacionais bio-inspirados além de ser de fácil implementação computacional. O PSO
não necessita de funções objetivo que sejam deriváveis nem a introdução de
conhecimentos específicos sobre os problemas a serem otimizados. Neste trabalho, são
analisados alguns problemas de otimização que são funções matemáticas com restrições
onde um PSO clássico os trata como sendo sem restrições através da introdução de um
esquema de penalização adaptativo – APM (Adaptive Penalty Method). O APM foi
originalmente desenvolvido para a aplicação em problemas de otimização com restrições
utilizando algoritmos genéticos e tem demonstrado ser robusto e eficiente. Ele trata
restrições de igualdade e desigualdades; não demanda o conhecimento explícito das
restrições como funções das variáveis do problema; é livre de parâmetros a serem
definidos pelo usuário e; é de fácil implementação computacional. Neste artigo são
avaliados problemas de otimização com restrições usando-se o APM e suas variantes
propostas recentemente.
Palavras chaves: Otimização, PSO, Restrições
Nono Simpósio de Mecânica Computacional
1
Universidade Federal de São João Del-Rei – MG – ABMEC
INTRODUÇÃO
A técnica de otimização através de enxame de partículas foi desenvolvida por Kennedy
e Eberhart (1995) e se baseia no processo de busca de alimento descrito por um conjunto
de pássaros. Esta técnica é utilizada para a solução de problemas de otimização sem
restrições, mas também pode ser aplicada a problemas de otimização com restrições.
Vários problemas clássicos de otimização com restrições nas áreas de engenharia e
matemática aplicada vem sendo estudados utilizando-se diversas técnicas encontradas na
literatura onde um dos objetivos é minimizar o custo computacional necessário para a
localização da solução ótima.
Uma das formas mais comuns de tratar os problemas com restrições é a de transformálos em problemas sem restrições através da introdução de uma função de penalidade. No
entanto, a tarefa de se obter uma função de penalidade que seja adequada é, por vezes,
árdua e ainda, tornar esta função com pouca dependência de parâmetros externos é bastante
complexo.
Este artigo objetiva a utilização de uma técnica de penalização adaptativa que
independe de valores a serem fornecidos pelo usuário, sugerida por Lemonge e Barbosa
(2004), e que se ajusta através do comportamento da população no espaço de busca ao
longo das gerações. Ainda, pretende-se mostrar uma análise comparativa desta técnica com
suas variações recentemente desenvolvidas e apresentadas em Barbosa e Lemonge (2008).
Este artigo está dividido da seguinte forma: a seção 2 descreve algumas características
da otimização inspirada em enxame de partículas e a estratégia de penalização adaptativa
usado no algoritmo, na seção 3 são apresentados e discutidos os experimentos numéricos e,
finalmente, a seção 4 apresenta as conclusões e trabalhos futuros.
2
OTIMIZAÇÃO POR ENXAME DE PARTÍCULAS
A otimização inspirada em enxame de partículas mais conhecida pela sigla PSO (do
inglês, Particle Swarm Optimization) é uma técnica de busca originalmente desenvolvida
por Kennedy e Eberhart (1995). O processo de busca foi baseado no comportamento social
de grupos de indivíduos, no caso inicial, de pássaros. Quando os pássaros iniciam sua
revoada em busca de alimento, por exemplo, esta busca é aleatória e, a princípio,
desordenada. Ao longo do tempo, percebe-se uma organização no vôo e um padrão de
busca sendo demonstrado. Caso o alimento seja encontrado espera-se que todo o bando se
dirija para este.
A partir das observações feitas neste processo, Kennedy e Eberhart (1995)
desenvolveram esta técnica onde os pássaros são considerados partículas em um espaço de
busca multidimensional e o objetivo a ser alcançado é um ponto neste espaço, no caso de
otimização de funções, o ponto ótimo.
O PSO é um algoritmo populacional que têm a inicialização da população feita de
forma aleatória tanto quanto os algoritmos genéticos citados em Davis (1991) e a técnica
ACO (do inglês, Ant Colony Optimization) disponível em Colorni et al (1998). Ainda, o
PSO pode ser considerado um algoritmo evolutivo em que, ao longo do tempo, o
posicionamento dos indivíduos ou partículas é atualizado baseado em regras préestabelecidas. As partículas colaboram entre si para a atualização do seu posicionamento
através da utilização função objetivo a ser alcançada como métrica para a avaliação das
posições e definição das melhores partículas.
A utilização desta técnica de otimização tem se mostrado bastante interessante em
diversas aplicações de engenharia como desenho de circuitos lógicos disponível em Coelho
e Luna (2003), projetos de controle citados em Zheng et al. (2003) e ainda, em sistemas de
potência como dito em Abido (2002) dentre outras.
Nono Simpósio de Mecânica Computacional
2.1
Universidade Federal de São João Del-Rei – MG – ABMEC
O ALGORITMO PSO
O algoritmo PSO pode ser considerado simples se comparado a outros algoritmos bioinspirados. Ele se baseia na atualização das velocidades das partículas ao longo do tempo e
conseqüente atualização posicionamento de cada partícula.
xi
vi
Seja k e k os vetores de posição e velocidade de uma partícula i em um tempo k
respectivamente. O algoritmo PSO se baseia em armazenar estes vetores durante o
processamento do algoritmo em uma geração k e utilizados para a atualização da
população na geração k+1.
Para a atualização da população também são necessárias duas informações, a saber: a
i
melhor posição da partícula i ao longo de todo o processo até o momento definida por pk e
a posição da melhor partícula de todo o enxame ao longo do processo até o momento
g
definida por pk .
A atualização da velocidade de cada partícula é dada pela equação (1).
vki +1 = wvki + c1rnd1
( pki − xki )
( p g − xki )
+ c2 rnd 2 k
∆t
∆t
(1)
i
k +1
onde v representa o vetor velocidade da partícula i tempo k+1, w é o fator de inércia,
rnd1 e rnd2 são duas variáveis aleatórias e independentes de distribuição uniforme entre 0 e
1, c1 e c2 são parâmetros de confiança do enxame em relação ao posicionamento da
partícula i e em relação ao posicionamento da melhor partícula do enxame até o momento
em todo o processo, respectivamente. ∆t é o espaço de tempo que neste trabalho será
utilizado como tendo valor unitário.
A atualização do posicionamento de cada partícula, a partir da velocidade atualizada, é
dada pela equação (2).
xki +1 = xki + vki +1∆t
(2)
O algoritmo PSO básico, utilizado para problemas sem restrições, pode ser definido
conforme a descrição textual abaixo:
1. Inicializar um conjunto de partículas em um tempo k=0 com velocidades e
posições aleatoriamente distribuídas dentro do espaço de busca;
2. Avaliar a função objetivo de cada uma das partículas da população;
3. Atualizar a melhor posição de cada partícula individualmente e a melhor posição
do bando;
4. Atualizar a posição de cada partícula no tempo k+1 baseado na posição e
velocidade no tempo k;
5. Repetir os processos de 2 a 4 até que uma condição de parada seja satisfeita.
O conjunto inicial de partículas é gerado de forma aleatória e independente espalhado
pelo espaço de busca conforme as equações (3) e (4):
x0i = xmin + rnd 3 ( xmax − xmin )
(3)
v0i = xmin + rnd 4 ( xmax − xmin )
(4)
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
i
i
Onde x0 e v0 são, respectivamente, os vetores posição e velocidade inicial da partícula
i, rnd3 e rnd4 são variáveis aleatórias independentes de distribuição uniforme entre 0 e 1,
xmin e xmax são os vetores que contém os limites inferior e superior da para x,
respectivamente.
O algoritmo PSO é considerado bastante eficiente para tratar problemas de otimização
sem restrições, mas não apresenta uma técnica ou estratégia adequada para tratar
problemas com restrições assim como os demais algoritmos bio-inspirados. A estratégia
mais comum utilizada para dar capacidade ao PSO de processar problemas com restrição é
transformá-los em problemas sem restrições através a introdução de estratégias para o
tratamento destas. As mais conhecidas são i) técnicas que preservam a viabilidade das
soluções; ii) técnicas baseadas em funções de penalização; iii) técnicas que reparam
soluções inviáveis; iv) técnicas para a separação de soluções viáveis das inviáveis, dentre
outras.
Parsopoulos e Vrahatis (2002) alteram o algoritmo PSO adotando-se uma função de
penalização multi-estágio e não-estacionária. Já em Ray e Liew (2001) sugere-se a
utilização de um ordenamento utilizando-se um conjunto de Pareto tratando as restrições
como uma matriz para se localizar uma BPL (Best Performance List). Outra abordagem
também pode ser encontrada em Zavala et al. (2005).
Hu, Eberhart e Shi (2003) apresentam uma estratégia para tratamento das restrições
onde são propostas modificações no algoritmo em que a população inicial deve possuir
todas as partículas factíveis e durante a atualização das memórias, também, são mantidas
somente as soluções factíveis.
Descrições de várias técnicas de penalização podem ser encontradas em Coello (2002).
Dentre as diversas técnicas apresentadas na literatura, uma comumente utilizada é a que
considera uma função de penalização, que pode ser aditiva ou multiplicativa, sobre o valor
da função objetivo. Dessa forma, a aptidão ou fitness de cada partícula pode ser escrita
como exporto na equação (5).
F ( x) = f ( x ) + hP ( x )
2.2
onde
P(x ) = 0 se x for factível ou
P(x ) > 0 caso contrário
(5)
PENALIZAÇÃO ADAPTATIVA
Em Lemonge e Barbosa (2002) é proposto o APM (do inglês, Adaptative Penalty
Method). O APM foi desenvolvido para a aplicação de problemas com restrições
analisados via algoritmos genéticos e tem demonstrado ser robusto e eficiente. Ele trata
restrições de igualdade e desigualdades; não demanda o conhecimento explícito das
restrições como funções das variáveis do problema; é livre de parâmetros a serem
definidos pelo usuário e; é de fácil implementação computacional.
A aptidão ou fitness F (x ) de cada partícula, com a utilização do APM, é obtida através
da equação (6).
se x for factível
 f ( x)

m
F ( x) = 
f
(
x
)
h j z j ( x) caso contrário
+
∑

j =1

onde
(6)
Nono Simpósio de Mecânica Computacional
 f ( x)
f ( x) = 
 f ( x)
Universidade Federal de São João Del-Rei – MG – ABMEC
se f ( x) > f ( x)
caso contrário
f (x)
Sendo
a média da função objetivo para a população na iteração atual, zj a
violação da restrição j sobre a população atual e hj o fator de penalização é calculado de
forma adaptativa conforme a equação (7).
h j = f ( x)
z j ( x)
∑ [ z ( x) ]
m
l =1
2
l
(7)
A Figura (1), retirada de Lemonge e Barbosa (2002) demonstra a determinação da
função f . O gráfico indica que se uma partícula candidata é infactível (pontos 1, 2, 3, 4, 5
e 6), em um problema de minimização, a sua função objetivo terá o seu valor alterado para
o valor médio da função objetivo em toda população, se esta partícula tiver a função
objetivo original com valor menor que este valor médio. Dessa forma, no exemplo
ilustrativo da Figura (1), os pontos infactíveis, 3, 4, 5 e 6, que tem a função objetivo com
f (x)
valor menor que a média, sofrerão alteração do valor desta função objetivo para
.
Figura 1 - Determinação da função f .
Recentemente em Barbosa e Lemonge (2008) foram apresentadas variantes do APM
que estão descritas de forma sucinta a seguir:
1. APM Esporádico
i. calcular a violação das restrições zj para a população atual;
ii. atualizar os coeficientes de penalidade hj mas;
iii. manter os coeficientes de penalidade hj fixos por f gerações.
2. APM Esporádico com acumulo das violações das restrições
i. acumular a violação das restrições zj por f gerações;
ii. atualizar os coeficientes de penalidade hj;
iii. manter os coeficientes de penalidade hj fixos por f gerações.
3. APM Monotônico
i. nenhum coeficiente de penalidade hj pode ter seu valor reduzido ao
longo das gerações
4. APM com Amortecimento
i. calcular o valor de hj da geração atual e ponderar este com o hj da
geração anterior conforme descrito na equação (8)
Nono Simpósio de Mecânica Computacional
h (j novo ) = θh (j novo ) + (1 − θ )h (j atual )
3
Universidade Federal de São João Del-Rei – MG – ABMEC
onde θ ∈ [0,1]
(8)
DEFINIÇÃO DOS PARÂMETROS PARA O PSO
Para o PSO três parâmetros devem ser definidos a saber: confiança do enxame em
relação ao posicionamento da partícula i, c1, a confiança relação ao posicionamento da
melhor partícula do enxame até o momento, c2, e a inércia w.
Na literatura é possível encontrar várias propostas para a determinação e atualização
dos parâmetros de confiança. Segundo Kennedy e Eberhart (1995) se deve utilizar valores
equilibrados entre c1 e c2. Neste trabalho utiliza-se c1 = 2 e c2 = 1, pois estes valores foram
os que fizeram com que o algoritmo tivesse o melhor desempenho na localização do ótimo
das funções computadas.
Para a inércia w, Eberhart e Shi (1998) sugerem a utilização de um valor fixo.
Embora seja uma estratégia interessante, um valor fixo pode encontrar bons resultados nas
primeiras iterações do algoritmo aumentando a capacidade de exploração do enxame mas,
quando se aproxima do ótimo, este valor fixo pode fazer com que o número de iterações
necessárias para atingi-lo cresça. Assim, Eberhart e Shi (2000) propõem uma variação
linear de w ao longo das iterações do algoritmo. Como o vetor de velocidades é
inicializado aleatoriamente, inicia-se o algoritmo com valores maiores para w com o intuito
de gerar uma busca mais abrangente no espaço. Ao longo das iterações, o valor de w vai
sendo reduzido gradativamente fazendo com que as partículas se fixem no ótimo de forma
mais rápida. A sugestão de Eberhart e Shi (2000) é de se utilizar o valor de inércia w
iniciando em 0,9 e terminando em 0,4.
Outra proposta para a variação da inércia foi apresentada por Chatterjee e Siarry (2004)
onde a variação da inércia é não-linear sendo descrita pela equação (9).
 ( N − k )n 
wk = 
 (wini − w fim ) + w fim
n
 N

(9)
onde wk é o valor da inércia na iteração k, wini e wfim são os valores inicial e final,
respectivamente, N é o número total de iterações e n é o expoente de não linearidade.
Após vários experimentos numéricos, optou-se neste trabalho pela variação não-linear
da inércia no intervalo de 0,4 a 0,9 e com coeficiente de não linearidade 1,2.
4
EXPERIMENTOS NUMÉRICOS
O grupo de funções G, do inglês G-Suite, citados em Koziel e Michalewicz (1999), tem
sido utilizado de forma a validar e comparar o desempenho de algoritmos de otimização.
Optou-se por utilizar este grupo para que fosse possível esta comparação com outros
métodos de otimização de problemas com restrições.
O grupo de funções G é composto por 24 funções. Neste trabalho optou-se por utilizar
as 11 primeiras funções para validação do algoritmo e comparar os resultados com as
mesmas 11 funções apresentadas em Barbosa e Lemonge (2008).
Os limites das variáveis e ótimos conhecidos das funções G estão descritos na Tabela
1.
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
Tabela 1 - Limites das variáveis e ótimo global conhecido das funções G
Função
Limites
G1
0 ≤ xi ≤ 1 (i = 1,...,9,13) 0 ≤ xi ≤ 100 (i = 10,11,12)
0 ≤ xi ≤ 10 (i = 1,...,20)
0 ≤ xi ≤ 1 (i = 1,...,10)
78 ≤ x1 ≤ 102 33 ≤ x 2 ≤ 45 27 ≤ xi ≤ 45 (i = 3,4,5)
0 ≤ xi ≤ 1200 (i = 1,2) − 0,55 ≤ xi ≤ 0,55 (i = 3,4)
13 ≤ x1 ≤ 100 0 ≤ x 2 ≤ 100
− 10 ≤ xi ≤ 10 (i = 1,...,10)
0 ≤ xi ≤ 10 (i = 1,2)
− 10 ≤ xi ≤ 10 (i = 1,...,7)
100 ≤ x1 ≤ 10000 1000 ≤ x2 ≤ 10000 (i = 2,3)
G2
G3
G4
G5
G6
G7
G8
G9
G10
10 ≤ xi ≤ 1000 (i = 4,...,8)
− 1 ≤ xi ≤ 1 (i = 1,2)
G11
Ótimo
Conhecido
-15,0000
-0,8036
-1,0005
-30665,5386
5126,4967
-6961,8138
24,3062
-0,0958
680,6300
7049,2480
0,7499
Foram feitas 30 execuções independentes para cada função e para cada variante do
APM utilizando como condição de parada o número de avaliações da função objetivo
adotado como 5x105. Os resultados do melhor e do pior valor nestas execuções estão
expostos nas Tabelas 2 a 6 bem como a média, desvio padrão e número de soluções
factíveis ao término do processamento. Para as variantes APM Esporádico e APM com
Acúmulo da Violação das Restrições foi utilizado o valor de f=10 e para a variante do APM
com Amortecimento utilizou-se θ = 0,5.
Tabela 2 - Resultado das execuções utilizando o APM
-15,0000
Desvio
Padrão
0
# Soluções
Factíveis
30
-0,7601
-0,7994
0,0094
30
-1,0005
-0,9894
-0,9986
0,0028
14
G4
-30665,5386
-30665,5386
-30665,5386
0
30
G5
5140,7590
5140,7590
-
-
1
G6
-6961,8138
-6961,8138
-6961,8138
0
3
G7
24,3315
25,6699
24,8695
0,4566
30
G8
-0,0958
-0,0958
-0,0958
0
30
G9
680,6317
680,6533
680,6397
0,0053
30
G10
-
-
-
-
-
G11
0,7499
0,7530
0,7501
0,0006
30
G12
-1,0000
-0,9693
-0,9974
0,0061
30
G13
0,0723
3,2191
0,9680
0,5492
23
Função
Melhor
Pior
Média
G1
-15,0000
-15,0000
G2
-0,8036
G3
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
Tabela 3 - Resultado das execuções utilizando o APM Monotônico
-15,0000
Desvio
Padrão
0
# Soluções
Factíveis
30
-0,7857
-0,8017
0,0044
30
-0,9770
-0,2160
-0,6550
0,2115
28
G4
-30665,5386
-30665,5386
-30665,5386
0
30
G5
5155,7969
5856,8046
5433,7649
288,6024
5
G6
-6961,8138
-6961,8138
-6961,8138
0
30
G7
24,3112
25,0359
24,6735
0,5124
28
G8
-0,0958
-0,0958
-0,0958
0
30
G9
680,6317
680,6558
680,6411
0,0070
30
G10
-
-
-
-
-
G11
0,7499
0,7695
0,7542
0,0038
30
Função
Melhor
Pior
Média
G1
-15,0000
-15,0000
G2
-0,8036
G3
Tabela 4 - Resultado das execuções utilizando o APM Esporádico
-15,0000
Desvio
Padrão
0
# Soluções
Factíveis
30
-0,7786
-0,8015
0,0054
30
-0,9987
-0,7760
-0,8916
0,0681
8
G4
-30665,5386
-30665,5386
-30665,5386
0
30
G5
-
-
-
-
-
G6
-6961,8138
-6931,7019
-6960,7370
5,6903
28
G7
24,3141
28,3965
24,8714
0,1834
26
G8
-0,0958
-0,0536
-0,0938
0,0086
24
G9
680,6315
680,6566
680,6422
0,0072
30
G10
-
-
-
-
-
G11
0,7499
0,7866
0,7563
0,0101
30
Função
Melhor
Pior
Média
G1
-15,0000
-15,0000
G2
-0,8036
G3
Tabela 5 - Resultado das execuções utilizando o APM Esporádico com Acúmulo das
Violações das Restrições
-15,0000
Desvio
Padrão
0
# Soluções
Factíveis
30
-0,7773
-0,800
0,008
29
-0,9976
-0,7860
-0,8876
0,3441
6
G4
-30665,5386
-30665,5386
-30665,5386
0
30
G5
-
-
-
-
-
G6
-6961,8138
-6931,7134
-6960,7456
5,8903
27
G7
24,3142
28,3955
24,8567
0,1223
25
G8
-0,0958
-0,0445
-0,0228
0,0176
22
G9
680,6325
680,6788
680,6349
0,0098
30
Função
Melhor
Pior
Média
G1
-15,0000
-15,0000
G2
-0,8036
G3
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
G10
-
-
-
-
-
G11
0,7499
0,7977
0,7690
0,0345
30
Tabela 6 - Resultado das execuções utilizando o APM com Amortecimento
-15,0000
Desvio
Padrão
0
# Soluções
Factíveis
30
-0,7926
-0,8017
0,0037
30
-0,9997
-0,8725
-0,9737
0,0417
8
G4
-30665,5386
-30665,5386
-30665,5386
0
30
G5
5128,2129
5206,5685
5167,3907
55,4058
2
G6
-6961,8138
-6961,8138
-6961,8138
0
9
G7
24,3410
26,6442
24,8620
0,5819
29
G8
-0,0958
-0,0958
-0,0958
0
30
G9
680,6329
680,6624
680,6443
0,0077
30
G10
-
-
-
-
-
G11
0,7499
1,0000
0,8935
0,1137
30
Função
Melhor
Pior
Média
G1
-15,0000
-15,0000
G2
-0,8036
G3
Na Tabela 7 são comparados os resultados das execuções do PSO com o APM e suas
variantes com aqueles obtidos em Barbosa e Lemonge (2008). As variantes do APM foram
rotuladas como se segue: 1: APM original, 2: APM Esporádico, 3: o APM Esporádico com
Acúmulo das Violações das Restrições, 4: APM com Amortecimento e 5: Monotônico.
Tabela 7 - Comparativo dos resultados obtidos com a utilização do APM e suas variantes
Função
G1
G2
G3
Ótimo
Conhecido
-15,0000
-0,8036
-1,0005
Variante
do APM
1
-15,0000
Lemonge e
Barbosa
-14,9999
2
-15,0000
-14,9999
3
-15,0000
-14,9999
4
-15,0000
-14,9999
5
-15,0000
-14,9999
1
-0,8036
-0,8015
2
-0,8036
-0,8025
3
-0,8036
-0,8023
4
-0,8036
-0,8030
5
-0,8036
-0,8025
1
-1,0005
-1,0004
2
-0,9987
-1,0004
3
-0,9976
-1,0004
4
-0,9997
-1,0004
5
-0,9770
-1,0004
Este Trabalho
Nono Simpósio de Mecânica Computacional
G4
G5
G6
G7
G8
G9
G10
G11
-30665,5386
5126,4967
-6961,8138
24,3062
-0,0958
680,6300
7049,2480
0,7499
Universidade Federal de São João Del-Rei – MG – ABMEC
1
-30665,5386
-30665,5237
2
-30665,5386
-30665,5369
3
-30665,5386
-30665,5375
4
-30665,5386
-30665,5332
5
-30665,5386
-30665,5209
1
5140,7590
5127,3606
2
-
5126,7738
3
-
5126,7738
4
5128,2129
5126,7738
5
5155,7969
5128,8443
1
-6961,8138
-6961,7960
2
-6961,8138
-6961,7960
3
-6961,8138
-6961,7960
4
-6961,8138
-6961,7960
5
-6961,8138
-6961,7960
1
24,3315
24,4162
2
24,3141
24,6482
3
24,3142
24,5543
4
24,3410
24,7315
5
24,3112
24,4148
1
-0,0958
-0,0958
2
-0,0958
-0,0958
3
-0,0958
-0,0958
4
-0,0958
-0,0958
5
-0,0958
-0,0958
1
680,6317
680,6334
2
680,6315
680,6673
3
680,6325
680,7122
4
680,6329
680,6505
5
680,6317
680,6527
1
-
7205,1435
2
-
7064,1563
3
-
7062,6060
4
-
7064,5428
5
-
7064,3344
1
0,7499
0,7523
2
0,7499
0,7521
3
0,7499
0,7521
4
0,7499
0,7521
5
0,7499
0,7501
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
Para ilustrar o desempenho do algoritmo PSO utilizando a penalização adaptativa
originalmente desenvolvida e suas variações, ilustramos nas Figuras 2 a 4 a convergência
da função objetivo em relação ao número de gerações do PSO para as funções G2, G6 e
G11.
Evolução da Fitness
0
Fitness
-0,2
-0,4
-0,6
-0,8
-1
Gerações
1
2
3
4
5
Figura 2 – Evolução da Fitness em relação as gerações para a função G2
Evolução da Fitness
800000
Fitness
600000
400000
200000
0
-200000
Gerações
1
2
3
4
5
Figura 3– Evolução da Fitness em relação as gerações para a função G6
Evolução da Fitness
2
Fitness
1,5
1
0,5
0
Gerações
1
2
3
4
5
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
Figura 3– Evolução da Fitness em relação as gerações para a função G11
5
CONCLUSÕES
Neste trabalho foi apresentado o algoritmo PSO modificado para tratar problemas com
restrições através de uma estratégia de penalização adaptativa que não necessita de
parametrização e é ajustada ao longo da evolução do processo. Esta técnica denominada
APM tem se mostrado robusta quando acoplada a outros algoritmos bio-inspirados para
tratar problemas com restrições. O algoritmo PSO usado foi o clássico contendo os
ingredientes básicos sugeridos na literatura. Foram apresentados testes da utilização do
algoritmo PSO com o APM original e com suas variantes recentemente propostas. Os
resultados apresentados demonstraram que o algoritmo foi eficiente na busca das soluções
ótimas na utilização da versão original do APM bem como em suas variantes.
Para futuras implementações sugere-se a utilização de problemas mais complexos da
engenharia mecânica e estrutura bem como as outras funções G disponíveis. Outras
sugestões disponíveis na literatura serão implementadas no algoritmo básico PSO como as
citadas em Albrecht (2005) e para o tratamento das restrições as variantes sugeridas por
Venter e Sobieszczanski-Sobiesk (2003) e Fourie e Groenwold (2002).
Agradecimentos
Os autores agradecem ao CNPq (processos número 311651/2006-2 e 301527/2008-3),
a FAPERJ (processo número E-26/102.825/2008) e a FAPEMIG (processo TEC 00425-09)
pelo apoio.
6
BIBLIOGRAFIA
Albrecht, C. H., 2005 Algoritmos Evolutivos Aplicados À Síntese e Otimização de
Sistemas de Ancoragem, Tese de Doutorado, Programa de Engenharia Oceânica,
COPPE/UFRJ, 2005.
Abido, M., 2002. Optimal design of power system stabilizers using particle swarm
optimization, IEEE Trans Energy Conversion, vol. 17, n. 3, pp. 406–413.
Barbosa H.J.C,. and Lemonge A.C.C., 2002. An adaptive penalty scheme in genetic
algorithms for constrained optimization problems. In GECCO 2002: Proceedings of
the Genetic and Evolutionary Computation Conference, Langdon WB, Cantú-Paz E,
Mathias K, Roy R, Davis D, Poli R, Balakrishnan K, Honavar V, Rudolph G, Wegener
J, Bull L, Potter MA, Schultz AC, Miller JF, Burke E, Jonoska N (eds). Morgan
Kaufmann: New York, 9–13 July 2002; 287–294.
Barbosa, H. J. C. and Lemonge, A. C. C., 2008. An Adaptive Penalty Method for Genetic
Algorithms in Constrained Optimization Problems. In: Aleksandar Lazinica. (Org.).
Frontiers in Evolutionary Robotics. Vienna: I-Tech Education and Publishing, 2008, v.
1, p. 9–34.
Coelho, C & Luna E., 2003. Use of particle swarm optimization to design combinational
logic cirtuits. Tyrell A., Haddow P., Torresen J., eds, %th International Conference on
Evolvable System: from biology to hardware, vol. 2606, pp. 398–409.
Colorni A, Dorigo M & Maniezzo V., 1998. Distributed optimization by ant colonies. In:
Proceedings of ECAL’91 - European Conference on Artificial Life. Paris, France:
Elsevier Publishing, pp. 134–42.
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João Del-Rei – MG – ABMEC
Chatterjee, A. & Siarry, P., 2004. Nonlinear Inertia Weight Variation for Dynamic
adaptation in Particle Swarm Optimization, Computers & Operations Research,
Elsevier, Article in Press.
Davis, L., 1991. HandBook of Genetic Algorithms, Van Nostrand Reinhold, New York,
MY.
Eberhart, R. C. & Shi, Y., 1998. A Modified Particle Swarm Optimizer, IEEE International
Conference on Evolutionary Computation, Anchorage, Alaska, pp. 1945–1950.
Eberhart, R. C. & Shi, Y., 2000. Comparing Inertia Weights and Constriction Factors in
Particle Swarm Optimization, IEEE International Conference on Evolutionary
Computation, San Diego, California, pp. 84–88.
Fourie, P. & Groenwold, A., 2002. The particle swarm optimization algorithm in size and
shape optimization. Structural and Multidisciplinary Optimization, Vol. 23(4), pp.
259–267.
Hu, X., Eberhart, R. C. & Shi, Y., 2003. Engineering Optimization with Particle Swarm,
Swarm Intelligence Symposium.
Kennedy, J. & Eberhart, R. C., 1995. Particle swarm optimization. In Proceedings of the
1995 IEEE International Conference on Neural Networks, volume 4, pp. 1942–1948,
Perth, Australia, IEEE Service Center, Piscataway, NJ.
Koziel S, Michalewicz Z. Evolutionary algorithms, homomorphous mappings, and
constrained parameter optimization. Evolutionary Computation 1999; 7(1):19–44.
Lemonge, A. C. C. & Barbosa, H. J. C., 2004. An adaptive penalty scheme for genetic
algorithms in structural optimization, International Journal For Numerical Methods In
Engineering, pp. 703–706.
Parsopoulos, K. E. & Vrahatis, M. N., 2002. Particle Swarm Optimization Method for
Constrained Optimization Problems, Intelligent Technologies - Theory and
Applications: New Trends in Intelligent Technologies, pp. 214–220.
Ray, T. & Liew, K. M., 2001. A swarm with an effective information sharing mechanism
for unconstrained and constrained single objective optimization problems, Proceedings
of IEE Congress on Evolutionary Computation (CEC 2001), pp. 77–80.
Venter, G. & Sobieszczanski-Sobiesk, J., 2003. Particle swarm optimization. AIAA
Journal, Vol. 41(8), pp. 1583–1589.
Zavala A. E. M., Aguirre, A. H., Diharce E. R. V., 2005. Constrainet Optimization via
Particle Evolutionary Swarm Optimization Algorithm (PESO), Proceedings of the
2005 Conference on Genetic and Evolutionary Computation.
Zheng Y., Ma L., Zhang L. & Qian J., 2003. Robust pid controller design using particle
swarm optimizer, IEEE International Symposium on Intelligence Control, pp. 974–
979.
Nono Simpósio de Mecânica Computacional
7
Universidade Federal de São João Del-Rei – MG – ABMEC
DIREITOS AUTORAIS
Os autores são os únicos responsáveis pelo conteúdo do material impresso incluído no
seu trabalho.