4 ESTADO DA ARTE

Os inúmeros trabalhos publicados desde o surgimento do problema de seleção de modelos até

os dias atuais, vide Tabela 4.1, destacam a preocupação dos pesquisadores com o tema e a im-
portância de uma solução de boa qualidade para este problema nas diversas aplicações em que as
SVMs são utilizadas. Neste capítulo, é apresentada uma revisão sobre os algoritmos empregados
entre os anos de 2002 e 2018, na busca por uma solução adequada para o problema de seleção de
modelos.
Devido à grande popularidade dos algoritmos meta-heurísticos, existem vários artigos de re-
visão de literatura sobre esses algoritmos. Neste capítulo, buscou-se fazer uma revisão criteriosa
destes artigos, a fim de obter informações mais concisas sobre o assunto.

4.1 INTRODUÇÃO

Desde a popularização das SVMs, o problema de seleção dos hiperparâmentros tem sido ex-
tensamente estudado. Na revisão bibliográfica apresentada na Tabela 4.1, foram compilados ses-
senta artigos sobre o problema de seleção de parâmetros para SVMs, sendo esse problema tratado
por diversos algoritmos meta-heurísticos. Porém, poucos trabalhos lançam mão de algoritmos
multiobjetivos para resolver tal problema, sendo que, nesta revisão, eles representam treze por-
cento do total.
Nesse cenário, devido ao potencial dos algoritmos PSO e DE em resolver problemas comple-
xos e haver poucos trabalhos que abordam o problema de seleção do modelo de SVMs como um
MOOP, foram implementadas versões multiobjetivos do PSO e DE com o objetivo de encontrar
ao invés de uma única solução um conjunto de soluções que produzam SVMs de alta qualidade,
avaliadas segundo as métricas descritas na Subseção 6.1.1.
Os algoritmos meta-heurísticos são uma representação simplificada de sistemas naturais com-
plexos (para este caso), tais como o comportamento de animais (individualmente ou em grupos),
na teoria da seleção natural, comportamento presa-predadores, leis físicas, comportamento físico
de materiais e outros (Jr et al. 2013). Eles apresentam capacidade de resolver problemas comple-
xos multimodais sem exigir que estes sejam diferenciáveis ou mesmo contínuos, sendo capazes
de explorar o espaço de busca e refinar as soluções, produzindo bons resultados. Nas SVMs, por
exemplo, o critério número de vetores de suporte não é diferenciável, impossibilitando assim o
uso de técnicas que envolvam o cálculo do gradiente.
Na Seção 4.2, evidencia-se a importância dos algoritmos meta-heurísticos para resolver pro-
blemas multiobjetivos e, na Seção 4.3, é realizado um levantamento de trabalhos publicados que
desenvolveram algoritmos meta-heurísticos na tentativa de resolver o problema de seleção de

45
modelo das SVMs a fim de salientar a preocupação da comunidade científica em obter os hiper-
parâmetros ótimos. Este levantamento mostra também as técnicas utilizadas para alcançar esses
resultados.

4.2 ALGORITMOS META-HEURÍSTICOS MULTIOBJETIVOS

Em muitos MOOP, obter o conjunto de Pareto completo e exato é uma tarefa árdua e, por isso,
a aproximação do conjunto de Pareto é aceita como solução dos problemas da engenharia. Os
algoritmos evolucionários têm provado serem capazes de encontrar uma boa aproximação para
problemas multiobjetivos multimodais complexos.
Vários trabalhos têm sido publicados envolvendo diversos tipos de algoritmos meta-heurísticos;
o que parece confirmar o grande interesse da comunidade científica nesses algoritmos e, conse-
quentemente, sua importância. Alguns exemplos de artigos de revisão bibliográfica sobre esses
algoritmos são (Correia 2013, Ulungu e Teghem 1994, Agarwal e Mehta 2014) e (Von L u cken,
Barán e Brizuela 2014). Entre esses algoritmos, destacam-se os algoritmos PSO e o DE.
Um ano depois que R. Storn e K. V. Price publicaram o primeiro relatório técnico descre-
vendo o DE (Storn e Price 1997), este algoritmo adquiriu popularidade depois do First Interna-
tional Conference on Evolutionary Computation, no qual alcançou o terceiro lugar como melhor
algoritmo evolucionário para resolver problemas testes de variáveis reais. Nos anos que segui-
ram, o DE e as suas variações sempre figuraram entre os melhores algoritmos em competições
internacionais (Das e Suganthan 2011). Em 2007 e 2009, o Differential Evolution alcançou o
segundo lugar e o primeiro lugar respectivamente para solução de problemas multiobjetivos. O
sucesso nestes eventos, frente aos demais algoritmos, motivou o desenvolvimento de um MODE
para determinação dos hiperparâmetros das SVMs.
O PSO e o DE são métodos que têm alcançado bons resultados na determinação de soluções
de boa qualidade na resolução de problemas NP-Completos. O PSO consiste em um método de
otimização estocástico baseado em população. Esse algoritmo tem sido aplicado com sucesso em
diversos problemas, como, por exemplo, treinamento de redes neurais, otimização de funções,
controle fuzzy e reconhecimento de padrões, controle preditivo e outros. O crescente interesse
pelo PSO pode ser observado na Figura 4.1.
Os critérios para construção do histograma da Figura 4.1 são descritos em (Correia 2013).
Observando a curva da Figura 4.1, fica evidente o quanto este algoritmo tem sido importante na
resolução de problemas complexos. Na Figura 4.1, a quantidade de artigos publicados cresceram
rapidamente entre 1997 e 2009. Nos anos seguintes, o interesse pelo algoritmo manteve-se alto,
alcançando, em 2012, quase 4.500 publicações (que continham o PSO no título do trabalho).
Na Seção 4.3, foi realizada uma busca bibliográfica a respeito dos algoritmos meta-herísticos
empregados no problema de seleção de parâmetros das SVMs.

