Repositório Digital

A- A A+

Otimização volumétrica de gemas de cor utilizadas para lapidação

.

Otimização volumétrica de gemas de cor utilizadas para lapidação

Mostrar registro completo

Estatísticas

Título Otimização volumétrica de gemas de cor utilizadas para lapidação
Outro título Volumetric optimization for colored gemstone cutting
Autor Silva, Victor Billy da
Orientador Ritt, Marcus Rolf Peter
Co-orientador Carvalho, Joao Batista da Paz
Data 2013
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Algoritmos geneticos
Otimização volumétrica
[en] Continuous global optimization problems
[en] Continuous GRASP
[en] Genetic Algorithms
[en] Heuristics
[en] Metaheuristics
[en] The gemstone cutting problem
Resumo O Problema do Lapidário tem como objetivo encontrar o modelo de lapidação que resulte no maior aproveitamento volumétrico para uma dada gema bruta. Nesta dissertação apresentamos um Algoritmo Genético com variáveis de valores reais, e um GRASP Contínuo como heurísticas para resolução deste problema. Ambos os algoritmos maximizam o fator de escala do modelo de lapidação, sobre todas as posições de centro e ângulos de giro que o modelo pode assumir, buscando encontrar o modelo de maior volume inscrito no interior da gema, representada virtualmente por uma malha triangular. Propomos também um algoritmo de avaliação de uma instância do problema, o qual determina eficientemente o maior fator de escala, para um dado centro e orientação, que o modelo de lapidação pode assumir permanecendo completamente no interior da gema. Os algoritmos propostos foram avaliados em um conjunto de 50 gemas reais para o problema, utilizando como modelos base os cortes redondo e oval. Por fim, comparamos os resultados computacionais obtidos em relação a aproveitamento volumétrico e tempo de execução com os principais trabalhos relatados na literatura, demonstrando que as heurísticas propostas são competitivas com as demais abordagens.
Abstract The goal of the gemstone cutting problem is to find the largest cutting design which fits inside a given rough gemstone. In this work, we propose a real-valued Genetic Algorithm and a Continuous GRASP heuristic to solve it. The algorithms determine the largest scaling factor, over all possibilities of centers and orientations which the cutting could assume, finding the cutting with the largest volume as possible inside a gemstone, represented by a triangular mesh. We also propose an algorithm to evaluate a problem instance. This method efficiently determines the greatest scaling factor, for a given center and orientation, such that the cutting fits inside the rough gemstone. The proposed algorithms are validated for an instance set of 50 real-world gemstones, using the round and oval cuttings. Finally, we compare our computational results, for volume yield and running time, with the state-of-art. Ours methods are proved be competitive with the previous approachs.
Tipo Dissertação
URI http://hdl.handle.net/10183/90428
Arquivos Descrição Formato
000915362.pdf (2.754Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.