您好,登錄后才能下訂單哦!
小編給大家分享一下如何使用Python地圖四色原理的遺傳算法著色,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
  首先,我們來明確一下本文所需實現(xiàn)的需求。
  現(xiàn)有一個由多個小圖斑組成的矢量圖層,如下圖所示;我們需要找到一種由4種顏色組成的配色方案,對該矢量圖層各圖斑進行著色,使得各相鄰小圖斑間的顏色不一致,如下下圖所示。
  在這里,我們用到了四色定理(Four Color Theorem),又稱四色地圖定理(Four Color Map Theorem):如果在平面上存在一些鄰接的有限區(qū)域,則至多僅用四種顏色來給這些不同的區(qū)域染色,就可以使得每兩個鄰接區(qū)域染的顏色都不一樣。
  明確了需求,我們就可以開始具體的代碼編寫。目前國內(nèi)各大博客中,有很多關于Python實現(xiàn)地圖四色原理著色的代碼,其中大多數(shù)是基于回溯法來實現(xiàn)的;而在一個英文博客網(wǎng)頁中,看到了基于遺傳算法的地圖四色原理著色實現(xiàn)。那么就以該代碼為例,進行操作。在這里,由于我本人對于遺傳算法的理解還并不深入,因此在代碼介紹方面或多或少還存在著一定不足,希望大家多多批評指正。
  遺傳算法是一種用于解決最佳化問題的搜索算法,屬于進化算法范疇。結合前述需求,首先可以將每一個區(qū)域的顏色作為一個基因,個體基因型則為全部地區(qū)(前述矢量圖層共有78個小圖斑,即78個區(qū)域)顏色基因的匯總;通過構建Rule類,將空間意義上的“相鄰”轉換為可以被遺傳算法識別(即可以對個體基因改變加以約束)的信息;隨后,結合子代的更替,找到滿足要求的基因組;最終將得到的基因組再轉換為空間意義上的顏色信息,并輸出結果。
  具體分步驟思路如下:
定義“規(guī)則”?!耙?guī)則”用以將區(qū)域之間的空間連接情況轉換為遺傳算法可以識別的信息;被“規(guī)則”連接的兩個區(qū)域在空間中是相鄰的。定義區(qū)域空間連接情況檢查所需函數(shù)。這些函數(shù)用于檢查兩兩區(qū)域之間的連接性是否滿足邏輯;例如,若在“規(guī)則”中顯示區(qū)域A與區(qū)域B連接,那么區(qū)域B也必須在“規(guī)則”中顯示與區(qū)域A連接。定義個體基因型。其中,各個體具有78個基因,每一個基因表示一個區(qū)域的顏色。個體更替與最優(yōu)基因選擇。通過個體的不斷更迭,選擇出滿足“規(guī)則”要求的個體基因型?;蛐徒忉尅⒌玫降膫€體基因型進行解釋,相當于第一步的反過程,即將基因信息轉換為空間連接情況。結果檢查。檢查所得到的顏色與最優(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ū)域之間的空間連接情況轉換為遺傳算法可以識別的信息。被“規(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()
  執(zhí)行上述代碼,即可得到結果。在這里值得一提的是:這個代碼不知道是其自身原因,還是我電腦的問題,執(zhí)行起來非常慢——單次運行時間可能在5 ~ 6個小時左右,實在太慢了;大家如果感興趣,可以嘗試著能不能將代碼的效率提升一下。
  代碼執(zhí)行完畢后得到的結果是文字形式的,具體如下圖所示。
  可以看到,通過203次迭代,找到了滿足要求的地圖配色方案,用時06小時06分鐘;代碼執(zhí)行結果除顯示出具體個體的整體基因型之外,還將分別顯示78個小區(qū)域(小圖斑)各自的具體顏色名稱(我上面那幅圖沒有截全,實際上是78個小區(qū)域的顏色都會輸出的)。
  當然,大家也可以發(fā)現(xiàn),這種文字表達的代碼執(zhí)行結果顯然不如直接來一幅如下所示的結果圖直觀。但是,由于代碼單次執(zhí)行時間實在是太久了,我也沒再騰出時間(其實是偷懶)對結果的可視化加以修改。大家如果感興趣的話,可以嘗試對代碼最終的結果呈現(xiàn)部分加以修改——例如,可以通過Matplotlib庫的拓展——Basemap庫將78個小區(qū)域的配色方案進行可視化。
以上是“如何使用Python地圖四色原理的遺傳算法著色”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學習更多知識,歡迎關注億速云行業(yè)資訊頻道!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。