46
Figura 4.1 – Número de artigos publicados com “Particles Swarm Optimization” em seu títulos nas bases de dados
Scopus, Google Scholar, Springer, Web of Science e IEEE Xplore (Correia 2013).

4.3 PROBLEMA DE SELEÇÃO DE PARÂMETROS - ESTADO DA ARTE

No processo de modelagem, o parâmetro de regularização e os parâmetros do kernel devem

ser definidos a priori, interferindo diretamente na qualidade final do classificador obtido, ou seja,
na sua capacidade de generalização e complexidade, conforme definido na seção 2.1.
A definição dos hiperparâmetros é um problema complexo, pois, para cada conjunto de trei-
namento, tem-se um problema distinto e, geralmente, esses problemas possuem vários mínimos
locais, dificultando, assim, sua determinação ótima (Miranda e Prudêncio 2013). No Apêndice
B, tem-se os gráficos das funções custo precisão e cardinalidade dos vetores de suporte para cada
combinação de benchmarks e kernels, onde pode ser observado o comportamento destas funções
e a complexidade que envole encontrar o conjunto de Pareto.
A determinação dos hiperparâmetros ótimos das SVMs têm atraído a atenção da comunidade
desde sua consolidação (no final dos anos noventa) com a publicação dos trabalhos de Vapnik
(C. Cortes e V. Vapnik 1995) e Smola (Smola e Vapnik 1997). A Tabela 4.1 apresenta vários
trabalhos sobre o tema compreendidos entre os anos de 2002 a 2018, enquanto na Figura 4.2, esses
trabalhos foram quantificados por ano de publicação. A interesse pelo tema nos anos de 2016 e
2017 é maior que nos demais anos, ficando clara a relevância das SVM/SVRs e a importância de
definir hiperparâmetros adequados para estes modelos.
Na Tabela 4.1, os artigos foram classificados como se segue: (a) ano de publicação; (b) quanto
ao algoritmo empregado na solução do problema de seleção do modelo; (c) tipo de dados empre-
gados para validar o algoritmo; (d) quanto à natureza multi ou mono-objetivo da formulação do
problema de seleção de modelos; (e) distinção entre modelos classificadores e regressores; e (f) a
quantidade de saídas do modelo SVM/SVR.

47
 Figura 4.2 – Artigos que trata o PSP-SVM classificados por ano.

Figura 4.3 – Artigos que trata o PSP-SVM classificados por meta-heurísticas.

O algoritmo PSO, descrito na Seção 3.2.1, é o mais empregado, seja na sua forma clássica ou
com modificações para evitar mínimos locais ou melhorar a convergência. Algoritmos baseados
no PSO tem mostrado-se tão eficientes que, dos cinquenta e nove encontrados na literatura (vide
Tabela 4.1), vinte o envolvem. A Figura 4.3, pode-se observar que o o PSO se destaca dos demais
em quantidade, sendo em maior quantidade que o grupo outros que consiste na soma de todos as
meta-heurísticas que somaram apenas um trabalho encontrado.
O algoritmo Simulated Annealing - SA também merece destaque, pois, embora seja consi-
derada uma técnica clássica, ainda hoje é utilizado para resolver problemas NP-Completo. Esse
algoritmo meta-heurístico simula o aquecimento de materiais e seu resfriamento controlado com
o objetivo de criar cristais perfeitos. Essa técnica é reconhecidamente robusta para diversos tipos
de problemas NP-Completo, sendo originalmente desenvolvido para resolver o problema do cai-

