IDENTIFICAÇÃO DE SISTEMAS NÃO LINEARES – UTILIZAÇÃO DE ALGORITMOS GENÉTICOS PARA SELEÇÃO DE ESTRUTURA POLI NOMIAL

Morais, J. S., Morais, A. S., Vincenzi, F. R. S., Yamanaka, K., Vieira Junior, J. B.. Núcleo de Controle e Automação (NCA) e Núcleo de Pesquisa em Eletrônica de Potência (NUPEP)

Faculdade de Engenharia Elétrica (FEELT) Universidade Federal de Uberlândia (UFU)

Av. João Naves de Ávila, 2160 - Bloco 3N - Campus Santa Mônica - CEP: 38.400-902 Uberlândia, MG, Brasil.

e-mail: josuemorais@gmail.com

Resumo - Este artigo apresenta um aplicativo que utiliza de algoritmos genéticos para obter o modelo discreto de circuitos elétricos, dispondo dos seguintes métodos de seleção: Rank, Roleta ou Torneio, ficando a critério do usuário esta escolha. Aplica-se também na seleção a técnica do elitismo. Os resultados desta implementação são apresentados em um aplicativo feito em QT, que é um pacote de programação gráfica em c++.

Palavras-Chave - Algoritmos Genéticos, Rank, Roleta, Torneio, Elitismo, QT, Modelo ARX, Modelo ARMAX.

IDENTIFICATION OF NONLINEAR

SYSTEMS - USE OF GENETIC ALGORITHMS FOR SELECTION OF

STRUCTURE POLYNOMIAL Abstract – This paper presents an application that uses

genetic algorithms for the discrete model electrical circuits, providing the following selection methods: rank, roulette or tournament, being at the user's choice. It also applies the technique in the selection of elitism. The results of this implementation are presented in an application made in QT, which is a package of graphics programming in c + +.

1 Keywords - Genetic Algorithms, Rank, Roulette,

Tournament, Elitism, QT, ARX Model, ARMAX Model.

I. INTRODUÇÃO

Com a era digital muitas mudanças ocorreram, entre elas a introdução de microprocessadores para o controle de circuitos de potência [2].

Dependendo da frequência de operação e da taxa de amostragem, estes conversores geram como resultado uma enorme quantidade de dados, e com eles surgem questões como: o que fazer com os pontos adquiridos, o que os dados dizem a respeito do acompanhamento e controle dos circuitos? Caso estes dados sejam gravados, devem ser

descartados? É possível extrair outras informações a partir desses dados? É possível utilizar estes dados em análises futuras, como a análise da qualidade do sinal de saída, ou na eficiência do conversor?

A fim de usar esses dados brutos, é importante que eles sejam representados de maneira adequada, e que o modelo construído com base nesses dados seja avaliado e validado. Uma das maneiras de alcançar essa meta é usar o processo chamado KDD – Knowledge Discovery in Databases [1] e [2].

Entre as pesquisas que utilizam KDD estão os sistemas de produção, a detecção de falhas, a qualidade do processo, a manutenção de equipamentos, entre outros [6].

Por outro lado mesmo com a atual capacidade de processamento, alguns problemas computacionais ainda aguardam pelas próximas fases evolutivas do hardware para o surgimento de soluções práticas viáveis.

A Computação Evolutiva, em especial os Algoritmos Genéticos (AG’s), apresentam-se cada vez mais como uma boa alternativa para estas soluções.

A identificação de circuitos elétricos através de modelagem se faz necessário para utilização de simulações em aplicativos matemáticos e ou validação de técnicas de controle. Em outros casos este modelo necessita ser implementado em microcontroladores, com baixo custo computacional, daí se faz necessário à obtenção de equações simples sem a necessidade que estas descrevam a física do processo.

O objetivo deste trabalho é propor e verificar a possibilidade de aplicar o uso de KDD e Algoritmos Genéticos como ferramenta de extração de conhecimentos, gerando assim no final um modelo polinomial, de forma que ele possa ser empregado nas previsões do comportamento do elemento a ser estudado, prevendo como o mesmo pode se comportar.

