欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python地圖四色原理的遺傳算法著色實現(xiàn)

 更新時間:2022年02月07日 16:57:11   作者:瘋狂學(xué)習(xí)GIS  
大家好,本篇文章主要講的是Python地圖四色原理的遺傳算法著色實現(xiàn),感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下

1 任務(wù)需求

  首先,我們來明確一下本文所需實現(xiàn)的需求。

  現(xiàn)有一個由多個小圖斑組成的矢量圖層,如下圖所示;我們需要找到一種由4種顏色組成的配色方案,對該矢量圖層各圖斑進(jìn)行著色,使得各相鄰小圖斑間的顏色不一致,如下下圖所示。

在這里插入圖片描述

在這里插入圖片描述

  在這里,我們用到了四色定理(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)。那么就以該代碼為例,進(jìn)行操作。在這里,由于我本人對于遺傳算法的理解還并不深入,因此在代碼介紹方面或多或少還存在著一定不足,希望大家多多批評指正。

2.1 基本思路

  遺傳算法是一種用于解決最佳化問題的搜索算法,屬于進(jìn)化算法范疇。結(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ī)則”要求的個體基因型?;蛐徒忉?。將得到的個體基因型進(jìn)行解釋,相當(dāng)于第一步的反過程,即將基因信息轉(zhuǎn)換為空間連接情況。結(jié)果檢查。檢查所得到的顏色與最優(yōu)個體基因組中的各個基因是否一致。 2.2 代碼講解

  接下來,將完整代碼進(jìn)行介紹。其中,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ū)域兩兩之間相鄰情況的準(zhǔn)確

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

# 運(yùn)行程序

GraphColoringTests().test()

2.3 結(jié)果展示

  執(zhí)行上述代碼,即可得到結(jié)果。在這里值得一提的是:這個代碼不知道是其自身原因,還是我電腦的問題,執(zhí)行起來非常慢——單次運(yùn)行時間可能在5 ~ 6個小時左右,實在太慢了;大家如果感興趣,可以嘗試著能不能將代碼的效率提升一下。

  代碼執(zhí)行完畢后得到的結(jié)果是文字形式的,具體如下圖所示。

在這里插入圖片描述

  可以看到,通過203次迭代,找到了滿足要求的地圖配色方案,用時06小時06分鐘;代碼執(zhí)行結(jié)果除顯示出具體個體的整體基因型之外,還將分別顯示78個小區(qū)域(小圖斑)各自的具體顏色名稱(我上面那幅圖沒有截全,實際上是78個小區(qū)域的顏色都會輸出的)。

  當(dāng)然,大家也可以發(fā)現(xiàn),這種文字表達(dá)的代碼執(zhí)行結(jié)果顯然不如直接來一幅如下所示的結(jié)果圖直觀。但是,由于代碼單次執(zhí)行時間實在是太久了,我也沒再騰出時間(其實是偷懶)對結(jié)果的可視化加以修改。大家如果感興趣的話,可以嘗試對代碼最終的結(jié)果呈現(xiàn)部分加以修改——例如,可以通過Matplotlib庫的拓展——Basemap庫將78個小區(qū)域的配色方案進(jìn)行可視化。

在這里插入圖片描述

總結(jié)

到此這篇關(guān)于Python地圖四色原理的遺傳算法著色實現(xiàn)的文章就介紹到這了,更多相關(guān)Python地圖四色原理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 使用Matplotlib繪制平行坐標(biāo)系的示例詳解

    使用Matplotlib繪制平行坐標(biāo)系的示例詳解

    平行坐標(biāo)系,是一種含有多個垂直平行坐標(biāo)軸的統(tǒng)計圖表,這篇文章主要為大家介紹了如何使用繪制平行坐標(biāo)系,需要的小伙伴可以參考一下
    2023-07-07
  • Python Pillow Image Invert

    Python Pillow Image Invert

    今天小編就為大家分享一篇關(guān)于Python Pillow Image Invert,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2019-01-01
  • Python接入MySQL實現(xiàn)增刪改查的實戰(zhàn)記錄

    Python接入MySQL實現(xiàn)增刪改查的實戰(zhàn)記錄

    這篇文章主要給大家介紹了關(guān)于Python接入MySQL實現(xiàn)增刪改查的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-03-03
  • django進(jìn)階之cookie和session的使用示例

    django進(jìn)階之cookie和session的使用示例

    這篇文章主要介紹了django進(jìn)階之cookie和session的使用示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-08-08
  • PyTorch模型轉(zhuǎn)TensorRT是怎么實現(xiàn)的?

    PyTorch模型轉(zhuǎn)TensorRT是怎么實現(xiàn)的?

    今天給大家?guī)淼氖顷P(guān)于Python的相關(guān)知識,文章圍繞著PyTorch模型轉(zhuǎn)TensorRT是怎么實現(xiàn)的展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下
    2021-06-06
  • python:print格式化輸出到文件的實例

    python:print格式化輸出到文件的實例

    今天小編就為大家分享一篇python:print格式化輸出到文件的實例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-05-05
  • pandas的object對象轉(zhuǎn)時間對象的方法

    pandas的object對象轉(zhuǎn)時間對象的方法

    下面小編就為大家分享一篇pandas的object對象轉(zhuǎn)時間對象的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-04-04
  • Python判斷文件和文件夾是否存在的方法(最新推薦)

    Python判斷文件和文件夾是否存在的方法(最新推薦)

    常在讀寫文件之前,需要判斷文件或目錄是否存在,不然某些處理方法可能會使程序出錯,所以最好在做任何操作之前,先判斷文件是否存在,沒有則創(chuàng)建,今天通過實例代碼講解下Python判斷文件和文件夾是否存在的方法,感興趣的朋友一起看看吧
    2022-11-11
  • Python數(shù)據(jù)庫編程之pymysql詳解

    Python數(shù)據(jù)庫編程之pymysql詳解

    本文主要介紹了Python數(shù)據(jù)庫編程中pymysql,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-05-05
  • Python程序員面試題 你必須提前準(zhǔn)備!(答案及解析)

    Python程序員面試題 你必須提前準(zhǔn)備!(答案及解析)

    這篇文章主要為大家解析了你必須提前準(zhǔn)備的Python程序員面試題答案,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01

最新評論