Teoria

Introdução

Definido como objetivo desta monografia, este trabalho se propôs a estudar e implementar duas heurísticas para o problema Problema do Corte Circular Restrito, tal como propostas por M. Hifi et al em [Hifi04]:

Construtiva (CH: Constructive Heuristics)
Baseada em algoritmo genético (GA-BH: Genetic Algorithm-based Heuristics)

Ambas utilizam uma abordagem construtiva (CA: Constructive Approach) como parte do processo, conforme explicado nas seções a seguir.

Algoritmos Genéticos

As idéias ligadas aos algoritmos genéticos são discutidas por Holland (1975) e Goldberg (1989). Aplicações desta metodologia heurística especificamente no campo dos problemas de empacotamente foram realizadas por diversos pesquisadores, como Davis (1985), Smith (1985), Prosser (1988), e outros.

Basicamente, um algoritmo genético é uma técnica de busca que gera soluções usando tanto informações de soluções anteriores quanto um certo grau de aleatoriedade. Uma população de soluções iniciais é gerada aleatoriamente e cada solução, codificada como uma série de números ou strings (cadeias de caracteres, usualmente binárias), é avaliada segundo algum critério de eficiência, ou seleção. Baseado na performance de cada string, um processo aleatório denominado crossover é usado para cruzar as strings umas com as outras, onde porções das strings são trocadas de modo a produzir novas strings, ou filhos. Há ainda um operador de mutação, responsável por introduzir ainda outro fator de aleatoriedade na geração de novas strings.

A população tende a conter strings cada vez melhores, porque os melhores exemplares são escolhidos como pais para a próxima geração. Um certo cuidado é tomado para evitar uma convergência demasiado rápida, o que pode comprometer o resultado. Em condições ideais, esta técnica ajuda a evitar o "problema do mínimo local", onde soluções sub-ótimas são encontradas em uma vizinhança, já que os elementos aleatórios presentes garantem uma investigação de amplo espectro dentro do espaço de soluções.

CA - Constructive Approach

Ambas as heurísticas descritas por [Hifi04] utilizam, em última análise, a abordagem construtiva delineada nesta seção. Esta, por sua vez, é determinística, uma vez que se tenha uma ordenação dos n círculos pertencentes ao conjunto I. O tema de cada heurística será, portanto, a obtenção da ordenação considerada ótima.

A abordagem construtiva, doravante denominada CA, é uma adaptação da técnica denominada BLP (Best Local Position), apresentada por Hifi et al em [Hifi02], e que trata de peças de formato irregular qualquer. Como neste problema estamos tratando apenas de círculos, ainda que de raios desiguais, desenvolveu-se a técnica denominada ABLP (Adapted Best Local Position), para peças circulares.

Dada uma ordenação de peças, cada uma é colocada na posição mais alta à esquerda possível dentre um conjunto finito de opções, obtido em relação às peças já colocadas, excluindo-se as posições repetidas e impossíveis (sobreposições). O conjunto de opções de posição relativa considerado está ilustrado abaixo:

Isto é, para cada peça P_i já colocada no retângulo, avaliam-se as posições P_j ilustradas acima. E, para cada par de peças já colocadas P_i1 e P_i2, acrescentam-se também as duas posições relativas acima. A cada iteração, a posição trivial que encosta o círculo em (0,0) também é considerada.

A verificação da eficiência desta abordagem é empírica, comparando-se com resultados previamente conhecidos da literatura (como em [Stoyan98]). Como o conjunto de posições examinadas é relativamente pequeno, esta técnica tem ótimo desempenho.

Conforme comentado acima, a CA é utilizada em ambas as heurísticas, seja como algoritmo de aproximação (no caso da CH), ou como operador de verificação de viabilidade (no caso da GA-BH).

Abaixo, um exemplo da construção CA, supondo-se uma ordenação inicial P1-P5:

A peça P1 é colocada no canto superior esquerdo, por default.
P2 pode ser colocada em 5 posições diferentes, segundo o algoritmo. Excluindo-se os locais impossíveis, restam duas possibilidades, e as regras de desempate determinam a colocação embaixo de P1, à esquerda.
P3 tem diversas possibilidades, sendo a preferencial a posição trivial que a encosta em (0,0).
De modo semelhante são escolhidas as posições de P4 e P5.

CH: Constructive Heuristics

Uma vez definida a CA, que servirá de algoritmo de aproximação, para definir a heurística construtiva propriamente dita é necessário apenas determinar um método para a ordenação inicial das peças.

Demonstra-se experimentalmente que uma boa ordenação das peças é a disposição em ordem não-crescente segundo a razão c_i / r_i. Em caso de igualdade, peças com c_i maior vêm primeiro. Esta heurística favorece, portanto, peças menores que promovam um retorno (ou "lucro") maior.

GA-BH: Genetic Algorithm-based Heuristics

Conforme discutido acima, esta heurística simula a evolução natural das espécies, gerando uma população inicial de indivíduos e aplicando operadores genéticos em cada reprodução.

No contexto deste problema, cada indivíduo, também denominado cromossomo, é uma possível solução, cuja aptidão, para efeitos da posterior seleção natural, é dada por uma função objetivo definida.

