|
| |
Implementação
Para a implementação do programa destinado a verificar a teoria estudada,
escolhemos a linguagem C, tendo sido utilizada a plataforma Borland C++Builder
como ambiente de desenvolvimento, disponível em versão para Windows (Win32). Os
programas, porém, foram escritos em ISO/ANSI C, sem utilização de nenhuma
biblioteca específica ou include files (.h) particulares do sistema operacional
Windows, e portanto sua compilação em outro sistema operacional e/ou com outro
compilador não deve apresentar maiores problemas.
Os seguintes módulos fazem parte da implementação, e estão disponíveis para
download na página dos
Arquivos:
| ccr.c |
unidade principal, contém main(), que recebe como entrada
um arquivo com as dimensões da chapa e lista de peças (círculos) a serem
distribuídos, e tem como saída um arquivo MetaPost (.mp) com a
distribuição obtida e (opcionalmente) um arquivo ASCII (.ccr) com log de
ações, decisões e a solução. |
ch.c
ch.h |
implementação da heurística construtiva (CH) e respectiva
abordagem construtiva (CA). Como a abordagem construtiva também é
utilizada pela heurística genética, a correspondente rotina está
disponível na interface.int CH (PChapa R, Pecas I, int N);
int CA (PChapa R, Pecas I, int N);
|
gabh.c
gabh.h |
implementação da heurística baseada em algoritmo genético
(GA-BH).int GABH(PChapa R, Pecas I, int N);
|
struts.c
struts.h |
estruturas de dados utilizadas (peças, chapa, etc.) e
correspondentes rotinas auxiliares (alocação/desalocação de memória,
ordenação [quicksort], etc.). Aqui, as duas estruturas mais importantes
para o programa:
typedef struct MyChapa {
double W,
L;
PPeca first,
last;
} Chapa;
typedef struct MyPeca {
int i;
double r,
c;
Ponto o;
PPeca next;
PAdj adj;
} Peca;
O tipo Chapa descreve o retângulo onde se irão encaixar as Peças
(círculos), e contém também ponteiros para uma lista ligada das peças que
de fato estão contidas na solução.
O tipo Peca contém as propriedades de cada círculo (raio, custo,
coordenadas do seu centro), bem como um ponteiro para a próxima peça
contida na solução (caso ela também faça parte da mesma), e uma lista
ligada das peças adjacentes a ela, para efeitos do funcionamento da
abordagem construtiva. |
metapost.c
metapost.h |
rotinas para geração de arquivos em formato
MetaPost, utilizado para exibição do layout
final obtido.int GeraMetapost(char* arquivo, PChapa R, Pecas I, int N);
|
log.c
log.h |
rotinas para geração do arquivo de log (.CCR) contendo
uma descrição detalhada dos passos, decisões e resultados obtidos pelo
programa. |
O programa CCR tem a seguinte sintaxe:
ccr <arquivo-de-pecas> <opcoes>
-hC: Heuristica Construtiva (default)
-hG: Heuristica Genetica
-d : Modo Debug (gera arquivo .CCR)
Vamos mostrar o funcionamento do programa e seu resultado através de um
exemplo pequeno, descrito abaixo. Pode-se clicar nas figuras para ampliá-las, e
todas estão disponíveis para download, juntamente com os arquivos auxiliares, em
Resultados.
 A
