A Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem

The main distinguishing feature of SPX is that instead of transferring genes from parents to a child, the genes are, so to speak, rearranged in the chromosomes of the parents. Let $(p^{\prime }, p^{″})$ be a pair of parents. Then, the process starts from an arbitrary position and the positions are scanned from left to right. The process continues until a predefined number of swaps, $s$ ($s<n$), have been performed. If, in the current position, the genes are the same for both parents, then one moves to the next position; otherwise, a pairwise interchange of genes of the parents’ chromosomes is accomplished. The interchange is performed in both parents. For example, if the current position is $i$ and $a=p^{\prime }(i)$, $b=p^{″}(i)$, then there exists a position $j$ such that $b=p^{\prime }(j)$, $a=p^{″}(j)$; then, after a swap, $p^{\prime }(i)=b$, $p^{″}(i)=a$ and $p^{\prime }(j)=a$, $p^{″}(j)=b$. Consequently, new chromosomes, say $p^{‴}$, $p^{⁗}$, are produced. In the next iteration, a pair $(p^{‴}, p^{⁗})$ is considered, and so on.

This modification is achieved when the best offspring (with respect to the fitness of the offspring) is retained in the course of gene interchanges.

The essential feature this crossover procedure is that the offspring fitness is dynamically evaluated: only the gene interchanges that improve the value of the objective function are accepted.

The cycle crossover is based on the pairwise gene interchanges. The key property of CX is the ability to produce the offspring without distortion of the genetic code; in the other words, CX enables to create the chromosome with no random (foreign) genes. The negative aspect of CX is that the offspring may genetically be very close to their predecessors.

The cohesive crossover was proposed by Z. Drezner [75] to efficiently recombine individuals’ genes by taking into account the problem data, in particular, the distances between objects’ locations. From several recombinations of genes, the recombination is selected that minimizes the objective function.

In the multi-parent crossover, several (or all) members of a population participate in creation of the offspring. More precisely, the ith position (locus) of the offspring’s chromosome $p°$ is assigned the value $j$ with the probability $P(p(i)=j)$ (under condition that the value $j$ has not been utilized before).

The probability that $p(i)=j$ ($P(p(i)=j)$) is calculated according to the formula: $P(p(i)=j)=\frac{q_{ij}}{{{\displaystyle \sum }}_{j=1}^n{q}_{ij}}$; where $q_{ij}$ is an element of the matrix $Q={(q_{ij})}_{n\times n}$; here, $q_{ij}$ denotes the number of times that the ith locus takes the value $j$ in the parental chromosomes. If there exist several values ($j_1$, $j_2$, …) with the same probability, then one of them is chosen randomly.

The universal crossover (UNIVX) [124] distinguishes for its versatility and the possibility of flexible usage depending on the specific needs of the user. It is somewhat similar to what is known as a simulated binary crossover [126].

Our operator is based on the use of a random mask. There are four controlling parameters: ${\chi }_1$, ${\chi }_2$, ${\chi }_3$, ${\chi }_4$. The mask length is equal to ${\chi }_1$, where ${\chi }_1$ is a (pseudo-)random number within the interval $[{\epsilon }_1, n]$, $n$ is the length of the chromosome, ${\epsilon }_1=\lfloor r\times n\rfloor$, $r$ is the user’s parameter close to $1$, for example, $0.9$. The mask contains binary values $0$ and $1$, where $1$ signals that the corresponding gene of the first parent’s chromosome must be chosen and $0$ is to indicate that the second parent’s gene needs to be replicated. The degree of randomness of the mask is controlled by the parameters ${\chi }_2$, ${\chi }_3$. The parameter ${\chi }_2$ (${\chi }_2\in [{\epsilon }_2, {\epsilon }_3]$, $0<{\epsilon }_2\le {\epsilon }_3<1$) dictates how many $0$’s and $1$’s are there in the mask: the higher the value of ${\chi }_2$, the bigger total number of $1$’s, and vice versa. The juxtaposition of bits is regulated by the parameter ${\chi }_3$. The bit generation itself is performed by using a kind of “anytime” min-max sorting algorithm. That is, if the sorting algorithm is interrupted at some random moment, this results in a randomized (“quasi-sorted”) sequence of bits. The moment of interruption is defined by the number $\eta$, where $\eta ={\chi }_{3}w$, here ${\chi }_3$ is a (pseudo-)random real number from the interval $[0, 1]$, and $w$ denotes the maximum number of iterations required to fully sort all the bits. (As an example, if the bits “$0000001111$” are to be sorted in the descending order and the algorithm is stopped at ${\chi }_3=0.9$, then the random mask similar, for example, to “$101100010$0” would be generated.) Having the mask generated, the decision is made as to about what genes have to be transmitted to the offspring’s chromosome. The index of the starting locus of the transferred genes, ${\chi }_4$, is generated randomly—in such a way that ${\chi }_4\in [1, n]$. Eventually, the empty loci (if any) are filled in randomly.

