??本文介紹利用Python語言，實現(xiàn)基于遺傳算法（GA）的地圖四色原理著色操作镰惦。
1 任務(wù)需求
??首先迷守，我們來明確一下本文所需實現(xiàn)的需求。
??現(xiàn)有一個由多個小圖斑組成的矢量圖層旺入，如下圖所示兑凿；我們需要找到一種由4種顏色組成的配色方案，對該矢量圖層各圖斑進行著色茵瘾，使得各相鄰小圖斑間的顏色不一致礼华，如下下圖所示。
??在這里拗秘，我們用到了四色定理（Four Color Theorem）圣絮，又稱四色地圖定理（Four Color Map Theorem）：如果在平面上存在一些鄰接的有限區(qū)域，則至多僅用四種顏色來給這些不同的區(qū)域染色雕旨，就可以使得每兩個鄰接區(qū)域染的顏色都不一樣扮匠。
2 代碼實現(xiàn)
??明確了需求，我們就可以開始具體的代碼編寫奸腺。目前國內(nèi)各大博客中餐禁，有很多關(guān)于Python實現(xiàn)地圖四色原理著色的代碼，其中大多數(shù)是基于回溯法來實現(xiàn)的突照；而在一個英文博客網(wǎng)頁中帮非，看到了基于遺傳算法的地圖四色原理著色實現(xiàn)。那么就以該代碼為例讹蘑，進行操作末盔。在這里，由于我本人對于遺傳算法的理解還并不深入座慰，因此在代碼介紹方面或多或少還存在著一定不足陨舱，希望大家多多批評指正。
2.1 基本思路
??遺傳算法是一種用于解決最佳化問題的搜索算法版仔，屬于進化算法范疇游盲。結(jié)合前述需求误墓，首先可以將每一個區(qū)域的顏色作為一個基因，個體基因型則為全部地區(qū)（前述矢量圖層共有78個小圖斑益缎，即78個區(qū)域）顏色基因的匯總谜慌；通過構(gòu)建Rule類，將空間意義上的“相鄰”轉(zhuǎn)換為可以被遺傳算法識別（即可以對個體基因改變加以約束）的信息莺奔；隨后欣范，結(jié)合子代的更替，找到滿足要求的基因組令哟；最終將得到的基因組再轉(zhuǎn)換為空間意義上的顏色信息恼琼，并輸出結(jié)果。
??具體分步驟思路如下：
- 定義“規(guī)則”屏富∏缇海“規(guī)則”用以將區(qū)域之間的空間連接情況轉(zhuǎn)換為遺傳算法可以識別的信息；被“規(guī)則”連接的兩個區(qū)域在空間中是相鄰的役听。
- 定義區(qū)域空間連接情況檢查所需函數(shù)颓鲜。這些函數(shù)用于檢查兩兩區(qū)域之間的連接性是否滿足邏輯；例如典予，若在“規(guī)則”中顯示區(qū)域A與區(qū)域B連接甜滨，那么區(qū)域B也必須在“規(guī)則”中顯示與區(qū)域A連接。
- 定義個體基因型瘤袖。其中衣摩，各個體具有78個基因，每一個基因表示一個區(qū)域的顏色捂敌。
- 個體更替與最優(yōu)基因選擇艾扮。通過個體的不斷更迭，選擇出滿足“規(guī)則”要求的個體基因型占婉。
- 基因型解釋泡嘴。將得到的個體基因型進行解釋，相當(dāng)于第一步的反過程逆济，即將基因信息轉(zhuǎn)換為空間連接情況酌予。
- 結(jié)果檢查。檢查所得到的顏色與最優(yōu)個體基因組中的各個基因是否一致奖慌。
2.2 代碼講解
??接下來抛虫，將完整代碼進行介紹。其中简僧，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
# 定義“規(guī)則”棉姐，用以將區(qū)域之間的空間連接情況轉(zhuǎn)換為遺傳算法可以識別的信息屠列。被“規(guī)則”連接的兩個區(qū)域在空間中是相鄰的
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
# 定義區(qū)域空間連接情況檢查所需函數(shù)，用以確保區(qū)域兩兩之間相鄰情況的準確
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個基因脸哀，每一個基因代表一個區(qū)域。個體基因需要滿足“規(guī)則”中相鄰的區(qū)域具有不同的顏色
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]])
# 輸出各區(qū)域顏色
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("%s\t%i\t%s" % (''.join(map(str, candidate.Genes)), candidate.Fitness, str(timeDiff)))
# 檢查各區(qū)域顏色是否與個體基因所代表的顏色一致
def getFitness(candidate, rules):
rulesThatPass = 0
for rule in rules:
if candidate[rule.Item] != candidate[rule.Other]:
rulesThatPass += 1
return rulesThatPass
# 運行程序
GraphColoringTests().test()
2.3 結(jié)果展示
??執(zhí)行上述代碼扭吁，即可得到結(jié)果。在這里值得一提的是：這個代碼不知道是其自身原因盲镶，還是我電腦的問題侥袜，執(zhí)行起來非常慢——單次運行時間可能在5 ~ 6個小時左右，實在太慢了溉贿；大家如果感興趣枫吧，可以嘗試著能不能將代碼的效率提升一下。
??代碼執(zhí)行完畢后得到的結(jié)果是文字形式的宇色，具體如下圖所示九杂。
??可以看到，通過203次迭代宣蠕，找到了滿足要求的地圖配色方案例隆，用時06小時06分鐘；代碼執(zhí)行結(jié)果除顯示出具體個體的整體基因型之外抢蚀，還將分別顯示78個小區(qū)域（小圖斑）各自的具體顏色名稱（我上面那幅圖沒有截全镀层，實際上是78個小區(qū)域的顏色都會輸出的）。
??當(dāng)然皿曲，大家也可以發(fā)現(xiàn)唱逢，這種文字表達的代碼執(zhí)行結(jié)果顯然不如直接來一幅如下所示的結(jié)果圖直觀。但是屋休，由于代碼單次執(zhí)行時間實在是太久了坞古，我也沒再騰出時間（其實是偷懶）對結(jié)果的可視化加以修改。大家如果感興趣的話劫樟，可以嘗試對代碼最終的結(jié)果呈現(xiàn)部分加以修改——例如痪枫，可以通過Matplotlib庫的拓展——Basemap庫將78個小區(qū)域的配色方案進行可視化。
