Algoritmos Evolutivo Multiobjetivo para Seleção de

UNIVERSIDADE FEDERAL DE GOIÁSINSTITUTO DE INFORMÁTICA

DANIEL VITOR DE LUCENA

Algoritmos Evolutivo Multiobjetivopara Seleção de Variáveis em Problemas

de Calibração Multivariada

Goiânia2013




Dissertação apresentada ao Programa de Pós–Graduação doInstituto de Informática da Universidade Federal de Goiás,como requisito parcial para obtenção do título de Mestre emComputação.

Área de concentração: Algoritmo Evolutivo,OtimizaçãoMultiobjetivo e Calibração Multivariada.Orientadora: Profa. Dra. Telma Woerle de Lima Soares

Goiânia2013




Dissertação defendida no Programa de Pós–Graduação do Instituto deInformática da Universidade Federal de Goiás como requisito parcialpara obtenção do título de Mestre em Computação, aprovada em 03 deMaio de 2013, pela Banca Examinadora constituída pelos professores:

Profa. Dra. Telma Woerle de Lima SoaresInstituto de Informática – UFG

Presidente da Banca

Prof. Dr. Clarimar José CoelhoDepartamento de Computação – PUCGO

Prof. Dr. Celso Gonçalves Camilo JuniorInstituto de Informática – UFG

Todos os direitos reservados. É proibida a reprodução total ou parcial dotrabalho sem autorização da universidade, do autor e do orientador(a).

Daniel Vitor de Lucena

Especialista em Qualidade e Gestão de Software pela Pontifícia UniversidadeCatólica de Goiás, Bacharel em Engenharia de Computação pela PontifíciaUniversidade Católica de Goiás. Experiência profissional em Gerência deProjetos, Arquitetura e Designer de Software, Coordenação de Equipe de TI.Experiência acadêmica na área de Algoritmo Genético, Teste de Software,Probabilidade e Estatística, com ênfase em Análise Multivariada, atuandoprincipalmente nos seguintes temas: detecção de outlier, inferência estatística,seleção de variáveis, otimização multiobjetivo e calibração multivariada.

Dedico este trabalho primeiramente aos meus pais, Marcondes Vitor de Lucenae Maria Honória Bessa de Lucena, que sempre proporcionaram-me, além de extensocarinho e amor, os conhecimentos da integridade e da perseverança.

Agradecimentos

Primeiramente quero agradecer aos meus pais que me deram a vida e meensinaram a vivê-la com dignidade, que se doaram inteiros e renunciaram aos seus sonhos,para que, muitas vezes, pudesse realizar os meus. Obrigado por todo o apoio e incentivodado antes e durante o desenvolvimento desse trabalho. Amo vocês!

A minha companheira Luane de Castro, por toda paciência e carinho.Agradeço à minha orientadora Telma Woerle de Lima Soares e ao meu co-

orientador Anderson da Silva Soares por toda orientação, esclarecimentos necessáriose dedicação ao meu trabalho. Por estarem sempre dispostos a ajudar. Além de grandesmentores, são também grandes amigos.

Ao Núcleo de Pesquisa em Computação (NPC) da Pontifícia UniversidadeCatólica de Goiás e a todos os colegas membros do grupo. Grupo esse que, assimcomo forneceu-me grande parte dos conhecimentos fundamentais para a realização dessetrabalho, tem apoiado vários pesquisadores em seus desafios por mais de uma década.Meus mais sinceros agradecimentos.

Aos amigos de primeira hora pela atenção e apoio.A empresa Requisito Tecnologia, em especial ao André de Paula e Welligton

Pereira, por compreenderem as ausências em pleno expediente.A todos meu muito obrigado!

Não é o mais forte que sobrevive, nem o mais inteligente, mas o quemelhor se adapta às mudanças.

Charles Darwin,A Origem das Espécies.

Resumo

de Lucena, Daniel Vitor. Algoritmos Evolutivo Multiobjetivo para Seleçãode Variáveis em Problemas de Calibração Multivariada. Goiânia, 2013. 55p.Dissertação de Mestrado. Instituto de Informática, Universidade Federal deGoiás.

Este trabalho propõe a utilização dos algoritmos genéticos multiobjetivo NSGA-II eSPEA-II na seleção de variáveis em problemas de calibração multivariada. Esses algo-ritmos são utilizados para selecionar variáveis para Regressão Linear Múltipla (MLR)com dois objetivos conflitantes: o erro de predição e do número de variáveis utilizadas naMLR. Para o estudo de caso são usado dados de trigo obtidos por espectrometria NIR como objetivo de determinar um subgrupo de variáveis com informações sobre a concentraçãode proteína. Os resultados das técnicas tradicionais de calibração multivariada como dosMínimos Quadrados Parciais (PLS) e Algoritmo de Projeções Sucessivas (APS) para aMLR estão presentes para comparações. Os resultados obtidos mostraram que a aborda-gem proposta obteve melhores resultados quando comparado com um algoritmo evolutivomonoobjetivo e com as técnicas tradicionais de calibração multivariada.

Palavras–chave

Calibração Multivariada; Algoritmo Genético; Otimização Multiobjetivo

Abstract

de Lucena, Daniel Vitor. Multiobjective Evolutionary Algorithms for Vari-ables Selection in Multivariate Calibration Problems. Goiânia, 2013. 55p.MSc. Dissertation. Instituto de Informática, Universidade Federal de Goiás.

This work proposes the use of multi-objective genetics algorithms NSGA-II and SPEA-IIon the variable selection in multivariate calibration problems. These algorithms are usedfor selecting variables for a Multiple Linear Regression (MLR) by two conflicting ob-jectives: the prediction error and the used variables number in MLR. For the case studyare used wheat data obtained by NIR spectrometry with the objective for determining avariable subgroup with information about protein concentration. The results of traditio-nal techniques of multivariate calibration as the Partial Least Square (PLS) and Succes-sive Projection Algorithm (SPA) for MLR are presents for comparisons. The obtainedresults showed that the proposed approach obtained better results when compared witha monoobjective evolutionary algorithm and with traditional techniques of multivariatecalibration.

Keywords

Multivariate Calibration; Genetic Algorithm; Multiobjective Optimization

Sumário

Lista de Figuras 11

Lista de Tabelas 12

Lista de Algoritmos 13

1 Introdução 141.1 Etapas de Desenvolvimento 161.2 Organização da Dissertação 16

2 Calibração Multivariada 172.1 Métodos Clássicos de Calibração 182.2 Medida de Avaliação do Modelo de Calibração 19

2.2.1 Regressão Linear Múltipla 192.3 O problema da Multicolinearidade e Seleção de Variáveis 202.4 Regressão em Mínimos Quadrados Parciais 21

2.4.1 Algoritmo de Projeções Sucessivas (APS) 22

3 Algoritmo Genético e Otimização Multiobjetivo 233.1 Algoritmo Genético 23

3.1.1 Indivíduos 243.1.2 Populações 24

Inicialização 253.1.3 Avaliação 253.1.4 Operador de Seleção 263.1.5 Operador de Cruzamento 263.1.6 Operador de Mutação 273.1.7 Atualização 273.1.8 Critério de Parada 28

3.2 Otimização Multiobjetivo 283.2.1 Algoritmo Genético de Classificação por Não Dominância II (NSGA-II) 293.2.2 Algoritmo Evolutivo da Força de Pareto II (SPEA-II) 313.2.3 Hipervolume 33

4 Materiais e Métodos 354.1 Dados do Trigo 354.2 Ferramentas e Ambiente 364.3 Decisor Multiobjetivo 38

5 Resultados e Discussões 405.1 Resultados dos algoritmos PLS, APS-MLR e MONO-AG-MLR 405.2 Resultados com 30 gerações 425.3 Resultados com 50 gerações 445.4 Resultados com 100 gerações 465.5 Considerações Finais 48

6 Conclusão 50

Referências Bibliográficas 52

Lista de Figuras

2.1 Processo de espectroscopia de absorção. 172.2 Organização dos dados. 18

3.1 Cálculo crowding-distance. Pontos marcados em círculos preenchidossão soluções da fronteira não dominada. 30

3.2 Procedimento NSGA-II. 313.3 Algoritmo de Corte do algoritmo SPEA-II [47]. 333.4 Hipervolume gerado pelo conjunto de soluções não dominadas para as

funções F1 e F2 34

4.1 Espectro das amostras de trigo após filtragem. 36

5.1 Comportamento RMSEP com diferentes números máximos de variáveisno algoritmo genético monoobjetivo. 41

5.2 Fronteiras de Pareto no conjunto de validação geradas pelo NSGA-II-MLR(a) e a população final resultante do SPEA-II-MLR (b) com 30 gerações 42

5.3 Variáveis selecionadas pelo NSGA-II-MLR (a) e a população final resul-tante do SPEA-II-MLR (b) com 30 gerações dispostas no espectro. 43

5.4 Fronteiras de Pareto geradas pelo NSGA-II-MLR (a) e a população finalresultante do SPEA-II-MLR (b) com 50 gerações 44


5.6 Fronteiras de Pareto geradas pelo NSGA-II-MLR (a) e a população finalresultante do SPEA-II-MLR (b) com 100 gerações 47


5.8 Amostras do grupo de predição. 49

Lista de Tabelas

5.1 Parâmetros de Configuração do NSGA-II-MLR e SPEA-II-MLR. 405.2 Resultados das técnicas tradicionais PLS, APS-MLR e MONO-AG-MLR 415.3 Resultado médio das soluções escolhidas pelo método decisor multiobje-

tivo dos algoritmos NSGA-II-MLR e SPEA-II-MLR no conjunto de predição. 435.4 Variáveis selecionadas pelo NSGA-II-MLR e SPEA-II-MLR. 445.5 Resultado médio das soluções escolhidas pelo método decisor multiobje-

tivo dos algoritmos NSGA-II-MLR e SPEA-II-MLR no conjunto de predição. 455.6 Variáveis selecionadas pelo NSGA-II-MLR e SPEA-II-MLR 465.7 Resultado médio das soluções escolhidas pelo método decisor multiobje-

tivo dos algoritmos NSGA-II-MLR e SPEA-II-MLR no conjunto de predição. 475.8 Variáveis selecionadas pelo NSGA-II-MLR e SPEA-II-MLR 48

Lista de Algoritmos

4.1 Inicialização da População 374.2 Avaliação dos Objetivos 384.3 Decisor Multiobjetivo 39

CAPÍTULO 1Introdução

A calibração é definida como o processo de construção de um modelo matemá-tico para relacionar variáveis independentes a variáveis dependentes que concede a pre-dição do valor de uma grandeza de interesse. Variáveis independentes são os conjuntosde dados coletados através de instrumentos que serão utilizados para construção de mo-delos de calibração multivariada organizados no formato matricial, denominado matrizde variáveis independentes ou matriz de respostas instrumentais. Variáveis dependentesé o conjunto de valores de referência obtido em laboratório que servirá como parâmetropara a calibração do modelo sendo representado como um vetor, denominado vetor devariáveis dependentes ou vetor de parâmetro de referência [4].

Dado um conjunto de variáveis independentes e dependentes é possível realizara calibração para a predição a partir de novas medidas de variáveis independentes. Nestecontexto, a predição é o processo de usar o modelo para estimar a concentração de umanalito a partir de propriedades medidas na saída do instrumento para uma determinadaamostra, como por exemplo, a absorvância a um comprimento de onda dado pode serrelacionado com a concentração do composto analisado [27].

