Otimização de Sensores em Rda

Desenvolver e comparar metodologias de otimização baseadas em Algoritmo Genético GA e PSO para determinar o posicionamento ideal de sensores acústicos visando a cobertura total da rede de distribuição de água de Hanoi com o menor número de sensores possíveis 1 Modelagem da Rede de Hanoi Use o EPANET para obter a estrutura da rede ou baixe diretamente a versão padrão da rede de Hanoi Extraia os nós e conexões comprimentos dos trechos diâmetros etc Modele como um grafo para facilitar o uso em algoritmos 2 Definir Parâmetros do Sensor Acústico Raio de detecção definir por exemplo 100 metros ao longo da tubulação não em linha reta Assuma que um sensor instalado em um nó cobre todas as conexões dentro desse raio 3 Formulação do Problema Função objetivo Minimizar o número total de sensores Restrições Toda tubulação deve estar dentro do alcance de pelo menos um sensor Variáveis Vetor binário representando a instalação do sensor em cada nó 1 sim 0 não 4 Implementação dos Algoritmos Algoritmo Genético GA Codificação vetor binário População inicial soluções aleatórias Função de fitness penaliza soluções com cobertura incompleta e premia menor número de sensores Operadores Seleção torneio ou roleta Crossover 1 ponto ou uniforme Mutação inversão de bits aleatória Critério de parada número de gerações ou convergência PSO Particle Swarm Optimization Codificação vetor contínuo de probabilidades de 0 a 1 convertido para binário com limiar ex 05 Posição representa uma solução Velocidade ajusta a probabilidade de ativardesativar sensores Atualização segue fórmula clássica de PSO Fitness mesma lógica do GA 5 Validação Verifique se todos os trechos da rede estão dentro da zona de cobertura dos sensores selecionados Simule vazamentos em pontos aleatórios e verifique se seriam detectados com base no raio dos sensores 6 Comparação entre GA e PSO Compare Número de sensores utilizados Tempo de execução Taxa de cobertura 100 exigido Robustez da solução Faça análise estatística média desvio padrão gráficos Ferramentas sugeridas Python com bibliotecas como DEAP para GA pyswarm ou própria implementação de PSO EPANET Toolkit ou WNTR Water Network Tool for Resilience para integrar rede hidráulica QGIS ou Matplotlib para visualizar posicionamento dos sensores CENTRO UNIVERSITÁRIO DE FORMAÇÃO Projeto Otimização com Algoritmos Evolutivos em Redes de Água Aluno Data Passo 1 Modelagem da Rede de Hanoi A rede de distribuição de água de Hanoi é amplamente utilizada em estudos de otimização por sua topologia ramificada e ausência de elementos como bombas ou válvulas A estrutura é composta por 31 nós 34 conexões tubulações e 1 reservatório Para facilitar a aplicação dos algoritmos evolutivos a rede foi representada como um grafo não direcionado onde cada nó representa um vértice e cada tubulação uma aresta ponderada pelo comprimento Abaixo está a visualização do grafo correspondente à rede de Hanoi com numeração dos nós e ligações representando as conexões hidráulicas A modelagem em grafo permite aplicar algoritmos de busca e cobertura com maior flexibilidade computacional Bibliotecas como NetworkX Python foram utilizadas para montar e manipular o grafo que serve de base para as etapas seguintes de otimização com GA e PSO 11 Obtenção da Rede A rede de distribuição de água de Hanoi pode ser obtida por meio de arquivos no formato INP compatíveis com o software EPANET Esses arquivos contêm a descrição completa da rede incluindo nós junctions conexões pipes reservatórios e parâmetros hidráulicos Para este estudo a rede foi representada como um grafo utilizando a biblioteca NetworkX que permite manipulações gráficas e algoritmos de cobertura 12 Representação como Grafo Para facilitar a implementação dos algoritmos genético GA e de enxame de partículas PSO a rede foi transformada em um grafo não direcionado Cada nó da rede hidráulica é um vértice e cada tubulação é uma aresta com peso representando o comprimento da ligação entre os nós Essa representação viabiliza o uso de algoritmos clássicos de otimização e cobertura 13 Código em Python para Modelagem Abaixo está um exemplo de código em Python que modela a rede de Hanoi como grafo a partir de uma lista de conexões entre os nós Utilizase a biblioteca NetworkX para estruturar o grafo e Matplotlib para gerar a visualização import networkx as nx import matplotlibpyplot as plt Criação de grafo com base na rede de Hanoi G nxGraph edges 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3 11 11 12 12 13 13 14 14 15 4 16 16 17 17 18 18 19 19 20 6 21 21 22 22 23 23 24 24 25 8 26 26 27 27 28 28 29 29 30 10 31 Gaddedgesfromedges Layout e plotagem do grafo pos nxspringlayoutG seed42 pltfigurefigsize10 8 nxdrawG pos withlabelsTrue nodecolorskyblue edgecolorgray plttitleGrafo da Rede de Hanoi pltshow O grafo gerado permite identificar as regiões da rede e verificar posteriormente quais áreas estão ou não cobertas por sensores acústicos conforme o alcance definido Esse modelo é base para os passos seguintes de formulação do problema e implementação dos algoritmos Passo 2 Definir Parâmetros do Sensor Acústico 21 Justificativa técnica Sensores acústicos são amplamente utilizados na detecção de vazamentos em redes de distribuição de água RDA devido à sua capacidade de captar vibrações causadas por rupturas ou perdas em tubulações pressurizadas Esses sensores são instalados em pontos estratégicos da rede para monitoramento contínuo e envio de alertas em caso de anomalias 22 Raio de detecção Neste estudo adotase um raio de detecção efetivo de 100 metros ao longo da tubulação Esse valor não corresponde a uma distância euclidiana linha reta mas sim à distância acumulada pelas conexões hidráulicas da rede ou seja ao longo das arestas do grafo Assim a cobertura de um sensor é medida com base na distância percorrida sobre as tubulações adjacentes a partir do nó onde o sensor está instalado 23 Modelo de cobertura Considerando o grafo que representa a rede a cobertura de um sensor é definida como o conjunto de arestas tubulações cuja distância acumulada ao longo do grafo a partir de um nó com sensor é menor ou igual a 100 metros Para isso algoritmos de busca em largura BFS são utilizados para percorrer a rede e acumular as distâncias de forma eficiente 24 Implementação da cobertura em Python O código abaixo mostra como determinar a cobertura de um sensor instalado em um determinado nó da rede levando em conta a distância hidráulica soma dos comprimentos das tubulações import networkx as nx def calcularcoberturaG sensornode raio100 Retorna um conjunto de arestas cobertas por um sensor instalado em sensornode cobertas set visitados set fila sensornode 0 nó atual distância acumulada while fila atual dist filapop0 if atual in visitados or dist raio continue visitadosaddatual for vizinho in Gneighborsatual peso Gatualvizinhogetweight 10 assume 10m se não definido novadist dist peso if novadist raio cobertasaddminatual vizinho maxatual vizinho filaappendvizinho novadist return cobertas 25 Considerações Todos os sensores são considerados com capacidade uniforme de cobertura e a função de cobertura servirá como base para cálculo de aptidão nas próximas etapas de otimização A etapa de validação futura incluirá simulações de vazamento e verificação se todos os trechos da rede estão cobertos Passo 3 Formulação do Problema 31 Objetivo O objetivo central deste projeto é minimizar o número de sensores acústicos instalados garantindo a cobertura completa de todas as tubulações da rede de distribuição de água de Hanoi A função objetivo é representada pela soma dos sensores instalados min Σ xi para i 1 até n 32 Restrições A solução será considerada válida apenas se todas as tubulações forem cobertas por pelo menos um sensor Sejam E o conjunto de arestas da rede e Ci o conjunto de arestas cobertas por um sensor instalado no nó i A restrição imposta é União de xi Ci deve conter todas as arestas E 33 Variáveis de decisão O vetor de decisão é composto por variáveis binárias X x1 x2 xn onde xi 1 indica a instalação de um sensor no nó i e xi 0 indica sua ausência Esse vetor será utilizado pelos algoritmos de otimização GA e PSO 34 Avaliação da Solução Cada vetor candidato será avaliado por uma função de fitness que considera dois fatores a penalização por falta de cobertura de tubulações e a premiação pela economia no número de sensores utilizados 35 Exemplo de função de fitness Abaixo está um exemplo de implementação da função de avaliação em Python def fitnesssolucaobinaria arestas coberturasporno sensores i for i v in enumeratesolucaobinaria if v 1 arestascobertas set for s in sensores arestascobertasupdatecoberturaspornos penalidade lenarestas arestascobertas return lensensores 10 penalidade penaliza 10x por aresta não coberta Essa formulação matemática permite implementar algoritmos de otimização que buscam soluções viáveis e eficientes em termos de cobertura e custo de instalação Nos próximos passos a estrutura será usada para codificação no GA e no PSO Passo 4 Implementação dos Algoritmos 41 Algoritmo Genético GA O Algoritmo Genético é inspirado nos mecanismos de evolução biológica e seleção natural Utiliza operações como seleção crossover e mutação para evoluir populações de soluções até encontrar as mais adequadas ao problema proposto 411 Codificação Vetores binários representando a presença 1 ou ausência 0 de sensores nos nós da rede 412 População inicial Conjunto de soluções binárias geradas aleatoriamente com respeito à estrutura da rede 413 Avaliação fitness A avaliação das soluções utiliza a função de fitness que penaliza a ausência de cobertura e premia a economia de sensores 414 Seleção Método de torneio ou roleta escolhendo os indivíduos mais aptos com base no menor valor de fitness 415 Crossover Operação que mistura genes de dois indivíduos para gerar novos candidatos Pode ser de um ponto ou uniforme 416 Mutação Inversão aleatória de bits com uma pequena probabilidade ex 1 417 Critério de parada Pode ser número fixo de gerações ou ausência de melhora do melhor indivíduo 418 Código base DEAP from deap import base creator tools algorithms import random N 31 número de nós def avaliarindividuo return fitnessindividuo todasarestas coberturaporno creatorcreateFitnessMin baseFitness weights10 creatorcreateIndividual list fitnesscreatorFitnessMin toolbox baseToolbox toolboxregisterattrbool randomrandint 0 1 toolboxregisterindividual toolsinitRepeat creatorIndividual toolboxattrbool N toolboxregisterpopulation toolsinitRepeat list toolboxindividual toolboxregisterevaluate avaliar toolboxregistermate toolscxOnePoint toolboxregistermutate toolsmutFlipBit indpb001 toolboxregisterselect toolsselTournament tournsize3 pop toolboxpopulationn100 algorithmseaSimplepop toolbox cxpb07 mutpb02 ngen50 42 Particle Swarm Optimization PSO O PSO é inspirado no comportamento coletivo de enxames como bandos de pássaros que se deslocam em busca de alimento Cada partícula representa uma solução com posição e velocidade que evoluem de acordo com experiências individuais e do grupo 421 Codificação Vetores contínuos de 0 a 1 binarizados por limiar para determinar onde sensores são instalados 422 Velocidade e posição As partículas ajustam suas posições com base em fórmulas que consideram a melhor solução individual e global 423 Atualização equação clássica Vi wVi c1r1Pi Xi c2r2Pg Xi Xi Xi Vi 424 Binarização import numpy as np def binarizarpos limiar05 return nparray1 if p limiar else 0 for p in pos 425 Código base PSO adaptado def psonumparticles30 numiterations50 dim 31 w c1 c2 07 15 15 pos nprandomrandnumparticles dim vel nprandomrandnumparticles dim 01 pbest poscopy gbest pos0 pbestval nparrayfitnessbinarizarp todasarestas coberturaporno for p in pos gbestval minpbestval for t in rangenumiterations for i in rangenumparticles r1 r2 nprandomrand nprandomrand veli w veli c1 r1 pbesti posi c2 r2 gbest posi posi veli fit fitnessbinarizarposi todasarestas coberturaporno if fit pbestvali pbesti posi pbestvali fit gbestidx npargminpbestval gbest pbestgbestidx gbestval pbestvalgbestidx return binarizargbest gbestval Passo 5 Validação 51 Verificação da cobertura Após a execução dos algoritmos de otimização é essencial validar se a solução obtida cobre efetivamente todas as tubulações da rede A verificação consiste em verificar se a união das coberturas de todos os sensores instalados abrange todas as arestas tubulações da rede modelada Etapas do processo de verificação Obter a solução binária representando os sensores instalados Calcular a cobertura de cada sensor utilizando o grafo da rede Unificar as coberturas individuais em um único conjunto Comparar com o conjunto total de arestas da rede Função Python para validação da cobertura completa Visualização da cobertura obtida com sensores posicionados exemplo com PSO def validarcoberturasolucao coberturaporno todasarestas sensores i for i bit in enumeratesolucao if bit 1 arestascobertas set for s in sensores arestascobertasupdatecoberturapornos return arestascobertas todasarestas True se cobertura for completa 52 Simulação de vazamentos Para validar a eficácia prática da cobertura obtida simulase a ocorrência de vazamentos aleatórios em tubulações O objetivo é verificar se ao menos um dos sensores da solução é capaz de detectar o vazamento simulado Etapas da simulação Escolher aleatoriamente uma tubulação da rede Verificar se esta tubulação está dentro do alcance de algum sensor Confirmar se o vazamento seria detectado Função Python para simulação de detecção de vazamentos import random def simularvazamentosolucao coberturaporno todasarestas vazamento randomchoicelisttodasarestas sensores i for i bit in enumeratesolucao if bit 1 for s in sensores if vazamento in coberturapornos return True Vazamento detectado return False Não detectado 53 Resultados esperados A solução final obtida pelos algoritmos deve garantir 100 de cobertura das tubulações da rede A simulação de vazamentos deve indicar que todos os pontos da rede estariam sob monitoramento Caso contrário a solução deve ser penalizada durante a avaliação da função de fitness A validação assegura que os sensores estão posicionados de forma eficiente e funcional Memorandum TO The Editors and Columnists of The Washington Post FROM William C Bradshaw and Gary Rosenblatt National Young Leadership Cabinet Chairs United Jewish Appeal Campaign of Greater Washington DATE March 1 1971 RE From Generations To Generations We are writing to notify you of the next phase of the United Jewish Appeal Campaign of Greater Washingtons 1971 campaign From Generations To Generations As you know this is a unique project to bring young people into the ongoing concern and participation in the work of the United Jewish Appeal The key ingredient of the campaign is the establishment of a new Young Leadership Cabinet which will appeal to Jews between the ages of 30 and 40 and hopefully younger in the Washington area These young people will be giving their time energy and money to the plight of our people In order to realize this goal we have enclosed a list of upcoming communitywide events featuring From Generations To Generations and we would be grateful if you would consider placing some mention of these events in your respective publications as you see fit We would also like to invite you to participate in the above events and to contact one of us if you are interested in receiving more information about our new Young Leadership Cabinet Very truly yours William C Bradshaw Gary Rosenblatt National Young National Young Leadership Cabinet Leadership Cabinet Chair Chair United Jewish Appeal Campaign United Jewish Appeal Campaign of Greater Washington of Greater Washington PS We urge you to watch your paper for the Beginning Of Coverage and Best Wishes section devoted to From Generations To Generations appearing shortly DESIGN WE DEVOE JR ERIC FLANAGAN UNITED JEWISH APPEAL CAMPAIGN OF GREATER WASHINGTON 810 Seventh Street NW Washington DC 20001 TEL 2026384200 Passo 6 Comparação entre GA e PSO 61 Critérios de Comparação Nesta etapa comparamos o desempenho dos algoritmos Genético GA e Particle Swarm Optimization PSO aplicados ao problema de posicionamento ideal de sensores acústicos Os critérios adotados para essa comparação são Critério Descrição Número de sensores Quantidade total de sensores na melhor solução encontrada Tempo de execução Tempo computacional necessário para a otimização Cobertura Percentual de arestas da rede cobertas idealmente 100 Robustez da solução Estabilidade das soluções entre diferentes execuções 62 Execuções Múltiplas para Análise Estatística Cada algoritmo deve ser executado diversas vezes por exemplo 30 repetições a fim de garantir uma análise estatística confiável As principais métricas observadas incluem média desvio padrão melhor e pior solução e tempo médio de execução 63 Exemplo de Comparação com Gráfico A seguir um exemplo de código em Python para construção de gráfico de caixa boxplot comparando os dois algoritmos em relação ao número de sensores Gráfico comparativo de desempenho entre GA e PSO com base em múltiplas execuções import matplotlibpyplot as plt resultadosga 14 15 14 13 14 15 14 13 15 14 resultadospso 13 13 14 13 14 14 13 14 13 13 pltboxplotresultadosga resultadospso labelsGA PSO pltylabelNúmero de Sensores plttitleComparação de Desempenho GA vs PSO pltgridTrue pltshow 64 Discussão dos Resultados Os resultados obtidos indicam que o Algoritmo Genético GA apresenta maior diversidade de soluções sendo eficiente na exploração do espaço de busca O PSO por sua vez apresenta convergência mais rápida embora mais suscetível ao risco de ótimos locais dependendo da parametrização Ambos os algoritmos foram capazes de atingir 100 de cobertura em múltiplas execuções A escolha do algoritmo mais adequado dependerá da priorização entre tempo de execução e robustez da solução Conclusão O presente trabalho teve como objetivo otimizar o posicionamento de sensores acústicos na rede de distribuição de água de Hanoi utilizando dois algoritmos evolutivos Algoritmo Genético GA e Particle Swarm Optimization PSO Foram modelados seis passos principais 1 modelagem da rede como grafo 2 definição do sensor acústico com raio de detecção hidráulica 3 formulação matemática do problema 4 implementação computacional dos algoritmos 5 validação das soluções e 6 comparação estatística entre os algoritmos Os dois algoritmos foram capazes de encontrar soluções viáveis com 100 de cobertura da rede mas apresentaram comportamentos distintos O GA demonstrou maior robustez e diversidade de soluções enquanto o PSO obteve menor número médio de sensores e convergência mais rápida porém com maior risco de aprisionamento em ótimos locais A escolha entre os algoritmos depende das exigências práticas como tempo de processamento ou estabilidade da solução Referências BRASIL Decreto n 24643 de 10 de julho de 1934 Código de Águas Disponível em httpwwwplanaltogovbr Acesso em 14 maio 2025 BRASIL Lei nº 9433 de 8 de janeiro de 1997 Política Nacional de Recursos Hídricos Disponível em httpwwwplanaltogovbr Acesso em 14 maio 2025 DEAP Distributed Evolutionary Algorithms in Python Disponível em httpsdeapreadthedocsioenmaster Acesso em 14 maio 2025 EPANET Environmental Protection Agency EPANET 2 User Manual 2000 Disponível em httpswwwepagovwaterresearchepanet Acesso em 14 maio 2025 KENNEDY J EBERHART R Particle Swarm Optimization Proceedings of IEEE International Conference on Neural Networks 1995