使用遺傳算法解決圖着色問題

圖着色

問題描述

在圖論中，圖是對象的結構化集合，用于表示對象對之間的關系。對象在圖中表示為頂點（或節點），而一對對象之間的關系使用邊表示：

圖是非常有用的對象，因為它們可以用于表示大量的現實生活中的結構、模式和關系，例如社交網絡，電網布局，網站結構，計算機網絡，原子結構等等。

圖着色任務可以簡單概括為：為圖中的每個節點配置設定一種顔色，并保證相連接配接的節點對不會使用相同的顔色，下圖顯示了争取着色的圖示例：

在圖着色問題中，我們通常希望使用盡可能少的顔色。例如，在上圖中，可以使用三種顔色正确地對所示圖進行着色。但是不可能僅使用兩種顔色對其進行正确着色。從圖論的角度而言，這意味着該圖的色數（chromatic number）為3。

應用

許多現實生活中的問題都可以轉化為圖表示，并可以抽象為圖着色問題。例如，為學生安排課程或為員工安排班次可以轉換為圖，其中相鄰節點表示導緻沖突的班級或班次。導緻沖突的原因可能是同時上課的班級或連續的班次。由于此沖突，将同一個人配置設定給兩個班級（或兩個班次）将導緻時間表無效。如果每種顔色代表不同的人，則将不同的顔色配置設定給相鄰節點将解決沖突。同樣，N皇後問題可以表示為圖着色問題，其中圖中的每個節點都代表棋盤上的正方形，而每對處于同一行、列或對角線的棋子通過邊連接配接。其他相關應用包括對無線電台的頻率配置設定，交通信号燈定時等等。

解的表示形式

可以使用整數清單表示圖着色問題的解，其中每個整數代表一種顔色，而清單的每個元素都與圖的節點之一比對。

假設圖中有10個節點，是以可以為每個節點配置設定0到9之間的索引。然後，使用10個元素的清單表示該圖的節點顔色。例如：

(0, 2, 1, 3, 1, 2, 0, 3, 3, 0)

1. 使用了四種顔色，分别由整數0、1、2、3表示。

2. 第一、第七和第十個節點用第一種顔色着色。

3. 第三和第五節點用第二種顔色着色。

4. 第二和第六節點用第三種顔色着色。

5. 第四、第八和第九節點用第四顔色着色。

為了評估解決方案，需要周遊每對相連接配接的節點，并檢查它們是否共享相同的顔色。将着色問題轉換為違反顔色限制的問題，目标是将違反次數最小化，直到其為零，以實作圖的正确着色。

同時還試圖将使用的顔色數量減到最少。如果已知最小顔色數，我們可以使用與已知顔色數一樣多的整數值。但是，多數情況下我們并沒有此先驗知識，一種解決方法是首先對使用的顔色數量進行估計。如果使用此數字找到合适的解決方案，則可以減少該數字，然後重試。如果未找到解決方案，則可以增加數量，然後重試直到找到能夠找到解決方案的最小數量。可以通過使用軟限制和硬限制來更快找到最小值。

圖着色問題中的限制條件

首先定義硬限制和軟限制：

1. 硬限制：為獲得有效解而必須遵守的限制

2. 軟限制：為獲得最佳解而盡可能遵守的限制

在圖着色問題中，顔色配置設定要求（其中兩個相連接配接的節點不能具有相同顔色）是一個硬限制。必須将違反此限制的次數最小化為零，以獲得有效的解。

将使用的顔色數量最小化作為一種軟限制。我們希望最小化此數字，但不以違反硬限制為代價。

以高于估計值的顔色數開始算法流程，并使色數最小化，直到——理想情況下——達到實際的最小顔色數。通過建立成本函數來實作此方法，其中硬限制違反的成本大于違反軟限制的成本。将總成本用作要最小化的适應度函數。

利用python實作問題建立

為了封裝圖形着色問題，建立名為 GraphColoringProblem 的 Python 類。