Neste contexto, algumas técnicas conhecidas para a construção de modelosde regressão são: Regressão Linear Múltipla (Multiple Linear Regression, MLR) [27],Regressão em Componentes Principais (Principal Component Regression, PCR) [24],e Regressão de Mínimos Quadrados Parciais (Partial Least Square Regression, PLS)[4][46][27].

Nem sempre é necessária a utilização de todos os dados recolhidos de umaamostra durante a calibração, por isso, quando se pretende analisar apenas algumascaracterísticas da amostra, é possível utilizar apenas um subconjunto dos dados quepossuem as informações sobre o analito de interesse. Selecionar variáveis com essasinformações, permite criar modelos mais simples e de fácil interpretação, evitando assimo processamento de informações irrelevantes. Alguns dos problemas encontrados nacalibração multivariada são: a) a colinearidade, onde duas ou mais variáveis possueminformação correlacionadas e b) a sensibilidade a ruídos, que prejudica a eficiência dacalibração e predição dos compostos da amostra, em especial a MLR [27][11].

15

Uma solução para o problema das variáveis colineares é eliminá-las por meioda seleção [17]. Neste processo, a utilização de algoritmos evolutivos, em particularos algoritmos genéticos (AGs), é uma opção. Um algoritmo de otimização como umalgoritmo evolutivo pode ser usado para escolher um subconjunto de variáveis com poucacorrelação e informação relacionada com as propriedades de interesse.

A característica do algoritmo genético mono-objetivo em obter um melhorresultado para sua função objetivo, faz com que muitas variáveis sejam selecionadasquando comparado a outras técnicas de seleção de variáveis como o Algoritmo dasProjeções Sucessivas (APS). No contexto da calibração multivariada, a função objetivousada é minimizar o erro residual entre a concentração predita pelo modelo de regressãoe a concentração real da propriedade de interesse. Esta função objetivo, induz o algoritmogenético a inserir no modelo uma nova variável para redução do erro residual mesmo queessa diferença seja irrelevante. Esse problema é conhecido como overfitting [19][3].

A otimização multiobjetivo, em geral, é aplicada em problemas onde dois oumais objetivos são conflitantes. Essa característica está presente em problemas de calibra-ção multivariada. A calibração multivariada é uma parte a química analítica para descreveras técnicas e operações associadas com a manipulação matemática e interpretação de da-dos químicos, denominada quimiometria [13]. A otimização multiobjetivo busca fornecersoluções factíveis e que sejam não dominadas compondo a chamada fronteira de Pareto.Uma solução é não dominada quando a melhora em um dos objetivos implica no detri-mento de pelo menos um dos outros objetivos. Foram propostos na literatura diversosalgoritmos genéticos para a otimização multiobjetivo nos quais se destacam o AlgoritmoGenético de Classificação por Não Dominância II (Non-Dominated Sorting Genetic Al-

gorithm II, NSGA-II) e o Algoritmo Evolutivo da Força de Pareto II (Strength Pareto

Evolutionary Algorithm II, SPEA-II) [9][47].Este trabalho propõem o uso dos algoritmos NSGA-II e SPEA-II para realizar

a seleção de variáveis e minimizar a colinearidade em problemas de calibração multi-variada. Com o uso de algoritmo genético multiobjetivo busca-se reduzir o overfitting

apresentado pelos algoritmos genéticos mono-objetivo. Os algoritmos genéticos multi-objetivo tem sido aplicados para problemas de calibração, em um contexto similar aoproposto, com resultados satisfatórios [5][12].

Como estudo de caso, os algoritmos propostos NSGA-II-MLR e SPEA-II-MLRserão aplicados ao processo de seleção de variáveis em um conjunto de dados do trigo.Ambos os algoritmos possuem duas funções objetivo a) minimizar o erro residual entrea concentração predita pelo modelo de regressão e a concentração real de proteína nogrão e b) minimizar a quantidade de variáveis selecionadas para o modelo de calibração,para reduzir o custo computacional e simplificar o modelo de calibração. Utiliza-se comobase de comparação os algoritmos de seleção de variáveis APS-MLR, AG-MONO-MLR

1.1 Etapas de Desenvolvimento 16

e PLS-MLR.

1.1 Etapas de Desenvolvimento

A realização desse trabalho segui as etapas descritas a seguir.

1. Definir do escopo do problema: foi escolhido dentre os problemas acerca dacalibração multivariada a seleção de variáveis como objeto de estudo.

2. Revisar a literatura: um levantamento bibliográfico foi realizado para identificaros trabalhos recentes sobre o problema escolhido.

3. Analisar trabalhos correlacionados: após uma investigação sobre trabalhos como mesmo propósito, construiu-se uma base para comparação dos resultados publi-cados com os resultados da proposta a ser definida.

4. Definir proposta de solução: o uso de algoritmo genético multiobjetivo foi defi-nido como alternativa para solucionar o problema de seleção de variáveis em pro-blemas de calibração multivariada.

5. Implementar solução proposta: os algoritmos genéticos multiobjetivo NSGA-II eSPEA-II foram implementados.

6. Elaborar a dissertação: os resultados da pesquisa foram descritos no texto dadissertação de mestrado e em artigos científicos.

1.2 Organização da Dissertação

O Capítulo 2 traz uma revisão sobre a calibração multivariada e alguns dos prin-cipais métodos de regressão como: Regressão Linear Múltipla e Regressão em MínimosQuadrados Parciais. Apresenta um síntese sobre o Algoritmo das Projeções Sucessivas eo cálculo da Raiz do Erro Quadrático de Predição. O Capítulo 3 mostra os conceitos sobrealgoritmo genético e otimização multiobjetivo. Mostra também a fundamentação teóricasobre os algoritmos multiobjetivo NSGA-II e SPEA-II. O Capítulo 4 relaciona os mate-riais e métodos usados na execução dos algoritmos propostos. O Capítulo 5 apresenta osresultados obtidos com o uso dos algoritmos NSGA-II-MLR e SPEA-II-MLR e faz umcomparativo com os resultados obtidos com os algoritmos AG-MONO-MLR, PLS-MLRe APS-MLR. O Capítulo 6 mostra considerações finais e aponta as sugestões de trabalhosfuturos.

CAPÍTULO 2Calibração Multivariada

A análise química quantitativa é a ciência da determinação da concentração deuma ou várias substâncias presentes numa amostra. O estado da arte para esta aplicação éo uso da técnica de espectrofotometria cuja medida da interação entre o objeto de análisee energia irradiada [39].

Esta interação é suportada pela lei de Lambert-Beer [26] ilustrada na Figura 2.1.Essa figura mostra a amostra recebendo radiação P0 e passando através uma energia menorP. A energia absorvida da amostra pode ser medida com espectrofotômetro e relacionadocom a concentração da propriedade. Por conseguinte, as intensidade de absorbância édada numericamente pela Equação (2-1).

x(λ) = logP0(λ)

P(λ)(2-1)

onde P0(λ) representa a radiação emitida pelo equipamento e P(λ) é a radiação emitidapela amostra no comprimento de onda λ.

Figura 2.1: Processo de espectroscopia de absorção.

Para obter a concentração da amostra inteira é necessário irradia-la com diferen-tes comprimentos de onda simultaneamente. Neste cenário é comum a sobreposição de

2.1 Métodos Clássicos de Calibração 18

comprimentos de ondas e, consequentemente, dois ou mais sinais podem enviar a mesmainformação. Em termos algébricos, as ondas sobrepostas significam alta correlação entreas variáveis e pode induzir a problemas matemáticos no processo de regressão [31].

Os dados obtidos a partir de procedimentos como absorção por espectroscopiasão dispostos no formato matricial ilustrado na Figura 2.2

Figura 2.2: Organização dos dados.

onde X é a matrix de respostas instrumentais denominada matriz de variáveis indepen-dentes. Cada coluna contém a absorbância de um determinado comprimento de onda paracada objeto analisado (linhas da matriz X). É mostrado também concentração do analitode interesse, obtido através de procedimentos laboratoriais, denominado variável depen-dente ou parâmetro de referência, denotado por Y. A variável dependente pode eventual-mente conter mais de um analito de interesse em que cada coluna refere-se a concentraçãode um determinado analito.

Como dificilmente a concentração dos analitos de interesse é fornecida direta-mente por meio de instrumentos de análise como o espectrofotômetro [32], a quimio-metria, através de calibração tem o objetivo de extrair essas informações com o uso demodelos matemáticos que relacionam linearmente o sinal analítico (resposta instrumen-tal) com o analito [32][38][33].

2.1 Métodos Clássicos de Calibração

Quando o sinal analítico utilizado nos métodos de calibração é função daconcentração esses métodos são chamadas de métodos clássicos, pois apresentam umarelação proporcional igual a prevista na Lei de Lambert-Beer [30]. Um modelo clássico éexpresso pela Equação (2-2).

X = K∗Y (2-2)

2.2 Medida de Avaliação do Modelo de Calibração 19

onde X é a matriz de respostas instrumentais, Y é a matriz de concentrações e K é a matrizque contém o sinal puro de cada componente da mistura.

O método clássico pode ser classificado em direto ou indireto. Ele é denominadoclássico direto (Direct Classical Least Square,DCLS) se K for obtido através de medidasexperimentais e denominado clássico indireto (Indirect Classical Least Square, ICLS)quando K é estimado empregando X e Y [4].

A vantagem da utilização dos métodos clássicos é a simplicidade dos cálculosenvolvidos, entretanto, a aplicação desses métodos é tem necessidade de dispor ou estimarK, que possui informações sobre as substâncias que geram o sinal analítico.

Uma exceção são os chamados de métodos inversos de calibração, os modelosonde a concentração Y é uma função do sinal analítico medido. Apesar de contrariar a Leide Lambert-Beer, esses métodos contornam algumas restrições dos métodos clássicos porutilizarem na modelagem dos dados a estrutura de variâncias e covariâncias da matriz X.

2.2 Medida de Avaliação do Modelo de Calibração

Obtido o modelo de calibração é possível avaliar sua capacidade preditiva pormeio de medidas tais como a Raiz do Erro Quadrático de Predição (Root Mean Square

Error of Prediction, RMSEP). O RMSEP avalia o quanto a concentração predita pelomodelo se aproxima da concentração esperada. O cálculo do RMSEP é expresso pelaEquação (2-3).

RMSEP =

√n

∑i=1

(yi− yi)2

n(2-3)

onde yi é a i-ésima concentração predita pelo modelo de regressão. Esta medida ajudana avaliação da performance do modelo de calibração e permite escolher modelos maisadequados para a predição.

2.2.1 Regressão Linear Múltipla

A Regressão Linear Múltipla (Multiple Linear Regression, MLR) é uma técnicaestatística para construção de modelos lineares. Esses modelos relacionam um conjunto deuma ou mais variáveis respostas (dependentes) à um conjunto de preditores ou variáveisindependentes [22]. O modelo clássico da regressão linear múltipla é dado pela Equação(2-4).

Y = Xβ+ ε (2-4)

2.3 O problema da Multicolinearidade e Seleção de Variáveis 20

onde X é a matrix de dados obtida através de respostas instrumentais de ordem (n x p),sendo n o número de observação e p a quantidade de variáveis de cada observação, β é ovetor de coeficientes de regressão de ordem (n x 1), ε é o vetor de erro residual de ordem(n x 1) e Y é a matriz de variável resposta de ordem (n x 1) que possui os valores dapropriedade de interesse obtido através de um método de referência, sendo cada variáveldependente de Y uma combinação linear obtida através das variáveis independentes damatriz de dados X [22]. O modelo (2-4) pode ser expresso em notação matricial conformea Equação (2-5).