figura ao lado reproduz a distribuição obtida após se aplicar o algoritmo em uma
lista de 21 peças. De acordo com a
heurística, uma boa ordenação inicial é obtida ordenando-se as mesmas em ordem
decrescente da relação c/r (custo / raio), conforme explicado em
CH. O algoritmo conseguiu encaixar um total de 16
peças, obtendo 93.07% de aproveitamento do custo.
A listagem abaixo mostra o resultado final para esta distribuição (as peças
marcadas com um asterisco foram incúídas na chapa). Por questões de formatação
desta página, foram omitidas as colunas correspondentes às coordenadas x e y da
peça na chapa (o arquivo original se encontra em
exemplo1.ccr):
Chapa R: 216.00(W) x 279.00(W)
Pecas P: 21
---------------------------------------------------------------------
i raio custo c/r
---------------------------------------------------------------------
* 6: 10.0000000000 130.0000000000 13.0000000000
* 11: 10.0000000000 130.0000000000 13.0000000000
* 16: 10.0000000000 130.0000000000 13.0000000000
* 1: 10.0000000000 130.0000000000 13.0000000000
* 7: 20.0000000000 65.0000000000 3.2500000000
* 17: 20.0000000000 65.0000000000 3.2500000000
* 12: 20.0000000000 65.0000000000 3.2500000000
* 2: 20.0000000000 65.0000000000 3.2500000000
* 4: 40.0000000000 110.0000000000 2.7500000000
* 14: 40.0000000000 110.0000000000 2.7500000000
* 19: 40.0000000000 110.0000000000 2.7500000000
* 9: 40.0000000000 110.0000000000 2.7500000000
* 8: 30.0000000000 40.0000000000 1.3333333333
* 3: 30.0000000000 40.0000000000 1.3333333333
* 18: 30.0000000000 40.0000000000 1.3333333333
13: 30.0000000000 40.0000000000 1.3333333333
* 0: 5.0000000000 2.0000000000 0.4000000000
20: 50.0000000000 15.0000000000 0.3000000000
5: 50.0000000000 15.0000000000 0.3000000000
15: 50.0000000000 15.0000000000 0.3000000000
10: 50.0000000000 15.0000000000 0.3000000000
---------------------------------------------------------------------
Pecas Colocadas: 16
Custo Incluido : 1342.00 (93.07%)
Area Ocupada : 34950.19 (58.00%)
O trecho abaixo dá idéia do comportamento do programa e as decisões que são
tomadas quando de sua execução (novamente, o arquivo completo está na página de
arquivos, em exemplo1.ccr):
----------
Peca: P6, raio 10.00
Ponto: trivial ( 10.00, 10.00) - OK
----------
Peca: P11, raio 10.00
Ponto: trivial ( 10.00, 10.00) - Bateu em P6
1-Adjacencia : P6
Ponto: superior ( 10.00, -10.00) - Fora da Chapa
Ponto: inferior ( 10.00, 30.00) - OK
Ponto: esquerda ( -10.00, 10.00) - Fora da Chapa
Ponto: direita ( 30.00, 10.00) - OK
----------
Peca: P16, raio 10.00
Ponto: trivial ( 10.00, 10.00) - Bateu em P6
1-Adjacencia : P6
Ponto: superior ( 10.00, -10.00) - Fora da Chapa
Ponto: inferior ( 10.00, 30.00) - OK
Ponto: esquerda ( -10.00, 10.00) - Fora da Chapa
Ponto: direita ( 30.00, 10.00) - Bateu em P11
1-Adjacencia : P11
Ponto: superior ( 30.00, -10.00) - Fora da Chapa
Ponto: inferior ( 30.00, 30.00) - Mais Longe
Ponto: esquerda ( 10.00, 10.00) - Bateu em P6
Ponto: direita ( 50.00, 10.00) - Mais Longe
2-Adjacencias: P6 e P11
Ponto: lado 1 ( 20.00, -7.32) - Fora da Chapa
Ponto: lado 2 ( 20.00, 27.32) - Mais Longe
----------
Pode-se ver, acima, a análise dos três grupos de posição para cada peça que
se coloca na chapa: a posição mais próxima de (0,0) (trivial), as 4
posições em torno de cada peça já presente na chapa (1-Adjacência:
superior, inferior, esquerda, direita), e as duas posições relativas a cada par
de peças presente na chapa (2-Adjacências: lado1, lado2).
 Para
se ter uma idéia do efeito da ordenação proposta pela heurística construtiva,
veja-se o mesmo conjunto de peças, porém ordenado aleatoriamente e disposto na
chapa mediante a mesma abordagem construtiva (ou seja, a única diferença para o
exemplo anterior é a ordenação das peças). Neste exemplo, obtivemos o encaixe de
16 peças também, mas que resultaram em um aproveitamento de custo de 86.48%.
 Um
exemplo maior, com 240 peças de tamanhos próximos, pode ser visto ao lado. A
taxa de aproveitamento do custo foi de 96.24% (com 78.98% de aproveitamento do
espaço).
 A
imagem à esquerda reflete uma distribuição a partir do mesmo conjunto de peças
anterior, mas sem avaliar as posições tangencias duas a duas (o terceiro
critério da abordagem construtiva), para efeito de comparação - neste caso, o
aproveitamento do custo foi de 94.76%.
A implementação da heurística baseada em algoritmo genético não está
validada, e seus resultados ainda estão por serem verificados para apresentação.
Por este motivo, não se encontra aqui uma descrição mais detalhada neste
momento. Em breve, publicaremos os resultados obtidos.
|
