Embed Size (px)
Citation preview
Guilherme de Paiva Pacheco
Algoritmos Genéticos - Efeitos da Utilização
de um Ranking Adaptativo de Diversidade na Convergência Prematura e Diversidade da
População
Belo Horizonte, MG – Brasil Junho de 2013
1
Guilherme de Paiva Pacheco
Algoritmos Genéticos - Efeitos da Utilização de um Ranking Adaptativo de Diversidade na
Convergência Prematura e Diversidade da População
Monografia submetida à banca
examinadora designada pelo Colegiado Didático do Curso de Graduação em Engenharia de Controle e Automação da Universidade Federal de Minas Gerais, como parte dos requisitos para aprovação na disciplina Projeto de Final de Curso II.
Orientador Frederico Gadelha Guimarães, Dr.
Supervisor Alan Robert de Freitas, Dr.
ESCOLA DE ENGENHARIA UNIVERSIDADE FEDERAL DE MINAS GERAIS
Belo Horizonte, MG – Brasil Junho de 2013
2
Agradecimentos
Dedico este trabalho aos meus pais, Wilma e Marcos, por todo carinho e compreensão ao longo destes duros anos de graduação. Às minhas metades Alice, Débora e Marianna, meus melhores ângulos. Aos meus melhores amigos, Lucas, Tatá, Dhiapa, Bernardo, Raíssa e Henrique, pelas alegrias e tristezas divididas nesses anos de jogos, viagens, estudos e palhaçadas. Ao meu irmão Leandro, um dos meus maiores porto-seguros. Ao John, por jogar na minha cara tudo que eu empurrava às tangências. Muito obrigado. Ao Renan, por me fazer inspirar Gorecki e expirar Lullaby... E, por último mas não menos importante: à Tita, pela companhia e amor insubstituíveis. Agradeço também ao Joss Whedon, pelo pano de fundo da minha imaginação.
3
Resumo
Algoritmos Genéticos se figuram como um dos principais métodos de otimização utilizados atualmente. Apesar disso, sua forma de funcionamento pode favorecer a convergência prematura da população em um ótimo local, o que prejudica a busca pelo ótimo global. Com o objetivo de impedir esse fenômeno, diferentes técnicas foram propostas para aumentar ou manter a diversidade da população ao longo da execução do algoritmo. O objetivo do presente estudo foi criar um ranking que selecione não somente os indivíduos com maior fitness, mas também os que apresentem diferença estrutural mínima de outros indivíduos previamente selecionados. Além disso, de forma a garantir uma melhor exploração do espaço amostral do problema, foi utilizada uma técnica que altera o funcionamento do ranking ao longo da execução, adequando-o aos estados de convergência da população e otimizando o seu funcionamento. Os testes foram aplicados em diferentes instâncias do Problema da Mochila, verificando o efeito do ranking em diversas combinações de tamanhos de população e tamanhos de indivíduos. Os resultados demonstraram os efeitos positivos provocados na eficiência e eficácia do algoritmo, além do aumento da diversidade da população ao longo de sua execução. Foi observada, no entanto, maior demanda computacional, já esperada devido às técnicas utilizadas para a construção do ranking.
4
Abstract Genetic Algorithms represents one of the main optimization methods used nowadays. Nevertheless, its operating manner may lead to a premature convergence to a local optimum, what can prejudice the search for the global optimum. Several techniques were proposed trying to prevent that from happening. The main purpose of this present study was to create a ranking that selects not only individual with greater fitness but also individuals with a minimum structural difference from others already selected. In addition, in an attempt to guarantee a better sample space exploration, a technique that alters the ranking behavior was used in order to adapt it to different population convergence states, improving its operation. The tests were applied in different instances of the Knapsack Problem, analysing the ranking effect in different combinations of population and individual sizes. The results demonstrated the positive effects in the algorithm's effectiveness and efficiency. Moreover, an increase in population diversity during execution was also demonstrated. It was observed, however, greater computational demand, already expected due to the techniques used to build the ranking.
5
Sumário
1. CAPÍTULO 1 .................................................................................................................... 9 1.1. INTRODUÇÃO ....................................................................................................................... 9 1.2. MOTIVAÇÃO ...................................................................................................................... 11 1.3. AMBIENTE DE DESENVOLVIMENTO .................................................................................. 14
2. CAPÍTULO 2 .................................................................................................................. 15 2.1. ESTADO DA ARTE .............................................................................................................. 15 2.2. DIVERSIDADE POR DIVISÃO DA POPULAÇÃO EM GRUPOS FUNCIONAIS ............................ 16 2.3. DIVERSIDADE POR OPERADORES ADAPTATIVOS .............................................................. 18 2.4. DIVERSIDADE PELA REINICIALIZAÇÃO DA POPULAÇÃO ................................................... 19 2.5. DIVERSIDADE PROPORCIONADA PELO RANKING .............................................................. 22
3. CAPÍTULO 3 .................................................................................................................. 26
3.1. GA-FRAMEWORK .............................................................................................................. 26 3.2. CONFIGURAÇÕES ADOTADAS NO PROJETO ....................................................................... 29 3.3. O PROBLEMA DA MOCHILA ............................................................................................... 32 3.4. DETALHES DE IMPLEMENTAÇÃO ....................................................................................... 35
4. CAPÍTULO 4 .................................................................................................................. 41 4.1. INSTÂNCIA COM 100 INDIVÍDUOS COM 500 BITS CADA ................................................... 41 4.2. RESULTADOS GERAIS PARA AS 9 INSTÂNCIAS .................................................................. 51 5. CAPÍTULO 5 .................................................................................................................. 54
5.1. CONCLUSÃO DO PROJETO .................................................................................................. 54 5.2. TRABALHOS FUTUROS ....................................................................................................... 55 REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................... 57
6
Lista de Figuras
FIGURA 1.1 - Exemplo de um Crossover .................................................................. 10
FIGURA 1.2 – Exemplo de uma Mutação .................................................................. 11 FIGURA 1.3 – Função Multimodal ............................................................................ 12 FIGURA 1.4 – Função Rastrigin ................................................................................ 13 FIGURA 2.1 – Esquema de Reprodução no Algoritmo de Taejin Park ..................... 17 FIGURA 2.2 – Exemplo da utilização da distância de Hamming ............................... 20 FIGURA 2.3 – Esquema do Ranking por Diversidade, proposto por Oliveira .......... 23 FIGURA 2.4 – (a) Exemplo de um centro de região .................................................. 24 FIGURA 2.4 – (b) Exemplo da não Transitividade da Divisão por Região ................ 24 FIGURA 3.1 – Estrutura do GA-Framework utilizado. ................................................ 27 FIGURA 3.2 – Retrato da GUI utilizada no GA-Framework de Alan de Freitas ....... 28 FIGURA 3.3 – Problema da Mochila ......................................................................... 32 FIGURA 3.4 – Exploração do espaço amostral pelo ranking com diversidade ......... 38 FIGURA 4.1 – Melhor resultado para f(x) em função do tempo – Instância V ........... 42 FIGURA 4.2 – Resultado do teste de Kruskal Wallis – Instância V .......................... 44 FIGURA 4.3 – Número de gerações em função do tempo – Instância V .................. 45 FIGURA 4.4 – DH média da população em função do tempo – Instância V ............. 46 FIGURA 4.5 – Detalhe da diminuição de variedade da população – Instância V ..... 47 FIGURA 4.6 – Entropia da população em função do tempo – Instância V ............... 48 FIGURA 4.7 – Número de grupos em função do tempo – Instância V ...................... 49 FIGURA 4.8 – Valor de Ɛ ao longo da execução – Instância V ................................. 50 FIGURA 4.9 – Resultado gráfico do teste de Friedman para as 9 instâncias ............ 52 FIGURA 4.10 – Melhor resultado para f(x) em função do tempo – Instância VIII ...... 53 FIGURA 4.11 – Número de gerações em função do tempo – Instância VIII .............. 53
7
Lista de Tabelas
TABELA 3.1 – Instâncias utilizadas para os testes. .................................................. 34 TABELA 3.2 – Dinâmica do valor de Ɛ ao longo da execução ................................. 39 TABELA 4.1 – Resultados finais encontrados em 20 execuções da Instância V .... 43 TABELA 4.2 – Resultados finais para as 9 instâncias .............................................. 51
8
Lista de Acrônimos
AG Algoritmos Genéticos GUI Grafical User Interface DH Distância de Hamming MP Main Population RP Reserve Population
9
1. CAPÍTULO 1 1.1. INTRODUÇÃO Em meio ao crescente ramo da computação evolucionária, a técnica dos
Algoritmos Genéticos (AGs) vem recebendo bastante destaque devido à sua eficácia
e simplicidade de suas soluções. Pode-se dizer que os AGs se figuram como um
método de pesquisa estocástico que se baseia nos princípios da genética e da
seleção natural (Xinping et al., 2009; Goldberg, 1989). São algoritmos criados para
buscar soluções de problemas complexos, cujo espaço amostral é considerado
extenso demais para ser percorrido por um algoritmo determinístico. Diferentemente
de outras técnicas de busca, que utilizam majoritariamente métodos numéricos, a
técnica dos AGs inicia a pesquisa por meio de um grupo de soluções aleatórias,
chamado de “população”. Os indivíduos desse grupo são denominados
“cromossomos” que, em geral, podem ser representados por uma cadeia, ou string,
de bits, em que cada bit é considerado um “gene” do cromossomo. Cada gene
fornece alguma característica ao seu cromossomo, contribuindo de alguma forma
para a qualidade da solução.
Os termos utilizados são os mesmos que os presentes na biologia devido ao
fato de que o processo de busca se baseia na evolução desses cromossomos por
meio de sucessivas iterações, que recebem o nome de “gerações”. Durante cada
geração, os cromossomos são avaliados quanto à qualidade da solução
correspondente frente a algum critério de seleção – chamada função fitness, que
varia de acordo com o objetivo do problema. Assim, os cromossomos que
apresentam os melhores fitness são selecionados em detrimento daqueles que não
apresentaram soluções tão satisfatórias frente ao critério de seleção pré-
estabelecido. A expectativa é de que, após várias iterações, o algoritmo convirja
para a melhor solução (Mitsuo e Runwei, 1999).
O método tradicionalmente utilizado para formar uma nova população é
constituído três etapas. Inicialmente, a aptidão dos cromossomos é avaliada pelo
fitness, a qual permite que os cromossomos sejam classificados e organizados
frente a alguma estratégia, como maximização de um valor, ou a minimização de um
10 erro em um controlador, por exemplo. Assim, é possível selecionar os cromossomos
mais adequados para a reprodução e consequente transmissão de genes para as
futuras populações. Há vários métodos de seleção destes indivíduos. No entanto,
normalmente em um algoritmo genético tradicional, utiliza-se o critério de seleção
por roleta, no qual os indivíduos são ordenados exclusivamente de acordo com o
fitness das soluções, e lhes são atribuídos probabilidades decrescentes de serem
escolhidos, as quais são proporcionais à razão entre o fitness do indivíduo e a soma
dos fitness de todos os indivíduos da população. A seleção é, então, realizada tendo
como base essas probabilidades, com o objetivo de garantir a escolha dos
indivíduos melhor adaptados, sem, contudo, desconsiderar completamente a
variedade desses indivíduos, já que por ser um método estocástico, os menos
adaptados podem também ser escolhidos, apesar da menor chance (Linden, 2008).
Após a seleção dos indivíduos, é realizado o Cruzamento, ou Crossover,
técnica na qual alguns genes de ambos os pais selecionados são replicados e
mesclados, originando, em geral, dois novos indivíduos. Essa recombinação visa
garantir que os indivíduos mais bem adaptados troquem entre si informações que os
levem a ser mais aptos a sobreviver, e futuramente gerar descendentes ainda mais
aptos (Goldberg, 1989), com maior fitness. Essa técnica é ilustrada pela Figura 1.1,
em que as duas palavras binárias inferiores são constituídas pela combinação das
metades das palavras superiores.
Figura 1.1 - Exemplo de um Crossover
Já com o objetivo de inserir certa variabilidade na população e impedir que
esta convirja prematuramente em um ótimo local, é realizada a Mutação, técnica na
11 qual um gene específico de algum indivíduo integrante da população atual é
escolhido estocasticamente, e, então, modificado, também de forma estocástica
(Goldberg, 1989). A Figura 1.2 exemplifica a técnica da Mutação, em que o sétimo
bit da palavra tem seu valor invertido, de ‘0’ para ‘1’.
Figura 1.2 – Exemplo de uma Mutação
Existem diferentes tipos de implementação de algoritmos genéticos, seja com
variações mais básicas nos critérios de seleção, ou na taxa de mutação; ou também
com mudanças mais drásticas como uma reestruturação da população para atender
diferentes objetivos. Algumas dessas diferentes implementações serão abordadas
no capítulo seguinte. Para a abordagem do problema, será tratado como o algoritmo
genético tradicional aquele que funciona da forma descrita acima, com o critério de
seleção através de um ranking baseado exclusivamente no fitness dos indivíduos.
1.2. MOTIVAÇÃO
O objetivo de um AG é encontrar o ótimo global de um determinado problema.
No entanto, em situações nas quais os problemas envolvam funções multimodais e
os algoritmos genéticos sejam implementados, à medida que a população evolui ao
longo das sucessivas iterações, é comum que esta convirja e fique aprisionada em
uma bacia de ótimo local. Dessa forma, com a população pouco diversificada dentro
dessa bacia é pouco provável que algum indivíduo das populações futuras escape
da bacia a fim de encontrar o ótimo global, o que caracteriza uma convergência
prematura. A única estratégia fornecida pelo AG tradicional para evitar a
12 convergência prematura é a mutação, que, no entanto, é um método muitas vezes
insuficiente para evitar esse fenômeno.
O efeito descrito no parágrafo acima pode ser identificado com o auxílio da
Figura 1.3, a qual representa a função sinc(x), expressa pela Equação 1.
𝑠𝑖𝑛𝑐 𝑥 =sin (𝑥)𝑥 (1)
Figura 1.3 –Função Multimodal
A função sinc(x) representa um tipo básico de uma função com diversos
ótimos locais e um único ótimo global. Ao se executar um AG tradicional, a
população pode ficar aprisionada dentro de um dos ótimos locais e
consequentemente não explorar o espaço amostral o bastante a fim de identificar a
existência do ótimo global da função, o que resulta em uma solução equivocada. A
função sinc(x) é uma função bidimensional e relativamente simples, na qual é fácil
observar que o máximo encontrado se trata de um máximo local e não um máximo
global. No entanto, em problemas mais complexos e com maior número de
dimensões, a identificação das diferenças entre esses máximos pode ser difícil,
sendo necessário um algoritmo genético eficaz e com maiores probabilidades de
encontrar o máximo global, frente aos algoritmos genéticos tradicionais.
A Figura 1.4 representa a função Rastrigin, expressa pela Fórmula (2), uma
função multimodal, tridimensional, com vários ótimos locais, e um único ótimo global.
É necessário um AG que seja eficaz para que se encontre o mínimo global da
função, de modo que não ocorra uma convergência prematura em algum dos vários
13 mínimos locais do espaço amostral. É justamente por essa dificuldade que a função
Rastrigin é muito utilizada para se avaliar a eficiência de algoritmos genéticos (Törn
e Zilinskas, 1989).
𝑓 𝑥 = 20 + 𝑥!! − 10 cos 2𝜋𝑥!
!
!!!
(2)
Figura 1.4 –Função Rastrigin
Fonte: http://www-optima.amp.i.kyoto-u.ac.jpg
É neste contexto que o presente estudo propôs melhorias. Uma alternativa
para evitar a convergência prematura consiste em modificar a estratégia do ranking,
de tal forma que não somente as soluções com maior fitness sejam valorizadas, mas
também as soluções que garantam a diversidade da população. A estratégia de
manutenção da diversidade da população vem sendo abordada na literatura de
diferentes formas, sendo as mais recorrentes apresentadas e discutidas no próximo
capítulo.
O objetivo deste trabalho é simular e comparar, em diferentes instâncias de
um problema de otimização, algoritmos genéticos com o ranking exclusivamente
baseado no fitness dos indivíduos, frente a algoritmos genéticos com ranking
visando também a manutenção da diversidade. A manutenção da diversidade da
14 população é promovida por meio da inserção de um código, desenvolvido nesse
projeto, em um toolbox para análise de algoritmos genéticos.
Ao final do trabalho, estáo apresentados os resultados obtidos a partir das
comparações entre as simulações, o que possibilitará avaliar o efeito da manutenção
da diversidade da população sobre a qualidade de um AG. O estudo medirá e
avaliará quatro efeitos principais dessas modificações enunciadas, que são
Ø Eficiência do Algoritmo.
Ø Eficácia do Algoritmo.
Ø Variedade da população ao longo da execução do algoritmo.
Ø Custo computacional decorrente das modificações.
1.3. AMBIENTE DE DESENVOLVIMENTO
O projeto será desenvolvido no software Matlab® Versão 2011, em um
toolbox, ou framework, de Algoritmos Genéticos. O toolbox pode ser obtido no
próprio site da MathWorks®. Essa ferramenta possibilita uma execução versátil de
algoritmos genéticos em qualquer problema de otimização criado pelo usuário.
Alguns problemas de otimização mais conhecidos estão disponibilizados junto ao
toolbox, como exemplo. O programa fornece resultados e características da
população a cada iteração do algoritmo. A versatilidade da execução diz respeito ao
fato de que é possível alterar vários parâmetros do algoritmo, como a taxa de
mutação, taxa de cruzamento, competição entre pais e filhos, dentre outros. Todos
os parâmetros relevantes à execução do projeto serão ressaltados nos próximos
capítulos.
No presente estudo, de forma a avaliar os efeitos de um ranking que garanta
a diversidade da população e uma melhor exploração do espaço amostral, foi
implementado um algoritmo que divide a população em grupos de similaridade
estrutural, e outro algoritmo que aumenta as chances de que todos os grupos
possuam ao menos um representante selecionado para realizar a reprodução, a fim
de evitar que a população perca sua diversidade e, consequentemente, genes
importantes que levariam o algoritmo à solução global. O código em Matlab criado
foi incluído dentro do framework, e, então, com as ferramentas disponibilizadas por
este, foi possível avaliar os resultados práticos de um AG com ranking que promova
a diversidade da população e comparar com os resultados de um que possua
ranking apenas pelo fitness das soluções.
15
2. CAPÍTULO 2 2.1. ESTADO DA ARTE
Estratégias utilizadas com o objetivo de evitar a convergência prematura em
algoritmos genéticos têm sido discutidas na literatura e, apesar de serem
fundamentalmente diferentes, a maioria apresenta medidas de investimento na
manutenção da diversidade da população. Essa diversidade, no entanto, pode ser
avaliada de diferentes maneiras. De acordo com Jackson et al. (2011) há duas
formas principais de se avaliar a diversidade de uma população: por meio da
variedade genética, e por meio da variedade fenotípica dos indivíduos.
A variedade genética pode ser avaliada observando-se a quantidade de
indivíduos de uma população estruturalmente diferentes uns dos outros (Jackson,
2011; Burke et al. 2002). Em situações nas quais os indivíduos são representados
por palavras binárias, como no presente estudo, essa diferença se baseia na
comparação bit a bit, de posições correspondentes, entre as palavras, de modo que
quanto maior a quantidade de bits diferentes, maior a diferença estrutural entre os
indivíduos. Sendo assim, uma população com maior número de indivíduos
estruturalmente diferentes uns dos outros, representa uma população mais
diversificada.
Uma das formas de se mensurar a diversidade genética da população é pela
razão entre a quantidade de indivíduos estruturalmente diferentes e a quantidade de
indivíduos possível em uma população. Quanto maior for essa razão, maior a
diversidade da população, e, sendo essa razão igual a ‘1’, todos os indivíduos são
estruturalmente diferentes uns dos outros (Jackson, 2011). Essa prática, no entanto,
é apropriada para problemas em que a quantidade de bits dos indivíduos possibilite
um número não muito maior do que o número de indivíduos na população. Para o
caso de indivíduos de 64 bits representando números reais, a diversidade da
população por esse método estaria sempre baixa, tendo em vista que a quantidade
de indivíduos possível é muito superior a um tamanho viável para a população.
Além de pela quantidade de indivíduos estruturalmente diferentes uns dos
outros, a variedade genética também é observada pelo quão diferentes são os
16 indivíduos uns dos outros. Uma população cujos indivíduos apresentem uma
diferença estrutural média de 60%, aproximadamente, representa uma população
com maior diversidade que uma população que apresente uma diferença de apenas
20%.
A variedade fenotípica, por sua vez, é relacionada aos resultados da
avaliação dos indivíduos. O exemplo mais comum de avaliação fenotípica é a
avaliação por fitness, mencionada no capítulo anterior. Neste contexto, uma
variabilidade fenotípica seria a presença de indivíduos que apresentem valores
diversificados de fitness, de forma que mesmo indivíduos que sejam estruturalmente
diferentes possam ser considerados idênticos ao se avaliar o fitness dos mesmos.
Ambas as formas de variedade, genética e fenotípica, em geral ocorrerem
paralelamente. A mutação, por exemplo, é uma operação que atua visando
diretamente a variação genética. A variação fenotípica, neste caso, ocorre de modo
indireto. A inversão estocástica de bits na palavra aumenta a diversidade entre os
indivíduos da população. O presente estudo optou por mensurar e atuar diretamente
na variabilidade genética, portanto, as seções seguintes evidenciam alguns dos
métodos mais comumente utilizados para se inserir este tipo de diversidade na
população.
2.2. DIVERSIDADE POR DIVISÃO DA POPULAÇÃO EM GRUPOS FUNCIONAIS
Como forma de garantir a manutenção da diversidade na população, Taejin et al.
(2007) implementou uma mudança estrutural em seu algoritmo. Neste, a população
foi dividida em dois grupos funcionais com objetivos distintos: o primeiro, chamado
de Main Population, MP, tem como propósito o principal do algoritmo, que é
encontrar após sucessivas iterações a solução ótima ao problema em questão; e um
segundo grupo, chamado de Reserve Population, RP, que tem como objetivo
realizar a manutenção da diversidade. Dessa forma, os critérios de seleção,
reprodução e mutação são diferentes para cada um desses grupos e, inclusive, até
mesmo o fitness para esses grupos são avaliadas de formas diferentes para que
estes atinjam seus respectivos objetivos. Os grupos, no entanto, não são isolados
um do outro: eles trocam informações entre si, de tal forma que o algoritmo procura
obter soluções diversificadas, com os genes provenientes da RP, e que também
17 apresentem alto valor de fitness, com os genes dos indivíduos da MP. Um
esquemático de como é feita a iteração e a troca de informação entre esses dois
grupos é apresentado no diagrama a seguir (Taejin e Kwang, 2007).
Figura 2.1 –Esquema de Reprodução no Algoritmo de Taejin Park
Fonte: (Taejin; 2007) Modificada pelo autor.
Apesar dos resultados encontrados para este tipo de implementação terem
sido satisfatórios, o lado negativo deste tipo de abordagem é que ao longo da
execução do algoritmo, e da inevitável convergência da população, os filhos
provenientes da RP raramente possuíam um fitness alto o suficiente para competir
com os filhos da MP, que em geral já estavam muito mais evoluídos, e assim, os
primeiros não eram selecionados e não mais contribuíam para a evolução da
população (Taejin e Kwang, 2007). Medidas estratégicas na seleção dos pais de
ambas as populações foram tomadas para atenuar este efeito, não obstante, a
probabilidade dos filhos da RP não serem selecionados foi significante.
Dessa forma, apesar da ideologia de garantir a diversidade da população pela
sua divisão em diferentes grupos ser comum ao método do presente estudo, a
divisão de funcionalidade entre esses grupos, no entanto, não será adotada. A
técnica do ranking pretendida neste trabalho necessita apenas da divisão da
população em grupos de semelhança estrutural, e não em grupos com diferentes
fins.
18 2.3. DIVERSIDADE POR OPERADORES ADAPTATIVOS
Outra estratégia bastante difundida na literatura é utilizada por Liu Xinping et
al. (2009). Também de acordo com Xinping (2009), a diversidade da população ao
longo da execução do algoritmo é de importância fundamental para se alcançar a
convergência global para o problema. Para tal, ele utiliza o conceito de distância
Hamming, DH, que é aplicável para indivíduos representados por cadeias de bits,
que é a forma de representação adotada para as soluções deste trabalho. A
distância Hamming, Hi, é definida pela Fórmula 3.
𝐻!" = (|𝑋!" − 𝑋!"|)!
!!!
𝑖 ≠ 𝑗 (3)
Os termos Xik e Xjk denotam o k-ésimo bit dos indivíduos Xi e Xj,
respectivamente. E ‘L’ equivale ao tamanho desses indivíduos. Logo, nota-se que
quanto maior for a diferença bit a bit dos indivíduos, maior será a DH entre eles. Em
seguida, é introduzida a medida adotada para se mensurar a diversidade da
população em relação a um indivíduo específico, Di, que é definida como a soma
das DH de todos os indivíduos da população em relação a um específico Xi. Essa
medida pode ser expressa pela Fórmula 4 (Xinping et al. 2009).
𝐷! = 𝐻! =!!!
!!!
(|𝑋!" − 𝑋!"|)!
!!!
!!!
!!!
𝑖 ≠ 𝑗 (4)
Xinpig defende que operadores de mutação e cruzamento estáticos
contribuem para uma convergência prematura do algoritmo, e, portanto ele sugere a
adoção de operadores adaptativos. Para tal, ele faz uso dos conceitos enunciados
acima para calcular em tempo real o valor ideal, em função da variabilidade da
população, para os operadores de mutação e cruzamento de forma a evitar a
convergência prematura da população. Sendo assim, é sugerida a aplicação das
seguintes fórmulas para se obter adaptativamente os operadores de cruzamento, Pc,
e de mutação, Pm.
19
𝑃! =𝑃!!.
!!"#!!!!!!"#!!!"#
+ 𝑃!!, 𝐷!! ≤ 𝐷!"#𝑃!!, 𝐷!! > 𝐷!"#
(5)
𝑃! =𝑃!!.
!!"#!!!!!"#!!!"#
− 𝑃!! − 𝑃!! .!!"#!!
!!"#!!!"#, 𝐷! ≥ 𝐷!"#
𝑃!!, 𝐷!! < 𝐷!"# (6)
Em que Pc1 e Pc2 representam a maior e menor probabilidade de cruzamento;
Pm1 e Pm2 são a maior e menor probabilidade de mutação, sendo todos estes valores
estipulados pelo programador do algoritmo. Dmed, Dmin e Di correspondem à média
das medidas de diversidade da população, ao menor valor de diversidade da
população, e ao valor de diversidade de um indivíduo específico, respectivamente.
D’i corresponde à menor medida de diversidade dentre os pares selecionados para
realizar o cruzamento. E, finalmente, fmax, fmed e f correspondem ao valor de fitness
máximo da população, ao valor de fitness médio e ao valor de fitness do indivíduo,
respectivamente.
Os resultados obtidos evidenciaram uma melhora na eficácia e rapidez na
obtenção dos resultados, diminuindo a ocorrência de convergências prematuras.
Desta forma, a estratégia de operadores adaptativos por eles adotada foi bem
sucedida. No entanto, para este projeto, a utilização deste tipo de mecanismo de
adaptação para os operadores poderia camuflar os efeitos da manutenção da
diversidade proporcionada pelo ranking criado, tornando difícil a distinção dos efeitos
provocados por cada um destes métodos isoladamente. Sendo assim, optou-se pela
utilização apenas da estratégia do ranking de diversidade, mantendo os operadores
de cruzamento e mutação fixos em seus valores iniciais.
2.4. DIVERSIDADE PELA REINICIALIZAÇÃO DA POPULAÇÃO
Uma das formas de se inserir diversidade na população é por meio da
reinicialização desta, ou seja, por meio da geração de novos indivíduos de forma
estocástica. Este procedimento é comumente feito quando é identificado o
Takeover.
Takeover é o termo dado para o momento em que toda a população converge
para um ou poucos indivíduos, com pouca variabilidade de fitness dentre eles, de
forma que a partir desse ponto esta passa a depender integralmente da mutação
20 para inserir alguma variabilidade que resulte em uma solução diferente do ótimo já
encontrado. Dessa forma, a população para de evoluir independentemente de
quantas iterações o código execute, resultando em um desperdício de tempo e de
demanda computacional.
Os algoritmos genéticos que operam com a técnica de reinicialização da
população necessitam de uma forma para detectar quando o takeover ocorreu, de
modo a poder reinicializar a população e procurar mais uma vez por um ótimo global.
O critério de detecção de takeover pode variar de problema para problema e de
algoritmo para algoritmo. No entanto, na maioria dessas formas é necessário
mensurar de algum modo a diversidade da população e julgar quando esta estiver
baixa.
Existem várias formas de se mensurar a diversidade da população, uma das
mais comuns é obtida através de uma derivação da Fórmula (4) explicitada
anteriormente, que corresponde a uma soma da DH de todos os indivíduos em
relação ao restante da população. Essa medida de diversidade da população, Dpop,
pode ser expressa pela Fórmula (7) (Morrison e Jong, 2001).
𝐷!"! = (|𝑋!" − 𝑋!"|)!
!!!
!!!
!!!!!
!!!!!
!!!
𝑖 ≠ 𝑗 (7)
‘N’ é o número de indivíduos da população e ‘L’ o comprimento da cadeia de
bits que constituem os indivíduos. Assim, obtido o valor para Dpop, é possível
mensurar a diversidade da população, e caso esta esteja abaixo de uma referência
previamente estabelecida, é identificado o takeover e reinicializa-se a população,
mantendo os melhores indivíduos já encontrados.
O maior inconveniente da utilização da Fórmula (7) é o seu elevado custo
computacional. Por ser uma operação a ser feita em todos os ‘N’ indivíduos,
comparando-o com todos os ‘N-1’ indivíduos, e cada um tendo seus ‘L’ bits
comparados um a um, essa operação pode ser de difícil utilização para problemas
com um número elevado de indivíduos (Morrison e Jong, 2001).
21
Figura 2.2 –Exemplo da utilização da distância de Hamming nos indivíduos da população.
A Figura 2.2 evidencia a utilização da DH para calcular diversidade na
população. Os indivíduos de 1 a 5 tiveram seus bits comparados um a um com os
bits dos outros indivíduos, resultando na esquema inferior da figura. A soma de
todos os DH, resultando 56 neste exemplo, pode ser utilizada para mensurar a
diversidade da população. Para um mesmo grupo de indivíduos em uma população,
quanto maior for a soma de todos os DH, maior será a diversidade do grupo. Um
grupo com a soma de DH equivalente a 0 é um grupo em que todos os indivíduos
são idênticos.
Outra forma de mensurar a diversidade foi adotada por Rosca et al. (1995),
que sugeriu uma medida de entropia, análoga a uma medida utilizada na biologia e
física. Nela, a diversidade da população pode ser medida por meio das razões entre
o número de indivíduos pertencentes a cada grupo na qual a população foi dividida.
A Fórmula (8) fornece o valor de entropia de uma população em função do número
de indivíduos enquadrados nos grupos em que a população foi dividida.
22
𝐸 = − 𝑃! . log (𝑃!)!
!!!
(8)
‘E’ representa a entropia da população, ‘G’ representa o número de grupos
no qual a população foi dividida, e ‘Pk’ representa a razão entre o número de
indivíduos pertencentes a um determinado grupo, correspondido por ‘k’, e o número
total de indivíduos da população. Por meio desta medida, é possível verificar o
comportamento da diversidade da população ao longo da execução do algoritmo.
Apesar dos eficiência provocada pela reinicialização da população em
algoritmos genéticos, o presente estudo não utilizou esta técnica nos testes
executados. Esta decisão foi tomada de forma a melhor observar a exploração do
espaço amostral pelo ranking de diversidade em uma população inicial frente a um
AG tradicional. Reinicializações da população introduziriam variações estocásticas
nos dados, dificultando a análise dos efeitos provocados pelo ranking na evolução
do algoritmo.
2.5. DIVERSIDADE PROPORCIONADA PELO RANKING
O objetivo do presente estudo é baseado em uma estratégia apresentada por
Oliveira et al. (2012). Oliveira, ao observar o fenômeno de convergência prematura
notou que o escalonamento do ranking exclusivamente pelo valor de fitness dos
indivíduos contribuía para uma indevida e rápida convergência do algoritmo (Oliveira
et al. 2012), e, consequentemente, para uma perda precoce da diversidade da
população. Tendo conhecimento disso, Oliveira et al. (2012) projetou uma alternativa
para o ranking de escalonamento, de tal forma que este passasse a valorizar não
somente indivíduos com maior valor de fitness, mas também indivíduos que possam
proporcionar a manutenção da diversidade na população.
Para isso, foi proposta uma divisão da população por grupos de proximidade
estrutural e implementou um algoritmo que procura selecionar os indivíduos com
maiores valores de fitness que pertençam a grupos diferentes, de forma a evitar a
presença desnecessária de vários indivíduos de uma mesma bacia local no grupo de
indivíduos selecionados, o que pouco contribuiria para explorar o espaço de
amostral do problema.
23
A Figura 2.3 ilustra a diferença de escalonamento da forma tradicional, como
está nativamente implementada no toolbox, frente ao escalonamento por
diversidade, proposta por Marcus.
Figura 2.3 –Esquema do Ranking por Diversidade, proposto por Oliveira.
Fonte: Oliveira et al. (2012) Modificada pelo autor.
Pela Figura 2.3 é possível observar que os indivíduos da Região 1 possuem
os maiores valores de fitness e, portanto, para o ranking tradicional, são os com
maior probabilidade de serem selecionados, seguidos pelo indivíduo da Região 2,
que por sua vez é seguido pelos indivíduos das Regiões 3 e 4, respectivamente.
Este tipo de ranking tende a ser ineficiente devido ao fato de que ele avalia e
seleciona redundantemente vários indivíduos de uma mesma região, aprisionando a
população em uma bacia cujo ótimo local já foi representado, levando o algoritmo à
uma convergência prematura, antes que o espaço de soluções seja devidamente
explorado em busca do ótimo global do problema. No entanto, pelo ranking de
diversidade, nota-se que a valor de fitness dos indivíduos continua sendo priorizado,
porém, indivíduos de regiões diferentes possuem preferência frente a indivíduos de
uma mesma região que já possua um representante selecionado. Dessa forma, a
população tende a permanecer diversa e ao longo da execução do programa,
proporcionando uma melhor exploração do espaço amostral antes de convergir.
Para se obter a divisão por regiões, é preciso antes introduzir o conceito de
equivalência, em que um indivíduo Xi equivale a um indivíduo Xj se, e somente se,
|Xi – Xj| < Ɛ, em que Ɛ é algum valor especificado maior que zero (Oliveira et al.,
2012) e corresponde à DH mínima entre dois indivíduos adotada para que estes
sejam considerados diferentes. Considerando um Xi como centro de uma região, e
um raio de valor determinado Ɛ, todos os outros indivíduos que estiverem dentro
deste círculo são considerados como pertencentes à região de Xi. Então, utilizando
esse conceito, uma vez determinada a região a que pertence cada indivíduo, o
procedimento é atribuir a melhor posição no ranking, e consequentemente a maior
24 probabilidade de ser selecionado, ao indivíduo mais apto da população. A segunda
posição no ranking, por sua vez, é atribuída ao melhor indivíduo dentre os restantes
que não esteja na mesma região do primeiro indivíduo selecionado. O terceiro
indivíduo será o mais apto dentre aqueles não pertencentes às regiões dos dois
primeiros indivíduos já escolhidos.
O procedimento descrito acima é realizado recursivamente até que todas as
regiões contenham ao menos um representante no ranking, quando então o
procedimento recomeça, sendo possível alocar um segundo representante de cada
região, ou até o número de vagas para a seleção de indivíduos acabar. Dessa
forma, é possível que indivíduos com menores valores de fitness recebam uma
maior chance de serem selecionados e passarem seus genes para populações
futuras, o que, por consequência, atrasa a convergência da população, aumenta a
diversidade da mesma e melhora a exploração do espaço amostral.
Apesar de parecer uma atividade simples, dividir o espaço de soluções em
regiões é uma tarefa complicada, não só devido ao fato de que cada problema
deverá ser individualmente avaliado, mas também porque a divisão em regiões não
é uma relação transitiva. A Figura 2.4 abaixo ilustra esta característica.
Figura 2.4 –a) Exemplo de um centro de região. b) Exemplo da não Transitividade da Divisão por Região
Fonte: Oliveira et al. (2012)
25
A não transitividade da divisão de grupos pode ser exemplificada pelo fato de
que, seja um Xi e um Xj, em que |Xi – Xj| < Ɛ, e seja um Xk em que |Xk – Xj| < Ɛ. Pela
primeira equação, Xi e Xj estão na mesma região, e o mesmo ocorre para Xj e Xk. No
entanto, não necessariamente Xi e Xk estão na mesma região, conforme mostrado
na Figura 2.4-b, evidenciando, assim a não transitividade da divisão em grupos e de
como se deve tomar um cuidado ao se realizar essa divisão para que o algoritmo
funcione corretamente. Maiores detalhes sobre como essa técnica foi implementada
no presente estudo serão apresentados no próximo capítulo.
26
3. CAPÍTULO 3
Os objetivos deste capítulo são: detalhar o ambiente de desenvolvimento do
projeto e sua organização; descrever o problema da mochila, o qual foi utilizado para
a implementação dos testes utilizados para investigar os efeitos das modificações
feitas e, por fim, descrever os algoritmos e as alterações implementadas no
ambiente a fim de se aperfeiçoar o funcionamento do GA.
3.1. GA-FRAMEWORK
Conforme enunciado no Capítulo 1, o ambiente de desenvolvimento do
presente estudo foi o GA-Framework desenvolvido para a plataforma Matlab®. O
GA-Framework segrega funções que são comuns a todos os problemas de
otimização das funções que são específicas para cada um, o que permite a sua
utilização em diferentes problema. Como exemplos, as funções de escalonamento e
seleção dos pais, reprodução, avaliação da população, avaliação da ocorrência de
takeover na população, inicialização e atualização das configurações do algoritmo,
são funções que devem ser executadas independentemente do problema a ser
avaliado. Essas funções, por sua vez, levam à utilização de funções específicas para
o problema, como a própria inicialização e da população inicial, a forma de se
realizar a cruzamento e a mutação em cada indivíduo da população, a avaliação da
adequação deste à função objetivo e a impressão dos resultados para a visualização
do usuário. Essa configuração permite maior flexibilidade do framework,
minimizando o trabalho para o usuário que queira personalizar um problema
específico.
A Figura 3.1 ilustra a estrutura das funções no toolbox, considerando o
problema da mochila como o problema a ser otimizado pelo programa.
27
Figura 3.1 – Estrutura do GA-Framework utilizado.
O GA-Framework possui uma Grafical User Interface (GUI), a qual permite
que o usuário selecione os parâmetros e configurações a serem utilizadas pelo
programa na busca da solução ótima para o dado problema. No presente estudo,
serão utilizados apenas os parâmetros que tratam de funções mono-objetivo.
28
Figura 3.2 – GUI utilizada no GA-Framework Fonte: Open Genetic Algorithm Toolbox (Freitas, Alan de)
Os parâmetros evidenciados na Figura 3.2 correspondem aos parâmetros
disponibilizados pelo framework, no entanto, de forma a se executar o AG de forma
mais simples, muitos dos parâmetros foram desativados. A seção seguinte descreve
o significado e qual a opção adotada para cada um dos parâmetros acima.
29 3.2. CONFIGURAÇÕES ADOTADAS NO PROJETO
A fim de avaliar os efeitos das mudanças implementadas no desempenho do
algoritmo, é necessário adotar algumas configurações padrões para os parâmetros
em todos os testes e coletas de dados realizados. Esses parâmetros podem ser
divididos em dois tipos: parâmetros numéricos e metodológicos. Os primeiros se
referem a parâmetros que são ajustados em números cardinais ou em uma faixa de
valores previamente estabelecida. Os parâmetros metodológicos, por sua vez, se
referem aos parâmetros que refletem na escolha de um determinado método ou
função a ser executada ao longo do algoritmo. A seguir será descrito o significado de
cada um dos parâmetros e qual o valor ou método adotado para eles.
3.2.1. Parâmetros Numéricos
O primeiro parâmetro do GA-framework a ser definido é o tamanho da
população. Uma população pequena tende a perder variedade de forma mais rápida
que uma população maior. Por outro lado, uma população muito grande demanda
maior custo computacional. Como o objetivo do presente trabalho é verificar os
efeitos do ranking de diversidade em diferentes instâncias do problema da mochila,
diversos tamanhos de população foram utilizados. Assim, os dois algoritmos foram
comparados por meio da sua implementação em populações com os seguintes
tamanhos: (a) 40 indivíduos (b) 100 indivíduos (c) 300 indivíduos. A existência de
tanto populações numerosas quanto populações reduzidas permitirá uma análise
mais aferida da diferença entre os rankings em execuções com diferentes custos
computacionais.
Apesar da GUI do framework utilizado possibilitar ajuste em tempo real dos
operadores de cruzamento e mutação, estes foram fixados nos valores iniciais e
não tiveram seus valores alterados em momento algum ao longo da execução,
permanecendo constantes. Optou-se por mantê-los constantes a fim de melhor
evidenciar os efeitos provocados pelo ranking de diversidade criado. O operador de
cruzamento foi fixado 90%, o que significa que um par de pais selecionados tem
chance de 90% de trocar informação genética, gerando dois novos filhos. Já o
operador de mutação, foi fixado em 5%, o que significa que cada filho resultante da
30 reprodução tem uma chance de 5% de ter algum bit, estocasticamente definido,
alterado.
Foi definido o total de dois pais por cruzamento, valor mais comum em AG
tradicionais. Além disso, adotou-se competição entre pais e filhos, ou seja, a seleção
da nova geração envolve tanto os indivíduos pais quanto os filhos, sendo metade
destes eliminada.
O elitismo da população se refere à manutenção forçada dos indivíduos mais
adaptados da população. Dessa forma, após a reprodução, os 10% de indivíduos
mais adaptados são sistematicamente selecionados para a próxima geração.
O critério de parada do algoritmo também é definido por argumentos
numéricos. O usuário pode exigir que o algoritmo finalize sua execução após um
determinado número de gerações, ou após um determinado número de gerações
sem nenhuma melhoria, ou impondo um limite de tempo para a execução. No caso
do presente estudo, o critério de parada para as diferentes instâncias foi o tempo.
Dessa forma, a velocidade de execução dos algoritmos pode ser avaliada de
maneira mais eficiente e justa, já que ambos terão direito à mesma fatia de tempo
para execução. Foi estabelecido o tempo de 250 segundos, que após testes iniciais
se mostrou como suficiente para evidenciar as diferenças de evolução e
variabilidade da população.
Por fim, o parâmetro binário de reinicializar população após takeover foi
desativado. O motivo para essa desativação é que um dos objetivos do presente
estudo é evidenciar a melhoria na exploração do espaço amostral do AG com
ranking diversidade frente ao tradicional. A inserção forçada de novos indivíduos
estocasticamente gerados insere uma variação na população que dificultaria analisar
e mensurar os efeitos ocasionados por cada ranking isoladamente.
Além da não utilização de nenhum tipo de reinicialização da população, para
uma mesma instância ambos os algoritmos iniciarão sua execução com a exata
mesma população, o mesmo ponto de partida, de modo que fique mais evidente a
diferença na forma de explorar o espaço amostral por ambos os algoritmos.
3.2.2. Parâmetros Metodológicos
Os parâmetros metodológicos se referem às diferentes formas de execução
do algoritmo para determinadas tarefas. Para este projeto, três destes são
31 configuráveis: o método de escalonamento, o método de seleção e o método de
adaptação.
O método de escalonamento especifica a forma através da qual os indivíduos
serão organizados e, em seguida, entregues para a função que realizará a seleção
dos pais. O método “Rank Based” é o método padrão utilizado pelo GA-framework e
corresponde à organização dos indivíduos em um ranking baseado exclusivamente
em seu fitness. Essa é forma de ranking tradicional enunciada no primeiro capítulo, e
este foi o método alterado por este estudo, de forma que o novo ranking diversidade
passou a valorizar, também, indivíduos diversificados na população. A partir deste
ponto no texto, o termo “Ranking Tradicional” estará se referindo a essa forma nativa
do toolbox utilizado para ranquear a população exclusivamente em função dos
valores de fitness, enquanto o termo “Ranking Diversidade” irá se referir ao modelo
proposto e modificado por este projeto.
O método de seleção é o SRS, Stochastic Remainder Sampling, que é um
método em que é feito uma razão entre o valor de fitness do indivíduo, fi, e o fitness
médio da população, fa. O valor inteiro dessa divisão corresponde ao número de
vezes que esse indivíduo será copiado, e consequentemente selecionado, para
realizar a reprodução. O valor do resto da divisão corresponde à probabilidade do
indivíduo ser selecionado. Por exemplo, um indivíduo que apresente a razão fi / fa =
1.36 terá uma cópia garantida na seleção de pais para a reprodução, e uma
probabilidade de 36% de garantir outra cópia dentro do grupo de selecionados. O
método SRS será o método utilizado em todos os testes, tanto com o ranking
tradicional quanto pelo ranking diversidade implementado.
Por fim, o método de adaptação, que pode ser Individual ou Populacional se
refere à atualização dos operadores de mutação e cruzamento ao longo da
execução do algoritmo. Essa atualização pode ser individual, ou seja, os operadores
são diferentes de indivíduo para indivíduo, ou são o mesmo para toda a população.
Conforme justificado no capítulo anterior, não haverá nenhum tipo de alteração ou
controle dos operadores de mutação ou cruzamento, de tal forma que estes
permanecerão constantes ao longo de toda a execução. O motivo dessa escolha é
uma melhor aferição dos efeitos ocasionados pelo ranking diversidade criado por
este estudo.
Com os parâmetros padronizados, os testes podem ser feitos de forma que as
diferenças entre o grupo controle, referente aos testes feitos com o ranking
tradicional e o grupo com os testes feitos com o ranking diversidade serão mais
32 facilmente observadas. No entanto, nem todos os parâmetros correspondem ao GA-
framework, alguns deles são específicos do problema e devem ser definidos em sua
fase de inicialização. A seção seguinte especifica o problema a ser tratado e os
parâmetros para ele definidos.
3.3. O PROBLEMA DA MOCHILA
O problema escolhido para se realizar os testes desse projeto foi o Problema
da Mochila, ou knapsack problem, um problema bastante utilizado para testes de
eficiência em algoritmos genéticos. O problema da mochila é um problema de
otimização combinatória, em que são dados n itens, cada um com um determinado
peso e um determinado valor, que devem ser alocados dentro de uma mochila com
uma capacidade máxima de peso. A otimização consiste em maximizar o valor dos
itens dentro da mochila sem, contudo, ultrapassar seu limite de peso máximo.
Figura 3.3 – Problema da Mochila
Fonte: http://z7.invisionfree.com/minhtanone/ar/t200.htm
Por meio da Figura 3.3 é possível visualizar didaticamente o problema da
mochila. Assim como o toolbox requer a definição de alguns parâmetros que
especificam a forma de execução do programa, o problema da mochila também
necessita ser inicializado e ter seus parâmetros especificados. É necessário definir a
quantidade de itens que disputarão um lugar na mochila, estabelecer o peso e o
valor de cada item, e por fim definir o tamanho da mochila.
33
Do modo que este problema está implementado, o GA-framework requer
apenas que o usuário forneça a quantidade n de itens que serão analisados. Em
seguida, o programa gera estocasticamente valores entre 0 e 1, e os atribui como os
pesos de cada item. O mesmo processo é feito para a atribuição do valor de cada
item. O limite de peso da mochila é estabelecido como um terço da soma do peso de
todos os itens.
Pela ótica de algoritmos genéticos, a população de indivíduos corresponde a
vetores de tamanho ‘n’, em que cada elemento assume ou o valor 1, indicando que o
item será alocado na mochila, ou o valor 0, indicando que o item não será alocado
pela mochila. Dessa forma, por meio de uma função também específica ao
problema, cada indivíduo é avaliado para se encontrar sua adequação à função
objetivo, somando-se o valor de todos itens alocados na mochila, e recebendo
pesadas penalidades caso a soma dos pesos dos elementos alocados na mochila
ultrapassem o peso máximo desta. Penalidade esta proporcional ao tanto que o
peso limite da mochila foi ultrapassado. Assim, à medida que o algoritmo é
executado, os melhores indivíduos são selecionados, se reproduzem até o ponto
que o melhor deles é indicado como o ótimo do problema, com o maior valor de itens
que não ultrapassem o peso máximo da mochila.
O tamanho ‘n’ de cada indivíduo um parâmetro numérico importante na
execução do presente estudo. Populações com indivíduos menores tendem a perder
a diversidade com maior facilidade, enquanto as com indivíduos maiores são mais
propensas a manterem diversidade ao longo da execução. Além disso, como o
algoritmo utiliza a comparação de indivíduos bit a bit para a definição do ranking,
quanto maior o tamanho desses indivíduos, maior será o custo computacional.
Dessa forma, também para melhor aferir os resultados ocasionados pelo ranking
diversidade criado, foram utilizados diferentes tamanhos de indivíduos: (a) indivíduos
com 100 bits (b) indivíduos com 500 bits (c) indivíduos com 1000 bits.
Definidos os parâmetros utilizados de tamanho da população e tamanho do
indivíduos, foi possível definir as instâncias de testes com a combinação desses
parâmetros. A Tabela 3.1 evidencia a combinação do tamanho da população com o
tamanho dos indivíduos para a definição das instâncias nas quais serão realizados
os testes.
34
Tabela 3.1 – Instâncias utilizadas para os testes.
Instância Número de
Indivíduos na População
Tamanho dos Indivíduos
Instância I 40 100 Instância II 40 500 Instância III 40 1000 Instância VI 100 100 Instância V 100 500 Instância VI 100 1000 Instância VII 300 100 Instância VIII 300 500 Instância IX 300 1000
O problema também exige a definição de certos parâmetros metodológicos,
como o método utilizado para se realizar a cruzamento e o método utilizado para a
mutação. A forma padrão adotada é a One Point Crossover, para a cruzamento e o
Bitfop para a mutação. O One Point Crossover é um método padrão, em que um
número entre 1 e o tamanho do vetor que representa o tamanho do indivíduo, no
caso n, é estocasticamente gerado pelo programa. Este valor representa o ponto de
“corte” dos indivíduos, e os filhos são resultados da cruzamento do conjunto de bits à
esquerda do ponto de corte em um pai, com o conjunto de bits à direita do ponto de
corte do outro pai. Esse foi o método ilustrado na Figura 1.1, no primeiro capítulo.
Já para a mutação, o método escolhido foi o Bitfllop conforme ilustrado na
Figura 1.2. Este método consiste na inversão de um bit, em uma posição
determinada estocasticamente, inserindo, assim uma variabilidade a mais na
população.
Definidos os parâmetros do toolbox e do problema a ser otimizado, foi
possível realizar os testes necessários para avaliar a eficácia das alterações
propostas. No entanto, no caso do problema da mochila, não basta apenas
padronizar os parâmetros, é necessário padronizar também os itens da mochila, ou
seja, seus pesos e valores, e a capacidade máxima da mochila. Caso contrário, a
cada execução do programa, novos itens seriam estocasticamente gerados, e o
problema teria sempre um ótimo global diferente, e dificuldades diferentes para
encontrá-lo.
Portanto, para cada instância, todos os itens possuem o mesmo peso e valor
em tanto para a execução com o ranking diversidade quanto para o tradicional,
permitindo assim uma análise mais eficaz da evolução da busca pelo ótimo global
35 para os diferentes algoritmos. Além disso, conforme evidenciado anteriormente, os
testes para uma mesma instância do problema partem, também, da mesma
população inicial.
Finalmente, introduzidos os detalhes do toolbox e do problema a ser
executado, é possível explicitar as implementações feitas no código do programa
para se obter a funcionalidade do ranking diversidade. Esses detalhes são
apresentados na seção seguinte.
3.4. DETALHES DE IMPLEMENTAÇÃO
O objetivo principal deste projeto é aumentar a eficácia e eficiência de um GA
tradicional por meio de uma estratégia que garanta uma melhor exploração do
espaço amostral e uma melhor manutenção da diversidade da população ao longo
da execução do programa.
Conforme explicitado anteriormente, a estratégia adotada é a de um ranking
baseado em uma combinação do fitness e da diversidade dos indivíduos. Assim,
inicialmente, foi necessário encontrar no toolbox a parte do código que organizava o
ranking dos indivíduos para implementar as mudanças e foi na função especificada
pelo método de escalonamento “Rank Based” que as alterações foram feitas,
criando uma nova função, denominada “Diversity Rank Based”.
Para a construção do ranking, é necessário a implementação de dois
algoritmos diferentes, um para dividir a população em grupos, e outro para ranquear
os indivíduos da população em função tanto da região a qual eles pertencem quanto
aos seus valores de fitness. Abaixo, segue um algoritmo utilizado para a divisão da
população em grupos de semelhança estrutural. O algoritmo foi baseado no
sugerido por Oliveira et al. (2012) em seu trabalho.
Algoritmo 1: Algoritmo para dividir os indivíduos em regiões Início
Regioes ß zeros; Regioes(1) ß 1; CentroRegioes(1) ß x1; para i = 2 à length (Populacao) faça para j = 1 à length (CentroRegioes) faça se ||xi - CentroRegioes(j)|| < K então Regioes(i) ß j; sai do loop;
36
fim fim se Regioes(i) = 0 então Regioes(i) ß max(Regioes) + 1; CentroRegioes(i) ß xi; fim fim
fim
O algoritmo exposto acima classifica o primeiro indivíduo, X1, da população
como pertencente a uma recém-criada região 1, e armazena como centro dessa
região o próprio valor de X1. Em seguida, ele percorre os demais indivíduos da
população calculando, por meio da equação de Hamming, a distância entre os
indivíduos e os centros de população já calculados. Caso o indivíduo se encontre a
uma distância maior do que a distância estabelecida de Ɛ de todos os centros
existentes até o momento, esse indivíduo se torna o centro de um novo grupo. Caso
se encontre a uma distância menor que Ɛ de algum centro, ele é alocado como
pertencente ao grupo correspondente ao centro em questão.
A determinação do valor que Ɛ deve assumir é de grande importância para o
correto funcionamento do ranking pois cada problema exige um determinado valor
mínimo de distância para que indivíduos diferentes, porém suficientemente
parecidos, possam ser enquadrados em uma mesma região. Como exemplo, no
caso de um problema de otimização de funções matemáticas, em que as soluções
representam números reais, o valor de Ɛ deve levar em conta as distâncias entre
estes números, e não entre os vetores binários, como feito no algoritmo apresentado
acima.
No caso do problema da mochila, no entanto, a diversidade na população
será mais garantida observando uma variabilidade genética, ou seja, nas estruturas
binárias dos indivíduos. Dessa forma, o cuidado com a escolha de Ɛ no caso desse
projeto se resume ao valor que este deve assumir em determinado momento ao
longo da execução do algoritmo.
Com toda a população dividida em grupos, é possível aplicar um segundo
algoritmo, que realiza o ranking levando em conta tanto o valor de fitness dos
indivíduos como a região a que pertencem. Priorizando colocar indivíduos de regiões
diferentes antes de repetir um indivíduo de uma mesma região. O algoritmo de
37 ranking com diversidade apresentado abaixo foi também baseado no sugerido por
Oliveira et al. (2012) em seu estudo.
Algoritmo 2: Algoritmo de Ranking com diversidade Início
Aptidão ß Populacao.aptidao; bacias ß Populacao.bacias; [aptidaoord, indice] ß ordena(aptidao); para i = 1 à length(aptidão) faça baciaord(i) ß bacias(indiceord(i)); fim Rank(indice(1)) ß tamanho(aptidao); prox ßtamanho(aptidao) - 1; baciasaux = baciasordenadas; enquanto prox ≠ 0 faça baciasordenadas ß baciasaux; baciasaux(1) ß 0; para i = 2 à tamanho(aptidao) faça se isempty(find(baciasordenadas(1 : i -1) = baciasordenadas(i)))
então Rank(indices(i)) ß prox; baciasaux(i) ß0; prox ß prox - 1; fim fim fim
fim
Com a utilização desse algoritmo, os indivíduos são organizados em um
ranking que prioriza, como esperado, maior fitness e como segundo objetivo, a
variedade do indivíduo, ou seja, a não participação deste em nenhuma região já
existente dentro do ranking.
O intuito da existência da distância mínima de Ɛ entre os indivíduos é impedir
que ocorra a ocorrência de indivíduos que são extremamente similares entre si mas
que apenas um deles, com maior fitness, realmente tenha algum efeito significante
no algoritmo, auxiliando-o a chegar em seu valor máximo. Neste caso, outros
indivíduos da mesma bacia, com fitness pouco menores que o representante desta,
não mais contribuem para encontrar o resultado, mas sim para a convergência
prematura da população.
O efeito esperado é apresentado pela Figura 3.4, que evidencia uma
redistribuição dos indivíduos previamente selecionados de uma mesma região ao
longo de outras regiões, de forma a melhor explorar o espaço.
38
Figura 3.4 –Maior exploração do espaço amostral pelo Ranking com diversidade
Deve se ressaltar que um dos objetivos do Ɛ é valorizar o efeito da mutação, e
os indivíduos gerados por ela. Em uma população já convergida, a mutação de um
bit em um indivíduo o fará ser um dos primeiros indivíduos do ranking, por este
apresentar diferença estrutural do restante da população, que tenderá a estar
enquadrada em um único grupo.
Ao longo da execução do algoritmo e da inevitável convergência da
população, o efeito de um Ɛ estático é cada vez menor, principalmente devido a
concentração de indivíduos em bacias com um ótimo local já encontrado, como
mostrado na Figura 3.4. Assim, será implementado um Ɛ que tenha seu valor
variado ao longo da execução do algoritmo em função da quantidade de grupos que
esta estiver sendo dividida em um determinado momento.
Ao início da execução, Ɛ assumirá o valor de 1, indicando que apenas
indivíduos idênticos serão enquadrados no mesmo grupo. A cada geração, Ɛ será
acrescido de uma unidade, e na geração seguinte mais uma unidade, e por aí em
diante. O aumento de Ɛ tende a diminuir o número de grupos na população, de
forma que os grupos existentes correspondam a bacias de ótimo local, que já
possuam um indivíduo central representando-a.
Ao atingir um número suficientemente alto, Ɛ passa agrupar todos os
indivíduos da população em um único grupo, o que inutiliza os efeitos do ranking
criado por este estudo, devendo o Ɛ, dessa forma, ter sua contagem reiniciada,
retornando ao valor inicial de 1. Ao ser reiniciado, o número de grupos aumenta
novamente, e a exploração do espaço amostral continua, por meio da valorização de
indivíduos diferentes uns dos outros.
A forma encontrada para determinar a variação de Ɛ foi uma heurística
adotada ao se realizar testes iniciais com diferentes ritmos de crescimento de Ɛ. Um
39 ritmo de subida muito acelerado resulta na criação de um grupo unitário muito
rapidamente, de tal forma que a as bacias não são identificadas a tempo e os
indivíduos não são devidamente agrupado nos grupos apropriados. Por esse motivo,
adotou-se a subida de apenas uma unidade no valor de Ɛ a cada geração. Já o
reinício de sua contagem é imprescindível. Caso Ɛ não retornasse ao valor de 1, a
partir do momento que todos os indivíduos da população fossem enquadrados em
um mesmo grupo, o ranking diversidade perderia seu efeito, por não mais dispor de
grupos diferentes para alternar nas prioridades.
A Tabela 3.2 relaciona, como exemplo, a dinâmica envolvida no ritmo de
crescimento e reinicialização do valor de Ɛ e o número de grupos na população. Os
valores dessa tabela foram retirados de um teste real, correspondente à instância V,
correspondente à uma população de 100 indivíduos de tamanho 500 bits.
Tabela 3.2 – Dinâmica do valor de Ɛ ao longo da execução.
Valor de N. de
Grupos
Valor de N. de
Grupos
Valor de N. de
Grupos
Valor de N. de
Grupos
Valor de N. de
Grupos Ɛ Ɛ Ɛ Ɛ Ɛ 1 100 21 108 41 22 61 8 81 3 2 186 22 97 42 20 62 8 82 3 3 186 23 97 43 24 63 8 83 3 4 178 24 101 44 21 64 8 84 3 5 172 25 89 45 19 65 7 85 3 6 171 26 88 46 18 66 8 86 3 7 162 27 79 47 20 67 7 87 1 8 161 28 77 48 20 68 7 1 83 9 162 29 78 49 16 69 7 2 75 10 156 30 62 50 12 70 5 3 62 11 157 31 54 51 12 71 5 4 54 12 146 32 51 52 10 72 4 5 43 13 136 33 43 53 10 73 4 6 40 14 144 34 46 54 8 74 4 7 35 15 136 35 48 55 12 75 4 8 28 16 139 36 44 56 10 76 4 9 26 17 118 37 36 57 10 77 3 10 25 18 132 38 30 58 8 78 3 11 25 19 128 39 34 59 9 79 3 12 21 20 116 40 30 60 7 80 3 13 23
40
Observa-se na tabela que quando Ɛ inicia a execução com o valor igual a 1,
há 100 grupos, para a população de 100 indivíduos pais. É possível concluir que
cada indivíduo compõe seu próprio grupo, indicando, também, que não há indivíduos
idênticos na população. A partir da segunda geração, no entanto, Ɛ assume o valor
de 2, e, no entanto, passam a existir 186 grupos. Pode parecer estranho a princípio,
mas deve ser notado que a partir da segunda geração passam a existir 200
indivíduos, compostos de 100 pais e 100 filhos, justificando, assim, a ocorrência de
186 grupos. Com esse número é possível concluir que há ou indivíduos idênticos na
população, ou com menos de 2 bits de diferença de algum outro na população.
O ritmo de crescimento de Ɛ continua, uma unidade por geração,
acompanhada de uma constante diminuição da quantidade dos grupos na
população, conforme previsto. Quanto Ɛ atinge o valor de 87, passa a existir apenas
um grupo na população, e seu valor deve ser reiniciado. Na geração seguinte, Ɛ
assume o valor inicial de 1, e o número de grupos na população volta a ser
relativamente alto, menor que a da primeira geração, obviamente, devido à inevitável
convergência da população.
Este foi, portanto, o ritmo de crescimento e reinicialização de Ɛ adotado nos
testes utilizados para encontrar os resultados expostos no capítulo seguinte,
41
4. CAPÍTULO 4
Neste capítulo estão detalhados os resultados encontrados a partir da
implementação das alterações propostas pelo presente estudo. Conforme
introduzido nos capítulos anteriores, os testes foram aplicados em nove diferentes
instâncias do problema da mochila, cada uma com diferentes parâmetros numéricos
relativos ao tamanho binário dos indivíduos e ao tamanho da população, de forma a
melhor averiguar os efeitos resultantes das alterações. As características das
instâncias estão apresentadas na Tabela 3.1, no capítulo anterior.
Incialmente, serão apresentados os resultados obtidos a partir da análise
individual da Instância V, de forma a avaliar os efeitos de ambos os algoritmos em
um mesmo problema. Em seguida, serão apresentados os resultados contendo as
análises para o grupo de 9 instâncias, a fim de se avaliar as diferenças entre os dois
algoritmos ao serem aplicados em problemas de otimização do tipo knapsack.
4.1. INSTÂNCIA COM 100 INDIVÍDUOS COM 500 BITS CADA
Conforme apresentado no primeiro capítulo, os experimentos visam mensurar
quatro variáveis: a eficiência e eficácia do algoritmo, o custo computacional para a
execução do algoritmo e a análise da diversidade da população ao longo da
execução.
Para a instância V, foram realizadas 20 execuções possuindo o mesmo
resultado ótimo a ser atingido, sendo 10 execuções realizadas com cada um dos
algoritmos de maneira alternada. Cada execução armazenou os dados necessários
em um arquivo .txt, e estes foram posteriormente compilados de modo a se obter os
resultados finais.
A Figura 4.1 corresponde a uma média das 10 execuções com o algoritmo
tradicional, em vermelho, e com o algoritmo modificado, em azul. O eixo das
abcissas corresponde ao tempo de execução e o eixo das ordenadas apresenta o
maior valor encontrado na população.
42
Figura 4.1 – Melhor resultado para f(x) em função do tempo – Instância V
O gráfico acima sugere a melhoria tanto na evolução da busca pelo melhor
resultado quanto o melhor resultado final encontrado para a instância específica. O
algoritmo modificado se sobressai ao tradicional logo no início da execução,
mantendo a superioridade até o final, em 250 segundos.
Durante aproximadamente os primeiros 20 segundos, os dois algoritmos
apresentaram valores negativos como melhor valor encontrado, o que ocorreu
devido às penalidades. Neste caso, a solução de maior valor seria não levar nenhum
item na mochila, de tal forma que o melhor resultado na população seria zero – valor
não representado no gráfico devido à escala definida, a qual teve como objetivo
favorecer o melhor entendimento das curvas após alcançarem valores postivos.
Além disso, é possível observar que após se tornarem positivas, as duas curvas
apresentam um degrau próximo do valor 90, ponto a partir do qual os dois algoritmos
passam a apresentar resultados diferenciados. Assim, a curva do algoritmo
tradicional se transforma em uma reta perpendicular ao eixo y, devido à
estabilização e estagnação de sua população, o que ocorreu como consequência da
sua menor diversidade. Após 20 segundos de execução, o algoritmo tradicional não
mais evoluiu, permanecendo estagnado até o final do tempo de amostragem.
43
O algoritmo modificado, por outro lado, apresenta contínua evolução do
resultado ao longo do tempo, demonstrando melhor exploração do espaço amostral.
A maior eficácia do algoritmo modificado frente ao tradicional fica evidente na
superioridade dos valores finais encontrados por cada um ao longo das execuções.
Esses valores estão evidenciados na Tabela 4.1, que contém o valor final de cada
uma das 20 execuções dos algoritmos para a Instância V.
Tabela 4.1 – Resultados finais encontrados em 20 execuções da Instância V.
Valor Final Encontrado Ranking Diversidade Ranking Tradicional
Teste I 138,7995 91,235 Teste II 134,4055 87,2182 Teste III 139,9021 93,0007 Teste IV 140,0212 94,2752 Teste V 138,46 88,874 Teste VI 139,7657 95,202 Teste VII 136,5099 87,6029 Teste VIII 141,504 91,7353 Teste IX 135,6175 89,8189 Teste X 136,2901 85,992
A Tabela 4.1 evidencia, também, a repetibilidade dos resultados. Apesar de
os testes terem sido implementados de maneira alternada entre os dois tipos de
ranking, os resultados encontrados foram extremamente similares para um mesmo
algoritmo e diferentes entre algoritmos.
A fim de investigar se a diferença entre os resultados dos dois algoritmos foi
estatisticamente significante, foi aplicado o teste de Kruskal Wallis com alpha de
0,05, o qual demonstrou que o algoritmo modificado apresentou valores
estatisticamente maiores quando comparado com o algoritmo tradicional (P =
0,0002) Como forma de ilustração, a Figura 4.2. demonstra a distância entre os
intervalos de confiança das médias dos resultados obtidos por cada um dos
algoritmos, o que reforça que a diferença entre eles é estatiscamente significativa.
44
Figura 4.2 – Resultado do teste de Kruskal Wallis – Instância V.
Como previsto, o algoritmo modificado apresentou maior tempo de execução
por geração, o que ocorreu devido ao custo da divisão da população em grupos e
posterior escalonamento dos indivíduos alternando entre os grupos existentes.
A Figura 4.3 demonstra a quantidade média de iterações, indicada pelo
número de gerações decorridas, para cada algoritmo, em função do tempo.
45
Figura 4.3 –Número de gerações em função do tempo – Instância V.
O custo computacional do algoritmo modificado é 40% maior do que o do
algoritmo tradicional para um mesmo número de gerações No entanto, esse custo é
decorrido por geração, o que é necessário para empregar as técnicas que dividem a
população em grupos e posteriormente os escalonam. Dessa forma, o maior custo
computacional pode ser aceitável quando em situações nas quais a eficácia do
algoritmo é o principal objetivo.
A Figura 4.3 também demonstra a maior eficiência do algoritmo modificado
quando se compara o número de gerações necessárias para se evoluir a população.
Assim, é possível observar que com um menor número de gerações o algoritmo
modificado conseguiu encontrar melhores resultados, mesmo o algoritmo tradicional
possuindo maior número de gerações.
Como último aspecto para essa instância individual, será analisado a
diversidade média da população ao longo das execuções para cada um dos
algoritmos. A diversidade foi medida por meio de duas formas: pela DH média dos
elementos da população e pela técnica da entropia, ambas técnicas explicadas no
Capítulo 2.
Para medir a diversidade pela DH média da população foi, em ambos os
algoritmos, adicionado o trecho de código – trecho este que não foi utilizado nos
46 demais testes deste estudo, devido ao seu elevado custo computacional – para
realizar a medição.
Figura 4.4 –DH média da população em função do tempo – Instância V.
A Figura 4.4 evidencia a diferença na velocidade da queda da diversidade em
ambos os algoritmos nos segundos iniciais. Nota-se que a queda do algoritmo
tradicional é mais acentuada, e direcionada ao zero. Enquanto que a curva relativa
ao algoritmo modificado evidencia uma maior suavização da queda nos segundos
iniciais.
Alterando a escala do gráfico é possível observar com maiores detalhes na
Figura 4.5 como o algoritmo modificado retarda o caimento da diversidade da
população ao longo da execução. Apesar da notável diminuição da DH média da
população à medida que a execução ocorre, nota-se que esta é feita de forma lenta,
de modo a manter a diversidade da população por mais tempo. Já no algoritmo
tradicional, após os 50 segundos iniciais, a DH média não sai de zero durante toda a
execução, o que contribui para a estagnação da evolução de sua população.
47
Figura 4.5 –Detalhe da diminuição de variedade da população – Instância V.
Nenhum dos algoritmos utilizaram técnicas de reinicialização da população, e
apesar disso, o algoritmo modificado conseguiu manter maior diversidade ao longo
de sua execução durante o tempo de amostragem. Por outro lado, após a queda da
diversidade nos primeiros segundos, o algoritmo tradicional mantém a diversidade
em zero durante o restante do período de execução.
Antes de analisar o gráfico de diversidade medida pela entropia, é necessário
ressaltar que o valor de entropia avalia a igualdade na divisão da população entre os
grupos criados, ou seja, ele resultará em um valor alto se todos os grupos tiverem o
mesmo número de indivíduos, como por exemplo, 24 grupos com 4 indivíduos cada.
Por outro lado, valores de entropia mais baixos indicam distribuições desiguais,
como por exemplo, nestes mesmos grupos, 23 deles conterem apenas um indivíduo
e o grupo restante conter os outros 73 indivíduos. Essa distribuição desigual
resultaria em um valor de entropia extremamente baixo, e, indicaria, neste caso, que
a diversidade da população está baixa, pois a maioria dos indivíduos são muito
parecidos estruturalmente uns com os outros. Além disso, a entropia indica valor 0
quando existe apenas um grupo contendo todos os indivíduos da população.
Como o algoritmo tradicional não possui nenhum tipo de divisão da população
em grupos, foi implementado, apenas para esta execução, o trecho de código que
48 realiza essa função, assim como a regulação de Ɛ , sem, contudo, afetar o ranking
ou o funcionamento original do algoritmo. Dessa forma, é possível analisar a
diferença na quantidade de grupos e na distribuição de indivíduos entre eles para os
dois algoritmos ao longo da execução. A Figura 4.6 evidencia os valores de entropia
para uma execução para cada um dos algoritmos.
Figura 4.6 –Entropia da população em função do tempo – Instância V.
Observa-se no gráfico acima que a diversidade é melhor mantida no algoritmo
modificado devido à oscilação entrópica ao longo da execução, evidenciando divisão
satisfatória da população em grupos. Por outro lado, o algoritmo tradicional
apresenta divisão apenas nos primeiros segundos de execução do algoritmo. É
possível notar, também, o caráter cíclico da entropia para o algoritmo modificado,
que aumenta toda vez que a contagem de Ɛ retorna ao valor inicial de 1, e segue
diminuindo a medida que o número de grupos é reduzido, o que evidencia o
agrupamento de uma maior quantidade de indivíduos em uma mesma bacia de
ótimo local.
A Figura 4.7 mostra o número de grupos ao longo da uma execução do
algoritmo com o ranking por diversidade. Apesar de o parâmetro do tamanho da
população estar configurado em 100, o valor no qual de fato o algoritmo é aplicado é
49 sempre o dobro, no caso, 200, pois considera-se tanto a população dos 100 pais,
como a dos 100 filhos, e, desses 200, seleciona-se os 100 mais adequados para
constituírem a nova população. Dessa forma, nota-se que a tendência natural do
número de grupos é reduzir até um único grupo, agrupando toda a população e, em
seguida, com a reinicialização de Ɛ, aumentar o número de grupos novamente,
retornando a eficácia do ranking criado pelo presente estudo.
Figura 4.7 –Número de grupos em função do tempo– Instância V.
A linha em vermelho na figura acima demarca a média de grupos ao longo da
execução do algoritmo. O valor encontrado de aproximadamente 12 grupos, para
uma população de 200 indivíduos, representa média de 16 indivíduos por grupo,
valores razoáveis para se obter funcionalidade efetiva do ranking criado.
Por fim, a Figura 4.8 evidencia o comportamento de Ɛ ao longo da execução
do algoritmo. Seu comportamento se assemelha ao observado na Figura 4.7,
contudo, apresentando maior suavidade em sua variação, devido à dinâmica
aproximadamente linear adotada para a variação de Ɛ.
50
Figura 4.8 –Valor de Ɛ ao longo da execução – Instância V.
É possível observar na Figura 4.8, que no início da execução do algoritmo
modificado, Ɛ consegue atingir valores altos sem alocar a população em um único
grupo, devido a elevada diversidade inicial da população. À medida que esta
converge, Ɛ atinge valores cada vez menores, conforme evidenciado acima. A linha
vermelha representa a média do valor de Ɛ ao longo da execução, com Ɛ = 12.
Analisados os resultados para a Instância V, nota-se que o algoritmo
modificado para o ranking com diversidade apresentou melhorias significantes na
exploração do espaço amostral antes da convergência completa da população.
Assim, o algoritmo proposto pelo presente estudo apresentou maior eficácia na
busca pela solução do problema, às custas, no entanto, de maior demanda
computacional por geração, sem, contudo, prejudicar a eficiência do algoritmo.
51 4.2. RESULTADOS GERAIS PARA AS 9 INSTÂNCIAS
As nove instâncias apresentadas são diferenciadas pelos parâmetros de
tamanho dos indivíduos e tamanho da população. Para a obtenção de seus
resultados, foram executados testes, alternando os algoritmos para cada uma das
instâncias. A Tabela 4.2. demonstra os resultados dos valores finais obtidos após
250 segundos de execução.
Tabela 4.2 –Resultados finais para as 9 instâncias.
Valor Final Encontrado Ranking Diversidade Ranking Tradicional
Instância I 34,6102 29,099 Instância II 148,6313 102,5169 Instância III 242,3503 187,039 Instância VI 32,1947 25,2811 Instância V 138,7995 91,2352 Instância VI 265,8395 193,3661 Instância VII 28,7988 25,3099 Instância VIII 140,217 100,4481 Instância IX 231,0207 197,2217
Os resultados obtidos para os diversos testes aplicados à Instância V e
evidenciados na seção anterior mostram a repetibilidade dos algoritmos para uma
mesma instância, de forma a permitir a consideração dos resultados mostrados na
Tabela 4.2 como suficientemente próximos às medias que seriam obtidas em
repetidos testes em cada instância.
Para a Instância V, foi aplicado o teste de Kruskal Wallis, cujo resultado
rejeitou a hipótese nula, comprovando a significância da diferença dos resultados
entre os algoritmos para uma mesma instância. Para a análise do efeito dos
algoritmos em diferentes instâncias, foi aplicado o teste de Friedman com alpha de
0,05, teste também não-paramétrico, a fim de se investigar se a diferença entre os
resultados dos algoritmos para as 9 instâncias foi estatisticamente significante.
A Figura 4.9 evidencia o resultado gráfico da análise estatística. O teste de
Friedman funciona por meio de um ranqueamento dos resultados, em 1 e 2, no caso
do presente estudo. Como todos os resultados do algoritmo modificado foram
superiores aos resultados encontrados pelo algoritmo tradicional nas nove
52 instâncias, o teste aplicado evidenciou essa diferença com o resultado gráfico
obtido.
Figura 4.9 –Resultado gráfico do teste de Friedman para as 9 instâncias.
O valor P foi igual a 0,0027, o que permite rejeitar a hipótese nula de não
diferença entre os algoritmos, o que confirma que a diferença entre os resultados é
estatisticamente significante.
Apenas para caráter ilustrativo, a Figura 4.10 mostra a evolução do maior
valor encontrado na população para a execução dos dois algoritmos para a Instância
VIII, com 300 indivíduos com 500 bits cada.
Apesar das semelhanças com a Figura 4.1, para a Instância V, evidenciando
uma curva estagnada para o algoritmo tradicional e uma curva ascendente para o
algoritmo modificado, é possível perceber um atraso na ascensão desta última. Isso
ocorre devido à maior diferença entre os algoritmos de demanda computacional por
geração. Para a Instância VIII, os indivíduos são mais numerosos e de maior
tamanho, o que resulta em um maior esforço computacional para separar os grupos
e ranqueá-los do que o apresentado pela Instância V.
53
Figura 4.10 – Melhor resultado para f(x) em função do tempo – Instância VIII
A Figura 4.11 comprova a maior diferença de velocidade entre as instâncias V
e VIII. Enquanto para a Instância V o algoritmo modificado era 40% mais lento por
geração que o algoritmo tradicional, essa diferença subiu para 75%, um aumento
muito significativo. No entanto, apesar da maior demanda computacional por
geração, a eficiência e eficácia do algoritmo não foi afetada, tendo em vista que
após 50 segundos de execução, a curva do algoritmo modificado ultrapassou a do
tradicional, mantendo a superioridade até o final da execução.
Figura 4.11 – Melhor resultado para f(x) em função do tempo – Instância VIII
54
5. CAPÍTULO 5
5.1. CONCLUSÃO DO PROJETO
Os resultados enunciados no capítulo anterior evidenciaram com auxílio
gráfico e estatístico a superioridade do algoritmo proposto pelo presente estudo
frente ao algoritmo tradicional. A manutenção da diversidade por meio do ranking
criado se figurou como uma alternativa que garante uma contínua evolução da
população para indivíduos mais adaptados, sem contudo perder a diversidade da
população.
Como pontos positivos das mudanças implementadas, notou-se uma melhor
exploração do espaço amostral do problema. Apesar de ambos os algoritmos
iniciarem suas execuções com a mesma população, o algoritmo tradicional
rapidamente convergiu para o primeiro ótimo local encontrado, enquanto o algoritmo
modificado pelo ranking diversidade apresentou uma contínua evolução ao longo de
todo o tempo de amostragem dos testes.
Em todas as nove instâncias testadas, o algoritmo modificado teve, passados
os primeiros segundos de execução, seus melhores valores encontrados acima dos
encontrados pelo algoritmo tradicional, que por sua vez ficou estagnado em um
mesmo valor durante a maior parte do tempo de execução. E, além da diferença na
evolução da melhor solução, em nenhuma execução o resultado final do algoritmo
tradicional foi melhor que o obtido pelo algoritmo modificado, o que evidencia a
maior eficácia do último na obtenção da solução global.
Quanto à maior variedade da população, esta foi observada pela
superioridade da DH média da população ao longo da execução para o algoritmo
modificado frente ao tradicional. Enquanto o primeiro, apesar de apresentar uma
contínua diminuição da DH média ao longo do tempo, a manteve acima de zero
durante todo o tempo amostrado, o último a manteve extremamente próxima a ou
em zero durante quase todo o período de execução.
55
É necessário observar que a variação do fator Ɛ durante a execução do
algoritmo é de grande importância para um ótimo funcionamento do ranking. Caso o
fator permanecesse constante com o seu valor inicial de 1, o ranking se tornaria
menos eficaz por não agrupar elementos de uma mesma bacia em um mesmo grupo
que já possuísse um representante, o que é garantido pelo seu crescimento a cada
geração. Por outro lado, a reinicialização de seu valor é imprescindível para o
momento em que atinja um valor tão alto a ponto de agrupar toda a população em
um único grupo, o que inutilizaria as mudanças efetuadas pelo ranking. Dessa
forma, é necessário que para o correto funcionamento do ranking, o valor de Ɛ seja
tanto crescente ao longo da execução, como reinicializado quando o valor se torne
alto demais.
O maior custo computacional por geração se figura como um dos aspectos
negativos, contudo, esperados do algoritmo modificado. Apesar do maior custo, este
não afetou a eficiência do algoritmo na busca pelo ótimo global, que em um mesmo
intervalo de tempo obtém um resultado superior ao obtido pelo algoritmo tradicional.
O fato do algoritmo modificado ter necessitado de menos gerações para
alcançar um resultado melhor que o alcançado pelo tradicional evidencia mais uma
vez como o preço da maior demanda computacional por população é recompensada
por gerações mais eficientes.
Analisando os resultados positivos e negativos das modificações propostas
neste projeto, conclui-se que a utilização de um ranking que priorize tanto melhores
resultados quanto resultados mais diversos apresenta respostas muito mais
satisfatórias, tanto em termos de eficiência quanto eficácia, do que o algoritmo
tradicional. A maior manutenção da diversidade e a melhor exploração do espaço
amostral resultam em um AG mais robusto, confiável e eficaz.
5.2. TRABALHOS FUTUROS
Apesar de todas as melhorias observadas nos resultados das mudanças
propostas neste estudo, há ainda muito a ser estudado e otimizado, principalmente
acerca da escolha e controle do valor de Ɛ. O método utilizado para o crescimento
deste fator se figura como uma heurística, adotado a partir de observações dos
testes feitos nos algoritmos. No entanto, observou-se que para as diferentes
instâncias, com diferentes tamanhos de população e indivíduos, o ritmo de
56 crescimento do fator Ɛ por vezes era lento demais, de tal forma que o número de
grupos ficava muito elevado por muito tempo, e por vezes era rápido demais, o que
mantinha a população continuamente alocada em um único grupo, o que em ambos
os casos pode diminuir a eficiência do ranking.
Dessa forma, para o crescimento de Ɛ, adotou-se um ritmo mínimo de uma
unidade por geração, pois ter muitos grupos é menos prejudicial ao funcionamento
ao algoritmo do que ter apenas um com toda a população. Esse ritmo apresentou
um bom resultado para todas as instâncias. No entanto, uma relação que considere
também o tamanho da população ou o tamanho dos indivíduos, de forma menos
intuitiva, poderia otimizar ainda mais o resultado para as diferentes instâncias.
Outra possível melhoria seria na utilização de alguns dos métodos
enunciados no segundo capítulo deste estudo, como uma reinicialização da
população por meio de uma eficiente métrica de takeover. A reinicialização
combinada com o ranking de diversidade criado pode resultar em um AG ainda mais
poderoso, com tanto um mecanismo forte de inserção de diversidade na população
quanto um eficiente para realizar a manutenção dessa diversidade.
Outro dos métodos enunciados no segundo capítulo que poderia potencializar
o efeito do ranking é a adaptação dos coeficientes de mutação e cruzamento ao
longo da execução do algoritmo. A combinação dessas duas ferramentas, se feita da
forma correta, pode otimizar a manutenção da diversidade, promovendo maior
chance reproduções para os indivíduos mais diversificados, e uma maior chance de
mutação para os indivíduos idênticos ou pertencentes a uma bacia de ótimo local
cujo representante já tenha sido encontrado.
Essas propostas de estudos futuros podem ser feitas tanto isoladamente
quanto em conjunto, assim como é possível aplicar e desenvolver diversas outras
técnicas que podem ser incorporadas ao algoritmo de modo a aproveitar essa
abordagem de ranking por diversidade, que se mostrou neste estudo como uma
ferramenta indispensável para o universo dos algoritmos genéticos.
57
REFERÊNCIAS BIBLIOGRÁFICAS A. Törn and A. Zilinskas. "Global Optimization". Lecture Notes in Computer Science, Nº 350, Springer-Verlag, Berlin, 1989.
Bin WU,Jian WU,Xu-yan TU, “Research of Fast Genetic Algorithm,” Journal of University of Electronic Science and Technology of China, pp. 49–53, 1999.
Burke, E., Gustafson, S., Kendall, G. and Krasnogor, N. Advanced Population Diversity Measures in Genetic Programming. In Proc. 7th Int. Conf. Parallel Problem Solving from Nature (PPSN), Lecture Notes in Computer Science, vol. 2439, Guervos, J.J.M et al (eds), Springer-Verlag, Berlin Heidelberg, 2002, 341-350.
FrameWork obtido em http://www.mathworks.com/matlabcentral/fileexchange/37998-open-genetic-algorithm-toolbox
Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.
Jackson, David; “Mutation as a Diversity Enhancing Mechanism in Genetic Programming” GECCO 2011 Proceedings of the 13th annual conference on Genetic and evolutionary computation; Pages 1371-1378.
Linden, Ricardo. Algoritmos Genéticos - uma importante ferramenta da inteligência computacional - 2ª Edição. BR: Brasport, 2008. Capítulo 9.
Liu Xinping; Liu Ying; , "Adaptive Genetic Algorithm Based on Population Diversity," Information Technology and Applications, 2009. IFITA '09. International Forum on , vol.2, no., pp.510-512, 15-17 May 2009.
Mitsuo Gen ; Runwei Cheng “Genetic Algorithms and Engineering Design” John Wiley & Sons Inc. 1999.
Oliveira, Marcus V., Freitas, Alan R. R. ; Guimarães, Frederico G. ; “Uma Estratégia De Ranking Baseada Em Diversidade Em Algoritmos Genéticos,” Simpósio Brasileiro de Pesquisa Operacional ; Rio de Janeiro; 2012.
Página da internet. Acessado em Janeiro de 2013. http://z7.invisionfree.com/minhtanone/ar/t200.htm
Página da internet. Acessado em Outubro de 2012. “http://www-optima.amp.i.kyoto u.ac.jp/member/student/hedar/Hedar_files/TestGO_files/ Page2607.htm”
Ronald W. Morrison, Kenneth A. De Jong; “Measurement of Population Diversity; Mitretek Systems. Inc., 2001, Disponível em “www.revolutionaryengineering.com/EA-01.pdf ”.
58 Rosca, J. Entropy-driven adaptive representation. In Rosca, J., editor, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 23-32, Tahoe City, CA, USA, 1995.
Taejin Park; Kwang Ryel Ryu; , "A dual population genetic algorithm with evolving diversity,"Evolutionary Computation, 2007. CEC 2007. IEEE Congress on , vol., no., pp.3516-3522, 25-28 Sept. 2007
