解決圖著色問題的膜進化算法

摘要：圖著色問題是圖論中比較熱門的NP難問題之一。針對該問題，有許多啟發式求解算法，但都存在求解的質量不高，計算時間較長等問題。近些年提出的膜進化算法，在處理NP難問題中展現出了獨特的優勢。基于膜進化算法框架，提出了解決圖著色問題的膜進化算法，把圖著色問題和膜結合，設計了復制、融合、分裂、溶解、融合分裂、禁忌搜索6種膜進化算子。這些算子在演變的過程中使膜和膜結構發生進化，從而找到更優解，最后求得解決方案。在DIMACS的40個挑戰數據集上面進行了實驗，與3個最新的圖著色算法比較的結果表明：在保證解的質量的情況下，文中提出的膜進化算法能有效降低求解的時間，其中有58%的實例占優。

關鍵詞：圖論；組合優化；NP難問題；圖著色問題；膜進化算法

中圖分類號：TP301.6" " " " " 文獻標志碼：A" " " 文章編號：1000-582X（2023）07-023-13

A membrane evolutionary algorithm for solving graph coloring problem

GUO Ping， GUO Bin

（College of Computer Science， Chongqing University， Chongqing 400044， P. R. China）

Abstract： The graph coloring problem is one of the popular NP-hard problems in graph theory. Various heuristic algorithms have been proposed to solve this problems; however， they often suffer from poor quality and long computation time. In recent years， the membrane evolutionary algorithm has shown unique advantages in dealing with NP-hard problems. Based on the membrane evolutionary algorithm framework， this study proposed a membrane evolutionary algorithm to solve the graph coloring problem. Six membrane evolutionary operators， namely， copy， fusion， division， cytolysis， fusion-division， and tabucol were designed to facilitate the evolution of the membranes and membrane structures， leading to the discovery of more optimal solutions. Experiments were conducted on 40 challenging datasets from DIMACS， and the results were compared with three latest algorithms. The resalts show the proposed algorithm effectively reduces the computation time while maintaining the solution quality， outperforming the other algorithms in 58% of the instances.

Keywords： graph theory; combinatorial optimization; NP-hard; graph coloring problem; membrane evolutionary algorithm

圖著色問題是一個經典的組合優化問題，它的應用十分廣泛，例如：Wifi信號的分配問題[1]，車輛網絡中的資源分配問題[2]，資源約束問題中的調度[3]等。同時，圖著色問題和最大團問題、最大獨立集問題都存在關聯，所以研究圖著色問題在理論和實踐方面都有很大的意義。作為NP難問題，可行的求解圖著色問題的算法主要是啟發式算法。經典算法包括混合進化算法[4]及其變體[5?6]。近些年涌現了一些新的方法來解決圖著色問題，比如通過利用鄰接矩陣的對角線分配顏色的算法[7]。將組合優化問題轉換為泛函優化問題來解決[8]。隨著膜計算的興起，利用膜結構與遺傳算法的結合來解決圖著色問題[9]。針對量子計算設備的優缺點，改進量子優化算法來解決圖著色問題[10]。用2個策略改進的二元蜻蜓算法來解決圖著色問題[11]，離散自私群優化算法[12]，基于概率學習的局部搜索算法[13]，基于種群的梯度下降權重學習算法[14]等來解決圖著色問題。

仿生群智能算法用于求解NP難問題一直都是比較熱門的話題。膜計算是自然計算中一個快速發展的分支，近幾年提出的膜進化算法，已經用來解決了很多NP難問題。例如：郭平等利用膜進化算法來解決最小頂點覆蓋問題[15]、最大團問題[16]、TSP問題[17]、雙目標關鍵節點檢測問題[18]和容量受限聚類問題[19]。

針對圖著色問題，結合進化算子和局部搜索的混合進化算法一直是研究的熱點。這些算法中，由于引入了較多的個體，在管理多樣性時存在很大的挑戰。在文獻[5]中，介紹了2種算法來解決圖著色問題：一種是加了精心設計的多樣性管理方法，另一種沒有加多樣性管理辦法，前者的結果更優。膜進化算法是進化算法中的一種，它根據問題來設計膜對象，膜進化算子和膜結構。利用膜進化算法中并行進化機制和膜進化算子之間的協同機制，有可能獲得更高質量的候選解并且縮短求解的時間。所以文中將膜進化算法應用到解決圖著色問題中。實驗結果表明，這個方法能夠得到一個良好的結果。

