Name
Title | ||
|---|---|---|
An improved Particle Swarm Optimization/Tabu search approach to the Quadratic Assignment Problem |
Abstract | ||
|---|---|---|
Previous work introduced an approach called TBHPSO, which combines Hierarchical Particle Swarm Optimization (HPSO) with Tabu Local Search and a heuristic bias term, to the Quadratic Assignment Problem (QAP). Specifically, in TBHPSO, a Robust Tabu Local Search is applied to the top particle in the hierarchy in each PSO iteration; in addition, a heuristic “goodness” function, similar to that used in Ant Colony Optimization, is used to bias the PSO velocity update equation. In previous work, TBHPSO was found to perform significantly better than Diversified-Restart Robust Tabu Search (DivTS), a state-of-the-art technique for the QAP. In this paper, we introduce three variations to TBHPSO. The first variation (RTBHPSO) aims to increase search diversity by applying Tabu Local Search to a randomly chosen particle rather than always applying it to the root of the HPSO hierarchy. The second variation (DTBHPSO) applies DivTS (instead of RTS) to the top particle in the hierarchy, while the third variation first selects a random particle and then probabilistically selects either DivTS or RTS to apply to it. The performance of our proposed variations is compared against the original TBHPSO, keeping the CPU time fixed for both methods in each comparison, using 31 problem instances from the QAPLib instance library. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/CEC.2015.7256895 | 2015 IEEE Congress on Evolutionary Computation (CEC) |
Keywords | Field | DocType |
particle swarm optimization,quadratic assignment problem,QAP,heuristic bias term,robust tabu local search,ant colony optimization,diversified-restart robust tabu search,DivTS,search diversity,QAPLib instance library | Particle swarm optimization,Hill climbing,Mathematical optimization,Guided Local Search,Computer science,Quadratic assignment problem,Multi-swarm optimization,Artificial intelligence,Local search (optimization),Tabu search,Machine learning,Metaheuristic | Conference |
ISSN | Citations | PageRank |
1089-778X | 0 | 0.34 |
References | Authors | |
29 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ayah M. Helal | 1 | 8 | 2.86 |
| Enas Jawdat | 2 | 0 | 0.68 |
| Ashraf M. Abdelbar | 3 | 243 | 25.43 |