48
xeiro viajante (Kirkpatrick et al. 1983). O SA foi utilizado para resolver o problema de seleção
de modelos em trabalhos publicados em 2008, 2012 e 2013, conforme a Tabela 4.1.
O Algoritmo Genético - AG (Holland 1975) é uma meta-heurística inspirada na teoria da se-
leção natural que afirma que, em determinado ambiente, os indivíduos mais adaptados a ele têm
mais chance de se reproduzir e passar seus genes adiante. O AG básico consiste nos operadores
seleção, crossover e mutação que atuam sobre uma população de indivíduos, definindo a pró-
xima geração. Uma característica importante do AG é sua capacidade de sair de mínimos locais,
característica, em grande parte, atribuída ao operador mutação.
O AG foi adaptado para tratar problemas multiobjetivos, sendo o Non Sorting Genetic Algo-
rithm - NSGA-II a proposta mais popular (Deb et al. 2002). Por exemplo, nesta revisão, dos
sete algoritmos multiobjetivos, três envolvem, de alguma forma, o NSGA-II, mostrando que não
existe uma variedade de algoritmos multiobjetivos que tratam o problema de seleção de hiperpa-
râmetros das SVMs. Na Figura 4.3, o NSGA-II foi classificado como AG, por aquele ser uma
variação deste último.
Entre as técnicas encontradas, algumas não utilizam a filosofia das heurísticas na resolução
do problema de seleção de parâmetros, tendo uma natureza determinística. Todavia esses mé-
todos necessitam de um conhecimento prévio dos dados do conjunto de treinamento e, muitas
vezes, são computacionalmente inviáveis. Neste cenário, três artigos (Cherkassky 2004, Miranda
e Prudêncio 2013, Ji et al. 2017) foram encontrados corroborando com essa informação.
Ainda na Tabela 4.1, encontram-se sete trabalhos que tratam o problema de otimização como
multiobjetivo, mostrando que essa importante teoria vem sendo pouco explorada, e o mais recente
deles o trabalho de Miranda at al. (Miranda et al. 2012). O que motiva o desenvolvimento
de algoritmos MOOP especializados no PSP. Na Figura 4.4, os trabalhos da Tabela 4.1, foram
categorizados em multiobjetivo e mono-objetivo, a porção que representa os artigos que tratam o
PSP como MOOP representam pouco menos de doze porcento do total.
No trabalho de Igel (Igel 2005), é proposto um algoritmo evolutivo auto adaptativo, que atu-
aliza os indivíduos baseado na distribuição normal N (0, 1) que não se altera durante o processo
evolutivo. O algoritmo é o primeiro auto adaptativo ES que usa ordenamento não dominante,
chamado de NSES (Igel 2005). O NSES, foi desenvolvido para emprego do kernel Gaussiano
para classificadores e destaca o estudo das possíveis funções objetivo do MOOP. O Igel et al.,
propõe um outro trabalho, no qual modela o problema de seleção de parâmetros com três funções
objetivos e emprega o mesmo algoritmo de (Igel 2005) em benchmarks e as funções objetivos
propostas ao NSGA-II, para classificar a presença de pedestres em imagens de carros autônomos.
Chatelain et al. em (Chatelain et al. 2007) o NSGA-II é empregado para resolver o problema
de seleção de parâmetros das SVMs, onde que as funções objetivos consideradas são os Falsos
Positivos - FP e Falsos Negativos FN, ou seja, não avalia complexidade da SVM. No trabalho
de Chatelain et al. (Chatelain et al. 2007) as variáveis de decisão do problema é o do kernel
Gaussiano e dois parâmetros de regularização, pois trata cada classe independentemente.

49
 Figura 4.4 – Artigos que trata o PSP-SVM classificados por quantidade de funções objetivos.

O algoritmo Muti-objective uniform design - MOUD, proposto por W. Li et al. (Li, Liu
e Gong 2011), emprega a técnica Uniform Design sendo esta semelhante ao Symmetric Latin
Hypercube Design - SLHD. O MOUD não considera complexidade das SVM, mas a sensibilidade
e a especificidade como critérios multiobjetivos para obter os hiperparâmetros ótimos das SVMs,
e o kernel utilizado é o Gaussiano e o polinomial.
Miranda et al. (Miranda et al. 2012) desenvolveram um algoritmo híbrido em que uma téc-
nica Meta-Learning - ML baseada na características dos problemas possa gerar um enxame de
soluções de boa qualidade como enxame inicial para o MOPSO. Esse MOPSO emprega o kernel
Gaussiano para gerar classificadores e os critérios do MOOP são #SV e a precisão. Uma res-
trição deste MOPSO é que o espaço de busca foi discretizado limitando-o a trezentos e noventa
e nove diferentes configurações de C e os hiperparâmetros adotados e consequentemente com-
prometendo a qualidade dos modelos. Miranda et al. propõe um outro trabalho com modificações
no processo de obtenção do ML e no MOPSO (Miranda et al. 2014).
O NSGA-II também é empregado no trabalho de Narzisi G. (Narzisi 2008), em que os critérios
adotados são #SV e a precisão. Narzisi G. realiza testes com o kernel Gaussiano e sigmoide,
para tratar dados não linearmente separáveis.
Os algoritmos multiobjetivos citados nos parágrafos anteriores (vide Tabela 4.1) utilizam em
sua maioria o NSGA-II, com kernel Gaussiano para desenvolver classificadores, ou seja, uma sub-
categoria do problema. Deve-se observar que para diferentes kernels tem-se problemas de seleção
de parâmetros com características distintas. Adicionalmente, nenhum dos estudos encontrados na
literatura abordam a definição de hiperparâmetros das SVRs, o que deixa evidente, a necessidade
de um estudo mais criterioso sobre o assunto, empregando diferentes kernels e algoritmos que
resolvam o problema de seleção de parâmetros como um MOOP.
A maioria dos artigos que optam pela abordagem mono-objetivo utilizam o MSE (SVR) e a
precisão (SVM) como métrica para direcionar o algoritmo meta-heurístico pelo espaço de busca.