1 相關工作

1.1 圖著色問題和膜進化算法

圖著色問題是給定一個無向圖G = （V， E），其中V是頂點集合，E是邊集合。給每個頂點分配一個顏色數，使得有邊相連的頂點擁有不同的顏色數。如果邊e連接的2個頂點v1和v2的顏色數相同，稱邊e為沖突邊，頂點v1和v2為沖突頂點。一個解決方案是給所有的頂點分配一個不大于K的顏色數并且無沖突。求得最小的整數K，稱之為色數。

膜進化算法是根據膜進化的過程提出的仿生智能算法[15]，膜進化算子抽象于膜進化過程中的行為，只要能在細胞活動中找到依據的行為都可以抽象成膜進化算子。膜進化算法最主要的特點是這些算子可以單獨使用或者根據問題的需求把不同的算子進行組合使用。在文獻[15]中，針對最小頂點覆蓋問題，設計出融合、分裂、選擇、溶解算子來解決。在文獻[17]中，設計了針對旅行商問題的膜進化算子，并將選擇和溶解算子進行組合使用。文獻[15]給出了膜進化算法的基本框架。

1.2 圖著色問題的典型算法

圖著色問題是經典的NP難問題，研究者已經提出了許多的求解算法。近年來，性能優秀的算法包括PLSCOL（improving probability learning based local search for graph coloring）、TensCol（population-based gradient descent weight learning for graph coloring problems）和HEAD（variations on memetic algorithms for graph coloring problems）。

PLSCOL[13]是一種基于概率學習的局部搜索算法，該算法包括3個階段：基于概率矩陣的起始著色階段、啟發式著色改進階段和基于學習的概率更新階段。該方法維護一個動態更新的概率矩陣，這個矩陣中的每個頂點會有一個指定屬于每個顏色組的概率。為了避免對稱解帶來的困難，使用了種群匹配過程來識別初始解和其改進解之間的關系，在優化解的階段采用流行的禁忌搜索算法。

TensCol[14]是一種基于種群的權重概率學習算法，它把求解搜索表述為一個連續權值張量優化過程。首先，使用權重矩陣表示候選顏色，對矩陣中每個元素對應于一個頂點接受特定顏色的學習傾向，然后使用梯度下降的方法，設計最小化全局損失函數引導梯度下降來改進解決方案。

HEAD[5]是一種混合進化算法，該算法結合交叉算子和禁忌搜索算法。禁忌搜索算法是一種局部搜索算法，交叉算子提供了一種良好的全局搜索能力。先利用交叉算子生成2個不同的解，再用禁忌搜索來提升這2個解的質量，最后用這2個提升的解去替換原來的2個解。如此往復，解的質量得到不斷提升，并在固定的進化代數引入精英來管理種群的多樣性。

2 膜進化算法MEA_GCP

根據膜進化算法框架，討論提出的解決圖著色問題的膜進化算法MEA_GCP（membrane evolutionary algorithm for solving graph coloring problem）。

2.1 初始膜結構

為了方便描述，采用以下符號。

M：膜結構，它包含4個膜個體和1個全局最優膜mg。0代表皮膚膜，如圖1（a）所示。

mi （i =1，2，3，4）：代表一個膜個體，如圖1（b）所示。為了簡化，在圖中用阿拉伯數字來表示膜個體，一個膜個體構成一個解決方案，它由K個子膜構成。

Vi （1≤i≤K）：代表一個子膜，存放一個解決方案中顏色為i的所有頂點。每個頂點只能有一種顏色，所以ViVj =（i≠j），V = V1V2…VK。 Vi中的對象（物質）表示為，i表示膜i，j表示顏色j。特別，當只在一個膜中討論問題時，省略對象的下標。

基于圖1（b）所示的膜結構，采用式（1）來評價膜的優劣，稱為適應度函數。顯然，只有當fit（m） = 0時表示該膜是一個解決方案，fit（m） ≠ 0時代表該膜是一個候選解決方案。當fit（m1）＜fit（m2）代表m1的適應度函數更小，即膜m1比m2更好。

