Solution

The results for nine instances of QAP are displayed, all proposed by Skorin-Kapov [11]. In this work, a data table shows the metaheuristics that were implemented. A table of results obtained by both metaheuristic in the same problem,same instance and the same metaheuristics.

The base code used to resolve this problem for different arrays, was extracted from (http://mistic.heig-vd.ch/taillard/\) which was originally develop in the programming language C.

It is important to mention that because of certain inefficiencies, the code was modified by authors of this work, in order to obtain the values needed to carry out the investigation, undo we change certain structures in the programming and change to C++.

We use the base algorithm of ant colony and simulated annealing, as we mention the first modification realize, is to get the code into classes and to programming language C++. Over the code we modify the process of data, in the original algorithm this initial values are get by a randomize function. We develop a function that produce values from a GRASP algorithm.

In this way, the algorithm does not start with random values, it start with “good” values for the search, in both cases it would start with values closer to the optimal solution. The algorithm is also modified in the structure; we introduce to code some recursive function base on this optimal search, so the algorithm could explore deeper solutions.

Experimental results were run on a Laptop with the following configurations:

ASUS K550, AMD A8-4500M APU with Radeon HD Graphics, 1.90 GHz, 4.00 GB RAM, and X64 based processor. This test was conducted with ACO, GRASP and SA algorithms.

In order to create a standard test set for QAP, in 1991QAPLIB was established which is accessible for all researchers and all QAP instances that were available to the authors at that time, are included in it. Following the huge positive feedback and continuing demands from scientific community in 1994 Bukard, Karisch and Rendl provided a major update which was even accessible through anonymous ftp as well.

Many new problem instances which were generated by researchers for their own testing purposed, were included in that update. In April 1996 QAPLIB was updated again. On one hand this update reflected on the big changes in electronic communication, which means, QAPLIB became a World Wide Web site, the QAPLIB Home Page. On the other hand, research activities around QAP were increased so much that another update was necessary and some recent (at that time) dissertations were added to the library. Some of the test instances were not solved optimally before, so another update released in June 2000 which contained new test instances and the optimal solutions for non-optimally solved old problems.

The next update was in January 2002 that again consists of new test instances and improvements on the best known feasible solutions, especially test the instances did not achieve to the optimal solution yet.Comparison of the algorithms is based on solution quality and execution time for real life QAP, in the experiment, we analyze the solution quality and run time for solving QAP using instances presented in QAPLIB site.

The next table statistics were obtained from 20 runs of the sequential program, for each instance in the metaheuristics.

Each table contains:

• Iterations = 4∗ n

• r = 150

• n = the array dimension

• OVBKV = Optimum value or best-known value

• BVF = Best value found in our proposal

• POS = Percentage by which the optimal solution or the BVF

• ARTCPU = Average CPU runtime

Table I presents the obtained results with the ACO metaheuristic. Table II presents the obtained results with the SA metaheuristic.

We determine the error that occurs in both metaheuristic with the following equation.

The following table (III) summarizes the error obtained for both metaheuristics, with the equation 4.

The following table (III) summarizes the error obtained for both metaheuristics, with the equation 4. these results, are the input parameters of these two algorithms, since the number of neighborhoods and interactions are crucial for a good efficiency. By Conducting further testing and modifying the random values, we conclude that the simulated annealing metaheuristic reaches the optimal value if we give a larger number of neighborhood and fewer iterations. Next table (III), shows these comparisons.

Table V presents certain numerical results for all of the instances in the QAPLIB, these were calculated with different algorithms proposed in this work. This table’s columns, contains several parts. The data from first part was taken form QAPLIB home page and the other parts are the results obtained from the algorithms.

The first part contains three columns. First column is the name of instances, which is abbreviation of author and size of the instance. The second column shows the feasible solution for all the instances. The gaps in between best known solution and the currently known best lower bound were shown in column number three. The other parts of this table contain two columns each. The best value found (BVF) and the average CPU runtime (ARTCPU) for ACO and SA, respectively.

The quadratic assignment optimization problem has always been studied since it was introduced to the scientific community, due to its complexity. There are problems that can be solved by exact algorithms or approximate heuristic but in the case of the exact algorithms, involves a too high computational cost and they are not feasible when time is critical. Metaheuristics are a good solution in a very competitive time in comparison with the exact algorithms with the disadvantage of poorer outcomes.

The ant colony optimization is a well defined metaheuristic and with good performance, ACO is applied to solve an increasing number of complex combinatorial optimization problems. We have compared two different metaheuristics applied to quadratic assignment problem. The results have shown that the ACO is a very fast metaheuristic. Simulated annealing is undoubtedly a very competitive method to find good solutions in short times applied to the quadratic assignment problem.

Simulated annealing metaheuristic is characterized by very short times in processing but their parameters are very difficult to configure.