50
Esta prática pode gerar máquinas com boa capacidade de generalização, mas, por outro lado,
muito complexas, impossibilitando a aplicação em situações em que o tempo de processamento e
memória são limitados.

Tabela 4.1 – Referências de seleção de parâmetros.

Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização
(Jack
Detecção de
e Algoritmo
2002 falhas em Mono SVM Binária
Nandi Genético
rolamentos
2002)
(Soa-
res,
Projeto METAL
Braz-
2004 Meta-learning http://www.metal- Mono SVR Single-target
dil e
kdd.org
Kuba
2004)
Método
(Cher- analítico
kas- 2004 baseado nos Artificial Mono SVR Single-target
sky dados de
2004) treinamento
Estratégia de
(Fri- evolução
edri- adaptativa Câncer de Mama,
chs e 2005 baseada na Diabetes, Coração Mono SVM Binária
Igel matriz de e Tiróide
2005) covariância –
CMA-ES.
(Igel Algoritmo
2005 Benchmarks UCI Multi-objetivo SVM Multi-classe
2005) Evolutivo
(Hu-
ang e
2006 GA Benchmarks UCI Mono SVM Multi-classe
Wang
2006)
(Sut-
Combinação
torp Identificação de
2006 de AE e Multi-objetivo SVM Binária
e Igel pedestres
NSGA-II
2006)

(Cha-
Reconhecimento
telain 2007 NSGA-II Multi-objetivo SVM Multi-classe
de manuscritos
et al.
2007)
Continua na próxima página.

51
 Tabela 4.1 – Continuando da página anterior.
Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização
(Sha-
owu Differential
2007 Artificial Mono SVR Single-target
et al. Evolution
2007)
(Hu-
ang e
2008 PSO Dados artificiais Mono SVM Multi-classe
Dun
2008)
(Guo
et al. 2008 PSO Benchmarks UCI Mono LS-SVM Binária
2008)
(Nar-
Benchmarks UCI,
zisi 2008 NSGA-II Multi-objetivo SVM Binária
Stalog, Delve
2008)
(Lo-
rena
e De Algoritmo
2008 Benchmarks UCI Mono SVM Multi-classe
Car- Genético
valho
2008)
(Lin
et al. 2008 PSO Benchmarks UCI Mono SVM Multi-classe
2008)
(Lin
Simulated
et al. 2008 Benchmarks UCI Mono SVM Multi-classe
Annealing
2008)

(Zhang
Reconhecimento
e 2009 PSO Mono SVM Multi-classe
de voz
Guo
2009)

(Tang
2010 PSO Benchmarks UCI Mono SVM Multi-classe
et al.
2010)
(Wu
e Projeto de peças
2011 PSO Mono SVR Single-target
Law de plástico
2011)
Continua na próxima página.

52
 Tabela 4.1 – Continuando da página anterior.
Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização

(Chen- Detecção de
glin 2011 PSO falhas em Mono SVM Binária
et al. sensores wireless
2011)
(Wu Projeto de peças
2011 PSO Mono SVR Single-target
2011) de plástico

(Gang
e Predição de con-
2011 PSO Mono SVR Single-target
Zhu- gestionamentos
ping
2011)
(Li, Multi-
Liu e objective
2011 Benchmarks UCI Multi-objetivo SVM Multi-classe
Gong uniform
2011) design
(Go-
mes Busca Tabu e
2012 Benchmarks Mono SVR Single-target
et al. PSO
2012)
(Dos
San-
Differential Identificação de SVR/Iden-
tos et 2012 Mono Single-target
Evolution processos termais tificação
al.
2012)
(Mi-
randa Benchmarks UCI,
2012 MOPSO Multi-objetivo SVM Binária
et al. WEKA
2012)
(Gas-
par,
Car-
bo- Simulated
2012 Benchmarks UCI Mono SVM Binária
nell e Annealing
Oli-
veira
2012)
(Bo-
Simulated
nesso 2013 Imagens Mono SVM Multi-classe
Annealing
2013)
Continua na próxima página.

53
 Tabela 4.1 – Continuando da página anterior.
Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização
(Mi-
randa
e
Active
Pru- 2013 Benchmarks UCI Mono SVM Multi-classe
Testing
dên-
cio
2013)
(Mi-
randa
2014 MOPSO Benchmarks UCI Multi-objetivo SVM Multi-classe
et al.
2014)
(You,
Gao Erros em
e Ka- 2014 Grid Search processos de Mono SVM Multi-classe
tayama solda
2014)