， （1）

式中，

圖2給出了一個例子。圖2（a）為圖G，頂點為{A，B，C，D，E}，色數K為3。圖2（b）是一個膜結構。膜1、2、3、4分別為圖G的候選解決方案。m1中包含有V1、V2、V3 三個子膜，頂點的顏色分別為：A和E為顏色1，B和D為顏色2，C為顏色3。按照式（1），可以求出m1的適應度函數值為2，m2的適應度函數值為1。所以m2比m1要好。mg的適應度函數為0，它是圖G的一個解決方案。

2.2 MEA_GCP算法

基于圖1（a）的初始膜結構，解決圖著色問題的膜進化算法見算法1，其膜進化算子包括：復制、融合、分裂、溶解、融合分裂和禁忌搜索算子（這些算子將在2.4節中詳細討論）。在算法1中，輸入的參數為圖G，色數K，禁忌搜索的迭代次數MaxIter，種群的大小P（文中設計的融合分裂算子需要兩兩組合，種群的數量應為偶數。在進化過程中，膜個體進行并行優化，需要多核處理器，結合實驗環境，最終選定為4個），maxgen為最大進化代數。

在算法1中，根據圖1（a）的初始膜結構初始化膜種群，并初始化參數（第1行到2行）。第3行是算法的結束條件，沒有達到最大的進化代數并且沒有找到解就一直執行第4到13行。融合分裂操作需要2個膜，所以將4個膜隨機分為2組（第4行）。因為要對每組膜進行2次融合分裂操作，所以要先將每組膜進行1次復制操作（第5行）。2組膜分別進行2次融合分裂操作之后會形成4個膜（第6到7行）。把這4個膜經過禁忌搜索進行局部提升之后，再將這4個膜全部替換原來的4個膜（第9行），同時更新全局最優的膜mg（第10到11行）。再把進化代數加1，這就完成了一次完整的進化過程。進化結束時，輸出最優膜mg。

解決圖著色問題的膜進化算法的膜結構變化如圖3所示。

由圖3可以看出，在解決圖著色問題中，膜結構在進化的過程中會變化。初始膜結構為圖3（a），把4個膜隨機分為2組之后，膜結構變成圖3（b）所示。再把每1組的膜經過復制算子復制1次，得到圖3（c）的膜結構。在禁忌搜索的過程中，膜結構如圖3（d）所示。

在種群的一代進化中，膜結構的變化過程可以總結為：圖3（a）→圖3（b）→圖3（c）→圖3（a）→圖3（d）→圖3（a）。

膜進化框架和MEA_GCP相比較，它們有3個主要區別。

1）膜結構方面的區別。對于MEA_GCP，膜主要有4種結構，膜種群為4個，在進化過程中，膜結構根據需求在一直變化。對于MEA的膜結構，給出了初始膜結構，膜種群的大小是根據不同的問題設定。

2）膜進化算子的區別：MEA_GCP的膜進化算子，分別為：復制算子、融合算子、分裂算子、溶解算子、融合分裂算子、禁忌搜索算子。MEA的進化算子有：融合算子、分裂算子、選擇算子、溶解算子。

3）適應度函數的區別：MEA_GCP的適應度函數是針對圖著色問題的一個具體衡量指標。MEA中的適應度函數也用來衡量一個膜的優劣，沒有針對具體問題，是一個比較抽象的概念。

膜進化算法是一個基礎的框架，解決圖著色問題的膜進化算法是在它的基礎上針對圖著色問題設計的算法。針對不同的問題，也要在該框架上面進行設計。

2.3 種群初始化

在膜種群的初始化過程中，每個膜的初始化原則是保證在較短的時間得到一個適應度函數比較小的初始解。算法2給出了膜種群初始化的偽代碼。

Random_init（算法3）完成種群的隨機初始化。先根據色數創建K個空的子膜（1到4行）。對于每個頂點隨機分配一個1到K的顏色數（第6行），再對應顏色數把頂點分配到不同的子膜中，形成一個膜個體（第7到10行）。

2.4 進化算子

