ALGORITMOS GENÉTICOS NO POSICIONAMENTO DE
TRANSFORMADORES DE POTÊNCIA EM PROPRIEDADES RURAIS
Elvio Prado da Silva, José Roberto Camacho
[email protected], [email protected]
Universidade Federal de Uberlândia, Faculdade de Engenharia Elétrica, Núcleo de Eletricidade Rural e
Fontes Alternativas de Energia, Uberlândia – MG
Resumo - Este presente artigo explora os Algoritmos
Genéticos para a obtenção do melhor lugar para a
localização de um transformador em uma propriedade
rural. O software apresenta um novo algoritmo para a
sequência de cruzamentos, onde um pai dominante cruza
com as melhores mães (n melhores mães), sendo este
dominante o pai de todos os filhos, ou seja, o pai dominante
passa material genético para todos os filhos. Uma interface
gráfica amigável e dinâmica foi desenvolvida onde o
usuário pode escolher entre várias cargas diferentes em
uma propriedade rural (casas, currais, ordenhas, irrigação,
etc...), e o Algoritmo Genético irá levar o transformador
(dinamicamente) em cada geração para o melhor ponto
determinado por esta geração.
Palavras-Chave - Algoritmos Genéticos, cromossomos,
cruzamento, mutação, transformadores de potência,
propriedade rural.
GENETICS ALGORITHMS FOR THE
POSITIONING POWER TRANSFORMERS
IN RURAL PROPERTIES
Abstract - This present article explores the Genetic
Algorithms for the attainment of optimum place for the
localization of transformers in a rural property. This
software presents a new algorithm for the sequence of
crossings, where a dominant father crosses with the best
mothers (n better mothers), being this dominant o father of
all the children, that is, the dominant father passes genetic
material for all the children. A friendly and dynamic
graphical interface was developed where the user can
choose enters some different loads in a country property
(houses, corrals, you milk, irrigation, etc…), and the
Genetic Algorithm will go to take the transforming one
(dynamically) in each generation for optimum point
determined for this generation.
1
Keywords - Genetic algorithms, chromosomes,
crossing, mutation, power transformers, rural property.
T
T
I. INTRODUÇÃO
Algoritmos Genéticos, foram criados para revolucionar a
busca de respostas em sistemas computacionais cujas
Nota de rodapé na página inicial será utilizada apenas pelo professor
avaliador para indicar o andamento do processo de revisão. Não suprima
esta nota de rodapé quando editar seu artigo.
possibilidades de soluções são muito grandes (da ordem de
n!).
Um Algoritmo Genético faz a comparação do plano
complexo, ao mundo animal, onde se verifica o cruzamento,
mutação, reprodução e seleção, de forma a criar uma vida
artificial perante os números, simulando a realidade e
encontrando respostas através da convergência dos genes e
seleção do mais apto.
Neste presente projeto, os Algoritmos Genéticos foram
implementados para conseguir a melhor localização para um
transformador em uma propriedade rural. A distribuição de
cargas é feita, tais como:
• Casas;
• Currais;
• Escritórios;
• Sistemas de Irrigação;
• Oficinas;
• Ordenhas Mecânicas;
• Tanques de Piscicultura;
• Trituradores para preparação de ração;
• Galinheiros (Granjas);
• etc,...
Em um sistema determinístico, teríamos que calcular
todas as possibilidades e escolher a melhor. No caso de
Algoritmos Genéticos, uma possibilidade boa e confiável é
conseguida de forma inteligente, imitando a natureza.
II. ESTADO DA ARTE
A população sujeita a esta vida artificial, segue os
Algoritmos Genéticos, que operam com a codificação dos
indivíduos que constituem a população.
A pesquisa feita pelos Algoritmos Genéticos é global,
através de uma função objetivo (fitness), operando na
população utilizando técnicas modeladas pela genética
biológica, onde sobrevivem os melhores indivíduos da
população.
As
gerações
desenvolvem-se
por
processos
probabilísticos. A figura 1, mostra um diagrama de fluxo de
dados exemplificando o algoritomo.
Começa pela geração aleatória de uma população, onde
depois de selecionados os melhores indivíduos, ficam
sujeitos ao cruzamento e à alteração de determinadas
características (mutação).
O processo repete-se até ser alcançado o objetivo
pretendido. Cada indivíduo é identificado por um
cromossomo, que representa uma posição no plano.
Algumas palavras chave no contexto dos Algoritmos
Genéticos:
• cromossomo;
• codificação;
• seleção;
• cruzamento (crossing-over);
• mutação;
• mérito (fitness);
• aprendizagem;
• elitismo.
IV. ANALISANDO A TÉCNICA
Foi criado para cada carregamento (casa, curral, etc...)
uma matriz (ex: int PosCasa[20][4]) contendo em suas
colunas:
• Coluna 0: a posição x;
• Coluna 1: a posição y;
• Coluna 2: índice indicando a quantidade de
elementos iguais deste mesmo carregamento;
• Coluna 3: Distância deste ponto até o
Transformador;
• Linhas : 20 linhas para indicar que poderemos ter
até 20 carregamentos iguais (ex: 20 trituradores);
Para a implementação genética, foi criado uma matriz de
cromossomos (int Cromossomo[MAX][3]) contendo:
• Coluna 0: Posição x do transformador;
• Coluna 1: Posição y do transformador;
• Coluna 2: Somatória de todas as distâncias até o
transformador;
• Linhas : A quantidade de linhas são dadas pelo
máximo número de indivíduos;
V. POPULAÇÃO INICIAL (CROMOSSOMOS)
Com uma função randômica criamos uma população
inicial de MAX aleatoriamente (É aleatória, mas quando
possível, o conhecimento da aplicação pode ser utilizado
para definir a população inicial). É criado então os
cromossomos x do transformador aleatório e y do
transformador aleatório.
Uma rotina inteligente, verifica se o ponto existe na área
de trabalho para poder garantir a criação de somente
cromossomos válidos.
VI. COMO CALCULAR O NÚMERO DE INDIVÍDUOS
(MAX)
Fig. 1. Diagrama de fluxo de dados do Algoritmo Genético
Como base para a criação dos cromossomos e para
definir esta nova técnica de seções de cruzamento, devemos
seguir a equação 1 para calcular MAX:
MAX = 2(n-1) + n
(1)
III. ALGORITMO GENÉTICO IMPLEMENTADO
O porque da equação 1 será explicado na seção VII.
Foi utilizado neste trabalho, um novo Algoritmo Genético
que pode ser entendido como:
• Gerar a população inicial (aleatória).
• Avaliar cada indivíduo da população (os mais aptos
foram colocados em ordem crecente de aptidão).
• Enquanto critério de parada não for satisfeito faça:
1. Selecionar os indivíduos mais aptos;
2. Criar novos indivíduos aplicando os
operadores crossover e mutação;
3. Substituir os piores indivíduos da
população pelos novos indivíduos gerados
(filhos);
4. Avaliar cada cromossomo da nova
população.
VII. TÉCNICA DE CRUZAMENTO
Esta técnica de Algoritmo Genético, utiliza um processo
de Elitismo forçado, colocando todos os indivíduos em
ordem crescente de aptidão. Em nosso caso, os mais aptos
são aqueles que a somatória de distâncias até o transformador
é a menor.
Após os indivíduos serem colocados em ordem
crescente, lembrando que o número de indivíduos foi dado
pela equação 1, e o procedimento de cruzamento é feito
cruzando o primeiro indivíduo(mais apto) com os outros
seguintes, conforme exemplo a seguir:
• cruzamento: cruzar x com x e y com y;
• Sabemos que MAX = 2(n-1)+n;
•
•
•
Cruzar o melhor com cada um dos n primeiros e
pegar os filhos criados e substituir pelos ultimos
da lista;
exemplo: para MAX = 7 indivíduos :
MAX = 2 (n-1)+n, logo n = 3;
pegar os 3 primeiros e cruzar o primeiro com o
segundo e o primeiro com o terceiro. Logo
teremos 4 filhos, que dá 3 + 4 = 7. Pegar os 4
filhos criados e substituir pelos 4 ultimos
indivíduos da população.
Pode-se observar que o mais apto cruza com os mas
aptos subsequentes a ele, e que este primeiro individuo é pai
de todos os filhos (pai dominante), com mães diferentes.
Veja a figura 2 :
convertemos o x e o y de cada indivíduo do Cromossomo
para binário para os cruzamentos.
Para o cruzamento: cruzar x com x e y com y.
O crossover é aplicado com uma dada probabilidade
denominada taxa de crossover (60\% a 90\%).
IX. MUTAÇÃO
A mutação é um mecanismo que ocorre com rara
freqüência genética. Podemos simular uma mutação,
invertendo os valores dos bits.
A mutação é aplicada com dada probabilidade,
denominada taxa de mutação (aproximadamente 1%), em
cada um dos bits do cromossomo.
Para a mutação, invertemos o bit selecionado, ou seja, se
o bit for “0” passa a ser “1” e vice versa.
A taxa de mutação não deve ser nem alta nem baixa, mas
o suficiente para assegurar a diversidade de cromossomos na
população. Veja a figura 4.
Fig. 4. Representação de uma mutação.
X. CROSSOVER MAIS MUTAÇÃO
Fig. 2. Representação da técnica de cruzamento proposta neste
artigo, verificando que o mais apto é pai (pai dominante) de todos
os filhos, com mães diferentes
O mecanismo completo de crossover(cruzamento) mais
mutação é demonstrado na figura 5.
VIII. CRUZAMENTO (CROSSOVER)
Para tal, temos o processo do crossover, onde
escolhemos aleatoriamete um ponto de corte no cromossomo,
como mostra a figura 3 onde os pais trocam material
genético.
Fig. 5. . Representação do processo completo, crossover mais
mutação
XI. PRÓXIMAS GERAÇÕES
Para as próximas gerações, repetiremos todo o processo
de seleção (ordem crescente de aptidão para definir o pai
dominante), cruzamento e mutação a fim de que cada
geração subseqüente seja melhor que a anterior.
Logo, a cada geração observaremos uma convergência
dos indivíduos, sendo seus filhos cada vez mais aptos para a
solução do problema.
Fig. 3. Representação de um crossover
Se o crossover é aplicado os pais trocam suas caldas
gerando dois filhos, caso contrário os dois filhos serão cópias
exatas dos pais. Isso é obtido convertendo os indivíduos a
serem cruzados, de real para binário. Neste caso,
XII. INTERFACE DO SOFTWARE
A interface principal do software para determinação da
melhor localização para transformadores em propriedades
rurais é dada pela figura 6.
Fig. 6. Interface principal do software
Afim de verificar a validade do algoritmo, foi feito um
teste com quatro indivíduos, igualmente espaçados nos
vértices de um quadrado. Logo, o transformador deve ficar
no centro, conforme figuras 7, 8 e 9.
Fig. 7. Quatro indivíduos igualmente espaçados no vértice de
um quadrado.
Fig. 9. Quatro indivíduos igualmente espaçados no vértice de
um quadrado.
XIII. CONCLUSÕES
Concluímos que o objetivo foi atingido em relação ao
posicionamento ótimo do transformador em uma propriedade
rural contendo várias cargas sendo posicionadas de diversas
formas possíveis, conforme o desejo do usuário do software.
Uma nova técnica de cruzamento foi apresentada, tendo
uma eficiência notável, pois conseguiu-se o ponto ótimo da
configuração da figura 6 em apenas 5 gerações, com
população de 58 indivíduos, logo, pela equação 1, temos n
igual a 20 cruzamentos e 38 filhos gerados, todos contendo
material genético do pai dominante.
O mecanismo de ordenamento em ordem crescente,
impõe elitismo ao pai dominante, e por conseguinte
cruzamento deste pai com as mães que estão na seqüência do
ordenamento, impõe cruzamento do melhor pai com as
melhores mães, conforme observado na natureza (entre os
leões por exemplo).
Pudemos observar que os algoritmos genéticos são uma
ferramenta muito importante na resolução de problemas,
onde podemos alcançar resultados cada vez mais prováveis e
melhores para um determinado problema.
Este tipo de algoritmo nos devolve a provável resposta,
ou seja a resposta mais próxima da ideal. Portanto é
importante salientar que este processo não é determinístico, e
sim probabilístico, onde o resultado é satisfatório, mas
dificilmente será exato.
AGRADECIMENTOS
Agradeço ao professor Keiji Yamanaka por oferecer a
disciplina Algoritmos Genéticos na pós-graduação da
Faculdade de Engenharia Elétrica, pois a disciplina foi base
para o desenvolvimento deste projeto.
Fig. 8. Quatro indivíduos igualmente espaçados no vértice de
um quadrado.
REFERÊNCIAS BIBLIOGRÁFICAS
[1] Rica rdo Linden, Algoritmos Genéticos, 1ed, Brasport
ISBN 8574522651, 2006
[2] Herbert Childt, C++Builder Referência Completa, 2ed,
Campus 2004
[3] Therbio de Lima, site DicasBCB
http://www.dicasbcb.com.br, acessado
dezembro de 2007.
C++Builder,
em 1 de
DADOS BIOGRÁFICOS
Elvio Prado da Silva , possui graduação em Engenharia
Elétrica pela Universidade Federal de Uberlândia (2006).
Atualmente é aluno regular de Doutorado do programa de
pós-graduação da Faculdade de Engenharia Elétrica da
Universidade Federal de Uberlândia. Tem experiência na
área de Engenharia Elétrica, atuando principalmente nos
seguintes temas: análise e diagnóstico, eletrônica,
supervisórios, engenharia de computação (software e
hardware), algoritmos genéticos, transformadores de força e
distribuição.
U
U
Jose Roberto Camacho , concluiu o doutorado em
Engenharia Elétrica University of Canterbury Nova Zelândia
em 1993. Atualmente é professor titular da Universidade
U
U
Federal de Uberlândia. Membro Senior do IEEE Institute of
Electrical and Electronic Engineers. Publicou 8 artigos em
periódicos especializados e 50 trabalhos em anais de eventos.
Possui 2 capítulos de livros publicados. Possui 1 produto
tecnológico registrado, 3 softwares sem registro de patente, 1
processo ou técnica registrado e outros 4 itens de produção
técnica. Publicou 10 artigos em jornais. Participou de 21
eventos no exterior e 11 no Brasil. Orientou 8 dissertações de
mestrado e 3 teses de doutorado na área de Engenharia
Elétrica. No momento orienta 4 doutorandos e 2 mestrandos.
Recebeu 3 prêmios e/ou homenagem. Atua na área de
Engenharia Elétrica, com ênfase em Máquinas Elétricas,
Dispositivos de Potência, Geração Distribuída, Energia
Alternativa e Energia para o meio rural. Em suas atividades
profissionais interagiu com 50 colaboradores em co-autorias
de trabalhos científicos. Em seu currículo Lattes os termos
mais freqüentes na contextualização da produção científica,
tecnológica e artístico-cultural são: motor de indução, motor
linear, monofásico, bifásico, motor assíncrono, gerador de
indução, assimetria magnética, chaveamento de capacitores,
Conexão Unitária e controle de velocidade.