Algoritmo cultural

Algoritmo cultural

(Parte 1 de 2)

Um Algoritmo Cultural para o Problema do Despacho Economico e Ambiental

Natalli Macedo Rodrigues1, Carolina Paula de Almeida1,2, Richard A. Goncalves1,2

1Departamento de Ciencia da Computacao

Universidade Estadual do Centro–Oeste (UNICENTRO) Guarapuava – PR – Brasil

2Centro de Pos-graduacao em Engenharia Eletrica e Informatica Industrial

Universidade Tecnologica Federal do Parana (UTFPR) Curitiba – PR – Brasil natallimacedo@yahoo.com.br,{carolpa,richardgoncalves}@cpgei.cefetpr.br

Abstract. This work presents the implementation of a cultural algorithm to solve the economic and environmental dispatch problem. Cultural Algorithm (CA) is an evolutionary methaheuristic based on the human cultural evolution. By definition, a CA is a hybrid method. In this work it’s hybridized with a genetic algorithm, which is inspired on species evolution theory. This paper presents a comparison between the proposed method and those found in the li-terature. The results obtained by the proposed method are comparable or better than those obtained by other known approaches.

Resumo. Este trabalho apresenta a implementacao de um algoritmo cultural que resolve os problemas de despacho economico e ambiental. O Algoritmo Cultural (AC) e uma metaheurıstica evolutiva baseada no processo de evolucao cultural da humanidade. O AC e um metodo hıbrido por definicao, sendo que nesse trabalho ele foi hibridizado com um metodo bastante conhecido: o algoritmo genetico, o qual se inspira na teoria da evolucao das especies. Ao final do trabalho tem-se a comparacao dos resultados obtidos com o metodo implementado e os resultados encontrados na literatura para o caso de usinas termoeletricas de seis e treze geradores de energia. Os resultados obtidos pelo algoritmo proposto sao comparaveis aos valores otimos publicados na lite-ratura e, em alguns casos, sao ate mesmo superiores.

1. Introducao

O objetivo do problema do despacho economico de energia, cujas caracterısticas sao complexas e altamente nao lineares, e alocar a cada uma das unidades geradoras a quantidade de energia a ser produzida de forma que se tenham os custos de operacao reduzidos, respeitando restricoes de igualdade e desigualdade [Coelho and Cocco 2006].

Quando se tem por objetivo do problema, alem da minimizacao do custo de geracao, a minimizacao de poluentes na atmosfera, trata-se de um problema de despacho economico/ambiental. Essa abordagem e importante pois apresenta um maior comprometimento ecologico.

XIV ERI-PR 2007 ISBN: 978-85-7669-115-0

Recentemente tem sido usadas tecnicas heurısticas de otimizacao como o simulated annealing, algoritmos evolucionarios, nuvem de partıculas, redes neurais e busca tabu por serem capazes de encontrar boas solucoes [Park et al. 2006] [Coelho and Cocco 2006].

Nesse artigo e apresentado o uso de um metodo recentemente explorado, chamado de algoritmos culturais que, alem de ser baseado nas caracterısticas fenotıpicas (conhecimento) dos indivıduos, usa desse conhecimento armazenado para guiar a populacao na sua evolucao genetica. Essa evolucao genetica e dada por qualquer metodo heurıstico que faca uso de uma populacao, como por exemplo os algoritmos geneticos, que foi o metodo populacional utilizado nesse trabalho. Os resultados obtidos por esse algoritmo sao comparados com resultados encontrados em trabalhos na literatura.

O restante do trabalho e organizado como segue. Na Secao 2 sao mostrados os conceitos dos problemas de despacho economico e ambiental e a sua formulacao matematica. Na Secao 3 tem-se a apresentacao do metodo utilizado no trabalho, os algoritmos culturais. Ja na Secao 4 e apresentada a metodologia adotada para a construcao e resolucao do trabalho. Finalmente, nas Secoes 5 e 6 se tem os resultados obtidos e as conclusoes finais, respectivamente.

