{'fraction_non_alphanumeric': 0.03263282521829214, 'fraction_numerical': 0.01220956045582359, 'mean_word_length': 4.73641765704584, 'pattern_counts': {'":': 0, '<': 0, '<?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': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Cuckoo Quantum Evolutionary Algorithm for the Graph Coloring Problem

Based on the framework of the quantum-inspired evolutionary algorithm, a cuckoo quantum evolutionary algorithm (CQEA) is proposed for solving the graph coloring problem (GCP). To reduce iterations for the search of the chromatic number, the initial quantum population is generated by random initialization assisted by inheritance. Moreover, improvement of global exploration is achieved by incorporating the cuckoo search strategy, and a local search operation, as well as a perturbance strategy, is developed to enhance its performance on GCPs. Numerical results demonstrate that CQEA operates with strong exploration and exploitation abilities, and is competitive to the compared state-of-the-art heuristic algorithms.


Introduction
Graph Coloring Problem (GCP) is one of the most important combinatorial problems in the scientific and engineering fields [1]. Due to its NP-completeness, heuristic algorithms have been widely investigated to develop efficient algorithms for large-scale GCPs. State-of-the-art heuristic algorithms for GCPs include the cuckoo search algorithm [2][3][4][5], the ant colony algorithm [6][7], the genetic algorithm [8][9], the memetic algorithm [10][11] and the tabu search algorithm [12] and so on. Recently, the marriage in honey bees optimization [13] and the DNA algorithm [14] are also developed for GCP.
Most of heuristic algorithms employ population-based search schemes, which enhance their convergence performance, but has the side-effect of heavy complexity. The quantum-inspired evolutionary algorithm (QEA) [15] operates with a small population, and thus, is of less complexity compared to most of population-based heuristic algorithms. Unfortunately, the small population would inevitably reduce its ability of global exploration, and sometimes results in local convergence to problems with complicated landscapes.
Imitating the behavior of cuckoos, the cuckoo search algorithm (CSA) with a few parameters has been successfully applied in engineering applications [16][17][18]. Introducing the quantum representation to the framework of CSA, Djelloul et al. [2] proposed a quantum inspired cuckoo search algorithm for graph coloring. However, falling into an optimal local trap and high runtime are two of the disadvantages of this research [1].
Recalling that QEA has low complexity arising from its small population size, we propose a novel cuckoo quantum evolutionary algorithm (CQEA) for the problem of graph coloring, where the cuckoo search (CS) schema is introduced to improve global exploration of QEA. Meanwhile, the inherited initialization strategy and special search strategies are developed to improve its performance on GCPs.
The rest of this article is organized as follows. Section 2 presents the formulation of GCP, and Section 3 elaborates details of CQEA for GCP. Performance of CQEA is validated in Section 4 by numerical experiments, and finally we conclude the work in Section 5.

Problem Description
In this paper, the GCP refers to the problem of vertex coloring. Given an undirected graph ( , ) G V E , where V represents the set of vertices and E is the set of edges, the GCP is dedicated to minimize the amount of colors to paint adjacent vertices by inconsistent colors. If k different colors are sufficient to coloring adjacent vertices with different colors, ( , ) The GCP to get the chromatic number of G can be model as a bi-level combinatorial optimization problem: is a partition of V that represents an assignment of colors of vertices. When 1 uv δ  , incident vertices of edge ( , ) uv are assigned the consistent color, and ( , ) uv is named as a conflicting edge. Then, () fS,the total amount of conflicting edge of S , is the objective function that evaluates qualities of color assignments. To get the chromatic number and the corresponding color assignment S , one must iteratively search the graph to minimize () fS for successively increasing/decreasing k , which is tedious and time consuming.

The Cuckoo Quantum Evolutionary Algorithm for GCPs
In this section, we first introduce the representation of the solution and outline the framework of the cuckoo quantum evolutionary algorithm. Then, details of population initialization, search strategy, cuckoo search operation, and perturbance strategy are presented.

Representation of the Solution to the Graph Coloring Problem
For an undirected simple graph G of n vertices, a color assignment with k colors can be represented by a kn  binary matrix, where each column includes only one "1" bit [2]. Fig. 1 illustrates an example that a graph of five vertices is colored by three colors. For a graph included in Fig.1(a), the assignment of color illustrated in Fig.1(b) can be represented by the 35  binary matrix in Fig.1(c). When nodes 1 and 4 are colored by the first color (namely yellow), elements at the first row of columns 1 and 4 are set to be "1"; for nodes 2 and 3 painted by the second color (namely green), and node 5 given the third color (namely blue), we know the "1"-bits in columns 2, 3 and 5 are located at rows 2, 2 and 3, respectively. Since a binary matrix x representing an assignment of color is equivalent to a partition S of the vertex set V , its quality can be evaluated by the number of conflicting edges, that is,

Quantum Matrix in the Cuckoo Quantum Evolutionary Algorithm
In the proposed cuckoo quantum evolutionary algorithm (CQEA), individuals are not binary matrices of coloring assignments but quantum matrices that present probability models about distributions of colors. An assignment of k colors to n vertices can be modelled by a 2kn  quantum matrix α denotes the probability to assign the th i color to vertex j , and 2 , ij β denotes the probability not to assign the th i color to vertex j . By performing the quantum measurement operation [15] on q , a binary matrix x can be generated. Since there could be more than one "1" in a column of x , a repair operation is necessary to transfer the generated x to a solution of GCP.

Framework of the Cuckoo Quantum Evolutionary Algorithm
The CQEA for GCP consists of two nested iterations. The inner loop tries to minimize number of conflicting edges for given color number K , and the external one is performed to minimize color numbers K to get the chromatic number of the graph G . Termination criterions of loops are set as follows.
If iteration number of the external loop reaches a preset value or the chromatic number of G is obtained, termination-condition 1 is satisfied; it quits the inner loop if the maximum number of generations is reached or a color assignment with no conflicting edges is obtained. Framework of the CQEA is presented as follows.  Note that CQEA performs iterations on with its quantum population and the solutions to GCP are binary matrices. Thus, it generates binary matrices by implementing the quantum measurement operation on quantum matrices [15]. In the quantum measurement operation, an infeasible color assignment could be generated with uncolored nodes or nodes painted by more than one colors [2]. Then, a feasible color assignment is generated by the repair operation detailed as follows.
1. For a vertex with multiple colors, randomly choose one to color the vertex; 2. for a vertex that is not assigned with a color, randomly choose a color to paint the vertex.
After generation of the solution population, a binary matrix x that represents an assignment of color is evaluated by (2). While the solution archive is empty, the best solution with the least number of conflicting edges in () Pt is put into () B gen ; if is not empty, the best solution in ( ) ( ) P t B gen is kept in () B gen .

Initialization of color number
K .
Since the CQEA is implemented by successive iterations of the outer loop, promising initialization of K is helpful to reduce the number of iterations to get the chromatic number. At the beginning, it sets = ( ) 1 K G   according to the following theorem [19].
is the degree of G , and k is the chromatic number of G .

Initialization of the Quantum Population and the Solution Population.
There are two different strategies employed to initialize the quantum population. While 0 gen  , the quantum population is randomly initialized; when 0 gen  , it is generated by the inheritance initialization strategy.

Random Initialization.
At the beginning, the state expressed by each individual in the population is the equal probability superposition of all its possible states [2,15]. By setting ( ) 1 KG    , each individual in the initial quantum population is taken as 1  ( Once the quantum population (0) Q is generated, the solution population (0) P can be generated by perform quantum measurement on each individual of (0) Q .

Inheritance Initialization.
If CQEA has successfully colored G by K colors, it attempts to color G by 1 K  colors. To further improve searching efficiency of the upcoming iteration, the inheritance initialization is performed to generate an initial quantum population, which can be implemented by obtained best binary matrix A and the corresponding quantum matrix A Q obtained with K feasible colors. Detailed operations of the inheritance initialization are described as follows. n . Since row 0 n has the least number of "1", we try to delete the corresponding color to get the initial coloring of iteration g . Then, delete row 0 n of A and rows 00 2

Take the best binary matrix
In this way, we can get an updated quantum matrix A Q and the corresponding binary matrix A . Take them as individuals in (0) Q and (0) P , respectively. Other individuals of (0) Q are generated by random initialization. Performing quantum measurement on (0) Q , one can get the other members of (0) P .

Local Search in the Solution Space
Inspired by the mutation operator proposed in [2] and the simple decentralized graph coloring (SDGC) algorithm proposed in [20], we introduce a local search performed in the solutions space to improve local exploitation of CQEA. Given a set P of binary matrix, the local search is performed for every P Note that the local search applies different strategies when adjusting color indexes of vertices. While it is applied to the best solution set () B gen , it is assigned the smallest available color index to attempt to reduce the amount of color number K ; however, when searching neighborhoods of () Pt , a randomly selected color index is selected to try to improve global convergence by introducing randomness to the result.
The local search is repeated for Limit times before a solution without conflicting edges is generated.

The Cuckoo Search
Global exploration of CQEA is enhanced by introducing the cuckoo search (CS) to the quantum population [16][17][18].

The Perturbance Strategy
The quantum population () Qt and archive () B new are further updated by performing the perturbance strategy.

Experimental results
In order to evaluate the efficiency of the CQEA, it is implemented in MATLAB R2020a. The running environment is Intel(R) Core(TM) i7 CPU 860 @ 2.80GHz, system memory 8GB and Win7 operating system. Benchmark problems are selected from the graph coloring instance library2. Numerical results for 10 independent runs are collected in Table 1, where the obtained color number and iterations are recorded. Numerical results in Table 1 indicate that the CQEA can successfully get the found the known optimal solution of 13 instances. Besides 11 problems that are optimized by CQEA with 100% success rate, the worst results of queen6_6 and miles500 are one greater than the known optimal results.
Competitiveness of CQEA is demonstrated by comparing it with state-of-the-art algorithms [3,9,2]. Table 2 tabulates the results on color number these algorithms. It is shown that CQEA and DBG [9] perform better on "queen6_6" than the other two. For the other 12 instances, all four algorithms can find the best known solutions. Since both CQEA and DBG [9] can find the currently known optimal solutions for 13 instances in Table 2, we compare their stability by success rates to get the best known number of colors. Results in Table 3 show that CQEA outperforms DBG [9] in terms of stability in 4 instances (namely david, miles250, anna, fpsol2.i.1), however, performs a bit worse than DBG on instance queen6_6. For miles120 and miles500, CQEA and DBG have a success rate of 100%. We conclude that CQEA is competitive to DBG, and more efficient than MCOA and QICSA.

Conclusion
Considering that the quantum-inspired evolutionary algorithm can perform well with a small population, this paper develops a cuckoo quantum evolutionary algorithm (CQEA) to efficiently address the graph coloring problem. Enhancement of global exploration is achieved by introduction of general cuckoo search and specific strategies specially designed for the GCP, including an inherited initialization strategy, a local search strategy and a perturbance strategy. Numerical comparison based on benchmark problems demonstrates that the proposed CQEA can outperform most of the state-ofthe-art algorithms, and is competitive to the DBG algorithm. The results also indicate that development of quantum-based heuristic algorithms could be a feasible solution to efficient address of large-scale GCPs. To further improve the performance of CQEA on large-scale GCPs, our future work would focus on designing efficient representation of solution and reduction strategy of graph scale.