為了實作該類，需要利用 NetworkX 庫，該庫可以進行圖的建立，處理和繪制。使用NetworkX 類的執行個體作為需要着色的圖。除了可以從頭開始建立圖之外，還可以利用該庫中預定義的圖。

GraphColoringProblem 類的構造函數接受要着色的圖形作為參數。此外，它接受hardConstraintPenalty 參數，該參數表示違反硬限制的懲罰因子。

# 導入所需庫
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
class GraphColoringProblem:
    def __init__(self,graph,hardConstraintPenalty):
       
        # 初始化執行個體變量
        self.graph = graph
        self.hardConstraintPenalty = hardConstraintPenalty
        # 建立圖節點的清單
        self.nodeList = list(self.graph.nodes)
        # 建立圖的鄰接矩陣
        self.adjMatrix = nx.adjacency_matrix(graph).todense()
    def __len__(self):
        """
        :return: the number of nodes in the graph
        """
        return nx.number_of_nodes(self.graph)
   
    def getCost(self,colorArrangement):
        """
       計算給定顔色組合的總成本
        """
        return self.hardConstraintPenalty * self.getViolationsCount(colorArrangement) + self.getNumberOfColors(colorArrangement)
   
    def getViolationsCount(self,colorArrangement):
        """
        計算給定顔色排列中違反顔色的次數
        """
        if len(colorArrangement) != self.__len__():
            raise ValueError("size of color arrangement should be equal to ", self.__len__())
        violations = 0
        # 周遊每對節點，查找它們之間是否存在連結并使用相同的顔色
        for i in range(len(colorArrangement)):
            for j in range(i + 1,len(colorArrangement)):
                if self.adjMatrix[i,j]:
                    if colorArrangement[i] == colorArrangement[j]:
                        violations += 1
        return violations
   
    def getNumberOfColors(self, colorArrangement):
        """
        計算給定顔色排列使用的顔色數量
        """
        return len(set(colorArrangement))
    def plotGraph(self, colorArrangement):
        """
        繪制具有根據給定顔色排列進行着色的圖
        """
        if len(colorArrangement) != self.__len__():
            raise ValueError("size of color list should be equal to ",self.__len__())
        # 建立唯一色清單
        colorList = list(set(colorArrangement))
        # 建立實際顔色清單
        colors = plt.cm.rainbow(np.linspace(0,1,len(colorList)))
        # 周遊節點，并根據顔色組合配置設定顔色
        colorMap = []
        for i in range(self.__len__()):
            color = colors[colorList.index(colorArrangement[i])]
            colorMap.append(color)
       
        # 對相應節點進行着色
        nx.draw_kamada_kawai(self.graph,node_color=colorMap,with_labels=True)
        return plt      

遺傳算法解決圖着色問題

常量及遺傳算子定義

1. 導入所需庫

from deap import base
from deap import creator
from deap import tools
import random
import numpy as np
from matplotlib import pyplot as plt
import seaborn as sns
import networkx as nx      

2. 硬限制懲罰因子

HARD_CONSTRAINT_PENALTY = 10      

3. 基因算法常量

POPULATION_SIZE = 100
P_CROSSOVER = 0.9
P_MUTATION = 0.1
MAX_GENERATIONS = 100
HALL_OF_FAME_SIZE = 10
MAX_COLORS = 10      

4. 執行個體化圖着色問題，該執行個體具有要解決的所需NetworkX圖，以及hardConstraintPenalty的所需值

gcp = GraphColoringProblem(nx.petersen_graph(),HARD_CONSTRAINT_PENALTY)      

5. 定義最小化适應度政策

creator.create("FitnessMin",base.Fitness,weights=(-1.0,))      

6. .由于解由代表參與顔色的整數值清單表示，是以需要定義一個随機生成器，該生成器将建立介于0和顔色數減1之間的整數。每個整數代表一種顔色。然後，定義解（個體）建立器，該建立器将生成随機整數的清單，清單的長度與給定圖的長度比對。最後，定義建立整個群體的運算符：

