本文介紹利用Python語言，實現基于遺傳算法（GA）的地圖四色原理着色操作。

  首先，我們來明确一下本文所需實現的需求。

  現有一個由多個小圖斑組成的矢量圖層，如下圖所示；我們需要找到一種由4種顔色組成的配色方案，對該矢量圖層各圖斑進行着色，使得各相鄰小圖斑間的顔色不一緻，如下下圖所示。

  在這裡，我們用到了四色定理（Four Color Theorem），又稱四色地圖定理（Four Color Map Theorem）：如果在平面上存在一些鄰接的有限區域，則至多僅用四種顔色來給這些不同的區域染色，就可以使得每兩個鄰接區域染的顔色都不一樣。

  明确了需求，我們就可以開始具體的代碼編寫。目前國内各大博客中，有很多關于Python實現地圖四色原理着色的代碼，其中大多數是基于回溯法來實現的；而在一個英文博客網頁中，看到了基于遺傳算法的地圖四色原理着色實現。那麼就以該代碼為例，進行操作。在這裡，由于我本人對于遺傳算法的理解還并不深入，因此在代碼介紹方面或多或少還存在着一定不足，希望大家多多批評指正。

  遺傳算法是一種用于解決最佳化問題的搜索算法，屬于進化算法範疇。結合前述需求，首先可以将每一個區域的顔色作為一個基因，個體基因型則為全部地區（前述矢量圖層共有78個小圖斑，即78個區域）顔色基因的彙總；通過構建Rule類，将空間意義上的“相鄰”轉換為可以被遺傳算法識别（即可以對個體基因改變加以約束）的信息；随後，結合子代的更替，找到滿足要求的基因組；最終将得到的基因組再轉換為空間意義上的顔色信息，并輸出結果。

  具體分步驟思路如下：

1. 定義“規則”。“規則”用以将區域之間的空間連接情況轉換為遺傳算法可以識别的信息；被“規則”連接的兩個區域在空間中是相鄰的。
2. 定義區域空間連接情況檢查所需函數。這些函數用于檢查兩兩區域之間的連接性是否滿足邏輯；例如，若在“規則”中顯示區域A與區域B連接，那麼區域B也必須在“規則”中顯示與區域A連接。
3. 定義個體基因型。其中，各個體具有78個基因，每一個基因表示一個區域的顔色。
4. 個體更替與最優基因選擇。通過個體的不斷更叠，選擇出滿足“規則”要求的個體基因型。
5. 基因型解釋。将得到的個體基因型進行解釋，相當于第一步的反過程，即将基因信息轉換為空間連接情況。
6. 結果檢查。檢查所得到的顔色與最優個體基因組中的各個基因是否一緻。

  接下來，将完整代碼進行介紹。其中，shapefile_path即為矢量圖層的保存路徑；"POLY_ID_OG"則為矢量圖層的屬性表中的一個字段，其代表每一個小圖斑的編号。

