Implementation of a user interface to select places and transitions

Metaheurísticas são ideias que podem ser aplicadas para o desenvolvimento de heurísticas para diferentes problemas. Devido a essa flexibilidade, geralmente elas possuem um conjunto de parâmetros que devem ser ajustados de acordo com o problema em que estão sendo empregadas. De modo análogo, os comitês de classificação possuem parâmetros que devem ser especificados devido às técnicas e representação empregadas. Esta seção apresenta como esses parâmetros são determinados, ou seja, como as soluções iniciais dos algoritmos de otimização são geradas e como os parâmetros dos algoritmos de otimização e os parâmetros de avaliação dos comitês são selecionados.

4.2.1 Soluções Iniciais

As técnicas de otimização utilizadas neste trabalho precisam de soluções iniciais para iniciar seu processamento. Para as técnicas baseadas em Busca Tabu é necessário fornecer uma solução inicial, isto é, um ponto de partida que será utilizada para gerar a estrutura de vizinhança e continuar o processamento deste ponto. Para as técnicas baseadas em Algoritmos Genéticos é necessário fornecer um conjunto de soluções iniciais, isto é, a população inicial a qual será aplicada os operadores de cruzamento e mutação para gerar uma nova população e assim continuar o processamento do algoritmo.

Em ambos os casos, as soluções são geradas por um mesmo processo: para cada posição do vetor booleano, que representa as variáveis independentes da solução, (ver 4.1.1) é sorteado, de modo uniforme, um valor aleatório no intervalo atribuindo o valor verdadeiro a esta posição do vetor caso o valor sorteado seja menor que 0,3 e falso em caso contrário. Assim, na maioria dos casos, uma solução inicial é um comitê de classificação onde todos os classificadores base estão ativos e cada uma utiliza um conjunto diferente de atributos da base de dados de quantidade próxima a 30% da quantidade total de atributos da base de dados.

Todas as soluções inicias geradas são válidas, isto é, possuem ao menos um classificador base ativo. Para as técnicas baseadas em Busca Tabu é gerada uma única solução inicial e para as técnicas baseadas em Algoritmos Genéticos é gerado um conjunto de soluções iniciais de cardinalidade igual ao tamanho da população usada pelo algoritmo. No caso do conjunto de soluções iniciais não garantimos que todas sejam diferentes, porém como as soluções são geradas por um processo estocástico é esperado que sejam diferentes.

4.2.2 Parâmetros dos Métodos de Construção

As técnicas de otimização utilizadas neste trabalho possuem diferentes parâmetros a serem ajustados, no entanto optamos por ajustar somente os principais parâmetros devido ao tempo necessário para gerar e avaliar os dados em função do tempo disponível para conclusão deste trabalho. Assim, para as técnicas baseadas em Busca Tabu ajustamos o tamanho da lista tabu e para as técnicas baseadas em Algoritmos Genéticos ajustamos a frequência em que o operador de mutação é aplicado.

A técnica de Busca Tabu mono-objetivo possui como parâmetros o tamanho da lista tabu, a quantidade de unidades em que o tamanho da lista é variado e a quantidade de soluções geradas para vizinhança. A versão

multiobjetivo possui os mesmos parâmetros com a adição da quantidade de vezes em que o mecanismo de diversificação é empregado. Em ambas as versões, a quantidade de soluções que o operador de vizinhança deve gerar é fixado em 30.

A técnica de Algoritmos Genéticos mono-objetivo possui como parâmetros a quantidade de indivíduos da população, a taxa de mutação e a taxa de cruzamento. A versão multiobjetivo possui os mesmos parâmetros. Assim como na Busca Tabu, a quantidade de indivíduos da população é fixada em 30.

Devido ao grande consumo de tempo computacional necessário para execução dos algoritmos de otimização utilizamos as bases de dados presentes na tabela 3 para realização desses experimentos (demoram cerca de uma semana para obter os resultados devido a infra-estrutura disponível), isto é, ajuste do tamanho da lista tabu e da frequência de aplicação do operador de mutação. Elas foram escolhidas de modo a representar as bases de dados presentes na tabela 13 (ver 4.3.1) em função da quantidade de atributos, instâncias, classes e presença de valores faltosos. Os parâmetros selecionados utilizando este subconjunto das bases de dados são aplicados aos algoritmos utilizados nos experimentos finais.

Bases de Dados Usadas para Seleção de Parâmetros Nº Base Quantidade de Atributos Quantidade de

