一种基于遗传算法的土地资源评价因子级别划分方法

摘要

本发明涉及一种基于遗传算法的土地资源评价因子级别划分方法，充分利用遗传算法在优化问题求解方面的优势，将遗传算法引入评价因子级别划分问题的求解；根据评价因子级别划分问题的特点，设计了遗传算法适应度函数和约束条件，构建了适用于评价因子级别划分的遗传算法模型；本发明能够为土地资源质量评价的因子影响分析提供科学、准确的基础依据，进而为促进土地资源的合理利用提供技术支持。

说明书

技术领域

本发明属于土地资源评价技术领域，特别是涉及一种基于遗传算法的土地资源评价因子级别划分方法。

背景技术

随着21世纪的到来，人类面临的人口问题、粮食安全问题等诸多全球性问题日益严峻。我国作为人口大国，土地资源相对稀缺，如何合理利用土地，实现土地资源的可持续利用是当前迫切需要解决的问题。因此，采用科学的技术手段和方法对土地资源的质量进行评价，是促进土地资源合理利用的必要手段。

根据联合国粮农组织FAO的定义，土地资源评价是指对土地针对特定的利用方式所表现出来的效果进行评估的过程，包括对土地的形态、土壤、植被、气候等方面属性进行质量综合鉴定，从而区分并比较不同土地利用方式对评价目标所表现出的适宜性程度。有关文献：[1]FAO.Land Evaluation.Towards a revised framework.2007.。在借鉴国外先进技术的基础上，我国已形成了包括针对农用地与建设用地的土地分等、定级、估价、土地适宜性评价、土地集约利用评价、土地退化评价等在内的符合当前国情需求的土地评价体系。

在进行评价土地资源质量时，对土地资源质量有着显著影响的各种因素实体如商服中心、集贸市场、灌溉水源、道路网络等对象，被定义为“土地资源评价因子”(简称为“评价因子”)或“土地资源评价指标”。由于评价因子的规模(或大小)的差异将直接导致评价因子所具备的功能和作用存在差别，其对土地质量的影响的空间范围和强度也存在明显的不同，在进行评价因子分析时也需要进行区别对待。例如城镇土地资源评价中，大小和规模不同的商服中心、医院等服务设施，其所具备的功能和能提供的各类服务也不同，进而对土地资源质量的空间影响范围、作用方式和强度也各不相同。因此，在进行土地资源评价时，需要根据评价因子规模将其划分为若干级别，分别对不同级别的评价因子的空间影响范围和作用强度进行分析。有关文献：[2]国家质量监督检验检疫总局.城镇土地分等定级规程(GB/T 18507-2001)[S].2001；有关文献：[3]国土资源部.农用地定级规程(TD/T 1005-2004)[S].2003。

然而，目前有关土地评价因子级别划分的方法主要是根据带分级的评价因子规模指数，由土地评价专家根据自身经验人为将土地评价因子划分为若干级别。(注：规模指数用于反映各因子对象对土地资源质量的影响程度，规模指数越大，则其对土地资源质量影响的强度越大。规模指数通常根据能够反应评价因子大小、规模的一系列指标综合计算得到，其计算方法在相关的土地评价标准规范中都有较为详细的阐述，如城镇土地分等定级规程、农用地定级规程等，不是本发明的关注重点。)其缺点主要在于主观性太强，划分结果的科学性严重依赖于专家经验。因此，为了更加科学、合理的划分土地评价因子，进而为土地评价因子空间影响范围和强度分析提供准确的基础数据支持，必须开发出更为合理的土地评价因子级别划分方法。

遗传算法(Genetic Algorithm)是一种模拟达尔文生物进化论的随机搜索方法，参见图1.，其求解问题的基本思路是：将待求解的问题的求解过程表示成染色体的适者生存过程，把搜索空间映射为遗传空间，即把每一个可能的解编码为一个向量，向量的每一个元素称为基因。所有染色体组成的种群初始化后按照一个适应度函数计算其适应度，即进行适应度评价。经过染色体的选择、交叉、变异等遗传操作，然后重新进行适应度评价，剔除适应度低的个体，保留适应度高的个体，从而得到新的种群。新种群比上一代种群具有更有的性态，如此反复迭代，直到满足预定的优化目标，即满足终止条件，解码得到问题的解。有关文献：[5]陈森发，复杂系统建模理论与方法[M]，2005.南京：东南大学出版社.采用遗传算法解决问题的基本流程见附图1.遗传算法作为一种随机搜索算法，即使搜索空间非常大、非常复杂，遗传算法也能找到全局最优解。相对于传统的搜索和优化算法，遗传算法的主要优势在于其具有自组织、自适应、自学习性，因而被广泛应用于组合优化、机器学习、聚类分析和人工生命等领域。有关文献：[6]黎夏等.智能式GIS与空间优化[M].2010.北京：科学出版社.

