Python实现地图四色原理的遗传算法(GA)着色实现

本文涉及的产品
全球加速 GA,每月750个小时 15CU
简介: Python实现地图四色原理的遗传算法(GA)着色实现

1 任务需求

  首先,我们来明确一下本文所需实现的需求。

  现有一个由多个小图斑组成的矢量图层,如下图所示;我们需要找到一种由4种颜色组成的配色方案,对该矢量图层各图斑进行着色,使得各相邻小图斑间的颜色不一致,如下下图所示。

  在这里,我们用到了四色定理(Four Color Theorem),又称四色地图定理(Four Color Map Theorem):如果在平面上存在一些邻接的有限区域,则至多仅用四种颜色来给这些不同的区域染色,就可以使得每两个邻接区域染的颜色都不一样。

2 代码实现

  明确了需求,我们就可以开始具体的代码编写。目前国内各大博客中,有很多关于Python实现地图四色原理着色的代码,其中大多数是基于回溯法来实现的;而在一个英文博客网页中,看到了基于遗传算法的地图四色原理着色实现。那么就以该代码为例,进行操作。在这里,由于我本人对于遗传算法的理解还并不深入,因此在代码介绍方面或多或少还存在着一定不足,希望大家多多批评指正。

2.1 基本思路

  遗传算法是一种用于解决最佳化问题的搜索算法,属于进化算法范畴。结合前述需求,首先可以将每一个区域的颜色作为一个基因,个体基因型则为全部地区(前述矢量图层共有78个小图斑,即78个区域)颜色基因的汇总;通过构建Rule类,将空间意义上的“相邻”转换为可以被遗传算法识别(即可以对个体基因改变加以约束)的信息;随后,结合子代的更替,找到满足要求的基因组;最终将得到的基因组再转换为空间意义上的颜色信息,并输出结果。

  具体分步骤思路如下:

  1. 定义“规则”。“规则”用以将区域之间的空间连接情况转换为遗传算法可以识别的信息;被“规则”连接的两个区域在空间中是相邻的。
  2. 定义区域空间连接情况检查所需函数。这些函数用于检查两两区域之间的连接性是否满足逻辑;例如,若在“规则”中显示区域A与区域B连接,那么区域B也必须在“规则”中显示与区域A连接。
  3. 定义个体基因型。其中,各个体具有78个基因,每一个基因表示一个区域的颜色。
  4. 个体更替与最优基因选择。通过个体的不断更迭,选择出满足“规则”要求的个体基因型。
  5. 基因型解释。将得到的个体基因型进行解释,相当于第一步的反过程,即将基因信息转换为空间连接情况。
  6. 结果检查。检查所得到的颜色与最优个体基因组中的各个基因是否一致。

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
# 定义“规则”,用以将区域之间的空间连接情况转换为遗传算法可以识别的信息。被“规则”连接的两个区域在空间中是相邻的
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()

2.3 结果展示

  执行上述代码,即可得到结果。在这里值得一提的是:这个代码不知道是其自身原因,还是我电脑的问题,执行起来非常慢——单次运行时间可能在5 ~ 6个小时左右,实在太慢了;大家如果感兴趣,可以尝试着能不能将代码的效率提升一下。

  代码执行完毕后得到的结果是文字形式的,具体如下图所示。

  可以看到,通过203次迭代,找到了满足要求的地图配色方案,用时06小时06分钟;代码执行结果除显示出具体个体的整体基因型之外,还将分别显示78个小区域(小图斑)各自的具体颜色名称(我上面那幅图没有截全,实际上是78个小区域的颜色都会输出的)。

  当然,大家也可以发现,这种文字表达的代码执行结果显然不如直接来一幅如下所示的结果图直观。但是,由于代码单次执行时间实在是太久了,我也没再腾出时间(其实是偷懒)对结果的可视化加以修改。大家如果感兴趣的话,可以尝试对代码最终的结果呈现部分加以修改——例如,可以通过Matplotlib库的拓展——Basemap库将78个小区域的配色方案进行可视化。

欢迎关注公众号/CSDN/知乎/微博:疯狂学习GIS


