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

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

關(guān)鍵詞：圖論；組合優(yōu)化；NP難問題；圖著色問題；膜進化算法

中圖分類號：TP301.6" " " " " 文獻標(biāo)志碼：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

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

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

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

1 相關(guān)工作

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

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

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

1.2 圖著色問題的典型算法

圖著色問題是經(jīng)典的NP難問題，研究者已經(jīng)提出了許多的求解算法。近年來，性能優(yōu)秀的算法包括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]是一種基于概率學(xué)習(xí)的局部搜索算法，該算法包括3個階段：基于概率矩陣的起始著色階段、啟發(fā)式著色改進階段和基于學(xué)習(xí)的概率更新階段。該方法維護一個動態(tài)更新的概率矩陣，這個矩陣中的每個頂點會有一個指定屬于每個顏色組的概率。為了避免對稱解帶來的困難，使用了種群匹配過程來識別初始解和其改進解之間的關(guān)系，在優(yōu)化解的階段采用流行的禁忌搜索算法。

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

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

2 膜進化算法MEA_GCP

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

2.1 初始膜結(jié)構(gòu)

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

M：膜結(jié)構(gòu)，它包含4個膜個體和1個全局最優(yōu)膜mg。0代表皮膚膜，如圖1（a）所示。

mi （i =1，2，3，4）：代表一個膜個體，如圖1（b）所示。為了簡化，在圖中用阿拉伯?dāng)?shù)字來表示膜個體，一個膜個體構(gòu)成一個解決方案，它由K個子膜構(gòu)成。

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

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

， （1）

式中，

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

2.2 MEA_GCP算法

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

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

解決圖著色問題的膜進化算法的膜結(jié)構(gòu)變化如圖3所示。

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

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

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

1）膜結(jié)構(gòu)方面的區(qū)別。對于MEA_GCP，膜主要有4種結(jié)構(gòu)，膜種群為4個，在進化過程中，膜結(jié)構(gòu)根據(jù)需求在一直變化。對于MEA的膜結(jié)構(gòu)，給出了初始膜結(jié)構(gòu)，膜種群的大小是根據(jù)不同的問題設(shè)定。

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

3）適應(yīng)度函數(shù)的區(qū)別：MEA_GCP的適應(yīng)度函數(shù)是針對圖著色問題的一個具體衡量指標(biāo)。MEA中的適應(yīng)度函數(shù)也用來衡量一個膜的優(yōu)劣，沒有針對具體問題，是一個比較抽象的概念。

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

2.3 種群初始化

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

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

2.4 進化算子

結(jié)合一個頂點為{A，B，C，D，E，F(xiàn)，G，H，I，J }，色數(shù)為3的圖對進化算子做詳細(xì)的介紹。

2.4.1 復(fù)制算子

復(fù)制算子就是將一個膜復(fù)制成為2個膜，復(fù)制之后，這2個膜中的子膜也應(yīng)該是相同的，如圖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 分裂算子

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

2.4.4 溶解算子

在進化的過程中，當(dāng)一個膜表達(dá)的解決方案已經(jīng)遠(yuǎn)離最優(yōu)解時，需要將該膜內(nèi)的對象以及膜都刪除，這時就需要進行溶解。溶解算子的作用在于刪除膜以及膜內(nèi)的對象。

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

2.4.5 融合分裂算子

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

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

2.4.6 禁忌搜索算子

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

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

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

， （2）

式中：的區(qū)間是[0，9]；；（m）代表當(dāng)前膜的適應(yīng)度函數(shù)。在文中，也采用這樣的設(shè)置方式。在加入標(biāo)記膜之后，膜結(jié)構(gòu)會發(fā)生變化，具體見圖3（d）所示。

3 對比實驗

在這一節(jié)中，介紹所選用的基準(zhǔn)實例和實驗的環(huán)境，參數(shù)設(shè)置和對比實驗。為了驗證MEA_GCP的有效性，將和現(xiàn)在已知最好的和最新的算法作對比。

3.1 實例和實驗環(huán)境

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

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

為了體現(xiàn)實驗對比的客觀性，下面將對比實驗的實驗環(huán)境也列出來做參考。

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

2）TensCol[14]：是基于種群的權(quán)重概率學(xué)習(xí)。用的語言是Python，在GPU設(shè)備上運行，利用英偉達(dá)RTX2080Ti顯卡和12GB的內(nèi)存。

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

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

3.2 與其他算法的對比

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

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

從表1可以看出，MEA_GCP更具有優(yōu)勢，具體來說：

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

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在保證解的質(zhì)量相當(dāng)?shù)那闆r下有效降低了求解的時間，其中有58%的實例具有更少的求解時間。這主要源于進化機制不同與計算策略不同2個方面。

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

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

由于表1中各算法運行的實例數(shù)不同，表2給出了各算法獲得最優(yōu)解實例數(shù)的百分比。從表2可知，MEA_GCP獲得的最優(yōu)解比例遠(yuǎn)高于對比算法。

4 結(jié)束語

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

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

參考文獻

［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.

（編輯" 詹燕平）