发明内容

针对现有土地资源评价中评价因子级别划分方法的局限性，发明一种智能化、自动化的基于遗传算法的土地资源评价因子级别划分方法。为科学合理的研究与分析评价因子对土地资源质量的影响提供准确的基础依据，为合理、可持续利用土地资源提供技术方法支持。

本发明提供的技术方案是一种基于遗传算法的土地资源评价因子级别划分方法，包括以下步骤：

步骤1，输入每个评价因子的规模指数，规模指数是取值范围为[0-100]的实数；

步骤2，设染色体种群规模为M，染色体的基因位长度为K，第i个基因位上存储第i个级别的中心规模指数，i的取值为1、2...K；采用随机的方式生成M个染色体，形成初始的染色体种群；随机生成的约束条件是，每个基因位上的中心规模指数是取值范围为[0-100]的实数；

步骤3，对当前的染色体种群中各染色体分别进行染色体适应度评价，评价方式包括以下步骤，

步骤3.1，针对每个染色体所存储的各级别中心规模指数，按照最小距离原则和步骤1输入的规模指数，将各评价因子划分到距离最近的一个级别中；

步骤3.2，采用适应度函数评价各染色体的适应度，适应度函数如式1，

$>f=1/\underset{i=1}{\overset{K}{\Sigma }}\underset{j=1}{\overset{J}{\Sigma }}{(x_j-c_i)}^2$>式1

式中，c_i表示第i个级别的中心规模指数，J为第i个级别中评价因子的总数，x_j为第i个级别中第j个评价因子的规模指数；

步骤4，选择，包括根据染色体适应度值从当前的染色体种群中随机选择染色体，选择出的染色体个数记为n；

步骤5，交叉，包括从步骤4中选择的n个染色体中，按照事先设定的概率Pc随机选择Round(n×Pc)对染色体进行交叉，得到交叉后的染色体种群，其中Round为取整数操作；对一对染色体执行交叉时，在染色体上随机确定一个交叉点，这对染色体在交叉点处互相交换编码；

步骤6，变异，包括对步骤5所得交叉后的染色体种群中的每个染色体，将每个基因位根据事先设定的概率Pm随机确定该基因位是否进行变异，若执行变异，则该基因位上的数值更改为一个随机生成的[0-100]的实数值，得到变异后的染色体种群；

步骤7，判断是否满足终止条件，不满足则返回步骤3继续对染色体种群进行进化，直至满足终止条件，进入步骤8；

步骤8，对当前的染色体种群中各染色体分别进行染色体适应度评价，得到划分结果，包括以下步骤，

步骤8.1，针对每个染色体所存储的各级别中心规模指数，按照最小距离原则和步骤1输入的规模指数，将各评价因子划分到距离最近的一个级别中；

步骤8.2，采用适应度函数评价各染色体的适应度，适应度函数如式1，

$>f=1/\underset{i=1}{\overset{K}{\Sigma }}\underset{j=1}{\overset{J}{\Sigma }}{(x_j-c_i)}^2$>式1

式中，c_i表示第i个级别的中心规模指数，J为第i个级别中评价因子的总数，x_j为第i个级别中第j个评价因子的规模指数；

步骤8.3，将适应度最高的染色体作为最优的评价因子分级划分方案，将步骤8.1中针对适应度最高的染色体划分各评价因子的结果输出。

而且，步骤7中，终止条件为满足以下三种条件任一，

(一)达到设定的最大进化代数；

(二)达到设定的最长执行时间；

(三)进化陷入停滞，当连续y代的染色体种群适应度差值都小于预设的阈值F时认定进化陷入停滞，y为预设的自然数。

而且，步骤4中，从当前的染色体种群中随机选择染色体的具体方式如下，

首先，按照式3计算染色体种群中每个染色体被选中的概率，

$>p_t=\frac{f_t}{\underset{t=1}{\overset{M}{\Sigma }}{f}_t}$>式3

式中，p_t为染色体t被选中的概率，f_t为染色体t的适应度，M为染色体种群中染色体的个数；

然后，对于每个染色体产生一个随机数rnd，若随机数rnd的值大于染色体的选择概率p_t，则该染色体不被选中；若小于或等于染色体的选择概率p_t，则该染色体被选中。