Instâncias Quantidade de Classes Valores Faltosos 4 _{Car 6 (0/6) 1728 4 Não} 6 _{Dermatology 34 (1/33) 366 6 Sim} 13 _{Ionosphere 34 (34/0) 351 2 Não} 14 _{Iris 4 (4/0) 150 3 Não} 19 _{Protein 126 (126/0) 583 5 Não} 20 _{Segment 19 (19/0) 1500 7 Não} 22 _{Simulated 600 (600/0) 60 6 Não} 24 _{Soybean 35 (0/35) 683 19 Sim} 30 _{Wine 13 (13/0) 178 3 Não}

Tabela 3: Bases de dados utilizadas nos experimentos para determinação dos parâmetros dos algoritmos de otimização. A coluna quantidade de atributos apresenta a quantidade de atributos na forma . Onde representa a quantidade total de atributos, representa a quantidade de atributos numéricos e a quantidade de atributos nominais.

Foram realizados experimentos para os algoritmos baseadas em Busca Tabu a fim de selecionar o melhor tamanho da lista tabu. Esses experimentos consistiram em 10 execuções de 3 minutos de cada algoritmo (Alg.T1-T3 e Alg.M1-M4) em cada base de dados presente na tabela 3 variando o tamanho da lista tabu em 20%, 30% e 40% da quantidade de atributos da base com no mínimo de uma posição. Nenhuma das comparações apresentou diferença significativa, isto é, todos os algoritmos são equivalentes para os valores experimentados. Assim, adotamos o valor de 30% nos experimentos finais.

Foram realizados experimentos para os algoritmos baseados em Algoritmo Genéticos a fim de selecionar a melhor taxa de mutação. Esses experimentos consistiram em 10 execuções de 3 minutos de cada algoritmo (Alg.G1-G3 e Alg.N1-N4) em cada base de dados presente na tabela 3 variando a taxa de mutação 1%, 5% e 10% de aplicações. Somente o algoritmo o algoritmo Alg.N2 apresentou diferenças significativas nos experimentos onde os resultados para os parâmetros de 10% e 5% são equivalentes e os resultados para os parâmetros de 1% melhores (valor de probabilidade de 0.047 em relação aos resultados de 10% e 0.047 em

relação aos de 5%). Porém, como foram observadas diferentes somente neste algoritmo optamos por manter a taxa de mutação em 10%.

O apêndice B deste trabalho apresenta a acurácia de cada algoritmo para cada base de dados nos casos experimentais citados.

4.2.3 Parâmetros da Avaliação das Soluções

A representação das soluções necessita que uma quantidade máxima de classificadores que compõem o comitê seja especificada antes da execução dos processos de otimização. O processo de otimização pode escolher a quantidade de classificadores entre um e a quantidade máxima especificada. É esperado que a acurácia dos comitês melhore com o aumento da quantidade de classificadores. Porém, quanto mais classificadores, maiores são recursos consumidos, isto é, memória necessária de armazenamento e tempo de processamento para treinar cada classificador.

Os experimentos realizados possuem como condição de parada o tempo de execução de 3 minutos ou a quantidade máxima de 500 iterações. Aumentar a quantidade de classificadores significa aumentar o tempo necessário para avaliar as soluções e assim, o algoritmo de otimização terá menos tempo para realizar a busca. No pior caso, o algoritmo irá consumir todo o tempo de processamento na avaliação de uma única solução e, no caso ideal, é desejado que o tempo gasto na avaliação não seja capaz de influenciar os resultados do algoritmo.

Assim, são executados experimentos para verificar como a quantidade de classificadores base influencia a acurácia dos comitês gerados e qual a melhor quantidade a ser utilizada nos experimentos. Cada algoritmo apresentado na tabela 2 é executado para as bases de dados presentes na tabela 3 variando a quantidade de classificadores base entre 3, 5 e 10. Cada algoritmo é executado 10 vezes utilizando como critério de parada a execução de 3 minutos ou 500 iterações.

Os resultados destes experimentos (APÊNDICE C) mostram que quase todos os algoritmos são equivalentes em relação à acurácia com poucas exceções. A tabela 4 apresenta as comparações em que o teste WSR verificou uma diferença significativa (valor de probabilidade menor que 0.05). Nos demais casos é indiferente utilizar 3, 5 ou 10 classificadores como quantidade máxima em relação à acurácia dos comitês gerados.