# -*- coding: utf-8 -*- """ Created on Sun Oct 31 19:22:33 2021 @author: Chutj """ import genetic import unittest import datetime from libpysal.weights import Queen shapefile_path="G:/Python_Home1/stl_hom_utm.shp" weights=Queen.from_shapefile(shapefile_path,"POLY_ID_OG") one_neighbor_other=weights.neighbors # 定義“規則”，用以将區域之間的空間連接情況轉換為遺傳算法可以識别的信息。被“規則”連接的兩個區域在空間中是相鄰的 class Rule: Item = None Other = None Stringified = None def __init__(self, item, other, stringified): self.Item = item self.Other = other self.Stringified = stringified def __eq__(self, another): return hasattr(another, 'Item') and \ hasattr(another, 'Other') and \ self.Item == another.Item and \ self.Other == another.Other def __hash__(self): return hash(self.Item) * 397 ^ hash(self.Other) def __str__(self): return self.Stringified # 定義區域空間連接情況檢查所需函數，用以确保區域兩兩之間相鄰情況的準确 def buildLookup(items): itemToIndex = {} index = 0 for key in sorted(items): itemToIndex[key] = index index = 1 return itemToIndex def buildRules(items): itemToIndex = buildLookup(items.keys()) rulesAdded = {} rules = [] keys = sorted(list(items.keys())) for key in sorted(items.keys()): keyIndex = itemToIndex[key] adjacentKeys = items[key] for adjacentKey in adjacentKeys: if adjacentKey == '': continue adjacentIndex = itemToIndex[adjacentKey] temp = keyIndex if adjacentIndex < temp: temp, adjacentIndex = adjacentIndex, temp ruleKey = str(keys[temp]) "->" str(keys[adjacentIndex]) rule = Rule(temp, adjacentIndex, ruleKey) if rule in rulesAdded: rulesAdded[rule] = 1 else: rulesAdded[rule] = 1 rules.append(rule) for k, v in rulesAdded.items(): if v == 1: print("rule %s is not bidirectional" % k) return rules # 定義顔色所代表的基因組 colors = ["Orange", "Yellow", "Green", "Blue"] colorLookup = {} for color in colors: colorLookup[color[0]] = color geneset = list(colorLookup.keys()) # 定義個體基因型，其中各個體有78個基因，每一個基因代表一個區域。個體基因需要滿足“規則”中相鄰的區域具有不同的顔色 class GraphColoringTests(unittest.TestCase): def test(self): rules = buildRules(one_neighbor_other) colors = ["Orange", "Yellow", "Green", "Blue"] colorLookup = {} for color in colors: colorLookup[color[0]] = color geneset = list(colorLookup.keys()) optimalValue = len(rules) startTime = datetime.datetime.now() fnDisplay = lambda candidate: display(candidate, startTime) fnGetFitness = lambda candidate: getFitness(candidate, rules) best = genetic.getBest(fnGetFitness, fnDisplay, len(one_neighbor_other), optimalValue, geneset) self.assertEqual(best.Fitness, optimalValue) keys = sorted(one_neighbor_other.keys()) for index in range(len(one_neighbor_other)): print(keys[index]," is ",colorLookup[best.Genes[index]]) # 輸出各區域顔色 def display(candidate, startTime): timeDiff = datetime.datetime.now() - startTime print("%s\t%i\t%s" % (''.join(map(str, candidate.Genes)), candidate.Fitness, str(timeDiff))) # 檢查各區域顔色是否與個體基因所代表的顔色一緻 def getFitness(candidate, rules): rulesThatPass = 0 for rule in rules: if candidate[rule.Item] != candidate[rule.Other]: rulesThatPass = 1 return rulesThatPass # 運行程序 GraphColoringTests().test()

  執行上述代碼，即可得到結果。在這裡值得一提的是：這個代碼不知道是其自身原因，還是我電腦的問題，執行起來非常慢——單次運行時間可能在5 ~ 6個小時左右，實在太慢了；大家如果感興趣，可以嘗試着能不能将代碼的效率提升一下。

  代碼執行完畢後得到的結果是文字形式的，具體如下圖所示。

  可以看到，通過203次叠代，找到了滿足要求的地圖配色方案，用時06小時06分鐘；代碼執行結果除顯示出具體個體的整體基因型之外，還将分别顯示78個小區域（小圖斑）各自的具體顔色名稱（我上面那幅圖沒有截全，實際上是78個小區域的顔色都會輸出的）。

  當然，大家也可以發現，這種文字表達的代碼執行結果顯然不如直接來一幅如下所示的結果圖直觀。但是，由于代碼單次執行時間實在是太久了，我也沒再騰出時間（其實是偷懶）對結果的可視化加以修改。大家如果感興趣的話，可以嘗試對代碼最終的結果呈現部分加以修改——例如，可以通過Matplotlib庫的拓展——Basemap庫将78個小區域的配色方案進行可視化。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!