Reconhecimento
(Anam
2014 PSO de movimentos Mono SVM Multi-classe
et al.
dos dedos
2014)
(Gar-
cía
Predição de
Nieto 2015 ABC Mono SVR Single-target
Cianotoxinas
et al.
2015)

(Shamshir- Predição da
band 2015 FFA, QPSO eficiência de Mono SVR Single-target
et al. motores Diesel
2016)
(Yao,
Xue
Alimentação de
e 2015 Grid Search Mono SVR Single-target
arames (Solda)
Zhou
2015)
(She-
Algoritmo Classificação
rin 2015 Mono SVM Multi-classe
Genético subaquática
2015)
(Gar-
Modelo preditivo
cía
do ciclo de
Nieto 2016 PSO Mono SVR Single-target
crescimento da S.
et al.
Platensis
2016)
Continua na próxima página.

54
 Tabela 4.1 – Continuando da página anterior.
Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização

Diagnose de
(Chen Algoritmo
2016 circuitos Mono SVM Multi-classe
et al. Genético
analógicos
2016)
(Yi et
Crescimento de
al. 2016 Fruit Fly Mono SVR Single-target
folha de arroz
2016)

(Phan,
Algoritmo
Nguyen 2016 Benchmarks UCI Mono SVM Multi-classe
Genético
e Bui
2016)

(Mah-
moudi,
Shuffled Frog
Orouji Qualidade da
2016 Leaping Mono SVR Single-target
e água
Algorithm
Fallah-
Mehdipour
2016)
(Ba-
ma-
kan,
Wang 2016 PSO Benchmarks UCI Mono SVM Binária
e Ra-
vasan
2016)

(Ghor-
bani,
Zar- Algoritmo Precipitação de
2016 Mono SVR Single-target
gar e Genético asfaltenos
Jazayeri-
Rad
2016)
(Min Algoritmo
2016 Benchmarks UCI Mono SVM Binária
2016) Genético
Continua na próxima página.

55
 Tabela 4.1 – Continuando da página anterior.
Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização

(Rast-
gou- Avalição de
fard HS, ACO, Segurança
2016 Mono SVM Multi-classe
e Di- PSO e DE Estática (Sistema
mi- de Potência)
trios
2016)
(Li et Diagnose de
Algoritmo
al. 2016 falhas em Mono SVM Multi-classe
Genético
2016) transformadores
(Ji et
Ensemble Benchmarks UCI,
al. 2017 Mono SVM Multi-classe
Kalman Filter LIBSVM
2017)

(Tharwat,
Moe-
men Whale Classificação de
e 2017 Optimization toxidade de Mono SVM Multi-classe
Has- Algorithm remédios
sa-
nien
2017)

Previsão da
(Zhang Cuckoo
2017 velocidade do Mono SVR Single-target
et al. Search
vento
2017)
(Su-
kawat-
tana-
vijit, Algoritmo Imagens de
2017 Mono SVM Multi-classe
Chen Genético satélite
e
Zhang
2017)
(Tha-
seen Técnica Detecção de
e Ku- 2017 baseada na invasão de redes Mono SVM Multi-classe
mar variância de computadores
2017)
(Gui Falhas em
et al. 2017 PSO, GS, GA estruturas de Mono SVM Binária
2017) construção civil
Continua na próxima página.

56
 Tabela 4.1 – Continuando da página anterior.
Tipo de
Ref. Ano Algoritmo Dados Máquina Saídas
Otimização
Ensemble
(Ji et
Kalman Filter
al. 2017 Benchmarks UCI Mono SVM Multi-classe
Scheme -
2017)
EnKFS
(Niu EMD-GRA- Predição de
e Dai 2017 MPSO- consumo de Mono SVR Single-target
2017) LSSVM energia

(Zhang,
Predição de
Wang Cuckoo
2017 consumo de Mono SVR Single-target
e Search - CS
energia
Zhang
2017)

(Alwan
e Ku- 2017 ACO Benchmarks UCI Mono SVM Multi-classe
Mahamud
2017)

Diagnose da
(Zeng Switching
2018 doença de Mono SVM Binária
et al. Delayed PSO
Alzheimer
2018)
(Fa-
Multi Verse
ris et
2018 Optimizer - Benchmarks UCI Mono SVM Multi-classe
al.
MVO
2018)
Teaching
(Das
Learning Predição de
e
2018 Based valores de Mono SVR Single-target
Padhy
Optimization commodities
2018)
- TLBO
(Al-
masi
e
2018 Adaptive PSO Benchmarks UCI Mono SVM Multi-classe
Kho-
oban
2018)

No contexto da pesquisa bibliográfica, trinta e seis porcento dos trabalhos pesquisados uti-
lizaram o repositório do UCI para realizar seus experimentos, entre eles sete com abordagem
multiobjetivo, o que possibilita a comparação direta com os algoritmos APMT-MODE e MOPSO
desenvolvidos neste trabalho. O algoritmo NSGA-II possui código-fonte aberto, assim a altera-

57
 Figura 4.5 – Artigos que modelam o PSP como MOOP para aplicações reais vs. benchmarks.

