Article Preview
Top1. Introduction
The Quadratic three-Dimensional Assignment Problem (Q3AP) is extended from the well-known Quadratic Assignment Problem (QAP). Solving the Q3AP consists of finding two permutation vectors as an optimum, whereas solving the QAP consists of finding one optimal permutation vector only. The Q3AP was introduced for the first time by Pierskalla (Pierskalla,1967) in 1967 and re-discovered by Hahn et al. (Hahn, 2008) later in 2008. In data transmission systems, when a data packet is sent through variable fading channels, some errors may remain in some bits of the received message, even after error correction mechanisms are used (Zhang,2008) and (Hahn, 2008).
The Hybrid Automatic Repeat reQuest (HARQ) mechanism transmits a package by breaking it down into segments and mapping these segments to symbols. In case of an irrecoverable error, the package is retransmitted with another mapping from segments to symbols. Finding an optimum mapping for two successive transmissions can be considered as an instance of Q3AP. The Q3AP is classified as one of the hardest permutation problems and whose solution can significantly increase throughput and reduce the cost for providing reliable digital transmission over noisy fading channels. For optimizing a HARQ protocol, solving the Q3AP consists of finding an optimal symbol mapping over two vectors whereas, a QAP is to solve a single vector permutation (Samra, 2005).
The Q3AP is an NP-hard problem (Hahn, 2008), because it is an extension of two problems which are themselves NP-hard: the quadratic assignment problem (QAP) and the axial 3-assignment problem (A3AP) (Hahn, 2008). We cannot solve large size instances using exact methods because the size of the search space for an instance of size N from Q3AP is N! 2 (Hahn, 2008) and since typical symbol-mapping (Q3AP) problems may be of sizes 8, 16, 32 and 64, we consider combining metaheuristics that have complementary features. We believe it can significantly improve the effectiveness of the solving methods.
Swarm intelligence (SI), is a discipline of artificial intelligence (AI), where the system is composed of many individuals that coordinate with each other. It is a set of nature-inspired paradigms that have received a lot of attention in computer science due to its simplicity and adaptability (Stützle, 2011). A few examples of swarm intelligence studies are Ant Colony Optimization (ACO) (Dorigo, 1991), Particle Swarm Optimization (PSO) (Kennedy, 1995) and Ant-based Control (ABC) (Schoonderwoerd, 1997). Many hard optimization problems were solved by swarm intelligence methods like the three Assignment Problem(3AP), the Quadratic Assignment Problem (QAP) and Travelling Salesman Problem (TSP).
The Particle Swarm Optimization (PSO) method figures among the most popular swarm intelligence algorithms due to its ability to solve many optimization problems like the QAP problem (Mamaghani, 2012),(Congying, 2011),(Liu, 2007),(Gong, 2008).
In one of our earlier work (Abderrahim, 2016), we tried to apply PSO to solve the Q3AP. The obtained results were not encouraging. Where in the PSO algorithm, the heuristic used to generate the next explored solution was breaking the permutation structure of the solution which caused a problem of convergence which produced only approximate solutions but not optimal even for small instances.
A popular way of producing improved algorithms is to hybridize two or more existing methods in an attempt to combine favorable features while omitting undesirable aspects. Some of the best results for real-life and classical optimization problems are obtained using hybrid methods. Local Search (LS) algorithms are a class of metaheuristics that have proved their efficiency to solve difficult optimization problems. These methods start from a feasible solution to the problem at hand and try to improve it by a solution of its neighborhood.
In this paper, we propose to solve the problem of the Q3AP using PSO algorithm that we adapted for Q3AP hybrid with a local search method which is an Iterated Local Search (ILS) embedding Tabu Search (TS) to solve the Q3AP. We can show that this approach could reach the optimal solution or best-known value for most of the instances. The remainder of the paper is organized as follows. In section 2, we define the QAP and Q3AP problems. Section 3 reviews the related works. In section 4, we describe the particle swarm optimization (PSO) algorithm and how it was adapted to optimize the Q3AP problem. In section 5, we present our proposal which is a hybrid optimization method that combines PSO with an ILS embedding a TS. Section 6 reports experimental results. Section 7 concludes the work and gives some perspectives.