Universidade Estadual Paulista "Júlio de Mesquita Filho" Faculdade de Engenharia de Bauru Programa de Pós-Graduação em Engenharia Elétrica Algoritmo Genético Direcionado e sua Análise Estocástica para Resolução do Problema de Despacho Econômico Lívia Teresa Minami Borges Bauru 2024 Lívia Teresa Minami Borges Algoritmo Genético Direcionado e sua Análise Estocástica para Resolução do Problema de Despacho Econômico Defesa de doutorado apresentada ao Programa de Pós-Graduação em Engenharia Elétrica da Universidade Estadual Paulista "Júlio De Mesquita Filho", UNESP, Campus de Bauru, como requisito para obtenção do título de Doutor em Engenharia Elétrica. Orientadora: Profa. Dra. Edilaine Martins So- ler. Coorientador: Prof. Dr. Leonardo Nepomu- ceno Bauru 2024 B732a Borges, Lívia Teresa Minami Algoritmo Genético Direcionado e sua Análise Estocástica para Resolução do Problema de Despacho Econômico / Lívia Teresa Minami Borges. -- Bauru, 2024 154 p. Tese (doutorado) - Universidade Estadual Paulista (UNESP), Faculdade de Engenharia, Bauru Orientadora: Edilaine Martins Soler Coorientador: Leonardo Nepomuceno 1. otimização. 2. meta-heurística. 3. convergência. 4. taxa de convergência. 5. fluxo de carga linearizado. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Dados fornecidos pelo autor(a). iv IMPACTO POTENCIAL DA PESQUISA O desenvolvimento do Algoritmo Genético Direcionado (AGD) e do Algoritmo Evo- lutivo Adaptativo (AEA) para resolver o Problema de Despacho Econômico considerando os efeitos de pontos de carregamento de válvula e zonas de operação proibida (PDEPVZ) e também a transmissão (PDEPVZ-RR) possui um impacto signi�cativo em diversas áreas, tanto do ponto de vista econômico quanto social. Do ponto de vista econômico, a aplicação dos algoritmos propostos permite uma uti- lização mais e�ciente dos recursos energéticos, resultando em uma operação mais econô- mica das usinas e, consequentemente, na redução dos custos de produção de energia elétrica. Além disso, a resolução e�caz do PDEPVZ e do PDEPVZ-RR com os novos algoritmos pode minimizar os custos associados à operação fora das zonas proibidas e aos impactos dos pontos de carregamento de válvula, otimizando a alocação de geração de energia. Concessionárias de energia que implementam essas metodologias podem se tornar mais competitivas no mercado, oferecendo tarifas mais atrativas e melhorando seus índices de e�ciência. Do ponto de vista social, a capacidade de planejar e operar de maneira otimizada re- duz a probabilidade de falhas no sistema elétrico, garantindo um fornecimento de energia mais estável e con�ável para a sociedade. A melhoria na operação dos sistemas de geração de energia pode evitar paradas repentinas, que causam prejuízos a diversos setores, in- cluindo a produção de bens e serviços essenciais. Além disso, uma operação mais e�ciente e econômica pode levar à redução dos custos de produção e, consequentemente, ao alívio das tarifas pagas pelos consumidores, contribuindo para a acessibilidade e sustentabilidade �nanceira do fornecimento de energia. v POTENTIAL IMPACT OF THE RESEARCH The development of the Directed Genetic Algorithm (DGA) and the Adaptive Evo- lutionary Algorithm (AEA) to solve the Economic Dispatch Problem considering Valve- Point Loading E�ects and Prohibited Operating Zones (EDPVPZ), as well as the trans- mission constraints (NC-EDPVPZ), has a signi�cant impact on various areas, both from an economic and a social perspective. From an economic standpoint, the application of the proposed algorithms allows for a more e�cient use of energy resources, resulting in a more economical operation of power plants and, consequently, reducing the costs of electricity production. Additionally, the e�ective resolution of the EDPVPZ and NC-EDPVPZ with the new algorithms can minimize costs associated with operating outside prohibited zones and the impacts of valve-point loading e�ects, optimizing the allocation of power generation. Energy utilities that implement these methodologies may become more competitive in the market by o�ering more attractive tari�s and improving their e�ciency indices. From a social perspective, the ability to plan and operate in an optimized manner reduces the likelihood of failures in the power system, ensuring a more stable and reliable energy supply for society. Improvements in the operation of energy generation systems can prevent sudden outages, which cause losses across various sectors, including the production of essential goods and services. Moreover, a more e�cient and economical operation can lead to lower production costs and, consequently, alleviate the tari�s paid by consumers, contributing to the accessibility and �nancial sustainability of energy supply. UNIVERSIDADE ESTADUAL PAULISTA Câmpus de Bauru ATA DA DEFESA PÚBLICA DA TESE DE DOUTORADO DE LÍVIA TERESA MINAMI BORGES, DISCENTE DO PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA, DA FACULDADE DE ENGENHARIA - CÂMPUS DE BAURU. Aos 14 dias do mês de outubro do ano de 2024, às 08:30 horas, por meio de Videoconferência, realizou-se a defesa de TESE DE DOUTORADO de LÍVIA TERESA MINAMI BORGES, intitulada Algoritmo Genético Direcionado e sua Análise Estocástica para Resolução do Problema de Despacho Econômico. A Comissão Examinadora foi constituida pelos seguintes membros: Profa. Dra. EDILAINE MARTINS SOLER (Orientador(a) - Participação Virtual) do(a) Departamento de Matemática / Faculdade de Ciências de Bauru UNESP, Prof. Dr. ANDRE CHRISTOVAO PIO MARTINS (Participação Virtual) do(a) Departamento de Engenharia Elétrica / Universidade Estadual Paulista (UNESP) - Faculdade de Ciências, Câmpus de Bauru , Prof. Dr. ANTONIO ROBERTO BALBO (Participação Virtual) do(a) Departamento de Matemática / Universidade Estadual Paulista (UNESP) - Faculdade de Ciências, Câmpus de Bauru, Prof. Dr. DIEGO NUNES DA SILVA (Participação Virtual) do(a) Departamento de Matemática / Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP, Prof. Dr. LEANDRO BATISTA MORGADO (Participação Virtual) do(a) Departamento de Matemática / Universidade Federal de Santa Catarina. Após a exposição pela doutoranda e arguição pelos membros da Comissão Examinadora que participaram do ato, de forma presencial e/ou virtual, a discente recebeu o conceito final:_ _ _ _ _ _ _ _ _ _ _ _ _ . Nada mais havendo, foi lavrada a presente ata, que após lida e aprovada, foi assinada pelo(a) Presidente(a) da Comissão Examinadora. Profa. Dra. EDILAINE MARTINS SOLER Faculdade de Engenharia - Câmpus de Bauru - Av. Engenheiro Luiz Edmundo Carrijo Coube, , 14-01, 17033360 https://www.feb.unesp.br/#!/pos-graduacao/ppgeeCNPJ: 48.031.918/0030-69. APROVADA Dedico este trabalho ao meu papito Celso (in memoriam) que tinha um coração maior que ele, à minha mãe Tereza que me deu suporte físico e emocional para enfrentar os desa�os, às minhas amadas �lhas Larisse e Milene por serem minha fonte de energia e amor, ao meu marido Fabiano por estar sempre ao meu lado e por me fazer sorrir mesmo nos momentos mais difíceis e por �m à minha família e amigos, pois cada um do seu jeitinho contribuiu para que este sonho de voltar a estudar se tornasse realidade. viii Agradecimento Agradeço primeiramente a Deus, que me orienta e me dá forças para seguir. Ao meu marido, companheiro e melhor amigo Fabiano pelo apoio, pelas conver- sas durante as caminhadas no �m de tarde, pelas palavras de encorajamento enquanto tomávamos milhares de garrafas de café e por estar sempre ao meu lado. Às minhas meninas Larisse e Milene, por tornarem os dias de estudo mais leves e por sempre me darem muitos beijinhos quando as coisas não saíam como o esperado. À minha cunhada Fernanda pelas risadas, pelas conversas, por me mostrar que o Python não morde e por estar sempre pronta para esclarecer minhas dúvidas de iniciante. À minha família pelo carinho e pela torcida. Obrigada mãe pelo suporte e por me socorrer sempre que eu gritava. À Profa. Dra. Edilaine Martins Soler, pela paciência, dedicação, parceria e por sempre estar sorrindo, isso torna o caminho mais suave e realmente faz toda diferença. Ao Prof. Dr. Leonardo Nepomuceno, pela competência, entusiasmo e por fazer dessa etapa uma experiência de extremo conhecimento pra mim, não só como estudante, mas como pessoa. Aos membros da banca, minha mais profunda gratidão pela atenção dedicada e pelos valiosos insights fornecidos. Com certeza suas contribuições e questionamentos enriquecerão imensamente minha pesquisa e me ajudarão a aprimorar meu trabalho. Aos colegas que, mesmo não nos conhecendo pessoalmente, tornaram o ensino re- moto mais leve, engraçado e produtivo. Aos professores e funcionários do programa de pós-graduação em engenharia elétrica da UNESP Bauru e do Departamento de Matemática. Ao programa de pós-graduação da FEB em Engenharia Elétrica e a UNESP pela oportunidade de realização do curso de doutorado. Ao IFSP pelo incentivo e aos professores da Matemática do Campus Birigui, pelo suporte e palavras de apoio. �A tarefa não é tanto ver aquilo que ninguém viu, mas pensar o que ninguém ainda pensou sobre aquilo que todo mundo vê.� (Arthur Schopenhauer) Resumo Neste trabalho, visando resolver o Problema de Despacho Econômico considerando os efeitos de pontos de carregamento de válvula e zonas de operação proibida (PDEPVZ), vamos propor o Algoritmo Genético Direcionado (AGD), um método baseado no Algo- ritmo Genético (AG) que, utilizando as singularidades da função objetivo e sem perder a capacidade de exploração do AG, realiza uma busca inteligente focada principalmente nessas singularidades do problema. Além disso, através de resultados da Teoria de Pro- babilidade e processos estocásticos provamos que o AGD converge. Para que pudéssemos validar o AGD, o algoritmo foi implementado no Python e testes foram realizados para resolver o PDEPV e o PDEPVZ para sistemas com 3, 5, 6 e 40 geradores. Propomos ainda o Algoritmo Evolutivo Adaptativo (AEA), que incorpora uma mutação adaptativa ao Algoritmo Evolutivo convencional com elitismo, e provamos que o AEA apresenta uma Taxa Média de Convergência (TMC) linear, quando aplicado à funções que são Lipschitz contínuas e que satisfazem determinadas hipóteses ((A1) ou (A2)). Adaptações foram feitas aos teoremas relacionados à TMC, para que toda a teoria pudesse ser aplicada ao PDEPV. Além disso, para tornar o PDEPVZ ainda mais representativo, propõe-se um modelo linear para a rede de transmissão (PDEPVZ-RR), onde tanto as perdas quanto os limites de �uxo de potência são aplicados a todos os indivíduos da população. Este modelo foi incorporado ao AGD através da criação de um operador que calcula as perdas e faz o balanço de potência. Testes foram realizados para os sistemas IEEE-118 barras e IEEE-300 barras. Palavras-chave: otimização; meta-heurística; singularidades; convergência; processos estocástico; mutação positiva-adaptativa; função Lipschitz contínua; �uxo de carga line- arizado. Abstract In this work, aiming to solve the Economic Dispatch Problem considering the e�ects of valve-point loading and prohibited operating zones (EDPVPZ), we propose the Directed Genetic Algorithm (DGA), a method based on the Genetic Algorithm (GA) that, by utilizing the singularities of the objective function without losing the GA's exploratory capability, performs an intelligent search primarily focused on these problem singularities. Additionally, through results from Probability Theory and stochastic processes, we prove that the DGA converges. To validate the DGA, the algorithm was implemented in Python, and tests were conducted to solve the EDPVP and EDPVPZ for systems with 3, 5, 6, and 40 generators. We also propose the Adaptive Evolutionary Algorithm (AEA), which incorporates an adaptive mutation into the conventional Evolutionary Algorithm with elitism. We prove that the AEA exhibits a linear Average Convergence Rate (ACR) when applied to functions that are Lipschitz continuous and satisfy certain hypotheses ((A1) or (A2)). Adaptations were made to the theorems related to ACR to apply the entire theory to the EDPVP. Additionally, to make the EDPVPZ even more representative, a linear model for the transmission network (TR-EDPVPZ) is proposed, where both losses and power �ow limits are applied to all individuals in the population. This model was incorporated into the DGA through the creation of an operator that calculates losses and performs the power balance. Tests were conducted for the IEEE-118 bus and IEEE-300 bus systems. Keywords: optimization; meta-heuristic; singularities; convergence; stochastic processes; positive-adaptive mutation; Lipschitz continuous function; linearized power �ow. Sumário 1 Introdução 24 2 Modelos Matemáticos para o Problema de Despacho Econômico 33 2.1 Formulação Clássica do PDE . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Formulação do PDEPV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3 Formulação do PDEPVZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Algoritmo Genético Direcionado - AGD 39 3.1 Descrição do método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.1 Algoritmo Genético - AG . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.2 Singularidades associadas ao problema . . . . . . . . . . . . . . . . 42 3.1.3 Pseudocódigo e Operadores . . . . . . . . . . . . . . . . . . . . . . 46 3.1.3.1 Pseudocódigo do AGD . . . . . . . . . . . . . . . . . . . . 46 3.1.3.2 População Inicial . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.3.3 Indivíduo pivô . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.3.4 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1.3.5 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1.3.6 Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1.3.7 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1.3.8 Critério de parada . . . . . . . . . . . . . . . . . . . . . . 50 4 Convergência 51 4.0.1 Noções preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.0.1.1 Funções contínuas em compactos . . . . . . . . . . . . . . 52 4.0.1.2 Teoria de Probabilidade: alguns conceitos e propriedades . 52 4.0.1.3 Variáveis Aleatórias . . . . . . . . . . . . . . . . . . . . . 55 4.0.1.4 Cadeia de Markov . . . . . . . . . . . . . . . . . . . . . . 57 4.0.2 Prova da convergência . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.1 Testes numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.1.1 AGD na resolução do PDEPV . . . . . . . . . . . . . . . . . . . . . 66 4.1.1.1 Sistema com 3 geradores . . . . . . . . . . . . . . . . . . . 66 4.1.1.2 Sistema com 5 geradores . . . . . . . . . . . . . . . . . . . 68 4.1.1.3 Sistema com 6 geradores . . . . . . . . . . . . . . . . . . . 69 4.1.1.4 Sistema com 40 geradores . . . . . . . . . . . . . . . . . . 70 4.1.2 AGD na resolução do PDEPVZ . . . . . . . . . . . . . . . . . . . . 72 4.1.2.1 Sistema com 3 geradores . . . . . . . . . . . . . . . . . . . 73 4.1.2.2 Sistema com 6 geradores . . . . . . . . . . . . . . . . . . . 74 4.1.2.3 Sistema com 40 geradores . . . . . . . . . . . . . . . . . . 77 4.1.3 In�uência do indivíduo pivô . . . . . . . . . . . . . . . . . . . . . . 79 5 Taxa Média de Convergência - TMC 81 5.1 Algoritmo Evolutivo Adaptativo - AEA . . . . . . . . . . . . . . . . . . . . 81 5.1.1 População Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.1.2 Função avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.1.3 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.1.4 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.1.5 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.1.6 Critério de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.2 Noções preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3 TMC linear para otimização de problemas com funções Lipschitz contínuas 89 5.4 Aplicações do AEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.4.1 Algoritmos Implementados . . . . . . . . . . . . . . . . . . . . . . . 96 5.4.2 Função Ackley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.4.3 Função Alpine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4.4 Função f(x, y) = x4 + y4 . . . . . . . . . . . . . . . . . . . . . . . . 104 5.4.5 Discussão: x∗ desconhecido . . . . . . . . . . . . . . . . . . . . . . 105 5.4.6 PDEPV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.4.6.1 Sistema com 3 geradores . . . . . . . . . . . . . . . . . . . 111 5.4.6.2 Sistema com 5 geradores . . . . . . . . . . . . . . . . . . . 113 5.4.6.3 Sistema com 40 geradores . . . . . . . . . . . . . . . . . . 115 6 Algoritmo Genético Direcionado Adaptativo - AGDA 119 6.1 Testes numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.1.1 Sistema com 3 geradores . . . . . . . . . . . . . . . . . . . . . . . . 119 6.1.2 Sistema com 5 geradores . . . . . . . . . . . . . . . . . . . . . . . . 120 6.1.3 Sistema com 40 geradores . . . . . . . . . . . . . . . . . . . . . . . 121 7 PDEPVZ com restrições de rede (PDEPVZ-RR) 124 7.1 Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 7.2 Adaptações ao AGD para resolução do PDEPVZ-RR . . . . . . . . . . . . 130 7.2.1 Pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7.2.2 Operador de Balanço de Potência . . . . . . . . . . . . . . . . . . . 130 7.2.3 Função de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.3 Testes numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.3.1 Sistema IEEE-118 barras . . . . . . . . . . . . . . . . . . . . . . . . 134 7.3.2 Sistema IEEE-300 barras . . . . . . . . . . . . . . . . . . . . . . . . 136 8 Considerações �nais e perspectivas futuras 140 Trabalhos publicados 142 Trabalhos submetidos 143 Referências Bibliográ�cas 143 A Apêndice 153 Lista de Figuras 2.1 Curva de custo de um gerador sem considerar efeitos de ponto de válvula (linha trace- jada) e com efeitos de ponto de válvula (linha contínua). . . . . . . . . . . . . . . . 35 2.2 Superfície de custo de um sistema de dois geradores considerando efeitos de ponto de carregamento de válvula. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3 Curva de custo de um gerador i considerando efeitos de ponto de carregamento de válvula e com zonas de operação proibida (área hachurada). . . . . . . . . . . . . . 38 4.1 Cadeia de Markov obtida para a população POPk. . . . . . . . . . . . . . . . . . . 60 4.2 Convergência do método AGD no Problema de Despacho Econômico considerando os efeitos de pontos de carregamento de válvula e zonas proibidas (PDEPVZ) com 6 geradores. 76 4.3 Média e desvio padrão das curvas de convergência para o AGD no PDEPVZ com 6 geradores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.4 Comparação do �tness médio do AGD e de todos os métodos usados nas comparações. . 79 5.1 Taxa Média de Convergência do AGA (Teorema 5.3 e Corolário 5.4) e do AG em 2000 gerações, na resolução do Problema 5.4.1. . . . . . . . . . . . . . . . . . . . . . . 101 5.2 Taxa Média de Convergência do EEA (Teorema 5.3 e Corolário 5.4) e do EE em 2000 gerações, na resolução do Problema 5.4.1. . . . . . . . . . . . . . . . . . . . . . . 102 5.3 Uma comparação entre a TMC do AGA (Teorema 5.3), EEA (Teorema 5.3), AG e EE em 2000 gerações na resolução do Problema (5.4.3) com n = 10. . . . . . . . . . . . 104 5.4 Comparação entre a TMC do AGA (Teorema 5.5), EEA (Teorema 5.5), AG and EE em 500 gerações na minimização de f(x, y) = x4 + y4. . . . . . . . . . . . . . . . . . . 105 5.5 Comparação entre a TMC de diferentes mutações (Teorema 5.3, σ e σ̂) aplicadas ao EEA e EE na resolução do Problema 5.4.1. . . . . . . . . . . . . . . . . . . . . . 107 5.6 Comparação entre a TMC de diferentes mutações (Teorema 5.3, σ e σ̂) aplicadas ao EEA e EE na resolução do Problema (5.4.3). . . . . . . . . . . . . . . . . . . . . 107 5.7 Comparação entre a TMC de diferentes mutações (Teorema 5.3, σ e σ̂) aplicadas ao EEA e EE na minimização de f(x, y) = x4 + y4. . . . . . . . . . . . . . . . . . . . 108 5.8 Comparação entre a TMC do AGA (Corolários 5.6 e 5.7) e AG em 100 gerações na resolução do Problema de Despacho Econômico considerando os efeitos de pontos de carregamento de válvula (PDEPV) com 3 unidades geradoras. . . . . . . . . . . . . 112 5.9 Comparação entre a TMC do EEA (Corolários 5.6 e 5.7) e EE em 100 gerações na resolução do PDEPV com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . 113 5.10 Comparação entre a TMC do EEA (Corolários 5.6 e 5.7) e EE em 100 gerações na resolução do PDEPV com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . 114 5.11 Comparação entre a TMC do EEA (Corolários 5.6 e 5.7) e EE em 100 gerações na resolução do PDEPV com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . 115 5.12 Comparação entre a TMC do Estratégia Evolutiva Adaptativa (EEA) (Corolários 5.6 e 5.7) e Estratégia Evolutiva (EE) em 200 gerações na resolução do PDEPV com 40 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Lista de Tabelas 3.1 Incidência de soluções nas singularidades do PDEPV segundo Secui (2015) para siste- mas de 10 e 13 geradores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.1 Dados da curva de custo para o PDEPV com 3 geradores. . . . . . . . . . . . . . . 67 4.2 Singularidades de cada um dos geradores para o PDEPV com 3 geradores. . . . . . . 67 4.3 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4 Dados da curva de custo para o PDEPV com 5 geradores. . . . . . . . . . . . . . . 68 4.5 Singularidades de cada um dos geradores para o PDEPV com 5 geradores. . . . . . . 68 4.6 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 5 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.7 Dados da curva de custo para o PDEPV com 6 geradores. . . . . . . . . . . . . . . 69 4.8 Singularidades associadas a cada um dos geradores para o PDEPV com 6 geradores. . . 70 4.9 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 6 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.10 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 40 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.11 Zonas de operação proibida para o PDEPVZ com 3 geradores. . . . . . . . . . . . . 73 4.12 Singularidades de cada um dos geradores para o PDEPVZ com 3 geradores. . . . . . . 73 4.13 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.14 Zonas de operação proibida para o PDEPVZ com 6 geradores. . . . . . . . . . . . . 75 4.15 Singularidades de cada um dos geradores para o PDEPVZ com 6 geradores. . . . . . . 75 4.16 Comparação entre custo mínimo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 6 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.17 Comparação entre custo mínimo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 40 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.18 Comparação de custos entre AG, AGDsp e AGD. . . . . . . . . . . . . . . . . . . 79 5.1 Constantes para o PDEPV com 3 geradores. . . . . . . . . . . . . . . . . . . . . . 111 5.2 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.3 Constantes para o PDEPV com 5 geradores. . . . . . . . . . . . . . . . . . . . . . 113 5.4 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 5 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.5 Comparação entre custo mínimo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 40 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . 116 6.1 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 3 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.2 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 5 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.3 Comparação de custo, custo médio, desvio padrão (DP) e tempo de execução: sistema com 40 unidades geradoras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.1 Comparação de custo mínimo, custo médio, desvio padrão (DP) e tempo de execução: sistema IEEE 118 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 7.2 Comparação de custo mínimo, custo médio, desvio padrão (DP) e tempo de execução: sistema IEEE 300 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.3 Resultados do teste de Wilcoxon comparando o AGD com outros algoritmos em diferentes instâncias, com base no custo mínimo, custo médio e tempo computacional. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.4 Resultados do Teste de Nemenyi para todas as comparações de métodos. . 139 Lista de Siglas PO Pesquisa Operacional PDE Problema de Despacho Econômico PDEPV Problema de Despacho Econômico considerando os efeitos de pontos de carre- gamento de válvula PDEPVZ Problema de Despacho Econômico considerando os efeitos de pontos de car- regamento de válvula e zonas proibidas PDEPVZ-RR Problema de Despacho Econômico considerando os efeitos de pontos de carregamento de válvula, zonas proibidas e restrições de rede MA-PDEPVZ Problema de Despacho Econômico múltiplas áreas considerando os efei- tos de pontos de carregamento de válvula, zonas proibidas MO-PDEPVZ Problema de Despacho Econômico multi-objetivo considerando os efeitos de pontos de carregamento de válvula, zonas proibidas SEP Sistema Elétrico de Potência ZOP Zonas de Operação Proibida AG Algoritmo Genético AGD Algoritmo Genético Direcionado AGA Algoritmo Genético Adaptativo AGDsp Algoritmo Genético Direcionado sem pivô AGDA Algoritmo Genético Direcionado Adaptativo AE Algoritmo Evolutivo AEA Algoritmo Evolutivo Adaptativo EE Estratégia Evolutiva EEA Estratégia Evolutiva Adaptativa ACO Ant Colony Optimization ED Evolução Diferencial EDOC Evolução Diferencial Otimizada Colaborativa PSO Particle Swarm Optimization EEAMC Estratégia Evolutiva de Adaptação de Matriz de Covariância CJADE Evolução Diferencial Adaptativa Caótica com Arquivo Externo Opcional HSES Estratégia Evolutiva de Amostragem Híbrida TMC Taxa Média de Convergência TMCA Taxa Média de Convergência Alternativa 24 Capítulo 1 Introdução A Pesquisa Operacional (PO) é uma área da matemática aplicada que tem como �nalidade desenvolver modelos matemáticos e algoritmos de solução que auxiliem na to- mada de decisão. Ela surgiu na Segunda Guerra Mundial, com a necessidade de se fazer um melhor gerenciamento de tarefas e recursos. Com o �m da guerra, a indústria se interessou pelas técnicas desenvolvidas, visando utilizá-las no planejamento e controle da produção, tendo chegado ao Brasil na década de 1960 (Arenales et al., 2006). Quando um problema de PO consiste em minimizar ou maximizar uma função, chamada de fun- ção objetivo, satisfazendo determinadas restrições, estamos diante de um problema de otimização. Dependendo das características das funções envolvidas, o problema pode ser classi�cado como problema de programação linear ou não-linear. Pode-se ainda classi�car um problema de otimização de acordo com a natureza de suas variáveis: se elas forem discretas, tem-se um problema combinatório, se forem contínuas, tem-se um problema contínuo e se houver ambos os tipos de variáveis, tem-se um problema inteiro misto. Diversos métodos determinísticos têm sido propostos na literatura para resolver os problemas de otimização, tais como Método Gradiente (Nesterov, 2015), Métodos de Ponto Interior (Bertsekas, 1997), Método de Newton (Wood et al., 2013) e Algo- ritmo de Programação Quadrática (Exler & Schittkowski, 2007), entre outros. Uma das principais di�culdades ocorre para problemas mais complexos com função objetivo multimodal. Nesses casos, os métodos determinísticos podem �car presos em mínimos locais. Isso ocorre pois a maioria dos métodos determinísticos usa a derivada para de- terminar a direção de busca e, como se sabe a partir do Cálculo Diferencial, a derivada 25 é um conceito usado para analisar o comportamento da função localmente, fazendo com que o método não tenha uma visão de todo o espaço de busca e acabe executando uma trajetória em direção ao mínimo local mais próximo. Um importante problema de otimização envolvendo os sistemas elétricos de potên- cia é o Problema de Despacho Econômico (PDE) que, segundo Happ (1977), surgiu por volta de 1920, e visa determinar a combinação ótima de saídas de potência ativa para um conjunto de geradores do Sistema Elétrico de Potência (SEP), buscando minimizar seus custos de produção de energia, e satisfazendo determinadas restrições, tais como o atendimento de demanda e limites da capacidade de geração de cada gerador. Na formu- lação matemática de um PDE, pode-se considerar vários aspectos de modelagem de modo a tornar o problema mais representativo da operação e/ou planejamento real. Porém, à medida que mais aspectos são considerados no modelo do PDE, mais este problema se torna complexo e de difícil resolução. Com a evolução das técnicas matemáticas de solução de problemas de otimização, a formulação matemática do PDE tem evoluído de modo a incorporar novas características físicas do processo de produção de energia, tais como: i) a representação dos efeitos provocados pela abertura e fechamento das válvulas de admissão de vapor, chamados efeitos de pontos de carregamento de válvula (Balamu- rugan et al., 2014); ii) a representação das zonas de operação proibida de determinadas unidades de geração (Pourakbari-Kasmaei et al., 2019); iii) a representação de uni- dades geradoras que têm a capacidade de operar utilizando múltiplos combustíveis (Arul et al., 2013); iv) a representação de alguns aspectos relacionados aos �uxos de potência ativa e reativa no sistema de transmissão (Pourakbari-Kasmaei et al., 2019), dentre outros. O Problema de Despacho Econômico considerando os efeitos de pontos de carre- gamento de válvula (PDEPV) é um problema de programação não linear, não convexo, multimodal e não diferenciável. O aspecto multimodal faz com que métodos tradicionais tenham di�culdade para a determinação de um mínimo global e a não diferenciabilidade da função objetivo impossibilita o uso direto do gradiente para a de�nição de direções de busca. As Zonas de Operação Proibida (ZOP) consistem em faixas de geração nas quais o gerador não pode produzir energia, devido a possíveis problemas mecânicos de operação 26 nestas regiões. A função objetivo do PDEPVZ se torna mais complexa e gera ainda mais pontos não diferenciáveis para o problema (além dos pontos de válvula já considerados no PDEPV). A representação do sistema de transmissão pode ser incluída no PDEPVZ e é re- alizada por meio de restrições que garantem o atendimento da demanda em cada barra (balanço de potência) e dos limites operacionais relacionados às linhas de transmissão e transformadores. Em geral, as restrições de balanço de potência em cada barra podem ser formuladas considerando apenas o balanço de potência ativa ou o balanço de potências ativa e reativa. Quando apenas o balanço de potência ativa é considerado, essas equa- ções costumam ser linearizadas. Devido às restrições adicionais relacionadas à rede de transmissão, a dimensão do problema aumenta consideravelmente em comparação com o PDEPVZ, pois as variáveis, parâmetros e restrições devem ser consideradas para cada barra do sistema. Diversas estratégias têm sido utilizadas para aprimorar a suavidade da função ob- jetivo do PDEPVZ e mitigar suas descontinuidades, de modo a permitir sua resolução por abordagens de otimização determinísticas. Em Pinheiro et al. (2022), os autores utilizam a função de Interpolação Polinomial Segmentada para lidar com as descontinui- dades causadas pelas ZOP e tratam a função objetivo para torná-la linear, possibilitando a resolução do problema por meio de métodos baseados em gradientes. Em Gonçalves et al. (2019), os autores apresentam uma abordagem determinística para resolver o Pro- blema de Despacho Econômico Ambiental usando uma técnica de suavização para lidar com a não diferenciabilidade da função objetivo. O termo meta-heurística foi utilizado pela primeira vez em 1986, em um artigo de Fred Glover que tratava sobre o algoritmo de Busca Tabu (Brownlee, 2011). Segundo Melián et al. (2003), este termo vem do pre�xo grego �meta�, que signi�ca além de e da palavra grega �euriskw � que signi�ca inventar, descobrir, encontrar. Juntas, trazem um signi�cado de descoberta de alto nível. As meta-heurísticas são estratégias que, através da experiência anterior, conduzem o processo de busca para obter a solução de um problema, buscando explorar o espaço de soluções de forma mais e�caz. Segundo Sörensen & Glover (2013), o termo meta-heurística pode ser de�nido da seguinte forma: �Uma meta-heurística é uma estrutura algorítmica independente de pro- 27 blemas de alto nível que fornece um conjunto de diretrizes ou estratégias para desenvolver algoritmos de otimização heurística. O termo também é usado para se referir a uma implementação especí�ca do problema de um algoritmo de otimização heurística de acordo com as diretrizes expressas em tal estru- tura� (Sörensen & Glover, 2013). As características de não convexidade e não diferenciabilidade do PDEPVZ têm di- �cultado a aplicação direta de métodos determinísticos para a solução deste problema. Assim, abordagens de otimização não exatas, envolvendo a utilização de meta-heurísticas, têm sido propostas para a solucioná-lo. Além de lidar diretamente com essas caracterís- ticas, as meta-heurísticas permitem uma maior exploração do espaço de busca e tendem a di�cultar a convergência precoce para ótimos locais, a qual ocorre frequentemente em métodos determinísticos tradicionais. Dentre as principais meta-heurísticas utilizadas na solução de problemas de otimização complexos, pode-se destacar: os Algoritmos Genéticos (Gaspar-Cunha et al., 2012), a Otimização por Enxame de Partículas (Engelbre- cht, 2007; Hosseinnezhad & Babaei, 2013), os Algoritmos de Otimização por Gafa- nhotos (Mandal & Roy, 2021), a Busca Tabu (Brownlee, 2011; Sa-Ngiamvibool et al., 2011), o Recozimento Simulado (Gaspar-Cunha et al., 2012; Vishwakarma et al., 2012), Algoritmo do morcego (Pang et al., 2023), a Otimização por Colônia de Formigas (ACO-Ant Colony Optimization)(Pothiya et al., 2010; Secui, 2015), dentre muitas outras. Entre as clássicas e recentes referências sobre meta-heurísticas aplicadas na resolução do PDE, pode-se mencionar (Singh & Dhillon, 2019; Sun et al., 2020; Chavez et al., 2019; Ghasemi et al., 2016; Srivastava & Das, 2020; Neto et al., 2017; Liu et al., 2016; Mohammadian et al., 2018; Gholamghasemi et al., 2019; Xin-gang et al., 2020). Apesar de existirem muitos métodos evolutivos propostos na literatura, não encontrou- se nenhum método especi�camente desenvolvido para resolver o PDE, cuja prova de con- vergência tenha sido apresentada. Neste trabalho propõe-se o Algoritmo Genético Direcionado (AGD) para resolver o PDEPVZ. O AGD baseia-se no Algoritmo Genético (AG) convencional, que é uma meta-heurística da classe dos algoritmos evolutivos e cuja metáfora envolve a evolução natural proposta por Charles Darwin. O método proposto busca reduzir o custo compu- 28 tacional através da diminuição do espaço de busca e evitar a convergência precoce, sem perder a capacidade de exploração, uma vez que realiza a busca de forma direcionada às singularidades da função objetivo. As singularidades são os pontos onde a função deixa de ser diferenciável e a motivação está no fato de que, segundo Zhan et al. (2014a) e Zhan et al. (2014b), os mínimos locais de um PDEPV estão nas singularidades (exceto possivelmente em um dos geradores, chamado de gerador slack), na grande maioria dos casos. Para problemas de pequeno porte, não haveria necessidade de nenhum método, pois todas as singularidades do problema poderiam ser investigadas e comparadas. Po- rém, para problemas de grande porte, tal análise teria um custo computacional muito alto e, neste caso, o AGD seria bastante útil. Outra contribuição deste trabalho está no fato de que o AGD é interpretado em um contexto de sistemas dinâmicos estocásticos, o que permitiu provar a convergência do método através de ferramentas da Teoria de Probabilidade. Mais especi�camente, demonstra-se que, com probabilidade 1, a trajetória percorrida pelo melhor indivíduo na população se aproxima de um ótimo global à medida que o número de iterações aumenta. A prova também assegura que o algoritmo é capaz de alcançar exatamente o ótimo global quando este está localizado em um ponto de singularidade da função objetivo. Foram realizados testes numéricos com o AGD na resolução do PDEPV e do PDEPVZ para sistemas com 3, 5, 6 e 40 geradores. O método mostrou-se e�caz e obteve resulta- dos de qualidade quando comparado com outros métodos da literatura, melhor até que o próprio AG convencional, comprovando que os operadores criados trouxeram melhorias ao método. Algoritmos Evolutivos, como Algoritmos Genéticos (AG) (Wang et al., 2023; Sukkerd & Wuttipornpun, 2016; Li & Gao, 2016; Fan et al., 2022), Estraté- gia Evolutiva (EE) (Auger, 2005; Beyer, 2013) e Evolução Diferencial (ED) (Zhang et al., 2024; Molina-Pérez et al., 2024; Yang et al., 2024), têm sido amplamente empregados na resolução de problemas não convexos, não diferenciáveis ou multimodais, como pode ser visto em Song & Lin (2021), Wang & Peng (2020), Semenov & Ter- kel (2003) e He & Yu (2001a). No entanto, mesmo com garantias formais de que a população Xt converge para o conjunto de soluções globais ótimas S∗, uma questão fun- damental surge: quão rapidamente a aptidão f(Xt) da população Xt converge para a 29 aptidão ótima f ∗? Nos artigos Ding & Kang (2001a) e He & Kang (1999b), é apresentada uma análise de convergência em distribuição para algoritmos evolutivos com elitismo. Utili- zando a teoria ergódica em cadeias de Markov e técnicas na álgebra de Banach, Ding & Kang (2001a) determinam taxas de convergência de ordem exponencial. Por outro lado, He & Kang (1999b) inicialmente analisam algoritmos evolutivos com operadores genéticos invariantes no tempo, estabelecendo um limite para a taxa de convergência no espaço geral. Para algoritmos adaptativos, eles determinam um limite para a taxa de convergência no espaço de estado �nito. De forma similar, He & Yu (2001b) estudam a convergência em distribuição de algoritmos evolutivos, fornecendo uma análise teórica das condições necessárias e su�cientes. Os autores também estabelecem limites superiores e inferiores para as taxas de convergência dos algoritmos evolutivos. Akimoto et al. (2020) investigam estratégias evolutivas aplicadas a funções quadráticas convexas, explo- rando o conceito de melhoria em um único passo. Tarlowski (2023) analisa a taxa de convergência assintótica através de erros de aproximação esperados durante um processo estocástico em tempo discreto, determinando um limite superior para a taxa de conver- gência e discutindo a relação entre a taxa de convergência no espaço objetivo e no espaço de busca. Além disso, Rudolph (1997a) apresenta uma condição de convergência para casos onde não há uma sequência monotonicamente decrescente de pontos viáveis em direção ao mínimo global e utiliza a razão de erro de uma geração para fornecer limites pre- cisos para a taxa de convergência de funções, como quadráticas, com matriz hessiana de�nida positiva. Recentemente, na busca por uma compreensão teórica da e�ciência do algoritmo (1+1)-ES, os autores em Morinaga et al. (2023) realizaram uma análise da taxa de convergência do algoritmo para uma classe mais ampla de funções convexas, especi�camente aquelas que são localmente L-fortes convexas com gradiente U-Lipschitz contínuo. Outros estudos investigaram a taxa de convergência de algoritmos evolutivos, como Rudolph (1997b); He & Kang (1999a); Auger & Hansen (2016); Ding & Kang (2001b); Jägersküpper (2006, 2007). Considere ft := E[f(Xt)] o valor esperado de f(Xt) e et := |ft− f ∗|, onde Xt é uma população na iteração t. Em He & Lin (2015) e Chen & He (2021), os autores observam 30 que a razão de erro et/et−1 usada em Rudolph (1997a) contém um ruído signi�cativo devido à aleatoriedade, tornando-a impraticável para experimentos numéricos. Portanto, eles propõem uma Taxa Média de Convergência (TMC), dada por Rt = 1 − (et/e0)1/t, que mede a rapidez com que o erro de aproximação de um algoritmo evolutivo converge para zero por geração. Ela incorpora a média geométrica das taxas de erro, fornecendo uma estimativa mais estável em comparação com et/et−1. Recentemente, Tarlowski (2023) utilizou a de�nição da TMC para mostrar que alguns algoritmos não convergem rapidamente, quando utilizados na resolução de problemas de otimização contínua não trivial. Outros trabalhos que utilizaram TMC para medir a velocidade de convergência de algoritmos evolutivos incluem Dong et al. (2018); Dhivyaprabha et al. (2018); Janiga et al. (2019); Li et al. (2019). Mais especi�camente, em Chen & He (2021), os autores apresentam uma aná- lise teórica da TMC em otimização contínua para métodos evolutivos e provam que a TMC é linear quando a mutação é positiva-adaptativa, mas sublinear quando a muta- ção é invariável ou zero-adaptativa. Para alcançar uma TMC linear, a mutação deve ser positiva-adaptativa. No entanto, até onde é do conhecimento do autor, nenhum trabalho fornece um resultado que garanta uma modi�cação na mutação para torná-la positiva- adaptativa e ainda apresente explicitamente um limitante inferior positivo para a TMC, exceto para o caso em que a função objetivo f é simples e a mutação ocorre apenas em uma das entradas (veja o exemplo (59) dado em (Chen & He, 2021, p. 216)). Neste trabalho, com base em Chen & He (2021), consideramos um problema de oti- mização em que a função objetivo é Lipschitz contínua. Para esses problemas, propomos duas alternativas para o operador de mutação e provamos que, em ambos os casos, ob- temos operadores que são positivos-adaptativos. Além disso, obtemos estimativas para o limitante inferior da TMC em termos da constante de Lipschitz e da dimensão do espaço (Teorema 5.3, Corolário 5.4 e Teorema 5.5). Os operadores de mutação propostos são integrados a um Algoritmo Evolutivo (AE) com elitismo, resultando no Algoritmo Evo- lutivo Adaptativo (AEA) proposto. O AEA adapta dinamicamente as taxas de mutação ao longo do processo de busca, visando alcançar uma TMC linear. Para ilustrar os resultados teóricos apresentados, considera-se problemas de otimi- zação tendo como função objetivo a função de Ackley, função Alpine e f(x, y) = x4 + y4, 31 sujeitas a restrições canalizadas. Estas são funções bem conhecidas e amplamente utili- zadas para testar algoritmos. Nestas aplicações, veri�ca-se que as funções satisfazem as condições necessárias e especi�ca-se as estimativas fornecidas no Teorema 5.3, Corolário 5.4 e Teorema 5.5. Alguns grá�cos relacionados à taxa Rt são analisados, onde pode-se observar os resultados teóricos obtidos. Além disso, adaptações foram feitas às hipóteses do Teorema 5.3 e Corolário 5.4, para que pudessem ser aplicados ao PDEPV (Corolários 5.6 e 5.7) e testes foram realizados na resolução do PDEPV utilizando o AEA. Fez-se ainda uma junção entre o AGD e o AEA, incorporando a mutação adaptativa ao AGD, originando o Algoritmo Genético Direcionado Adaptativo (AGDA). Testes foram realizados para o PDEPV com 3, 5 e 40 geradores. Foi possível notar que o AGDA apresenta resultados ainda melhores que os outros métodos propostos na tese. Quando incorporamos a transmissão da rede ao PDEPVZ, temos um modelo ainda mais representativo e próximo da realidade, denominado Problema de Despacho Econô- mico considerando os efeitos de pontos de carregamento de válvula, zonas proibidas e restrições de rede (PDEPVZ-RR). A representação do sistema de transmissão é geral- mente feita utilizando a abordagem da matriz de coe�cientes B (para mais detalhes ver Grainger & Stevenson Jr (1994), Seção 13.3). No entanto, essa abordagem ou negli- gencia os limites de �uxo de potência nas linhas de transmissão ou representa tais limites apenas para as linhas de interconexão, como visto nos modelos PDEPVZ-MA. Neste tra- balho, um novo modelo de sistema de transmissão é desenvolvido para o PDEPVZ-RR, capaz de representar tanto as perdas quanto os limites de �uxo de potência na rede. Este modelo é implementado no AGD por meio de um novo operador, capaz de calcular as perdas e realizar o balanço do �uxo de potência. Implementações são apresentadas na resolução dos sistemas IEEE-118 barras e IEEE-300 barras. A partir das discussões apresentadas, as principais contribuições deste trabalho são: � Propor o AGD, um método de busca direcionada para a resolução do PDEPV e PDEPVZ; � Provar a convergência do AGD através da interpretação da trajetória do melhor indivíduo num contexto de sistema dinâmico estocástico (Proposição 4.22 e Teorema 4.24); 32 � Propor o AEA, um método que incorpora a um algoritmo evolutivo um operador de mutação positivo-adaptativo; � Demonstrar que, para uma função objetivo que seja Lipschitz contínua e satisfaça determinadas hipóteses, o AEA apresenta TMC linear (Teorema 5.3, Corolário 5.4 e Teorema 5.5); � Fornecer explicitamente uma estimativa para o limitante inferior da TMC do AEA, em termos da constante de Lipschitz e da dimensão do problema; � Propor o AGDA, método que incorpora a mutação adaptativa do AEA ao AGD para a resolução do PDEPV (Corolários 5.6 e 5.7); � Desenvolver um novo modelo de sistema de transmissão para o PDEPVZ-RR, capaz de representar tanto as perdas quanto os limites de �uxo de potência na rede e incorporá-lo no AGD através de um novo operador genético chamado �operador de balanço de potência�. Este trabalho está organizado da seguinte forma: o Capítulo 2 apresenta a formu- lação do PDE com efeitos de carregamento de ponto de válvula e zonas de operação proibida. No Capítulo 3, tem-se a descrição do AGD, método proposto neste trabalho e que usa as singularidades da função objetivo para realizar sua busca de forma direcio- nada, prova-se a sua convergência e apresenta-se os testes realizados para validar o AGD na resolução do PDEPV e do PDEPVZ. Faz-se ainda comparações com outros métodos existentes na literatura. No Capítulo 5 propõe-se o AEA, um algoritmo que incorpora uma mutação adaptativa ao AE com elitismo e apresenta-se a TMC, uma forma de medir a velocidade com que o erro médio de um algoritmo tende a zero (He & Lin, 2015; Chen & He, 2021). Ainda neste capítulo, conduz-se uma análise teórica relacionada à TMC em problemas de otimização com função objetivo que seja Lipschitz contínua, prova-se que com as mutações propostas obtém-se uma TMC linear e determina-se estimativas para o limitante inferior da TMC. Além disso, aplica-se os resultados obtidos para minimizar as funções: Ackley, Alpine, f(x, y) = x4 + y4 e na resolução do PDEPV. Já no Capítulo 6 apresenta-se o AGDA, um método que incorpora a mutação adaptativa ao AGD. No Capítulo 7 apresenta-se o modelo PDEPVZ-RR e os testes numéricos realizados. Por �m, no Capítulo 8, conclusões e perspectivas futuras são apresentadas. 33 Capítulo 2 Modelos Matemáticos para o Problema de Despacho Econômico O Problema de Despacho Econômico (PDE) tem sido utilizado como uma ferramenta computacional fundamental para a operação e planejamento de sistemas de potência. O PDE tem como objetivo encontrar o despacho ótimo de geração de energia que atenda uma demanda de energia pré-estabelecida de modo a minimizar os custos de produção, e satisfazendo restrições associadas ao sistema de geração de energia, tais como os limites operacionais de cada unidade geradora. Várias formulações matemáticas têm sido adotadas para o PDE de modo a repre- sentar, de forma cada vez mais detalhada, o processo de geração de energia e os limites operacionais do sistema de geração. Assim, alguns aspectos de modelagem foram sendo progressivamente considerados no PDE tais como: a representação de zonas de operação proibida para algumas unidades geradoras, a representação dos pontos de carregamento de válvula, a representação de unidades que operam com múltiplos combustíveis e a repre- sentação da rede de transmissão. A representação destes aspectos de modelagem aproxima o PDE da operação/planejamento de um sistema de geração mais realista, porém pode tornar o PDE um problema de grande dimensão e de difícil solução, devido a natureza dos problemas de otimização obtidos. Neste capítulo, apresentam-se algumas formulações que têm sido propostas na lite- ratura para o PDE. Na Seção 2.1, descreve-se o modelo para o PDE clássico, proposto 34 na década de 1920 e reformulado como um problema de otimização em Happ (1977). Na Seção 2.2, é descrito o modelo para o PDEPV, em que é introduzida a representação dos pontos de carregamento de válvula para as unidades termelétricas e na Seção 2.3 é descrito o modelo para o PDEPVZ, em que é introduzida a representação das zonas de operação proibida. 2.1 Formulação Clássica do PDE Em sua formulação clássica, o PDE consiste em determinar o despacho ótimo de potência ativa Pi de cada unidade geradora i, buscando minimizar o custo total de pro- dução, de tal forma que as potências geradas estejam dentro dos limites operacionais de cada unidade geradora dados por Pmin i e Pmax i , respectivamente, a �m de suprir uma determinada demanda D. O PDE clássico é modelado como um problema de otimização com função objetivo convexa e quadrática, proposta pela primeira vez por Steinberg et al. (1943). Assim, sendo tem-se que o PDE clássico é descrito pelo modelo (2.1.1): min P nG∑ i=1 [ aiP 2 i + biPi + ci ] s.a. : nG∑ i=1 Pi = D Pmin i ≤ Pi ≤ Pmax i , i = 1, . . . , nG, (2.1.1) em que P = (P1, . . . , PnG) é o vetor de potências ativas geradas, nG é a quantidade de geradores do sistema e ai, bi e ci são os coe�cientes da função de custo do gerador i. 2.2 Formulação do PDEPV Nos geradores termelétricos, existem válvulas de admissão de calor cuja abertura parcial provoca perdas de energia durante a passagem de vapor, aumentando os custos de produção. Além disso, quanto mais estrangulado o vapor, isto é, quanto menor a aber- tura da válvula, menor o rendimento da mesma. Para melhorar o rendimento global, o 35 vapor é controlado por múltiplas válvulas parciais. Portanto, no momento de abertura de cada uma dessas válvulas parciais há uma alteração na curva de rendimento global e, por conseguinte, na curva de custos. Este fenômeno é chamado de efeito de ponto de carrega- mento de válvula, e sua inserção no PDE resulta no problema de despacho denominado de PDEPV. O ponto de carregamento de válvula é de�nido em Happ (1977) como o ponto imediatamente anterior à abertura da próxima válvula. Na função objetivo de custo de combustível do PDE utilizada para as unidades termelétricas, os efeitos provocados pelos pontos de carregamento de válvula podem ser expressos por meio da adição de termos modulares. Dessa forma, a inserção destes termos modulares para a representação dos pontos de carregamento de válvula torna a função objetivo do problema não convexa e não-diferenciável nestes pontos de carregamento de válvula. O problema passa, então, a ser multimodal, di�cultando a determinação de um mínimo global. Gra�camente, os efeitos de ponto de carregamento de válvula para um gerador podem ser vistos na Figura 2.1, em que a linha tracejada indica a curva de custo do gerador i sem considerar os efeitos de ponto de carregamento de válvula e a linha contínua indica a função custo do mesmo gerador, considerando os efeitos de ponto de carregamento de válvula. Os pontos de não diferenciabilidade �cam evidentes no grá�co da função. Figura 2.1: Curva de custo de um gerador sem considerar efeitos de ponto de válvula (linha tracejada) e com efeitos de ponto de válvula (linha contínua). Pmin i Pmax i Pi [MW] C i( P i) [$ /h ] Fonte: Elaborada pelo autor. Com a introdução dos pontos de carregamento de válvula no PDEPV, os métodos determinísticos clássicos �cam impossibilitados de serem diretamente utilizados para a sua solução, pois a não diferenciabilidade da função objetivo impede a determinação do vetor 36 gradiente, utilizado para determinar a direção de busca, e de matrizes hessianas, quando necessário, em alguns métodos. Mesmo que a não diferenciabilidade possa ser tratada para serem aplicados métodos determinísticos, por meio de funções aproximantes, ou por meio de reformulação através de um modelo equivalente, o PDEPV ainda continua sendo um problema multimodal, de modo que os métodos determinísticos tendem a �car presos nos mínimos locais. Uma abordagem que tem sido amplamente utilizada para contornar este problema consiste em utilizar métodos meta-heurísticos para a solução do PDEPV. Mesmo não tendo garantias matemáticas de otimalidade de suas soluções, as meta-heurísticas podem ser capazes de escapar de mínimos locais e encontrar boas aproximações para o mínimo global. Por outro lado, uma desvantagem das meta-heurísticas é que, para problemas de grande porte, o espaço de busca pode se tornar muito amplo, di�cultando a determinação do mínimo global. Conforme se aumenta a quantidade de unidades geradoras, tem-se um aumento substancial da quantidade de mínimos locais. De fato, para um sistema de geração com duas unidades geradoras i e j, o grá�co da função custo pode ser visto na Figura 2.2, a qual apresenta uma quantidade bem maior de mínimos locais, di�cultando a determinação de um mínimo global e aumentando as chances de métodos determinísticos �carem presos. Para sistemas com muitas unidades geradoras, o problema resultante pode atingir números excessivamente altos de pontos de mínimo e máximo locais. Figura 2.2: Superfície de custo de um sistema de dois geradores considerando efeitos de ponto de carregamento de válvula. Pi [MW] Pj [MW] C i( P i) + C j (P j ) [$ /h ] Fonte: Elaborada pelo autor. A partir da discussão acima, o modelo de PDEPV possui as mesmas restrições do problema de PDE clássico, porém sua função objetivo possui um termo que corresponde 37 ao módulo de uma senoide, que representa os pontos de carregamento de válvula, conforme mostrado em (2.2.1): min P nG∑ i=1 [ ai · P 2 i + bi · Pi + ci+ | ei · sen(fi · (Pmin i − Pi)) | ] s.a. nG∑ i=1 Pi = D Pmin i ≤ Pi ≤ Pmax i , i = 1, . . . , nG, (2.2.1) em que as constantes ai, bi, ci, ei e fi são os coe�cientes da curva de custo de combustível do gerador i. 2.3 Formulação do PDEPVZ De acordo com De Oliveira et al. (2008), as ZOP de uma unidade termelétrica podem existir devido a faltas nas máquinas, oscilações das válvulas a vapor no eixo da máquina ou nos serviços auxiliares como caldeiras, bombas de alimentação, entre outras causas. A melhor maneira de tratar esse problema é evitando a operação destas unidades nas regiões proibidas. Assim, se forem considerados os efeitos de ponto de carregamento de válvula e as zonas de operação proibida, a função de custo de produção do problema passa a apresentar regiões de descontinuidade, como mostra a Figura 2.3, em que as zonas de operação proibida são as regiões hachuradas. Dada uma unidade geradora i, denotando o limite mínimo e máximo da p−ésima zona proibida por P l i,p e P u i,p, respectivamente, as zonas de operação permitida do gerador i podem ser descritas conforme (2.3.1): Pmin i ≤ Pi ≤ P l i,1 P u i,p−1 ≤ Pi ≤ P l i,p, p = 2, . . . , zi P u i,zi ≤ Pi ≤ Pmax i (2.3.1) em que zi é a quantidade de zonas de operação proibida deste gerador. Denotando-se Pmin i = P u i,0 e Pmax i = P l i,zi+1, tem-se que o PDEPVZ pode ser mode- 38 Figura 2.3: Curva de custo de um gerador i considerando efeitos de ponto de carregamento de válvula e com zonas de operação proibida (área hachurada). Pmin i P l i,1 P u i,1 P l i,2 P u i,2 P l i,3 P u i,3 Pmax i Pi[MW] C i( P i) [$ /h ] Fonte: Elaborada pelo autor. lado conforme descrito em (2.3.2): min P nG∑ i=1 [ aiPi 2 + biPi + ci + |ei sen(fi(P min i − Pi))| ] s.a: nG∑ i=1 Pi = D Pi ∈ zi⋃ p=0 [ P u i,p, P l i,p+1 ] , i = 1, . . . , nG. (2.3.2) Além dos modelos apresentados neste capítulo para o PDE, podemos ainda con- siderar as características do sistema de transmissão, resultando em um PDEPVZ com restrições de rede (PDEPVZ-RR), que será investigado no Capítulo 7, bem como as adaptações propostas ao AGD para o tratamento das restrições adicionais associadas à rede de transmissão. Para a resolução de problemas de despacho econômico, no próximo capítulo, além do AG convencional e da de�nição de singularidades (conceito fundamental para a construção do AGD), são apresentados os detalhes do AGD e cada um de seus operadores. 39 Capítulo 3 Algoritmo Genético Direcionado - AGD Este capítulo tem como objetivo descrever o AGD, método proposto neste traba- lho para a solução do PDEPVZ (também pode ser aplicado ao PDEPV). Inicialmente, descreve-se AG em sua versão clássica, incluindo a �metáfora� que inspira o método e seus operadores fundamentais. Em seguida, as singularidades relacionadas ao PDEPVZ são descritas, bem como a sua importância na resolução do problema. Então apresenta-se o método AGD, método inspirado no AG clássico e que utiliza as propriedades relacionadas às singularidades da função objetivo do PDEPVZ no seu processo de busca. Além disso, a convergência do AGD é provada e testes numéricos são realizados. 3.1 Descrição do método 3.1.1 Algoritmo Genético - AG Os métodos evolutivos são algoritmos que se baseiam na Teoria da Evolução de Charles Darwin e utilizam o cruzamento (crossover) e a seleção natural (sobrevivência do mais apto) para determinar uma solução para um problema. Estes métodos têm sido amplamente utilizados na solução de problemas de engenharia, machine learning e inteligência arti�cial. Alguns exemplos de métodos evolutivos envolvem: algoritmos genéticos, programação evolutiva e estratégias evolutivas, evolução diferencial, dentre outros. Segundo Gaspar-Cunha et al. (2012), os métodos evolutivos surgiram em 1960 com o trabalho do americano John Henry Holland, da Universidade de Michigan. 40 Neste trabalho, o método evolutivo abordado é o Algoritmo Genético (AG). Nesta seção, descreve-se a metáfora utilizada como inspiração para o desenvolvimento do método e detalha-se os principais operadores utilizados na construção do AG. O AG tem sua inspiração na Teoria da Evolução criada por Charles Darwin no século XIX, em que um indivíduo mais adaptado ao meio tende a sobreviver em determinada condição e se reproduzir. Ao fazê-lo, suas características mais �vantajosas� passam para outras gerações (descendentes) através da reprodução. Em contrapartida, os indivíduos menos adaptados, tendem a se extinguir. De acordo com Darwin, existe uma luta cons- tante pela sobrevivência e nessa luta somente os mais aptos sobrevivem. Este processo é chamado seleção natural e durante sua realização, podem ocorrer as chamadas mutações, evitando que os �lhos sejam cópias de seus pais. A seleção natural pode ser de três tipos: direcional (um determinado fenótipo tem sua frequência aumentada), estabilizadora (os fenótipos intermediários são selecionados e os extremos são eliminados) e disruptiva (os extremos são favorecidos se comparados com os intermediários pois os extremos são mantidos na população). Os genes fornecem todas as características que serão passadas aos descendentes, como tamanho, peso, cor, dentre outros. A ideia do AG é gerar uma população inicial onde cada indivíduo é uma solução potencial para o problema a ser resolvido, e cada um de seus genes corresponde ao valor que uma das variáveis do problema deve assumir. Em seguida, ocorre um processo de seleção em que são de�nidos os pais que irão se reproduzir e gerar iterativamente indivíduos �lhos a partir da população anterior, buscando sempre melhorar os indivíduos e transmitir as melhores características de cada um deles. A mutação é incorporada ao método através de uma pequena perturbação em um ou mais genes dos indivíduos �lhos. No AG, a cada iteração obtém-se uma geração de indivíduos em que cada um deles representa uma solução potencial para o problema que se deseja resolver. De forma 41 bastante geral, as principais etapas envolvidas no algoritmo são enumeradas a seguir: (i) Estabeleça uma representação cromossomial; (ii) Inicialize a população de indivíduos; (iii) Avalie cada indivíduo criado; (iv) Selecione os pais; (v) Faça o crossover ; (vi) Faça a mutação; (vii) Avalie os �lhos; (viii) Veri�que o critério de parada. Na etapa (i), cada indivíduo é representado por uma sequência numérica, chamada de cromossomo. Cada cromossomo representa os valores a serem assumidos por cada variável do problema de otimização que está sendo resolvido. O cromossomo é geralmente descrito por meio de uma codi�cação que pode ser realizada utilizando-se números reais ou binários. Na etapa (ii), determinam-se os valores iniciais que devem ser assumidos pela po- pulação inicial. Em geral, estes valores são estabelecidos de forma aleatória. Na etapa (iii), cada indivíduo criado deve ser avaliado por meio de uma função avaliação que mede o grau de adaptabilidade (�tness) do indivíduo. Esta função deve levar em consideração o valor da função objetivo e o grau de factibilidade do indivíduo, no que diz respeito ao atendimento das restrições do problema de otimização que se pretende resolver. Na etapa (iv), a operação de seleção escolhe os pais que deverão participar no pro- cesso de reprodução. A seleção pode ser feita aleatoriamente, com pesos iguais para todos os indivíduos, ou associando cada indivíduo a uma probabilidade de ser selecionado, de acordo com o valor obtido na função de avaliação anterior. Dessa última forma, os indiví- duos que tiverem melhor avaliação terão maiores chances de serem escolhidos no processo seletivo. Outra forma de o indivíduo ser selecionado envolve o operador denominado de elitismo. Por meio deste operador, os melhores indivíduos sempre são escolhidos para compor a próxima geração, sem a necessidade de cruzamento com outro indivíduo. 42 Na etapa (v), os novos indivíduos (�lhos) são gerados a partir do cruzamento dos indivíduos selecionados (pais) mais aptos, de modo a buscar uma evolução continuada dos indivíduos em cada geração. De acordo com Engelbrecht (2007), este cruzamento (crossover) pode ser assexual (um pai gera toda a prole), sexual (dois pais são utilizados para produzir um ou dois �lhos) ou multi-recombinação (mais de dois pais são utilizados para gerar um ou mais descendentes). No cruzamento sexual, uma possibilidade é escolher aleatoriamente um ponto de corte para o cromossomo dos indivíduos selecionados, realizar o corte e recombinar as partes, obtendo dois novos indivíduos (�lhos). Na etapa (vi), os indivíduos gerados (�lhos) podem estar sujeitos a sofrer mutação. O operador de mutação consiste em uma perturbação aleatória nos genes dos indivíduos. O grau de incidência da mutação em cada gene do indivíduo é determinado pelo chamado coe�ciente de mutação, que estabelece uma taxa (porcentagem) que de�ne se a mutação deve ou não ocorrer em cada gene. Assim, o coe�ciente de mutação precisa ser estabelecido como um número pequeno para que o algoritmo não perca as boas características genéticas já adquiridas dos indivíduos. Por outro lado, quando utilizada com coe�cientes de mutação altos, a mutação permite o surgimento de indivíduos que podem ser geneticamente diversos de seus pais, promovendo maior variabilidade ao algoritmo. Na etapa (vii), a população é atualizada com os melhores indivíduos entre a popula- ção de pais e os indivíduos �lhos, tomando o cuidado de manter o tamanho da população �xo em cada geração. Por �m, na etapa (viii), veri�ca-se o critério de parada do algoritmo, que pode envolver dois critérios básicos: a quantidade máxima de gerações é atingida ou ocorre uma estagnação (não melhora) dos valores de �tness no melhor indivíduo de cada geração. Após esta etapa, caso o critério de parada não seja atingido, o algoritmo retorna à etapa (iv) para um novo processo de seleção, e assim, sucessivamente. 3.1.2 Singularidades associadas ao problema Na literatura, alguns trabalhos que propõem métodos determinísticos para resolver o PDEPV e o PDEPVZ utilizam técnicas para suavizar a função objetivo nos pontos não diferenciáveis ou reescrever a função modular de forma equivalente (Pinheiro et al., 43 2022). Nos métodos determinísticos, a reformulação da parcela não diferenciável da função objetivo é absolutamente necessária, pois estes métodos dependem intrinsecamente da obtenção das derivadas da função (bem como das funções associadas às restrições) para compor suas direções de busca, as quais são baseadas no gradiente e/ou hessiana. Por outro lado, essas questões de diferenciabilidade não são importantes para os algoritmos baseados em meta-heurísticas, uma vez que nestes algoritmos não se faz distinção entre pontos diferenciáveis e não-diferenciáveis. No entanto, no AGD aqui proposto, dá-se ênfase exatamente nos pontos onde a função objetivo não é diferenciável e portanto algumas de�nições se fazem necessárias. Nesta seção de�ne-se pontos especí�cos de uma função, denominados singularida- des, e evidencia-se a sua importância na resolução do PDEPV. Mostra-se que grande parte das soluções numéricas que têm sido obtidas para o PDEPV apresenta valores de potência ativa ótima das unidades geradoras posicionados exatamente nos pontos de sin- gularidade da função objetivo. Assim, o AGD realiza a busca da solução ótima focando principalmente nestes pontos de singularidade da função objetivo, cuja de�nição será dada a seguir. De�nição 3.1. Considere a função Ci : Di ⊂ R→ R de�nida por Ci(xi) = aixi 2 + bixi + ci + |ei sen(fi(P min i − xi))|, em que Di é um conjunto compacto. Um ponto xi ∈ Di é chamado de singularidade de Ci se for um ponto de carregamento de válvula do gerador i, um limitante de sua capacidade de geração ou um limitante de alguma zona de operação proibida deste gerador. Para a função F (x1, . . . , xn) = n∑ j=1 Cj(xj), n ≥ 2, dizemos que x = (x1, . . . , xn) ∈ D = D1 × . . . × Dn é uma singularidade de F se existe uma lista de n− 1 coordenadas de x tal que para todo xj nesta lista, temos que xj é uma singularidade de Cj. De acordo com a de�nição, uma singularidade associada ao PDEPVZ (ou ao PDEPV) possui na i−ésima entrada, uma singularidade de Ci, para todas as suas coordenadas, ex- ceto, possivelmente, em uma delas. Portanto, a �m de determinar as singularidades de F, vamos determinar as singularidades factíveis associadas a cada gerador e combinar os 44 valores obtidos em n−1 coordenadas. Os pontos onde a função Ci não é diferenciável são aqueles onde o termo modular se anula (derivada muda de sinal), ou seja, sen(fi · (Pmin i − Pi)) = 0 ⇒ fi · (Pi − Pmin i ) = ki · π, ki ∈ Z ⇒ Pi = ki · π fi + Pmin i . (3.1.1) Para que as potências geradas respeitem os limites da capacidade de geração do gerador i, dadas por Pmin i ≤ Pi ≤ Pmax i , é necessário que 0 ≤ ki ≤ Ni, onde Ni = ⌊ fi · Pmax i − Pmin i π ⌋ . Acima, byc denota a função piso, ou seja, ela transforma o número real y no maior inteiro menor ou igual a y. Além destes pontos, devemos incluir Pmax i (Pmin i já foi considerado para ki = 0) e to- dos os limites (inferior e superior) de todas as zonas de operação proibida. E ainda excluir as singularidades que pertencerem às zonas de operação proibida. Com este processo, ob- temos todas as singularidades associadas a cada gerador do sistema e, consequentemente, as singularidades associadas ao PDEPVZ. O conceito de singularidade é fundamental para o AGD pois, utilizando técnicas baseadas no AG, realiza sua busca de forma direcionada às singularidades associadas ao problema. Este direcionamento nas buscas é utilizado para que possamos diminuir o espaço de busca, aumentando assim a velocidade de convergência, e se faz através das singularidades pois, segundo Zhan et al. (2014a), quando resolvemos o PDEPV, na grande maioria das vezes, o mínimo global se encontra em uma singularidade do problema. Em Zhan et al. (2014a), os autores analisam primeiramente o PDEPV com duas variáveis, considerando constantes as outras variáveis do problema. Esta análise é feita através do sinal das derivadas laterais de primeira e segunda ordem da função objetivo e, 45 fazendo uma pequena perturbação (para mais e para menos) nas coordenadas do ponto, veri�cando se o ponto inicial é um mínimo local ou não. Mais precisamente, dado um ponto factível (x, y), para um valor pequeno qualquer ε, consideram-se os pontos (x + ε, y−K · ε) e (x− ε, y+K · ε), onde K é um valor considerado para que o atendimento de demanda continue sendo respeitado. Em seguida, compara-se o valor da função objetivo nos três pontos, buscando concluir se (x, y) é um mínimo local. Após realizarem este procedimento com pontos que estão em cada área da região factível (singularidades em ambas as coordenadas, em apenas uma delas ou em nenhuma delas), foi possível criar uma tabela com todas as situações possíveis e caracterizar os mínimos locais do problema. Ainda de acordo com Zhan et al. (2014a), para o PDEPV com n geradores os autores observaram que se (x1, . . . , xn) é um mínimo local então, se tomarmos duas va- riáveis quaisquer, teremos um mínimo local no problema de duas variáveis, considerando as outras variáveis constantes. Isso é válido pois a função objetivo do PDEPV (também PDEPVZ) não possui termos mistos (termos envolvendo mais de uma variável). Como os mínimos dos problemas de duas variáveis foram analisados e caracterizados, os autores puderam dividir os mínimos locais de um problema de n variáveis em dois tipos: Tipo 1 - Existe no máximo uma unidade geradora cuja saída de potência ativa gerada não se localiza em uma singularidade; Tipo 2 - Existem duas ou mais unidades geradoras cujas saídas de potência ativa gerada não se localizam em singularidades. Note que o Tipo 1 signi�ca que o mínimo local está em um ponto singular e o Tipo 2 ocorre quando o mínimo local não está em um ponto singular da região factível. Além disso, os autores analisam a proporção entre os mínimos do Tipo 1 e Tipo 2, e detectam que o Tipo 2 ocorre em apenas 2.75% das vezes e que, portanto, este tipo de mínimo local é muito pouco provável de ocorrer. Assim, os autores concluem que na grande maioria dos casos, os mínimos locais estão em pontos de singularidade da região factível (i.e. geradores com saída de potência ativa em pontos de singularidade, exceto possivelmente em um deles). Os autores calculam ainda o erro causado ao modi�carmos um ponto do Tipo 2 para o Tipo 1 e concluem que esta mudança provoca uma perda muito pequena na precisão. Em geral, o gerador que se permite gerar fora das suas singularidades é o responsável pelo ajuste de potência necessário para que ocorra o atendimento da demanda. 46 3.1.3 Pseudocódigo e Operadores Nesta seção, são fornecidos os detalhes do AGD, método proposto neste trabalho e que, visando melhorar o desempenho do AG na resolução do PDEPVZ e aumentar a velocidade de convergência, propõe modi�cações ao método descrito na Seção 3.1.1, de modo a direcionar o processo de busca, priorizando mínimos locais do Tipo 1. A motivação para a criação de novos operadores no AG são as informações apresen- tadas na Seção 3.1.2 sobre as singularidades da função objetivo do problema e sua estreita relação com as soluções do PDEPV (e também do PDEPVZ). Além disso, como visto na Seção 3.1.2, como as singularidades são os pontos em que a função não é diferenciável, no PDEPVZ estes pontos correspondem àqueles em que ocorre o carregamento de válvula, os extremos da capacidade de geração e também os extremos das zonas de operação proibida. Outra motivação para o AGD está no trabalho descrito em Secui (2015), onde os autores utilizam a busca direcionada a singularidades para resolver um PDEPV di- nâmico por meio de um método que pertence ao Ant Colony Optimization (ACO), um grupo de algoritmos baseados no comportamento das formigas. Nos testes realizados, após determinarem as soluções, os autores também observaram a alta incidência de óti- mos posicionados em pontos de carregamento de válvula e em limites da capacidade de geração, constatando que aproximadamente 90% das soluções encontradas estavam nas singularidades associadas ao problema. Os dados percentuais obtidos em Secui (2015), com relação à incidência de mínimos nas singularidades, estão resumidos na Tabela 3.1. Tabela 3.1: Incidência de soluções nas singularidades do PDEPV segundo Secui (2015) para sistemas de 10 e 13 geradores. 10 geradores (%) 13 geradores (%) Pontos de válvula 48,34 72,44 Pmin ou Pmax 38,33 18,27 Total 86,67 90,71 Fonte: Secui (2015). 3.1.3.1 Pseudocódigo do AGD O AGD recebe este nome pois realiza sua busca de forma direcionada às singulari- dades associadas ao problema, uma vez que esta característica é levada em consideração na criação dos indivíduos e na presença do indivíduo pivô, que será descrito em detalhes 47 a seguir. O pseudocódigo do AGD é mostrado no Algoritmo 1, sendo que cada operador será detalhado nas próximas seções. Algoritmo 1 Pseudocódigo do AGD 1: Inicialize os parâmetros: t = 0, nI (número de indivíduos) e pM (probabilidade de ocorrência da mutação); 2: Determine todas as singularidades factíveis de cada gerador; 3: Gere a população inicial POP de acordo com a Seção 3.1.3.2; 4: Gere o indivíduo pivô Ip de acordo com a Seção 3.1.3.3 e acrescentar à POP ; 5: Ajuste todos os indivíduos de POP, para que todos se tornem factíveis de acordo com Seção 3.1.3.2; 6: Avalie cada indivíduo de POP de acordo com Seção 3.1.3.6; 7: while condição de parada não é satisfeita do 8: for i = 1, ..., nI 2 do 9: Selecione aleatoriamente dois indivíduos de POP ; 10: Aplique o crossover de acordo com a Seção 3.1.3.4; 11: Aplique a mutação com probabilidade pM de acordo com a Seção 3.1.3.5; 12: Ajuste os indivíduos �lhos, para que se tornem factíveis de acordo com Seção 3.1.3.2; 13: Compare os dois �lhos obtidos com os pais e mantenha os dois melhores; 14: end for 15: Atualize a população; 16: Faça a mutação do indivíduo pivô Ip como descrito na Seção 3.1.3.3, compare com o pivô anterior e acrescente o melhor deles em POP ; 17: t = t+ 1 18: end while 19: Retorne o melhor indivíduo de POP como solução. 3.1.3.2 População Inicial Para gerar a população inicial de tamanho nI ≥ 2, determina-se primeiramente todas as singularidades de cada gerador i, i = 1, . . . , nG. Feito isso, cada indivíduo será da forma Ij = (P j 1 , . . . , P j nG ), j = 1, . . . , nI , e cada gene P j i é escolhido aleatoriamente entre as singularidades do gerador i. Note que ao realizar a escolha de seus genes de forma aleatória, as restrições de limite de capacidade de geração são intrinsecamente satisfeitas, uma vez que as singularidades criadas já obedecem tais limites. Por outro lado, os indivíduos gerados não levam em consideração a restrição de atendimento da demanda. Para que tenhamos um indivíduo Ij factível com respeito também ao atendimento de demanda D, alguns ajustes precisam ser realizados: 48 � Calcula-se ∆j: ∆j = D − nG∑ i=1 P j i . � Se ∆j > 0, signi�ca que a demanda não foi atendida em sua integralidade e é necessário aumentar um pouco a potência total despachada. Veri�ca-se então se existe algum gerador capaz de gerar o que já estava previsto mais essa diferença dada por ∆j, sem violar sua capacidade de geração. Se existir tal gerador, este será o gerador slack. Caso contrário, é necessário distribuir a diferença, de forma sucessiva, entre os demais geradores, começando por aquele que possui maior capacidade livre, até que a demanda seja atendida; � Se ∆j < 0, signi�ca que a potência total despachada está acima da demanda e, portanto, é necessário reduzir as gerações para o atendimento da demanda. De forma semelhante ao caso anterior, veri�ca-se, inicialmente, se existe algum gerador do qual pode-se retirar todo o excesso de geração sem violar nenhuma de suas restrições. De forma análoga ao caso anterior, se existir tal gerador, este será o gerador slack. Caso contrário, é necessário retirar a diferença, de forma sucessiva, dos demais geradores, até que a demanda seja satisfeita. A partir do procedimento acima, obtém-se uma população inicial composta somente por indivíduos factíveis. Este ajuste também será realizado sempre antes de um indivíduo ser avaliado. 3.1.3.3 Indivíduo pivô Na Seção 3.1.2 mostrou-se que no PDEPV os mínimos ocorrem, em sua grande mai- oria, nas singularidades da função objetivo. Entretanto, a aplicação de alguns operadores genéticos, tais como a mutação (descrita em 3.1.3.5) ou o ajuste (3.1.3.6), podem fazer com que os indivíduos saiam das singularidades. Neste caso, como as singularidades são pontos (medida nula), se todos os indivíduos saírem das singularidades, existe a proba- bilidade de nunca mais voltarem, comprometendo o desempenho do método. Para evitar que isso ocorra, propõe-se neste trabalho um novo operador genético chamado de indiví- duo pivô Ip, que realizará sua busca apenas nas singularidades (ele caminhará apenas nas singularidades, buscando a melhor solução). Em cada geração, o indivíduo pivô tem a 49 possibilidade de �pular� de uma singularidade para outra, se esta for uma solução melhor que a anterior. 3.1.3.4 Crossover O crossover é realizado para que possamos gerar novos indivíduos. Para realizá-lo, escolhe-se aleatoriamente dois indivíduos da população e realiza-se o crossover da seguinte forma: sorteia-se um ponto de corte e realiza-se a troca das entradas a partir deste ponto. Então, se os indivíduos escolhidos para sofrerem o crossover forem I i = (P i 1, . . . , P i nG ), e Ij = (P j 1 , . . . , P j nG ), e se o ponto de corte sorteado for k, então os �lhos serão dados por: filho1 = (P i 1, . . . , P i k, P j k+1, . . . , P j nG ) e filho2 = (P j 1 , . . . , P j k , P i k+1, . . . , P i nG ). 3.1.3.5 Mutação Com uma taxa de mutação pM , cada indivíduo �lho obtido pode sofrer uma mutação feita através da soma de uma perturbação a cada gene do indivíduo. Cada perturbação é obtida aleatoriamente da distribuição normal de média 0 e desvio padrão 1, denotada por N (0, 1). Assim, se o indivíduo Ij = (P j 1 , . . . , P j nG ) sofrer a mutação, este indivíduo passa a ser dado por: Ij + ξ = (P j 1 + ξ1, . . . , P j nG + ξnG), em que ξi ∈ N (0, 1), i = 1, . . . , nG. 3.1.3.6 Avaliação A função FA(Ij) tem como objetivo fazer a avaliação de cada indivíduo Ij, de modo que seja possível estabelecer parâmetros de adaptabilidade (i.e. �tness) que permitam selecionar os indivíduos que devem sobreviver e identi�car aqueles que serão extintos. Antes de avaliar os indivíduos, é necessário executar o procedimento de ajuste des- crito na Seção 3.1.3.2, de modo que o atendimento de demanda seja viabilizado, e para que as restrições impostas pela capacidade de geração de cada gerador não sejam violadas, de modo que somente indivíduos factíveis sejam avaliados, assim como realizado na criação da população inicial. Portanto, após a realização deste procedimento, não existe a neces- 50 sidade de penalização dos indivíduos pelo não atendimento das restrições do PDEPVZ. Nesse caso, dado que todos os indivíduos são factíveis, a função de avaliação deve levar em conta somente a função objetivo original do problema, conforme descrito a seguir: FA(Ij) = 1 C(Ij) = ( nG∑ i=1 Ci(P j i ) )−1 em que C(Ij) é o custo de combustíveis associado ao indivíduo Ij = (P j 1 , . . . , P j nG ). Por- tanto, a partir da função de avaliação descrita acima, o indivíduo com menor custo terá a melhor avaliação. 3.1.3.7 Elitismo O elitismo é um operador que impede a piora na função objetivo da população. No AGD, o elitismo ocorre através da sobrevivência do melhor indivíduo para a próxima geração. Além disso, após a avaliação dos �lhos gerados, eles são comparados com seus pais e apenas os dois indivíduos com melhor avaliação vão sobreviver. 3.1.3.8 Critério de parada No AGD, assim como na grande maioria das meta-heurísticas, utiliza-se dois critérios de parada: a quantidade de gerações (i.e. o número de iterações do método) ng e a não melhora nas soluções das últimas iterações (estagnação), o que ocorrer primeiro. 51 Capítulo 4 Convergência Nesta seção demonstra-se a convergência do AGD, método proposto neste traba- lho para resolver o PDEPVZ, o qual se baseia no AG e cujos detalhes são descritos na Seção 3.1. Para facilitar a compreensão da prova de convergência, primeiramente são for- necidos alguns conceitos preliminares relacionados à Análise e Teoria de Probabilidade. Entretanto, estes temas não serão descritos de forma aprofundada, uma vez que fogem aos objetivos deste trabalho. Para maiores detalhes envolvendo estes temas, sugere-se as referências Barry (2008), Elon (2009) e Allen (2010). Em seguida, demonstra-se que se o PDEPVZ tiver pelo menos um ótimo global e este estiver localizado em uma singu- laridade, o método será capaz de encontrá-lo e se o PDEPVZ tiver pelo menos um ótimo global e este não estiver localizado em uma singularidade, o AGD conseguirá chegar tão próximo quanto se queira deste ótimo global. 4.0.1 Noções preliminares Nesta seção são fornecidos alguns conceitos necessários para o entendimento da prova da convergência do AGD. Para isso, criou-se as seguintes seções: funções contínuas em compactos, teoria de probabilidade, variáveis aleatórias e cadeia de Markov. 52 4.0.1.1 Funções contínuas em compactos De�nição 4.1. Considere a função f : X ⊂ Rn → R. Dizemos que f é contínua em a ∈ X se para todo ε > 0 existe um δ > 0 tal que x ∈ X e ‖x− a‖ ≤ δ ⇒ |f(x)− f(a)| ≤ ε. Dizemos que f é contínua se for contínua em todo seu domínio. De�nição 4.2. Dizemos que K ⊂ Rn é um conjunto compacto se ele for limitado e fechado. Uma propriedade que segue da de�nição é que se K1, . . . , Kp são compactos em Rn, então K1 ∪ . . . ∪ Kp é compacto. Esta propriedade será útil, uma vez que no problema considerado, a existência das zonas de operação proibida fazem da região factível uma união de compactos. Proposição 4.3. (Weierstrass) Toda função real contínua f : K → R, de�nida em um conjunto compacto K ⊂ Rn, atinge seu máximo global e seu mínimo global em K, isto é, existem pontos x0, x1 ∈ K tais que f(x0) ≤ f(x) ≤ f(x1) para todo x ∈ K. 4.0.1.2 Teoria de Probabilidade: alguns conceitos e propriedades Uma medida num conjunto Ω é uma função que a cada subconjunto de Ω associa um número real não negativo, de tal forma que a propriedade aditiva seja preservada (a medida da união de dois conjuntos disjuntos é a soma das suas medidas). Uma medida importante é a medida de Lebesgue, que atribui comprimento, área ou volume aos con- juntos, dependendo do espaço Ω. Outra medida também bastante importante é a medida de probabilidade, que associa cada evento à sua probabilidade de ocorrer (uma medida que assume valores em [0, 1]). Existem muitas medidas interessantes e bastante úteis, mas neste trabalho utilizaremos as duas citadas anteriormente. Como pode ser visto em detalhes em Cabral (2010), nem sempre é possível atribuir (de forma consistente) uma medida a todos os subconjuntos de um conjunto qualquer Ω. Para isso, se faz necessário criar uma coleção especial F de subconjuntos de Ω onde a medida está de�nida, chamada σ-álgebra de subconjuntos de Ω. 53 De�nição 4.4. Seja Ω um conjunto e F uma família de subconjuntos de Ω. Dizemos que F é uma σ-álgebra em Ω se satisfaz as seguintes propriedades: (i) ∅ ∈ F ; (ii) A ∈ F =⇒ AC ∈ F , (AC = Ω \ A, complemento de A em Ω); (iii) A1, A2, . . . An, . . . ∈ F =⇒ A := ∞⋃ i=1 Ai ∈ F . Os subconjuntos de Ω que pertencem a uma σ-álgebra F são ditos F -mensuráveis em Teoria da Medida e, no contexto de Teoria de Probabilidade, são chamados eventos. O par (Ω,F) é chamado de espaço mensurável. Uma σ-álgebra bem conhecida na reta real, denominada σ-álgebra de Borel e deno- tada por B (neste caso o espaço mensurável é (R,B)), é quando consideramos a menor σ-álgebra que contém todos os conjuntos abertos da reta real e, portanto, os fechados (por causa do item (ii) da de�nição anterior). Os elementos desta σ-álgebra são chama- dos borelianos. Em termos intuitivos, um boreliano é um conjunto que pode ser obtido de um número enumerável de abertos, aplicando-se as operações união, interseção e comple- mentar um número enumerável de vezes. Esta de�nição pode ser estendida naturalmente para Rn considerando seus abertos, obtendo assim o espaço mensurável (Rn,B). A seguir, é apresentada uma construção axiomática de probabilidade que se deve a Kolmogorov, e que permite um olhar �mais matemático� se comparado à de�nição �frequentista� ou �estatística� de probabilidade. De�nição 4.5. Dada uma σ-álgebra F e uma função P : F → [0, 1], dizemos que P é uma medida de probabilidade no espaço de medida (Ω,F) se satisfaz: (i) P(∅) = 0, P(Ω) = 1; (ii) se A1, A2, ... ∈ F são dois a dois disjuntos, então P ( ∞⋃ i=1 Ai ) = ∞∑ i=1 P(Ai). (Os eventos são dois a dois disjuntos se são mutuamente exclusivos, isto é, Ai ∩Aj = ∅ se i 6= j). Um espaço de probabilidade é composto pela tripla (Ω,F ,P). Quando uma função µ : F → [0,∞] satisfaz apenas a condição aditiva (ii) acima, diz-se simplesmente que µ é uma medida. 54 De�nição 4.6. Seja (Ω,F ,P) um espaço de probabilidade. Se B ∈ F e P(B) > 0, a probabilidade condicional de A dado B é de�nida por: P(A|B) = P(A ∩B) P(B) , A ∈ F . A seguir, será enunciado o Lema de Borel-Cantelli que fornece uma ferramenta para veri�car se uma sequência de eventos (An) ocorre in�nitas vezes. Este lema diz que se a soma in�nita das probabilidades dos eventos é �nita, então o conjunto de todos os resultados que são �repetidos� in�nitamente (muitas vezes) devem ocorrer com probabi- lidade zero. Dizer que a soma das probabilidades é �nita signi�ca que, a menos de um número �nito, as probabilidades são estritamente menores que 1. Mais que isso, conforme n cresce, a probabilidade desses eventos precisa se tornar tão pequena quanto se queira. Sua demonstração pode ser encontrada em Ruffino (2012). Lema 4.7. Borel-Cantelli Seja (An) uma sequência de eventos em um espaço de pro- babilidade e Bn = An ∪ An+1 ∪ . . .. Se ∞∑ n=1 P(An) <∞, então P(B1 ∩B2 ∩ . . .) = 0. Observação 4.8. O conjunto ∞⋂ n=1 ∞⋃ k=n Ak, chamado de limite superior da sequência (Ak), é o evento �ocorrência de um número in�nito dos An�. Para de�nir a medida de Lebesgue, de�ne-se a medida exterior de Lebesgue, criada a partir do conceito de comprimento de intervalos. Feito isso, utilizando do método de Carathéodory ((Cabral, 2010), p.10), obtém-se a σ-álgebra de Lebesgue e a medida de Lebesgue, através da extensão da medida exterior de Lebesgue sobre a σ-álgebra gerada. Por sua vez, esta σ-álgebra obtida é grande o su�ciente para conter os borelianos, ou seja, os borelianos são Lebesgue mensuráveis ((Cabral, 2010), Teorema 1.29). De�nição 4.9. (Medida exterior de Lebesgue) Seja I = (a, b) ⊂ R com ‖I‖ = b − a e ‖∅‖ = 0. A medida exterior de Lebesgue de A ⊂ R é dada por: µ̃(A) = inf { ∞∑ j=0 ‖Ij‖ : (Ij)j∈N é uma sequência de intervalos abertos, tal que A ⊂ ⋃ j∈N Ij } . 55 A σ-álgebra de subconjuntos de R gerada por µ̃ é dada por F̃ = {A ⊂ R | µ̃(E) = µ̃(E ∩ A) + µ̃(E \ A) para todo E ⊂ R}, e seus elementos são chamados de conjuntos mensuráveis a Lebesgue. De�nição 4.10. (Medida de Lebesgue) A medida de Lebesgue µ é dada por µ : F̃ → [0,∞), onde µ(A) = µ̃(A). De�nição 4.11. (Medida (de Lebesgue) nula) Dizemos que A ⊂ R tem medida (de Lebesgue) nula se para todo ε > 0, existe uma sequência (In)n∈N de intervalos abertos e limitados, tal que A ⊂ ∞⋃ n=1 In e ∞∑ n=1 ‖In‖ ≤ ε, sendo ‖I‖ = b− a, se I = (a, b). Um conjunto A tem medida de Lebesgue positiva se não tiver medida de Lebesgue nula. Intuitivamente, pode-se pensar que a região possui área ou volume positivo, de- pendendo da dimensão em que se encontra. Todos os conceitos podem ser estendidos de forma natural para Rn. A proposição a seguir é utilizada por vários autores como uma forma de caracterizar um conjunto Lebesgue-mensurável, como sendo aquele que pode ser �espremido� entre um conjunto fechado contido nele e um conjunto aberto que o contém. Proposição 4.12. Se o conjunto V ⊂ Rn é Lebesgue-mensurável então para todo ε > 0 existe um aberto A e um fechado F, tal que F ⊂ V ⊂ A e µ(A \ F ) < ε, onde µ é a medida de Lebesgue. 4.0.1.3 Variáveis Aleatórias Uma variável aleatória é uma função X que associa os elementos de Ω a números reais, tal que a imagem inversa de qualquer boreliano U ⊂ R é um evento da σ-álgebra F . Isso é exigido para que se possa associar uma probabilidade da variável aleatória X assumir seus valores num determinado boreliano U ⊂ R. Formalmente, tem-se a seguinte de�nição de variável aleatória. 56 De�nição 4.13. Seja (Ω,F ,P) um espaço de probabilidade e (R,B) um espaço men- surável. A função X : Ω → R é uma variável aleatória (ou mensurável) se, para todo boreliano U ∈ B, temos que: X−1(U) = {ω ∈ Ω; X(ω) ∈ U} ∈ F . Na literatura é bastante comum ocorrer a omissão do termo ω e denotar simples- mente por {X ∈ U} ∈ F , portanto faz sentido escrever P({X ∈ U}). De�nição 4.14. As variáveis aleatórias X1, . . . , Xn, de�nidas no mesmo espaço de pro- babilidade (Ω,F ,P), são independentes se P(X1 ∈ U1, X2 ∈ U2, . . . , Xn ∈ Un) = n∏ i=1 P(Xi ∈ Ui), onde cada Ui, i = 1, . . . , n é um boreliano da reta real. A seguir são dadas algumas de�nições sobre distribuição de uma variável aleatória. De�nição 4.15. A variável aleatória X é absolutamente contínua se existe uma função f(t) ≥ 0, tal que FX(x) := P(X ≤ x) = ∫ x −∞ f(t) dt, ∀x ∈ R. Neste caso, dizemos que f é função densidade de probabilidade de X ou simplesmente densidade de X. A função FX é chamada de função de distribuição de X. De�nição 4.16. A variável aleatória X possui distribuição normal com média x̄ e desvio padrão σ se X tem densidade f(x) = 1√ 2πσ e−(x−x̄)2/2σ2 , x ∈ R. Notação: X ∼ N(x̄, σ). De�nição 4.17. Seja (X1, . . . , Xn) um vetor aleatório e F sua função de distribuição. Se existe uma função f ≥ 0, tal que F (x1, . . . , xn) = ∫ xn −∞ . . . ∫ x1 −∞ f(t1, . . . , tn)dt1 . . . dtn, ∀(x1, . . . , xn) ∈ Rn, 57 então f é chamada densidade do vetor aleatório (X1, . . . , Xn) ou densidade conjunta das variáveis aleatórias X1, . . . , Xn. A seguir serão dados alguns resultados importantes para a prova da convergência do AGD. Proposição 4.18. (Barry (2008), p. 63) Se X1, . . . , Xn são variáveis aleatórias inde- pendentes e possuem densidades fX1 , . . . , fXn , então a função f(x1, . . . , xn) = n∏ i=1 fXi(xi), xi ∈ R é densidade conjunta das variáveis aleatórias X1, . . . , Xn, isto é, f = fX1,...,Xn . Proposição 4.19. (Barry (2008), p. 52) Suponha que a variável aleatória X possui função densidade fX . Seja Y uma variável aleatória dada por Y = bX + c, onde b > 0 e c ∈ R. Então a função densidade de Y será: fY (y) = 1 b · fX ( y − c b ) , y ∈ R. 4.0.1.4 Cadeia de Markov Um processo estocástico discreto é uma sequência de variáveis aleatórias Xn, ou seja, para cada �tempo� n ∈ N, Xn é uma variável aleatória em (Ω,F). Se �xarmos ω ∈ Ω e deixarmos variar n, a função n→ Xn(ω) é chamada de trajetória (ou realização) de Xn. Os valores assumidos pela variável aleatória são chamados estados. Para maiores detalhes sobre espaço de probabilidade para uma sequência de variáveis aleatórias ver por exemplo Oliveira et al. (2017). Uma cadeia de Markov (ou processo de Markov) é um processo estocástico discreto (Xn)n∈N cuja probabilidade de transição para determinados estados depende apenas do estado presente em que processo se encontra, ou seja, seu futuro não depende do passado. Mais precisamente, considere um espaço de estados com um número �nito (ou enumerável) de elementos E = {e1, . . . , en}. Então (Xn)n∈N é uma cadeia de Markov se a probabilidade condicional satis�zer P(Xn+1 = xn+1|X0 = x0, . . . , Xn = xn) = P(Xn+1 = xn+1|Xn = xn), (4.0.1) 58 para todo n ≥ 1 e para toda sequência x0, x1, . . . , xn+1 de elementos do espaço de estados E. A probabilidade condicional pij := P(Xn+1 = ej|Xn = ei) é chamada probabilidade de transição do estado ei para ej, e representa a probabilidade do processo estar em ej no tempo n+ 1 dado que estava no estado ei no tempo n. Os estados de uma cadeia de Markov, de acordo com a dinâmica gerada pelas proba- bilidades de transição, podem ser classi�cados como recorrentes, transientes, absorventes, dentre outros. Um estado ei é dito absorvente se, uma vez que o processo chegar nele permanece para sempre, ou seja, pii = 1. Dizemos que um estado é recorrente se a proba- bilidade do processo retornar a ele é 1, do contrário, é dito transiente: existe probabilidade positiva do processo não retornar. Formalmente temos: De�nição 4.20. Dizemos que um estado ej é recorrente se P(Xn+m = ej para algum m ≥ 1 | Xn = ej) = 1, caso contrário é dito transiente. Assim como temos várias formas de convergência para uma sequência de funções, o mesmo ocorre para uma sequência de variáveis aleatórias: como se trata de uma sequência de funções num ambiente probabilístico, surgem naturalmente vários tipos de convergên- cia, como por exemplo, convergência quase sempre, convergência em probabilidade e a convergência em distribuição. Para o AGD foi possível provar a convergência quase sem- pre (ver De�nição 4.21), que é mais �forte� que as outras duas. De fato, a convergência quase sempre implica em convergência em probabilidade (prova em Barry (2008) p.195), e a convergência em probabilidade implica em convergência em distribuição (prova em Barry (2008) p.248). De�nição 4.21. Seja (Xn)n∈N uma sequência de variáveis aleatórias. Dizemos que (Xn)n∈N converge quase sempre (quase certamente, fortemente ou com probabilidade 1) para a variável aleatória X, se P( lim n→∞ Xn = X) = 1. 59 4.0.2 Prova da convergência De maneira geral, o PDEPVZ pode ser modelado da seguinte forma:  min x F (x) s.a. : h(x) = 0 x ∈ R (4.0.2) onde o conjunto factível R ⊂ Rn é compacto (união de compactos), a função objetivo F é contínua no compacto R e a função h é contínua. Para esta seção, a �m de mostrarmos a convergência do método AGD, considerare- mos algumas hipóteses: (H1) A população inicial é não vazia; (H2) Para todo x factível, seja B(x, δ) a bola aberta de centro x e raio δ > 0. A medida de Lebesgue do conjunto B(x, δ) ∩ R é positiva, para todo δ. Isso signi�ca que se tomarmos qualquer vizinhança de um ponto factível, a interseção dela com a região factível possui volume (ou área) positivo; (H3) Existe pelo menos um ótimo global que não é singularidade, denotado por x∗ns, e pelo menos um ótimo global que é singularidade, denotado por x∗s. Note que ambos possuem o mesmo custo, uma vez que são ótimos globais. A região factível associada ao problema PDEPVZ satisfaz a condição (H2). Em geral, esta é uma condição usada em métodos evolutivos em geral, como pode ser visto, por exemplo, em Wang et al. (2005), e a utilizaremos na prova do item (iv) da Propo- sição 4.22 abaixo. Por outro lado, a hipótese (H3) nos permite apresentar as dinâmicas estocásticas mais gerais a serem realizadas pelo AGD. Casos especí�cos são discutidos na Observação 4.26. Considere S = {x ∈ R : x é singularidade} 60 e Qns = {x ∈ R\S : |F (x)− F (x∗ns)| < ε}, para um dado ε > 0. No que se segue, construiremos um processo estocástico discreto (mostrado na Figura 4.1) realizado pelo melhor indivíduo x∗k da população POPk, onde k = 1, 2, . . .. Para esse �m, assumimos o seguinte critério de desempate para a seleção do melhor indivíduo: se houver dois indivíduos, um em uma singularidade e o outro não, com o mesmo valor da função objetivo, o algoritmo deve escolher o indivíduo na singularidade. Além disso, de�nimos os seguintes estados: 1. A população POPk está no estado E1 se x∗k ∈ Qns; 2. A população POPk está no estado E2 se x∗k /∈ S e x∗k /∈ Qns; 3. A população POPk está no estado E3 se x∗k ∈ S e F (x∗k) 6= F (x∗s) 4. A população POPk está no estado E4 se x∗k ∈ S e F (x∗k) = F (x∗s). Figura 4.1: Cadeia de Markov obtida para a população POPk. E4 E2 E3 E1 Fonte: Elaborada pelo autor. 61 Seja pij a probabilidade de transição da população POPk do estado Ei para o es- tado Ej. Como a probabilidade pij não depende dos estados já visitados pela população anteriormente, temos uma Cadeia de Markov. O resultado a seguir nos dará ferramentas para que possamos aplicar o Lema 4.7 e assim mostrar que teremos a convergência quase sempre da sequência gerada pelas imagens do melhor indivíduo de cada geração para o ótimo global do problema. Proposição 4.22. (Probabilidades de transição) Nas condições assumidas anteriormente temos: (i) p12 = p13 = 0; (ii) p44 = 1; (iii) p23 > 0, p24 > 0 e p34 > 0; (iv) p32 > 0; (v) p21 > 0 e p31 > 0. Demonstração. De acordo com a Seção 3.1.3.7, como o melhor indivíduo de cada geração sempre sobrevive, temos que os itens (i) e (ii) são verdadeiros. Para que p24 > 0 e p34 > 0 ocorram, basta notar que o indivíduo pivô IP pertence a POPk e portanto, existe a probabilidade de IP sofrer mutação e se tornar exatamente x∗s, fazendo com que a população esteja no estado E4. Como IP pode sofrer mutação e se tornar o melhor indivíduo da população na próxima iteração, temos que p23 > 0. Temos ainda que p32 > 0 pois, através da mutação, se o melhor indivíduo está em uma singular