y1

y2...

yn

=

1 x11 x12 · · · x1p

1 x21 x22 · · · x2p...

...... . . . ...

1 xn1 xn2 · · · xnp

β1

β2...

βn

+

ε1

ε2...

εn

(2-5)

A pseudo-inversa de uma matriz A de ordem (m x n) com colunas linearmenteindependentes é determinada por uma matriz de ordem (n x m) onde A+ = (AT A)−1AT .Os coeficientes de regressão são determinados pela combinação linear calculada pormínimos quadrados a partir da pseudo-inversa de X [22] conforme apresentado naEquação (2-6).

β = (X′X)−1(X′Y) (2-6)

A variável resposta estimada é definida pela combinação linear entre a matriz dedados X e os coeficientes de regressão estimado β [35], logo

Y = Xβ (2-7)

o erro residual ε é calculado pela diferença entre a variável resposta estimada Y e avariável resposta de referência Y [35].

ε = Y− Y (2-8)

2.3 O problema da Multicolinearidade e Seleção de Va-riáveis

Em estatística, a existência de correlação linear entre duas ou mais variáveisindependentes em um modelo de regressão múltipla é definida como multicolinearidade[2][6]. Este problema pode causar sérias dificuldades com a confiabilidade das estimativas

2.4 Regressão em Mínimos Quadrados Parciais 21

dos coeficientes β do modelo matemático e dificuldade em compreender os valoresobtidos na variável de resposta Y [2][6].

Em situações em que existe um número elevado de variáveis dependentes, amaior parte pode contribuir pouco ou nada na precisão de predição. Selecionar umconjunto reduzido de variáveis informativas pode influenciar positivamente no modelode regressão [40][20]. O ponto principal é determinar quantas e quais variáveis devemcompor este subconjunto.

As razões para a utilização de apenas uma parte das variáveis preditoras dispo-níveis ou possíveis incluem [29]:

1. Estimar ou predizer a um custo menor reduzindo o número de variáveis em que osdados são coletados;

2. Predizer com precisão eliminando variáveis sem informação;3. Descrever um conjunto de dados multivariados com mais simplicidade;4. Estimar os coeficientes de regressão com pequenos erros padrões (especialmente

quando alguns dos preditores são altamente correlacionados).

Existem pelo menos duas maneiras de contornar o problema da multicolineari-dade das variáveis independentes, as quais podemos citar a seleção de variáveis e a trans-formação de dados. Como exemplo da aplicação dessas técnicas temos o Algoritmo dasProjeções Sucessivas (APS) e Algoritmo Genético (AG) como exemplo de técnicas de se-leção de variáveis e a Regressão em Mínimos Quadrados Parciais (PLSR) como exemplode transformação de dados.

A estratégia proposta neste trabalho para o problema da seleção de variáveis emregressão linear múltipla é a utilização de algoritmos genéticos multiobjetivo. O critériomultiobjetivo envolve reduzir o custo pela redução do número de variáveis e minimizar oerro de predição.

2.4 Regressão em Mínimos Quadrados Parciais

Mínimos Quadrados Parciais (PLS) é um método para a construção de modelospreditivos, quando existe um grande número de variáveis independentes colineares. Note-se que a ênfase está em predizer as respostas e não necessariamente em tentar entender arelação subjacente entre as variáveis [45][1].

A base fundamental do PLS é o PCA. O PCA consiste na manipulação da matrizde dados de tal forma a representar as variações presentes em muitas variáveis atravésde um número menor de novas variáveis denominadas fatores [24][23]. Os fatores repre-sentam o novo sistema de eixos também chamados de componentes principais, variáveislatentes ou autovetores, para representar as amostras. A principal diferença do PLS em

2.4 Regressão em Mínimos Quadrados Parciais 22

relação ao PCA é que ao invés de se utilizar apenas a variância das variáveis originais,o PLS utiliza o vetor Y para rotacionar os eixos de componentes principais. Tal rotaçãopermite obter uma maior capacidade preditiva [1].O primeiro fator (variável latente) des-creve a direção de máxima variância, também correlacionada com a concentração. Estasvariáveis latentes são combinações lineares dos componentes principais calculados pelométodo PCA [13][15].

Há vários algoritmos para calcular os componentes principais utilizados noalgoritmo PLS dos quais vale citar os mais comuns NIPALS e SVD [15][13].

2.4.1 Algoritmo de Projeções Sucessivas (APS)

O algoritmo das projeções sucessivas é uma técnica de seleção de variáveis paraminimizar problemas de colinearidade em regressão linear múltipla [3][14].

APS é uma técnica do tipo forward (passo a frente) que dado uma variávelinicial, a cada iteração, inseri-se uma nova variável até que um número máximo n de sejaatingido. O objetivo principal do APS é selecionar as variáveis que contenham o mínimode redundância possível minimizando o problema de colinearidade [3]. APS é compostopor três fases principais:

1. A primeira consiste em operações de projeção realizadas na matriz X de respostasinstrumentais. Estas projeções são usadas para gerar cadeias de variáveis com cadavez mais elementos. Cada elemento de uma cadeia é selecionado de modo a obtera menor colinearidade com a anterior.

2. Na fase seguinte, os subconjuntos de variáveis candidatas são avaliados de acordocom o desempenho preditivo RMSEP no modelo MLR.

3. A última fase consiste no procedimento de eliminação de variáveis, em que pormeio de um teste estatístico verifica-se se a eliminação de uma dada variável nãocompromete significativamente o erro RMSEP. Tal procedimento visa melhorar asimplicidade do modelo.

O APS não modifica os vetores de dados originais pois as projeções são utilizadasapenas para propósitos de seleção. Portanto, a relação entre os vetores de dados evariáveis espectrais é preservada [3].Os últimos resultados da literatura sobre calibraçãomultivariada mostrou que o APS-MLR tem os melhores resultados em termos de RMSEPe parcimônia, quando comparado com o algoritmo genético clássico e PLS [41][42].

CAPÍTULO 3Algoritmo Genético e Otimização Multiobjetivo

3.1 Algoritmo Genético

Os Algoritmos Genéticos (AGs) são técnicas de otimização inspirados no prin-cípio da sobrevivência e reprodução dos indivíduos mais aptos, proposto por CharlesDarwin [16]. Os AGs fazem uso de mecanismos de busca paralela e adaptativa. Forampropostos na década de 70 por Holland e tem sido largamente aplicados a problemas deotmização [21].

Nos AGs as soluções candidatas do problema (indivíduos) são mantidas emuma população, que determina a característica paralela do algoritmo. No início de suaexecução o AG cria uma população inicial que é submetida a um processo evolutivocomposto pelas seguintes etapas:

1. Avaliação: análise da aptidão dos indivíduos (soluções) para verificar a sua respostaao problema;

2. Seleção: seleção dos indivíduos para reprodução. São selecionados os indivíduosmais aptos para a solução;

3. Cruzamento: os indivíduos selecionados são cruzados para geração de novosindivíduos;

4. Mutação: características de indivíduos selecionados são alteradas para dar varie-dade à população;

5. Atualização: os indivíduos gerados são inseridos na população para próximageração;

6. Finalização: verificação se a condição de parada do algoritmo foi atingida e oalgoritmo é encerrado em caso positivo ou retorna a etapa de avaliação.

A seguir são detalhados os principais conceitos e etapas do funcionamento doAG.

3.1 Algoritmo Genético 24

3.1.1 Indivíduos

Os indivíduos representam as possíveis soluções para o problema compostapor uma cadeira de genes. Gene, termo criado em 1909 por Johannsen, na definiçãoda genética clássica, é a unidade funcional da hereditariedade onde estão presentes osácidos nucleicos, portadores de informações genéticas que proporcionam a diversidadeentre os indivíduos. O alelo é uma das diversas formas de um certo gene, que ocupa umadeterminada posição em um cromossomo, tal posição é definida como locus [36].

Para permitir a manipulação da solução pelo AG esta precisa ser codificada e aotérmino do processo evolutivo, o indivíduo precisa ser decodificado para obter a soluçãofinal encontrada. A escolha da codificação do indivíduo é uma das partes mais importantedo algoritmo, uma vez que será responsável pelo desempenho do AG. A escolha do tipode codificação depende diretamente do problema a ser resolvido.

Os tipos mais utilizados para representação dos indivíduos são a binária e a real.Na representação binária os indivíduos são compostos por cadeias binárias de 0’s e 1’s.Na representação real cada indivíduo é composto por um número real [16].

As características mais importantes são:

1. Genótipo: informação presente na estrutura de dados dos indivíduos (codificação);2. Fenótipo: resultado da decodificação do indivíduo;3. Grau de Adaptação (fitness): representa o grau de resposta do indivíduo para o

problema. É calculado por uma função objetivo.

3.1.2 Populações

A evolução do AG só é possível pela dinâmica populacional [16]. Essa dinâmicaatua propagando características importantes a gerações seguintes (cruzamento) enquantonovas são testadas (mutação). O AG é responsável pela manipulação das sequências degenes dos indivíduos presentes nas populações que atua.

As características das populações são:

1. Geração: representa o número de vezes que a população passou pelo processoevolutivo (seleção, reprodução, mutação e atualização);

2. Média de Adaptação: média dos resultados do valor de aptidão de cada indivíduo.É representada pela Equação (3-1).

MA =∑

ni=1 fo(i)

n(3-1)

3. Grau de Convergência: representa o quão próxima a média de adaptação dageração atual está em relação as gerações anteriores. O AG é responsável pela


convergência da população para um valor ótimo de adaptação. A população podesofrer de convergência prematura que ocorre quando ela converge para uma médiade adaptação sub-ótima e não consegue sair devido a baixa diversidade;

4. Diversidade: variação entre os genótipos da população. Ela é fundamental paraampliar o espaço de busca. Um valor baixo de diversidade está relacionado aconvergência prematura do AG;

5. Elite: melhores indivíduos da população. Uma técnica comum nos AGs é o eli-tismo, onde os m melhores indivíduos são preservados para a próxima geração.

Inicialização

A inicialização de um AG consiste na criação da sua população inicial de solu-ções. Normalmente, essa etapa é realizada por meio de funções aleatórias para geraçãodos indivíduos, com o objetivo de obter uma maior diversidade. Existem alternativas paraesse processo aleatório, que visam suprir deficiências quando a representação do indiví-duo é mais complexa e/ou quando se deseja um melhor desempenho. Os operadores deinicialização mais tradicionais são [16][37]:

• Inicialização Aleatória Uniforme: à cada gene do indivíduo é atribuído um valordo conjunto de alelos, sorteado de forma aleatoriamente uniforme;• Inicialização Aleatória Não Uniforme: a escolha do valor a ser atribuído ao gene

depende da frequência dele em relação aos demais valores;• Inicialização Aleatória com dope: indivíduos otimizados são inseridos na popula-

ção. A presença desses indivíduos otimizados pode guiar o AG a uma convergênciaprematura;• Inicialização Parcialmente Enumerativa: indivíduos são inseridos de tal forma

que fazem com que a população comece o processo evolutivo possuindo todos osformatos possíveis de uma determinada ordem.

3.1.3 Avaliação