II. O PROCESSO DE KDD

Na descoberta de conhecimentos em bases de dados, o KDD consiste na identificação de padrões válidos, novos, potencialmente úteis e compreensíveis em um repositório de dados [1].

Uma das características do KDD é a sua forma funcional. O KDD é baseado em técnicas conhecidas como aprendizagem de máquina, reconhecimento de padrões e estatística clássica para descobrir padrões nas análises. Outras técnicas a serem consideradas são os de visualização

de dados que estimulam a percepção e a inteligência humana, proporcionando uma compreensão refinada para compreender e associar os novos padrões [8].

Muitas vezes o termo KDD pode ser confundido com a mineração de dados, mas o termo de mineração de dados é considerado como um dos passos necessários ao processo de KDD, além de também pode ser considerado como uma parte essencial do processo. O KDD é considerado como um processo, um todo, enquanto a mineração de dados é considerada como uma etapa do KDD. Ou ainda, a mineração de dados está relacionada com a aplicação de algoritmos responsáveis para extrair padrões que são encaixados em dados [1].

A mineração de dados está associada à ideia de extrair conhecimento a partir de uma quantidade enorme de dados. É importante notar que o KDD pode ser executado independentemente da quantidade de dados disponíveis nas suas fases [7].

As fases do KDD são representadas como um conjunto de fases orientadas por atividades que são direcionadas para a extração e manejo dos dados, assim como a aplicação de técnicas de mineração de dados. No passado, a avaliação dos padrões de extração foi feita [9].

O processo de KDD está concentrado na relação de muitos autores, onde o sucesso dessas relações é diretamente dependente desta relação. Estes agentes são divididos em três classes, sendo o especialista do domínio responsável pelo conhecimento do domínio da aplicação; o analista de dados, que tem um papel importante porque é este o responsável pela execução do KDD, sendo um especialista nas etapas do processo. Por fim, tem-se o usuário final, que emprega o conhecimento extraído pelo processo de KDD para usá-lo na tomada de decisões [8].

A Figura 1 apresenta a representação das fases do processo de KDD:

Fig. 1 – O Processo de KDD - Knowledge Discovery in Databases.

O modelo de KDD é composto de nove etapas que são descritas abaixo, conforme [1]:

• Conhecimento do domínio: este conhecimento está relacionado à compreensão de uma forma muito abrangente da área de domínio da aplicação do KDD, dando prioridade aos objetivos do usuário;

• Seleção de dados: nesta etapa é feita a seleção de dados, que serão utilizados no processo de extração, que é a etapa em que as formas de acesso serão definidas com os dados dos registros utilizados;

• Pré-processamento: esta etapa é responsável pela limpeza, onde os dados inválidos ou irrelevantes no processo são descartados ou eliminados;

• Redução: a característica mais importante desta etapa é encontrar a interdependência entre os dados para obter uma redução na dimensão dos dados;

• Escolha das ferramentas de mineração de dados: nessa etapa é selecionada a ferramenta que será utilizada para fazer a mineração de dados;

• Escolha do algoritmo de mineração de dados: nesta etapa é feita a escolha do algoritmo de mineração de dados, entre eles o algoritmo genético, ferramentas estatísticas, etc.;

• Mineração de dados: considerada como a inteligência do processo de descoberta, nesta etapa os processos de análise de dados são iniciados para descobrir onde, através da mineração de dados, novos padrões serão encaixados em dados;

• A interpretação dos dados minados: quando os padrões são identificados, o analista deverá analisar e interpretar os dados que foram gerados pela mineração de dados;

• Resultados: os resultados obtidos ajudam na tomada de decisões ou até mesmo na geração de situações que serão necessárias para executar o processo de mineração de dados novamente.

III. IDENTIFICAÇÃO DE SISTEMAS

A Identificação de Sistemas é a área do conhecimento que estuda técnicas alternativas de modelagem matemática. Nela há a necessidade de desenvolver formas de se obter modelos matemáticos a partir de dados observados e não exclusivamente partindo-se das equações que descrevem a física do processo [6].

