Multi-swarm PSO algorithm for the Quadratic Assignment Problem: a massive parallel implementation on the OpenCL platform
This paper presents a multi-swarm PSO algorithm for the Quadratic Assignment Problem (QAP) implemented on OpenCL platform. Our work was motivated by results of time efficiency tests performed for single-swarm algorithm implementation that showed clearly that the benefits of a parallel execution platform can be fully exploited, if the processed population is large. The described algorithm can be executed in two modes: with independent swarms or with migration. We discuss the algorithm construction, as well as we report results of tests performed on several problem instances from the QAPLIB library. During the experiments the algorithm was configured to process large populations. This allowed us to collect statistical data related to values of goal function reached by individual particles. We use them to demonstrate on two test cases that although single particles seem to behave chaotically during the optimization process, when the whole population is analyzed, the probability that a particle will select a near-optimal solution grows.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal Assignment and Motion Control in Two-Class Continuum Swarms
We consider optimal swarm control problems where two different classes of agents are present. Continuum idealizations of large-scale swarms are used where the dynamics describe the evolution of the spatially-distributed …
Green Heron Swarm Optimization Algorithm - State-of-the-Art of a New Nature Inspired Discrete Meta-Heuristics
Many real world problems are NP-Hard problems are a very large part of them can be represented as graph based problems. This makes graph theory a very important and prevalent field of study. In this work a new bio-inspir…
Combinatorial OptimizationA Benchmark for Multi-UAV Task Assignment of an Extended Team Orienteering Problem
A benchmark for multi-UAV task assignment is presented in order to evaluate different algorithms. An extended Team Orienteering Problem is modeled for a kind of multi-UAV task assignment problem. Three intelligent algori…
Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem
A quadratic assignment problem (QAP) is a combinatorial optimization problem that belongs to the class of NP-hard ones. So, it is difficult to solve in the polynomial time even for small instances. Research on the QAP ha…
Combinatorial OptimizationPasMoQAP: A Parallel Asynchronous Memetic Algorithm for solving the Multi-Objective Quadratic Assignment Problem
Multi-Objective Optimization Problems (MOPs) have attracted growing attention during the last decades. Multi-Objective Evolutionary Algorithms (MOEAs) have been extensively used to address MOPs because are able to approx…
Evolutionary Algorithms