本发明的技术方案总体上具有简单、自动化、智能化特点，相对于目前在实际工程中广泛应用的各种评价因子级别划分方法，本发明主要解决的问题有：(1)充分利用遗传算法在优化问题求解方面的优势，将遗传算法引入评价因子级别划分问题的求解；(2)根据评价因子级别划分问题的特点，设计了遗传算法适应度函数和约束条件，构建了适用于评价因子级别划分的遗传算法模型；(3)本发明能够为土地资源质量评价的因子影响分析提供科学、准确的基础依据，进而为促进土地资源的合理利用提供技术支持。

附图说明

图1是遗传算法的基本流程；

图2是本发明实施例的评价因子级别划分所用染色体编码示意图；

图3是本发明实施例的染色体交叉示意图；

图4是本发明实施例的染色体变异示意图。

具体实施方式

土地资源质量评价因子级别划分问题本质上属于聚类问题。聚类是一种将一组对象根据其某种特性进行分类的过程。常用的聚类算法有K-均值聚类方法、K-中心聚类法等。上述方法的主要特点都在于通过迭代搜索K个级别的类别中心，再比较待分类对象和各类中心之间的相似程度，并将其和最相似的类中心归为一类。其中，对象和类中心的相似程度通常通过计算对象和类中心的某类指标之间的差值进行衡量。由于聚类的基本思想是要达到“物以类聚”的目的，基本要求是“类内对象差距最小化，类间对象差距最大化”。因此，聚类过程就可以转换为寻找最优聚类中心的过程。遗传算法通过模拟生物进化过程中的“适者生存，优胜劣汰”规则，能够实现对优化问题全局最优解的搜索，因而也被广泛应用于聚类、分类问题的研究。采用遗传算法解决土地资源质量评价因子级别划分问题的本质就是评价因子规模指数类中心的优化问题。

本发明技术方案可采用计算机软件技术实现自动运行流程。以下结合附图和实施例详细说明本发明技术方案。实施例设计的基于遗传算法的土地资源质量评价因子级别划分方法，具体实现过程如下：

步骤1，输入每个评价因子的规模指数，规模指数是取值范围为[0-100]的实数。

规模指数用于反映某一类评价因子(如商服中心)的规模大小，通常由一系列指标(如商服中心的营业额等)综合计算得到，其计算方法非本发明的关注重点，具体可参见相关的土地评价规程。具体实施时，可以预先计算规模指数，作为参数输入。

步骤2，设染色体种群规模为M，染色体的基因位长度为K，第i个基因位上存储第i个级别的中心规模指数，i的取值为1、2...K；采用随机的方式生成M个染色体，形成初始的染色体种群；随机生成的约束条件是每个基因位上的中心规模指数是取值范围为[0-100]的实数。K值根据具体待划分的级别而定，可由用户预先输入。

实施例将土地资源评价因子级别划分问题(因子级别划分方案)转换为计算机算法可识别的数据结构(染色体)，即每一个染色体即对应一种因子级别划分方案，通过优化染色体寻找最优的因子级别划分方案。

设需要将N个商服中心根据规模指数划分成K个级别，则采用遗传算法对其进行级别划分的基本思想就是对K个级别的中心规模指数进行优化。在土地资源质量评价因子级别划分问题中，各评价因子的规模指数取值范围通常是[0-100]。因此，故染色体采用实数编码，其长度为K，每个基因位上的值分别代表其中一个级别的中心规模指数，染色体各基因位上的取值范围也设置为[0-100]。初始的染色体种群中，各染色体的每个基因位上的值由计算机生成的随机数进行填充。

原理见附图2，待分级的评价因子对象集中共有N个评价因子，评价因子1、2、3、4、5、6、7、8、9...N将分到K个级别，具体划分根据每个级别的中心规模指数实现，而K个级别的中心规模指数从级别1、2、3...K存储在染色体的第1、2、3...K个基因位上。

步骤3，对当前的染色体种群中各染色体分别进行染色体适应度评价。群中的每个染色体对应一种评价因子级别划分方案。在进行染色体适应度值计算时需要依次执行以下步骤。

步骤3.1，针对每个染色体所存储的各级别中心规模指数，按照最小距离原则和步骤1输入的规模指数，将各评价因子划分到距离最近的一个级别中。

确定各评价因子归属的级别，具体方法是，分别计算当前待分级评价因子的规模指数与K个类别的中心规模指数的差值，找出与其差值最小的类别，将其归为该类。