ção de suas funções objetivo para tratar o problema de seleção de modelos das SVMs foi im-
plementado e comparado com os algoritmos APMT-MODE e MOPSO. A disponibilidade do
código-fonte do NSGA-II também justifica seu emprego em três dos sete trabalhos que utilizam
a metodologia multiobjetivo.
Adicionalmente, pode ser observado na Figura 4.5 que dois dos cinco trabalhos pesquisados
(Chatelain et al. 2007, Suttorp e Igel 2006), ou seja, 28, 57% modelam o PSP das SVMs como
um MOOP, sendo o NSGA-II, empregado em ambos casos para definir os hiperparâmetros dos
modelos de SVMs classificadores. Diante do exposto, conclui-se que existe uma carência no de-
senvolvimento de meta-heurísticas que abordem o PSP como um MOOP para aplicações reais em
que os modelos possuem saídas são contínuas, principalmente quando estas possuem restrições
de energia, recursos físicos (hardware) e tempo de resposta do modelo.
Metade dos trabalhos pesquisados e apresentados na Tabela 4.1 utiliza as SVM binária ou
SVR single-targe em que não há necessidade de alteração no modelo original de Vapnik. A outra
metade envolve classificação (SVMs) multiclasse em que são necessárias adaptações ou técnicas
adicionais, como, por exemplo, One-Against-One (OAO) e One-Against-All (OAA). As técni-
cas que envolvem estudos multiclasses exigem um esforço maior na resolução do problema de
seleção de modelo da SVM, pois deve-se atribuir valores aos hiperparâmetros de várias máqui-
nas simultaneamente ou definir hiparâmetros iguais que atendam ao modelo de forma satisfatória
como um todo.
Embora existam técnicas que definem SVRs multi-target, não foram encontrados estudos es-
pecíficos que tratam a seleção de parâmetros dessas máquinas, o que indica que pode ser uma
área de pesquisa promissora. Essas máquinas possuem várias aplicações, visto que é comum em
aplicações práticas saídas contínuas interdependentes, como, por exemplo, o controle de corrente,
a tensão e a alimentação do arame em processos de soldagem (Yao, Xue e Zhou 2015).

58
 4.4 MÉTRICAS DE AVALIAÇÃO DA FRONTEIRA DE PARETO - ESTADO DA ARTE

Um problema MOOP consiste em encontrar a solução ótima de várias funções objetivos con-
traditórias simultaneamente como definido na Seção 3.1 e, possui, como decorrência desta defi-
nição um conjunto de soluções não dominantes que são adotadas como igualmente boas. Neste
contexto, a fronteira de Pareto consiste em um conjunto de pontos (soluções) não dominantes
pertencente ao Espaço Objetivo, cujo seus elementos devem ser avaliados em conjunto.
Segundo Okabe et al. (Okabe, Jin e Sendhoff 2003), a fronteira de Pareto é avaliada em três
quesitos: (a) cardinalidade da fronteira de Pareto, (b) precisão das soluções contidas no conjunto,
ou seja, proximidade da fronteira de Pareto teórica e (c) e distribuição ou espalhamento, sendo es-
tas duas significam características semelhantes mas, em essência diferentes. A distribuição refere
a relativa distâncias entre as soluções do conjunto não dominante, enquanto que espalhamento a
faixa coberta por estas soluções (Riquelme, Lücken e Baran 2015).
A Tabela 4.2, apresenta as métricas utilizadas por algoritmos multiobjetivos entre os anos de
1998 e 2019, e devido a diversidade de métricas utilizadas conclui-se que o problema de avaliar
a qualidade da fronteira Pareto ainda está em aberto, por não apresentar um consenso entre os
trabalhos apresentados.

Tabela 4.2 – Revisão de métricas de avaliação de algoritmos multiobjetivo.

Ref. Ano Algoritmo Problemas Métricas

(Zitzler e
VEGA, NSGA,
Thiele 1998 Knaspsack Problem Hipervolume
AVOW, NPGA
1998)
Generational distance,
(Deb et al.
2002 NSGA-II Benchmarks Spacing
2002)

(Suttorp e UCI Classification Area Under Curve,

2006 NSGA-II
Igel 2006) Pedestres Hipervolume
Hipervolume, Diferença a
(Alberto e
Benchmarks CEC um conjunto referência,
Mateo 2009 EA - Standart
(2007) Generational distance Set
2011)
coverage
(Huang et objective-wise
2009 CEC2009 IGD
al. 2009) MOSaDE
(Wagner e
Benchmarks (ZDT1,
Traut- Dominated HV, Additive ✏,
2010 SMS-EMOA ZDT2, ZDT3,
mann R2 indicator
ZDT4)
2010)
(Mateo e Hipervolume, Diferença a
Alberto 2011 EA CEC (2007) um conjunto referência, Set
2012) coverage
Continua na próxima página.

59
 Tabela 4.2 – Continuando da página anterior.