結合一個頂點為{A，B，C，D，E，F，G，H，I，J }，色數為3的圖對進化算子做詳細的介紹。

2.4.1 復制算子

復制算子就是將一個膜復制成為2個膜，復制之后，這2個膜中的子膜也應該是相同的，如圖4所示。

2.4.2 融合算子

融合算子有3種操作：1）將2個或者2個以上的膜合并形成一個膜的過程。如圖5（a），將2個膜里面的子膜合并在同一個膜中（為了對融合后的子膜方便描述，把融合后的子膜記為Vij，其中i代表原膜i，j代表子膜j。如V21代表原膜2中的子膜1，V12代表原膜1中的子膜2）。2）把一個膜融合到皮膚膜中，如圖5（b）所示。3）子膜和膜的融合，如圖5（c）所示。

2.4.3 分裂算子

分裂算子是把膜中頂點按照一定的規則分裂在不同膜中。分裂過程中，子膜中頂點的顏色不改變，如圖6所示。

2.4.4 溶解算子

在進化的過程中，當一個膜表達的解決方案已經遠離最優解時，需要將該膜內的對象以及膜都刪除，這時就需要進行溶解。溶解算子的作用在于刪除膜以及膜內的對象。

在MEA_GCP中，不單獨使用溶解算子，而是將它與其他算子一起使用。例如，在融合分裂算子結束后，會得到2個膜，其中1個膜是比較差的，所以要將這個膜溶解掉，就用到溶解算子。

2.4.5 融合分裂算子

在膜進化算法中，算子不僅可以單獨使用，而且可以組合使用。在算法4中，就是將融合與分裂算子結合起來使用實現融合分裂功能。

在圖7中，給出了融合分裂算子的具體分裂過程，這是解決圖著色問題的關鍵。算法4中，第1行將2個膜融合為1個膜mt。第4到5行，算法會間隔選擇頂點最多的子膜融合到m1'中。如圖7（a），首先，選擇子膜V12（D，E，F，G）融合到m1'中，再把mt中與子膜V12相同的頂點分裂到m2'中；然后，選擇子膜V23（B，H，J）融合到m1'中，接著，把mt中與子膜V23相同的頂點分裂到m2'中，如圖7（b）。直到循環結束后，把還沒有分裂的頂點分裂到m1'和 m2'中，如圖7（d），把V13分裂到m1'的V3中，把V21分裂到m2'的V1中。最后，把m2'溶解，就得到了m1'。

2.4.6 禁忌搜索算子

如果單獨只用進化算法去解決圖著色問題，其結果比較差。比較有效的做法是把局部搜索算法與進化算法相結合組成混合進化算法：進化算法的算子用來提供種群的多樣性，提供一個更廣的搜索空間；局部搜索用來做局部提升，能在一個基礎上找到一個更好的解。文中用到的局部搜索算法是禁忌搜索。

禁忌搜索[20]自1987年提出以來得到了廣泛的應用，算法5給出了文中的禁忌搜索算子的具體步驟。文中提出的禁忌搜索引入了標記膜mc，標記膜的膜結構如圖8（a）所示，膜內對象為頂點，頂點右上角的數字代表頂點移動到的子膜的標記，右下角的t代表在t次迭代內不能做同樣的移動操作。圖G，膜m和最大迭代的次數MaxIter作為算法的輸入。迭代的過程中首先將輸入的膜m作為當前最優的膜，并重置迭代次數，設置一個空的標記膜，把膜內頂點的右上下標設置為0（第1到2行）。第3行是終止條件。在第4行，嘗試把頂點v從Vi移動到Vj使適應度函數變小。如果標記膜中該v的t為0，則代表該移動是被允許的（第5行）。在膜m中，就執行該移動。在標記膜mc中，把這個移動記錄下來（第6行），并且更新最優膜（第7行）。如果該移動不被允許，那就將該移動的禁忌次數減1（第9行）。在第12行，達到迭代次數后，輸出最優的膜。

在禁忌搜索當中，參數t叫禁忌期。它的大小直接影響了對鄰域的搜索效果。禁忌期較長可以探索大的搜索空間，但是如果設置得太長則不能起到禁忌作用；如果禁忌期較短，搜索將被限制在一個較小范圍，不易獲得更優的解。文獻[21]中采用式（2）以半隨機的方式動態生成禁忌期有很強的魯棒性。

