ارزیابی عملکرد الگوریتم چندمنظوره کلونی مورچه بر روی مسائل تخصیص دو هدفه درجه دوم

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.

The quadratic assignment problem (QAP) is one of the NP-hard problems. Since its first formulation introduced by Koopmans and Beckmann [1], it has been used to model a wide variety of areas in real-life problems such as facility layouts, parallel and distributed computing, and combinatorial data analysis. In addition, the traveling salesman problem which is a combinatorial optimization problem, the problems such as maximum clique and graph partitioning problems can be formulized as a QAP. It is possible to see many different formulations to describe QAP instances as structural. Some of these are integer programming, combinatorics, linear algebra, graph theory etc. In spite of some difficulties in solving QAP, with the evolution of new mathematical-based solution techniques that are less than metaheuristic techniques quantifically, it has become more encouraging and challenging. Multiobjective optimization problems that have to be optimized simultaneously, making it particularly difficult to solve the problem therefore, are characterized by a few objectives. The use of metaheuristics for these problems has been subject to a growing interest in the last decade. The existence of many multiobjective problems in the real world, their intrinsic complexity, and the advantages of metaheuristic procedures to deal with them has strongly developed in this research area in the last few years [2]. The difficulties of solving multiobjective combinatorial optimization problems have led researchers to investigate the alternatives and approaches that have been getting better performances. In recent years some algorithms based on ant colony optimization (ACO) have been proposed to solve the multiobjective problems. ACO is a metaheuristic inspired by some varieties of ant species that are searching for the shortest path for food resources. Since Dorigo et al. [3] launched a study on the first ACO algorithm (Ant System), many researchers have evaluated different ACO algorithms to solve similar combinatorial optimization problems such as traveling salesman problem, quadratic assignment problems, scheduling, vehicle routing, financing. Recently, some researchers have designed ACO algorithms to solve multiobjective problems. Many various multiobjective problems included scheduling, portfolio selection, vehicle routing etc. have been solved by the algorithms which are called multiobjective ant colony optimization (MOACO) algorithms and good results have been obtained. It was the starting point of this study that MOACO algorithms have never been used to solve multiobjective QAP (MOQAP) instances. Thus, cited MOACO algorithms in the existing literature have been researched and programmed to solve biobjective quadratic assignment problem (BiQAP) instances. Then, the performances of these algorithms have been evaluated by a multi significance test. A metric called P is introduced in this study for effectively evaluating the biobjective algorithms in a pairwise comparison base. The paper is organized as follows: Section 2 presents QAP studies, formulations of BiQAP and MOQAP; Section 3 describes ant colony optimization and MOACO algorithms; Section 4 presents computational experiments and results; Section 5 closes with conclusions.

In this study, the authors emphasize that sometimes it could be impossible to evaluate all the criteria by looking at only one criterion and to define performance metrics. Especially, they indicate that to evaluate the performance comparisons from a statistical perspective is difficult, and also studies which are done by variance analysis and multi significance tests are still required. In our study a multi significance test has been used in a non hierarchical structure and a performance metric called P metric was introduced for this test. Then paired samples t tests were run for statistical comparisons of the MOACO algorithms from these priority values. Thus, we compare performances of the MOACO algorithms in an inductive and statistical way according to the priority values calculated from Pareto fronts of the algorithm runs and introduce the most successful MOACO algorithms. On the other hand, this is the first time that MOACO algorithms are compared by solving BiQAPs. It can be seen from the paired samples t tests that PACO and BA algorithms are the most successful algorithms and MOAQ algorithm is the worst one. It should be pointed out that the MOAQ algorithm is a method that do not consider Pareto front as a strategy. So, we can comment from all of these empirical studies that the methods which construct pheromone updating strategies especially by looking at the Pareto front and search the Pareto front faster and homogenously while constructing these strategies are successful rather than from the classical single objective systems for solving BiQAPs.