ANT SYSTEM RÁPIDO COM BUSCA TABU APLICADO À … · perpassa pela busca da qualidade da solução com um esforço computacional aceitável (ABDELAZIZ, ... é a informação heurística

ANT SYSTEM RÁPIDO COM BUSCA TABU APLICADO À RECONFIGURAÇÃO DE SISTEMAS

ELÉTRICOS DE DISTRIBUIÇÃO

MIGUEL PEREIRA SANTOS NETO, NIRALDO ROBERTO FERREIRA

Escola Politécnica, Depto. de Engenharia Elétrica, Programa de Pós Graduação em Engenharia Elétrica,

Universidade Federal da Bahia

CEP 40210-630, Salvador, Bahia

E-mails: [email protected], [email protected]

Abstract This article proposes a model of Ant Colony Optimization based on Ant System (AS) combined with Tabu Search (TS)

and Method of Acceleration of the AS, conveniently called this work by AS_BT_MA applied to Reconfiguration of Electrical Distri-

bution Systems. The strategy aims to improve the performance of the AS through a local search with BT, while reducing the compu-

tational effort by identifying and eliminating redundancies. The proposed algorithm was tested for the systems 16, 33, 69, and 84

nodes founds in the literature. The simulation results showed that the algorithm converged to good solutions in satisfactory computa-

tional time.

Keywords Ant Colony Optimization, Reconfiguration, Tabu Search, Method of Acceleration.

Resumo Este artigo propõe um modelo de Otimização por Colônia de Formigas baseado no Ant System (AS) combinado com

Busca Tabu (BT) e um Método de Aceleração do AS, convenientemente chamado neste trabalho por AS_BT_MA, aplicado à Recon-

figuração de Sistemas Elétricos de Distribuição. A estratégia visa melhorar o desempenho do AS por meio de uma pesquisa local com

a BT, além de reduzir o esforço computacional por identificação e eliminação de redundâncias. O algoritmo proposto foi testado para

os sistemas de 16, 33, 69 e 84 barras obtidos na literatura. Os resultados das simulações mostraram que o algoritmo convergiu para

boas soluções em tempo computacional satisfatório.

Palavras-chave Otimização por Colônia de Formigas, Reconfiguração, Busca Tabu, Método de Aceleração.

1 Introdução

A Reconfiguração de Sistemas Elétricos de Dis-

tribuição (RSED) é um problema combinatorial que

envolve a modificação da topologia inicial. Nor-

malmente os objetivos são a minimização de perdas

ativas, o isolamento de faltas, o balanceamento de

cargas entre alimentadores e/ou a melhoria dos ní-

veis de tensão.

A Otimização por Colônia de Formigas ou ACO

(Ant Colony Optmization) é um método eficiente de

resolver este tipo de problema. O principal desafio

perpassa pela busca da qualidade da solução com um

esforço computacional aceitável (ABDELAZIZ,

2010).

Este artigo propõe um estudo do Algoritmo por Co-

lônia de Formigas baseado no AS (Ant System) com-

binado com Busca Tabu e um Método de Aceleração

do AS, aplicado à RSED. A estratégia visa intensifi-

car a exploração das formigas por meio de uma pes-

quisa local, melhorando o desempenho do AS.

O método proposto dispensa a verificação da radiali-

dade, tanto na construção das configurações, quanto

no pesquisa de vizinhança realizada pela BT.

2 Aplicação do Algoritmo Colônia de Formigas

ao problema de RSED

Otimização por Colônia de Formigas é uma me-

taheurística que busca, através de formigas artifici-

ais, obter resultados adequados, ótimos ou próximos

deste, no contexto de um dado problema de otimiza-

ção combinatória.

O método surgiu com Dorigo (1996), que utilizando

o comportamento de cooperação coletiva das formi-

gas e o mecanismo de comunicação indireta através

do feromônio, explorou o fato de as formigas conse-

guirem encontrar o menor caminho entre o formi-

gueiro e a fonte de alimento.

A formulação do problema para o caso de RSED

pode ser feito do seguinte modo:

,

12

)22()(

RN

mi

V

mQ

mP

mR

xfMinimizar

(1)

tendo como restrições:

Limite de magnitude das tensões nodais:

Vmin ≤ Vi ≤ Vmáx, ∀ i, i ϵ Nb;

Capacidade das ligações Im ≤ Imáx, ∀ m, m ϵ

NR;

Radialidade.

Nb e NR são o conjunto de barras e ramos do sistema,

respectivamente, Rm é a resistência do ramo m, Im e

Imáx são a magnitude da corrente e o limite máximo

de corrente em cada trecho m, Vi é a magnitude da

tensão no nó i, Vmin e Vmáx são os limites mínimo e

máximo da tensão, respectivamente.

O pseudocódigo do ACO pode ser resumido confor-

me o algoritmo 1:

Anais do XX Congresso Brasileiro de Automática Belo Horizonte, MG, 20 a 24 de Setembro de 2014

304

2.1 Construção de Configurações Radiais

Para garantir que as configurações construídas

sejam sempre radiais utilizou-se o critério de

(SOUZA et al., 2010). Assim, durante a escolha das

ligações que formam uma Configuração Radial, as-

sumiremos os seguintes critérios:

Um nó pode assumir dois estados: ligado ou

desligado;

Uma ligação pode assumir três estados: de-

sativada, ativável ou ativada.

A Figura 1 ilustra a estratégia.

Figura 1. Estado dos nós e das ligações.

Inicialmente todos os nós fontes estão ligados e os de

carga desligados, de modo que nenhuma ligação

esteja ativada. Uma das formigas posicionada em

nós ligados se deslocará respeitando as seguintes

regras:

As formigas se deslocam exclusivamente

por ligações ativáveis;

Quando uma formiga chega ao nó desligado

da ligação ativável que tenha percorrido,

este nó torna-se ligado e a ligação ativada,

surgindo outra formiga para ocupar o nó

originalmente ligado deixado por ela;

O percurso de uma formiga se completa

quando ela não puder mais seguir por liga-

ções ativáveis;

A expedição termina quando nenhuma

formiga tiver mais mobilidade, ou seja,

quando não houver mais nenhuma ligação

ativável.

Ao final das expedições sempre teremos as for-

migas estabilizadas em configurações radiais, dis-

pensando assim, a verificação de radialidade.

2.2 Escolha Pseudo-Aleatória das Ligações

Na construção da rota, cada formiga deve esco-

lher um caminho, dentre as possibilidades de trilhas,

tendo como base o seu conhecimento individual (re-

sistência das ligações) e coletivo (quantidade de fe-

romônio depositado nas ligações). A cada iteração o

conhecimento coletivo é atualizado.

A escolha, então, deve ser feita de forma probabilís-

tica. Com isso, a probabilidade de um agente k que

se encontra em uma barra j, possuindo Ψ (conjunto

de x ligações partindo do nó j, visitar uma barra z é

dada pela equação de transição (2):

zse

zse

ljljl

jzjz

k

jzP

,0

,

(2)

em que τjz é a quantidade de feromônio na ligação jz,

ηjz é a informação heurística expressa pelo inverso

da resistência da ligação jz, α é o peso da carga de

feromônio e β é o peso da resistência.

O termo do numerador corresponde à trilha jz esco-

lhida pela formiga k para ser visitada, enquanto o

denominador, indica todos os caminhos que o agente

pode escolher a partir do nó corrente j.

Com a probabilidade de cada trecho calculada gera-

se uma roleta constituída por intervalos numéricos,

por meio do qual será feita o sorteio da próxima tri-

lha a ser percorrida pela formiga.

Supondo, por exemplo, que para uma determinada

transição a formiga tenha que escolher entre as liga-

ções 1, 11, 15, 25, 30, 43, 47, 56, 65, 73 e 77 com

probabilidades calculadas conforme equação (2) e

mostrada na Tabela 1.

Os intervalos são calculados tomando 0 como refe-

rência e somando a probabilidade em cada trecho ao

valor acumulado. Assim, somando 0,018 à 0,112

teremos os limites inferior e superior 0,018 e 0,130,

respectivamente, para a ligação 11. O procedimento

é repetido para todas as chaves, conforme Tabela 1.

Tabela 1. Intervalos numéricos para construção da roleta.

Ligação Probabilidade Intervalo

1 0,018 [0 - 0,018]

11 0,112 (0,018 - 0,130]

15 0,053 (0,130 - 0,183]

25 0,212 (0,183 - 0,395]

30 0,017 (0,395 - 0,412]

43 0,279 (0,412 - 0,691]

47 0,008 (0,691 - 0,699]

56 0,011 (0,699 - 0,710]

65 0,277 (0,710 - 0,987]

73 0,004 (0,987 - 0,991]

77 0,009 (0,991 – 1,000]

Em seguida, sorteia-se um número aleatório entre 0

e 1 (para o presente trabalho foi utilizado a função

“rand” do matlab). O valor gerado vai estar necessa-

riamente contido em um dos intervalos estabeleci-

Algoritmo 1: pseudocódigo do ACO

1. Inicializar parâmetros e matrizes de fe-

romônio e informação heurística

2. Para i = 1 : n° de iterações

3. Construir soluções

4. Atualizar feromônio

5. Pesquisa local

6. Fim para

7. Retornar solução


305

dos. Supondo que para o caso apresentado na Tabela

1 o valor sorteado aleatoriamente tenha sido 0,9890.

Logo, a formiga vai escolher visitar a ligação 73.

2.3 Distribuição do Feromônio

Após os agentes completarem uma Configura-

ção Radial factível, as rotas interligando todas as

barras terão o feromônio atualizado sobre os seus

caminhos conforme (3), também conhecido como

atualização global.

zsejz

zsejzjz

jz

)1(

)1( (3)

Em que Ω é o conjunto das ligações ativadas da nova

configuração, jz representa a ligação, ρ é a taxa de

evaporação (um número entre 0 e 1) e Δτjz é a carga

incremental de feromônio na ligação jz:

,Fjz

(4)

sendo F a função objetivo sujeito às restrições, con-

forme expressão (1) e γ o fator de ajuste.

2.4 Pesquisa Local do AS com Busca Tabu

De uma forma geral, a busca local no Algoritmo

de Formigas pode ser usada de forma opcional para

melhorar o desempenho do método.

Este artigo utiliza uma adaptação da metaheurística

Busca Tabu (BT), proposta por Glover (1986), para

realizar uma pesquisa de vizinhança através de mo-

vimentos aplicados sobre a solução corrente do AS

em busca de outras soluções de melhor qualidade.

Durante o procedimento de busca por um ótimo glo-

bal, o algoritmo mantém uma memória constituída

por duas listas que podem ser (ZHOU et al., 2009):

Lista Tabu – É a memória de curto prazo,

onde contêm as soluções recentemente visi-

tadas (TOUNE et al., 2002);

Lista Elite – É a memória de longo prazo,

onde são armazenadas as melhores soluções

visitadas (TOUNE et al., 2002).

Partindo de uma solução inicial, a busca move-se, a

cada iteração, para a melhor solução na vizinhança,

não aceitando movimentos que levem a soluções já

visitadas por permanecerem armazenadas em uma

Lista Tabu. Esse procedimento evita retornar a um

ótimo local visitado previamente.

As soluções são mantidas na Lista Tabu por certo

número de operações conhecidas como Período Ta-

bu. Assim, após certo número de iterações, as solu-

ções antigas tendem a ser apagadas da Lista Tabu,

enquanto as novas são incorporadas nela (TOUNE et

al., 2002; GLOVER, 1989, 1990).

A Busca Tabu utiliza a estratégia de permutação das

ligações para poder gerar novas configurações, a

partir da solução corrente e radial fornecida pelo AS.

Para garantir que as novas soluções da BT sejam

também radiais utilizou-se o seguinte procedimento

(ABDELAZIZ, 2010):

Com a topologia radial fornecida pelo AS,

identificar os nós de derivação que limitam

os ramos que contém as chaves abertas;

Identificar as ligações fechadas, vizinhas e

adjacentes às chaves abertas e que esteja

limitada pelos nós de derivação;

Fechar uma chave aberta e abrir uma liga-

ção vizinha e adjacente a esta;

Realizar todas as permutações possíveis até

que não haja mais combinações entre as li-

gações (vizinhas e adjacentes às chaves

abertas da configuração inicial).

O método de permutação pode ser melhor entendido

recorrendo-se a um exemplo com um sistema de 16

barras, das quais 3 são fontes. A Configuração Radi-

al fornecida pelo AS foi obtida pela abertura das

chaves 12, 24 e 25, conforme se vê na Figura 2.

Figura 2. Configuração Radial para o Sistema de Distribuição de 16

barras.

Com base no procedimento descrito, devemos iniciar

identificando os nós de derivação que limitam os

ramos que contém as chaves abertas. Dessa forma,

para a chave 12, temos os nós 4 e 9, para a chave 24,

temos os nós 8 e 13 e, por fim, para a chave 25, te-

mos os nós 4 e 13, conforme Figura 3.

Figura 3. Identificação dos nós de derivação que limitam os ramos

que contém as chaves abertas


306

Procedemos agora identificando as ligações fecha-

das, vizinhas, adjacentes e limitadas pelos nós de

derivação contidos nestes ramos, conforme Tabela 2.

Tabela 2. Vizinhos imediatos das chaves abertas.

Chaves vizinhas Chaves abertas Chaves vizinhas

- 12 15

21 24 -

26 25 23

A permutação será realizada fechando uma chave

aberta do ramo e abrindo uma ligação vizinha e ad-

jacente a esta. Assim, fechando a chave 12 e abrindo

a chave 15 teremos uma nova configuração gerada

pela abertura das chaves 15, 24 e 25. Da mesma

forma, fechando a chave 25 e abrindo a 26 teremos

agora as chaves abertas 12, 24 e 26. O procedimento

é retido para todas as chaves vizinhas.

Dessa forma, para este exemplo, no final da permu-

tação teremos 4 configurações geradas na Busca

Tabu e 1 configuração obtida pelo AS, conforme

Tabela 3.

Tabela 3. Chaves abertas após a permutação.

Método de exploração Chaves abertas na

configuração

Chaves abertas no AS 12-24-25

Chaves abertas na BT

15-24-25

12-21-25

12-24-26

12-24-23

2.5 Método de Aceleração do Algoritmo de Formi-

gas

Em Tseng et al. (2010) é apresentado um algo-

ritmo, aplicado ao problema do caixeiro viajante,

que pode ser incorporado ao AS de modo a propor-

cionar redução do esforço computacional. Esta seção

abordará a metodologia do MA (Método de Acelera-

ção do AS) aplicado ao problema da Reconfiguração.

A estratégia consiste em identificar o mais rápido

possível as ligações que poderão fazer parte da solu-

ção final, ou seja, subsoluções que possuem grande

tendência de pertencer à melhor trilha e, portanto,

podem ser comprimidos e removidos do espaço de

busca do AS para eliminar parte das redundâncias

computacionais nas iterações posteriores (TSAI et

al., 2009).

De acordo com Tseng et al. (2010), o Método de

Aceleração pode ser incorporado ao ACO adicio-

nando ao algoritmo 1 a rotina, doravante chamada

neste artigo, redução padrão, localizada na linha 6,

conforme algoritmo 2.

O algoritmo de redução padrão inicia identificando

as ligações que possuem alta probabilidade de fazer

parte da solução final. O algoritmo 3 mostra o pro-

cedimento utilizado.

Onde n é o comprimento da solução, υ é o vetor

registrador de visitas das formigas, ω é o limite usa-

do para determinar se uma ligação ejz pode ser com-

primida.

O limite ω pode ser estabelecido pela quantidade de

formigas m que atravessam uma determinada liga-

ção em um determinado intervalo de iterações π, ou

seja, para uma quantidade π de iterações é verificado

quais ligações alcançaram o limite ω de visitas.

Modificando os parâmetros m e π poderemos estabe-

lecer os limites adequados para melhorar a eficiência

do algoritmo. Estes valores dependem do problema.

Dessa forma, quanto menor o valor de ω mais rápido

o algoritmo AS converge. Por outro lado, pode pro-

porcionar redução da qualidade da solução (TSAI et

al., 2013).

O registro de quantas vezes cada ligação é atraves-

sada pelas formigas é feita por meio da matriz υ,

algoritmo 3, como mostrado nas linhas 2 à 4. A atu-

alização desta matriz é feita a cada expedição do

algoritmo AS até que se atinja o intervalo π itera-

ções. Atingido o limite de iterações, a matriz υ será

inicializada para nova contabilização de visitas, ou

seja, o intervalo de iterações (π) é um parâmetro

estabelecido para inicialização da contabilização de

visitas nas ligações dado pela matriz υ.

Para cada expedição do AS, a matriz υ é analisada

para verificar quais ligações alcançaram o limite

pré-estabelecido ω de visitas. Se uma ligação da ma-

triz υ possuir um número de visitas maior ou igual

Algoritmo 2: pseudocódigo do ACO

1. Inicializar parâmetros e matrizes de fe-

romônio e informação heurística

2. Para i = 1 : n° de iterações

3. Construir soluções

4. Atualizar feromônio

5. Pesquisa local

6. Redução padrão

7. End

8. Retornar solução

Algoritmo 3: Operador de Detecção

1. % Registrar o número de vezes que cada liga-

ção é atravessada

2. Para i=1: n

3. υjz υjz+1

4. Fim para i

5. %Fazer as ligações atravessadas ω ou mais

vezes como comuns

6. Para cada ligação ejz

7. Se υjz ≥ ω

8. ζjz1 9. Fim se

10. Fim para


307

ao limite pré-estabelecido ω, então esta ligação será

considerada uma das componentes da solução do

problema.

O registro das ligações que alcançaram o limite ω é

realizado por meio da matriz ζ, de forma que, se υjz

for maior que ω, então ζjz 1, como descrito nas

linhas 6 à 10 (TSAI et al., 2010, 2013).

O princípio de funcionamento do Método de Acele-

ração pode ser melhor explicado recorrendo-se à

rede de quatro nós de carga, uma subestação, e sete

ligações, mostrado na Figura 4.

Figura 4. Rede de quatro nós de carga e sete ligações.

Adotando-se para o intervalo de 4 iterações (π=4

iterações) e 4 formigas (m=4 formigas), ou seja, o

limite estabelecido para este intervalo de iterações é

de 4 formigas, ω=4.

Supondo que após 4 expedições do AS tenha se obti-

do 4 configurações radiais, ou seja, uma configura-

ção por iteração, conforme Figura 5.

Figura 5. Configurações radiais obtidas.

Para esta 4° iteração, a frequência de visitas das

formigas à ligação é registrada utilizando a matriz υ,

conforme Tabela 4.

Com base nos dados da tabela 4 e sabendo-se que

ω=4, obtêm-se a matriz ζ, que identifica as ligações

que alcançaram o limite estabelecido ω, conforme

Tabela 5.

Tabela 4. Contabilizando a frequência de visitas nas ligações.

ejz 1 2 3 4 5 6 7

υjz 3 3 2 3 1 4 0

Tabela 5. Registro das ligações que alcançaram o limite de visitas

nas últimas iterações.

ejz 1 2 3 4 5 6 7

ζjz 0 0 0 0 0 1 0

Como pode ser observado, para este exemplo, so-

mente a ligação 6 foi identificada como subsolução

do problema, pois em suas 4 iterações, 4 formigas

passaram por este caminho.

A atualização da matriz ζ é realizada em cada expe-

dição e inicializada somente no início do AS.

Uma vez conhecida a matriz ζ, o próximo passo é

comprimir e remover estas subsoluções. O primeiro

e importante passo é modificar o cálculo da probabi-

lidade expresso em (2), para garantir que o AS sem-

pre selecione a ligação que tenha alcançado ζ 1,

por esta ter uma alta probabilidade de ser parte da

solução final (TSAI et al., 2013).

Esta modificação pode ser realizada conforme (5):

zse

zse

ljljl

jzjz

jzse

k

jzP

,0

,

1,1

(5)

Dessa forma se uma formiga estiver localizada em

um nó qualquer j e tiver que escolher o próximo nó a

ser visitado z. Existindo ligação identificada como

subsolução ζjz=1, a formiga escolherá esta. Caso não

exista identificação de subsoluções, a estratégia pro-

babilística utilizada é a mesma que descrita no AS,

expresso por (2).

2.6 Fluxo de Carga e o Cálculo das Perdas

Após a obtenção da Configuração Radial, faz-se

necessário a avaliação do custo dessa solução. Para

isto, pode-se utilizar o método da soma de potência

(MSP) expressa em Baran & Wu (1989) e SU et al.,

(2005).

Supondo, por exemplo, uma ligação m iniciando em

nó i e chegando ao nó j e Ψ um conjunto de x liga-

ções partindo do nó j, conforme Figura 6.

Figura 6. Ramo de um Sistema de Distribuição.


308

Em que, Pm e Qm são os fluxos de potência ativa e

reativa no fim da ligação m, PLj e QLj corresponde as

potências ativa e reativa instaladas na barra j, Rm e

Xm correspondem a resistência e reatância da ligação

m e Vi e Vj são as tensões nas barras i e j, respecti-

vamente.

Então, as perdas de potência ativa e reativa nos di-

versos trechos podem ser obtidas por (6) e (7).

,2

)22(

jV

mQ

mP

mR

mP

(6)

,

mR

mP

mX

mQ

(7)

onde, ΔPm e ΔQm são as perdas de potência ativa e

reativa.

A perda de potência total do sistema é calculada

somando as perdas nos diversos trechos.

O processo iterativo do MSP converge quando o erro

absoluto entre as perdas totais de uma iteração e a

iteração precedente é menor que uma tolerância pré-

estabelecida.

3 Aplicação do Algoritmo Proposto

O algoritmo inicia fazendo todos nós fontes li-

gados e os de carga desligados. Assim como, atribui-

se a todas as ligações a mesma quantidade de fe-

romônio.

Posiciona-se uma formiga em cada nó ligado (fon-

tes1) e executa o movimento conforme procedimento

descrito na seção 2.1. Durante a construção das con-

figurações, a escolha probabilística das trilhas é rea-

lizada como descrito na expressão (6) da seção 2.5.

A Configuração Radial será gerada quando não exis-

tir mais nenhuma ligação ativável.

Tão logo as formigas construam uma topologia radi-

al, inicia-se a pesquisa local na vizinhança utilizan-

do a Busca Tabu, conforme descrito em 2.4. A avali-

ação das configurações obtidas serão realizadas pelo

MSP, conforme seção 2.6.

Por fim, atualiza a carga de feromônio e o registro

de visitas das trilhas com base na melhor solução da

expedição, conforme seções 2.3 e 2.5, respectiva-

mente.

O algoritmo será executado enquanto houver expe-

dições da colônia de formigas. Ao final, o algoritmo

apresenta a melhor configuração indicando suas

ligações e as perdas totais. O algoritmo proposto

pode ser visto conforme Figura 7.

1 O procedimento descrito na seção 2.1 pode ser utilizado para múl-

tiplos alimentadores.

Início

Ler os dados da rede e os

parâmetros do algoritmo

híbrido

Depositar uma

quantidade inicial de

feromônio em todas

as ligações

Incrementar o

contador de

expedições

Fazer todos os nós

fontes ligados e os nós

de carga desligados

Incrementar o

contador de

expedições

Posicionar uma

formiga em cada

nó ligado

Existe

ligação

ativável?

Existe

ligação

comum?

Buscar vizinhos

factíveis a partir

da configuração

radial corrente

não

Escolher uma das

ligações ativáveis

com probabilidade

calculada

Deslocar a formiga

que esteja no nó

ligado da ligação

ativável selecionada

Analisar

configuração?

É tabu?

simsim

Executar o MSP:

calcular fluxos e

as perdas ativas

totais

Atualizar Lista

tabu e Lista Elite

não

Escolher a melhor

solução da

expedição

Atualizar a carga

de feromônio

Última

expedição?

Apresentar a

configuração radial

final indicando suas

ligações e as perdas

totais.

Fim

Registrar o

número de vezes

que cada ligação

é visitada

Registrar as ligações

frequentemente

visitadas como

comuns

não

sim

não

Escolher

aleatoriamente

uma formiga do nó

ligado para realizar

o movimento

sim

sim

não

Figura 7. Fluxograma do Algoritmo proposto.

4 Resultados

O algoritmo proposto foi implementado em Ma-

tlab® R2010b, computador Intel (R), Core (TM) i5,

2,60 GHz e 4,0 GB de memória RAM e testado com

o sistema de 16 barras encontrado em (SOUZA et

al., 2010), 33 barras encontrado em (BARAN &

WU, 1989), 69 barras encontrado em (CHIANG et

al., 1990) e 84 barras encontrado em (SU et al.,

2005).

Os parâmetros de entrada dependem do problema e

foram estabelecidos com base no melhor desempe-

nho do algoritmo, conforme Tabela 6.

Tabela 6. Parâmetros de entrada do algoritmo.

Parâmetros N° de barras

16 33 69 84

Tolerância do MSP 10-3

10-3 10

-3 10-3

Feromônio inicial 1 1 1 1

Taxa de evaporação 0,15 0,15 0,05 0,005

N° de expedições 200 200 200 4600

Interv. de exped. do MA 5 7 7 10

Formigas do MA 5 5 5 6

Comprim. da lista tabu 50 100 150 200

Peso do feromônio 1 1 1 1

Peso da inf. heuríst. 2 2 1 1

Fator de Ajuste 10-2

10-2

10-2

10-1

Limite máximo de cor-

rente nos ramos (pu) 0,02 0,03 0,02 0,02

Limite mínimo de tensão

nas barras (pu) 0,90 0,92 0,92 0,92

Limite máximo de tensão

nas barras (pu) 1 1 1 1


309

Para validar o algoritmo Ant System combinado

com Busca Tabu e Método de Aceleração

(AS_BT_MA), quanto à solução obtida, compara-

mos os resultados encontrados pelo método proposto

com os de outros autores, conforme Tabela 7.

Tabela 7. Validação do algoritmo AS_BT_MA.

Algoritmos Perdas

(kW)

Redução

(%)

Chaves aber-

tas

16 barras

Conf. inicial 511,40 - 15-21-26

AS 466,11 8,86 17-19-26

AS_BT_MA 466,11 8,86 17-19-26

SU et al., 2005 466,11 8,86 17-19-26

CHANG et al., 1994 466,11 8,86 17-19-26

33 barras

Conf. inicial 202,68 - 33-34-35-36-37

AS 139,55 31,15 7-9-14-32-37

AS_BT_MA 139,55 31,15 7-9-14-32-37

ZVIETCOVICH,

2006 139,55 31,15 7-9-14-32-37

CHANG et al., 1994 139,55 31,15 7-9-14-32-37

69 barras

Conf. inicial 20,91 - 70-71-72-73-74

AS 9,34 55,33 14-57-62-70-71

AS_BT_MA 9,34 55,33 14-57-62-70-71

ZVIETCOVICH,

2006 9,34 55,33 15-59-62-70-71

CHANG et al., 1994 9,40 55,05 15-56-62-70-71

84 barras

Conf. inicial 531,99 -

84-85-86-87-

88-89-90-91-

92-93-94-95-96

AS 470,10 11,63

7-13-34-39-55-

61-83-86-72-

89-90-92-95

AS_BT_MA 470,05 11,64

7-13-34-39-42-

55-63-72-83-

86-89-90-92

SU et al., 2005 469,88 11,68

7-13-34-39-41-

55-62-72-83-

86-89-90-92

Também comparamos o tempo de processamento do

algoritmo AS_BT_MA com o Ant System (AS) pu-

ro, com o AS somente com a Busca Tabu e com o

AS somente com o Método de Aceleração. Os resul-

tados encontrados nas simulações foram organizados

na Tabela 8.

Tabela 8. Desempenho do AS_BT_MA em relação ao AS.

Barras 16 33 69 84

Tempo de processamen-

to do AS (seg.) 0,48 1,69 5,21 271,27


to do AS_BT (seg.) 0,27 1,23 3,60 165,53


to do AS_MA (seg.) 0,36 1,47 3,10 157,33


to do AS_BT_MA (seg.) 0,16 1,10 2,92 83,36

Figura 8. Perfil de tensão nas barras para o Sistema de 16 barras.





310

5 Conclusão

Neste artigo foi apresentado um método, conve-

nientemente chamado por AS_BT_MA, para Recon-

figuração de Sistemas de Distribuição baseado em

Colônia de Formigas combinado com Busca Tabu e

Método de Aceleração com o objetivo de melhorar o

desempenho do AS na minimização das perdas de

potência ativa em Sistemas de Distribuição Radial.

O método apresentou boas soluções para a perda de

carga em tempo computacional satisfatório, encon-

trando valores coerentes com os apresentados por

outros trabalhos da literatura (Tabela 7).

Também mostrou melhora significativa com relação

à redução do esforço computacional, conforme apre-

sentado na Tabela 8, principalmente quando se au-

menta o número de barras.

Assim, os testes realizados mostraram que a combi-

nação do AS à um método baseado em pesquisa lo-

cal (Busca Tabu) melhorou o algoritmo de formigas

com relação à qualidade da solução, devido à obten-

ção de novas configurações radiais geradas a partir

da topologia fornecida pelas formigas.

Além disso, o esforço computacional do AS pôde ser

minimizado com a incorporação do Método de Ace-

leração que identifica e elimina as redundâncias

computacionais durante o processo de construção

das configurações radiais.

Referências Bibliográficas

Abdelaziz, A.Y.; Mohamed, F.M. .; Mekhamer, S.F.

and Badr, M.A.L. (2010). Distribution System

Reconfiguration Using a Modified Tabu Search

Algorithm. Electric Power Systems Research,

Vol. 8, N° 8; 943-943.

Baran, M. E. and Wu, F. F. (1989). Network

Reconfiguration in Distribution Systems for

Loss Reduction and Load Balancing. IEEE

Transactions on Power Delivery, Vol. 4, N° 2;

pp. 1401-1407.

Chang, H.-C. and Kuo, C.-C. (1994). Network

Reconfiguration in Distribution Systems Using

Simulated Annealing. Electric Power Systems

Research, Vol. 29, N° 3; 227-238.

Chiang, H. D. and Jean-Jumeau, R. (1990). Optimal

Network Reconfiguration in Distribution

Systems Parte 2: Solution Algorithms and

Numerical Results. IEEE Transactions on

Power Delivery, Vol. 5, N° 3; pp: 1568-1574.

Dorigo, M.; Maniezzo, V. and Colorni, A. (1996).

Ant System: Optimization by a Colony of

Cooperating Agents. IEEE Transaction of

Systems, Man, and Cybernetics-Part B:

Cybernetics, Vol. 26, n° 1; pp. 29-41.

Glover, F. (1986). Future Paths for Integer

Programming and Links to Artificial

Intelligence. Computers and Operations

Research, Vol. 13, n° 5; pp. 533-549.

Glover, F. (1989). Tabu Search, Part I. ORSA

Journal on Computing, Vol. 1, N° 3; pp. 190-

206.

Glover, F. (1990). Tabu Search, Part II. ORSA

Journal on Computing, Vol. 2, N° 1 . pp. 4-32.

Souza, B. A.; Silva, J. P. S. and Ferreira, N. R.

(2010). Configuração Ótima de Redes de

Distribuição Aplicando um Algoritmo Colônia

de Formigas. In: IEEE PES Transmission and

Distribution Latin America Conference and

Exposition, São Paulo.

Su, T. C.; Chang, C. F. and Chiou, J. P. (2005).

Distribution Network Reconfiguration for Loss

Reduction by Ant Colony Search Algorithm.

Electric Power Systems Research, Vol. 75, N°

2-3; pp. 190-199.

Toune, S.; Fugo, H.; Genji, T. and Fukuyama, Y.

(2002). Comparative Study of Modern Heuristic

Algorithms to Service Restoration in

Distribution Systems. IEEE Trans. Power

Delivery, Vol. 17, N° 1; pp. 173-181.

Tsai, C. W.; Lee, C. Y.; Chiang, M. C. and Yang,

C. S. (2009). A fast VQ Codebook Generation

Algorithm Via Pattern Reduction. Pattern

Recognition Letters, Vol. 30, N° 7; pp. 653-660.

Tsai, C. W.; Tseng, S. P.; Chiang, M. C. and Yang,

C. S. (2010). A Framework for Accelerating

Metaheuristics via Pattern Reduction. in Proc.

2010 of the 12th Annual Conference on

Genetic and Evolutionary Computation

(GECCO); pp. 293-294.

Tsai, C. W.; Tseng, S. P.; Yang, C. S. and Chiang,

M. C. (2013). PREACO: A Fast ant Colony

Optimization For Codebook Generation.

Applied Soft Computing, Vol. 13, N° 6; pp.

3008-3020.

Tseng, S. P.; Tsai, C. W.; Chiang, M. C. and Yang,

C. S. (2010). A Fast Ant Colony Optimization

for Traveling Salesman Problem. Evolutionary

Computation (CEC), 2010 IEEE Congress on;

pp. 1-6.

Zhou, P and Deng, Q. (2009). Hybridizing Fast

Taboo Search with ant Colony Optmization

Algorithm for Solving Large Scale permutation

Flow Shop Scheduling Problem. in IEEE

International Conference on Granular

Computing, 2009, GRC ‘09; pp. 809-813.

Zvietcovich, W. G. (2006). Reconfiguração de

Sistemas de Distribuição de Energia Elétrica

Utilizando a Metaheurística Busca Tabu em

Vizinhança Variável. Dissertação de Mestrado.

São Paulo, Brasil, Universidade Estadual

Paulista Júlio de Mesquita Filho.


311

Documents

ANT SYSTEM RÁPIDO COM BUSCA TABU APLICADO À … · perpassa pela busca da qualidade da solução com um esforço computacional aceitável (ABDELAZIZ, ... é a informação heurística