， （2）

式中：的區間是[0，9]；；（m）代表當前膜的適應度函數。在文中，也采用這樣的設置方式。在加入標記膜之后，膜結構會發生變化，具體見圖3（d）所示。

3 對比實驗

在這一節中，介紹所選用的基準實例和實驗的環境，參數設置和對比實驗。為了驗證MEA_GCP的有效性，將和現在已知最好的和最新的算法作對比。

3.1 實例和實驗環境

本次選用的基準實例主要是第二次DIMACS競賽中的40個困難實例，這些實例在近年的研究中被廣泛使用。

MEA_GCP算法的實現語言是C++，實驗環境是windows10，處理器是：AMD Ryzen5 4600H六核，主頻3GHz。

為了體現實驗對比的客觀性，下面將對比實驗的實驗環境也列出來做參考。

1）PLSCOL[13]：基于概率學習的局部搜索算法，用的語言是C++，在Intel Xeon E5-2760 2.7 GHz的處理器上實現，結束時間為5 h。

2）TensCol[14]：是基于種群的權重概率學習。用的語言是Python，在GPU設備上運行，利用英偉達RTX2080Ti顯卡和12GB的內存。

3）HEAD[5]：最新的混合進化算法。用的語言是C++，并行運行在4核3.1GHz的Intel Xeon處理器。

在文中的實驗對比情況中，比較2個算法哪個較優是采用先比較色數，再比較成功率，再比較求解時間的順序評價。因為更新一個圖的色數是非常困難的，所以先比較色數，其次是成功率，成功率代表著該算法是否比較穩定，魯棒性是否比較強。同時，求解時間的長短也是比較重要的一個指標。

3.2 與其他算法的對比

關于圖著色問題的色數，已經很多年沒有出現過更新，說明想要取得更好的結果的難度是巨大的。文中選擇與HEAD[5]、PLSCOL[13]和TensCol[14]算法進行對比，它們是近幾年來求解成功率和求解效率都是優秀的算法。需要說明的是，對于對比算法，筆者沒有采用文中實現的這些算法的結果，而是直接使用了相關文獻中的結果。原因在于筆者實現這些算法所獲得的結果中的大多數沒有參考文獻中的結果優秀。

表1是MEA_GCP和3個算法的對比結果，其中最好的結果用粗體表示，‘-’表示在相應的文獻中沒有給出對應實例的計算結果。第1列為實例的名稱，第2列K*代表已知的最小色數，后面4大列分別為4種算法的結果。kbest代表用該算法出的最優色數，SR代表成功率（成功次數/總共運行的次數），t（s）為算法的平均時間，單位為s。

從表1可以看出，MEA_GCP更具有優勢，具體來說：

1）在最優解方面，PLSCOL在34個實例中的獲得了1個比其他3個算法更好的解，TensCol在34個實例中獲得了2個比其他3個算法更好的解，HEAD在32個實例中獲得了4個比其他3個算法更好的解，MEA_GCP在40個實例中有31個實例與其他3個算法的最優解相同。

2）在求解成功率方面，PLSCOL在34個實例中的獲得了1個比其他3個算法高的成功率，TensCol在34個實例中獲得了4個比其他3個算法更高的成功率，HEAD在32個實例中獲得了1個比其他3個算法更高的成功率，MEA_GCP的40個實例中有3個實例比其他3個算法的成功率高。

3）在時間消耗方面，PLSCOL在34個實例中的獲得了1個比其他3個算法更少的時間，TensCol在34個實例中獲得了2個比其他3個算法更少的時間，HEAD在32個實例中獲得了2個比其他3個算法更少的時間，MEA_GCP的40個實例中有33個實例比其他3個算法的時間少。

總體來說，MEA_GCP在保證解的質量相當的情況下有效降低了求解的時間，其中有58%的實例具有更少的求解時間。這主要源于進化機制不同與計算策略不同2個方面。