2. Problemas de Despacho

A seguir sao apresentados os conceitos basicos e definicoes relacionadas ao despacho economico e despacho economico/ambiental.

2.1. Despacho Economico

O despacho economico e o estudo da alocacao otima de uma demanda entre as unidades geradoras de um sistema de geracao termoeletrica. Ele possui o objetivo de minimizar o custo de producao de energia eletrica atraves da otimizacao da distribuicao da producao entre os geradores e da utilizacao eficiente dos recursos energeticos.

Alem desse objetivo, e indispensavel que as condicoes de operacao do sistema sejam satisfeitas. Como resultado da satisfacao dos objetivos, obtem-se as potencias de saıda de cada uma das unidades geradoras de energia consideradas. A funcao custo total da geracao e obtida atraves da soma de cada uma das unidades geradoras.

O modelo matematico que rege o problema do despacho economico se da atraves da seguinte formulacao:

min Fe (1) Sujeito a:

i=1 Pi = PD

Pmini ≤ Pi ≤ Pmax i tal que Fe e a funcao custo total de geracao do despacho economico, Pi corresponde a potencia de saıda do i-esimo gerador, Pmaxi e Pimin representam, respectiva-

XIV ERI-PR 2007 ISBN: 978-85-7669-115-0 mente, as potencias maximas e mınimas de geracao de cada unidade geradora e PD e o valor da demanda de energia.

O custo total da geracao termoeletrica e obtida atraves de uma funcao quadratica aplicada a cada uma das unidades geradoras de energia.

2.2. Despacho Economico/Ambiental

As usinas termoeletricas geralmente se baseiam apenas na estrategia do despacho economico, afim de se obter a minimizacao do custo de producao de energia. Porem, a queima de combustıveis fosseis emitem na atmosfera muitos poluentes que sao prejudiciais nao so para os seres humanos como para os animais e plantas [Samed et al. 2003]. Uma estrategia para minimizar essas emissoes na atmosfera e chamada de Despacho Economico/Ambiental (DEA) e consiste na combinacao do custo de combustıvel e emissao de poluentes em uma funcao simples com o ajuste de diferentes pesos.

Como custo e emissao sao objetivos conflitantes, nao se pode obter a minimizacao de ambos simultaneamente. Por isso se tem diferentes pesos atribuıdos a cada um dos objetivos, para que determinadas exigencias sejam satisfeitas para diferentes situacoes.

O modelo de otimizacao para o despacho economico/ambiental e dado por:

i=1 Pi = PD

Pmini ≤ Pi ≤ Pmax i tal que α pode assumir qualquer valor no intervalo [0,1], Fe e a funcao custo total de geracao do Despacho Economico, Fa e a funcao emissao total de geracao do

Despacho Ambiental, Pi corresponde a potencia de saıda do i-esimo gerador, Pmaxi e Pimin representam, respectivamente, as potencias maximas e mınimas de geracao de cada unidade geradora e PD e o valor da demanda de energia.

Quando α assumir o valor 0, implicara em emissoes mınimas, ou seja, Despacho

Ambiental. Analogamente, quando α assumir o valor 1, implica em custo mınimo, ou seja, Despacho Economico.

3. Algoritmos Culturais

Os Algoritmos Culturais (ACs) sao algoritmos evolucionarios baseados no processo de evolucao cultural da humanidade [Reynolds 1999, Reynolds 001a, Reynolds 001b, Reynolds 2003]. Os ACs foram propostos por Robert Reynolds [Reynolds 1994] como um complemento a metafora evolutiva utilizada na computacao evolutiva, metafora essa que se concentra nos aspectos geneticos da evolucao e na teoria da selecao natural proposta por Darwin. Em contrapartida, os algoritmos culturais baseiam-se em teorias sociais e arqueologicas que modelam a evolucao cultural dos povos [Becerra 2002].

XIV ERI-PR 2007 ISBN: 978-85-7669-115-0

Os algoritmos culturais sao compostos por dois componentes principais: o espaco populacional e o espaco de crencas (descritos a seguir).

