一种基于改进遗传算法的村镇土地宗地多边形自动构建方法_刘治东.pdf

第 卷 第 期 年 月测绘与空间地理信息 ，收稿日期：基金项目：国家重点研发计划课题（）资助作者简介：刘治东（），男，安徽宿州人，人口学专业博士研究生，主要研究方向为地理信息系统、数理人口学。通信作者：封 宁（），男，浙江杭州人，副研究员，博士，年毕业于浙江大学生物医学工程专业，主要从事地理信息系统、土地管理科学、人工智能方面的研究工作。一种基于改进遗传算法的村镇土地宗地多边形自动构建方法刘治东，封 宁，米 红（浙江大学 公共管理学院，浙江 杭州）摘要：针对村镇土地宗地多边形自动构建的自动化智能化程度低以及精度不高的问题，本文提出一种基于改进遗传算法的宗地多边形自动构建方法。该算法具有以下特点：根据无序界址点位置信息构建宗地多边形，充分挖掘宗地多边形内在数学约束，加入宗地转角频率分布这一关键优化参数，将宗地各个转角频率乘积作为遗传算法的适应度函数，并针对宗地多边形的自相交问题进行了检验；该算法只需要获取界址点位置坐标和宗地代码信息，比较简洁高效。实验结果表明，本算法的准确率达到了 以上。关键词：遗传算法；村镇土地；宗地多边形自动构建中图分类号：文献标识码：文章编号：（），（，）：，：，；，：；引 言在村镇土地确权登记调查过程中，准确构建出宗地多边形是工作重点。传统的业务流程需要耗费大量人力物力，不仅需要外业人员实地测量调查，还需要内业人员多次对数据进行检查。研究宗地多边形自动构建问题可以提高村镇土地确权登记的效率和智能化水平，具有重要的研究意义和应用价值。目前，已经有大批学者对多边形拓扑关系自动构建算法进行了研究。闫浩文等提出了一种基于方位角计算的多边形快速构建算法即左转算法，但该算法会产生重复和无效多边形，需要一一对比进行消除。梁晓文等针对以上情况，改进了左转算法，根据基于夹角变化趋势判断多边性搜索方向的算法，有效地判断出了多边形的搜索方向，避免了无效多边形的生成，但未对复杂的多边形如圆、椭圆等生成的多边形文件进行处理。此外，刘昌振也对左转算法进行了改进，消除了悬挂线段对左转算法构面的影响。为了避免了无效搜索和回退搜索，申传庆等提出了一种矢量外积的高效多边形自动生成算法，提高了时间效率。刘刚等引入方向夹角和类方位角概念，提出建立结点上弧弧拓扑关系的类方位角算法，用优秀的参数形式来保证算法的高效性。刘岳峰等提出一种基于扫描思想的弧段分割和多边形自动生成算法，该算法以较小的算法复杂度和极小的计算量，实现弧段分割和多边形自动构建；避免了传统方法中多边形嵌套关系的计算，并能有效地处理桥和悬边问题，在效率方面有明显的提升。前人的研究基本都是基于结点和弧段信息进行宗地多边形的拓扑关系构建，其研究重点是建立更加高效的弧段搜索算法，但这些研究很少提及根据界址点位置信息进行构建宗地多边形，考虑到未来宗地界址点测量手段的日益智能化精准化，基于界址点位置信息快速构建宗地多边形具有重要的应用价值，可以大大提高村镇土地确权登记的效率，节省人力物力，这也是本研究的出发点。算法思路遗传算法（，）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作，不需要求导计算，具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中遗传操作包括选择、交叉和变异 种，而参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等要素构成了遗传算法的核心内容。本文对遗传算法进行改进来解决散点构图问题，一个宗地多边形很自然的表示为 个界址点的排列，但基于二进制编码的交叉和变异操作不能适用。多边形路径表示是对应的基因编码的最自然、最简单的表示方法，它在编码、解码、存储过程中相对容易理解和实现。如多边形（）可以直接表示为（）。具体算法流程如图 所示，主要包括以下几个步骤：）初始化种群。种群的初始化采用随机排列原则，对于（为每个宗地的界址点总数）共 个整数产生 个不同的随机排列，代表不同界址点连线顺序下的宗地多边形。）设计适应度函数。适应度函数的设计是遗传算法的关键一步，直接影响到算法的优劣。针对宗地散点构图这一问题适应度函数的设计是重难点，考虑到村镇土地宗地边界大多数是房屋边界，而房屋形状普遍都具有一定规律，如房屋转角（本文中对宗地转角的定义是，以该界址点为顶点，以该点所在的 条界址线作为边组成的不大于 的角）一般都是直角，基本不会是角度很小的锐角。图 是根据某地的 个转角画出的频率分布直方图，从图中可以明显看出宗地转角基本都分布在 和 附近。基于图 我们设计如下适应度函数：图 宗地多边形自动构建的改进遗传算法流程图 式中，代表同一宗地的不同界址点，而为第 个界址点所在转角的频率值（由图 求得），将宗地的各个转角频率乘积作为适应度函数可以保证在迭代的过程中自动寻找到概率更大的转角，所计算的宗地形状也就有更大的概率是正确的。图 宗地转角频率分布直方图 ）选择操作。一般地说，选择将使适应度较大（优良）个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。遗传算法通常采用轮盘赌选择机制，令表示群体的适应度值之总和，表示种群中第 个个体的适应度值，它产生后代的能力正好为其适应度值所占份额。）交叉操作。先随机生成 个交叉点，定义这两点间的区域为匹配区域，并交换 个父代的匹配区域。父代（）和父代（）交换后变为：（）和 （）。对于、中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：，测绘与空间地理信息 年，则得到子代（）和子代（）。）变异操作。在散点构图问题中个体的编码是一批界址点的序列，随机地在这个序列抽取 个界址点，然后交换它们的位置，这样就实现了个体编码的变异，算法如下：产生两个 之间的随机实数；将这 个随机实数转化为（界址点总数）之间的随机整数；将这 个随机整数指代的界址点进行交换。）自相交检验。因为宗地多边形是不存在界址线自相交情况的，所以需要在算法中添加自相交检验，我们设置一个自相交检验的最大次数，当每经过（最大迭代次数）次迭代后进行一次自相交检验，如果不存在自相交情况，则直接输出最终结果，如果存在自相交情况则重新初始化种群进行迭代，自相交检验次数超过 次时无论是否自相交都输出相应结果。自相交检验本质是为了跳出局部最优结果，而去寻找到全局最优，理论上肯定能够提高计算准确率，但不可避免会增加运算时间，所以 值的设定不能太大。编程实现结果本文随机选择 个不同村镇地区一共 个宗地的数据作为算法输入，包括 个宗地的宗地代码和 个界址点的坐标信息。最大迭代次数 设置为，种群数量设置为 个，交叉概率为，变异概率为，自相交检验最大次数 ，在同样的数据输入和参数设置下一共进行 次计算并对 次计算结果取平均，算法结果见表。算法仿真采用的计算机配置为 和 ，代码用 语言实现。表 算法仿真结果 宗地个数正确个数错误个数准确率（）计算效率（一个宗地）第 次计算 第 次计算 第 次计算 第 次计算 第 次计算 次平均结果 根据表 结果，可以看出本算法的正确率稳定在以上，平均每个宗地需要计算 。为了对本文算法进行深入分析，将表 第 次计算结果中的正确和错误宗地区分开，按照宗地界址点总数分别画出直方图，结果如图 所示，其中横坐标是界址点的总数，纵坐标是宗地个数。讨 论）由表 结果可知，本研究改进的遗传算法思路对于解决村镇土地宗地乱序电子界址点自动构面的问题具图 仿真计算结果直方图 有可行性，其中适应度函数的设计是关键，本文创新点在于宗地的转角频率乘积作为适应度函数。同时本文算法引入了自相交检查，这在一定程度上降低了算法的偶然性风险。）当宗地的界址点数量比较大时，本文算法的准确率会下降，这主要是因为散点构图本质上是 难的 问题，当界址点数量增大，算法复杂度会急剧加大，针对这一问题，后续可以进一步深入挖掘宗地形状规律，如利用宗地的对称性等特点将问题简化，进而大大提高计算速度和准确率。结束语本文提出一种基于改进遗传算法的村镇土地宗地多边形自动构建方法，通过挖掘宗地多边形内在数学约束，提取出宗地转角频率这一关键参数，并参与遗传算法的适应度函数的设计，还在算法中针对宗地多边形的自相交问题进行了检验，仿真结果表明，算法成功率达到 以上，后续还可以利用宗地的对称性等特点来优化算法提高运算效率和准确率。本算法只需要各宗地的界址点位置信息及宗地代码即可自动构建出宗地多边形，为村镇土地调查登记的智能化快速化提供了一种思路。参考文献：闫浩文，杨维芳，陈全功，等基于方位角计算的拓扑多边形自动构建快速算法中国图象图形学报，（）：闫浩文，祝方雄拓扑多边形自动构建的一种快速算法浙江测绘，（）：，梁晓文，刘宗岐，陈宜金基于夹角变化趋势的多边形自动搜索和生成算法中国图象图形学报，（）：刘昌振基于改进左转算法的拓扑构面测绘通报，（）：，（下转第 页）第 期刘治东等：一种基于改进遗传算法的村镇土地宗地多边形自动构建方法 结束语采用不同年份遥感数据，运用 分类法和 空间分析等方法研究了 年北京市土地利用动态变化和环路空间特征，以及植被覆盖度分布特点，研究结果表明：）北京市面积占比最大的土地类型是绿地 耕地。年土地变化主要呈绿地 耕地面积明显缩减，建筑用地扩张的趋势。）绿地 耕地和建筑用地的空间消长特征表现为建筑用地综合扩张程度远高于绿地 耕地，年的 是绿地 耕地的 倍，主要是由于建筑用地的扩张速度快，达。）研究期间北京市中高植被覆盖和高植被覆盖区域变化最大。其中，高覆盖度面积共减少，中高覆盖度面积增加有，低植被盖度面积则呈波动式增长趋势，表现为先增加后减少，前后共增长。）土地类型和植被覆盖度动态变化具有明显的时空差异。表现为 年的绿地 耕地综合扩张指数是 年的 倍，建筑用地为 倍，研究前期的高植被覆盖度减少面积是后期的 倍。另外，年各环路中表现为绿地 耕地减少和建筑用地增加，年则相反。表明在 年阶段，建成区扩张现象得到有效遏制。）北京市绿地 耕地及建筑用地的动态变化存在明显的环路差异。表现在四环内 种土地类型的相对变化率和总变化率涨幅差异不大，而绿地 耕地的相对变化率远大于建筑用地；在五环和六环 内区域的 个指标则有明显增长。参考文献：张梅，卢学辉基于遥感与 的北京市土地利用变化分析 长春师范 大 学 学 报，（）：，张岩，熊琦基于 城市建设用地及城市绿地空间分异研究河北林业科技，（）：谢亚娟，危小建，孙显星南昌市城市扩张特征与空间格局分析江西科学，（）：龚文峰，曹凯华，周莹基于 和 的甘南县 年植被覆盖度时空演变分析湖北农业科学，（）：韩桂兰，王亮朝乌鲁木齐城市空间扩张及其驱动力研究河南科技学院学报，（）：黄迎春，闫雅梅，张文新 年北京市土地利用变化区际差异分析城市发展研究，（）：易扬改革开放以来山区土地景观格局时空变化特征 以北京市门头沟区为例亚热带水土保持，（）：陈宇达，刘艳梅，汪新庆非监督分类的 方法在从化市 遥感图像的应用科技资讯，（）：程红芳，章文波，陈锋植被覆盖度遥感估算方法研究进展国土资源遥感，（）：吴见，彭建，谷双喜黄山市近 植被盖度时空变化遥感分析黑龙江工程学院学报，（）：编辑：任亚茹（上接第 页）申传庆，唐新明，史绍雨，等多边形自动生成的一种改进算法测绘科学，（）：，刘刚，李永树构建结点上弧弧拓扑关系的类方位角算法测绘科学，（）：刘岳峰，孙鹰，张凯，等一种基于平面扫描的弧段分割与多边形自动构建算法北京大学学报（自然科学版），（）：，（）：，（）：编辑：刘莉鑫（上接第 页）孙运豪，高洪，胡朵朵，等无人机倾斜摄影在文物修复中的应用北京测绘，（）：，杨新涅，吴维，孟令航民用航空概论 北京：人民交通出版社股份有限公司，王松基于旋翼无人机的机场实景三维测绘工程流程设计工程建设与设计，（）：国务院，中央军事委员会中华人民共和国飞行基本规则（修订版）北京：中国民航出版社，中华人民共和国住房和城乡建设部工