1）進化機制不同。MEA_GCP中把4個膜分成兩兩一組，然后分別對每個組的膜進行融合、分裂操作。經歷融合、分裂之后得到的膜通過禁忌搜索算子并行提升之后再去替換原來的4個膜，再進行分組操作，繼續進化。HEAD利用交叉算子和禁忌搜索的結合，整個種群是2個解在并行進化，2個解利用交叉算子生成不同的個體，再用禁忌搜索進行提升后替換原來的2個解。PLSCOL是改進的禁忌搜索算法，整個進化過程主要是圍繞著1個解進行計算，解的改進過程可以概括為：初始解→局部最優解→全局最優解。TensCol是基于種群的梯度下降權值學習方法，種群的大小為200，把圖著色問題轉化為連續權值張量優化問題，建立每個個體和種群的關系，每個個體又在并行進化，一次進化結束，所有的解會通過全局損失函數整合最好的解。對于HEAD、MEA_GCP的種群個體數較多，在進行融合分裂時，把2個膜分為兩兩一組，每次都會有3種不同的選擇，而HEAD只有2個個體，沒有不同的選擇，所以MEA_GCP個體的多樣性會更好，求解的效率更高。PLSCOL求解只針對1個個體進行改進，本質是一種局部搜索算法。MEA_GCP有4個個體，個體之間會互換信息，它的全局搜索能力更好，所以用的時間較少。TensCol的種群大小為200，這200個個體并行經歷一次進化后，都會去計算各個解之間的關系，然后整合關系去尋找最優解。而MEA_GCP只需要比較每個膜的適應度函數就能判斷哪個膜更優，所以MEA_GCP有更高的效率。

2）計算策略不同。HEAD是混合進化算法，其中采用交叉算子來提供全局搜索能力。MEA_GCP是膜進化算法，其中的融合分裂算子在設計時用到了交叉算子的貪心策略，但是融合分裂算子的最后一步做了改進。交叉算子在最后一步是采用隨機著色的方式，這會使解產生較多的沖突。而融合分裂算子在最后分裂時，頂點的顏色和原來的膜相同，比隨機著色的產生的沖突要少。PLSCOL算法主要是圍繞著一個概率矩陣對禁忌搜索算法進行改進來解決圖著色問題。概率矩陣貫穿著色的整個過程，從起始著色到著色改進，再到概率更新，還需要計算解之間的關系。這些步驟都需要大量的時間，并且計算時間和圖的規模成正比。再加上禁忌搜索的時間，PLSCOL的計算時間會更長。對于MEA_GCP，計算時間的99%都是由禁忌搜索產生，融合分裂所花費的時間非常少。所以MEA_GCP在大規模實例上的計算時間占較大優勢。對于TensCol算法，它主要是把圖著色問題轉化為了連續權值張量的優化問題，該算法是解決圖著色問題的一個通用框架。不僅僅針對文中提出的圖著色問題，還可以解決ECP（equitable graph coloring problem）問題，它是在GCP問題上加上每種顏色的頂點個數相差不大于1的條件。1個方法解決2個問題，在計算全局損失函數時，針對GCP，會進行一些不必要的計算，所以消耗了大量的時間。

由于表1中各算法運行的實例數不同，表2給出了各算法獲得最優解實例數的百分比。從表2可知，MEA_GCP獲得的最優解比例遠高于對比算法。

4 結束語

膜進化算法是受膜進化過程啟發的仿生智能算法，在膜進化演變的過程中尋找解。依據膜進化算法的框架，結合圖著色問題，文中提出了MEA_GCP算法，設計并實現了該算法的復制、融合、分裂、融合分裂、溶解、禁忌搜索算子，并在DIMACS挑戰數據集上與目前優秀的圖著色問題求解算法進行了對比實驗。MEA_GCP在78%的實例上與其他3個算法取得相同的結果，在70%的實例上獲得了100%的求解成功率，在58%的實例上具有更少的求解時間。由此，使用膜進化算法解決圖著色問題是有效的和可行的。

文中在設計MEA_GCP的進化算子的時候主要借鑒了交叉算子的設計思路。進一步的研究可以從以下兩方面展開：更好地結合禁忌搜索與膜對象進化使對象更新效率更高；簡化膜內對象的表示和引入新的進化策略（例如對象貢獻度）使進化算法具有通用性。

參考文獻

