Two-Dimensional Quantum Genetic Algorithm: Application to Task Allocation Problem

This paper presents a Two-Dimensional Quantum Genetic Algorithm (2D-QGA), which is a new variety of QGA. This variety will allow the user to take the advantages of quantum computation while solving the problems which are suitable for two-dimensional (2D) representation or can be represented in tabular form. The performance of 2D-QGA is compared to two-dimensional GA (2D-GA), which is used to solve two-dimensional problems as well. The comparison study is performed by applying both the algorithm to the task allocation problem. The performance of 2D-QGA is better than 2D-GA while comparing execution time, convergence iteration, minimum cost generated, and population size.


Introduction
The Genetic algorithm (GA) [1] is a class of bio-inspired algorithms that can produce the optimal or near-optimal solution of complex optimization problems in a reasonable time. It was first proposed by Holland [2] inspired by Darwin's principle of survival of the fittest. The possible solution of an optimization problem is encoded in a chromosome which consists of an array of bits called genes. The individual chromosome is evaluated by a fitness function. A genetic population consists of a finite number of chromosomes. The chromosomes of the new population are generated by the application of genetic operations such as crossover, mutation, and reproduction on the present population. The new population optimizes the fitness function and thus provides an improved solution. The solution thus approaches the optimal solution over several generations. There exist many applications of GA viz. optimization [3,4], machine learning [5], neural networks [6], fuzzy logic controllers [7], identification [8], fault diagnosis [9], and financial market [10].
As quantum technology emerges as a powerful computational tool, there was an effort to combine quantum computation [11,12] with intelligent optimization algorithms. The first attempt to combine quantum mechanics principles and Genetic Algorithm was made by Narayanan and Moore to propose Quantum Genetic Algorithm (QGA) [13]. QGA is applicable to the category of problems which are solved using conventional genetic algorithm. Moreover, QGA speeds up the computation of genetic evolutionary process by exploiting the power of quantum computation. QGA has higher convergence rate, less execution time, less population size, and strong global search capability [14][15][16]. QGA has been proved to be efficient in solving various kind of problems such as combinatorial and functional optimization problems, engineering optimization problems, image processing and identification, and many others. A few example application can be found in [14,[17][18][19][20][21][22][23][24] and many more.
The GA and QGA discussed so far consider the chromosomes as a one-dimensional array. Obviously, these chromosomes cannot represent a possible solution for the problems which naturally have two-dimensional representation. Examples of such problems include Ising problem, Packing problem, Scheduling problem, Optimal topology in Multi-Agent 1. A novel 2D-QGA is proposed in this paper, which is a new algorithm in GA family.
Thus, the power of quantum computation can be used to solve problems having twodimensional representation. The quantum computation speeds up the computation and delivers optimal results in less time with a smaller population size.

New Qgate rotation technique for 2D chromosomes is proposed in this work. This
Qgate is the key factor to speed up the computation in 2D-QGA. 3. The proposed algorithm is implemented to multi-robot task allocation problem, which has the two-dimensional form and it is egarded as NP-hard. 4. A detailed analysis of the convergence time, iteration, cost, execution time of 2D-QGA is discussed. It also includes a detailed comparison with existing 2D-GA.
The rest of the paper is organized as follows. In Section 2, details of QGA is presented, which is the preliminary for two-dimensional QGA. In Section 3, 2D-QGA is introduced. An application of the algorithm is shown in Section 4. The comparison study is presented in Section 5. A brief conclusion is given in Section 6.

Quantum Genetic Algorithm (QGA)
In this section, the Quantum Genetic Algorithm is discussed, which is the preliminary for two-dimensional QGA. In quantum computation, 2 m independent states can be represented using m qubits. However, during the measurement of the qubits, a single state of the quantum state (i.e., |0 or |1 ) is obtained, which is similar to a conventional genetic algorithm, i.e., a chromosome's representation is defined as a string of m information units.

Qubit Representation
Qubit is the basic unit of information used in quantum computations. In a quantum system, the basic state is not deterministic; i.e., it does not have a fixed value. The basic state maybe |0 , |1 , or any complex value which is a linear combination or superposition of basis states. A qubit is represented in Equation (1) as where α and β are complex numbers which signify the magnitude of left and right vector respectively. α and β satisfy the condition given in Equation (2).
|α| 2 and |β| 2 provide the probabilities that the qubit can be found in the '0' state and '1' state, respectively. The pictorial representation of qubit is given in Figure 1. A chromosome is represented by a string of qubits (given in Equation (3)). The encoding length of the chromosome is n.

Quantum Gate Rotation (Qgate)
The operation for changing the state of the qubit is known as the quantum gate or Qgate. There exist several quantum gates. Examples of such gates are Not gate, controlled-NOT gate, rotation gate, Hadamard gate etc. One of the widely used gates is the rotation gate which is described as follows.
The rotation gate is operated on the present population to obtain the new one. It helps to maintain the diversity of the population, which is a key updating operation in quantum evolution algorithm. Rotation gate U(∆θ i ) is employed to update the probability amplitude of quantum states. The ith qubit (α i , β i ) is updated as follows. where where T is a rotation matrix and θ i = s(α i , β i )∆θ i is rotation angle. s(α i , β i ) is the sign of θ i and it determines the rotation direction. ∆θ i is the amount of rotation. The rotation sign and magnitude is determined in a look-up table which is shown in Table 1.
The rotation gate for qubit individuals in a polar plot is shown in Figure 2. The solution α i β i of current generation is rotated by an angle of ∆θ i anticlockwise to obtain possible best solution ᾱ ī β i . r i corresponds to the binary code of individual chromosome i. The binary code corresponding to the best individual is b i and f (.) denotes the fitness function to find the fitness value. α i β i > 0 signifies that they lie in the first or third quadrant. If α i β i < 0 then the individual i lies in the second or fourth quadrant. If the combination is 0-1, set the rotation angle to be 0.5π. If the combination is similar, i.e., 0-0 and 1-1, select a smaller rotation of angle 0.2π. If it is not possible to determine specific quadrant, then rotation is not preferred.

Initial Population Generation
The qubits present in the initial population have equal probability to be in the state of |0 and |1 . For such case, α = 1 , i.e., |q = 1 have string of such α and β. The encoding length of the chromosome is n and the population size is N. The algorithm for generation population is given in Algorithm 1.

Generate Binary String by Measuring Quantum Chromosome
The function for measuring the quantum chromosome measure_chrom() is shown in Algorithm 2. In this algorithm, a random number x ∈ (0, 1) is generated by MATLAB function rand() and it is compared to each α 2 j (denoted as Chrom(1, j) 2 ) of the chromosome.
Algorithm 2 Initial population of quantum chromosome measure_chrom()

end for
If x > α 2 ij the the (i, j)th element of a temporary matrix B is assigned as 0; otherwise assigned as 1. This matrix B is stacked in a 3D matrix binary.

QGA Algorithm
For better understanding, the QGA algorithm is shown in Algorithm 3. It includes the operations for QGA which are described so far.

Algorithm 3 QGA algorithm
Initialize QGA parameters Generate initial quantum population Q(t)

Two-Dimensional QGA (2D-QGA)
Two-dimensional QGA is a new algorithm which inherits the properties of QGA, and applicable to problems which can be represented by two-dimensional chromosome. The major works are done to present the idea of 2D quantum chromosome and its rotation technique. The description of the 2D quantum chromosome and Qgate rotation is given in the following sections.

Two-Dimensional Quantum Chromosome
In contrast to QGA, a two-dimensional quantum chromosome is a matrix. Each row of the matrix signifies a gene. A diagram of the quantum chromosome is shown in Figure 3. 'i = 1, 2, . . . , m' denotes the objects, and each of them is encoded by a string of qubits of length n. It can be mentioned that the quantum chromosomes encode the instants of all the objects together to represent a solution of a 2D problem. The number of rows is double the number of objects since each row is a string of qubits α and β. The quantum population consist of N two-dimensional quantum chromosomes Ch 1 , Ch 2 , . . . , Ch N as shown in Figure 4. The algorithm for the generation of the population is given in the following section.

Initial Population Generation
The initial population generation for 2D-QGA is slightly different from QGA. The method Init_Pop_2D() is shown in Algorithm 4.

end for
A common strategy is to initially populate the chromosome such that the qubits appear with equal probability i.e., α = β = 1 √ 2 and they change as the algorithm is executed.
Therefore, the initial values of qubits are assigned as 1 √ 2 = 0.7071. A sample quantum chromosome is shown in Figure 5. This is a chromosome generated using Algorithm 4.

Generation of Binary Population
The binary population is generated from quantum population using Algorithm 5. This algorithm is similar to the binary population generation for QGA. The modification is done to apply it for 2D chromosomes. An example of a binary chromosome generated is shown in Figure 6. It is the binary chromosome generated considering the quantum chromosome given in Figure 5.

Qgate Rotation for Two-Dimensional Chromosome
The rotation for 2D quantum chromosome is different because unlike the QGA (each chromosome dimension 2 × n) the chromosomes of 2D-QGA have the dimension of 2m × n. In this paper, two types of quantum gate rotation technique for two-dimensional quantum chromosome are presented. They are described in the following sections.
3.4.1. Qgate Rotation Type-I Each 2D quantum chromosome is a matrix, as shown in Figure 3. It can be noted that each row of this chromosome is similar to the chromosome of QGA (i.e.,1D array). In rotation type-I, the Qgate operation for 2D-QGA is performed for each row using the Qgate for QGA (shown in Table 1). The algorithm for implementing Qgate type-I operation for 2D quantum chromosome is shown in Algorithm 6.

Algorithm 6 Qgate rotation of 2D Quantum Chromosome
Perform checks and operation in Table 1 end for end for

Qgate Rotation Using N-dimensional Rotation Matrix (Qgate Type-II)
In this type, each column vector of the 2D chromosome is rotated. The length of the column vector is 2m. Therefore the rotation matrix should have the dimension 2m × 2m. Fortunately, there exists a well-defined method for such operation, which is known as 'Rodrigues' rotation formula'. The 2D quantum chromosomes are rotated using this method. The definition is given as follows.
Definition 1. If u and v are two orthonormal vectors, a matrix that rotates the span of u and v by angle θ is In every generation, each chromosome is rotated by an angle θ, i.e., all columns ( 2m ) of each 2D quantum chromosome are rotated by the same angle. Rotation angle at each generation is different, and it is selected in a random manner. The sign of the rotation is also random. The rotation process is shown in Algorithm 7.
The population size is N. The chromosomes are represented by Ch(:, :, i), i = 1, 2, . . . , N. The sign of the rotation i.e., s is selected in random manner. In the algorithm, x is assigned random number between 0 and 1 by MATLAB function rand(). if x > 0.5, then assign s = 1; otherwise assign s = −1. The value of θ is obtained by θ = s * rand() * (0.1π). Next, a random matrix M is generated. Then M is converted to orthonormal matrix M orth by MATLAB function orth(). Each rows of M are orthogonal. Two rows of M (for example, first and second row as shown in the algorithm) are selected as u and v. The rotation matrix R(θ, u, v) is calculated using values of θ, u, and v. Finally, the chromosomes are rotated using the rotation matrix. It can be mentioned that, for each chromosome the values of 's' and 'θ' are random. Therefore each chromosome is rotated with different rotation angle.
The flow diagram for implementing the steps of the proposed algorithm is shown in Figure 7.

Application to Task Allocation Problem
The problems which naturally have two-dimensional representation can be solved using 2D-QGA, which considers 2D quantum chromosome as a probable solution. It can be mentioned that the task assignment problem can be represented in two-dimension. In this paper, we will study the implementation of 2D-QGA to solve task assignment problem. It is important to note that the problem considered here is for demonstration purpose. The main focus of the work is to show the implementation of the algorithm to such a problem. The assumptions made for this problem are given as follows.
1. Each drone can perform one task at a time i.e., each drone is assigned to one task at a time. 2. At least one drone is required to finish each task 3. All drones should be assigned with a task 4. The task and drone positions are known The problem is formulated considering these assumptions and given in the following section. The allocation problem is given as follows.

Problem Formulation
x ij = 0, 1 Equations (6)-(8) defines a constrained optimization problem. The constraints in Equations (7) and (8) signifies the assumptions 1-3. The variable d ij is the distance between ith drone and jth task. x ij is a binary variable which takes a value of 1 if ith drone is assigned to jth task, i.e., x ij = 1, otherwise x ij = 0. This cost function is purely distancebased. The objective of the cost function is to minimize the overall distance between the drones and task positions i.e., assign tasks to the drones depending on their distance from them.

Simulation Study
The simulation study is performed considering ten drones (i.e., N D = 10; D = [D 1 D 2 . . . D N D ]) and four tasks (i.e., N T = 4; T = [T 1 T 2 T 3 T 4 ]). It can be mentioned that, this is an example problem. The user can increase the problem size as per the requirement. The task and drones positions are generated in a random manner in an area of length 1000 m and width 100 m using the MATLAB command 'randi'. The task allocation problem has been solved using both types of 2D-QGA, i.e., type-I and II. The simulation is performed on a PC with AMD Ryzen5 (2.3 GHz) processor and 8 Gb RAM. The results obtained using the proposed algorithm are discussed in the following sections.

Results Obtained Using 2D-QGA with Qgate Type-I
The results generated using 2D-QGA with Qgate type-I is shown here. The algorithm is executed for fifty generations. The cost (J) generated for all generations is shown in Figure 8. The algorithm has converged in fourteen generations to achieve minimum cost. The assignment matrix (optimal solution) is a 2D chromosome. This chromosome shows the optimal assignment of drones to the tasks, as shown in Figure 9. A particular task and the drones assigned to that task are marked with the same colour. The tasks T = [T 1 T 2 T 3 T 4 ] are shown in solid circles, and the drones are shown as empty circles. It can be noticed that each drone is assigned to one task. At least one drone is allocated to execute each task. Therefore the constraints are satisfied. The time consumed to execute each generation is shown in Figure 10. It can be observed that most of the generation consumed around 0.57 s. The Qgate type-I consumes around 0.11 s in most of the generations as shown in Figure 11.

Results Obtained Using 2D-QGA with Qgate Type-II
In this case, a different set of task and drone positions are generated. The results are generated using 2D-QGA with Qgate type-II. The cost for all generations is shown in Figure 12. The algorithm converged in 8 generations to produce minimum cost. The task allocation to the drones is shown in Figure 13. The tasks T 1 , T 2 , T 3 , T 4 and the drones assigned to the tasks are shown in the same colour as described in the previous case. Also, the tasks are shown in solid circles and drones in empty circles. Each drone is assigned to one task, and each task is allocated at least one drone. Therefore, the constraints are satisfied by the 2D-QGA type-II. The time consumed to execute each generation is shown in Figure 14. It can be observed that most of the generation consumed around 0.48 s. The time to execute Qgate type-II in each generation is shown in Figure 15. In most of the generations, Qgate type-II needs around 0.011-0.014 s for execution. The results generated using the proposed 2D-QGA algorithms (type-I and II) are discussed individually. However, the effect of quantum computation in 2D-QGA should be evaluated. The appropriate way should be to compare 2D-QGA with an algorithm which solves similar problems. It has been discussed in the introduction section that 2D-GA can solve the problems with two-dimensional representation. Therefore, the performance of 2D-QGA is compared to 2D-GA when they are used to solve the task allocation problem. The results obtained are discussed in the following section.

Comparison Study
The whole study is divided into three parts. In each part, two algorithms among 2D-GA, 2D-QGA type-I, and 2D-QGA type-II are compared. In the first part, the comparison between 2D-GA and 2D-QGA type-I is presented. In the second part, 2D-GA and 2D-QGA type-II are compared, and in the last part 2D-QGA, type-I and II are compared. The algorithms of each part are executed to solve the task allocation problem. It can be mentioned that the task and drone positions remain identical for each part. The comparison is performed by executing the pair of algorithms of each part for a finite number of iterations. In this study, the number of iterations considered to be 50. The general structure of the iteration is shown in Algorithm 8. In the algorithm, the iteration number N is set as 50, but the user can select a different number. In each iteration, the algorithms are allowed to evolve for fifty generations. The comparison between algorithms in each part is based on the points as follows. This measure shows how many times (or %) in a specific number of iterations one algorithm converges in fewer iterations compared to another one. 3. The percentage of iteration one algorithm of a pair takes less time compared to the other one. This is the time consumed by each algorithm of a pair to execute the maximum number of generation in one iteration. 4. The percentage of iteration one algorithm of a pair produces less cost compared to the other one.
These measures are essential to understand the importance of the features that 2D-QGA has. The results obtained for each part is discussed in the following sections.

Part 1: Comparison between 2D-GA and 2D-QGA Type-I
The comparison between 2D-GA and 2D-QGA type-I is given in this section. The population size of both 2D-GA and 2D-QGA type-I is considered to be 2000. The first comparison is about 'Average time consumed' by these algorithms. The comparison result is shown in Figure 16. It can be observed that 2D-GA consumed more time to execute each generation compared to 2D-QGA type-I. The operations involved in each generation for 2D-QGA type-I are designed by quantum computation. The next comparison is about the percentage of iteration the algorithms take fewer generations for convergence. The comparison is shown in Figure 17. It can be observed that 80% of iterations the 2D-QGA type-I takes fewer generations to converge.  Another important comparison is the total time taken by the algorithms to execute an equal number of generations. The result obtained is shown in Figure 18. It can be noticed that 2D-QGA type-I need lees execution time for all the iterations. The last and one of the most important comparison is the percentage of iterations the algorithms produce less cost. 2D-QGA type-I produces less cost for 100% of the iterations, as shown in Figure 19. The comparison is summarized in Table 2.   In this study, it is clear that 2D-QGA type-I is more efficient compared to 2D-GA. In the following section, the comparison between 2D-GA and 2D-QGA type-II is presented.

Part 2: Comparison between 2D-GA and 2D-QGA Type-II
The comparison between 2D-GA and 2D-QGA type-II is given in this section. The population size of both 2D-GA and 2D-QGA type-II are 2000. The average time consumed by 2D-GA and 2D-QGA type-II is shown in Figure 20. The time consumed to execute each generation by 2D-QGA type-II is less compared to 2D-GA. Figure 21 shows the percentage of iterations the algorithms converge with fewer generations. It is clear that 2D-QGA type-II converges with fewer generations for 60% of iterations.
The total time of execution of the same number of generations is compared in Figure 22. 2D-QGA type-II has consumed less execution time for 90% of iterations.   The comparison of percent of less cost generation is shown in Figure 23. It can be noticed that 2D-QGA type-II produces less cost for 90% of iterations. The comparison is summarized in Table 3.  The comparison between 2D-GA and 2D-QGA (type-I and II) is made in parts 1 and 2. Both types of 2D-QGA have performed much better compared to 2D-GA in terms of average execution time per generation, per cent of iterations each algorithm converges in fewer generations, consumes less execution time, and produces less cost. Moreover, the quantum computation helped the 2D-QGA to reduce the number of generations for convergence and overall execution time. Therefore the 2D-QGA speeds up the computation for the class of problems discussed in this paper.
It is clear that both types (I and II) of 2D-QGA are more efficient than 2D-GA. Also, there should be a similar comparison between them to identify the more efficient one. This comparison primarily reflects the influence of the Qgate operation involved in each type of 2D-QGA. In part 3, the comparison between 2D-QGA type-I and type-II is presented.

Part 3: Comparison between 2D-QGA Type-I and 2D-QGA Type-II
The comparison between 2D-QGA type-I and 2D-QGA type-II is given in this section. For a proper comparison, the population size of both 2D-QGA type-I and 2D-QGA type-II is considered to be 2000.
It can be observed that the average execution time per generation consumed by 2D-QGA type-II (around 0.47 s) is less than 2D-QGA type-I (around 0.55 s) as shown in Figure 24. The percentage of iteration each algorithm converges in fewer generations is shown in Figure 25. It can be observed that 78% of the iterations, 2D-QGA type-II converges in fewer generations compared to 2D-QGA type-I. In case of total execution time, 2D-QGA type-II consumes less for almost all of the iterations (97%) as shown in Figure 26.   Percent of iterations each algorithm produces less cost is shown in Figure 27. 2D-QGA type-II produces less cost for 80% of the iterations. The comparison is summarized in Table 4.  In addition to the comparison shown above, it is important to compare the execution time of 2D-QGA type-I and II for each generation in the same iteration. This comparison is shown in Figure 28. The execution time for each generation for type-I is more than type-II, i.e., type-II is faster. It can be observed that type-II takes around 0.1 s less time per generation compared to type-I and saves around 4-5 s over 50 generations. The saving of time increases if the number of generations is increased. The main reason behind type-II being faster is the time consumed by the Qgate process in type-II is much less than type-I.  The time consumed by Qgate of type-I and II is shown in Figure 29. The time consumed by Qgate type-I and II is around (average value) 0.12 s and 0.017 s respectively.
It is clear that 2D-QGA type-II has the advantage over type-I in terms of execution time per generation, total execution time, and convergence iterations. These advantages are important features of 2D-QGA type-II, which are useful for solving problems having two-dimensional representation. There are a few factors that can affect the performance of the proposed algorithm. The quality of optimal solution depends on the population size, the number of generations, formulation of appropriate cost function etc.

Conclusions
The simulation study showed that both types of 2D-QGA (type-I and II) had consumed less average execution time per generation compared to 2D-GA. This leads to less total execution time for 2D-QGA. Almost all the time (80-90%) the 2D-QGA produces less cost consuming fewer generations compared to 2D-GA. All of these improvements are achieved with population size much less than 2D-GA. The proposed Qgate type-I and II speeds up the computation. In particular, the type-II is faster between the two types. Therefore the 2D-QGA is a potential algorithm for solving problems with two-dimensional representation.

Conflicts of Interest:
The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.