Detalhes bibliográficos
Ano de defesa: |
2019 |
Autor(a) principal: |
Prates, Marcelo de Oliveira Rosa |
Orientador(a): |
Lamb, Luis da Cunha |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Tese
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
eng |
Instituição de defesa: |
Não Informado pela instituição
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Palavras-chave em Inglês: |
|
Link de acesso: |
http://hdl.handle.net/10183/199216
|
Resumo: |
Graph Neural Networks (GNN) constituem uma técnica promisora para conectar programação diferencial e domínios combinatoriais. GNNs lançam mão de módulos treináveis os quais podem ser montados em diferentes configurações, cada uma refletindo a estrutura relacional de uma instância específica. Nessa tese, nós propomos uma nova formulação para GNNs, a qual faz uso do conceito de “tipos” para particionar os objetos no domínio do problema em múltiplas classes distintas, resultando no modelo das Typed Graph Networks (TGN) e numa biblioteca Python / Tensorflow para prototipar TGNs. Esta tese também se preocupa com a aplicação de GNNs no Problema do Caixeiro(a) Viajante (PCV). Nós mostramos que GNNs são capazes de aprender a resolver, com pouquíssima supervisão, a variante de decisão do PCV, um problema NP-Completo altamente relevante. Nosso modelo é treinado para funcionar, efetivamente, como um algoritmo de troca de mensagens em grafos no qual as arestas do grafo de entrada comunicam-se com os vértices do grafo de entrada por um determinado número de iterações, depois do qual o modelo é forçado a responder se o grafo de entrada admite ou não uma rota Hamiltoniana de custo < C 2 R+ 0 . Nós mostramos que esta rede pode ser treinada com conjuntos de exemplos duais: dado o custo ótimo C , produzimos uma instância de decisão com custo alvo (C) x% menor e uma com custo alvo x% maior do que C . Nós fomos capazes de obter 80% de acurácia treinando o modelo com desvios de −2%,+2%, e o mesmo modelo treinado foi capaz de generalizar para desvios mais relaxados com melhor performance. Também mostramos que o modelo é capaz de generalizar para problemas maiores. Finalmente, nós oferecemos um método para predizer o custo de rota ótimo dentro de 1.5% de desvio relativo para o valor real. Em resumo, nosso trabalho demonstra que GNNs são suficientemente poderosas para resolver problems NP-Completos que combinam dados simbólicos e numéricos, além de propor uma reformulação moderna do meta-modelo. |