A identificação de um sistema segue uma série de passos de forma iterativa, até que se encontre um modelo adequado ao uso previsto. Os principais passos podem ser assim descritos [10]:

• Obtenção de dados de experimentação do sistema que se deseja modelar;

• Detecção de estrutura que será utilizada para representar o sistema;

• Estimação dos parâmetros do modelo;

• Validação do modelo obtido.

No caso de representações no contexto de sistemas lineares discretos pode-se citar os modelos ARX e ARMAX, e como representações não-lineares as Redes Neurais Artificiais [10].

Estrutura do Modelo ARX

A estrutura de auto-regressão pode ser modificada de forma a levar em consideração também as entradas do processo. Este modelo faz uso da auto-regressão (AR) e da variável exógena B.u(t), motivo pelo qual é conhecido como ARX.

. 1 ⋯ . . ut 1

⋯ b. . 01

O vetor de parâmetros (θ) para o modelo ARX pode ser determinado de acordo com a equação abaixo: … … . 02 Estrutura do Modelo ARMAX

O modelo anterior torna-se mais genérico considerando-se a equação de erro comportando-se como ruído branco, e assumindo-se sua média móvel para a determinação dos estados futuros. Desta forma, uma menor restrição à liberdade das propriedades dos distúrbios é conferida ao modelo, que recebe o nome de ARMAX devido à parte da média móvel (Moving Average) adicionada ao sistema ARX. Assim: . 1 ⋯ . . ut 1

⋯ b. . 1 ⋯ .

. 03

O vetor de parâmetros (θ) para o modelo ARMAX pode ser determinado de acordo com a equação abaixo:

… … …

IV. FUNDAMENTOS DE ALGORITMOS GENÉTICOS

Um algoritmo genético (AG) é uma técnica de busca utilizada na ciência da computação para achar soluções aproximadas em problemas de otimização e busca, fundamentado principalmente pelo americano John Henry Holland. Algoritmos genéticos é uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade, mutação, seleção natural e recombinação (ou crossing over).

Algoritmos genéticos são implementados como uma simulação de computador em que uma população de representações abstratas de solução é selecionada em busca de soluções melhores. A evolução geralmente se inicia a partir de um conjunto de soluções criado aleatoriamente e é realizada por meio de gerações. A cada geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são selecionados para a próxima geração, e recombinados ou mutados para formar uma nova população. A nova população então é utilizada como entrada para a próxima iteração do algoritmo.

Algoritmos genéticos diferem dos algoritmos tradicionais de otimização em basicamente quatro aspectos:

• Baseiam-se em uma codificação do conjunto das soluções possíveis, e não nos parâmetros da otimização em si;

• Os resultados são apresentados como uma população de soluções e não como uma solução única;

• Não necessitam de nenhum conhecimento derivado do problema, apenas de uma forma de avaliação do resultado;

• Usam transições probabilísticas e não regras determinísticas [1].

Os Algoritmos genéticos são em geral algoritmos simples e fáceis de serem implementados. Na Figura 2 temos um fluxograma de um programa básico.

Fig. 2. – Fluxograma de uma estrutura básica para algoritmos

genéticos.

A grande vantagem dos algoritmos genéticos esta no fato de não precisarmos saber como funciona o calculo de aptidão, apenas temos que tê-lo disponível para ser aplicado aos indivíduos e comparar os resultados.

O indivíduo é meramente um portador do seu código genético. O código genético é uma representação do espaço de busca do problema a ser resolvido, em geral na forma de sequências de bits. Por exemplo, para otimizações em problemas cujos valores de entrada são inteiros positivos de valor menor que 255 podemos usar 8 bits, com a representação binária normal, ou ainda uma forma de código gray. Problemas com múltiplas entradas podem combinar as entradas em uma única sequência de bits, ou trabalhar com mais de um "cromossomo", cada um representando uma das entradas. O código genético deve ser uma representação

capaz de representar todo o conjunto dos valores no espaço de busca, e precisa ter tamanho finito.

