Ilha SolteiraIlha Solteira UNIVERSIDADE ESTADUAL PAULISTA “ JÚLIO DE MESQUITA FILHO” Câmpus de Ilha Solteira - SP INEDIO ARCARI A META-HEURÍSTICA DE BUSCA DISPERSA APLICADA NO PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO Ilha Solteira 2014 INEDIO ARCARI A META-HEURÍSTICA DE BUSCA DISPERSA APLICADA NO PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO Tese apresentada à Faculdade de Enge- nharia do Câmpus de Ilha Solteira- UNESP como parte dos requisitos para obtenção do título de Doutor em Engenharia Elétrica. Especialidade: Automação. Prof. Dr. Rubén Augusto Romero Lázaro Orientador Ilha Solteira 2014 Arcari A META-HEURÍSTICA DE BUIlha Solteira2014 137 Sim Tese (doutoradoEngenharia Elét30400007 Sim FICHA CATALOGRÁFICA Desenvolvido pelo Serviço Técnico de Biblioteca e Documentação Arcari, Inedio. A meta-heurística de busca dispersa aplicada no planejamento da expansão de sistemas de transmissão / Inedio Arcari. -- Ilha Solteira: [s.n.], 2014 137 f. : il. Tese (doutorado) - Universidade Estadual Paulista. Faculdade de Engenharia de Ilha Solteira. Área de conhecimento: Automação, 2014 Orientador: Rubén Augusto Romero Lázaro Inclui bibliografia 1. Planejamento da expansão de sistemas de transmissão. 2. Meta- heurísticas. 3. Busca dispersa. A668a DEDICO À minha família, em especial à minha esposa Carlene, por todo amor, apoio, confiança e incentivo em todos os momentos e ao meu filho Igor, que um dia vai entender as ausências do pai. AGRADECIMENTOS Meus agradecimentos a todos os familiares, amigos, professores e funcionários da FEIS- UNESP, que direta ou indiretamente contribuíram para a realização deste trabalho. Em especial, dedico meus agradecimentos: • A Deus, por ter iluminado meu caminho até aqui; • A minha querida esposa Carlene e ao meu filho Igor por suportar a dor da distância e acompanharem firmes neste passo tão importante; • Aos meus pais Verginia e Juarez e ao meu irmão Alessandro pela amizade, apoio e incen- tivo; • Ao Prof. Dr. Rubén, por todo ensinamento, incentivo, confiança e orientação, principal- mente pela amizade; • Aos Professores do DEE pelo acompanhamento nas bancas examinadoras, sugestões e incentivos; • Aos meus amigos e colegas do laboratório que de forma direta ou indiretamente me aju- daram, com o qual compartilhamos o nosso crescimento; • Aos colegas da UNEMAT, pelo companheirismo e pela amizade. • A Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) pela oportu- nidade e apoio financeiro. “A sabedoria consiste em ordenar bem a nossa própria alma.” Platão RESUMO Neste trabalho é realizada uma análise teórica e a implementação computacional de um algo- ritmo de Busca Dispersa especializado para resolver o problema de planejamento da expansão de sistemas de transmissão (PPEST) de energia elétrica estático. O problema de planejamento consiste em determinar entre um conjunto de circuitos candidatos, aqueles que quando forem incorporados ao sistema apresentarem o menor custo de investimento possível. Este problema é considerado complexo e difícil de ser resolvido por ser um problema não linear inteiro misto, altamente ilhado, envolvendo “explosões” combinatórias. A meta-heurística de busca dispersa é um algoritmo evolutivo que se propõe a combinar soluções de qualidade e de diversidade do espaço de busca. O algoritmo de busca dispersa desenvolvido apresentou-se altamente eficiente para encontrar soluções de ótima qualidade para todos os problemas testados comparados com a literatura consultada, especializada na área. A garantia da diversidade oferecida pelo algoritmo é adicionada intencionalmente como forma de evitar, ou mesmo avançar por ótimos locais. Ou- tro fato importante é que o método opera sobre um conjunto reduzido de soluções do espaço de busca criteriosamente gerado, que faz reduzir significativamente o número de combinações que são realizadas. Rotinas geradas com a utilização de algoritmos heurísticos construtivos gulosos de Garver e Villasana-Garver-Salon para modelos como o de Transportes e o modelo DC no PPEST apresentaram alto desempenho neste trabalho. Uma perturbação controlada nos custos de instalação das linhas de transmissão foi decisiva para que o processo de geração de soluções (factíveis, diversas e/ou com qualidade) fosse altamente eficiente, sendo possível encontrar o ótimo global em alguns problemas ainda nesta etapa de geração de soluções. Mecanismos de melhoramento local aplicados durante o processo do algoritmo de busca dispersa especializado completa a implementação apresentada neste trabalho. São utilizados para testes os sistemas de Garver de 6 barras e 15 ramos, IEEE de 24 barras e 41 ramos, Sul Brasileiro de 46 barras e 79 ramos, o Colombiano de 93 barras e 155 ramos e o Norte-Nordeste de 87 barras e 183 ramos. Palavras-chave: Planejamento da expansão de sistemas de transmissão. Meta-heurísticas. Busca dispersa. ABSTRACT This work presents a theoretical analysis and computational implementation of a specialized Scatter Search algorithm to solve the static transmission network expansion planning (TNEP) problem of electric power systems. The objective of such planning problems is to determine a set of circuits among the candidates in which not only satisfy the demands but also the minimum investment cost is at hand. This problem is considered as a complex mixed integer nonlinear programming (MINLP) problem that has a lot of local optimum problem. The scatter search is an evolutionary method with the objective of maintaining a set of diverse and high-quality candidate solutions. The proposed scatter search algorithm has been applied in engineering opti- mization problems especially in electric power system problems and has presented high quality solutions. The diversity sets ensure to avoid getting trapped in a local optimum. Another im- portant factor is that the proposed methodology reduces the search space and consequently the number of combinations is reduced. In this work, a high quality solution of TNEP is obtained using the greedy constructive heuristic algorithms such as Garver, and Villasana-Garver-Salon that work based on Transport model and DC model respectively. In this work, in order to gene- rate the initial solutions, a controlled disturbance has been added in the costs of the transmission lines in order to obtain diverse and high quality solutions that lead to find the global optimum for some problems even in the initial generation step. Moreover, the proposed scatter search algorithm presents a local improvement phase during the implementation. In order to show the effectiveness of the proposed algorithm, 5 case studies are conducted such as Garver 6-bars and 15 branches , IEEE 24-bars and 41 branches , South Brazilian 46-bars and 79 branches, Colom- bian 93-bars and 155 branches, and the North-Northeast 87-bars and 87 branches systems. Keywords: Expansion planning of transmission systems . Metaheuristics . Scatter search. LISTA DE FIGURAS Figura 1 Ilustração da Busca Dispersa de 1977.. . . . . . . . . . . . . . . . . . . 56 Figura 2 Fluxograma do algoritmo de busca dispersa. . . . . . . . . . . . . . . . . 61 Figura 3 Ilustração da Distância Mínima entre as soluções do conjuntoP e o CSQ . . 66 Figura 4 Atualização Dinâmica do CSQ. . . . . . . . . . . . . . . . . . . . . . . 68 Figura 5 Estratégia de reconstrução do CSQ. . . . . . . . . . . . . . . . . . . . . 70 Figura 6 Estratégia de atualização do CSQ com 2 Níveis. . . . . . . . . . . . . . . 71 Figura 7 Estratégia de atualização do CSQ com três Níveis. . . . . . . . . . . . . . 72 Figura 8 Trajetória dopath relinking . . . . . . . . . . . . . . . . . . . . . . . . 74 Figura 9 Trajetória dopath relinkingsimultâneo. . . . . . . . . . . . . . . . . . . 75 Figura 10 Ilustração do Sistema de 6 barras de Garver.. . . . . . . . . . . . . . . . 82 Figura 11 Codificação dos ramos do sistema de 6 barras e 15 ramos de Garver.. . . . . 82 Figura 12 Vetor que representa as linhas instaladas na configuração base do sistema de 6 barras de Garver.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Figura 13 Vetor que representa as linhas que serão adicionadas na configuração base do sistema de 6 barras de Garver.. . . . . . . . . . . . . . . . . . . . . . . 83 Figura 14 Vetor que representa uma configuração corrente do sistema com as novas li- nhas adicionadas na configuração base do sistema de 6 barras de Garver.. . . 83 Figura 15 Distância entre as soluções representadas pelos vetoresn(1) en(2). . . . . . 87 Figura 16 Exemplo de um esquema dos passos dopath relinkingelaborado para ser uti- lizado como Método de Combinação das soluções do CSQ na implementação da BD aplicada no PPEST.. . . . . . . . . . . . . . . . . . . . . . . . . 90 Figura 17 Busca local por troca simples.. . . . . . . . . . . . . . . . . . . . . . . 92 Figura 18 Ilustração do Sistema de 6 barras de Garver. As linhas pontilhadas repre- sentam novos ramos candidatos. As linhas adicionadas estão indicadas entre parênteses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Figura 19 Ilustração da configuração base do Sistema de 24 barras IEEE. As linhas adi- cionadas estão indicadas entre parênteses.. . . . . . . . . . . . . . . . . 98 Figura 20 Ilustração da configuração base do Sistema de 46 barras Sul Brasileiro. As li- nhas pontilhadas representam novos ramos candidatos. As linhas adicionadas estão indicadas entre parênteses.. . . . . . . . . . . . . . . . . . . . . . 99 Figura 21 Ilustração da configuração base do Sistema de barras Colombiano (Plano P3). As linhas pontilhadas representam novos ramos candidatos.. . . . . . . . . 101 Figura 22 Ilustração da configuração base do Sistema Norte-Nordeste (Plano P1). As linhas pontilhadas representam novos ramos candidatos.. . . . . . . . . . 102 LISTA DE TABELAS Tabela 1 Vetores binários gerados pelo Método de Geração de Soluções Diversas. . . 64 Tabela 2 Distância entre as soluçõesx ey. . . . . . . . . . . . . . . . . . . . . . 65 Tabela 3 Combinação das soluçõesx ey com o uso doscore. . . . . . . . . . . . . 67 Tabela 4 Tabela de custos mínimo, original e máximo do sistema de 6 barras quando submetidos a uma perturbação de±10% (em milhões de dólares).. . . . . . 85 Tabela 5 Busca local por inviabilização de ramos (custos em milhões de dólares).. . . 86 Tabela 6 Distância mínima entre as soluções. . . . . . . . . . . . . . . . . . . . . 88 Tabela 7 Dados de barras do sistema 24 barras.. . . . . . . . . . . . . . . . . . . 97 Tabela 8 Dados de barras do sistema Sul Brasileiro.. . . . . . . . . . . . . . . . . 100 Tabela 9 Dados de barras do sistema Colombiano (Plano P3).. . . . . . . . . . . . 100 Tabela 10 Dados de barras do sistema Norte Nordeste.. . . . . . . . . . . . . . . . 103 Tabela 11 Dados de barras do sistema 24 Barras.. . . . . . . . . . . . . . . . . . . 105 Tabela 12 Linhas adicionadas na solução ótima.. . . . . . . . . . . . . . . . . . . 105 Tabela 13 Linhas adicionadas na Geração deP. . . . . . . . . . . . . . . . . . . . . 106 Tabela 14 Linhas adicionadas na Geração deP. . . . . . . . . . . . . . . . . . . . . 107 Tabela 15 Solução com linhas adicionadas para o sistema Norte Nordeste.. . . . . . . 108 Tabela 16 Tabela dos valores incumbentes em dólares, gerados em cada parte do método de BD por sistema teste para o Modelo de Transportes.. . . . . . . . . . . 108 Tabela 17 Tabela dos valores incumbentes em dólares, gerados em cada parte do método de BD por sistema teste para o Modelo DC.. . . . . . . . . . . . . . . . 109 Tabela 18 Dados de barras do sistema de Garver de 6 barras.. . . . . . . . . . . . . 117 Tabela 19 Sistema de Garver de 6 barras e 15 ramos.. . . . . . . . . . . . . . . . . 117 Tabela 20 Dados de barras do sistema IEEE 24 barras.. . . . . . . . . . . . . . . . 118 Tabela 22 Dados do sistema Sul Brasileiro de 46 barras.. . . . . . . . . . . . . . . . 120 Tabela 23 Dados de linhas do sistema Sul Brasileiro de 46 barras.. . . . . . . . . . . 121 Tabela 24 Dados do sistema Colombiano de 93 barras.. . . . . . . . . . . . . . . . 124 Tabela 25 Dados de linhas do sistema Colombiano de 93 barras.. . . . . . . . . . . . 126 Tabela 26 Dados do sistema Norte-Nordeste de 87 barras de 2002.. . . . . . . . . . 131 Tabela 27 Dados de linhas do sistema Norte-Nordeste de 87 barras de 2002.. . . . . . 134 LISTA DE ABREVIAÇÕES E SIGLAS AC Alternating Current(Corrente Alternada-CA) AG Algoritmo Genético AHC Algoritmo Heurístico Construtivo BD Busca Dispersa CSQ Conjunto de Soluções de Qualidade DC Direct Current(Corrente Contínua-CC) GRASP Greedy Randomized Adaptative Search Procedure PPL Problema de Programação Linear PNL Programação Não-Linear PPNLIM Problema de Programação Não-Linear Inteiro Misto PPEST Problema de Planejamento de Expansão de Sistemas de Transmissão RCL Restricted Candidate List SA Simulated Annealing TS Tabu Search VGS Villasana-Garver-Salon VNS Variable Neighborhood Search LISTA DE SÍMBOLOS ci j custo da instalação de um circuito no ramoi j d vetor de demanda dmin distância mínima dist valor limitante para uma distância f vetor dos fluxos fi j fluxo total no ramoi j f ′ vetor dos fluxos nas linhas novas, que podem ser adicionadas fo vetor dos fluxos nas linhas existentes f ′i j vetor dos fluxos nas linhas novas, adicionadas no ramoi j f o i j fluxo no ramoi j pelas linhas existentes f i j fluxo máximo permitido para um circuito no ramoi j g vetor de geração g vetor de máxima capacidade de geração nas barras de geração hash função de checagem de vetores idênticos ni j número de circuitos adicionados no ramoi j no i j número de circuitos na configuração existente no ramoi j ni j vetor do número máximo de adições permitidas no ramoi j γo i j susceptância equivalente de todas as linhas existentes no ramoi j θi ângulo de fase da tensão na barrai Ω conjunto das barras que não estão ilhadas Ω1 conjunto de circuitos existentes na configuração base Ω2 conjunto de circuitos correspondentes aos novos ramos Ωb conjunto de barras do sistema elétrico Pool conjunto de soluções de elite armazenadas durante o processo S matriz de incidência nó-ramo do circuito elétrico So matriz de incidência nó-ramo das linhas existentes score índice de sensibilidade v investimento a partir das novas configurações aplicadas ao sistema vob valor da função objetivo SUMÁRIO 1 INTRODUÇÃO 27 2 PLANEJAMENTO 31 2.1 INTRODUÇÃO 31 2.2 MODELAGEM MATEMÁTICA BÁSICA PARA O PPEST 32 2.2.1 Modelo DC 33 2.2.2 Modelo Híbrido Linear 34 2.2.3 Modelo de Transportes 36 2.3 MODELOS MATEMÁTICOS MAIS COMPLEXOS 38 2.3.1 Modelo Matemático para o Planejamento Multiestágio 38 2.3.2 Modelo Matemático para o Planejamento com Restrições de Segurança 39 2.3.3 Modelo Matemático para o Planejamento com Mercado Elétrico Competitivo 40 2.3.4 Modelo Matemático para o Planejamento com fluxo de corrente AC 40 2.4 MÉTODOS DE OTIMIZAÇÃO CLÁSSICOS 41 3 REVISÃO SOBRE AS META-HEURÍSTICAS 43 3.1 INTRODUÇÃO 43 3.2 HEURÍSTICAS 43 3.2.1 O Algoritmo Heurístico Construtivo 44 3.2.2 A Heurística de Busca Através de Vizinhança 45 3.3 META-HEURÍSTICAS 46 3.3.1 Simulated Annealing(SA) 47 3.3.2 Algoritmo Genético (AG) 48 3.3.3 Tabu Search(TS) 50 3.3.4 Greedy Randomized Adaptative Search Procedure(GRASP) 51 3.3.5 Busca em Vizinhança Variável (VNS) 52 4 REVISÃO SOBRE A BUSCA DISPERSA 55 4.1 INTRODUÇÃO 55 4.2 TEORIA BÁSICA SOBRE A BUSCA DISPERSA 55 4.2.1 Modelo de Busca Dispersa de Glover (1998) 57 4.2.2 Busca Dispersa Aplicada 61 4.2.2.1 Problema de Otimização Não Linear Irrestrito 62 4.2.2.2 Problema da Mochila 63 4.3 PROPOSTAS AVANÇADAS DA HEURÍSTICA DE BUSCA DISPERSA 67 4.3.1 Conjunto de Soluções de Qualidade 67 4.3.1.1 Atualização Dinâmica do CSQ 68 4.3.2 Controle de Diversidade e Soluções Duplicadas 71 4.4 DETALHES ADICIONAIS SOBRE A BUSCA DISPERSA 73 5 BUSCA DISPERSA APLICADA AO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 77 5.1 INTRODUÇÃO 77 5.2 AHC DE GARVER PARA O MODELO DE TRANSPORTES 77 5.3 AHC DE VILLASANA-GARVER-SALON PARA O MODELO DC 78 5.4 ALGORITMO DE BUSCA DISPERSA ESPECIALIZADO PARA O PPEST. 80 5.4.1 Codificação 81 5.4.2 Geração de soluções 83 5.4.3 Método de melhoramento por retirada de linhas irrelevantes 84 5.4.4 Geração do Conjunto de Soluções DiversificadasP 84 5.4.5 Melhoramento Local por Inviabilização de Ramos 86 5.4.6 Geração do CSQ 87 5.4.7 Estratégia Utilizada para o Método de Combinação das Soluções de Qualidade 89 5.4.8 Melhoramento Local por Troca Simples 91 6 TESTES E RESULTADOS 95 6.1 INTRODUÇÃO 95 6.1.1 BD Aplicado em PPEST usando Garver para o Modelo de Transportes 95 6.1.1.1 Sistema de Garver de 6 Barras e 15 Ramos sem Redespacho 96 6.1.1.2 Sistema IEEE de 24 Barras sem redespacho 97 6.1.1.3 Sistema Sul Brasileiro sem Redespacho 97 6.1.1.4 Sistema Colombiano (Plano P3) sem Redespacho 100 6.1.1.5 Sistema Norte-Nordeste (Plano P1) sem Redespacho 101 6.1.2 BD Aplicado em PPEST Usando o AHC de VGS para o Modelo DC 103 6.1.2.1 Sistema de Garver de 6 Barras e 15 ramos sem Redespacho 103 6.1.2.2 Sistema IEEE de 24 Barras sem Redespacho 104 6.1.2.3 Sistema Sul Brasileiro sem Redespacho 105 6.1.2.4 Sistema Colombiano (Plano P3) sem Redespacho 106 6.1.2.5 Sistema Norte-Nordeste (Plano P1) sem Redespacho 107 6.2 CONCLUSÕES PARCIAIS. 107 7 CONCLUSÕES 111 REFERÊNCIAS 113 ANEXO A - Dados dos Sistemas Testes 117 27 1 INTRODUÇÃO Um sistema elétrico eficiente e confiável é fundamental para a base que impulsiona a econo- mia de um país, proporcionando uma cadeia produtiva eficiente, agilidade nas tarefas, o conforto e o bem-estar, dentre outros inúmeros benefícios. Sistemas elétricos mesmo de pequeno porte podem parecer simples, mas na verdade exigem grandes conhecimentos de engenharia, mate- mática e outras áreas, construídas ao longo da história para o seu funcionamento. Em linhas gerais um sistema elétrico pode ser dividido em três partes distintas: os sistemas de geração, transmissão e distribuição de energia elétrica. Como são necessários altos investimentos para as construções destes sólidos sistemas, existe a preocupação em realizar profundos estudos em torno da viabilidade e operacionalização, com a preocupação constante em minimizar os custos. Existem atualmente alimentando os sistemas elétricos várias formas de fontes de energia como a energia solar, de usinas hidrelétricas, eólica, usinas atômicas, térmicas, dentre outras. Nos últimos anos o aumento da demanda de energia elétrica por conta do crescimento do setor industrial e pela variedade de equipamentos elétricos que vem sendo produzidos torna-se evidente a preocupação com a geração, a transmissão e a distribuição de energia elétrica para abastecer de forma eficiente todos os setores da economia. Os impactos de um colapso do sis- tema elétrico podem ser graves para a economia de um país, por isso, é crescente a preocupação dos governos em torno da garantia da estabilidade de um sistema elétrico eficiente e cada vez mais longe de riscos. Baseados no histórico de crescimento do setor energético e da projeção de demanda futura, são realizados profundos estudos procurando estabelecer o equilíbrio entre geração e demanda. Estes estudos levam sempre em consideração a minimização dos custos necessários tanto para a segurança bem como da expansão do sistema. Gradativamente, os sistemas elétricos estão sendo interligados buscando a estabilidade e a segurança juntamente com a construção de novas usinas em virtude das demandas atual e futura e que nem sempre estão próximas dos centros consumidores, o que aumenta o desafio no planejamento do sistema de transmissão de energia elétrica. Por conta da localização e da distância dos centros consumidores em que as fontes gerado- ras de energia estão instaladas, o número de combinações de caminhos por onde as linhas de transmissão podem ser construídas pode ser muito grande. Com esforço razoável e com técnicas clássicas é possível encontrar soluções de boa qualidade e até ótimas para sistemas de pequeno porte, mas as dificuldades crescem para sistemas de médio e grande porte, pois o número de combinações possíveis cresce exponencialmente. Com os sistemas elétricos já instalados, a preocupação consiste no planejamento para a sua 28 1 INTRODUÇÃO expansão onde estão envolvidos vários fatores, dentre os quais podemos relacionar a capacidade de geração do sistema, a demanda, os custos para construir as redes que farão a interligação en- tre geração e demanda, a questão ambiental e muitos outros. Para resolver estes problemas foram propostos ao longo de décadas mecanismos matemáticos atrelados a avançadas enge- nharias, potencializados com o avanço da informatização. Ferramentas matemáticas poderosas incorporadas a sistemas robustos de computação ofereceram uma nova visão no conceito de otimização, atualmente alvo de muitos estudos. No planejamento da expansão de sistemas de transmissão, considera-se a topologia cor- rente como a configuração base do sistema sobre o qual se pretende propor a adição de novos circuitos procurando atender a demanda. Este planejamento geralmente é feito em horizontes de curto, médio e longo prazos tendo em vista o tempo necessário para construção ou ampli- ação de unidades geradoras e construção das linhas de transmissão. Portanto, a previsão futura de crescimento da demanda para um sistema elétrico é primordial para um planejamento ade- quado, fornecendo informações reais para as tomadas de decisões, como a da construção de novas redes e em que sequência ao longo do tempo. Para resolver o problema de planejamento da expansão da transmissão existe o modelo estático, que considera a ampliação do sistema em um único estágio, e o modelo dinâmico, ou seja, multiestágio, em que o planejamento da expansão do sistema ocorre em dois ou mais momentos. Em ambos os modelos são necessárias as informações de demanda e geração em cada estágio. Este problema pode ser formulado como um problema de programação não linear inteiro misto (PNLIM), considerado um problema NP-completo de difícil tratamento. Apli- cando uma proposta de investimento neste problema ele pode ser reduzido a um problema de programação linear que simplesmente verifica a viabilidade da proposta. Um dos critérios de segurança mais utilizados no planejamento é o critério (N-1), onde é retirada uma linha da configuração proposta e o sistema ainda deve operar sem cortes de carga. Para o tratamento do problema de planejamento de expansão de sistemas de transmissão é necessária uma modelagem que represente adequadamente todas as condições para a operação, como os fluxos de carga, a geração fornecida, a demanda e outros. Os modelos em destaque e atualmente utilizados são os modelos de transporte, híbrido linear, híbrido não linear, o linear disjuntivo, o DC e o CA. Nem todos os modelos podem ser resolvidos por técnicas de otimização clássica, como por exemplo,Branch and Bounde Decomposição de Benders. Estas técnicas são muito eficien- tes para alguns sistemas de pequeno e médio porte, mas ainda apresentam dificuldades nos de grande porte, pois exigem um grande esforço computacional. Nestes casos existe a necessidade da implementação de técnicas mais sofisticadas, uma vez que o problema torna-se difícil de ser resolvido quando incorpora simultaneamente variáveis reais e inteiras. Em geral, estes pro- blemas em sua essência são de programação linear inteira mista ou de programação não linear 1 INTRODUÇÃO 29 inteira mista o que aumenta em muito o grau de dificuldade. Nesses casos são empregadas téc- nicas de solução especializadas em realizar uma busca inteligente nos espaços de solução com a intenção de obter o ótimo global do problema. Pode existir um grande número de ótimos locais em que a técnica pode convergir. Essas técnicas, denominadas heurísticas e meta-heurísticas, dependem muito da experiência do pesquisador para a criação e adequação de parâmetros e índices de sensibilidade, pois as buscas em sua maioria são do tipo passo a passo. Destacam-se por permitirem a sondagem de regiões do espaço de busca de forma eficiente, aceitam soluções “boas” mesmo não sendo ótimos globais e são muito versáteis, onde pequenas alterações na sua rotina podem oferecer maior rapidez durante a busca acompanhada da diminuição do tempo computacional usado. Como contribuição para o planejamento da expansão de sistemas de transmissão este tra- balho faz uma aplicação da técnica de busca dispersa, do inglês “scatter search”, que foi desen- volvido a princípio para resolver problemas na área de economia. Neste trabalho foi elaborado um algoritmo de Busca Dispersa (BD) especializado para o problema de planejamento do modo estático com o modelo de transportes e com o modelo DC. Em linhas gerais, a meta-heurística de BD trabalha com um espaço de busca reduzido onde seleciona um conjunto com até 100 soluções (factíveis ou não, pois podem ser melhoradas) de tal forma que representam todas as regiões do espaço. Dessas 100 soluções são selecionadas 20, em geral 10 de melhor valor na função objetivo e 10 mais distantes ou diversas (por um critério de distância pré-estabelecido) dentre aquelas já selecionadas. Este conjunto menor será alvo de combinações que irão gerar um novo conjunto de soluções, que por um processo de melhoramento, se forem de melhor qua- lidade poderão substituir as piores do conjunto que é base para as combinações. Este processo pode ser repetido de acordo com a conveniência do pesquisador e a melhor solução factível durante o processo é considerada solução para o problema. Este trabalho está organizado da forma descrita a seguir. No Capítulo 2 são tratados os problemas relacionados ao planejamento da expansão de sis- temas de transmissão, com abordagens sobre a modelagem matemática para estes problemas e são descritos os modelos existentes na literatura, como Modelo de Transportes, Modelo Híbrido Linear e Modelo DC. As principais heurísticas, destacando o Algoritmo Heurístico Construtivo, a heurística de Busca Através de Vizinhança e das principais meta-heurísticas sendo oSimulated Annealing, os Algoritmos Genéticos, oTabu Search, GRASP e a Busca em Vizinhança Variável, serão brevemente apresentadas. Os elementos das técnicas básicas que sustentam este trabalho são tratados conceitualmente no Capítulo 3. Uma revisão sobre a Busca Dispersa é apresentada no Capítulo 4, destacando a teoria básica envolvida na heurística, e suas variações, que foram propostas no livro “Scatter Search” de Laguna e Martí (2003). 30 1 INTRODUÇÃO Detalhes da aplicação do algoritmo de Busca Dispersa especializado aplicado ao Problema de Planejamento da Expansão de Sistemas de Transmissão são efetivamente apresentados e de- talhados no Capítulo 5, adicionalmente são apresentadas as propostas de implementação com- putacional desenvolvidas e aplicadas. A técnica porPath Relinkingutilizada para realizar as combinações necessárias e o algoritmo de melhoria das soluções estão detalhados. No Capítulo 6 são apresentados os resultados dos testes realizados com sistemas de refe- rência correspondentes às seguintes bases de dados: Garver, IEEE, Sul Brasileiro, Colombiano e Norte-Nordeste, respectivamente de 6, 24, 46, 93 e 87 barras ou nós. O Capítulo 7 está reservado para as conclusões e discussões futuras que o projeto atual tem verificado durante as pesquisas, apresentando novos direcionamentos. 31 2 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 2.1 INTRODUÇÃO A operação adequada de um sistema elétrico deve garantir a estabilidade entre a geração e a demanda, ou seja, no mercado de energia elétrica a demanda fundamentalmente orienta o volume de produção de energia elétrica que precisa ser injetado no sistema. É fato que, com raras exceções, a demanda de energia cresce ao longo dos anos e junto com ela vem o desafio de manter o equilíbrio deste sistema. A maneira como deve ser feita a ampliação do sistema para satisfazer esta demanda é preocupação para o planejamento da ampliação dos três principais subsistemas do setor elétrico: geração, transmissão e distribuição. O gerenciamento do sistema elétrico geralmente está sob o controle de entidades devidamente regulamentadas que definem metas a partir de um planejamento para avaliar, por exemplo, a possibilidade da construção de usinas hidrelétricas, ou de térmicas, construção de novas linhas de transmissão, verificar se dois sistemas independentes podem ser interligados e se isto traria benefícios e mais “saúde” para o sistema comparado com a configuração corrente. O governo participa do controle do mercado energético juntamente com as partes envolvidas, regulamentando este mercado competitivo que cresce, preocupado com a economia e a sustentabilidade. A maneira com que são tomadas as decisões no planejamento para a construção de unidades geradoras, linhas de transmissão e instalação de equipamentos sempre leva em consideração a minimização dos custos e a maximização dos lucros. Portanto, a ordem temporal das instalações é fundamental uma vez que é possível assim adiar os investimentos. Também faz parte do planejamento o acompanhamento dos fenômenos climáticos que determinam a viabilidade e a necessidade da entrada das usinas térmicas no sistema. Muitas usinas geradoras ou linhas de transmissão e distribuição que estão fora de operação ou operando com capacidade reduzida, do ponto de vista do planejamento estão estrategica- mente preparadas para entrar em operação sempre que forem necessárias. No período de secas, por exemplo, que ocorre em muitas regiões do Brasil, provocam o esvaziamento dos reservató- rios das hidrelétricas. Isto obriga que o sistema coloque em operação as usinas térmicas, para restabelecer o patamar normal de geração, embora com um custo muito maior de operação. Este custo geralmente é repassado diretamente para a conta do consumidor, que pode também ser subsidiado pelo governo para não incidir completa ou parcialmente sobre o consumidor. Então são inúmeras as variáveis que podem ser consideradas em um planejamento do sistema elétrico. O planejamento da expansão de sistemas de transmissão pode ocorrer de forma estática, 32 2 PLANEJAMENTO em que para um dado horizonte de planejamento é considerada a instalação de todos os equi- pamentos em um único estágio ou multiestágio de forma dinâmica, onde as instalações dos equipamentos e operação são realizadas em momentos bem definidos dentro deste horizonte de planejamento, geralmente a longo prazo. São considerados como dados ou variáveis para o pla- nejamento a topologia base, os ramos candidatos, os dados de geração e demanda, as restrições de investimento e de capacidade de transmissão, a reatância dos circuitos e muitos outros. A solução de um problema de planejamento do setor elétrico depende de um modelo mate- mático e uma técnica de solução. Na sequência deste capítulo são apresentados conceitos sobre os modelos matemáticos que sustentam a proposta deste trabalho. 2.2 MODELAGEM MATEMÁTICA BÁSICA PARA O PPEST A modelagem matemática é a área do conhecimento que estuda os sistemas reais procu- rando representá-los matematicamente com a finalidade de avaliar o comportamento dos mes- mos. Muitas pesquisas são desenvolvidas para entender, explicar e posteriormente tentar incor- porar certos fenômenos oriundos de problemas da vida real. O conhecimento da dinâmica do problema é fundamental para o progresso em direção à sua resolução. A profundidade e o vo- lume de conhecimento que se têm do problema aliados às ferramentas disponíveis orientam as pesquisas que em geral culminam com a construção de um modelo que represente o sistema mais adequadamente possível. Os modelos matemáticos são ferramentas utilizadas para repre- sentar os sistemas reais com a preocupação de fazer uma previsão do comportamento deles de acordo com uma variação controlada de determinadas variáveis que foram consideradas no modelo. Como os modelos são representações matemáticas dos problemas, a resolução destes está diretamente ligada à eficiência das ferramentas matemáticas de resolução que se têm dis- poníveis no dado momento. Em muitos casos, o fato de se ter em poder muitas informações do problema não significa ter garantias de uma qualidade melhor da solução do problema. Estes problemas podem tornar-se tão complexos que as ferramentas matemáticas e a capacidade de processamento computacional disponíveis ainda sejam insuficientes para uma avaliação mais adequada de seu comportamento. Desta forma, fica evidente que na tarefa de se resolver alguns destes problemas, ferramentas matemáticas são adaptadas ou até criadas e modelos matemáti- cos mais arrojados são propostos. Desta forma é significativo o crescimento do domínio dos pesquisadores sobre uma diversidade de problemas ao longo dos anos. Muitos modelos, bem como as técnicas de resolução para estes modelos, têm sofrido cons- tantes alterações, principalmente com a evolução da computação. A velocidade e a capacidade de armazenamento de informações que os computadores trouxeram para os cálculos proporcio- naram uma nova forma de se analisar os problemas de modo geral. Problemas antes sem solução 2.2 MODELAGEM MATEMÁTICA BÁSICA PARA O PPEST 33 puderam ter seu comportamento observado com mais propriedade e se não foram encontradas as soluções exatas no mínimo foram atingidos ótimos locais com alguma qualidade. Um modelo de programação matemática é composto de uma função objetivo e um conjunto de restrições. Estas restrições relacionam um conjunto de variáveis de decisão através de um conjunto de equações ou inequações algébricas. No planejamento de expansão de um sistema de transmissão deve ser considerada a topo- logia de rede com os circuitos que já existem na configuração base. O planejamento deve ser capaz de identificar quais linhas devem ser adicionadas a fim de encontrar a configuração ótima para que o sistema opere adequadamente no horizonte de planejamento especificado. Muitos modelos foram propostos para o problema de planejamento da expansão de sistemas de transmissão (PPEST), dentre os quais serão abordados o Modelo de Transportes, o Modelo Híbrido Linear e o Modelo DC. Os Modelos de Transportes e Híbrido são versões relaxadas do Modelo DC que é considerado pelos especialistas o modelo ideal para o PPEST. Estes modelos são problemas de otimização que, de acordo com a sua formação, podem conter variáveis de decisão inteiras e reais, apresentar relações algébricas lineares e não lineares. As leis que regem os fluxos em circuitos elétricos utilizadas nos modelos são as leis de Kirchhoff. Um sistema está operando adequadamente quando estão sendo atendidas estas duas leis, respectivamente a primeira lei, conhecida como Lei das Correntes de Kirchhoff (LCK), em que “a soma algébrica de todas as correntes em qualquer nó de um circuito é igual a zero”, e a Lei das Tensões de Kirchhoff (LTK), em que “a soma algébrica de todas as tensões ao longo de qualquer caminho fechado em um circuito é igual a zero” (NILSSON; RIEDEL, 2009, p. 24). 2.2.1 Modelo DC Em problemas de planejamento de sistemas de transmissão, o modelo mais utilizado por especialistas da área é o modelo DC. Este modelo atende as duas leis de Kirchhoff para um sistema elétrico em que todas as barras e todas as linhas existentes em operação estão condici- onadas devem satisfazer. O problema de planejamento da expansão da transmissão em sistemas elétricos, de acordo com o modelo DC, pode ser escrito como o modelo de otimização para o PPEST apresentado em (1). min v = ∑ (i, j) ci j ni j (1) s.a. S f+g= d 34 2 PLANEJAMENTO fi j − γi j (n o i j +ni j )(θi−θ j) = 0 ∣ ∣ fi j ∣ ∣≤ (no i j +ni j ) f i j 0≤ g≤ g 0≤ ni j ≤ ni j ni j inteiro fi j irrestrito θ j irrestrito ∀(i, j) ∈Ω em que: v : investimento das novas adições de circuito realizadas no sistema; ci j : custo da instalação de um circuito no ramoi j ; ni j : número de circuitos adicionados no ramoi j ; S: matriz de incidência nó-ramo do circuito elétrico; f : vetor dos fluxos; g: vetor de geração; d: vetor de demanda; fi j : fluxo total no ramoi j ; γi j : susceptância de todas as linhas; no i j : número de circuitos na configuração existente no ramoi j ; θi : ângulo de fase da tensão na barrai; f i j : fluxo máximo permitido para um circuito no ramoi j ; g: vetor de máxima capacidade de geração nas barras de geração; ni j : número máximo de adições permitidas no ramoi j ; Ω: representa o conjunto de todos os circuitos instalados no ramo, da configuração base e os novos adicionados. 2.2.2 Modelo Híbrido Linear O modelo híbrido linear foi proposto por Villasana, Garver e Salon (1985) com o intuito de contornar os problemas de convexidade do modelo DC. O modelo híbrido linear combina a 2.2 MODELAGEM MATEMÁTICA BÁSICA PARA O PPEST 35 eficiência do modelo de transportes no tratamento de barras isoladas do sistema principal com a precisão que o modelo DC oferece do sistema, pois o modelo DC opera com todas as informa- ções do sistema, principalmente com as susceptâncias de todos os circuitos. O relaxamento de algumas restrições do modelo DC dá condições para que as ferramentas de resolução matemáti- cas disponíveis possam oferecer resultados com algumas garantias. Para resolver um problema de programação não linear inteiro misto são relaxadas as restrições que produzem maior com- plexidade. O problema relaxado é de programação linear. As soluções ótimas globais geradas na programação linear serão aceitas como soluções ótimas locais relaxadas para o problema não linear. Nesta modelagem, o problema resultante é um problema de programação linear inteira mista. As leis de Kirchhoff são atendidas distintamente em circuitos existentes. A primeira lei deve ser aplicada em cada barra para todos os ramos, sejam eles existentes na configuração base ou novos ramos adicionados, e a LTK deve ser atendida somente pelos laços da rede original formados pelos circuitos existentes na topologia base. Pelo modelo híbrido, quando uma nova linha for adicionada neste mesmo ramo ela só vai precisar atender a LCK, ou seja, o fluxo de potência que vai percorrer esta linha poderá ser diferente da linha que já existia na configuração base neste circuito. O modelo híbrido linear pode ser escrito como o modelo de otimização para o PPEST apresentado em (2). min v = ∑ (i, j) ci j ni j (2) s.a. S f′+So fo+g= d f o i j − γo i j (θi−θ j) = 0 ∀(i, j) ∈Ω1 ∣ ∣ f o i j ∣ ∣≤ f i jn o i j ∀(i, j) ∈Ω1 ∣ ∣ f ′i j ∣ ∣≤ f i jni j ∀(i, j) ∈Ω 0≤ g≤ g 0≤ ni j ≤ ni j ni j inteiro f o i j e f ′i j irrestritos θ j irrestrito ∀ j ∈Ωb no sistema conexo No modelo, as variáveis são representadas por: v : investimento das novas adições de circuito realizadas no sistema; ci j : custo da instalação de um circuito no ramoi j ; 36 2 PLANEJAMENTO ni j : número de circuitos adicionados no ramoi j ; S: matriz de incidência nó-ramo do sistema elétrico completo; f ′: vetor dos fluxos nas linhas novas, que podem ser adicionadas; So: matriz de incidência nó-ramo das linhas existentes; fo: vetor dos fluxos nas linhas existentes; g: vetor de geração; d: vetor de demanda; f o i j : fluxo no ramoi j pelas linhas existentes; γo i j : susceptância equivalente de todas as linhas existentes no ramoi j ; θi : representa o ângulo de tensão na barrai que está conexa na topologia existente; f i j : fluxo máximo permitido para um circuito no ramoi j ; no i j : número de circuitos na configuração existente no ramoi j ; f ′i j : vetor dos fluxos nas linhas novas, adicionadas no ramoi j ; g: vetor de máxima capacidade de geração nas barras de geração; ni j : número máximo de adições permitidas no ramoi j ; Ω1: conjunto de circuitos existentes na configuração existente; Ω: conjunto das barras que não estão ilhadas; Ωb: conjunto de barras do sistema elétrico. 2.2.3 Modelo de Transportes O Modelo de Transportes foi proposto inicialmente por Garver (1970b) na década de 70. Este foi o primeiro modelo aplicado para o problema do planejamento da expansão de sistemas de transmissão e representou um marco nas pesquisas no setor elétrico. No modelo de trans- portes adaptado para o PPEST somente a LCK é atendida pela configuração base da rede e para as novas linhas adicionadas. O problema em questão é de programação linear inteira mista, compreendendo equações e restrições lineares e variáveis de decisão inteiras e reais. Neste pro- blema é considerado que a soma dos fluxos de que entram em uma barra deve ser igual ao fluxo que sai desta mesma barra de acordo com a LCK. O modelo de transportes configurado para o problema de planejamento da expansão de sistemas de transmissão pode ser escrito como o modelo de otimização apresentado em (3). 2.2 MODELAGEM MATEMÁTICA BÁSICA PARA O PPEST 37 min v = ∑ (i, j) ci jni j (3) s.a. S f+g= d ∣ ∣ fi j ∣ ∣≤ (ni j +no i j ) f i j 0≤ g≤ g 0≤ ni j ≤ ni j ni j inteiro fi j irrestrito Este problema de minimização procura o investimentov ótimo do modelo que depende do custoci j para a instalação de um novo circuito no ramo da barrai para a barraj. As variáveis consideradas são: v : investimento a partir das novas configurações aplicadas ao sistema; ci j : custo da instalação de um circuito no ramoi j ; ni j : número de circuitos adicionados no ramoi j ; S: matriz de incidência nó-ramo do circuito elétrico; f : vetor dos fluxos; fi j : fluxo total ativo no ramoi j ; g: vetor de geração; d: vetor de demanda; no i j : número de circuitos na configuração base no ramoi j ; f i j : fluxo máximo permitido no ramoi j ; g: vetor de máxima capacidade de geração nas barras de geração; ni j : número máximo de adições permitidas no ramoi j ; A equação minv ∑(i, j)ci j ni j indica que o investimento depende do custo de cada linha e do número de linhas que se pretende adicionar no sistema. A LCK é representada na rela- ção S f+ g = d, atendida em cada barra do sistema. A inequação ∣ ∣ fi j ∣ ∣ ≤ (ni j + no i j ) f i j res- tringe os limites de fluxo nos dois sentidos entre as barrasi e j e as restrições 0≤ g ≤ g expressam os limites de geração, enquanto a inequação 0≤ ni j ≤ ni j restringe o número de linhas novas no ramoi j . A complexidade do problema aumenta quando a restrição do número 38 2 PLANEJAMENTO de linhas a serem adicionadas é incorporada ao modelo, pois devem assumir valores inteiros. Vale observar que, de acordo com a restrição do módulo,fi j está implicitamente limitado por −(no i j +ni j) f i j ≤ fi j ≤ (no i j +ni j) f i j . Quando uma linha atrativa é adicionada no circuito, o fluxo de potência é redistribuído, fato este que deve ser verificado resolvendo um problema de programação linear inteira mista, iden- tificando quais ramos serão candidatos a receber a adição de novas linhas, dentre os ramos que se apresentarem sobrecarregados, desta forma, o processo se repete até que todas as sobrecargas sejam eliminadas do sistema (ROMERO, 1993). Este modelo não é considerado ideal para a resolução do PPEST, pois não existem garantias de que a solução esteja próxima do modelo DC porque obrigatoriamente o modelo não leva em consideração a LTK. As variáveis reais e inteiras no modelo tornam o modelo complexo, mas o fato de não aparecerem equações não lineares consiste em sua principal vantagem. 2.3 MODELOS MATEMÁTICOS MAIS COMPLEXOS Alguns modelos matemáticos foram formulados tentando representar com a maior fideli- dade possível os problemas envolvendo situações reais. Quanto maior a proximidade de um modelo com a realidade, em geral, as estratégias de resolução aumentam em complexidade. Alguns modelos que são tratados a seguir foram desenvolvidos de forma a considerar alguns fatos de forma independente, como modelos que levam em conta os fatores de risco e segurança do sistema, outros consideram o mercado elétrico ou dividem o sistema em estágios. 2.3.1 Modelo Matemático para o Planejamento Multiestágio Nos modelos desenvolvidos para resolver problemas de expansão de sistemas de trans- missão multiestágio são levados em conta a configuração ótima de operação do sistema, a disposição das linhas de transmissão na topologia do sistema e os investimentos necessários. Neste contexto é determinado o melhor momento num horizonte de planejamento em que cada etapa do processo de expansão é mais interessante economicamente, atendendo sempre os pré- requisitos entre geração e demanda. Um horizonte de planejamento geralmente compreende grandes intervalos de tempo, algo em torno de 10, 20, 30 ou mais anos e estes horizontes são subdivididos em vários estágios. Em cada estágio, num horizonte é decidida a aplicação dos investimentos levando em conta vários fatores. O tempo necessário para construção de linhas de transmissão, construção de usinas, definir a ordem dos investimentos que devem ser aplicados, fazer uma previsão da geração futura bem como uma previsão da demanda ao longo do tempo, são alguns exemplos de decisões. No problema de otimização correspondente, o crescimento da demanda e da geração ao 2.3 MODELOS MATEMÁTICOS MAIS COMPLEXOS 39 longo do tempo, num horizonte considerado, são representados por crescimentos discretos apro- ximados para determinados anos que correspondem aos estágios, assumindo que o sistema não sofra alterações entre dois estágios consecutivos. Vários trabalhos foram desenvolvidos para tentar reduzir custos de investimento usando esta metodologia multiestágio para planejamento de sistemas elétricos e podem ser observados, por exemplo, em Haffner (2000), Silva Junior (2005) dentre outros. Definida uma taxa anual de desconto I, a atualização dos valores correntes dos custos de investimento, para o ano de referênciat0, a partir do ano inicialt1, dentro de um horizonte de planejamento detT − t1 anos emT estágios, é determinado pela função objetivo dada pela Equação 4. c(x) = (1− I)t1−t0c1(x)+(1− I)t2−t0c2(x)+ . . .+(1− I)tT−t0cT(x), t = 1. . . ,T. (4) em quex representa as linhas a serem construídas,cT(x) representa o custo do investimento no estágiot. Partindo desta formulação para a função objetivo, de modo geral basta acrescentar nos modelos de fluxo de potência para problemas estáticos o parâmetro tempo, transformando-os em modelos multiestágios. 2.3.2 Modelo Matemático para o Planejamento com Restrições de Segurança Poucos trabalhos da literatura especializada podem ser citados, como Silva Junior (2005), Seifu, Salon e List (1989), que ainda são realizados em torno de um planejamento de expan- são de um sistema elétrico considerando restrições de segurança. O planejamento é realizado em uma primeira fase sem considerar as restrições de segurança e na segunda são simuladas retiradas de circuitos e adição de novos circuitos, com a vantagem de necessitar de um esforço computacional relativamente pequeno. No trabalho de Silva Junior (2005), a restrição de segurança para sistemas de transmissão utilizado foi o critério (N-1), realizando testes no sistema em que no planejamento da expansão mesmo com a retirada de uma linha o sistema ainda opere sem a existência de linhas sobrecar- regadas, com cortes de carga. O trabalho de planejamento resolve apenas o problema de fluxo de potência ativa. Um dos primeiros trabalhos envolvendo restrições de segurança foi produzido em 1989 por Seifu, Salon e List (1989), que organiza o procedimento exemplificando com a aplicação do modelo DC para o sistema de 6 barras. 40 2 PLANEJAMENTO 2.3.3 Modelo Matemático para o Planejamento com Mercado Elétrico Competitivo A concorrência no setor elétrico tem modificado profundamente a forma de tratamento dado ao comércio da energia, definindo metas de confiabilidade cada vez mais exigentes. A partici- pação efetiva das partes interessadas nas decisões envolvendo o processo de expansão de um sistema elétrico procura garantir que as principais necessidades sejam atendidas e os serviços sejam ofertados com qualidade. Muitas metodologias de planejamento não consideram em sua formulação fatores mercadológicos nas características principais de reestruturação de mercados de energia em fase de planejamento. A influência do governo sobre o comércio energético, em situações adversas, interfere drasticamente no mercado elétrico e principalmente em planeja- mentos em que fatores desta natureza são desconsiderados, como incentivos fiscais, exigências de ampliação do sistema em função de metas de governo e outros. Modelos que incorporam o fator de concorrência no setor elétrico é discutido em muitos trabalhos e aumentam a cada dia, como exemplo os trabalhos de Bresesti et al. (2009), Haffner (2000) e de Singh, Hao e Papalexopoulos (1998). Os interesses dos três grandes setores do mercado elétrico, que são geração, transmissão e distribuição acompanham as tendências do mercado. Neste sentido, a relação entre oferta e demanda estimulam a concorrência, afetando diretamente os preços praticados no mercado. As necessidades de previsão de geração, de demanda, de recursos de investimento são itens primordiais para a correta operação do sistema elétrico, mas são fortemente afrontadas pelas incertezas de mercado, que têm grande influência como, por exemplo, de colocar ou não em operação as usinas térmicas. As térmicas por sua vez têm um custo muito alto de operação com relação às hidrelétricas, em curtos intervalos de tempo. Outra discussão gira em torno do custo de construção de uma usina hidrelétrica, que é muito alto e o retorno do investimento somente a longo prazo. 2.3.4 Modelo Matemático para o Planejamento com fluxo de corrente AC Dentre os tipos de fluxo de corrente elétrica utilizados em sistemas elétricos podemos des- tacar o fluxo de corrente DC (Direct Current) que corresponde a corrente contínua e o fluxo de corrente AC (Alternating Current) que corresponde à corrente alternada. O modelo AC é o que mais se aproxima da representação do fenômeno físico do comportamento dos fluxos nos sistemas elétricos, porém poucos trabalhos são publicados na literatura especializada de planejamento da expansão. O planejamento de expansão de sistemas elétricos se desenvolveu em grande parte utili- zando modelos relaxados deste, pois a alta complexidade a que chega o modelo quando in- corpora os reativos do sistema o torna pouco atraente. Outra dificuldade é o tratamento com problemas altamente ilhados e não convexos que o modelo AC apresenta. 2.4 MÉTODOS DE OTIMIZAÇÃO CLÁSSICOS 41 As vantagens do uso do modelo AC no planejamento da expansão datransmissão segundo Rider (2006) são: a consideração de reativos no sistema, alocação de fontes de potência reativa de maneira otimizada, determinação de perdas ativas exatas, incorporação de controladores FACTS, entre muitos outros. Ainda conforme Rider (2006), o planejamento da expansão de sistemas de transmissão é realizado em dois momentos bem definidos. Assim, num primeiro passo são realizados plane- jamentos para expansão levando em consideração somente o fluxo de potência ativa e muitas vezes sem a consideração de perdas dependendo do modelo. Em um segundo momento e com- plementar é realizada a alocação ótima de fontes de potência reativa para melhorar as condições de operação do sistema elétrico considerando a operação sob o ponto de vista do fluxo de carga AC. O processo de otimização não ocorre simultaneamente o que poderia gerar apenas confi- gurações subótimas quando otimizamos a instalação de linhas de transmissão e a alocação de fontes reativas através de dois processos sucessivos de otimização. O modelo AC vem sendo estudado por especialistas ainda sem muita popularidade devido aos problemas mencionados, mas com avanços na computação e no quesito ferramental matemático é uma promessa futura. 2.4 MÉTODOS DE OTIMIZAÇÃO CLÁSSICOS USADOS EM PLANEJAMENTO DE SIS- TEMAS DE TRANSMISSÃO Muitos métodos de otimização foram desenvolvidos ao longo dos anos sempre com a pre- ocupação de obter o resultado mais próximo possível da realidade. Os métodos de otimização podem ser classificados em: a) métodos exatos, também chamados de métodos clássicos de otimização; b) métodos aproximados, que podem ser divididos em algoritmos heurísticos e meta-heurísticos. O algoritmo de Decomposição deBendersfoi um dos mais utilizados dentre os métodos exatos para resolver o problema de planejamento de sistemas de transmissão. O algoritmo de Decomposição deBendersdecompõe matematicamente problemas complexos ou de grande porte através da resolução de uma sucessão de problemas menores. Aplicações da utilização desta técnica para o problema de planejamento de sistemas de transmissão podem ser encontradas em Romero e Monticelli (1994) e Haffner (2000). Outro método exato que vem ganhando espaço é o algoritmoBranch and Boundainda pouco usado em planejamento da expansão de sistemas de transmissão. Trata-se de um algo- ritmo enumerativo em que é construída uma árvore com nós representando problemas candi- datos e os ramos representando as restrições. Desta forma são enumeradas todas as soluções inteiras factíveis do problema implícita ou explicitamente garantindo a obtenção da solução 42 2 PLANEJAMENTO ótima. Pesquisas envolvendo o uso do algoritmoBranch and Boundno problema de planeja- mento da transmissão podem ser consultados em Haffner (2000). Os métodos aproximados são tratados em maiores detalhes no capítulo seguinte. 43 3 REVISÃO SOBRE AS META-HEURÍSTICAS 3.1 INTRODUÇÃO O advento da computação influenciou o avanço de muitas áreas do conhecimento, muitos problemas foram resolvidos, principalmente nas áreas de matemática e das engenharias. As téc- nicas de solução clássicas são ferramentas que funcionam com parâmetros muito bem definidos e as regiões de busca precisam de uma modelagem apropriada. Os problemas que apresentam descontinuidade nos intervalos de domínio, com valores discretos, existência de regiões não convexas, não podiam ser tratados pela otimização clássica. Os problemas ganharam dimen- sões que não podiam ser tratados pela modelagem matemática conhecida. Este fato ganhou destaque com o crescimento da matemática e da computação, em que grandes problemas surgi- ram quando muitos parâmetros começaram a ser considerados em um único problema além de explosões combinatórias que começaram a ser frequentes. Novas ferramentas foram adaptadas baseadas no conhecimento existente dos problemas em conjunto com a experiência dos pes- quisadores. Neste contexto, os métodos aproximados, ou seja, as heurísticas e meta-heurísticas foram utilizadas para resolver os problemas que a otimização clássica não tinha condições de resolver. A maioria dos sistemas de teste para o PPEST que são tratados neste trabalho já foram resolvidos por métodos exatos. As soluções encontradas pelos testes realizados com algoritmos aproximados são comparados com as soluções obtidas pelos métodos exatos. Neste capítulo são apresentadas as principais heurísticas e meta-heurísticas, podem ser consultadas com mais detalhes em Resende et al. (2010). 3.2 HEURÍSTICAS As heurísticas são métodos de otimização que surgiram para contornar e resolver proble- mas não resolvidos pelos métodos clássicos. Certos problemas tem algumas características bem específicas que devem ser atendidas, como: garantir convexidade nas regiões de busca e pos- suir funções contínuas e deriváveis no intervalo considerado. Os problemas reais facilmente fogem desse padrão. No contexto do planejamento da expansão da transmissão, as heurísticas ganharam força nas décadas de 60 e 70 como pode ser visto nos trabalhos de Garver na área de Planejamento em Engenharia Elétrica. Problemas reais começaram a ganhar um aumento de dimensão considerável, e exigiu-se computadores com capacidade de processamento cada vez maior. Mesmo que as heurísticas apresentem dificuldades em atingir ótimos globais elas podem oferecer ótimos locais. 44 3 REVISÃO SOBRE AS META-HEURÍSTICAS Como as heurísticas possuem mecanismos de busca de solução realizados por um processo passo-a-passo, várias formas de configuração foram propostas ao longo dos anos. Podem ser simples enquanto a experiência e o bom senso norteiam o pesquisador e especializadas quando necessitam de modelos mais estruturados como, por exemplo, o algoritmo genético que é inspi- rado na busca de soluções com a evolução genética das espécies. Em cada etapa de um processo heurístico, ajustado por indicadores de sensibilidade, gera-se uma nova solução de melhor ou pior qualidade dependendo do algoritmo, em busca do ótimo global. Em muitas situações, a qualidade da solução depende do número de operações que são realizadas, ou seja, quanto mais caminhos puderem ser avaliados, mais qualidade se agrega na solução obtida. Atualmente a velocidade com que uma heurística encontra uma determinada solução é importante, pois para se resolver muitos problemas de grande porte é necessário avaliar um número muito alto de combinações, e por isso estão sendo estudados algoritmos inteligentes que fazem uma busca mais seletiva. São inúmeros os desafios enfrentados, como a limitação de processamento dos computadores e a necessidade de se resolver problemas reais que são de grande porte. Alguns problemas reais dependem do conhecimento de soluções praticamente instantâneas necessárias para as tomadas de decisões importantes e que disponibilizem um tempo de reação suficiente. Algumas das principais heurísticas podem ser encontradas em Resende et al. (2010) e na sequência desta seção será dado um tratamento mais específico ao algoritmo heurístico cons- trutivo e à heurística de busca através de vizinhança. 3.2.1 O Algoritmo Heurístico Construtivo O algoritmo heurístico construtivo (AHC) é uma técnica de otimização muito difundida e aplicada em diversas áreas do conhecimento e é considerado um algoritmo eficiente. De- pendendo de certas circunstâncias ou do porte do problema pode não ser eficiente, quanto à qualidade da solução encontrada. Ele pode ser utilizado como único mecanismo ou operar combinado com outras técnicas de otimização. O tipo de AHC mais utilizado isoladamente é o Algoritmo Guloso. Uma heurística construtiva, ou míope, consiste em tentar encontrar uma boa solução, consi- derando a cada interação somente o próximo passo, ou seja, o critério de escolha é basicamente local. Ela parte de uma solução vazia e passo-a-passo constrói uma solução de forma incremen- tal. Adiciona componentes individuais (nós, arcos, variáveis). O método guloso procura sempre o melhor componente que é escolhido e depois inserido na solução até gerar uma solução com- pleta. O componente escolhido em cada passo é, em geral, o melhor candidato de acordo com algum critério, ou seja, um indicador de sensibilidade ajustado para cada problema. A construção de uma solução para o problema da mochila dá uma idéia do algoritmo heu- rístico construtivo guloso. São definidas inicialmente para o problema as limitações do volume 3.2 HEURÍSTICAS 45 da mochila e os preços e volumes de cada item disponível para ser adicionado. O índice de sensibilidade é definido pela razão do preço pelo volume de cada item. Os itens então são dis- postos em ordem decrescente pelo valor desta razão obtida. Uma solução pode começar a ser construída de forma gulosa adicionando-se o primeiro item que detiver o maior valor obtido das razões recentemente calculadas. Segue-se o critério de adicionar na mochila os itens de acordo com a ordem do maior para o menor dos valores das razões em cada passo enquanto o volume máximo da mochila não seja violado. Caso o próximo item da sequência extrapole o volume da mochila, percorre-se a sequência na ordem decrescente na intenção de encontrar algum item que ainda pode ser adicionado na mochila. Quando mais nenhum item puder ser adicionado então uma solução para o problema da mochila estará criada pelo procedimento guloso. Um algoritmo guloso básico gera somente soluções factíveis, pois em cada passo são adi- cionados somente os atributos que não violam as restrições do problema. Para esta tarefa de adicionar um atributo é usado um indicador de sensibilidade que pode variar de acordo com cada problema e da experiência do pesquisador. 3.2.2 A Heurística de Busca Através de Vizinhança A heurística de busca através de vizinhança executa uma varredura em torno de uma solução inicialmente apresentada para o algoritmo e está restrita a uma região de vizinhança também previamente escolhida. Muito utilizada em problemas que dispõem de pelo menos uma solução factível inicial e se pretende proporcionar uma melhoria. Cada passo do algoritmo faz com que uma nova solução seja atingida avançando sobre a vizinhança da solução corrente. Somente são aceitas soluções de melhor qualidade que a solução corrente. Quando a última solução encontrada não puder mais ser melhorada dentro da vizinhança definida, será tomada como a melhor solução obtida pelo processo de busca partindo da solução inicial apresentada. Para implementar uma heurística de busca através de vizinhança é fundamental uma co- dificação adequada. Tal codificação deve representar as soluções do problema, contemplando um conjunto de variáveis de decisão realmente significativas para o problema ou uma forma equivalente de representação de uma proposta de solução. Esta codificação deve ser precisa o suficiente para garantir que duas codificações distintas representem soluções distintas do espaço de busca. Uma proposta de solução está adequadamente codificada se ela for passível de avaliação na função objetivo e se sua factibilidade puder ser avaliada. A qualidade de uma codificação implica diretamente na eficiência da implementação das etapas do algoritmo heurístico. A proposta de codificação define o tamanho do espaço de busca para um problema especí- fico, em que uma codificação adequada pode oferecer uma qualidade maior a este espaço. Desta forma este espaço pode conter ou não soluções de elite, além de poder ter representadas regiões 46 3 REVISÃO SOBRE AS META-HEURÍSTICAS factíveis e infactíveis. Uma codificação deficiente corre o sério risco de gerar um espaço de busca que não contenha as soluções ótimas para o problema, pois a heurística vai proporcionar buscas sobre esta região. Muitos tipos de estrutura de vizinhança podem ser criados para cada tipo de problema. A heurística depende desta estrutura para realizar uma trajetória de busca eficiente. A partir de uma solução inicial representada por um vetor codificado, define-se a estrutura de vizinhança, ou seja, o vetor inicial sofre perturbação em um ou mais de seus elementos pelo critério definido. Todos os vetores solução que são gerados a partir da perturbação caracterizam a vizinhança do vetor inicial. Dentre todas as soluções desta vizinhança, a solução que apresentar melhor valor na função objetivo será tomada como solução corrente, e o processo é repetido até que a solução corrente não possa ser substituída por uma de melhor qualidade. Novas soluções poderão ser alcançadas somente com propostas de soluções iniciais diferentes. Na definição de vizinhança é prudente que esta estrutura gere se possível somente soluções factíveis, pois ao contrário a heurística deve ter condições de dar um tratamento mais apurado sobre as soluções vizinhas. Uma forma geral da heurística de busca através de vizinhança pode atender os seguintes passos: a) identificar e extrair os dados relevantes do problema. Escolher uma codificação apropri- ada para representar uma solução. Definir a forma de avaliação da qualidade da solução na função objetivo. Definir a estrutura de vizinhança; b) encontrar uma solução inicial para compor a solução corrente; c) na vizinhança proposta, avaliar e identificar a melhor solução vizinha da solução corrente; d) se a melhor solução vizinha avaliada pela função objetivo apresentar qualidade superior relativamente à solução corrente, a solução vizinha vai ocupar o lugar de solução corrente e volta ao passo c, caso contrário o processo termina. A solução corrente será considerada ótima local encontrada pela heurística de busca através da vizinhança. As heurísticas de busca local e busca através de vizinhança compartilham do mesmo prin- cípio, pois avançam sempre sobre regiões factíveis. Mas fica evidente que a segunda avança a passos mais lentos que a primeira. Enquanto a busca local constrói uma única solução (de qua- lidade ou não), a busca em vizinhança analisa um número maior de soluções e avança somente sobre soluções de elite durante a busca. 3.3 META-HEURÍSTICAS As meta-heurísticas são métodos de otimização que combinam as ferramentas de busca lo- cal com técnicas de busca mais sofisticadas. As meta-heurísticas têm como objetivo suprir as 3.3 META-HEURÍSTICAS 47 dificuldades que as ferramentas de busca local enfrentam. O fato mais evidente destas dificul- dades é a forma prematura em que as heurísticas atingem ótimos locais, interrompendo a busca. As meta-heurísticas criam estratégias inteligentes adaptando-se com as heurísticas. Um exem- plo é tornar dinâmica a estrutura de vizinhança da heurística de busca através da vizinhança, em que, a cada passo no progresso da busca, o tamanho da vizinhança pode ser modificado, bem como a forma de composição desta vizinhança. Dentre uma variedade de meta-heurísticas existentes foram escolhidas oSimulated Anne- aling, os Algoritmos Genéticos, oTabu Search, o GRASP e a Busca em Vizinhança Variável para uma breve apresentação, que são consideradas importantes nesta linha de pesquisa. 3.3.1 Simulated Annealing(SA) Algumas meta-heurísticas foram desenvolvidas levando em consideração a observação de certos fenômenos naturais ou controlados sob condições específicas, como é o caso doSimu- lated Annealing. No processo de produção de cristais perfeitos chamada deannealing, os ma- teriais são elevados a altas temperaturas e seguindo uma rotina de controle de resfriamento assumem a forma perfeita esperada. As altas temperaturas provocam extrema agitação das mo- léculas que perdem sua estrutura original. Com um resfriamento lento e controlado levando em conta as leis da termodinâmica, em especial, o equilíbrio termodinâmico, é esperado um rearranjo específico das moléculas, que quando atingido, este novo material se transformará em um cristal perfeito. O algoritmo deSimulated Annealingtem uma estrutura semelhante ao processoannealing na produção dos cristais e sua formulação básica acompanha os seguintes passos: a) identificar e extrair os dados relevantes do problema. Escolher uma codificação apro- priada para representar uma solução. Definir a forma de avaliação da qualidade da solução na função objetivo. Definir a estrutura de vizinhança. Escolher os parâmetros do SA como as temperaturas de início e fim, ou outro critério, definir os níveis de temperatura, um controle sobre as tentativas de transição entre dois níveis em cada temperatura, e um parâmetro de controle da diminuição de temperatura; b) encontrar uma solução inicial para compor a solução corrente; c) em uma vizinhança proposta, avaliar e identificar uma solução vizinha da solução corrente escolhida aleatoriamente; d) caso a solução vizinha avaliada pela função objetivo apresente qualidade superior em relação à solução corrente, será autorizada uma transição, a solução vizinha vai ocupar o lugar da solução corrente e volta-se ao passo c. Caso contrário, pode ser utilizado o valor 48 3 REVISÃO SOBRE AS META-HEURÍSTICAS obtido por uma expressão que relaciona o valor da função objetivo da solução corrente e a nova gerada na temperatura em questão. Este será usado para comparar a um número aleatório gerado entre 0 e 1, para autorizar um passo para esta solução de pior qualidade ou manter a solução atual. Voltar ao passo c; e) caso um número especificado de tentativas de transição for atingido sem melhoria na solução ir ao passo f, caso contrário seguir para o passo c; f) se a condição de convergência do passo e for satisfeita, pare, assumido como critério de parada. Caso contrário atualizar a temperatura e o número de transições permitidas sem melhoria pelos parâmetros correspondentes e voltar ao passo c. Uma breve avaliação deste mecanismo mostra que quanto maior a queda na temperatura, menor é a chance de soluções de pior qualidade serem aceitas. O processo termina de forma muito semelhante ao fenômeno físico doannealingonde a temperatura se estabiliza com a do ambiente externo ao controle. O caráter aleatório atribuído à escolha de uma solução vizinha re- duz significativamente o trabalho de busca na vizinhança e pode ser considerada uma vantagem quando se pensa em tempo de processamento. Mesmo com a capacidade de fugir de ótimos locais nas temperaturas de início do processo apresenta a desvantagem de não ter informações sobre a qualidade das soluções não selecionadas. 3.3.2 Algoritmo Genético (AG) A meta-heurística do AG foi largamente difundida desde a sua criação na década de 70, intensificando o seu uso em problemas de pesquisa operacional em 80. O AG foi desenvolvido para resolver problemas de otimização inspirado no processo evolutivo das espécies e de seleção natural. A teoria sobre o AG pode ser encontrada em Goldberg (1989). Uma codificação para uma solução no AG tenta reproduzir a configuração de um cromos- somo estudado pela Genética. Na realidade cada cromossomo é composto por duas cadeias de informações em que cada posição (alelo) do cromossomo contém as características dos pais, um da mãe e outro do pai. Um cromossomo no AG corresponde a um vetor que carrega as informações das características dos pais e cada posição (alelo) do vetor são representadas por um código binário, que representa a existência ou ausência da referida característica naquele indivíduo. A diversidade de indivíduos de uma determinada espécie ocorre geneticamente pelo fenô- meno da recombinação, que é responsável por provocar recombinações variadas entre as in- formações genotípicas recebidas do pai e da mãe. Como ocorre na evolução natural das espé- cies, ao passar dos tempos, os indivíduos começam a ficar muito parecidos e até idênticos, o 3.3 META-HEURÍSTICAS 49 mecanismo da recombinação adaptado para o AG apresenta um comportamento parecido. A combinação de soluções no AG pode gerar soluções de melhor ou pior qualidade. A mutação é outro fator natural que ocorre nas espécies e pode gerar indivíduos diferentes dos existentes, pois aleatoriamente seleciona e altera alguns alelos depois da recombinação que necessariamente não representam as informações dos pais. No AG, a mutação consiste na troca de 0 para 1 ou 1 para 0 em algumas posições selecionadas por algum indicador das propostas de solução que estão sendo geradas. As etapas de um AG básico podem ser formulados a partir dos seguintes passos: a) identificar e extrair os dados relevantes do problema; escolher uma codificação apropriada para representar uma solução; definir a forma de avaliação da qualidade da solução na função objetivo; definir a estrutura de vizinhança; escolher os parâmetros do AG, como, o tamanho da população, as taxas de recombinação e mutação, o tipo de seleção e um critério de parada; b) gerar um conjunto de soluções iniciais (população) para se tornarem as soluções corren- tes; c) avaliar a qualidade de todas as soluções que representam a população e atualizar a incum- bente; d) se o critério de parada for satisfeito, pare. Em caso contrário, ir ao passo e; e) implementar um mecanismo de seleção; f) implementar um mecanismo de recombinação; g) implementar um mecanismo de mutação, atualizar a população atual e voltar ao passo c. Em versões mais recentes, o AG foi adaptado para alguns problemas e os vetores solução não assumem mais somente valores binários, mas também, inteiros, discretos, reais ou outra forma não numérica. Este tipo de adaptação provocou uma melhor representação das variáveis de muitos problemas, consequentemente melhores resultados puderam ser atingidos. O mecanismo de seleção determina o número de participações que deve ter cada elemento de uma população na formação de uma nova. A seleção proporcional por muito tempo foi utilizada embora com muitas críticas. O processo de seleção nas fases inicias do AG são pra- ticamente aleatórias. Muitos estudos foram lançados na tarefa de incorporar estratégias mais promissoras tentando substituir a seleção proporcional e principalmente o uso da roleta. A seleção por torneio ganhou força na medida em que os problemas de otimização podiam oferecer maior diversidade na geração da nova população. 50 3 REVISÃO SOBRE AS META-HEURÍSTICAS A recombinação no AG gera descendentes que vão carregar uma parcela contínua de um gerador e outra parcela de outro, no caso de um ponto de recombinação, mas podem ser de dois ou mais pontos. A mutação completa o fato natural de gerar diversidade nos descendentes em que se propõe uma perturbação na combinação de uma proposta de solução. A mutação procura realizar uma rápida busca numa vizinhança muito próxima e a forma de recombinação faz uma busca um pouco maior no espaço de busca. 3.3.3 Tabu Search(TS) Glover (1996), grande pesquisador na área de otimização clássica, desenvolveu o meca- nismo TS no intuito de criar uma estratégia inteligente de busca que não estivessem preocu- padas em simulações que se assemelhavam aos fenômenos comportamentais de espécies como o AG ou de simulação de fenômenos controlados no caso doAimulated Annealing. Para a implementação de um TS básico basta seguir o roteiro a seguir: a) identificar e extrair os dados relevantes do problema. Escolher uma codificação apropri- ada para representar uma solução. Definir a forma de avaliação da qualidade da solução na função objetivo. Definir a estrutura de vizinhança. Identificar os atributos que devem ser proibidos e um critério de aspiração. Definir o critério de parada; b) encontrar uma solução inicial para compor a solução corrente; c) na vizinhança proposta, avaliar e identificar todas as soluções vizinhas e ordená-las por qualidade sendo a primeira solução da lista a melhor solução vizinha; d) substituir a solução corrente pela solução vizinha de melhor qualidade que não tenha atributo proibido, ou que satisfaça o critério de aspiração; e) atualizar a incumbente e a lista de atributos proibidos. Parar se o critério de parada for satisfeito senão voltar ao passo c. Umas das importantes diferenças entre o TS e as outras meta-heurísticas é a presença de um indicador de sensibilidade. Uma lista de atributos proibidos permite ao algoritmo realizar caminhos sobre soluções de pior qualidade que a solução corrente. No caso da vizinhança ter todas as soluções de pior qualidade que a solução corrente é realizado um avanço para a melhor solução entre as piores nesta vizinhança. A busca deve usufruir de uma estratégia que evite avaliar uma solução já visitada pelo algoritmo. Isto pode ser feito armazenado-se todas as soluções encontradas ou armazenar apenas os atributos que já foram visitados. Problemas de espaço de memória de armazenamento motivaram implementações que de- pendem de outras informações que permitam evitar avaliar soluções já visitadas. 3.3 META-HEURÍSTICAS 51 O critério de aspiração completa o algoritmo, em que mesmo comum atributo proibido de uma solução vizinha ela possa ser aceita. Um critério pode ser ter qualidade superior àquela da solução incumbente na função objetivo e eliminar temporariamente a proibição. Pode ser usado o critério de aspiração para uma solução que apresente melhor qualidade que as vizinhas nas últimasn iterações. 3.3.4 Greedy Randomized Adaptative Search Procedure(GRASP) Uma junção das heurísticas de busca através da vizinhança e da heurística de busca gulosa realizadas por Feo e Resende (1995) resultaram na construção da meta-heurística GRASP (Gre- edy Randomized Adaptative Search Procedure). A estrutura desta metodologia mescla fases de busca bem distintas como pode ser observado nos passos a seguir: a) identificar e extrair os dados relevantes do problema. Escolher uma codificação apropri- ada para representar uma solução. Definir a forma de avaliação da qualidade da solução na função objetivo. Escolher uma heurística construtiva e uma estratégia de busca local; b) implementar uma fase de pré-processamento; c) realizar a fase de busca construtiva; d) realizar a fase do pós-processamento de busca local. Caso seja possível, atualizar a in- cumbente; e) parar se um critério de parada for satisfeito, caso contrário voltar ao passo c. Na fase do pré-processamento são identificadas as soluções mais promissoras por algum critério de análise de atributos das soluções para permitir que o algoritmo de busca construtiva opere num espaço de busca mais seletivo. A observação de certos componentes presentes nestas soluções fornece pistas de que elas não sejam promissoras e devam ser evitadas, reduzindo assim consideravelmente o espaço de busca e concentrando-se em soluções mais interessantes. Na fase construtiva do GRASP são geradas soluções de qualidade com um algoritmo heurís- tico construtivo do tipo guloso generalizado munido de estratégias que superem suas limitações. Em alguns problemas, o algoritmo guloso pode enfrentar dificuldades em encontrar a solução ótima. Esse algoritmo guloso permite gerar um número considerável de propostas de soluções distintas. A proposta mais usada para generalizar o algoritmo guloso é a construção da lista reduzida chamada de RCL (Restricted Candidate List) cujo tamanho é variável, construída em função da qualidade das soluções candidatas. A fase construtiva pode ser realizada pelos passos a seguir: 52 3 REVISÃO SOBRE AS META-HEURÍSTICAS a) nesta fase construtiva é escolhida uma solução inicial em construção que pode ser inicial- mente vazia; b) construir uma RCL incorporando os elementos mais atraentes sob a orientação de um in- dicador de sensibilidade. Os componentes da RCL são determinados de forma adaptativa; c) escolhe-se um dos elementos da RCL para ser adicionado na solução em construção cor- rente; d) caso a solução em construção corrente seja factível ou um critério de parada seja atingido, conclui-se a fase construtiva, ou caso contrário voltar ao passo b. São variadas as configurações que podem ser produzidas para gerar a RCL, com índices de sensibilidade ajustados para cada problema em específico e de acordo com cada configuração de solução. O tamanho da RCL também pode ser controlado por outro indicador de sensibilidade específico também. Na fase de pós-processamento, uma busca local na vizinhança da solução gerada constru- tivamente procura soluções de qualidade, que pode assumir configurações muito simples até muito complexas. 3.3.5 Busca em Vizinhança Variável (VNS) A busca em vizinhança variável (Variable Neighborhood Search- VNS) é uma meta- heurística para resolver problemas de otimização cuja ideia básica consiste na variação sis- temática do tamanho da vizinhança durante uma busca local. Esta meta-heurística foi proposta na década de 90 por Mladenović e Hansen (1997), e não permite degradação da solução na função objetivo para realizar uma transição. Fatos importantes na VNS, como, por exemplo, a relação que existe entre as configurações de estrutura de vizinhança e ótimos locais, são apresentado em Resende et al. (2010). Um con- junto de estruturas de vizinhanças pode ser obtido de forma determinística, aleatória ou combi- nadas e produzem efeitos bem particulares em cada tipo de busca. Também vale ressaltar que ótimos locais fornecem informações relevantes para a progressão da VNS sobre o ótimo global. De acordo com condições específicas do problema, são altas as chances do ótimo global ser atingido por uma intensificação do algoritmo VNS em torno do ótimo local. Em contrapartida, se o ótimo global estiver em outra região, somente uma estratégia de diversificação pode fazer o algoritmo VNS reiniciar uma busca em outra região. O tempo e a velocidade de processamento podem ser otimizados quando vizinhanças de ótimos locais pouco promissoras deixarem de ser analisadas buscando atingir o ótimo global. Os passos principais da heurística da VNS são apresentados a seguir: 3.3 META-HEURÍSTICAS 53 a) identificar e extrair os dados relevantes do problema. Selecionar um conjunto de estru- turas de vizinhança numa determinada sequência que serão usadas na busca. Definir a forma de avaliação da qualidade da solução na função objetivo. Escolher um critério de parada; b) encontrar uma solução inicial para compor a solução corrente; c) gerar aleatoriamente uma solução na vizinhança da solução corrente levando em conside- ração a estrutura de vizinhança atual; d) aplicar uma heurística de busca local em torno da solução gerada no passo c e encontrar um ótimo local nesta vizinhança; e) se a solução ótima local encontrada no passo d nesta vizinhança apresentar qualidade melhor que a da solução corrente, tornar a solução vizinha em solução corrente, retomar a primeira estrutura de vizinhança e ir ao passo c. Caso contrário avançar para a próxima estrutura de vizinhança do conjunto e voltar ao passo c. Parar se a condição de parada for satisfeita. Muitas estratégias de busca utilizando um algoritmo VNS híbrido foram propostas nos úl- timos anos. 54 3 REVISÃO SOBRE AS META-HEURÍSTICAS 55 4 REVISÃO SOBRE A BUSCA DISPERSA 4.1 INTRODUÇÃO No presente capítulo é apresentada a metodologia de Busca Dispersa baseado em Laguna e Martí (2003). Não é intenção esgotar o assunto, mas sim oferecer as ferramentas necessárias para a compreensão desta metodologia para posterior aplicação no problema de planejamento de sistema de transmissão de energia elétrica. A Busca Dispersa (BD) é um método evolutivo em que seus conceitos e princípios foram propostos nos anos 70, baseados em formulações que antecedem os anos 60. Apóia-se em estratégias de busca que enfatizam diversificação e intensificação, operando sobre um conjunto de soluções de qualidade. Um resumo do método da BD pode ser encontrado em Martí, Laguna e Glover (2006) para quem deseja ter uma visão preliminar do tema e uma breve descrição da evolução histórica pode ser encontrada em Martí (2006). 4.2 TEORIA BÁSICA SOBRE A BUSCA DISPERSA A proposta básica da BD foi originalmente criada por Glover (1977) e destaca-se por ser a primeira publicação escrita desta metodologia. A BD nasceu num momento histórico em que a metodologia de resolução de problemas ocupava o centro das atenções, em pleno auge do desenvolvimento do Algoritmo Genético. Foi utilizada como uma extensão heurística na área de relaxação matemática em problemas de programação inteira. Ela contrapõe o efeito aleatório dos processos de otimização e propõe de maneira sofisticada e sistematizada a busca ordenada de soluções no espaço de busca. Na proposta original obtêm-se pontos ou soluções de maneira sistemática, evitando a alea- toriedade de forma a representar as características de várias partes do espaço de busca. A partir destes pontos criados por uma sucessão coordenada de busca seleciona-se um conjunto com aqueles pontos que contemplem prioritariamente qualidade ou diversidade, a que será tratado como Conjunto de Soluções de Qualidade (CSQ). O ponto central desta estratégia é a forma de combinação convexa, ou ponderações dos centros de gravidade realizada entre os pontos do CSQ. Estas combinações definirão novas subregiões do espaço de busca, que sistematicamente serão avaliadas. Considerando que um ponto pode ser, por exemplo, uma solução de um problema de otimização em que se procura minimizar uma função. Todos os pontos obtidos durante o processo são avaliados e depois 56 4 REVISÃO SOBRE A BUSCA DISPERSA melhorados por um algoritmo de melhoria pre-estabelecido para cada problema. O melhor dentre estes pontos será considerado a solução do problema. Na Figura 1 pode ser visualizada a proposta de combinação realizada na Busca Dispersa de 1977. Os pontos de 1 a 16 são os centróides representantes de uma subregião do espaço de busca. O ponto 8 é o centro da subregião determinada por uma combinação convexa dos pontos A, B e C do CSQ. Quaisquer desses pontos podem representar o novo CSQ, por exemplo, os pontos 6, 7 e 11 ou 4, 5 e 12, onde a escolha vai depender da distribuição dos pontos e da região, em geral factível. Existe a possibilidade de se obter um conjunto de pontos que sejam derivados de ponderações entre os centróides apresentados na Figura 1, para assumir o novo CSQ. São realizadas combinações entre estes pontos e o CSQ será atualizado com soluções melhoradas até que um valor desejável para a função objetivo seja atingido. Figura 1 -Ilustração da Busca Dispersa de 1977. b b b C A B b b b b b b b b b b b b b b b 16 5 4 12 3 7 b 6 10 8 13 15 1114 12 9 Fonte:Glover (1977) Na descrição de Glover (1977) é indicada que a própria evolução da busca oferece indi- cativos para influenciar o ajuste da estratégia de busca. Aborda uma combinação de mais de duas soluções para gerar centróides como parte central da busca e propõe a combinação de to- dos os pontos do CSQ. A combinação linear quando utilizada para gerar soluções sobre uma reta é considerada a forma mais simples do método. Buscas sistematizadas que evitam o fator aleatório no processo com ponderações apropriadas para encontrar centróides, podem oferecer melhores resultados. Indica que as combinações entre soluções sempre devem atender o critério de convexidade e insiste na importância da dispersão dos pontos. Comparada ao algoritmo genético que trabalha com um conjunto em torno de 100 elemen- 4.2 TEORIA BÁSICA SOBRE A BUSCA DISPERSA 57 tos, a BD opera sobre um CSQ de até 20 elementos. O volume de cálculos envolvidos é reduzido significativamente, o que será assunto de discussão adiante sobre a eficiência do método. Uma modificação da proposta original foi apresentada em Glover (1994) associando a dis- persão com oTabu Searchem que cria sistematicamente um conjunto de pontos de qualidade usando memória adaptativa e critérios de aspiração doTabu Search. Nesta versão, como exem- plo, a busca é realizada sobre retas que passam pelos centróides que são gerados pelas melhores soluções correntes obtidas durante o processo. Este método é descrito como um gerador siste- mático de soluções dispersas no espaço de busca das quais se escolhem as que irão compor o CSQ. Basicamente a modificação sugere que: a) o método inicie de um conjunto de pontos iniciais S gerados sistematicamente; b) no processo, o CSQ corrente seja definido pela união dos melhores elementos de S e das melhores soluções geradas ao longo da busca; c) uma interação consiste da primeira geração dos centros de gravidade de todos os sub- conjuntos gerados pelas melhores soluções de S. Estes pontos serão combinados com os pontos do CSQ para criar retas de busca para aumentar o número de soluções a serem avaliadas; d) a partir de combinações lineares de duas soluções do CSQ serão geradas novas propostas sobre a reta que passa por elas; e) quando a qualidade da proposta de solução obtida excede a qualidade média das soluções, a busca é intensificada em torno desta solução; f) a memória adaptativa é usada para controlar a admissão de novas soluções. Na sequência são apresentados alguns dos modelos de BD que foram sugeridos ao longo das últimas cinco décadas e que fizeram parte do cenário de muitas pesquisas em diversas áreas do conhecimento. 4.2.1 Modelo de Busca Dispersa de Glover (1998) O modelo apresentado por Laguna e Martí (2003) tem sido utilizado como referência para implementações do algoritmo de BD em vários problemas incorporando outras estratégias. Os procedimentos básicos deste modelo reformulado são esboçados a seguir: a) gera-se um conjunto inicial de soluções garantindo um nível crítico de diversidade e aplica-se uma heurística na tentativa de melhorar sua qualidade. São selecionadas para 58 4 REVISÃO SOBRE A BUSCA DISPERSA compor o CSQ as melhores soluções considerando não somente qualidade, mas também a diversidade; b) criam-se novas soluções a partir de combinações estruturadas das soluções incorporadas no CSQ; c) aplica-se novamente a heurística de melhoramento utilizada no passo a nas soluções ob- tidas no passo b, melhorando-as e retirando possíveis infactibilidades; d) extrair as melhores soluções do passo c e acrescentá-las ao CSQ se estas soluções tiverem melhor qualidade na função objetivo; e) repetir os passos b, c e d até que o CSQ não sofra mais alterações ou parar quando atingir um limite especificado de iterações. O fator preponderante deste modelo é o fato de que, através de combinações convexas e não-convexas no processo de busca, é possível provocar um deslocamento destas soluções para regiões do espaço ainda não exploradas. Desta forma, a exploração não fica restrita ao espaço compreendido entre duas soluções no processo. A estratégia para escolher e para combinar duas ou mais soluções do CSQ são fundamentais no processo, principalmente para permitir que novas soluções sejam produzidas e assim compor a atualização do CSQ. O método deve estar preparado para que o mecanismo de melhoria consiga operar sobre re- giões infactíveis, ou seja, que seja capaz de remover a infactibilidade das soluções, melhorá-las a fim de que sejam candidatas a compor o CSQ. Assume-se que o CSQ contém informações e características úteis das soluções ótimas para orientar o processo de busca. É importante for- necer mecanismos capazes de construir combinações das soluções que extrapolem as regiões abrangidas pelas soluções consideradas. Pode ser importante realizar um mapeamento das so- luções combinadas durante a busca. O modelo geral para implementação da BD é caracterizado por 5 Métodos: a) Método de Geração de Soluções com Diversidade: com uma estratégia apropriada para o problema é gerada uma coleção de soluções distintas e que representem o espaço de busca da forma abrangente; b) Método de Melhoramento de Soluções: é aplicado toda vez que existirem soluções infac- tíveis ou que possam ser melhoradas, aplicando-se alguma heurística de busca local; c) Método de Atualização do CSQ: é o método que incorpora no CSQ as melhores soluções encontradas durante o processo. Como o conjunto não comporta mais que 20 soluções, elas serão substituídas de acordo com a qualidade ou diversidade; 4.2 TEORIA BÁSICA SOBRE A BUSCA DISPERSA 59 d) Método de Geração de Subconjuntos de Soluções: de acordo com cada problema a gera- ção de subconjuntos especifica que cada subconjunto conterá duas ou mais soluções do CSQ e que posteriormente são submetidas ao Método de Combinação de Soluções; e) Método de Combinação das Soluções: neste método são geradas uma ou mais soluções a partir da estratégia de combinação das soluções de cada subconjunto de soluções gerado pelo Método de Geração de Subconjuntos. Das cinco etapas apresentadas somente quatro são consideradas fundamentais, pois o mé- todo de melhoramento é indicado quando são desejadas soluções de alta qualidade. Da mesma forma que em outras meta-heurísticas a BD básica pode ser progressivamente implementada. O modelo inicia com o método de Geração de Soluções com Diversidade para construir um conjunto de soluções diversas e distintas. Esta geração é particular e adaptada para cada tipo de problema e mesmo sendo evitada a geração aleatória de soluções é em geral o único momento de toda a meta-heurística da BD do modelo básico em que é aceito o uso do recurso aleatório. Cada solução obtida pelo Método da Geração de Soluções é submetida ao Método de Me- lhoramento de Soluções. O melhoramento consiste na exploração da vizinhança desta solução por uma busca local sistematizada na tentativa de encontrar uma solução vizinha que tenha me- lhor qualidade (melhor valor na função objetivo) que ela. Para o caso em que a solução for infactível, este processo submete a mesma heurística de melhoramento escolhida na tentativa de torná-la factível e posteriormente tentar melhorar sua qualidade. Depois que a primeira solução gerada e melhorada for incluída no conjunto aqui denomi- nado de conjuntoP, as demais que forem sendo geradas somente serão incluídas no conjunto se não existirem soluções com a mesma configuração das que já foram escolhidas, independen- temente do seu valor avaliado na função objetivo. Caso já exista solução idêntica simplesmente esta solução será descartada, e então será repetido o procedimento de geração até completar o número de soluções especificado para o conjuntoP, que tem em geral 100 soluções. O conjunto deve ser ordenado por qualidade, ou seja, da solução de menor valor na função objetivo para o de maior valor. De posse do conjunto de soluções diversas e melhoradas, inicia-se a seleção das soluções deste conjunto para compor um conjunto reduzido aqui identificado como Conjunto de Solu- ções de Qualidade (CSQ) pelo Método de Atualização do CSQ. O CSQ deve ser composto por soluções de qualidade, em geral 10. Entende-se por qualidade as soluções com melhor valor na função objetivo e as que possuem a maior dispersão no espaço de busca, independente do valor funcional. São selecionadas respectivamente para compor o CSQ soluções de qualidade e soluções dispersas. 60 4 REVISÃO SOBRE A BUSCA DISPERSA Depois desta seleção e com uma métrica pre-estabelecida é calculada a distância entre todas as soluções incorporadas no CSQ com todas as que ainda restaram no conjuntoP. A distância entre uma solução do conjuntoP e o CSQ será definida como a menor das distâncias entre esta solução deP e todas as soluções do CSQ. Na sequência as soluções do conjuntoP serão ordenadas pelos valores das menores distâncias. A solução que detiver a maior distância é excluída deP e incluída no CSQ. A próxima solução será obtida tomando-se as distâncias entre todas as soluções de|P|-1 com as do CSQ atualizado, e o processo se repete até completar as soluções com diversidade do CSQ. As soluções presentes no CSQ são finalmente ordenadas pelo valor que assume na função objetivo. As soluções contidas no CSQ serão submetidas ao Método de Geração de Subconjuntos de Soluções e as formas de agrupamento podem ser das mais variadas possíveis. A estratégia utili- zada neste passo também é determinante para a eficiência do método. Em geral são produzidos subconjuntos de duas soluções distintas retiradas do CSQ. Em um CSQ comn soluções podem ser confeccionados até n(n−1) 2 subconjuntos de duas soluções distintas. Estes subconjuntos evidenciam a preocupação em realizar buscas de soluções melhores através da análise das infor- mações que pode oferecer a combinação entre soluções "boas", entre soluções dispersas, entre soluções “boas” e dispersas concomitantemente e consequentemente direcionar a busca. No Método de Combinação das Soluções, todas as soluções, contidas nos subconjuntos gerados no método anterior contendo duas ou mais soluções são combinadas. A estratégia utili- zada para este método de combinação das soluções é fundamental para se encontrar soluções de boa qualidade e evitar que o método pare em ótimos locais, realizando combinações convexas e não convexas. Novas soluções serão geradas pelo Método de Combinação das Soluções, que poderão ser de baixa qualidade e até infactíveis, portanto, estas novas soluções passarão pela mesma heurística de melhoramento que já foi utilizada. Quando todas as soluções do Método de Combinação das Soluções tiverem sido combi- nadas, as novas soluções obtidas devem passar pelo crivo do Método de Atualização do CSQ. Elas poderão atualizar o CSQ se tiverem melhor valor na função objetivo que qualquer uma das soluções ali existentes. Quando uma solução é aceita no CSQ, a solução de pior qualidade será excluída, e o CSQ é reordenado. Quando todas as soluções combinadas passaram pela atua- lização do CSQ o processo é repetido iniciando uma nova rotina de geração de subconjuntos mantendo a mesma sequência, conforme apresentado no fluxograma da Figura 2. O algoritmo de BD é executado até que nenhuma solução seja aceita pelo método de atua- lização do CSQ, ou seja, as soluções do CSQ sejam soluções de elite. Considera-se como solução final do problema a primeira solução presente no CSQ que se mantém ordenado pelo valor obtido na função objetivo. 4.2 TEORIA BÁSICA SOBRE A BUSCA DISPERSA 61 Figura 2 -Fluxograma do algoritmo de busca dispersa P atingiu o tamanho desejado? Método de Geração de Soluções Método de Melhoramento pertence ao ConjuntoP? SIM NÃO SIM Método de atualização do conjunto de soluções de qualidade O conjunto Método de Geração de Método de combinação de soluções Método de Melhoramento de Soluções novas soluções? SIM FIM NÃO de soluções de qualidade aceita com Diversidade das Soluções A solução gerada e melhorada Armazenar a solução gerada no conjuntoP Subconjuntos de Soluções NÃO Fonte: Elaboração do próprio autor Observando os passos apresentados no fluxograma da Figura 2 é possível oferecer uma descrição mais detalhada do modelo básico da meta-heurística de Busca Dispersa. 4.2.2 Busca Dispersa Aplicada Os problemas de Otimização Não Linear Irrestrita, o Problema de Ordenamento Linear e o Problema da Mochila aparecem descritos no livro de Laguna e Martí (2003) para exemplificar a aplicação da BD com algumas implementações. A estrutura da meta-heurística BD implemen- tada depende das características do problema e do tipo de codificação proposta. Nesta seção são apresentados o mecanismo da meta-heurística de BD nos problemas de Otimização Não Linear Irrestrita e o Problema da Mochila que podem contribuir para um entendimento inicial sobre sua aplicação. 62 4 REVISÃO SOBRE A BUSCA DISPERSA 4.2.2.1 Problema de Otimização Não Linear Irrestrito No livro de Laguna e Martí (2003), para resolver um dado problema deUnconstrained Nonlinear Optimizationsão apresentadas implementações do algoritmo da BD que merecem destaque, considerando que as variáveis são reais. No método de diversificação é empregado um controle aleatório conjugado a uma memória baseada na frequência (a mesma utilizada no Tabu Search). O intervalo compreendido entre os limites de uma restrição real é dividido em 4 subintervalos de mesma magnitude. Uma solução é construída em duas etapas: na primeira um dos subintervalos é escolhido aleatoriamente, em que a probabilidade da escolha de um subintervalo é inversamente propor- cional à frequência com que for escolhido e, no segundo passo, um valor é escolhido aleato- riamente para ser atribuído à variável dentro do intervalo selecionado. Estes dois passos são executados até que todos os elementos de um vetor solução sejam gerados. O número de ve- zes que um subintervalo é escolhido para gerar uma solução é armazenado em uma matriz de frequência. Desta maneira, o Método de Geração de Soluções com Diversidade é tipicamente aplicado até atingir o número máximo de 100 soluções distintas no conjuntoP ou equivalente a cinco vezes o número de soluções do C