In the beginning, the sequence $r=(r(1), r(2), \dots , r(\xi ))$ of random integers $r(i)\in \{1, \dots ., n\}$ is generated. Then, we start with the pair $(r(1), r(2))$, and the elements $p(r(1))$, $p(r(2))$ are interchanged. Then, we exchange the elements $p(r(2))$, $p(r(3))$, and so on. This is repeated $\xi -1$ times, where $\xi$ is the value of the mutation rate defined by the algorithm’s user. The result of the mutation procedure is thus the solution $p^{~}$ satisfying the conditions: $p^{~}\in {\mathsf{\Pi }}_n$, $\delta (p, p^{~})=\xi$ (see Figure 3).

On the basis of the random pairwise interchanges, other modified mutation procedures can be developed [138].

In this case, the mutation process consists of two basic steps: (1) random pairwise interchanges; (2) shuffling the interchanged elements using a random key. A random key, $rk$, is a list of random indices of size $\xi$—$rk(1), rk(2), \dots , rk(\xi )$. The random key values simply determine which elements are again interchanged. The intention is to get a more “deeply” mutated solution and avoid returning to previously visited solutions.

In this mutation procedure, the position’s index, let’s say $k$, is randomly determined. Then, the element $e=p(k)$ is replaced by the following opposite value: $o=((p(k)+\frac{n}{2}-1) \mathrm{mod} n)+1$, where $\mathrm{mod}$ denotes the modulo operation. After this replacement, the solution element that was previously equal to $o$ must also be changed. After both changes, $p(k)$ becomes equal to $o$, $p(l)$—equal to $e$; $l$ indicates the element which was equal to $o$. The process is repeated $\frac{\xi }{2}$ times, where $\xi$ is the muation rate.

In this procedure, the indices of the pairs of elements to be interchanged are generated in such a way that the “distance” ($d$) between those indices is as large as possible. The following formula for generating the indices $k_1, k_2, \dots , k_{\xi }$ is used: $k_l=\lfloor ((d{q}_l+\varsigma -1) \mathrm{mod} n)+1\rfloor$, here $d=\frac{n}{\xi }$, $\varsigma$—(pseudo)random real number from the interval $[0, 1]$, $q_l=(q_{l-1} \mathrm{mod} n)+1$, $l=1,2,\dots , \xi$; the initial value $q_0$ is a random integer from the interval $[1,n]$.

This is similar to the random pairwise interchanges. The sequence of random real-coded values from the interval $[0, 1]$ is generated. The generated numbers along with their corresponding indices—known as smallest positive values—are sorted in the ascending order. These values, in particular, determine the elements to be interchanged.

The list of random indices is obtained by directly generating random integers from the interval $[1, n]$. The integers may duplicate each other. To avoid duplications, the integers are sorted according to the ascending order. Indices corresponding to the sorted numbers indicate the elements that are to be interchanged.

This mutation procedure consists of two combined mutation procedures. Initially, the list of indices of the pairs of elements to be interchanged is constructed (see Section 3.4.2.6). The selected elements are then changed using opposite values (see Section 3.4.2.3).