A seleção também é outra parte chave do algoritmo. Em geral, usa-se o algoritmo de seleção por "roleta", onde os indivíduos são ordenados de acordo com a aptidão e lhes são atribuídas probabilidades decrescentes de serem escolhidos. A escolha é feita então aleatoriamente de acordo com essas probabilidades. Dessa forma conseguimos escolher como pais os mais bem adaptados, sem deixar de lado a diversidade dos menos adaptados. Outra forma de seleção é o Torneio onde é selecionado aleatoriamente um grupo de “k” elementos e neste subgrupo de forma também aleatória é escolhido um elemento, e repete esta operação ate completar a população. Mas neste artigo vamos analisar o método Ranking onde ordenamos a população pela sua aptidão de forma decrescente num vetor e é gerado um número aleatório de zero ao tamanho da população. Os indivíduos sorteados serão selecionados. Isto será feito de forma a obter outra população de mesmo tamanho da anterior

A reprodução, tradicionalmente, é dividida em três etapas: acasalamento, recombinação e mutação. O acasalamento é a escolha de dois indivíduos para se reproduzirem (geralmente gerando dois descendentes para manter o tamanho populacional). A recombinação, ou crossing-over é um processo que imita o processo biológico homônimo na reprodução sexuada: os descendentes recebem em seu código genético parte do código genético do pai e parte do código da mãe. Esta recombinação garante que os melhores indivíduos sejam capazes de trocar entre si as informações que os levam a ser mais apto a sobreviver, e assim gerar descendentes ainda mais aptos. Por último vem as mutações, que são feitas com probabilidade a mais baixa possível, e tem como objetivo permitir maior variabilidade genética na população, impedindo que a busca fique estagnada em um mínimo local [2].

V. MATERIAIS E MÉTODOS

Esse trabalho foi dividido em duas etapas:

• Etapa de aquisição, compactação, filtragem e normalização dos dados (KDD). Nesta etapa os dados repetidos foram removidos, e todas as variáveis foram normalizadas para variarem de 0 a 1.

• Etapa Interpretação utilizando de Algoritmos genéticos para a obtenção de um Modelo ARMAX considerando um sistema SISO (uma entrada e uma saída).

Na etapa de interpretação é escolhida aleatoriamente a quantidade de termos que a equação terá, ou seja, o tamanho do meu cromossomo em se tratando do algoritmo genético. É escolhido também de forma aleatória o tamanho de combinação entre entradas com entradas e ou saídas que cada termo da equação terá. O algoritmo genético procura a melhor estrutura e utiliza do método dos mínimos quadrados para encontra os melhores coeficientes e o erro gerado. O cromossomo com o menor erro no final das iterações é a

solução desejada e esta quantidade de iterações é informada pelo operador.

Dai o aplicativo retorna com a estrutura e seus respectivos coeficientes.

Os testes foram efetuados em um aplicativo desenvolvido em QT e que dispõe de uma interface conforme Figura 3.

Fig. 3. – Tela principal do aplicativo desenvolvido.

No aplicativo devemos inserir as seguintes informações:

tamanho da população (N), fator da probabilidade para ocorrer cruzamento (PC), fator da probabilidade para ocorrer mutação (Pm), quantidade de indivíduos pertencentes ao elitismo (E), fator do torneio (K), se a seleção vai ser do tipo torneio ou roleta ou Ranking conforme mostrado na Figura 4 uma tela onde é indicado o caminho do arquivo onde se encontra os pontos de entrada e saída e quais são estes pontos neste arquivo, conforme mostrado na Figura 5.

Fig. 4. – Barra de ajustes.

Fig. 5. – Diálogo para seleção de entrada e saída de dados.

Também foi implementado um campo de visualização

conforme Figura 6, onde são plotados os resultados

referentes a cada interação para uma melhor avaliação do operador.

Fig. 6. – Campo de informações.

Por último é apresentado um gráfico com a sinalização do

melhor ponto encontrado e da media para cada geração, vide Figura 7.