Na etapa de avaliação cada indivíduo é avaliado para que seja determinado o seufitness. Essa avaliação é realizada por meio da função objetivo do problema. O cálculo dafunção objetivo é realizado repetidamente ao longo do processo evolutivo. Dependendoda complexidade da função objetivo, o custo de processamento pode ser alto. Em taissituações é comum o uso de funções não determinísticas, que avaliam apenas parte dascaracterísticas dos indivíduos [7][16].


3.1.4 Operador de Seleção

A etapa de seleção é responsável pela perpetuação das melhores característicasna espécie. Seleção é um processo dirigido, pois opera de forma determinística oupróxima disso, sendo também, um processo cumulativo, pois os benefícios gerados emuma geração são mantidos para outra geração [8].

Na seleção os indivíduos mais aptos são escolhidos para a etapa de cruzamento.Esses indivíduos são selecionados com base na sua aptidão. Os principais métodos deseleção são [16][37]:

• Ranking: os indivíduos são organizados em um ranking de acordo com o suaaptidão. A probabilidade de escolha é atribuída conforme a posição que ocupamno ranking;• Roleta: calcula-se o somatório dos fitness da população (total); sorteia-se um valor

i tal que i ∈ [0; total]; seleciona o indivíduo x que se localiza na faixa do somatóriocorrespondente ao valor i [7];• Torneio: sorteia-se aleatoriamente dois ou mais k indivíduos que competem entre

si, sendo selecionado o mais apto. Quanto maior o valor de k, maior a pressão deseleção do AG;• Uniforme: todos os indivíduos possuem igual probabilidade de serem escolhidos.

Consequentemente, a taxa de convergência é lenta.

3.1.5 Operador de Cruzamento

Com os indivíduos já selecionados, estes são submetidos ao cruzamento (cros-

sover). Nesta etapa os indivíduos selecionados são agrupados em pares e os genes decada um são utilizados para formação de um novo indivíduo (filho). Os operadores decruzamento mais conhecidos são de um ponto, multiponto, segmentado, uniforme e com-binação parcial [16][7].

• Crossover de um ponto (1PX): nesse tipo de cruzamento escolhe-se um ponto decorte nos genomas dos pais e parte de cada um é dado para os filhos. Dado doisgenomas x e y com comprimentos lx e ly, respectivamente, sorteia-se um número p

tal que 0 < p < lg. O filho f0 herdará todos os genes de 1 até p de x e todos os genesde p+1 até ly de y. O filho f1 herdará todos os genes de p+1 até lx de x e todos osgenes de 1 até p de y.• Crossover multiponto (MPX): semelhante ao cruzamento de um ponto, com a

diferença de que são escolhidos n pontos de corte, n é um número fixo.• Crossover segmentado (SX): semelhante ao cruzamento multiponto. Entretanto, o

número n de pontos de corte é alterado todas as vezes que é executado.


• Crossover uniforme (UX): nesse cruzamento é sorteado para cada gene de qualpai esse será herdado. Geralmente utiliza-se uma máscara de 0s (zeros) e 1s (uns)construída para cada cruzamento. Nessa, 1s indicam que o gene virá de um pai e 0virá de outro. Para construir o segundo filho, inverte-se o padrão.• Crossover de dois pontos (PMX): dois pontos de corte são escolhidos. Os filhos

herdam os genes que estão entre os pontos de corte dos dois pais. Os genes restantessão preenchidos com valores considerados mais adequados para cada filho.

3.1.6 Operador de Mutação

Consiste em introduzir pequenas alterações na estrutura dos indivíduos. Essasalterações são condicionadas a uma probabilidade de ocorrência do operador. A mutaçãoé importante, pois garante diversidade na população, permitindo uma maior exploração doespaço de busca. Porém, uma taxa muito alta de mutação pode fazer com que a populaçãoperca características fundamentais [16][37][7].

Alguns exemplos de mutação são:

• Mutação flip: o gene a ser mutado tem o seu valor alterado por outro sorteadoaleatoriamente dentro dos valores válidos. No caso da representação binária esseoperador troca o valor do gene de 0 (zero) para 1 (um) e vice-versa;• Mutação por troca: n pares de genes são sorteados e os valores de cada par são

trocados entre si;• Mutação creep: um valor aleatório é somado ou subtraído ao gene a ser mutado.

3.1.7 Atualização

Após as etapas de cruzamento e mutação a etapa da atualização fica responsávelpor atualizar a população para a próxima geração. Essa atualização depende da políticaadotada pelo AG. Na forma tradicional do AG o número de indivíduos da população semantém fixo. O número de indivíduos gerados na etapa de cruzamento é igual ao númerode indivíduos da população original. Todos os novos indivíduos substituem o indivíduosda população anterior [16][7].

Existem alternativas a abordagem de atualização do AG tradicional. O númerode indivíduos gerados pode ser menor do que o tamanho da população, o tamanho dapopulação pode variar a cada geração e o critério de inserção de novos indivíduos podevariar. Neste último, por exemplo, os indivíduos são inseridos somente se o fitness dofilho for melhor do que o do pai, ou todos são inseridos mas são mantidos n melhoresindivíduos pais (elitismo) [16][7]. Outra alternativa é aplicar algum dos métodos deseleção apresentados na Seção 3.1.4.

3.2 Otimização Multiobjetivo 28

3.1.8 Critério de Parada

O critério de parada não envolve um operador genético, é apenas um passoque indica o término da execução do algoritmo. Os critérios de parada variam desde onúmero de gerações realizadas até o grau de convergência da população atual e dependedo problema a ser resolvido [16].

3.2 Otimização Multiobjetivo

Muitos problemas de tomada de decisão no mundo real, possuem a necessidadede otimização simultânea de múltiplos objetivos [28]. Para esses problemas realizar o pro-cesso de otimização observando um único objetivo, torna-se uma abordagem insuficientepara encontrar soluções satisfatórias, visto que grande parte desses problemas apresentamuma coleção de objetivos a serem otimizados. Esses objetivos nem sempre são harmôni-cos, podendo haver conflitos entre eles, e consequentemente, a melhoria de um implicana deterioração do outro.

Tais problemas de otimização multiobjetivo (Multiobjective Optimization,MOO) requerem técnicas distintas, que são muito diferentes das técnicas de otimizaçãopadrão para problemas de objetivo único. É muito claro que se houver dois objetivos aserem otimizados, pode ser possível encontrar uma solução que é o melhor no que dizrespeito ao primeiro objetivo, e uma outra solução, que é o melhor no que diz respeito aosegundo objetivo [28]. A descrição de um problema MOO, em forma geral, é dada por:

MOO =

X∗ = x ∈ℜn

x∗ =minx

maxxf (x)

sujeito à: x ∈ Fx

(3-2)

onde X∗ é o conjunto de soluções eficientes, ℜn é o espaço de parâmetros de otimização,x∗ um ponto pertencente a X∗, f (x) o vetor de funções objetivos do problema e Fx oconjunto de pontos factíveis pertencentes ao espaço dos parâmetros de otimização [44].

É importante classificar todas as possíveis soluções para problemas de MOO emsoluções dominadas e não dominadas. Data uma solução x, esta é dominada se existeuma solução viável y não pior do que x em todas as coordenadas, ou seja, para todos osobjetivos fi(i = 1, · · · ,k) [28]:

fi ≤ fi(y); para 1≤ i≤ k (3-3)

Não existindo tal relação, ou seja, não existindo uma solução dominada porqualquer outra solução viável, esta é definida como solução não-dominada ou solução


Pareto-ótima, também, grupo de soluções Pareto-ótimas é denominado conjunto Pareto-ótimo. Este conjunto pode ser de algum interesse, idealmente, o sistema deve informar-lo[28].

Schafter, em 1984, implementou o primeiro AG para MOO chamado VEGA(Vector Evaluated Genetic Algorithm), sendo este uma extensão do GENESIS, programapara incluir funções multicritério. Em 1994, Srivivas e Deb [43] propuseram uma novatécnica denominada Algoritmo Genético de Classificação por Não Dominância (Non-

Dominated Sorting Genetic Algorithm, NSGA) baseada em classificar os indivíduosem vários grupos, denominados fronteiras (fronts). Esse processo de agrupamento érealizando com base na não dominação, antes da seleção [28]. Em 1998, Zitzler eThiele [48] apresentou um algoritmo que incorporou a abordagem do elitismo, nãoexplicitamente usada por seus antecessores, chamado Algoritmo Evolutivo da Força dePareto (Strength Pareto Evolutionary Algorithm,SPEA). Em 2001 o SPEA foi estendidosurgindo o SPEA-II. O objetivo do SPEA-II consiste em localizar e manter uma fronteirade soluções Pareto-ótimas [47].

3.2.1 Algoritmo Genético de Classificação por Não Dominância II(NSGA-II)

Desenvolvido por Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, e Meyarivan,o NSGA-II, assim como sua primeira versão NSGA, implementa o conceito de dominân-cia, classificando a população em fronteiras conforme o grau de dominância. As melho-res soluções de cada geração ficam localizadas na primeira fronteira (não dominados) aopasso que as piores soluções na última fronteira (mais dominadas) [9].

A principal diferença do NSGA-II e um AG simples é a forma como o operadorde seleção é aplicado, sendo este operador subdividido em dois processos: ClassificaçãoRápida por Não Dominância (Fast Non-Dominated Sorting) e o Distância de Agrupa-mento (Crowding Distance). Os demais operadores são aplicados de maneira tradicional[9].

A execução do processo de Classificação Rápida por Não Dominância é feitoem 2 partes: primeiramente todos os indivíduos da população (novos e antigos) sãocomparados entre si para determinação do grau de dominância e consequentementeclassificados. Ao término da primeira parte do processo, os indivíduos que possuíremo grau de dominância igual a zero, ou seja, não dominados e são inseridos na primeirafronteira (Pareto-Ótima) [9].

A segunda parte do processo irá tratar os indivíduos cujo o grau de dominância édiferente de zero. Retira-se da população os indivíduos de dominância zero e recalcular adominância dos demais indivíduos. Após o novo cálculo os indivíduos de dominância zero


são inseridos na próxima fronteira, assim por diante para todas as fronteiras. O processoé repetido até que a população esteja vazia [9].

O processo de encontrar soluções Pareto-ótimas tende a convergir para umamesma região do espaço de busca. Uma característica desejada em um AG multiobjetivoé que as soluções encontradas estejam espalhadas neste espaço. Para tal, é aplicado osegundo processo do operador de seleção do NSGA-II, a Distância de Agrupamento.

A Distância de Agrupamento é uma nova abordagem baseada na comparaçãode aglomerado proposta para substituir a abordagem da função de compartilhamento doNSGA. Outra função da Distância de Agrupamento é ordenar as soluções dentro de umamesma fronteira [9].

Para melhor compreender a abordagem do Crowding Distance, é necessáriodefinir a métrica para estimação de densidade e o operador de comparação.

Figura 3.1: Cálculo crowding-distance. Pontos marcados em cír-culos preenchidos são soluções da fronteira não domi-nada.

A estimativa da densidade de soluções em torno de uma solução particular dapopulação, é obtida através do cálculo da distância média de dois pontos de cada ladodeste ponto ao longo de cada um dos objetivos. O valor i serve como uma estimativado perímetro do cuboide formado usando os vizinhos mais próximos como os vértices,conforme Figura 3.1 [9].

O operador de comparação (≺n) tem o objetivo de orientar o processo de seleçãonas várias fases do algoritmo em direção a uma fronteira Pareto-ótima uniformementeespalhada. Supondo que cada indivíduo na população tem dois atributos:

1. Rank de não dominância (irank);2. Distância de Agrupamento (Crowding Distance) (idistance).

