18169.dvi

Computing and Informatics, Vol. 28, 2009, 1001–1012, V 2009-Mar-2 OPTIMIZATION OF QUADRATIC ASSIGNMENTPROBLEM USING SELF ORGANISINGMIGRATING ALGORITHM Donald Davendra, Ivan Zelinka Department of Applied InformaticsTom´ 760 01 Zl´ın, Czech Republice-mail: {davendrai, zelinka}@fai.utb.cz Revised manuscript received 9 December 2008 Abstract. This paper introduces the primary research involving Self OrganinsingMigrating Algorithm (SOMA) to the permutative problem of Quadratic Assign-ment. SOMA is transformed from its canonical form to successfully solve permuta-tive optimization problems. Conversion and repairment routines are added to thegeneric SOMA. The results presented outline the high effectiveness of SOMA forsolving QAP problems.
Keywords: Self organizing migrating algorithm, quadratic assignment problem,combinatorial optimization NP problem optimization comprises a large and important class of practical problemsin science, engineering and business [1]. While real domain problems (non-linear,differential etc) comprise a large domain of optimization problems, permutativeproblems command a higher difficulty rating since most are intractable.
The principle application for such problems can be seen in real life applications, like manufacturing floor design and planning, routing problems like vehicle, networkdata amongst others. Layout planning and design alongside large scale manufactur-ing system depend on optimization tools [1].
D. Davendra, I. Zelinka Currently a number of heuristics exist which deal with these problems; however, most arose as canonically real optimization tools, later modified for permutativeproblems. Ant Colony [2], Differential Evolution [3, 4] are few of such heuristics.
This research introduces a next generation optimization heuristic of SOMA, which has proven highly effective in solving real optimization problems [5, 6]. SOMAis transformed to solve the Quadratic Assignment Problem (QAP) and its effective-ness is compared against some other optimization tools.
This paper is divided into the following sections. Section 2 outlines SOMA and its transformation routines. Section 3 describes QAP and its formulation. Section 4discusses the experimentation and results and Section 5 concludes the work.
2 SELF ORGANINSING MIGRATING ALGORITHM SOMA is a stochastic optimization algorithm modelled on the social networkingbehaviour of co-operating individuals [18]. It was chosen because it has been proventhat the algorithm has the ability to converge towards the global optimum [5, 6].
SOMA works on a population of candidate solutions in loops called migration loops or generation loops. The population is initialized randomly which gives ita distribution over the search space at the beginning of the search. In each loop,the population is evaluated and the solution with the highest fitness becomes theleader. Apart from the leader, in one migration loop, all individuals will traversethe input solution space in the direction of the leader.
An individual will travel a certain distance (called the path length) towards the leader in n steps of defined length or step size. If the path length is chosen tobe greater than one, then the individual will overshoot the leader. This path isperturbed randomly.
Mutation, the random perturbation of individuals, is an important operation forevolutionary strategies (ES). It ensures the diversity amongst the individuals andit also provides the means to restore lost information in a population. However,mutation is applied differently in SOMA compared with other ES strategies. SOMAuses a parameter called PRT to achieve perturbation. This parameter has the sameeffect for SOMA as mutation has for GA. It is defined in the range [0, 1] and is usedto create a perturbation vector (PRT Vector) as follows: if rndj < P RT then PRTVectorj = 1 The novelty of this approach is that the PRT Vector is created before an indi- vidual starts its journey over the search space. The PRT Vector defines the finalmovement of an active individual in search space.
Optimization of QAP using SOMA The randomly generated binary perturbation vector controls the allowed dimen- sions for an individual. If an element of the perturbation vector is set to zero, thenthe individual is not allowed to change its position in the corresponding dimension.
2.2 Generating New Candidate Solutions In standard ES the Crossover operator usually creates new individuals based oninformation from the previous generation. Geometrically speaking, new positionsare selected from an N dimensional hyper-plane. In SOMA, which is based on thesimulation of cooperative behaviour of intelligent beings, sequences of new positionsin the N -dimensional hyperplane are generated. They can be thought of as a seriesof new individuals obtained by the special crossover operation. This crossover ope-ration determines the behaviour of SOMA. The movement of an individual is thusgiven as follows: • r: new candidate solution• r0: original individual• m: difference between leader and start position of individual • t ∈ [0, Path length]• PRTVector: control vector for perturbation.
It can be observed from Equation (2) that the PRT vector causes an individual to move toward the leading individual (the one with the best fitness) in N − kdimensional space. If all N elements of the PRT vector are set to 1, then thesearch process is carried out in an N dimensional hyperplane (i.e. on a N + 1 fitnesslandscape). If some elements of the PRT vector are set to 0 then the second termon the right-hand side of Equation (2) equals to 0. This means those parameters ofan individual that are related to 0 in the PRT vector are ‘frozen', i.e. not changedduring the search. The number of frozen parameters k, is simply the number ofdimensions that are not taking part in the actual search process. Therefore, thesearch process takes place in an N − k dimensional subspace.
2.3 Permutative Approach As mentioned earlier, the canonical approach of SOMA is for differential problem,which accepts real numbers as parameters. In this research, SOMA is slightly modi-fied to work within the integer domain, specifically permutative. Permutative impliesthat each unique value in the solution.
The process to transform the heuristic is done in two parts: 1. permutative population2. repairment of solution.
D. Davendra, I. Zelinka 2.3.1 Permutative Population As in the general case with all heurisitcs, the initial population is randomly generatedto resemble a permutative structure. For example, if solving a 5 size problem,a solution string containing 5 unique integers ranging from 1 to 5 will be randomlygenerated.
2.3.2 Repairment of Solution SOMA transforms the solution into real values, simply through its inner transfor-mation. The resulting solution is real. In order to transform it back into the integerdomain, a simple rounding of the value is done to achieve its integer equivalent asgiven in the following equation: ri = int [ ri] .
Subsequently, the entire solution is rendered integer. At this point, a repairment procedure is applied to first bring all values within the operating range, and thena repairment procedure is applied.
upper bound ≤ ri ≤ lower bound 2.4 Repairment Pseudocode The first routine scans the solution for all the missing values. Starting from an indexin the solution, all subsequent values are scanned for replicated value. If one isdetected, then it is stored in the missing value array.
if (solution is infeasible)Scan solution for missing valuesFor (i = 1; i < Upperbound; i++) { Bool = false;For (j = 0; j < Upperbound; j++) { If (Solution == i)Bool = true; If (Bool == false) missing val array = i Optimization of QAP using SOMA The second routine assigns a value 0, for all positions which contain a replicated value. This simplifies the potions for replacement.
∗Scan solution for replicated valuesFor (i = 1; i < Upperbound; i++) { Pos Array = 0;For (j = 0; j < Upperbound; j++) { If (Solution == i)Pos Array = 0; If (Pos Array > 1) Replicated pos = Pos Array The third routine replaces the values assigned to 0 by a value from the missing value array.
∗Randomly select values to be replaced with missing valuesFor (i = 0; i < size of missing value array; i++) Rand [SolutionReplicated pos] = Rand [missing val array]Delete value from Replicated Pos arrayDelete Rand [missing val array] The last function is presented in simplified format. In essence it shows that a random value is selected from the missing val array, and this value is insertedin the solution array indexed by a value randomly selected from the replicated posarray. After completion, both these values are deleted from their respective arrays.
The primary reason for demonstrating this routine is that it has proven to be highly effective in repairing infeasible solutions [7, 8]. However, the reader shouldkeep in mind that only infeasible solution are repaired. The repaired solution is thentested for its fitness value, and compared against the leader of the population.
A schematic of the operations of SOMA is given as an example in Figures 1–3.
Figure 1 gives the initial conditions of SOMA. For illustration purpose, the operating parameters in Figure 1 are set in "Parameter Settings". The Step Sizeis 0.23, Path Length is 3 and PRT is set to 0.1.
The crossover and mutation schema of SOMA is illustrated in Figure 2. Only 5 solutions are generated, and vetted for its fitness. As shown, Solution 3 has theminimal fitness, and is selected as the "leader".
Taking each solution in turn, a jump sequence is done towards the leader using the SOMA routine. However, the obtained solutions can be infeasible (real values)as shown by value 2.92. The "repair" routine repairs the solution (from 2.92 to 5)so that all values are permutative.
The new fitness of the solution is calculated, and if it improves on the old fitness as is the case of the third solution with value 34 231, the new soluion replaces the old D. Davendra, I. Zelinka PRT Vector
Path Length 3PRT 0.1 Migrations 300PopSize 5 i=1 j =1 Fig. 1. Initial Conditions solution with value 65 376 in the "population". After each iteration, the "leader" isrecalculated.
3 QUADRATIC ASSIGNMENT PROBLEM The QAP is a combinatorial optimization problem stated for the first time by [9] andis widely regarded as one of the most difficult problems in this class. The approachis to have two matrices of size n × m given as: The objective is then to find the permutation π∗ which minimizes min f (π) = X X aijbπ(i)π(j) where Q (n) is a set of permutations of n elements. QAP is considered a NP hardproblem [14] and problem sizes larger than 20 are considered intractable. Manyapplication have been identified for QAP, which include, amongst others, the allo-cation of plants to candidate locations; layout of plants; backboard wiring problem;design of control panels and typewriter keyboards; balancing turbine runners; or-dering of interrelated data on a magnetic tape; processor-to-processor assignment ina distributed processing environment; placement problem in VLSI design; analyzingchemical reactions for organic compounds; and ranking of archaeological data. Thedetails and references for these and additional applications can be found in [11].
For large sized problems, heuristic approaches have been developed. The most notable ones include: simulated annealing [12], tabu searches of [11, 12, 13], thehybrid genetic-tabu searches [14] and the ant colony approach [2].
Optimization of QAP using SOMA Parameter 1 Parameter 2 Parameter 3 Parameter 4 Parameter 5 x MK +1 = x MK + x MK ! xMK i, j L, j t " 0, by Step to, PathLength New Position
Best solutions are selected
for next generation
Fig. 2. SOMA schematic for QAP 4 RESULTS AND ANALYSIS The benchmark QAP problems were obtained from the OR Library [15] which isthe respository of all benchmark scheduling problems. Two different sets of experi-mentations were conducted; on Irregular and Regular problems.
The difference between regular and irregular problems is based on the flow − dominance(fd) which is used to differentiate among the classes of QAP instances. Itis defined as a coefficient of variation of the flow matrix entries multiplied by 100.
D. Davendra, I. Zelinka Parameter 1 Parameter 2 Parameter 3 Parameter 4 Parameter 5 Fig. 3. Final Solution where:µ = 1 · Pn Pn Irregular problems have fd larger than 1.2 where as regular problems have fd lower than 1.2.
The results produced by SOMA for these two different problem sets are given in Tables 1 and 2. These are the average values over 10 iterations, each having 200migrations.
Table 1. Comparison data of SOMA for regular QAP problems Optimization of QAP using SOMA Table 2. Comparison data of SOMA for irregular QAP problems For these experimentations, the SOMA version of All−to−One was selected.
The reasoning for this issue was the issue of optimizing the execution time. Theoperations parameters of SOMA as outlined in Section 2 were found through expe-rimentation and are given in Table 3.
Table 3. Operational parameters for SOMA Three native SOMA parameters are to be optimized, namely PathLength, Step Size and PRT. PRT is chosen as 0.1 therefore a maximum of 90 % of the dimensionsare under consideration at any iteration. The PathLength is set as 3, since the solu-tion jumps two steps beyond the leader from its starting point. PathLength longerthan 3 is not deemed feasible due to the extended execution time required. TheStepSize is the only variable which can generally be said to be problem dependent.
The starting point of 0.1 and incrementation of 0.01 − 0.02 per execution wouldbe sufficient to obtain the optimal operating value. Population size and number ofiterations/migrations are, as in all metaheuristics, problem dependent.
Comparisons were made with other heuristics of Tabu Search TT [11], Reactive Tabu Search (RTS) [16] and the Genetic Hybrid (GH) method [14]. A SimulatedAnnealing (SA) [12] approach that is cited as a good implementation in [17] was alsoincluded. Finally the work covered [18] with Ant Colony (HAS-QAP) is comparedas the best results for these instances of QAP.
The average quality of the solutions produced by the methods is shown, mea- sured in per cent above the best solution value known from the OR Library [15].
The best results obtained are indicated in boldface. The well performing heuristicsare able to produce solutions with at less than 1 % with the same computing powerand time.
D. Davendra, I. Zelinka Analysis of the results reveals that SOMA functions exceptionally well in the both classes of problems. For the bur problem class, it only fails to find one optimalsolution, and is the best heuristic in the chr problem. It performs better in the kraproblem set and competes evenly in the tai set with the other heuristic of HAS-QAP.
On reflection HAS-QAP only performs better on 4 instances than SOMA.
The irregular problems reflect the advantage of SOMA more clearly. SOMA obtains the best solution in all but two problem instances of sko42 and wil50, andthe optimal solution in the three instances of nug20, tai20 and tai25.
A sample generation output is given in Figure 4.
SOMA Best Individual History
Bur26a QAP Instance
1.3 ´ 107
1.2 ´ 107
1.1 ´ 107
Fig. 4. QAP generation output The application domain of SOMA has been extended in this research to permutativeNP problems. The experimentations with QAP have validated the stated approach,with comparable results, both with other heuristics but more importantly with theoptimal solutions. The results obtained especially for the irregular problems high-lighted the effectiveness of SOMA.
The authors believe that this is the first application of SOMA in NP problems and further research would entail the application to other problems like flow shopand traveling salesman.
Optimization of QAP using SOMA This research was supported by grant from the Grant Agency of Czech RepublicGACR 102/06/1132.
[1] Onwubolu, G.: Emerging Optimization Techniques in Production Planning and Control. Imperial College Press, London, 2002.
[2] Dorigo, M.—Gambardella, L.: Ant Colony System: A Co-operative Learning Approach to the Traveling Salesman Problem. IEEE Transaction on EvolutionaryComputations, 1997, No. 1, pp. 53–65.
[3] Price, K.: An Introduction to Differential Evolution. In: D. Corne, M. Dorigo and F. Glover (Eds.): New Ideas in Optimization, McGraw-Hill, London, UK, 1999,pp. 79–108.
[4] Onwubolu, G.—Davendra, D.: Scheduling Flow Shops Using Differential Evolution Algorithm. European Journal of Operations Research, Vol. 171, 2006,pp. 674–679.
[5] Zelinka, I.: SOMA – Self Organizing Migrating Algorithm. In: G. Onwubolu and B. Babu, (Eds.): New Optimization Techniques in Engineering, Springer-Verlag,2004.
[6] Zelinka, I.—Lampinen, J.—Nolle, L.: On the Theoretical Proof of Conver- gence for a Class of SOMA Search Algorithms. Proceedings of the 7th InternationalMENDEL Conference on Soft Computing, Brno, CZ, June 6–8, 2001, pp. 103–110.
[7] Davendra, D.: Hybrid Differential Evolution Algorithm for Discrete Domain Prob- lems. Master of Science Thesis, University of the South Pacific, Suva, Fiji Islands,2003.
[8] Garca, P.—Gonzalez-Castano, F.—Burguillo-Rial, J.: A Combined Glo- bal & Local Search (CGLS) Approach to Global Optimization. Journal of Global Op-timization, Vol. 34, 2006, No. 3, pp. 409–426.
[9] Koopmans, T.—Beckmann, M.: Assignment Problems and the Location of Eco- nomic Activities. Econometrica, 1957, No. 25, pp. 53–76.
[10] Sahni, S.—Gonzalez, T.: P-Complete Approximation Problems. Journal of the ACM. 1976, No. 23, pp. 555–565.
[11] Battitti, R.—Tecchiolli, G.: The Reactive Tabu Search. ORCA Journal on Computing, Vol. 6, 1994, pp. 26–140.
[12] Connolly, D.: An Improved Annealing Scheme for the QAP. European Journal of Operation Research, 1990, No. 46, pp. 93–100.
[13] Taillard, E.: Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing, Vol. 17, 1991, pp. 443–455.
[14] Fleurent, C.—Ferland, J.: Genetic Hybrids for the Quadratic Assignment Prob- lem. Operations Research Quarterly, Vol. 28, 1994, pp. 167–179.
[15] OR Library web site. Available at: http://mscmga.ms.ic.ac.uk/info.html.

D. Davendra, I. Zelinka [16] Taillard, E.: Comparison of Iterative Searches for the Quadratic Assignment Prob- lem. Location Science, 1995, No. 3, pp. 87–105.
[17] Burkard, R.: Location With Spatial Interactions: The Quadratic Assignment Prob- lem. In: P. Mirchandani and R. Francis (Eds.): Discrete Location Theory, John Wiley,1991.
[18] Gambardella, L.—Thaillard, E. D.—Dorigo, M.: Ant Colonies for the Quadratic Assignment Problem. Journal of Operational Research, 1999, No. 50,pp. 167–176.
is a Ph. D. candidate in technical cybernet- aˇs Baˇta University in Zl´ın, Czech Republic. He has a M. Sc. in computer science from the University of the SouthPacific, Fiji. His research area is in intelligent manufacturingand chaotic systems applied to evolutionary heuristics.
is the Associate Professor of Informatics at To- m´aˇs Baˇta University in Zl´ın. He is the recipient of the SiemensBest European Ph. D. Dissertation Award for his work on SO-MA. He is also the inventor of analytical programming, and au-thor of books and articles on chaotic and evolutionary systems.
His website is www.fai.utb.cz/people/zelinka/hp.

Source: http://www.cai.sk/ojs/index.php/cai/article/download/31/18