［1］" Orden D， Marsa-Maestre I， Gimenez-Guzman J M， et al. Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction[J]. Discrete Applied Mathematics， 2019， 263： 234-243.

［2］" Gao L， Hou Y， Tao X， et al. A graph-based resource sharing and admission control for vehicular networks[C]// 2019 IEEE Wireless Communications and Networking Conference Workshop （WCNCW）. IEEE， 2019， 1-6.

［3］" Hsiao H C， Chen C W， Wang J， et al. Architecture-aware memory access scheduling for high-throughput cascaded classifiers[C]// 2019 IEEE 22nd International Symposium on Design and Diagnostics of Electronic Circuits amp; Systems （DDECS）. IEEE， 2019：1-4.

［4］" Galinier P， Hao J K. Hybrid evolutionary algorithms for graph coloring[J]. Journal of Combinatorial Optimization， 1999， 3（4）： 379-397.

［5］" Moalic L， Gondran A. Variations on memetic algorithms for graph coloring problems[J]. Journal of Heuristics， 2018， 24（1）： 1-24.

［6］" Lü Z， Hao J K. A memetic algorithm for graph coloring[J]. European Journal of Operational Research， 2010， 203（1）：241-250.

［7］" Negi C， Shukla A N. An approach for solving the graph coloring problem using adjacency matrix[C]// 2019 8th International Conference System Modeling and Advancement in Research Trends （SMART）. IEEE， 2019： 10-13.

［8］" Crnki? A， Povh J， Ja?imovi? V， et al. Collective dynamics of phase-repulsive oscillators solves graph coloring problem[J]. Chaos， 2020， 30（3）： 033128.

［9］" Andreu-Guzmán J A， Valencia-Cabrera L. A novel solution for GCP based on an OLMS membrane algorithm with dynamic operators[J]. Journal of Membrane Computing， 2020， 2（1）： 1-13.

［10］" Tabi Z， El-Safty K H， Kallus Z， et al. Quantum optimization for the graph coloring problem with space-efficient embedding[C]// 2020 IEEE International Conference on Quantum Computing and Engineering （QCE）. IEEE， 2020： 56-62.

［11］" Baiche K， Meraihi Y， Hina M D， et al. Solving graph coloring problem using an enhanced binary dragonfly algorithm[J]. International journal of swarm intelligence research， 2019， 10（3）： 23-45.

［12］" Zhao R， Wang Y， Liu C， et al. Discrete selfish herd optimizer for solving graph coloring problem[J]. Applied Intelligence， 2020， 50（5）： 1633-1656.

［13］" Zhou Y， Duval B， Hao J K. Improving probability learning based local search for graph coloring[J]. Applied Soft Computing， 2018， 65： 542-553.

［14］" Goudet O， Duval B， Hao J K. Population-based gradient descent weight learning for graph coloring problems[J]. Knowledge-Based Systems， 2021， 212：106581.

［15］" Guo P， Quan C， Chen H. MEAMVC： A Membrane evolutionary algorithm for solving minimum vertex cover problem[J]. IEEE Access， 2019， 7： 60774-60784.

［16］" Guo P， Wang X， Zeng Y， et al. MEAMCP： A membrane evolutionary algorithm for solving maximum clique problem[J]. IEEE Access， 2019， 7： 108360-108370.

［17］" Guo P， Hou M， Ye L. MEATSP： a membrane evolutionary algorithm for solving TSP[J]. IEEE Access， 2020， 8：199081-199096.

［18］" Xu Y C， Guo P. MEA-CNDP： a membrane evolutionary algorithm for solving biobjective critical node detection problem[J]. Computational Intelligence and Neuroscience， 2021， 2021： 1-20.

［19］" Liu Y Y， Guo P， Zeng Y. MEACCP： a membrane evolutionary algorithm for capacitated clustering problem[J]. Information Sciences， 2022， 591： 319-343.

［20］" Hertz A， Werra D. Using tabu search techniques for graph coloring[J]. Computing， 1987， 39（4）： 345-351.

［21］" Fleurent C， Ferland J A. Genetic and hybrid algorithms for graph coloring[J]. Annals of Operations Research， 1996， 63（3）：437-461.

（編輯" 詹燕平）