步骤3.2，采用适应度函数评价各染色体的适应度，则可得到N个染色体的适应度f。

通常在对分类(分级)结果进行评价时，主要采用误差平方和进行度量，各级别的误差平方和越小，则分类结果越好。其中误差平方和的计算方式见下式：

$>E=\underset{i=1}{\overset{K}{\Sigma }}\underset{j=1}{\overset{J}{\Sigma }}{(x_j-c_i)}^2$>式2

根据土地资源评价因子级别划分的需求，设置遗传算法中染色体的评价函数，染色体的适应度值越大，则染色体(问题对应的解)越优。评价因子级别划分的基本要求是级别内因子对象的差别最小化，级别间的差别最大化。因此实施例评价某一染色体(因子级别划分方案)的优劣可以通过计算为各级别内因子与级别中心的误差平方和得到。由此实施例的遗传算法适应度函数(fitness function)如下：

$>f=1/\underset{i=1}{\overset{K}{\Sigma }}\underset{j=1}{\overset{J}{\Sigma }}{(x_j-c_i)}^2$>式1

式1中各符号含义与式2一致，c_i表示第i个级别的中心规模指数，J为第i个级别中评价因子的总数，x_j为第i个级别中第j个评价因子的规模指数。

步骤4，选择，包括根据染色体适应度值从当前的染色体种群中随机选择染色体，选择出的染色体个数记为n。

实施例从父代中选择适应度较高的个体产生下一代的新种群，从而确保优良个体能够存活到下一代，其中在对个体进行选择时，首先按照式3计算当前染色体种群中各染色体被选中的概率；对于给定的染色体，由计算机产生一个随机数rnd，若rnd的值大于该染色体的选择概率p_t，则该染色体不被选中，若小于或等于该染色体的选择概率p_t，则该染色体被选中。

$>p_t=\frac{f_t}{\underset{t=1}{\overset{M}{\Sigma }}{f}_t}$>式3

式中：p_t为染色体t被选中的概率，f_t为染色体t的适应度，M为染色体种群中染色体的个数，t的取值为1，2...M。

步骤5，交叉，包括从步骤4中选择的n个染色体中，按照事先设定的概率Pc随机选择Round(n×Pc)对染色体进行交叉，得到交叉后的染色体种群，其中Round为取整数操作；对一对染色体执行交叉时，在染色体上随机确定一个交叉点，这对染色体在交叉点处互相交换编码。

实施例根据事先设定的交叉概率Pc(取值为0-100％之间的百分数)，从n个随机选择出Round(n×Pc)对染色体进行交叉，即每次都从这n个染色体中随机的选择出1对，一共选择n*pc次。对于交叉的染色体个体，首先随机确定一个交叉点，进行交叉的染色体对在交叉点处互相交换编码，得到交叉后的2个新的染色体，从而更新了种群。

实施例从染色体种群中按照预设的概率Pc随机的选择出一对染色体进行交叉操作时，交叉的方法是：1)在染色体中，随机产生一个交叉点C(其中C的取值范围是[1，K-1])；2)2个染色体互相交换交叉点前的结构，从而得到2个新的染色体。其基本原理见附图3，交叉点为4，即染色体2的第1、2、3、4个基因位与染色体1的第1、2、3、4个基因位进行数值交换，而第5、6...K个基因位保存不变，第4位与第5位之间就是随机交叉点。执行染色体交叉操作是遗传算法产生新的染色体的主要方式，其执行效率和性能直接决定了遗传算法的搜索能力。

步骤6，变异，包括对步骤5所得交叉后的染色体种群中的每个染色体，将每个基因位根据事先设定的概率Pm随机确定该基因位是否进行变异，若执行变异，则该基因位上的数值更改为一个随机生成的[0-100]的实数值，得到变异后的染色体种群。

变异是将染色体上某个基因位上的值随机改成其他值的过程。在进行变异操作时，各染色体上的基因位均按照预设的概率Pm随机确定该基因位是否进行变异。基本操作过程是：遍历染色体上的每一个基因位，在每个基因位置随机生成一个随机数，若随机数小于或等于变异概率Pm，则该基因位执行变异，否则不变异。基本原理见附图4，随机确定第4个基因位进行变异，第4位就是随机变异点。

步骤7，判断是否满足终止条件，不满足则返回步骤3继续对染色体种群进行进化，直至满足终止条件，得到最优的评价因子分级结果。