No espaco populacional sao representadas as caracterısticas e comportamentos dos indivıduos. Essa representacao pode ser feita atraves de qualquer tecnica que faca uso de uma populacao de indivıduos, como e o caso dos algoritmos geneticos que sao algoritmos estocasticos de busca inspirados no comportamento das especies na natureza [Coelho 2003].

O espaco de crencas e o repositorio de sımbolos que representam os conhecimentos adquiridos pelo espaco populacional ao longo do processo evolutivo. O espaco de crencas permite que os indivıduos sejam removidos da populacao sem que o conhecimento por eles adquiridos seja perdido. O espaco de crencas foi criado para guiar os indivıduos na direcao das melhores regioes do espaco de busca.

Os protocolos de comunicacao ditam as regras sobre quais indivıduos podem contribuir com conhecimentos para o espaco de crencas (funcao de aceitacao) e como o espaco de crencas vai influenciar a geracao de novos indivıduos (funcao de influencia).

Na funcao de aceitacao sao selecionados indivıduos que irao influenciar o espaco de crencas atual. A funcao de influencia estabelece como o conhecimento armazenado no espaco de crencas vai interferir nos operadores do espaco populacional. Geralmente e utilizada uma funcao de influencia para cada tipo de conhecimento armazenado.

4. Metodologia Utilizada

Este trabalho tem a caracterıstica de possuir auto-adaptacao de alguns parametros, sendo eles a funcao de aceitacao, a taxa de mutacao, a taxa de cruzamento, probabi-lidade da influencia ser exercida pelos conhecimentos situacional, normativo e situacional/normativo, o passo (tamanho) da mutacao sob influencia dos conhecimentos normativo e situacional/normativo e o intervalo normativo.

O algoritmo cultural desenvolvido nesse trabalho segue os passos apresentados pelo Algoritmo 4. Em seguida, os passos do algoritmo sao explicados.

Algoritmo Cultural Implementado Criar Espaco de Crenca; Inicializar a Populacao; Avaliar a Populacao Inicial; Enquanto (!Condicao de Parada()) faca

Selecionar Pais; Gerar novos Indivıduos pelas Funcoes de Influencia;

Avaliar os novos Indivıduos;

Selecionar Indivıduos para a Proxima Geracao; Atualizar Espaco de Crencas; Atualizar Parametros; Fim Enquanto

XIV ERI-PR 2007 ISBN: 978-85-7669-115-0

O primeiro passo do AC e a criacao do espaco de crencas. Isso envolve a inicializacao dos varios tipos de conhecimento e das probabilidades de utilizacao dos mesmos. Logo apos a inicializacao do espaco de crencas se tem a inicializacao da populacao de indivıduos que sera evoluıda. A representacao utilizada no trabalho foi real, onde cada gene do cromossomo armazena o valor de uma potencia gerada. A populacao e inicializada de maneira aleatoria e garante que nenhum indivıduo violara as restricoes de capacidade de producao de cada gerador. A unica restricao verificada posteriormente e a de demanda mınima.

A funcao de avaliacao e entao aplicada aos indivıduos da populacao inicial.

Esse ciclo e executado ate que a condicao de parada seja alcancada. Sao entao selecionados os pais que sao utilizados na geracao dos filhos. Essa selecao e realizada atraves de um torneio que favorece indivıduos factıveis com bom valor de aptidao e indivıduos infactıveis que violam pouco a restricao de demanda mınima.

Os filhos sao gerados atraves da aplicacao das funcoes de influencia (que sao melhores descritos na sequencia) e avaliados da mesma maneira que os indivıduos da populacao inicial. As funcoes de influencia sao modificacoes dos operadores de mutacao e cruzamento para utilizar o conhecimento armazenado ao longo da evolucao no espaco de crencas.

Os melhores indivıduos sao entao selecionados para compor a populacao da proxima geracao. Novos conhecimentos sao extraıdos da populacao e utilizados na atualizacao do espaco de crencas. Finalmente, alguns calculos que servem para atualizar os principais parametros do algoritmo sao feitos e serao utilizados na proxima iteracao do algoritmo.

