{'fraction_non_alphanumeric': 0.02537593984962406, 'fraction_numerical': 0.008646616541353383, 'mean_word_length': 4.789989118607182, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Genetic Algorithm for solving Quadratic Assignment Problem(QAP)

The Quadratic Assignment Problem (QAP) is one of the models used for the multi-row layout problem with facilities of equal area. There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the aim of minimizing the sum of the distances multiplied by the corresponding flows. The QAP is among the most difficult NP-hard combinatorial optimization problems. Because of this, this paper presents an efficient Genetic algorithm (GA) to solve this problem in reasonable time. For validation the proposed GA some examples are selected from QAP library. The obtained results in reasonable time show the efficiency of proposed GA.


INTRODUCTION
Some multi-row layout problems are the control layout problem, the machine layout problem in an automated manufacturing system and office layout problem also the Travelling Salesman Problem (TSP) may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same nonzero (constant) value. Many other problems of standard combinatorial optimization problems may be written in this form (see [1] and [2]).
The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications and is widely regarded as one of the most difficult problem in classical combinatorial optimization problems. The QAP is NP-hard optimization problem [7], so, to practically solve the QAP one has to apply heuristic algorithms which find very high quality solutions in short computation time. And also there is no known algorithm for solving this problem in polynomial time, and even small instances may require long computation time [2].
The location of facilities with material flow between them was first modeled as a QAP by Koopmans and Beckmann [3]. In a facility layout problem in which there are n facilities to be assigned to n given location. The QAP formulation requires an equal number of facilities and locations. If there are fewer than n, say m<n, facilities to be assigned to n locations, then to use the QAP formulation, n-m dummy facilities should be created and a zero flow between each of these and all others must be assigned ( including the other dummy facilities). If there are fewer locations than facilities, then the problem is infeasible [4]. Considering previous works in QAP ([2], [8] and [9]) this paper is developed to solve this problem with GA in short computation time.
In the next section the QAP is described and formulated. After introducing GA in Section 3, the encoding scheme, solution representation and GA operators are described in this section.
The computational results are reported in Section 4. Finally, Section 5 concludes this paper and offers some directions for further research.

Mathematical model
The following notation is used in formulation of QAP [4]: The objective function (1) minimizes the total distances and flows between facilities. Constraints (2) and (4) ensure that each facility I is assigned to exactly one location. As well as Constraints (3) and (4) assure that each location j has exactly one facility which assigned to it. The term quadratic stems from the formulation of the QAP as an integer optimization problem with a quadratic objective function.

Encoding scheme
In this section we describe the encoding scheme for different component of proposed GA when n=5. For creating initial population we consider a chromosome with n gene, as any gene is depictive of assignment each facility to exactly one location. For example the chromosome in Figure 1 show that facilities 2,4,3,1 and 5 is assigned to locations 1,2,3,4 and 5 respectively that it is a feasible solution.

Crossover
We use two point crossovers for implementation of GA. For making child 1 and child 2, two points are randomly selected from 1 to 5 and between these points is hold fixed. Then, child 1 is created according to orders of parent 2 and fixed components of parent 1, as well as child 2 is produced according to order of parent 1 and fixed components of parent 2 (see Figure 3). After tuning the crossover probability is determined equal to 0.8. This means that 80% of selected parents participate in crossover operation.

Selection
In selection operator the number of chromosomes required to complete next generation from crossover, mutation and previous generation are determined special mechanism that we use roulette wheel mechanism. In roulette wheel selection, candidate solutions are given a probability of being selected that is directly proportionate to their fitness. The selection probability of a candidate solution I is  As it is illustrated in Table 1 the proposed GA results in the short computational time with acceptable GAP.

Conclusion
In this paper at first QAP as a special type of multi-row layout problem with facilities of equal area is introduced and its various applications in different fields are described. Then, due to NP-hard nature of QAP an efficient GA algorithm is