3.1.1 Princípios
O homem vem se inspirando na natureza para buscar soluções para alguns problemas em seu cotidiano. Exemplos são algumas invenções tais como o avião (pássaros), o submarino (peixes), as redes neurais (cérebro humano), dentre outros. Nesse contexto, surgiu por volta do século XIX o princípio da Seleção Natural, do naturalista britânico Charles Robert Darwin, onde na natureza os seres vivos mais adaptados ao ambiente têm mais chances de sobrevivência frente aos demais. A medicina e ciências afins vêm mapeando toda a informação genética humana, relacionando deste modo cada gene de cada cromossomo às características que eles representam nos indivíduos (hereditárias, físicas ou funcionais). O projeto Genoma é um bom exemplo de investimento na pesquisa genética. Criado em 1990, tem por objetivo o mapeamento do genoma humano, o que contribuirá para o entendimento acerca de diversas doenças e sua possível cura (GENOMA, 2005).
Partindo da ideia do homem se basear em princípios naturais para resolução de problemas, especificamente em métodos evolutivos e nos mecanismos da genética, aliado ao grande desenvolvimento de técnicas computacionais, foram criados algoritmos capazes de oferecer boas soluções em tempo viável para grandes e complexos problemas numéricos. Esses algoritmos são conhecidos na literatura por Algoritmos Genéticos (DAVIS, 1991; GOLDBERG, 1989). Baseiam-se em fundamentos no processo da seleção natural proposto por Darwin e nos mecanismos da genética. Eles trabalham com uma população de indivíduos (soluções), onde cada possui certo grau de “aptidão”, que pode aumentar no decorrer de sucessivas gerações sob ação de operações genéticas tais como
recombinação e mutação. Após a última geração apenas os indivíduos mais “adaptados” sobrevivem (LEMONGE, 1999).
3.1.2 Definições
Como discutido anteriormente, os Algoritmos Genéticos (AG) são inspirados na teoria evolucionista de Darwin. A solução de um problema resolvido por um AG é desenvolvida ao longo de um número pré-determinado de gerações. Ao final da execução de um AG, espera-se que se tenha chegado a uma solução ótima ou próxima o bastante. Inicialmente tem-se um conjunto de soluções (cromossomos) que constituem uma população. As soluções de uma população são utilizadas para gerar uma nova população, que se espera que seja melhor que a anterior. O processo de geração de uma solução melhor, mais adaptada, se dá através de algumas operações, implementadas de acordo com a estrutura de problema abordado. Essas operações são as que modificam a estrutura dos cromossomos (mutação e cruzamento ou recombinação), criando melhores cromossomos. A seguir são apresentadas as definições dos elementos presentes nos AGs.
3.1.2.1 Cromossomos e Genes
Os cromossomos consistem, em cadeias de caracteres, representando alguma informação relativa às variáveis do problema. Cada cromossomo representa deste modo uma solução do problema. Sua estrutura está relacionada diretamente com a estrutura do problema em si. A unidade básica de um cromossomo é um gene, que pode ser binário ou multivalorado. No primeiro caso, o cromossomo possui uma codificação binária {0, 1} e seu número de representações diferentes é da ordem de 2n, sendo n o seu tamanho. Um cromossomo multivalorado possui um número maior de representação por gene, possuindo uma faixa de representação da ordem de Mn, onde M se refere ao tamanho do alfabeto (número de representações por gene) e n o tamanho do cromossomo.
Cada gene de um cromossomo representa uma variável ou unidade de uma solução para o problema. Seu valor pode indicar uma decisão a se tomar dentro do contexto do problema. Então, para um cromossomo de tamanho n, uma combinação de genes representa um valor de custo ou lucro para uma solução. Por exemplo, uma representação
de cromossomo para o problema do caixeiro viajante, cada gene poderia indicar uma cidade a ser visitada, de acordo com a ordem definida. A Figura 3.1 ilustra uma representação de cromossomo para o PCV e uma rota definida de acordo com a ordem dos genes.
Figura 3.1 – Exemplo de Cromossomo para o PCV.
Fonte: Autor.
3.1.2.2 População e Gerações
Uma população consiste num conjunto de cromossomos. Cada cromossomo representa uma solução, logo temos um conjunto de soluções, cada uma com um valor. No início da execução de um AG, é configurada uma população inicial, que na maioria das vezes é formada seguindo um critério aleatório. Porém algumas vezes uma solução heurística é utilizada para gerar uma população inicial, tal como um critério de escolha guloso, com soluções mais interessantes (GOLDBERG, 1989).
Definida uma população inicial, os indivíduos desta irão ser avaliados durante um número pré-definido de etapas. Essas etapas são denominadas de Gerações. A cada geração espera-se uma população cada vez mais próxima da solução ótima para o problema.
O tamanho de uma população (número de indivíduos) afeta o desempenho global e a eficiência do AG. Se criada uma população pequena, haverá pouca cobertura no espaço de busca das soluções. Porém se criada uma população maior, previne a convergência prematura para ótimos locais, entretanto, demanda um tempo maior de processamento.
3.1.2.3 Seleção
São responsáveis pela preservação dos melhores indivíduos nas gerações seguintes, baseando-se no princípio da “sobrevivência dos mais fortes”. Em contrapartida os indivíduos com menor aptidão são descartados.
Computacionalmente, os indivíduos são diretamente selecionados da população aos pares para a reprodução, sendo seus herdeiros implantados na próxima geração. Inúmeros esquemas de seleção já foram propostos e implementados na prática dos AGs, alguns não sendo biologicamente plausíveis (BLICKLE e THIELE, 1995). Na seqüência, alguns dos mais empregados na literatura são discutidos:
Método da Roleta: uma probabilidade de seleção é calculada de acordo com a aptidão de cada indivíduo. Uma forma de quantificar a probabilidade pi do i-ésimo indivíduo xi da população vir a ser selecionado para reprodução é o cálculo proporcional ao seu valor da função de aptidão: fi = f (xi). Uma das formas para se efetuar este cálculo seria (HOLLAND, 1975):
onde fi é assumida positiva e n o tamanho da população. Então cada indivíduo da população é representado proporcionalmente ao seu índice de aptidão. Assim, os indivíduos com alta aptidão recebem uma porção maior da roleta, enquanto que os de menor aptidão ocuparão uma porção relativamente menor da roleta. Deste modo, realiza-se o lançamento n vezes da roleta, dependendo do tamanho da população, e escolhem-se para a população temporária aqueles indivíduos por ela sorteados. Por ser fortemente dependente da função de aptidão, este método possui uma desvantagem de produzir um grande número de cópias de um bom cromossomo, o que faz diminuir a diversidade da população. Esta falha pode ocasionar uma convergência prematura do algoritmo para um ótimo local. Por outro lado, quando a evolução está avançada, onde as aptidões não diferem muito entre si, observa-se
uma estagnação do algoritmo, isto é, uma baixa pressão de seleção entre aptidões parecidas.
Método do Torneio: são escolhidos aleatoriamente x indivíduos da população, dos quais é selecionado aquele com o maior valor da função de aptidão. Esse processo é repetido tantas vezes quanto for o número de indivíduos da população intermediária a ser gerada. Sua escolha aleatória não provê uma convergência prematura da solução, inibindo também a estagnação do método.
Método do Ranking: os indivíduos da população são ordenados de acordo com seus valores da função de adaptação. Esta ordenação é chamada de ranking. A cada indivíduo é associado um peso, proporcional à sua posição no ranking. Assim, o indivíduo mais adaptado terá mais chance de ser escolhido para a próxima população, pois a ele será atribuído o maior peso. Analogamente, o indivíduo menos adaptado terá a menor chance de escolha.
Amostragem Universal Estocástica (Stochastic Universal Sampling): semelhante ao método da roleta, mas difere na quantidade de indivíduos selecionados. Neste método, um conjunto contendo k indivíduos (k>2) é escolhido dentre todos os indivíduos de uma população. Indivíduos com maior aptidão possuem mais chances de serem escolhidos, sendo possível na escolha haver várias repetições de si mesmos.
Elitismo: este método seleciona um número k (k≥1) melhores indivíduos de uma
população. Geralmente aplicado em conjunto com outros métodos de seleção, o elitismo preserva os cromossomos com maior aptidão, protegendo-os dos operadores genéticos mutação e recombinação. Sua principal vantagem é o fato de garantir a convergência, ou seja, caso o ótimo global seja descoberto durante o processo de busca, o algoritmo genético deve convergir para tal solução. Sua desvantagem é a possibilidade de forçar a busca, pela presença de mais uma cópia do melhor indivíduo, na direção de algum ponto ótimo local que tenha sido descoberto antes do global, embora normalmente um algoritmo genético escape de tais armadilhas. Uma alternativa é guardar separadamente a melhor solução encontrada durante a evolução, para no final da execução designá-la como o indivíduo ótimo encontrado, mesmo que ele não esteja presente na última geração da execução.
Randômico: esta técnica seleciona aleatoriamente um dos pais da população para reprodução. Por não avaliar a função de aptidão dos cromossomos, garante uma grande diversificação. Porém, há a desvantagem de se extrair cromossomos com baixa aptidão para a reprodução.
3.1.2.4 Operadores Genéticos
Os métodos de seleção discutidos anteriormente têm a finalidade de escolher os indivíduos que irão passar por uma operação genética que irá gerar novos indivíduos na população seguinte, mantendo as melhores características da população anterior. Os operadores genéticos são responsáveis pela diversificação da população possibilitando a inserção de indivíduos melhores que sua geração anterior. A cada geração, é esperado que os novos indivíduos tenham funções de aptidão bem próximas da solução ótima para o problema.
A seguir, são discutidos os operadores genéticos: Cruzamento (Crossover) e Mutação:
3.1.2.4.1 Cruzamento
Este operador tem por finalidade cruzar dois ou mais indivíduos pais e criar novos indivíduos (filhos) com a herança genética de seus pais. Também é conhecido como Recombinação ou Crossover (SIVANANDAM e DEEPA, 2008) e funciona definindo pontos de cortes para troca de informações genéticas (genes) entre os cromossomos pais. Existem várias definições de onde e como devem ser inseridos os pontos de corte. A seguir são discutidos os mais empregados:
Um-ponto: um ponto de cruzamento é escolhido e, a partir dele, as informações genéticas dos pais são trocadas, conforme demonstrado na Figura 3.2. Nesta figura, a linha tracejada indica a altura do ponto de corte. Note que duas regiões de genes de mesmo tamanho de cada cromossomo pai são trocadas entre si e são gerados cromossomos com uma nova configuração de genes:
Figura 3.2 – Crossover de um ponto
Fonte: (SIVANANDAM e DEEPA, 2008).
Dois-pontos: agora dois pontos de corte são definidos e conseqüentemente haverá três regiões de genes em cada cromossomo pai. A adição de pontos de cortes pode reduzir o desempenho do AG. Mas, em contrapartida, o espaço de busca é explorado profundamente (SIVANANDAM e DEEPA, 2008). A Figura 3.3 demonstra o uso do crossover com dois pontos de corte. Nesta figura, foram escolhidas as regiões centrais de cada cromossomo pai a serem trocadas, mas sem problema algum poder-se-ia trocar as regiões das duas extremidades, caso fosse esse o critério adotado:
Figura 3.3 – Crossover de dois pontos
Multi-pontos: são definidos n pontos de cortes dividindo os cromossomos pais em
n+1 regiões. Fica a critério do programador do AG definir se haverá trocas a partir
da primeira ou segunda região, ou se será feito de modo aleatório.
Uniforme: nenhum ponto de corte é definido. É criada uma máscara do tamanho dos cromossomos pais que contém uma codificação binária que indica quais genes copiar de cada pai para formar um filho. Então para cada bit 1 na máscara, será copiado o gene do pai 1 na posição correspondente, caso contrário será copiado o gene do pai 2. A Figura 3.4 ilustra o uso da máscara binária.
Outras maneiras de inserção de pontos de corte podem ser encontradas em Sivanandam e Deepa (2008).
Figura 3.4 – Crossover Unifome usando Máscara
Fonte: (Sivanandam e Deepa, 2008).
3.1.2.4.2 Mutação
Após a operação de cruzamento, discutida no subitem anterior, ocorre a operação de mutação sobre alguns indivíduos selecionados aleatoriamente da população. Esta operação é importante para a diversificação genética da população, alterando arbitrariamente um ou mais genes de um cromossomo escolhido. Dessa forma, mantém-se a probabilidade de se chegar a qualquer ponto do espaço de busca, evitando estagnar em possíveis ótimos locais. Este operador é aplicado aos indivíduos com uma probabilidade dada pela taxa de mutação Pm. Geralmente, utiliza-se um valor baixo para Pm (assim como acontece na genética natural), pois se é utilizado uma taxa maior, a busca pela solução se torna essencialmente aleatória. Essa taxa varia de 0% a 100% e define a probabilidade de mutação de um cromossomo.
Porém, há outras maneiras de se definir a taxa de mutação de um cromossomo e o modo como é feito, dentre os quais alguns são discutidos a seguir:
Definindo-se um cromossomo de mutação: um cromossomo de mutação (mutation
chromosome) é gerado aleatoriamente. Trata-se de um cromossomo com
codificação binária, contendo zeros (0) e uns (1). Em cada ocorrência de um bit 1, a posição correspondente no cromossomo pai é trocada pelo bit inverso. A Figura 3.5 demonstra esse esquema:
Figura 3.5 – Esquema do Cromossomo de Mutação
Fonte: (SIVANANDAM e DEEPA, 2008).
Troca de posição: dois genes são escolhidos aleatoriamente num cromossomo e são trocados de posição. Ou seja, como visto na Figura 3.6 os genes da segunda e sexta posição, sentido esquerda para a direita, são trocados de lugar:
Figura 3.6 – Esquema da Troca de Posição
Fonte: (SIVANANDAM e DEEPA, 2008).
Inversão: uma posição aleatória no cromossomo é determinada e os genes próximos são invertidos. Na Figura 3.7 são escolhidos para inversão os dois últimos genes:
Figura 3.7 – Inversão de Genes
Fonte: (SIVANANDAM e DEEPA, 2008).
Portanto, a definição da operação Mutação e sua taxa de probabilidade implicam na alteração de alguns indivíduos de uma nova população, podendo ou não sair de ótimos locais para uma solução melhor. Se definida de forma aleatória, poderá melhor varrer todo o espaço de busca, porém poderá destruir indivíduos que representam boas soluções. Por isso é preferível que seja realizada aproveitando-se melhor a estrutura do problema, para
que seja possível ganhar a cada geração soluções melhores cada vez mais próximas de uma solução ótima.
3.1.3 Estrutura
Por se tratar de um algoritmo, um AG possui uma execução sequencial e finita (CORMEM ET AL, 2002). Dessa forma, inicialmente um AG armazena dados de entrada, processa estes dados durante certo tempo e gera uma saída com resultados. Na literatura são encontradas diversas estruturas de AGs, mas todas seguem uma base genérica como apresentada na Figura 3.8.
Inicialmente, um AG cria aleatoriamente ou através de algum método de construção guloso, uma população p com base nos dados de entrada (parâmetros do problema). O passo seguinte é o cálculo da função de aptidão (Fa) de cada indivíduo da população inicialmente criada. O valor de Fa é comparado ao valor objetivo (SO), caso este seja conhecido, e se forem iguais, o algoritmo encerra, atingindo seu objetivo. Caso contrário, o algoritmo prossegue para um processo de evolução que consiste em várias etapas, encerrando quando se chega ao objetivo ou um número máximo de gerações (LGmax) é atingido. Durante cada etapa do processo evolutivo, operações genéticas (seleção, cruzamento e mutação) são realizadas nos cromossomos da população, e ao final é esperada uma nova população com maior valor Fa que a anterior, definindo assim a evolução genética.
Figura 3.8 – Estrutura básica do AG desenvolvido no trabalho.
Fonte: Autor.
3.2 Algoritmos Meméticos
Os Algoritmos Meméticos (AM) pertencem à classe dos algoritmos evolutivos que além de possuírem os métodos de seleção e operadores genéticos tais como crossover e mutação encontrados no AGs, trabalham com o conceito de evolução cultural onde os próprios indivíduos, denominados de agentes, trocam informações culturais entre si adquiridas ao longo de sua existência (MOSCATO e NORMAN, 1992). Os AMs são amplamente estudados e possuem grande aplicabilidade a vários problemas de otimização encontrados na literatura, segundo Moscato e Cotta (2003).
A primeira vez que o termo “Algoritmo Memético” foi utilizado na literatura consta do ano de 1989 por Moscato, num trabalho com o título “On Evolution, Search,
Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms”
aplicado ao PCV para teste de resultados. Por sua vez o termo “memético” deriva do termo “meme” (unidade de informação) e foi idealizado por Richard Dawkins por volta da década de 70. Em AMs os memes são transferidos entre os agentes de uma população sem
que transcorra uma geração. Entende-se dessa forma que os agentes estão recebendo/transmitindo informações culturais entre si que são adaptadas da melhor maneira possível para cada indivíduo.
A principal diferença entre genes e memes está no processo de transmissão aos seus descendentes. Os genes, no processo de evolução, são transmitidos de forma que os descendentes gerados herdem características e habilidades presentes em seus progenitores. Já quando o meme é transmitido, ele será adaptado pela entidade que o recebe, com base no seu conhecimento e para melhor atender às suas necessidades. Com isso, a informação memética é transmitida de modo mais rápido e flexível que a genética.
O mecanismo que permite a transmissão da informação memética é a introdução de um (ou mais) operador (es) de busca local. A idéia principal de um AM é explorar a vizinhança das soluções obtidas por um AG e caminhar em busca do ótimo local (para cada solução) antes de retornar para o AG e continuar o processo.
De acordo com Merz e Freisleben (1999), num AM os operadores de recombinação (crossover) e mutação agem como estratégias de diversificação. Os indivíduos da população podem estar localizados numa região do espaço de busca contendo um ótimo local, conhecida por “base de atração do ótimo local”. Utilizando a informação contida na população, novos pontos de partida podem ser descobertos após a busca local. Os operadores de recombinação e mutação podem gerar indivíduos da população localizados em bases de atração de ótimos locais ainda não explorados, de modo que um novo pico deva ser alcançado, no caso da maximização (Figura 3.9), ou um vale deva ser explorado, no caso da minimização.
Figura 3.9 – Operadores de recombinação e mutação agindo como estratégias de
diversificação junto a AMs. Fonte: (CONCILIO, 2000).
A busca local começa com um indivíduo e tenta continuamente encontrar melhores elementos dentre os vizinhos, sendo S todo o espaço de busca. Em outras palavras, a finalidade será remeter esse indivíduo para um local onde a função de fitness tenha um valor melhor que o atual. Essa busca deverá ser realizada até que uma condição de parada seja satisfeita, sendo que essa condição deve ser atendida sempre que o processo de busca não tenha mais a capacidade de melhorar a solução atual. Em Concilio (2000), é apresentado um pseudocódigo genérico representativo de uma busca local:
Em Moscato (1999), encontra-se a seguinte definição formal para a busca local: seja um domínio computacional de entrada , tendo um conjunto de respostas correspondentes. Faz-se necessário a garantia de um subconjunto que esteja contido em que identifica as soluções válidas de . Um algoritmo soluciona se para a sua entrada apresentar como saída qualquer , caso contrário ele apresenta que não existe solução . A otimização combinatória trata-se de um tipo especial de problema de busca em que cada tem um conjunto de cardinalidade finita e cada solução possui um valor de fitness . A busca nesse tipo de problema será responsável por encontrar uma solução válida que maximize o fitness . Na Figura 3.10, é apresentado um fluxograma definindo de forma geral uma estrutura para AMs:
Procedimento busca local início
repita
final verdade
para i 1 até número de indivíduos faça
início
elemento indivíduo(i)
aplicar busca local (elemento)
se fitness é melhor então final falso
fim até final fim
Figura 3.10 – Estrutura Geral de um AM.
Fonte: (NETO, 2009).
3.3 Vocabulary Building
A Vocabulary Building (VB) trata-se de uma técnica de otimização e foi idealizada por Glover (1992), dentro do contexto de Path Relinking. Em Glover e Laguna (1993), essa técnica foi implementada dentro da metaheurística Busca Tabu. Na década de 90, Rochat e Taillard (1995) e Kelly e Xu (1995) possuem trabalhos com aplicações com VB em PRV. A partir de 1997 surgem várias outras publicações acerca da VB: Glover e Laguna (1998); Scholl, Klein e Domschke (1998); Glover (1999); Glover, Laguna e Marti (2000); Glover (2003).
Trabalhos mais recentes acerca da VB encontram-se: em Guedes e Aloise (2006), que aplicaram VB num Algoritmo Memético – AM para o Problema do Caixeiro Viajante Assimétrico; em Soares (2008), que utilizou VB num algoritmo Busca Tabu para o