Fig. 7. – Curva de desempenho

VI. RESULTADOS

Foram confeccionadas e coletadas as informações de um conversor do tipo Boost conforme Figura 8, para o teste do aplicativo.

Fig. 8. – Conversor Boost avaliado. Tabela 1. Componentes Utilizados.

CARACTERÍSTICAS DO P ROJETO

inV 127= RMS 0P 36W=

Lf 60Hz= Sf 55kHz=

C1V 200V= outR 180= Ω

PARÂMETROS DO REATOR Boost

BoostL 2mH=

Capacitores 1C 1500 F= µ

2C 1500 F= µ

Semicondutores, chaves e diodos 1S IRF840→

1D a 4D 1N4007→

5D UF4007→

Na Tabela 1 estão os componentes utilizados, na tabela 2 os valores de ajustes do aplicativo desenvolvido, e na Tabela 3 estão os resultados encontrados utilizando a seleção pelo método do “Ranking” e elitismo igual a cinco:

Tabela 2. Considerações do projeto.

Variável Descrição Valor

QP Quantidade de pontos 20

N Tamanha da população 500

PC Probabilidade de cruzamento 0,7

PM Probabilidade de mutação 0,1

E Tamanho do elitismo 1

K Tamanha do torneio 3

I Nº de interações 450

Tabela 3. Resultados obtidos.

Geração Erro

0 3.10061 84 0.33647 181 0.323619 282 0.297099

A equação de modelagem obtida do circuito para uma

ordem 5 foi:

= −1,21965. + 0,466139. −

1,7532. + 6,36903. − 1,98933. +

2,26176. − 0,705368. + 1,87044. −

5,98038. + 1,76213. + 0,297099. 04

VII. CONCLUSÃO

As contribuições deste trabalho passam pela apresentação

de um resumo do estado da arte de algoritmos genéticos e mineração de dados, conforme objetivo proposto e termina com a elaboração de um aplicativo que modele um circuito elétrico de potência.

Para a proposta de utilizar algoritmos genéticos para a obtenção de um Modelo ARMAX considerando um sistema SISO (uma entrada e uma saída), e com saída invariante no tempo os resultados foram satisfatórios e com isto acredita-se facilitar a modelagem e ampliar o emprego de técnicas de controle em circuitos elétricos de potência.

VIII. REFERÊNCIAS BIBLIOGRÁFICAS

[1] FAYYAD, U. & SHAPIRO, G.P. Data Mining and Knowledge Discovery in Databases: an Overview. Communications ACM, Special Issue on Data Mining, v.39 n0 11, 1996.

[2] FOURTULAN, M.R. The use of Business Intelligence to produce performance indicators in the shop floor: an application proposal in a manufacturing company. 180p. PhD Thesis, USP, São Carlos, 2006.

[3] GOLDBERG, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989.

[4] HARDING, J.A.; SHAHBAZ M.; SRINIVAS A.; KUSAIAK, A. (2006). Data Mining in Manufacturing: A Review. In: Journal of Manufacturing Science and Engineering, 2006, ASME, Proceedings, v. 128, p. 969-976.

[5] LEE, H.D. Selection of important features for knowledge extraction from data bases. 182p. PhD Thesis, USP, São Carlos, 2005.

[6] LJUNG, L. System Identification: theory for the user, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1987.

[7] MEIRA, C.A.A. (2008). Process of knowledge discovery in databases for analysis and warning of crop diseases and its application on coffee rust. 220p. PhD Thesis. Campinas, 2008.

[8] REZENDE, S.O.; PUGLIESE, J.B.; MELANDA, E.A.; PAULA, M.F. (2002) Intelligent Systems: Fundamentals and Applications. Barueri, 2002.

[9] SHIBA, S.K. Development of a Knowledge Extraction Process Model applied to Support Decision Systems. 111p. Master Degree Thesis, São Paulo, 2008.

[10] AGUIRRE, L.A. Introdução à identificação de sistemas: técnicas lineares e não-lineares aplicadas a sistemas reais. UFMG. 3. Ed., 2007.