Uma ordem parcial ≺n é definido por:


i≺n se (irank < jrank)

ou

((irank = jrank) e (idistance > jdistance))

(3-4)

Para duas soluções entre diferentes fronteiras não-dominadas, este modelo dápreferência a escolha da solução com melhor rank, ou seja, menor rank, caso contrário, éescolhida a solução localizada em uma região de menor aglomeração [9].

Finalizado o processo de classificação, os indivíduos pertencentes a primeirafronteira são não dominados e dominam os indivíduos pertencentes as demais fronteiras.Na etapa seguinte os indivíduos são selecionados para compor a próxima geração a partirdos pertencentes a primeira fronteira, até completar a nova população. Se uma fronteiranão puder ser totalmente inserida na população o algoritmo usa como critério a distânciade agrupamento para escolher quais indivíduos estarão na nova população [9]. A Figura3.2 exemplifica o processo descrito no NSGA-II.

Figura 3.2: Procedimento NSGA-II.

3.2.2 Algoritmo Evolutivo da Força de Pareto II (SPEA-II)

Proposto por Zitzler [47] o algoritmo SPEA-II é uma abordagem evolutiva mul-tiobjetivo que inclui o conceito de elitismo, não presente no NSGA-II. O algoritmo, assimcomo o NSGA-II, utiliza duas populações P e P. A população P, denotada populaçãoexterna, armazena apenas as soluções não-dominadas encontradas pelo algoritmo. É for-necido como parâmetro o tamanho da população P, denotado como Nnext . As populaçõesP e P, em cada iteração t = 1,2, · · · ,Niter, são denotadas com Pt e Pt , respectivamente[47].

O algoritmo começa com a criação de uma população inicial aleatória P0 e umapopulação externa P0 vazia. A cada iteração t, é calculada a função de aptidão para cadasolução i em Popt = Pt ∪Pt . No cálculo da função de aptidão, são usados os conceitos de


dominância e de densidade, que será definida a seguir. O objetivo é minimizar o valor dafunção de aptidão. Quanto menor o valor da função de aptidão de um indivíduo, melhor éa adaptação do indivíduo [47]. A força do indivíduo, denotada por Si, é dada pelo númerode soluções que ele domina:

Si = |{ j, j ∈ Popt ∧ i� j}|. (3-5)

O número de soluções em Popt dominadas pela solução i é representado pelovalor i. Logo, as soluções que não dominam nenhuma outra possui o valor de Si iguala zero. O valor de aptidão bruto do indivíduo, denotado por Ri, também é calculadosomando as forças de todos os indivíduos que o dominam, conforme apresentada pelaEquação (3-6) [47]. O valor de aptidão bruto Ri das soluções não dominadas é igual azero enquanto as soluções dominadas tem o valor Ri alto.

Ri = ∑j∈Popt , j�i

S j (3-6)

A densidade do indivíduo e uma função decrescente em relação ao k-ésimovizinho mais próximo. Para os casos onde existem muitas soluções não dominadas, o valorSi aproxima-se de zero para todas as soluções. Assim, é necessário haver um mecanismopara privilegiar soluções dentre as não dominadas chamado fator de densidade, denotadopor Di, mostrado na Equação (3-7) [47].

Di =1

distki j +2

(3-7)

Para cada indivíduo i, as distâncias (no espaço dos objetivos) entre i e todos osindivíduos j ∈ Popt são calculadas e armazenadas em uma lista. Logo após a ordenaçãoda lista em ordem crescente, o k-ésimo elemento representa o termo distk

i j. É sugeridopara k o valor k =

√|Popt |. Enfim, a aptidão final para cada solução i em Popt , denotada

Fi, é dada pela Equação (3-8).

Fi = Ri +Di (3-8)

O método de seleção do SPEA-II primeiramente copia todos os indivíduos nãodominados de Pt e de Pt para a população externa da próxima geração Pt+1. Neste cenário,existem três situações possíveis:

1. O número de indivíduos no conjunto não dominado é exatamente o mesmo dapopulação externa (|Pt+1|= Next);

2. O número de indivíduos no conjunto não dominado é menor que o tamanho dapopulação externa (|Pt+1|< Next);


3. O número de indivíduos no conjunto não dominado é menor que o tamanho dapopulação externa (|Pt+1|> Next);

No primeiro caso, o processo de seleção está completo. No segundo caso, sãocopiados para a nova população externa, os melhores Next−|Pt+1| indivíduos dominados,incluindo a população regular e a população externa na geração anterior. No terceiro caso,utiliza-se um algoritmo de corte. O objetivo do algoritmo de corte do SPEA-II é restringiro tamanho de Pt+1 a Next soluções. Em cada iteração, é removida a solução cuja distânciapara seu vizinho mais próximo seja menor dentre as distâncias existentes. Em caso deempate, calcula-se a segunda menor distância e assim sucessivamente [47]. A soluçãoi é escolhida para ser removida se i ≤d j para todo j ∈ Pt+1 satisfazendo as seguintescondições:

i≤d j⇔ ∀ 0 < k < |Pt+1| : σki = σ

kj ∨

∃ 0 < k < |Pt+1| :[(∀ 0 < l < k : σ

li = σ

lj)∧σ

ki = σ

kj

](3-9)

A Figura 3.3 apresenta à esquerda, um conjunto de soluções pertencentes àpopulação externa Pt+1. À direita, após a aplicação do algoritmo de corte, algumassoluções são eliminadas. Além disso, o algoritmo de corte garante que as soluçõesextremas para cada objetivo sejam mantidas.

Figura 3.3: Algoritmo de Corte do algoritmo SPEA-II [47].

3.2.3 Hipervolume

A comparação de desempenho de um ou vários métodos de otimização multiob-jetivo é uma tarefa complexa. Duas metas da otimização multiobjetivo são: convergência ediversidade das soluções encontradas [10]. Logo, existem métricas que ajudam na análisedestas metas com destaque para as métricas:


1. Taxa de erro;2. Distância geracional;3. Métrica de cobertura;4. Espaçamento;5. Espalhamento;

Uma métrica bastante usada na avaliação de algoritmos multiobjetivos é oindicador de hipervolume (HV) [10]. No HV, calcula-se o volume da região coberta entreos pontos das soluções na fronteira de Pareto P e um ponto de referência W. Para cadasolução i ∈ P, constitui-se um hipercubo, vi com referência a um ponto W. Este ponto dereferência pode ser encontrado construindo-se um vetor com os piores valores da funçãoobjetivo. A união de todos os hipercubos encontrados é o resultado da métrica sendoque quanto maior o valor do HV melhor. Um alto valor de HV indica que houve umelevado espalhamento entre as soluções de P e indica que houve também uma melhorconvergência. O HV é calculado conforme Equação (3-10) e ilustrado na Figura 3.4representado pela área em cinza.

HV = ∑i∈P

vi (3-10)

Figura 3.4: Hipervolume gerado pelo conjunto de soluções nãodominadas para as funções F1 e F2

CAPÍTULO 4Materiais e Métodos

4.1 Dados do Trigo

Todas as amostras são de trigo de grão inteiro, obtidos a partir de materialvegetal de produtores ocidentais canadenses. Os dados de referência foram determinadosno Laboratório de Pesquisa de Grãos, em Winnipeg. Os dados de referência são: aconcentração de proteína (%); teste de peso (kg/hl); PSI (textura do grão de trigo)(%); absorção de água por farinografia (%), tempo de desenvolvimento de massa porfarinografia (em minutos), e índice de tolerância à mistura por farinografia (UnidadesBrabender). O conjunto de dados para o estudo de calibração multivariada consiste de 775espectros VIS-NIR de amostras de todo o grão de trigo, que foram utilizados como dadosshoot-out em 2008 na Conferência Internacional Reflectância Difusa (http://www.idrc-chambersburg.org/shootout.html).

A concentração de proteína foi escolhida como a propriedade de interesse.Os espectros foram adquiridos na faixa de 400-2500nm, com uma resolução de 2nm.No presente trabalho, a região NIR na faixa de 1100-2500nm foi empregado. A fimde eliminar as características indesejáveis, foram calculadas a primeira derivada dosespectros usando um filtro Savitzky-Golay com um polinômio de 2a ordem e uma janelade 11-pontos. Mas apenas os dados referentes a concentração de proteína foram usadasnestes testes.

O algoritmo de Kennard-Stone (KS) [25] foi aplicada ao espectro resultante paradividir os dados em conjuntos de validação, calibração e predição de amostras 389, 193e 193, respectivamente, contendo cada conjunto 690 variáveis independentes. O conjuntode validação foi utilizado para orientar a seleção de variáveis em APS-MLR, MONO-GA-MLR, NSGA-II-MLR e SPEA-II-MLR.

O conjunto de predição foi apenas utilizado na avaliação do desempenho finaldos modelos resultantes MLR. No estudo de PLS, os conjuntos de calibração e devalidação foram unidos num único conjunto de modelagem, o qual foi utilizado noprocedimento de validação cruzada leave-one-out. O número de variáveis latentes foiselecionado com base no erro de validação cruzada, utilizando o critério de teste F de

4.2 Ferramentas e Ambiente 36

Haaland e Thomas com α = 0,25, tal como sugerido por Haaland [18]. O conjunto depredição só foi empregado na avaliação final do modelo de PLS.

A Figura 4.1 apresenta o espectro derivado das amostras de trigo após a aplicaçãodo filtro Savitzky-Golay com um polinômio de 2a ordem e uma janela de 11-pontos.

Figura 4.1: Espectro das amostras de trigo após filtragem.

4.2 Ferramentas e Ambiente

Para execução dos algoritmos propostos NSGA-II-MLR e SPEA-II-MLR foiutilizado o software Matlab na versão 7.10 (R2010a). O código base do NSGA-II foiobtido no seguint link http://www.mathworks.com/matlabcentral/fileexchange/10429e o código base do SPEA-II foi obtido no seguinte link http://pcdomino.rts.tu-harburg.de/Inter/lectureE14.nsf/720dc6235ba3559b41256a1d002a1be2/7b3ab9df2e63ca27c125739f0054fcd3?OpenDocument.

A seguir serão apresentados as adaptações realizadas nos algoritmos NSGA-IIe SPEA-II necessárias para a aplicação destes algoritmos na seleção de variáveis emproblemas de calibração multivariada. A primeira adaptação foi alterar a representaçãocromossomial de números reais para binária. Assim, cada gene passa a representar umavariável do conjunto de dados de variáveis independentes. Neste cenário, cada gene comvalor igual a 1 indica a seleção da variável para inclusão da mesma no modelo matemáticoe o gene com valor igual a 0 indica a não seleção desta variável.

O Algoritmo (4.1) apresenta a função de inicialização da população dos algorit-mos NSGA-II-MLR e SPEA-II-MLR utilizando a representação cromossomial binária.

4.2 Ferramentas e Ambiente 37

Algoritmo 4.1: Inicialização da PopulaçãoEntrada: Tamanho da População (nind),Dados de Interesse (Xcal,Ycal,Xval,Yval)Saída: População (P), Fitness (F)

1 Início/* Calculando o número maximo de genes no cromossomo */

2 totalVars← obterNumeroDeColunas(Xcal);/* Número mínimo de genes ’1’ no cromossomo */

3 minVars← 1;/* Número máximo de genes ’1’ no cromossomo */

4 maxVars← nind;5 para i← 1 até nind faça

/* Preencher cada gene do cromossomo com zero */

6 P[i]← gerarGenesZeros(totalVars);/* Calcular quantos genes ’1’ serão criados no intervalo

entre minVars e maxVars */

7 numVars← obterInteiroAleatório(minVars, minVars);/* Gerar a quantidade de genes ’1’ calculada em numVars em

posições aleatórias no intervalo entre 1 a totalVars

*/

8 P[i]← gerarGenesUnsAleatoreamente(numVars);/* Calcular Fitness */

9 F[i]← avaliarObjetivos(P[i], totalVars,Xcal,Ycal,Xval,Yval);

10 fim11 fim

Os algoritmos serão executados com população de 100 indivíduos, com 30, 50e 100 gerações. O método de seleção dos pais para reprodução será o torneio binário e ooperador de mutação será o Flip, tanto para o NSGA-II-MLR como para o SPEA-II-MLR.

Para o NSGA-II-MLR serão utilizados a probabilidade de mutação de 50%,o operador de crossorver de um ponto e probabilidade de crossover de 90%. Serãoutilizados para SPEA-II-MLR a probabilidade de mutação de 50% para o indivíduo ede 5% para cada gene do cromossomo, o operador de crossorver será o de um ponto comprobabilidade de 50% e sobre os indivíduos resultados será aplicado o crossover uniformecom probabilidade de 100%.

É apresentado no Algoritmo (4.2) a função de avaliação dos objetivos 1) minimi-zar o erro residual entre a concentração predita pelo modelo de regressão e a concentraçãoreal de proteína no grão e 2) minimizar a quantidade de variáveis selecionadas para o mo-

