Cunning Ant System for Quadratic Assignment Problem with Local Search and Parallelization
The previously proposed cunning ant system (cAS), a variant of the ACO algorithm, worked well on the TSP and the results showed that the cAS could be one of the most promising ACO algorithms. In this paper, we apply cAS to solving QAP. We focus our main a
- PDF / 575,384 Bytes
- 10 Pages / 430 x 660 pts Page_size
- 115 Downloads / 202 Views
Abstract. The previously proposed cunning ant system (cAS), a variant of the ACO algorithm, worked well on the TSP and the results showed that the cAS could be one of the most promising ACO algorithms. In this paper, we apply cAS to solving QAP. We focus our main attention on the effects of applying local search and parallelization of the cAS. Results show promising performance of cAS on QAP.
1
Introduction
In a previous paper [1,2], we have proposed a variant of the ACO algorithm called the cunning Ant System (cAS) and evaluated it using TSP which is a typical NP-hard optimization problem. The results showed that the cAS could be one of the most promising ACO algorithms. In this paper, we apply cAS to solving the quadratic assignment problem (QAP). The QAP is also an NPhard optimization problem and it is considered one of the hardest optimization problems [3,4]. The QAP is also a good set of problems for testing the capabilities of solving combinatorial optimization problems. There are many studies on solving QAP with ACO showing better results than with other meta-heuristics. These studies are summarized in [5]. Typical examples of ACO algorithms for the QAP are AS-QAP, MMAS-QAP, and ANTS-QAP. Among these, it is reported that MMAS-QAP [3] is the best performing algorithm [5]. We performed a preliminary study which applied cAS to solving QAP in [6]. In this paper, we apply cAS to solving QAP and compare the performance with the performance of MMAS [3]. We also discuss an approach for parallelization of the cAS for QAP. In the remainder of this paper, Section 2 gives a brief overview of cAS when it is applied in TSP. Then, Section 3 describes how the solutions with cAS for the QAP are constructed. In Section 4, we provide an empirical analysis of the cAS and compare the results with MMAS. In Section 5, we study the use of a kind of parallelization of cAS, with the aim of achieving faster execution of the algorithm in a network environment. Finally, Section 6 concludes this paper. A. Ghosh, R.K. De, and S.K. Pal (Eds.): PReMI 2007, LNCS 4815, pp. 269–278, 2007. c Springer-Verlag Berlin Heidelberg 2007
270
2
S. Tsutsui
A Brief Overview of cAS
cAS [1,2] introduced two important schemes. One is a scheme to use partial solutions which we call cunning. The other is to use the colony model, dividing colonies into units. Using partial solutions to seed solution construction in the ACO can be found in [7,8,9] with other frameworks. The agent introduced in cAS is called cunning ant (c-ant ). The c-ant differs from traditional ants in its manner of solution construction. It constructs a solution by borrowing a part of existing solutions. The remainder of the solution is constructed based on τij (t) probabilistically as usual. In a sense, since this agent in part appropriates the work of others to construct a solution, we named the agent c-ant after the metaphor of its cunning behavior. An agent from whom a partial solution has been borrowed by a c-ant is called a donor ant (d-ant ). We use a colony model which consis
Data Loading...
