English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The Multidimensional Knapsack Problem(MKP) is one of the best known combinatorial optimization problem with many practical applications. Despite its popularity and demand for high-quality solutions, this is aNP-hard problem, which needs alternative strategies to obtain good solutions in a viable time. In this context, metaheuristics have been successful in solving different difficult problems, including MKP. In this work, two GPGPU implementations of the Particle Swarm Optimization Algorithm (PSO) are proposed. The run time improvement of the GPGPU programs compared to the sequential version was relevant, which showed the effectiveness of using parallelization strategies with the studied metaheuristic. Resumo. Um dos problemas mais conhecidos de otimização combinatória, que possui diversas aplicações práticas, é o problema da mochila multidimensional (MKP). Apesar de sua popularidade e da demanda por soluções de alta qualidade, este é um problema NP-difı́cil, o que leva à necessidade de buscar estratégias alternativas para obtenção de boas soluções em tempo viável. Neste contexto, as metaheurı́sticas se destacam, visto que têm sido bem sucedidas na resolução de diferentes problemas difı́ceis, inclusive do MKP. Neste trabalho, são propostas duas implementações usando GPGPU do algoritmo de otimização por enxame de partı́culas (PSO). A redução nos tempos de execução dos programas GPGPU em comparação com a versão sequencial foi relevante, o que mostrou a eficácia do uso de estratégias de paralelização com a metaheurı́stica estudada. 1. Introdução O Problema da Mochila Multidimensional (multidimensional knapsack problem – MKP) é uma variante do problema da mochila binária no qual há um conjunto de itens (com seus respectivos custos) e um conjunto de duas ou mais restrições. Deseja-se encontrar uma combinação de itens que respeite as restrições e maximize a função objetivo. Dado que o problema é NP-difı́cil, não são conhecidos algoritmos eficientes capazes de obter uma solução ótima em tempo viável para instâncias arbitrariamente grandes. Devido a essa caracterı́stica, é necessário utilizar estratégias alternativas para solucionar o problema, ainda que de forma aproximada. Dentre tais estratégias, a utilização de metaheurı́sticas populacionais, como, por exemplo, algoritmos genéticos [Chu and Beasley 1998], otimização por colônia de formigas [Fingler et al. 2014], algoritmo de otimização por enxame de partı́culas (Particle Swarm Optimization – PSO) [Chih et al. 2014], entre outros, tem recebido destaque e se mostraram efetivos de acordo com a literatura. O PSO, foco dos estudos deste trabalho, utiliza inteligência de um enxame de partı́culas para explorar o espaço de soluções. Ele foi inicialmente proposto com foco na solução de problemas contı́nuos, mas, desde então, diversas novas versões foram propostas, incluindo versões paralelas e hı́bridas, tais como propuseram [Jam et al. 2017], até mesmo para problemas discretos como o MKP [Essaid et al. 2019]. O MKP e o PSO são definidos na Seção 2 e Seção 3, respectivamente; na Seção 4, os modelos implementados são descritos; os experimentos realizados, com os respectivos resultados, são mostrados na Seção 5; na Seção 6, as conclusões e trabalhos futuros são apresentados. 2. Problema da Mochila Multidimensional (MKP) O problema da mochila multidimensional (multidimensional knapsack problem – MKP), também conhecido como problema da mochila multidimensional 0-1, é um problema de otimização combinatória bastante conhecido na literatura e consiste em, dado um conjunto de itens, obter o subconjunto deles que maximiza o valor da mochila, sem que suas múltiplas restrições sejam violadas. Formalmente, o problema pode ser definido por uma mochila com suas restrições r1, r2, ..., rm , um conjunto com n itens, cada um destes i itens, 1 ≤ i ≤ n, com seu valor associado, vi, e a quantidade de recurso consumido, pij . Considerando xi uma variável de decisão binária que indica a presença de i na solução, define-se a função objetivo a ser maximizada de acordo com a Equação (1) [Chu and Beasley 1998]

Implementações GPGPU do Algoritmo de Otimização por Enxame de Partı́culas para o Problema da Mochila Multidimensional