Ref. Ano Algoritmo Problemas Métricas
(Ali, Multi-Objective
Benchmarks (ZDT1,
Siarry e Differential Generational distance,
2012 ZDT2, ZDT3,
Pant Evolution Algorithm Diversity metric, Spacing
ZDT4)
2012) (MODEA)
(Fortin e Benchmarks (ZDT1,
Generational distance,
Parizeau 2013 NSGA-IIr ZDT2, ZDT3,
Spacing
2013) ZDT4)
Multiobjective
evolutionary
(Li et al.
2014 algorithm based on CEC2009 IGD, Hipervolume
2014)
decomposition
(MOEA/D)
Benchmarks
(Deb e
2014 NSGA-III (DTLZ1, DTLZ3, IGD
Jain 2014)
DTLZ6 )
Multi-Objective
Benchmarks (ZDT1,
(Lin et al. Particle Swarm
2015 ZDT2, ZDT3, IGD
2015) Optimization
ZDT4)
(MOPSO)
(Mirjalili Benchmarks (ZDT1,
2016 Dragonfly IGD
2016) ZDT2, ZDT3)
(Mirjalili
Grey Wolf Optimizer IGD, Spacing, Maximum
et al. 2016 Benchmarks
(GWO) spread
2016)
Benchmarks Binh,
(Meza et Hipervolume, Generational
2017 MOVPSO Fonseca, Viennet,
al. 2017) distance
Viennet-2
(Bejina-
MOPSO, MOGSA,
riu, Luca Segmentação de Avaliação gráfica da
2018 Black Hole
e Costin imagem fronteira de pareto
Algorithm
2018)

(Zapotecas-
Martínez,
Benchmarks
García- Hipervolume, Inverted
2019 MOGWO/D (DTLZ1, DTLZ3,
Nájera e Generational Distance plus
DTLZ6 )
López-
Jaimes
2019)

A Figura 4.6, foi obitida a partir da Tabela 4.2, em que pode-se verificar que o hipervolume
é a métrica mais empregada seguida pela métrica IGD, o que sugere que as duas métricas são
bem aceitas pela comunidade, ainda na Figura 4.6, observa-se que há uma vasta variedade de

60
 Figura 4.6 – Classificação das métricas por trabalho pesquisado.

métricas, sendo coluna Outros, composta por métricas que aparecem uma única vez na Tabela
4.2. Entretanto, segundo a pesquisa realizada em (Riquelme, Lücken e Baran 2015), a métrica
hipervolume é a mais utilizada em trabalhos que envolvem algoritmos evolutivos, enquanto que a
métrica IGD, ocupa a quarta colocação.
O hipervolume é calculado sem que seja necessário o conhecimento da fronteira de Pareto,
bastando definir um ponto conhecido como nadir (pior solução possível) e tendo este como vér-
tice calcular o hipervolume do poliedro gerado pelo conjunto candidato a fronteira de Pareto. Essa
métrica é unária, ou seja, retorna um único valor escalar que representa simultaneamente a diver-
sidade e a precisão das soluções do conjunto em avaliação. Quanto maior o hipervolume, maior a
diversidade do conjunto e mais distante do ponto nadir, portanto, mais próximo da solução ótima.
O cálculo da métrica hipervolume segundo Bader (Bader 2010) na melhor das hipóteses pos-
sui complexidade máxima de O (d/2)N , onde d é a dimensionalidade do espaço objetivo e N a
cardinalidade do conjunto em avaliação. Ainda segundo Bader (Bader 2010) o cálculo do hiper-
volume consiste em um problema não polinomial. Diante dos exposto e dos resultados obtidos
durante a elaboração deste trabalho, o hipervolume não apresentou um comportamento esperado
para avaliar os algoritmos implementados pois, para todos os algoritmos, o hipervolume os des-
creve como tendo uma convergência com menos de trinta iterações. Entretanto, quando observada
as fronteiras geradas nas iterações finais (maior que cem), os conjunto de soluções não dominan-
tes são significativamente melhores em valores absolutos, ou seja, o hipervolume gera um falso
positivo para convergência dos algoritmos. A Figura 4.7 apresenta o comportamento descrito.
Para o cálculo da métrica IGD é necessário que seja conhecida a fronteira de Pareto, esta
métrica é unária e, assim como o hipervolume, avalia a diversidade e a qualidade do conjunto
candidato a fronteira de Pareto. Na Tabela 4.2, todos os trabalhos que emprega o IGD como
avaliação utilizou como problema benchmarks em que as fronteiras de Pareto são conhecidas,
evidenciando que esta métrica é empregada com certo sucesso apenas nas situações em que se

61
 Hypervolume Metric
1

0.9

0.8

0.7

0.6
Hypervolume

0.5

0.4

0.3

0.2

0.1

0
0 50 100 150 200
Iteration

Figura 4.7 – Hipervolume obtido pelo MOPSO para o benchmark Ecoli.

conhece a fronteira de Pareto.