The basic principle of this mutation procedure is that the solution is disintegrated in some way, and then reconstructed. The mutation process consists of two steps: (1) disintegration of the solution, which is random; (2) reconstruction of the solution, which is greedy-deterministic. In the first step, $\xi$ elements are disregarded. In the second step, a greedy constructive algorithm is applied, which tries to find the best possible solution out of $\xi !$ available options. The value of $\xi$ in this case should be quite small to prevent large increase in the run time of the mutation procedure. This mutation procedure (and also other procedures described below) are no longer problem-independent as the problem domain-specific knowledge is taken into account.

This mutation procedure resembles the one described above. The difference is that a greedy randomized adaptive search procedure (GRASP) [70] is used in the partial solution reconstruction phase to obtain an improved solution.

In this case, quick procedure based on random pairwise interchanges is initially performed (see Section 3.4.2.1). Then, a set of randomly selected elements is formed. A local search is then performed using the constructed set, i.e., only transitions between solutions that improve the value of the objective function are accepted.

This mutation variant is similar to the previous randomized local search variant, except that the randomly constructed neighbourhood is fully explored in a systematic way. Again, only improving transitions between solutions are accepted.

Let $p^{(1)}=\underset{i=1, \dots , n-1, j=i+1, \dots , n, move\_acceptance\_criterio{n}^{(i,j)}=\mathrm{TRUE}}{\mathrm{argmin}}\{z(p^{i,j})\}$ and

$p^{(2)}=\underset{i=1, \dots , n-1, j=i+1, \dots , n, move\_acceptance\_criterio{n}^{(i,j)}=\mathrm{TRUE}}{\mathrm{argmin}}\{z(p^{i,j})|p^{i,j}\ne p^{(1)}\},$ where:$move\_acceptance\_criterio{n}^{(i,j)}=\{\begin{array}{ll}\mathrm{TRUE},\hfill & (tabu\_criterio{n}^{(i,j)}=\mathrm{FALSE}) \mathrm{or} (aspiration\_criterio{n}^{(i,j)}=\mathrm{TRUE})\hfill \\ \mathrm{FALSE},\hfill & \mathrm{otherwise}\hfill \end{array}$, $tabu\_criterio{n}^{(i,j)}=\{\begin{array}{ll}\mathrm{TRUE},\hfill & (t_{ij}\ge q) \mathrm{and} (\varsigma \ge \alpha )\hfill \\ \mathrm{FALSE},\hfill & \mathrm{otherwise}\hfill \end{array}$,

$aspiration\_criterio{n}^{(i,j)}=\{\begin{array}{ll}\mathrm{TRUE},\hfill & z(p)+\Delta (p^{i,j}, p)<z^{•}\hfill \\ \mathrm{FALSE},\hfill & \mathrm{otherwise}\hfill \end{array}$, $q$ denotes the current iteration number, $\varsigma$ is a (pseudo-)random number within the interval $[0, 1]$, $\alpha$ denotes the randomization coefficient, $z^{•}$ denotes the best so far value of the objective function. Then, in the randomized tabu search procedure, the best achieved solution (“winner solution”) $p^{(1)}$ is accepted with the probability $\gamma$, meanwhile the second solution $p^{(2)}$ is chosen with the probability $1-\gamma$ (note that, in the case of $\gamma =1$, we get the standard (deterministic) tabu search.) In our algorithm, we use $\gamma =0.2$. So, the central idea of the randomized tabu search is just this quasi-random mixing between the “winner solution” and “next to the winner solution” in the course of the tabu search process. Based on the extensive experimentation, we found out that this type of mutation is the most promising mutation procedure among all the procedures examined. The explanation would be that this type of mutation rather is more gentle, moderate and controlled than the other mutation procedures.

In the end, note that the computational complexity of all our mutation procedures is proportional to $O(\xi n^2)$. This is due to the fact that our mutation procedures recalculate the differences of the objective function (i.e., the values of the matrix $\mathsf{\Xi }$) approximately $\xi$ times (see Algorithm 5 (Note. The values of the matrix $\mathsf{\Xi }$ are recalculated using Equation (9).)). So, the smaller the value of $\xi$, the faster is the mutation procedure. Also, note that the difference matrix Ξ is (permanently) stored in a RAM (operating memory), so there is no need to calculate the differences of the objective function from scratch.