4.3 Decisor Multiobjetivo 38

delo de calibração utilizada pelos algoritmos NSGA-II-MLR e SPEA-II-MLR.

Algoritmo 4.2: Avaliação dos ObjetivosEntrada: Indivíduo (ind),Total de variáveis (totalVars),Dados de Interesse (Xcal,Ycal,Xval,Yval)Saída: Fitness (F)

1 Início/* Identificar as posições dos genes ’1’ no indivíduo */

2 selVars← índicesUns(ind);/* Calcular coeficiêntes de regressão conforme Equação (2-6)

*/3 β← calcularBeta(Xcal,Ycal,selVars);

/* Calcular a regressão linear múltipla conforme Equação (2-4)*/

4 Ypred ← mlr(Xval, β,selVars);/* Calcular o RMSEP entre o valor predito Ypred e valor real

Yval conforme Equação (2-3) */

5 F1← rmsep(Yval, Ypred,selVars);/* Calcular o somatório do número variáveis selecionadas no

indivíduo (genes 1) */

6 F2← contarUns(ind);7 fim

4.3 Decisor Multiobjetivo

O algoritmo NSGA-II-MLR apresenta um conjunto de soluções para o problemamultiobjetivo em sua primeira fronteira e o algoritmo SPEA-II-MLR apresenta umconjunto de soluções em sua população final. Para ajudar a escolher uma solução dentrodesses conjuntos, foi aplicado o teste de Wilcoxon Signed-Rank como um tomador dedecisão multiobjetivo.

Wilcoxon Signed-Rank é um teste de hipóteses não paramétrico usado quandose comparam duas amostras relacionadas em uma única amostra para avaliar se o rankdas médias populacionais são diferentes. Ele pode ser usado como alternativa ao teste t

pareado de Student para amostras dependentes quando a população não pode ser assumidacomo uma distribuição normal [34].

Seja Yi= yi

1,yi2, · · · ,yi

n o i-ésimo valor estimado do teor de proteína e εi a dife-rença entre o valor estimado Yi e o valor real Y e ε j a diferença entre o valor estimadoY j e o valor real Y. O algoritmo do tomador de decisão multiobjetivo no primeiro passoescolhe o cromossomo do conjunto de soluções com o menor valor RMSEP calculadoa partir do conjunto de validação. Deseja-se avaliar se o εi obtido com k variáveis não

4.3 Decisor Multiobjetivo 39

tem diferença significativa com ε j obtido com k− p variáveis. Isto é, o menor númerode variável sem alterar a capacidade preditiva. A hipótese nula é formulada por um testede hipótese de dois lados em que εi− ε j pertencem a uma distribuição cuja mediana ézero, isto é, a diferença não pode ser significativa [34]. A função para tomada de decisãomultiobjetivo utilizada pelos algoritmos NSGA-II-MLR e SPEA-II-MLR é mostrada noAlgoritmo (4.3).

Algoritmo 4.3: Decisor MultiobjetivoEntrada: Conjunto de Soluções (solucoes), Fitness ( f itness),Dados de Interesse (Xcal,Ycal,Xval,Yval), Nível de significância (α)Saída: Solução Sugerida (solucaoEscolhida)

1 Início2 numeroSolucoes← contar(solucoes);3 solucaoi← solucoes[1];

/* Calcular β conforme Equação (2-6) */

4 βi← calcularBeta(Xcal,Ycal,solucaoi);/* Calcular a MLR conforme Equação (2-4) */

5 Yi← mlr(Xval, βi,solucaoi);

/* Calcular o erro residual entre o valor estimado Yi e valor

real Yval conforme Equação (2-8) */

6 εi← Yval− Yi;

7 para j← 2 até numeroSolucoes faça8 solucao j← solucoes[ j];9 β j← calcularBeta(Xcal,Ycal,solucao j);

10 Y j← mlr(Xval, βj,solucao j);

11 ε j← Yval− Y j;

/* Calcular se a diferença a nível α de significância entre

εi e ε j */