Os principais componentes do AC, como por exemplo os tipos de conhecimento que foram codificados para a realizacao do trabalho, sao descritos a seguir.

Como todo algoritmo genetico, o espaco populacional desse trabalho possui uma populacao de cromossomos (chamados de indivıduos nesse trabalho por causa da terminologia dos algoritmos culturais), operadores geneticos, um metodo de selecao dos pais e um metodo de selecao dos indivıduos da proxima populacao (polıtica de substituicao na terminologia dos algoritmos geneticos).

Os operadores geneticos utilizados sao variacoes do cruzamento aritmetico e da mutacao gaussiana e sao melhores detalhados juntamente com os tipos de conhecimento.

4.2. Espaco de Crencas

Nesse trabalho foram utilizados tres tipos de conhecimentos: o conhecimento situacional, conhecimento normativo e o conhecimento situacional/normativo. A forma como eles foram desenvolvidos e melhor detalhada na Subsecao 4.2.1.

Uma caracterıstica importante do espaco de crencas e a forma como seus protocolos de comunicacao (funcao de aceitacao e funcoes de influencia) sao implementados. A funcao de aceitacao utilizada e a funcao de aceitacao dinamica, onde a quantidade de indivıduos aceitos varia de geracao para geracao.

XIV ERI-PR 2007 ISBN: 978-85-7669-115-0

A funcao de influencia principal e utilizada para escolher qual dos tipos de conhecimento sera utilizado para influenciar a geracao dos indivıduos. Nesse trabalho, a funcao de influencia principal adapta geracao a geracao as probabilidades de cada tipo de conhecimento de acordo com o sucesso que eles tiveram na ultima geracao. As demais funcoes de influencia sao detalhadas a seguir juntamente com os respectivos tipos de conhecimentos.

4.2.1. Tipos de Conhecimento

Os tipos de conhecimento sao a alma do algoritmo cultural. Cada conhecimento tem diferentes influencias nos operadores do espaco populacional. No caso particular desse algoritmo cada conhecimento interfere tanto no operador de mutacao quanto no operador de cruzamento.

A seguir e mostrado como foram desenvolvidos os conhecimentos.

A caracterıstica do conhecimento situacional e armazenar um ou mais dos melhores indivıduos encontrados ao longo do processo evolutivo e utiliza-los como guias na evolucao dos demais indivıduos. Em termos matematicos tem-se:

indi,j = melhork,j + mult ∗ percg ∗ (lim supj − lim infj) (5) tal que indi,j e o j-esimo gene (gerador) do indivıduo sendo mutado, melhork,j e o j-esimo gene de um dos melhores indivıduos armazenado no conhecimento situacional, mult e um fator multiplicativo adaptado ao longo das geracoes, percg e um valor aleatorio gerado de acordo com uma distribuicao gaussiana de media zero e desvio padrao um

(implementado de acordo com [Knuth 1998]), lim supj e o limite superior para o j-esimo gene e lim infj e o limite inferior para o j-esimo gene.

Na influencia do conhecimento situacional na mutacao, ao inves de aplicar a mutacao num componente do indivıduo sofrendo a mutacao, ele aplica a mutacao num componente de um dos melhores indivıduos e coloca esse valor no indivıduo sendo mutado.

Ja na influencia do conhecimento situacional no cruzamento um dos pais utilizados na geracao dos filhos e escolhido pelo processo de selecao descrito anteriormente e e implementado como uma combinacao linear dos dois indivıduos, que gera dois filhos. A combinacao linear permite que os filhos gerados estejam a uma distancia intermediaria dos dois pais, ou seja, permite explorar a regiao do espaco de busca entre os pais. Como um dos pais e um dos melhores indivıduos encontrados ao longo de toda evolucao, esse operador ajuda a explorar bem as regioes do espaco de busca ao redor dos melhores indivıduos.

(Parte 1 de 2)

Comentários