终止条件可在程序执行前进行预先设置。为防止算法过早终止得不到最优解，或陷入停滞后依然长时间运行，浪费计算时间，本实施例执行时预设3种终止条件。当算法运行满足其中任意1条时即可退出。终止条件依次为：

1)最大运行代数，即运行到预设的代数时退出，可设置一个较大的运行代数，如1000代；

2)最长运行时间，根据计算机软硬件环境及数据规模进行设置，可设置一个较长的运行时间，如2个小时等；

3)进化停滞条件，即种群连续y代最优解的适应度值差值小于预设的阈值时，认为进化陷入停滞，结束进化。可设计程序为，每次步骤6之后对当前的染色体种群中各染色体分别进行染色体适应度评价计算，具体实现可参见步骤3；然后计算最高适应度与上一代染色体种群中最高适应度的差值，连续y代小于预设的阈值时停止返回步骤3。其中y的取值可有本领域技术人员自行设置，建议取值范围为10-30代。代与代之间最优解适应度差的判断阈值通常需要结合特定的问题进行设置。在采用本条件时，步骤8可以不必再重复执行计算，直接输出最终的评价因子级别划分方案。

具体实施时，本领域技术人员可以自行设计程序来判断是否满足终止条件，本发明不予赘述。

步骤8，对当前的染色体种群中各染色体分别进行染色体适应度评价，得到划分结果，包括以下步骤，

步骤8.1，针对每个染色体所存储的各级别中心规模指数，按照最小距离原则和步骤1输入的规模指数，将各评价因子划分到距离最近的一个级别中；

步骤8.2，采用适应度函数评价各染色体的适应度，适应度函数如式1，

$>f=1/\underset{i=1}{\overset{K}{\Sigma }}\underset{j=1}{\overset{J}{\Sigma }}{(x_j-c_i)}^2$>式1

式中，c_i表示第i个级别的中心规模指数，J为第i个级别中评价因子的总数，x_j为第i个级别中第j个评价因子的规模指数；

步骤8.3，将适应度最高的染色体作为最优的评价因子分级划分方案，将步骤8.1中针对适应度最高的染色体划分各评价因子的结果输出以种群中适应度值最高的染色体作为最终的评价因子级别划分方案。

步骤8.1和步骤8.2与步骤3.1和3.2分别实现方式一致，不予赘述。根据步骤8.2的计算结果，得到最优的评价因子分级划分方案，以此分别计算待分级评价因子对象的规模指数和K个类中心规模指数的差值，将其归入与其差值最小的一类。至此，土地资源质量评价因子级别划分过程结束。由于步骤8.1已经针对适应度最高的染色体进行了分类。此时输出相应分类结果即可实现解码。

采用遗传算法进行土地资源质量评价因子级别划分时，算法的关键参数设置是否合理影响算法的性能和运行结果的准确度，建议具体实施时涉及参数及建议的参数设置如下：

  参数  参数描述  建议取值  M  种群规模  建议取值50-200  Pc  交叉概率  建议取值范围0.4-0.99  Pm  变异概率  建议取值范围0.005-0.01  T  进化代数  建议取值范围100-1000

为便于了解本发明效果起见，以对某地的城镇土地资源质量评价为例进行说明。需要将其中的22个商服中心(采用ID标记)因子划分为4个级别分别计算因子的影响范围与作用强度，其中待分级的因子对象及规模指数如下：

  ID  规模指数  ID  规模指数  ID  规模指数  1  33.1  9  59.1  17  15.4  2  37.8  10  30.7  18  23.2  3  30.7  11  22.0  19  23.6  4  17.0  12  24.1  20  16.5  5  20.1  13  21.3  21  60.3  6  14.2  14  13.7  22  52.0  7  31.9  15  10.2  8  66.2  16  12.8

在计算机中编写程序实施以下步骤：

(1)参数设置，设置种群规模为100，交叉率为0.5，变异率为0.008，进化代数为200代。

(2)编码，采用实数编码，构建长度为4的初始的染色体群体。

(3)适应度函数及约束条件设计，采用式(1)作为适应度函数，各基因位的取值为[1-100]；

(4)按照上述步骤4～7设计的流程依次执行染色体的评价、选择、交叉、变异等操作，最终得到评价因子分级结果，解码后结果如下：

  级别  中心规模指数  因子个数  1  89.6  4  2  46.8  5  3  31.1  6  4  19.5  7

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。例如，本发明技术人员可以根据具体精度要求自行设定级别划分方案；在不影响结果的前提下，具体执行步骤顺序可以调整。