Neste trabalho, para gerar o conjunto de soluções não dominante mais próximo possível da
fronteira Pareto, para cada problema, foram reunidas todos os conjuntos solução não dominantes
de todos os algoritmos a serem avaliados em um único conjunto, e então, foi empregado a função
Truncate, para determinar o conjunto de soluções não dominantes referência, para ser utilizado
pelo IGD como fronteira de Pareto. Essa estratégia permite avaliar os conjuntos de soluções
encontradas por cada algoritmos em relação ao melhor conjunto encontrado entre todos.
Nos trabalhos pesquisados, Tabela 4.1, em nenhum trabalho foi encontrada a técnica CLO
pois, segundo Coello et al. (Coello e Veldhuizen 2007), a principal desvantagem do CLO é a
aleatoriedade da função objetivo, que, no caso de MOOP com grande número de funções objetivo
a aleatoriedade pode tender a uma determinada função ou grupo delas. Porém, para o PSP mode-
lado como um MOOP, tem-se duas funções objetivo o que não caracteriza a desvantagem citada
do CLO. Por outro lado, o CLO possui vantagem de tratar problemas que possuem a fronteira de
Pareto convexa, formato que tem apresentado as fronteiras dos problemas tratados neste trabalho.

4.5 CONCLUSÕES DO CAPÍTULO

Os algoritmos meta-heurísticos são amplamente utilizados na resolução de problema multi-

objetivos, em parte devido ao sucesso que obtiveram no tratamento de problemas NP-Completo

62
mono-objetivo. Para o problema de seleção de parâmetros das SVMs, dos sessenta e um artigos
encontrados sobre o assunto (vide Tabela 4.1), sete tratam o problema como um MOOP.
Por exemplo, para solução de problemas multimodais mono-objetivos, foram desenvolvidas
uma imensa variedade de técnicas de adição de diversidade com o objetivo de encontrar o equilí-
brio entre a exploração do espaço de busca e o refinamento das soluções. Para problemas multi-
objetivos, praticamente foram implementados apenas os algoritmos básicos das meta-heurísticas,
com pouco ou nenhuma adição de diversidade, ou técnicas para ajustes de parâmetros.
As métricas de avaliação da qualidade do conjunto de soluções não dominantes encontrada
pelos algoritmos meta-heurísticos tem-se mostrado um desafio, seja devido a complexidade com-
putacional ou a dependência da fronteira de Pareto conhecida. Entretanto é possível gerar um
conjunto de soluções não dominantes que é usado como referência para definir quais algoritmos
possuem um desempenho melhor quanto utilizado a métrica IGD.
A pesquisa bibliográfica também expõe a carência de algoritmos meta-heurísticos que tratam o
PSP como um MOOP, que foram desenvolvidos para geração de modelos SVM/SVRs para serem
utilizados em situações reais, principalmente em relação a aplicações práticas em que os modelos
são aproximadores de funções. Neste sentido, destaca-se a relevância dos algoritmos desenvol-
vidos neste trabalho, que possibilitam o ajuste dos hiperparâmetros das SVM/SVRs buscando o
compromisso entre complexidade e a precisão.
Minimizar os critérios complexidade e capacidade de generalização dos modelos SVM/SVRs
possui grande relevância em aplicações onde há restrição de energia, disponibilidade de hardware
e ainda se preza pela precisão do modelo, condições estas que motivaram o desenvolvimento das
meta-heurísticas APMT-MODE, AP-MODE e MOPSO.
A maioria dos trabalhos apresentados na Tabela 4.1, utilizam o kernel Gaussiano para levar os
dados ao espaço característica de dimensão superior onde os dados são linearmente separáveis.
Entretanto, para cada benchmark ou aplicação existe uma função kernel mais eficiente para cada
caso, quando considerados os critérios complexidade e precisão simultaneamente. Nenhum dos
trabalhos multiobjetivo pesquisados mencionam o uso de diversas funções kernel, ou mesmo, um
estudo de qual é mais eficiente para o problema abordado, o que mostra que há uma lacuna a
ser preenchida, o que expões os questionamentos: Qual função kernel é mais apropriado para
um determinado conjunto de treinamento, considerando os objetivos complexidade e precisão?
Quais os hiperparâmetros adequados para cada PSP (quando combinado kernel e conjunto de
treinamento)?
Toda função que satisfaz as condições do Teorema de Merce pode ser empregado como kernel
para um modelo SVM/SVRs, ou seja, existe inúmeros kernels com características diversas que
em sua lei de formação pode ser empregado operações trigonométricas, operações aritméticas,
exponenciais, constantes irracionais, raízes e outras. Portanto, reduzir as funções kernels a opera-
ções comuns ou definir métricas para comparar a complexidade destas funções é uma tarefa que
ainda não foi abordada na literatura. Tendo em vista que os poucos trabalhos que consideram
comparar a complexidade entre modelos de kernels distintos o fazem considerando a quantidade

63
de vetores de suporte do modele, o que computacionalmente, não é uma comparação justa.
Como solução para comparação da complexidade entre os modelos de SVM/SVRs com ker-
nels diferentes, neste trabalho, os modelos foram implementados em linguagem de programação
C e então, os modelos foram excutados no ARM e tomados seus tempos de execução.

64