A idéia é que indivíduos altamente aptos se reproduzam através de um processo de crossover, e com incidência de ocasionais mutações. Resta definir como estes descendentes substituem a população em cada iteração.

O que determina a característica individual de uma implementação baseada em algoritmos genéticos são as escolhas que se faz para cada um dos processos acima. Via de regra, há bastante liberdade nestas escolhas, tanto em termos de metodologia, quanto no grau de aleatoriedade introduzido, conforme se verá.

Cromossomo

Cada cromossomo P é definido como sendo uma sequência ordenada de peças, resultado da concatenação de uma solução factível S para o problema e de um conjunto U = P \ S de peças que não puderam ser posicionadas em R.

Por exemplo, podemos ter P = (P1,P2,P2,P3,P3,P3,P4,P3,P4,P4), com S = (P1,P2,P2,P3,P3,P3,P4) e U = (P3,P4,P4) , o que significa que S é o conjunto de peças que podem ser posicionadas em R pela CA, enquanto que U é o conjunto de peças que não podem ser colocadas em R.

Nestas circunstâncias, a aptidão de P é definida simplesmente como ∑_iЄS c_i = ∑_iЄS (1/WL) π r_i², isto é, a somatória dos lucros advindos da colocação das peças em S no retângulo (assumimos neste exemplo que a função objetivo é aquela dada na formulação do problema).

Para determinar S e U a partir de uma ordenação inicial, utilizamos a CA como operador de verificação de viabilidade de P ou, mais ainda, como operador de mutabilidade de P (mutaciona P não-factível em factível, determinando S e U).

Seleção de Pais

Para fazer a seleção dos pais que, a cada iteração (ou geração), irá produzir novos indivíduos, pode-se utilizar diversas metodologias, entre as quais:

	Seleção por torneio: escolha determinada por concurso.
	Seleção proporcional: uma parcela fixa é escolhida para se reproduzir.
	Escalação por aptidão: cada um dos indivíduos mais aptos é escolhido sucessivamente para ser o primeiro pai; o segundo pai é escolhido aleatoriamente entre os mais aptos

Neste trabalho optou-se pela terceira metodologia pois, além de produzir uma implementação eficiente, cada pai apto tem a chance de se reproduzir ao menos uma vez com certa diversidade, promovendo a escolha do melhor enquanto minimiza os riscos de duplicação e/ou estagnação em um mínimo local, o que ocorreria se fosse criada uma homogeneidade muito prematura, devida ao cruzamento de indivíduos muito semelhantes (em termos de aptidão).

Crossover

Crossover é a combinação de pedaços de dois pais aptos em busca de filhos promissores. Aqui também há diversas técnicas exploradas, tendo sido escolhida uma variação daquela conhecida por Crossover OX Davis Two Points.

Um trecho (j,k) de genes, 1 ≤ j ≤ k ≤ n, escolhido aleatoriamente, é transmitido do Pai1 para o Filho1 e do Pai2 para o Filho2. O restante dos genes de cada filho é preenchido com os genes do outro pai, segundo certos critérios para evitar a repetição dos genes. Este método chama-se de dois pontos em referência aos intervalos (1, ,j-1) e (k+1, n) que conterão o "crossover", isto é os trechos de pais diferentes.

Mutação

Há dois tipos diferentes de mutação ocorrendo no algoritmo genético:

	Há uma mutação que é sempre aplicada a qualquer indivíduo candidato, isto é, a cada cromossomo, seja qual tiver sido sua origem: a aplicação de CA em todo novo filho, transformando um cromossomo não-factível em factível. ex.: P = (P1, P2, P3, P3, P3, P4, P4, P4, P4) é mutado em (P1, P2, P3, P3, P4) U (P3, P4, P4). Esta é uma aplicaçao trivial de mutação.
	Com certa frequência (usualmente baixa), é feito um swap (troca) de duas subsequências de genes, ou ainda uma inversão de ordem de uma subsequência de genes, em cromossomos factíveis, para aumentar o espaço de busca, evitando a convergência prematura. Como sempre, após esta mutação, aplica-se novamente a mutação de primeiro tipo, descrita acima.

Substituição da População

O último ponto sensível em relação à implementação de um algoritmo genético se refere a como uma nova geração de cromossomos gerada substitui indivíduos pré-existentes da população. Há duas escolhas básicas, sendo que a segunda foi adotada neste trabalho:

	Método Geracional: se a nova geração substitui toda a população anterior.
	Método Incremental: quando apenas os indivíduos menos aptos são substituídos.

Para a implementação do método incremental, é preciso compor inicialmente a população inicial, e definir como se fazem as iterações seguintes:

	População Inicial: o primeiro indivíduo é obtido com a CH. Os m-1 outros cromossomos são gerados aleatoriamente, e sofrem mutação. Dos 3m indivíduos resultantes, os m mais aptos constituem a população inicial.
	Cada iteração: escolhem-se os m mais aptos de uma população de 5m, obtida por sua vez a partir de m pais, 2m filhos por crossover e 2m cromossomos obtidos por mutação destes 2m filhos.