目录
打赏
0
1
1
1
118
分享
相关文章
zk基础—1.一致性原理和算法
本文详细介绍了分布式系统的特点、理论及一致性算法。首先分析了分布式系统的五大特点:分布性、对等性、并发性、缺乏全局时钟和故障随时发生。接着探讨了分布式系统理论,包括CAP理论(一致性、可用性、分区容错性)和BASE理论(基本可用、软状态、最终一致性)。文中还深入讲解了两阶段提交(2PC)与三阶段提交(3PC)协议,以及Paxos算法的推导过程和核心思想,强调了其在ZooKeeper中的应用。最后简述了ZAB算法,指出其通过改编的两阶段提交协议确保节点间数据一致性,并在Leader故障时快速恢复服务。这些内容为理解分布式系统的设计与实现提供了全面的基础。
基于GA遗传算法的悬索桥静载试验车辆最优布载matlab仿真
本程序基于遗传算法(GA)实现悬索桥静载试验车辆最优布载的MATLAB仿真(2022A版)。目标是自动化确定车辆位置,使加载效率ηq满足0.95≤ηq≤1.05且尽量接近1,同时减少车辆数量与布载时间。核心原理通过优化模型平衡最小车辆使用与ηq接近1的目标,并考虑桥梁载荷、车辆间距等约束条件。测试结果展示布载方案的有效性,适用于悬索桥承载能力评估及性能检测场景。
基于GA遗传优化的最优阈值计算认知异构网络(CHN)能量检测算法matlab仿真
本内容介绍了一种基于GA遗传优化的阈值计算方法在认知异构网络(CHN)中的应用。通过Matlab2022a实现算法,完整代码含中文注释与操作视频。能量检测算法用于感知主用户信号,其性能依赖检测阈值。传统固定阈值方法易受噪声影响,而GA算法通过模拟生物进化,在复杂环境中自动优化阈值,提高频谱感知准确性,增强CHN的通信效率与资源利用率。预览效果无水印,核心程序部分展示,适合研究频谱感知与优化算法的学者参考。
基于EM期望最大化算法的GMM参数估计与三维数据分类系统python源码
本内容展示了基于EM算法的高斯混合模型(GMM)聚类实现,包含完整Python代码、运行效果图及理论解析。程序使用三维数据进行演示,涵盖误差计算、模型参数更新、结果可视化等关键步骤,并附有详细注释与操作视频,适合学习EM算法与GMM模型的原理及应用。
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
17 1
|
12天前
|
基于 Python 跳表算法的局域网网络监控软件动态数据索引优化策略研究
局域网网络监控软件需高效处理终端行为数据,跳表作为一种基于概率平衡的动态数据结构,具备高效的插入、删除与查询性能(平均时间复杂度为O(log n)),适用于高频数据写入和随机查询场景。本文深入解析跳表原理,探讨其在局域网监控中的适配性,并提供基于Python的完整实现方案,优化终端会话管理,提升系统响应性能。
34 4
基于GA遗传优化的三维空间WSN网络最优节点部署算法matlab仿真
本程序基于遗传算法(GA)优化三维空间无线传感网络(WSN)的节点部署,通过MATLAB2022A实现仿真。算法旨在以最少的节点实现最大覆盖度,综合考虑空间覆盖、连通性、能耗管理及成本控制等关键问题。核心思想包括染色体编码节点位置、适应度函数评估性能,并采用网格填充法近似计算覆盖率。该方法可显著提升WSN在三维空间中的部署效率与经济性,为实际应用提供有力支持。
|
2月前
|
Apriori算法的Python实例演示
经过运行,你会看到一些集合出现,每个集合的支持度也会给出。这些集合就是你想要的,经常一起被购买的商品组合。不要忘记,`min_support`参数将决定频繁项集的数量和大小,你可以根据自己的需要进行更改。
122 18
分布式锁—1.原理算法和使用建议
本文主要探讨了Redis分布式锁的八大问题,包括非原子操作、忘记释放锁、释放其他线程的锁、加锁失败处理、锁重入问题、锁竞争问题、锁超时失效及主从复制问题,并提供了相应的优化措施。接着分析了Redis的RedLock算法,讨论其优缺点以及分布式专家Martin对其的质疑。此外,文章对比了基于Redis和Zookeeper(zk)的分布式锁实现原理,包括获取与释放锁的具体流程。最后总结了两种分布式锁的适用场景及使用建议,指出Redis分布式锁虽有性能优势但模型不够健壮,而zk分布式锁更稳定但部署成本较高。实际应用中需根据业务需求权衡选择。

热门文章

最新文章

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问