Diferenças dos Resultados Quanto a Quantidade Máxima de Classificadores

Algoritmo Comparação Valor-p Melhor Quantidade

Alg.T1 3 x 10 0.046 3 Classificadores

Alg.T2 3 x 5 0.012 5 Classificadores

Alg.M4 5 x 10 0.018 5 Classificadores

Alg.G2 3 x 5 0.012 5 Classificadores

Alg.G2 3 x 10 0.046 10 Classificadores

Tabela 4: Diferenças significativas da acurácia dos comitês gerados em relação à quantidade máxima de classificadores base.

Os resultados mostram que os comitês fazem uso da quantidade máxima de classificadores com exceção das bases de dados Soybean, Iris e Car (APÊNDICE C). Tais bases não utilizam a quantidade máxima de classificadores base. Esse comportamento se verifica em quase todos os algoritmos. No entanto, na maioria

dos casos, a quantidade de classificadores aumenta em função do aumento da quantidade máxima de classificadores base. A tabela 5 apresenta os resultados associados a essas bases.

Quantidade Média de Classificadores Utilizados

Car Soybean Iris

Algoritmo 3 5 10 3 5 10 3 5 10 Alg.T1 2.4 4.2 8.9 2 4.3 6 2.0 4 8.2 Alg.T2 3 5 9.2 3 5 10 3 5 10 Alg.T3 1.3 3.1 8.6 1 1 1 1 1 1 Alg.M1 2.603 4.758 9.3 3 5 9.967 2.333 4.4 9.94 Alg.M2 1.733 4.1 7.7 1 1.45 2.65 1.633 1.725 2.467 Alg.M3 2.501 4.477 9.233 2.2 2.745 5.6 2 3 7.899 Alg.M4 2.395 4.46 8.65 2.414 3.271 7.034 2 3.043 8.644 Alg.G1 2.8 5 9.3 3 4.8 8.7 2 4 9.4 Alg.G2 3 5 10 3 5 10 3 5 10 Alg.G3 1.3 3.8 8.7 1 1 1 1 1 1 Alg.N1 2.909 4.949 9.503 3 5 9.85 2.76 4.798 9.971 Alg.N2 2.558 4.632 8.987 1 1 3.179 1.3 1.7 2.334 Alg.N3 2.702 4.797 9.486 2.467 3.395 6.959 2.573 4.14 8.102 Alg.N4 2.838 4.85 9.38 2.77 3.437 7.447 2.275 4.356 8.253

Tabela 5: Quantidade média de classificadores utilizados para as execuções variando a quantidade máxima de classificadores base entre 3, 5 e 10.

Outro fator observado é que em todos os experimentos se verifica uma diminuição da quantidade de iterações proporcional ao aumento da quantidade máxima de classificadores base. A tabela 6 apresenta o comportamento da quantidade de iterações do algoritmo Alg.T1 utilizando 3, 5 e 10 como quantidade máxima de classificadores base. Os demais algoritmos apresentam comportamento semelhante (APÊNDICE C).

Iterações do Algoritmo Alg.T1

Base 3 5 10 Car 23.9 15.3 5 Dermatology 142.8 97.6 56.5 Ionosphere 104.7 67.6 33.5 Iris 500 500 440.2 Proteina 9.8 6.2 2.9 SegmentChallenge 10.4 5.8 2.8 Simulated 135.8 83.5 41.8 Soybean 159.2 104.6 51 Wine 500 349.9 180.2

Tabela 6: Quantidade de iterações do algoritmo Alg.T1 para as execuções utilizando 3, 5 e 10 como quantidade máxima de classificadores base. A quantidade máxima de iterações nesses experimentos é 500.

Em vista dos resultados obtidos, não é possível determinar qual a melhor quantidade máxima de classificadores base. Utilizar 3 classificadores base aumenta a quantidade de iterações dos algoritmos, porém, pode ser uma quantidade muita pequena de classificadores que com o aumento do tempo de execução dos algoritmos pode prejudicar o desempenho dos comitês gerados. Por outro lado, a quantidade de 10

classificadores diminui a quantidade de iterações, mas com o aumento do tempo de execução pode melhorar o desempenho dos comitês. Como as quantidades de 3, 5 e 10 classificadores se mostraram equivalentes optamos realizar duas análises experimentais: um caso experimental utilizando a quantidade máxima de 3 classificadores base e outro utilizando 10.