creator.create("Individual",list,fitness=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("Integers",random.randint,0,MAX_COLORS - 1)
toolbox.register("individualCreator",tools.initRepeat,creator.Individual,toolbox.Integers,len(gcp))
toolbox.register("populationCreator",tools.initRepeat,list,toolbox.individualCreator)      

7. 通過調用GraphColoringProblem類的getCost()方法，将适應度評估函數設定為計算解的違反顔色數和使用的顔色數量

def getCost(individual):
    return gcp.getCost(individual),
toolbox.register("evaluate",getCost)      

8. 定義遺傳算子

toolbox.register("select",tools.selTournament,tournsize=2)
toolbox.register("mate",tools.cxTwoPoint)
# mutUniformInt運算符，将給定的整數更改為允許範圍内的另一個随機生成的整數
toolbox.register("mutate",tools.mutUniformInt,low=0,up=MAX_COLORS - 1,indpb=1.0/len(gcp))      

使用精英主義政策

使用名人堂可以用來保留進化過程中種群中曾經存在的最佳個體，并不會由于選擇，交叉或變異而失去了它們，HallOfFame類在tools子產品中實作。

将Halloffame對象用于實作精英主義。 Halloffame對象中包含的個體被直接注入下一代，并且不受選擇，交叉和突變的遺傳算子的影響

# 名人堂成員數量
HALL_OF_FAME_SIZE = 30
def eaSimpleWithElitism(population,
    toolbox,
            cxpb,
            mutpb,
            ngen,
            stats=None,
            halloffame=None,
            verbose=__debug__):
    """
    使用halloffame來實作精英機制。 包含在名人堂麥中的個體被直接注入下一代，并且不受選擇，交叉和突變的遺傳算子的影響。
    """
   
    logbook = tools.Logbook()#用于監控算法運作，和統計資料
    logbook.header = ['gen','nevals'] + (stats.fields if stats else [])
    # 計算個體适應度
    invalid_ind = [ind for ind in population if not ind.fitness.valid]
    fitnesses = toolbox.map(toolbox.evaluate,invalid_ind)
    for ind,fit in zip(invalid_ind,fitnesses):
        ind.fitness.values = fit
   
    if halloffame is None:
        raise ValueError("halloffame parameter must not be empty!")
    #更新名人堂成員
    halloffame.update(population)
    hof_size = len(halloffame.items) if halloffame.items else 0
    record = stats.compile(population) if stats else {}
    logbook.record(gen=0,nevals=len(invalid_ind),**record)
    if verbose:
        print(logbook.stream)
   
    #開始遺傳流程
    for gen in range(1,ngen + 1):
        #選擇個體數目=種群個體數-名人堂成員數
        offspring = toolbox.select(population,len(population) - hof_size)
        #種群更新到下一代
        offspring = algorithms.varAnd(offspring,toolbox,cxpb,mutpb)
        #計算個體适應度
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = toolbox.map(toolbox.evaluate,invalid_ind)
        for ind,fit in zip(invalid_ind,fitnesses):
            ind.fitness.values = fit
       
        #将名人堂成員添加到目前代
        offspring.extend(halloffame.items)
        #更新名人堂
        halloffame.update(offspring)
        #使用目前代替換種群
        population[:] = offspring
        #将目前統計資訊附加到日志
        record = stats.compile(population) if stats else {}
        logbook.record(gen=gen,nevals=len(invalid_ind),**record)
        if verbose:
            print(logbook.stream)
       
    return population,logbook      

遺傳流程

def main():
    # 建立初始種群
    population = toolbox.populationCreator(n=POPULATION_SIZE)
    # 定義監聽統計資料
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("min",np.min)
    stats.register("avg",np.mean)
    # 執行個體化名人堂類
    hof = tools.HallOfFame(HALL_OF_FAME_SIZE)
    # 執行遺傳流程
    population, logbook = eaSimpleWithElitism(population,
            toolbox,
            cxpb=P_CROSSOVER,
            mutpb=P_MUTATION,
            ngen=MAX_GENERATIONS,
            stats=stats,
            halloffame=hof,
            verbose=True)
   
    # 列印算法找到的最優解
    best = hof.items[0]
    print("-- Best Individual = ",best)
    print("-- Best Fitness = ",best.fitness.values[0])
    print()
    print("Number of colors = ",gcp.getNumberOfColors(best))
    print("Number of violations = ",gcp.getViolationsCount(best))
    print("Cost = ",gcp.getCost(best))
    # 繪制最優解
    plt.figure(1)
    gcp.plotGraph(best)
    # 提取監聽的統計結果
    minFitnessValues,meanFitnessValues = logbook.select("min","avg")
    # 繪制統計結果
    plt.figure(2)
    sns.set_style("whitegrid")
    plt.plot(minFitnessValues, color='red')
    plt.plot(meanFitnessValues, color='green')
    plt.xlabel('Generation')
    plt.ylabel('Min / Average Fitness')
    plt.title('Min and Average fitness over Generations')
    plt.show()      

結果與分析

運作程式：

if __name__ == "__main__":
    main()      

列印最佳解的相關資訊：

-- Best Individual =  [0, 8, 3, 0, 3, 8, 0, 0, 3, 8]
-- Best Fitness =  3.0
Number of colors =  3
Number of violations =  0
Cost =  3      

由于此圖較為簡單是以算法找到的最佳解就是本問題包含的最優解。

最小适應度和平均适應度的變化：

使用不同圖測試算法效果

使用複雜圖進行測試

gcp = GraphColoringProblem(nx.mycielski_graph(6), HARD_CONSTRAINT_PENALTY)      

列印出算法找到的最優解

-- Best Individual =  [3, 6, 4, 4, 2, 3, 5, 4, 0, 6, 2, 1, 5, 0, 0, 1, 1, 6, 4, 4, 5, 1, 2, 1, 2, 3, 0, 5, 3, 6, 0, 5, 5, 2, 1, 0, 0, 1, 1, 3, 6, 1, 5, 1, 1, 3, 4]
-- Best Fitness =  7.0
Number of colors =  7
Number of violations =  0
Cost =  7      

由于知道該圖的色數為6，是以盡管沒有違反硬限制，是有效解但并不是最佳解。如果我們事先不知道着色數怎麼辦？一種解決方法是更改遺傳算法的參數。例如，增加種群數量（可能還有HOF數量）或增加世代數。另一種方法是重新開始相同的搜尋，但是減少顔色數量。由于該算法找到了具有7種顔色的解決方案，是以可以将最大顔色數減少為6種，并檢視算法是否仍然可以找到有效的解決方案：

MAX_COLORS = 6      

MAX_COLORS = 6 時列印結果

-- Best Individual =  [0, 2, 0, 3, 4, 4, 5, 3, 5, 4, 0, 0, 1, 1, 3, 1, 1, 1, 1, 1, 1, 0, 4, 4, 2, 0, 2, 4, 5, 4, 5, 5, 2, 0, 0, 2, 3, 2, 2, 5, 5, 5, 5, 2, 0, 4, 1]
-- Best Fitness =  6.0
Number of colors =  6
Number of violations =  0      

當我們将顔色的數量從10減少到6時，搜尋空間将大大減少——在這種情況下，将從 10​47 減少到 6​47 （因為圖中有47個節點）——是以該算法更有可能找到最佳解，即使世代數和人口規模并未改變。是以，雖然算法的第一次運作可以使我們更接近最優解，但是最好不斷減少顔色的數量，直到算法找不到更好的解決方案為止。

如果嘗試将顔色的最大數量減少到5種，将始終存在至少遇到一種違反硬限制的情況。

MAX_COLORS = 5      

MAX_COLORS = 5時列印結果

-- Best Individual =  [1, 0, 1, 3, 2, 2, 2, 3, 3, 2, 1, 2, 0, 3, 4, 0, 2, 3, 3, 0, 2, 0, 1, 1, 4, 1, 4, 2, 2, 4, 4, 4, 2, 4, 4, 0, 4, 4, 0, 2, 4, 4, 4, 4, 0, 1, 3]
-- Best Fitness =  15.0
Number of colors =  5
Number of violations =  1
Cost =  15