12 hipotese← wilcoxonSignedRank(εi,ε j,α)13 se (hipotese = nula e (contarUns(solucoes j)< contarUns(solucoesi))

então14 εi← ε j;15 solucaoi← solucoes j;

16 fim17 fim18 solucaoEscolhida← solucaoi;

19 fim

CAPÍTULO 5Resultados e Discussões

Neste capítulo são apresentados os resultados obtidos com os algoritmos NSGA-II-MLR e SPEA-II-MLR. Os algoritmos foram aplicados ao problema de seleção devariáveis em calibração multivariada descrito no Capítulo 2 sobre os dados do trigo napredição da concentração de proteína. Para a execução dos algoritmos foram usados osparâmetros apresentados na Tabela 5.1 com 30 repetições para cada número de gerações.

Tabela 5.1: Parâmetros de Configuração do NSGA-II-MLR eSPEA-II-MLR.

NSGA-II-MLR SPEA-II-MLR

Tamanho da População 100 100

Numero de Gerações 30, 50 e 100 30, 50 e 100

Operador de Seleção Torneio Binário Torneio Binário

Operador de Mutação Flip Flip

Probabilidade de Mutação 0,5 0,5 para o indivíduo0,05 para o gene

Operador de Crossover Crossover de Um Ponto Crossover UniformeCrossover de Um Ponto

Probabilidade de Crossover 0,9 0,5 e 1,0

A Seção 5.1 apresenta os resultados obtidos pelos algoritmos clássicos de cali-bração. As seções seguintes detalham os resultados obtidos para cada um dos algoritmospropostos.

5.1 Resultados dos algoritmos PLS, APS-MLR e MONO-AG-MLR

Primeiramente apresenta-se os resultados dos algoritmos clássicos PLS, APS-MLR e MONO-AG-MLR. Esses resultados são mostrados na Tabela 5.2. Como pode-sever, os resultados são similares para esses algoritmos em termos dos valores de RMSEP.

5.1 Resultados dos algoritmos PLS, APS-MLR e MONO-AG-MLR 41

Todavia, o MONO-AG-MLR usa um número expressivo de variáveis quando comparadocom o APS-MLR. Esses resultados podem ser explicados pelo fato do MONO-AG-MLRusar apenas um objetivo, o RMSEP no conjunto de validação. Na prática o APS-MLR éusado porque ele utiliza menos variáveis do que o MONO-AG-MLR e PLS. Vale ressaltarque o PLS usa todas as variáveis originais para construir as novas variáveis latentes.

Tabela 5.2: Resultados das técnicas tradicionais PLS, APS-MLR eMONO-AG-MLR

RMSEP Número de variáveis

PLS 0,21 15∗

APS-MLR 0,20 13#

MONO-AG-MLR 0,21 146#

Precisão dos dados no conjunto de predição: 10,2 à 16,2% m/m. ∗variáveis latentes, #variáveis originais.

O algoritmo genético clássico é projetado para minimizar a mesma função doAPS, isto é, a Equação RMSEP (2-3). No entanto, assim que reduz o RMSEP, maisvariáveis são incluídas no modelo. Por exemplo, usando os mesmos dados da Seção 4.1,o AG monoobjetivo foi executado com número diferente de variáveis máximas a seremincluídas. Os resultados são apresentados na Figura 5.1. Pode-se notar que o RMSEP éreduzido tão logo mais variáveis são incluídas no modelo. Por outro lado se o númerode variáveis é grande, a Equação da pseudo-inversa (2-6) têm um mal condicionamentoe, consequentemente, uma generalização ruim em novas amostras. Nas situações em quepequenas perturbações relativas nos valores originais induzem grande variaçõoes relativasna solução os sistemas dizem-se mal condicionados. Como pode ser visto na Figura 5.1,o RMSEP e o número de variáveis são objetivos conflitantes.

Figura 5.1: Comportamento RMSEP com diferentes números má-ximos de variáveis no algoritmo genético monoobje-tivo.

5.2 Resultados com 30 gerações 42

5.2 Resultados com 30 gerações

Os resultados apresentados a seguir referem-se a execução dos algoritmos pro-postos com 30 gerações. A Figura 5.2 mostra as fronteiras de Pareto obtidas pelo NSGA-II-MLR (Figura 5.2(a)) e a população final resultante do SPEA-II-MLR (Figura 5.2(b))no conjunto de validação. Como pode-se observar, ambos os algoritmos minimizaram osdois objetivos propostos: número de variáveis e RMSEP. No entanto, o SPEA-II-MLRobteve uma melhor distribuição das soluções no espaço de busca.

Conforme discutido por Deb [9], uma boa métrica para comparar algoritmosmultiobjetivo é a medida hipervolume que calcula a diversidade das soluções obtidapelos algoritmos. O hipervolume médio do NSGA-II-MLR foi 867.16 e para o SPEA-II-MLR foi 985.02. Esses resultados mostram que o SPEA-II-MLR obteve uma modestasuperioridade em relação ao NSGA-II-MLR. Também nessas figuras apresenta-se assoluções escolhidas pelo decisor para ambos os algoritmos. É possível notar que o métodoproposto escolheu soluções que ponderam entre os objetivos considerados, descartandosoluções que possuem um baixa aptidão em um dos objetivos.

As soluções obtidas pelo decisor em cada uma das execuções serão utilizadasa partir deste ponto, a fim de calcular a medida RMSEP no conjunto de predição. Esteconjunto não foi utilizado em nenhuma fase dos algoritmos propostos, sendo usado paramedir a capacidade de generalização das soluções obtidas. A Tabela 5.3 apresenta oresumo dos resultados do NSGA-II-MLR e SPEA-II-MLR. Os resultados foram obtidosnas 30 execuções de cada um dos algoritmos. Vale notar que os dados referem-se a soluçãoescolhida pelo decisor em cada execução aplicada no conjunto de predição.

(a) (b)

Figura 5.2: Fronteiras de Pareto no conjunto de validação geradaspelo NSGA-II-MLR (a) e a população final resultantedo SPEA-II-MLR (b) com 30 gerações

Em geral, o número de variáveis selecionadas são menores no SPEA-II-MLRque no NSGA-II-MLR. O NSGA-II-MLR encontrou soluções com 23 variáveis enquantoo SPEA-II-MLR encontrou soluções com apenas 15 variáveis.


Tabela 5.3: Resultado médio das soluções escolhidas pelo métododecisor multiobjetivo dos algoritmos NSGA-II-MLR eSPEA-II-MLR no conjunto de predição.


RMSEP No Variáveis RMSEP No Variáveis

Média 0,08 23 0,12 15

Menor 0,06 (28#) 19 (0,08+) 0,08 (17#) 10 (0,16+)

Maior 0,13 (20#) 29 (0,07+) 0,18 (14#) 19 (0,10+)#número de variáveis selecionadas, +RMSEP.

Tal como pode-se perceber o NSGA-II-MLR e SPEA-II-MLR possuem uma pe-quena diferença na média RMSEP de aproximadamente 0.03. No entanto, o SPEA-II-MLR tem melhores resultados em termos de número de variáveis selecionadas, selecio-nando em média 8 variáveis a menos do que o NSGA-II-MLR. O uso de menos variáveispode ser observado na Figura 5.3.

(a) (b)

Figura 5.3: Variáveis selecionadas pelo NSGA-II-MLR (a) e a po-pulação final resultante do SPEA-II-MLR (b) com 30gerações dispostas no espectro.

A Figura 5.3 apresenta o espectro da primeira amostra do conjunto de calibraçãoe as variáveis selecionadas pelo NSGA-II-MLR (Figura 5.3(a)) e SPEA-II-MLR (Figura5.3(b)). As variáveis selecionadas foram obtidas a partir do cromossomo resultante dodecisor multiobjetivo que possui número de variáveis e RMSEP mais próximos da médiacalculada para cada objetivo (ver Tabela 5.3).

Apesar do SPEA-II-MLR selecionar menos variáveis, os dois algoritmos cobrema mesma região espectral, como pode ser visto na Figura 5.3, Essa semelhança indica quepossivelmente essas regiões da observação onde as variáveis forão selecionadas são asmais promissoras para usar no espectrofotômetro. Na prática, esses resultados implicamem um menor número de comprimentos de onda medidos no espectrofotômetro paraquantificar o teor de proteínas em amostras reais de trigo. A Tabela 5.4 apresenta as


posições do espectro das variáveis selecionadas pelo NSGA-II-MLR (Figura 5.3(a)) eSPEA-II-MLR (Figura 5.3(b)).

Tabela 5.4: Variáveis selecionadas pelo NSGA-II-MLR e SPEA-II-MLR.

RMSEP Número de variáveis Variáveis Selecionadas

NSGA-II-MLR 0,08 23

29; 43; 64; 117; 118; 150157; 204; 231; 283; 286; 333;349; 380; 426; 446; 511; 538;597; 613; 637; 640; 664

SPEA-II-MLR 0,12 1511; 26; 39; 42; 83; 101165; 180; 255; 333; 367; 484;589; 679; 688


Alterado o número de gerações para 50, tem-se na Figura 5.4 as fronteirasde Pareto obtidas pelo NSGA-II-MLR (Figura 5.4(a)) e a população final resultantedo SPEA-II-MLR (Figura 5.4(b)) no conjunto de validação. Neste cenário, é possívelobservar que não houve evolução significativa dos resultados do NSGA-II-MLR com 30gerações. No entanto, nos resultados obtidos pelo SPEA-II-MLR percebe-se uma reduçãosignificativa no número de variáveis selecionadas, com um RMSEP similar, conformeapresentado na Tabela 5.5.

(a) (b)

Figura 5.4: Fronteiras de Pareto geradas pelo NSGA-II-MLR (a) ea população final resultante do SPEA-II-MLR (b) com50 gerações

O comportamento geral entre os algoritmos NSGA-II-MLR e SPEA-II-MLRcom 50 gerações manteve-se equivalente ao comportamento com 30 gerações. A distri-


buição das soluções calculada pelo hipervolume médio foi de 901,70 para NSGA-II-MLRe de 1383,96 para o SPEA-II-MLR. Observa-se através desses valores que houve uma me-lhoria na diversidade das soluções em relação aos testes com 30 gerações para ambos osalgoritmos. Esses resultados mostram que o SPEA-II-MLR obteve uma evolução maisexpressiva do que o NSGA-II-MLR na cobertura do espaço de busca após o incrementode gerações.

Novamente, as soluções obtidas pelo decisor em cada uma das execuções serãoutilizadas a partir deste ponto, a fim de calcular a medida RMSEP no conjunto depredição. A Tabela 5.5 apresenta o resumo dos resultados do NSGA-II-MLR e SPEA-II-MLR obtidos nas 30 execuções de cada um dos algoritmos.




Média 0,08 21 0,12 11

Menor 0,06 (24#) 12 (0,17+) 0,06 (14#) 6 (0,23+)


As variáveis selecionadas foram obtidas a partir do cromossomo resultante dodecisor multiobjetivo que possui número de variáveis e RMSEP mais próximos da médiacalculada para cada objetivo (ver Tabela 5.5). Na Figura 5.5 é apresenta o espectro daprimeira amostra do conjunto de calibração e as variáveis selecionadas pelo NSGA-II-MLR (Figura 5.5(a)) e SPEA-II-MLR (Figura 5.5(b)). A cobertura da região espectralpor ambos os algoritmos permanece a mesma comparado com os testes com 30 gerações,como pode ser visto na Figura 5.5, mesmo o número de variáveis selecionadas pelo SPEA-II-MLR ser menor e a medida hipervolume ser maior.


(a) (b)


A Tabela 5.6 apresenta as posições do espectro das variáveis selecionadas peloNSGA-II-MLR (Figura 5.5(a)) e SPEA-II-MLR (Figura 5.5(b)).

Tabela 5.6: Variáveis selecionadas pelo NSGA-II-MLR e SPEA-II-MLR


NSGA-II-MLR 0,08 21

28; 39; 82; 86; 134; 136;149; 242; 256; 257; 330; 344;373; 412; 449; 464; 581; 592;617; 640; 661

SPEA-II-MLR 0,12 1127; 40; 67; 135; 138; 369428; 442; 471; 596; 596; 663


Executado os algoritmos NSGA-II-MLR e SPEA-II-MLR com 100 geraçõescada, é possível observar que existiu melhoria dos resultados em ambos os algoritmosem relação aos resultados com 50 gerações. É apresentado na Figura 5.6 as fronteirasde Pareto obtidas pelo NSGA-II-MLR (Figura 5.6(a)) e a população final resultante doSPEA-II-MLR (Figura 5.6(b)) no conjunto de validação. Ainda em comparação com ostestes com 50 gerações, o NSGA-II-MLR reduziu em média 3 variáveis selecionadas,porém mantendo o resultado para o RMSEP similar. O SPEA-II-MLR reduziu apenasuma variável em média, no entanto, reduziu 0,03 em média o RMSEP. Esses resultadospodem ser observados na Tabela 5.7.


(a) (b)

Figura 5.6: Fronteiras de Pareto geradas pelo NSGA-II-MLR (a) ea população final resultante do SPEA-II-MLR (b) com100 gerações

Novamente o comportamento geral entre os algoritmos NSGA-II-MLR e SPEA-II-MLR manteve-se equivalente ao comportamento com 30 e 50 gerações. Todavia, épercebido através do hipervolume médio calculado, 936.70 para o NSGA-II-MLR e1432.24 para o SPEA-II-MLR, que a diversidade das soluções obteve uma melhoriaainda maior. É possível notar nesses resultados que o SPEA-II-MLR foi mais eficientena cobertura do espaço de busca quando comparado ao NSGA-II-MLR. Na Tabela 5.7 éapresentado o resumo dos resultados do NSGA-II-MLR e SPEA-II-MLR obtidos nas 30execuções de cada um dos algoritmos. Vale lembrar que as soluções obtidas pelo decisorem cada uma das execuções serão utilizadas a partir deste ponto, a fim de calcular amedida RMSEP no conjunto de predição.




Média 0,08 18 0,09 10

Menor 0,06 (24#) 12 (0,17+) 0,07 (11#) 6 (0,18+)


A Figura 5.7 apresenta o espectro da primeira amostra do conjunto de calibraçãoe as variáveis selecionadas pelo NSGA-II-MLR (Figura 5.7(a)) e SPEA-II-MLR (Figura5.7(b)). O cromossomo resultante do decisor multiobjetivo que possui número de variá-veis e RMSEP mais próximos da média calculada para cada objetivo foi usado para obteras variáveis selecionadas apresentadas na Tabela 5.7. Pode ser ser visto na Figura 5.7 que

5.5 Considerações Finais 48

a cobertura da região espectral por ambos os algoritmos permanece a mesma para todasas gerações 30, 50 e 100.

(a) (b)


É apresentado na Tabela 5.8 as posições do espectro das variáveis selecionadaspelo NSGA-II-MLR (Figura 5.7(a)) e SPEA-II-MLR (Figura 5.7(b)).

Tabela 5.8: Variáveis selecionadas pelo NSGA-II-MLR e SPEA-II-MLR


NSGA-II-MLR 0,08 1829; 41; 108; 114; 138; 142;144; 356; 373; 374; 385; 394;478; 497; 640; 682; 686

SPEA-II-MLR 0,09 1027; 39; 109; 117; 119; 135141; 261; 598; 614

5.5 Considerações Finais

Analisando os resultados obtidos pelos algoritmos NSGA-II-MLR e SPEA-II-MLR inferimos que SPEA-II-MLR tem um melhor comportamento. Além de menosvariáveis selecionadas e pequena diferença no erro de predição (RMSEP), o SPEA-II-MLR tem também um hipervolume superior ao NSGA-II-MLR o que mostra que estealgoritmo tem uma melhor cobertura do espaço de busca. A melhor cobertura pode serimportante em outros problemas de calibração, quando a medida espectroscópica podeser cara. Neste casos, o especialista pode escolher uma solução com um erro de prediçãoum pouco maior, porém com poucas variáveis.

5.5 Considerações Finais 49

Comparados os resultados obtidos pelo SPEA-II-MLR com os algoritmos clás-sicos, pode-se notar que a formulação multiobjetivo resolve o problema do número exces-sivo de variáveis da abordagem monoobjetivo. Enquanto o MONO-AG-MLR selecionou146 variáveis com um erro de predição de 0.21 o SPEA-II-MLR selecionou apenas 10variáveis com um erro de predição de 0.09. Este resultado mostra que o problema deoverfitting relacionado ao MONO-AG-MLR foi minimizado com a formulação multiob-jetivo, visto que os modelos de predição obtidos pelo NSGA-II-MLR e SPEA-II-MLRpossuem poucas variáveis e um menor erro no conjunto de predição. Em comparaçãocom o APS-MLR, o SPEA-II-MLR também utilizou um número menor de variáveis, emmédia (APS-MLR utilizou 13 variáveis). O resultado RMSEP médio do SPEA-II-MLRfoi 57% melhor do que o PLS e MONO-AG-MLR e 55% melhor do que o APS-MLR.

Figura 5.8: Amostras do grupo de predição.

A Figura 5.8 apresenta a concentração de proteínas real versus a concentraçãopredita pela solução do SPEA-II-MLR com 100 gerações e o menor valor RMSEP. Emuma predição perfeita, os pontos estariam dispostos sobre a reta. O erro de predição podeser medido pela distância entre cada ponto e a reta. Como pode ser visto, a predição dosvalores são próximos dos valores reais.

CAPÍTULO 6Conclusão

Neste trabalho foi proposto uma formulação do algoritmo genético multiobjetivopara o problema de seleção de variáveis em problemas de calibração. Um estudo decaso baseado na concentração de proteína de trigo foi apresentado. Tal conjunto possuiinicialmente 690 variáveis e 389 amostras de calibração. A natureza deste conjunto dedados implica em variáveis colineares entre si levando o sistema de equações à apresentarproblemas de multicolinearidade. Foi possível mostrar que a formulação monoobjetivoleva o algoritmo genético a um número excessivo de variáveis selecionadas.

Neste cenário, foi proposto o uso dos algoritmos NSGA-II-MLR e SPEA-II-MLR para selecionar as variáveis com baixa colinearidade, maior capacidade preditivado composto de interesse e baixo número de variáveis. Os resultados obtidos demonstramque enquanto a formulação com algoritmo genético monoobjetivo usa um grande númerode variáveis com um erro de predição similar aos algoritmos clássicos, os algoritmosmultiobjetivos propostos usam menos variáveis com um menor erro de predição.

Quando comparado com os algoritmos clássicos como PLS, APS-MLR eMONO-AG-MLR, os resultados obtidos pelos algoritmos NSGA-II-MLR e SPEA-II-MLR foram melhores em todos os casos analisados. No estudo de caso, o SPEA-II-MLRmelhorou a predição da concentração de proteína em grãos de trigo em 57% comparadocom PLS e MONO-AG-MLR e 55% comparado ao APS-MLR utilizando apenas 10 va-riáveis.

As principais contribuições do trabalho incluem: 1) uma modelagem mais ade-quada para o problema de seleção de variáveis no domínio original dos dados em sistemaslineares considerando além do erro de predição, o número de variáveis em uma aborda-gem multiobjetivo; 2) a elaboração de um decisor que escolhe uma solução dentro doconjunto de soluções do espaço multiobjetivo.

É importante destacar que mesmo os algoritmos NSGA-II-MLR e SPEA-II-MLR indicar uma solução escolhida pelo decisor multiobjetivo dentro do conjunto desoluções, o analista dos dados pode optar por uma solução diferente da sugeria pelodecisor multiobjetivo. Na formulação do algoritmo genético monoobjetivo é fornecidaapenas uma possível solução.

51

Como estudos futuros, é sugerida a inclusão de um terceiro objetivo, a sensibili-dade a ruído. Outros estudos sugerem que os algoritmos NSGA-II e SPEA-II não operamadequadamente para problemas com três ou mais objetivos. Logo, é interessante analisaro comportamento de algoritmos que permitem a inclusão de um maior número de objeti-vos. Além disso, propõem-se o desenvolvimento de mecanismos de reprodução que levamem consideração as características particulares dos problemas de calibração, tais como amulticolinearidade.

Referências Bibliográficas

[1] ABDI, H. Partial least squares (pls) regression. Encyclopedia of Social Sciences

Research Methods, 3(6):1–7, 2003.

[2] ALIN, A. Multicollinearity. Wiley Interdisciplinary Reviews: Computational Statistics,

2010.

[3] ARAÚJO, M. C. U.; SALDANHA, T. C. B.; GALVÃO, R. K. H.; YONEYAMA, T.; CHAME,

H. C.; VISANI, V. The successive projections algorithm for variable selection in

spectroscopic multicomponent analysis. Chemometrics and Intelligent Laboratory

Systems, 57(2):65 – 73, 2001.

[4] BEEBE, K.; PELL, R.; SEASHOLTZ, M. Chemometrics: a practical guide. Wiley-

Interscience series on laboratory automation. Wiley, 1998.

[5] BEKELE, E. G.; NICKLOW, J. W. Multi-objective automatic calibration of SWAT

using NSGA-II. Journal of Hydrology, 341(3-4):165–176, Aug. 2007.

[6] CHONG, IL-GYO.; JUN, C.-H. Performance of some variable selection methods

when multicollinearity is present. Chemometrics and Intelligent Laboratory Sys-

tems, v. 78, n. 1-2, (pp. 103-112), 2005.

[7] DAVIS, L. Handbook of genetic algorithms. VNR computer library. Van Nostrand

Reinhold, 1991.

[8] DAWKINS, R. A Escalada do monte improvável: uma defesa da teoria da

evolução. Companhia das Letras, 1996.

[9] DEB, K.; PRATAP, A. A.-S. . M. T. A Fast and Elitist Multiobjective Genetic

Algorithm: NSGA-II. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION,

VOL. 6, NO. 2, 2002.

[10] DEB, K.; KALYANMOY, D. Multi-Objective Optimization Using Evolutionary Algo-

rithms. Wiley, 1 edition, June 2001.


[11] DRAPER, R. N. & SMITH, H. Applied regression analysis. Willey series and

probability and statistics, 1998.

[12] EFSTRATIADIS, A. & KOUTSOYIANNIS, D. One decade of multi-objective calibra-

tion approaches in hydrological modelling: a review. Hydrological Sciences Jour-

nal, 55(1):58–78, 2010.

[13] FERREIRA, M. A. M. C.; ANTUNES, A. M.; MELGO, M. S.; VOLPE, P. L. O. Quimi-

ometria I: calibração multivariada, um tutorial. Química Nova, 22:724 – 731, 09

1999.

[14] GALVÃO, R. K. H. A variable elimination method to improve the parsimony of

MLR models using the successive projections algorithm. Chemometrics and

Intelligent Laboratory Systems, Volume 92, Issue 1, (pp 83-91), 2008.

[15] GELADI, P.; KOWALSKI, B. R. Partial least-squares regression: a tutorial. Analy-

tica Chimica Acta, 185(0):1 – 17, 1986.

[16] GOLDBERG, D. E. Genetic algorithms in search, optimization, and machine

learning. Addison-Wesley, New York, 1989.

[17] GUYON, I. An Introduction to Variable and Feature Selection. Journal of Machine

Learning Research, [S.l.], v.3, (pp.1157-1182), 2003.

[18] HAALAND, D. M. & THOMAS, E. V. Partial Least-Squares Methods for Spectral

Analysis 1. Relation to Other Quantitative Calibration Methods and the Extraction of

Quantitative Information, Anal. Chem, 60, (pp 1193), 1988.

[19] HAWKINS, D. M. The Problem of Overfitting. Journal of Chemical Information and

Computer Sciences, 44(1):1–12, 2004.

[20] HOCKING, R. R. The analysis and selection of variables in linear regression.

Biometrics, 32, pp. 1-49, 1976.

[21] HOLLAND, J. H. Adaptation in Natural and Artificial Systems. The University of

Michigan Press, 1975.

[22] JOHNSON, R. A. & WICHERN, D. W. Applied Multivariate Statistical Analysis. 5th

ed. Prentice Hall, New Jersey, 1976.

[23] JOLLIFFE, I. T. Principal Component Analysis. Springer, second edition, Oct. 2002.

[24] JOLLIFFE, I. T. A Note on the Use of Principal Components in Regression.

Applied Statistics, 31(3):300+, 1982.


[25] KENNARD, R. . S. L. A. Computer aided design of experiments. Technometrics,

11, (pp 137-148), 1969.

[26] KOBAYASHI, M.; ITO, Y.; SAKAUCHI, N.; ODA, I.; KONISHI, I.; TSUNAZAWA, Y.

Analysis of nonlinear relation for skin hemoglobin imaging. Opt. Express,

9(13):802–812, Dec 2001.

[27] MARTENS, H. & NAES, T. Multivariate Calibration. John Willey & Sons, Chichester,

1989.

[28] MICHALEWICZ, Z. Genetic algorithms + data structures = evolution programs. 3

ed. Springer, Berlin, 1996.

[29] MILLER, A. Selection of Subsets of Regression Variable. Journal of the Royal

Statistical Society. Series A (General), Vol. 147, No. 3, (pp.389-425), 1984.

[30] NAES, T.; ISAKSSON, T.; FEARN, T.; DAVIES, T. A User Friendly Guide to Multiva-

riate Calibration and Classification. NIR Publications, Chichester, UK, 2002.

[31] NÆS, T.; MEVIK, B.-H. Understanding the collinearity problem in regression and

discriminant analysis. Journal of Chemometrics, 15(4):413–426, 2001.

[32] NUNES, P. G. A. Uma nova técnica para seleção de variáveis em calibração

multivariada aplicada às espectrometrias UV-VIS e NIR, Tese de Doutorado.

UFPB/CCEN, João Pessoa, 2008.

[33] PIMENTEL, M. F.; BARROS NETO, B. Calibração: Uma revisão para Químicos

Analíticos. Química Nova. 19: 268, 1999.

[34] RAMSEY, P. H.; HODGES, J. L.; SHAFFER, J. P. Significance probabilities of

the wilcoxon signed-rank test. Journal of Nonparametric Statistics, 2(2):133–153,

1993.

[35] RENCHER, A. C. Methods of Multivariate Analysis. Willey-Interscience, 2002.

[36] SADLER, T.; LANGMAN, J. Langman. Embriología médica: con orientación

clínica. Editorial Medica Panamericana Sa de, 2007.

[37] SCHULZ, A. G. Fuzzy rule-based expert systems and genetic machine learning.

Physica-Verlag, 1997.

[38] SKOOG, D. A.; HOLLER, J. F.; CROUCH, S. R. Principles of Instrumental Analysis.

Brooks Cole, 6 edition, Dec. 2006.


[39] SKOOG, D. A.; LEARY, J. J. Principles of instrumental analysis. 6. ed. New York

: Saunders College Publishing, 1992.

[40] SNEDECOR, G. W. & COCHRAN, W. G. Statistical Methods. 6 ed., Iowa: Ames,

1972.

[41] SOARES(A), A. S.; GALVÃO FILHO, A. R. G. A. R. K. H. . A. M. C. U. Improving

the computational efficiency of the successive projections algorithm by using a

sequential regression implementation: a case study involving nir spectrometric

analysis of wheat samples. J. Braz. Chem. Soc., v. 21, n. 4, São Paulo, 2010.

[42] SOARES(B), A. S.; GALVÃO FILHO, A. R. G. A. R. K. H. . A. M. C. U. Multi-

core computation in chemometrics: case studies of voltammetric and NIR

spectrometric analyses. J. Braz. Chem. Soc., v. 21, n. 9, São Paulo, 2010.

[43] SRINIVAS, N. & DEB, K. Multiobjective Optimization Using Nondominated Sor-

ting Genetic Algorithms. Evolutionary Computation, Vol.2, No.3, 1994.

[44] TAKAHASHI, R. H. C. Otimização Escalar e Vetorial. Universidade Federal de

Minas Gerais,[S.l.], 2004.

[45] TOBIAS, R. An Introduction to Partial Least Squares Regression. TS-509. SAS

Institute Inc., Cary, NC., 1997.

[46] WOLD, S.; SJÖSTRÖMA, M. . E. L. PLS-regression: a basic tool of chemometrics.

Chemometrics and intelligent laboratory, v. 58, (pp. 109-130), 2001.

[47] ZITZLER, E.; LAUMANNS, M.; THIELE, L. Spea2: Improving the strength pareto

evolutionary algorithm. Technical report, 2001.

[48] ZITZLER, E.; THIELE, L. An evolutionary algorithm for multiobjective optimiza-

tion: The strength pareto approach, 1998.

Documents

Algoritmos Evolutivo Multiobjetivo para Seleção de