2023, Vol. 43文章信息
- 王昊煜, 高培超, 谢一茹, 宋长青, 王元慧
- WANG Haoyu, GAO Peichao, XIE Yiru, SONG Changqing, WANG Yuanhui
- 基于遗传算法的土地利用优化: NSGA-Ⅱ和NSGA-Ⅲ的对比研究
- Land-use optimization based on genetic algorithm: A comparison between NSGA-Ⅱ and NSGA-Ⅲ
- 生态学报. 2023, 43(2): 639-649
- Acta Ecologica Sinica. 2023, 43(2): 639-649
- http://dx.doi.org/10.5846/stxb202103150687
-
文章历史
- 收稿日期: 2021-03-15
- 网络出版日期: 2022-09-23
2. 北京师范大学地理科学学部地理数据与应用分析中心, 北京 100875
2. Center for GeoData and Analysis, Faculty of Geographic Sciences, Beijing Normal University, Beijing 100875, China
土地利用是人类活动的载体, 也是人类活动在地球上最直接的表现。合理、科学、可持续的土地利用规划对人类社会至关重要[1]。土地利用规划是将不同的土地利用类型分配到一个区域内特定空间单元的过程[2]。这样的分配过程涉及不同土地利用人群(例如政府、农民、居民和商家)的多种且通常是相互矛盾的需求, 所以土地利用规划已成为一个多目标、甚至往往为超多目标优化问题[3]。该问题的求解异常复杂, 体现在两大方面：通常涉及大量的变量, 并且很多问题中都包含非线性目标, 这都使得土地利用优化非常复杂; 往往涉及空间属性, 局部区域的变动可能会对周围甚至更远的地方产生影响[4—5]。
为解决上述问题, 学者们做出了持久的努力, 引入了多种算法。最先被引入的是线性规划法[6], 通过对多目标问题中的每一个目标赋予权重, 然后计算加权和来将多目标优化转换为单目标优化。然而, 线性规划模型无法处理非线性问题和土地利用类型之间的空间相互作用, 所以对于复杂的土地利用优化问题并不适用[7]。此外, 在为每个目标赋予权重时, 往往会加入规划者的主观判断, 降低了优化的科学性。在这种情况下, 启发式算法被引入土地利用优化[8—10], 例如模拟退火算法[11—13]、遗传算法[14]、蚁群算法[15—17]、粒子群算法等[18—20]。其中遗传算法受到了广泛的关注和使用[21—24]。
遗传算法始于20世纪70年代。它是通过模仿自然界中生物进化过程和机制来求解极值问题的一类启发式算法。遗传算法采用适应度函数控制搜索的方向, 不受目标函数连续可微的限制, 并且从一个种群出发, 同时处理多个个体, 降低了陷入局部最优风险[25—26]。而遗传算法的种群进化特征还使其越来越多地被应用于解决多目标问题。
非支配排序遗传算法(nondominated sorting genetic algorithm, NSGA)是由N. Srinivas和K. Deb等于1994年提出的一种基于Pareto前沿的多目标遗传算法[27]。在NSGA的基础上, Deb等又分别于2002年和2014年提出了改进后的NSGA系列第二代[28]和第三代[29]算法(NSGA-Ⅱ, NSGA-Ⅲ)。该系列算法的核心思想在于通过非支配排序和控制种群多样性来选择最优个体。其中, NSGA-Ⅱ算法是该系列中最流行的、被使用范围最广的, 而NSGA-Ⅲ则是最近被提出的、最先进的算法。在土地利用优化领域中, NSGA-Ⅱ算法已经得到了广泛的应用。例如, Shaygan等[30]设计了四目标土地利用优化模型并采用NSGA-Ⅱ算法求解。有的学者对NSGA-Ⅱ进行了改进, 使其更适用于土地利用优化问题。例如, Mohammadi等[31]选择了五个目标进行土地利用优化, 并基于此重新设计了NSGA-Ⅱ算法的算子; Cao等[32]对北京市通州区设计了三目标土地利用优化模型, 利用改进的NSGA-Ⅱ算法进行求解。此外, 有的学者对NSGA-Ⅱ算法进行了对比研究。Gao等[33]设计了一套多目标优化算法评价标准并对两种改进型NSGA-Ⅱ算法进行了评估。Song等[8]以NSGA-Ⅱ为多目标遗传算法的代表与多目标模拟退火算法和多目标粒子群算法进行了对比。由于NSGA-Ⅲ提出时间较晚, 将其用于土地利用优化的研究暂时还比较少。Li等[34]利用NSGA-Ⅲ对11种生态系统服务进行了优化; Maleki等[35]建立了一个五目标土地利用优化模型, 并改进NSGA-Ⅲ算法对其进行求解。NSGA-Ⅲ算法在解决实际土地利用问题时的性能还没有得到充分的检验。
随着技术的发展, 优化技术在土地利用规划中的应用逐渐深入。但目前通过优化技术得到的客观规划结果通常用来为规划者提供参考, 难以完全取代规划者的主观设计。而对优化算法的评价可以为规划者提供更加直观的参考。虽然当前已有对不同启发式土地利用优化算法的对比评价, 但都局限于多目标优化算法, 关于超多目标优化算法的关注和评价非常欠缺。由于优化算法难以清晰、完整地展示规划过程, 因此需要根据算法原理分析其在实际规划中的合理性。此外, 优化结果作为算法实际应用效果最直接的表现, 是评价算法时需要考虑的重要因素。
本文将对NSGA系列中最流行的算法NSGA-Ⅱ和最先进的算法NSGA-Ⅲ进行对比分析。首先从算法原理出发进行理论分析。然后以拉萨市为研究区, 设计土地利用优化问题进行实验。根据一套科学合理的算法评估框架对实验结果进行分析, 讨论二者的优势和不足。
1 NSGA-Ⅱ和NSGA-Ⅲ的理论对比 1.1 NSGA-Ⅱ和NSGA-Ⅲ的基本框架NSGA-Ⅱ和NSGA-Ⅲ都是多目标遗传算法。遗传算法是一种通过模拟自然选择和遗传机理来寻找最优解的启发式算法。它从一个包含多个初始解(遗传算法中解又被称为个体)的种群出发, 根据解的优劣为每一个解赋予适应度值。然后模仿优胜劣汰的自然法则, 选择适应度高的个体进行交配产生子代。而子代个体有一定的概率发生交叉和变异, 从而丰富种群的多样性。通常情况下, 两个父代个体交配会生成两个子代, 以保证每代的种群大小不变。子代种群继续循环上述过程, 直到某一代种群满足给定的终止条件, 则一次优化完成。
NSGA-Ⅲ是在NSGA-Ⅱ的基础上改进得到的, 它们的基本框架是一致的。基本框架如图 1所示。对于种群大小为N的第t代种群Pt, 首先按照基本的遗传算法的流程进行选择、交叉、变异生成子代种群Qt。接下来将Pt和Qt合并, 记为Rt, 并从有2N个个体的Rt中筛选出N个个体作为下一代种群Pt+1。该筛选过程分为两大步：
|
| 图 1 NSGA-Ⅱ和NSGA-Ⅲ的基本框架 Fig. 1 The basic framework of NSGA-Ⅱ and NSGA-Ⅲ NSGA-Ⅱ：第Ⅱ代非支配排序遗传算法; NSGA-Ⅲ：第Ⅲ代非支配排序遗传算法 |
(1) 将Rt中的个体进行非支配排序。所谓的非支配排序, 就是给所有的解赋予一个非支配等级。对于一个解来说, 如果在解集中不存在所有目标函数值都优于它的解, 则这个解被称为非支配解。非支配解的非支配等级为1, 去掉这些等级为1的解后种群中的非支配解的非支配等级为2, 以此类推, 直至所有解都被赋予非支配等级。将非支配等级为i的解的集合记为Fi。然后从F1开始按非支配等级从小到大的顺序将Rt中的个体选入下一代Pt+1, 直到首个使得Pt+1的个体数大于N的集合Fj。
(2) 在Fj中选择种群密度最小的几个个体进入Pt+1, 使得Pt+1中的个体数达到N。
1.2 NSGA-Ⅱ和NSGA-Ⅲ的差异NSGA-Ⅱ和NSGA-Ⅲ的差异在于筛选的第2步, 即控制Fj的种群多样性的方法不同。NSGA-Ⅱ采用计算拥挤距离(crowding distance)的方法[28], 其思想为计算同一非支配等级中每一个个体在每一个维度上左右相邻两解的距离和。假设有m个目标函数, 则目标空间为的维数为m。对于Fj中的一个个体来说, 在每一个维度上, 都有一个或两个相邻的个体。如果只有一个相邻个体, 则认为该个体位于Fj的边缘。如果每一个维度上都有左右两个相邻个体, 则为非边缘个体。对于非边缘个体, 可以计算每一个维度上两个相邻个体在该维度上的归一化距离。m个归一化距离的和即为拥挤距离。对于边缘个体, 拥挤距离为无穷大。拥挤距离越大, 说明该个体周围的解密度越小, 种群多样性就越大。NSGA-Ⅱ选择拥挤距离更大的个体进入下一代。
而NSGA-Ⅲ则基于归一化超平面上均匀分布的参考点进行选择[29]。以最小化为例, 首先将m维目标空间的坐标系平移至新的原点, 该原点为每个目标函数的最小值。然后在这个新的坐标系下建立一个m-1维的超平面。这个超平面需要m个解确定。其中第i个解的确定方式为：非支配等级小于j的解中, 先计算每一个解的所有非第i个目标函数值(m-1个)的最大值, 然后选择这个最大值最小的解。在由这m个点确定的超平面上, 以用户指定的间隔均匀地分布一些参考点。参考点与新原点的确定的直线称为参考线。对于非支配等级小于j的解, 确定与其距离最近的参考线, 称解与j参考点关联。寻找关联解个数最小(记为j)的参考点(记为)。若Fj中不存在解与关联, 则删除该参考点; 否则判断ρj是否为0, 若是, 则选择Fj中距离j最近的解进入下一代, 否则在Fj中随机选择一个与j关联的解进入下一代。
通过对比可以看出, NSGA-Ⅱ主要基于局部的种群密度进行选择。通过控制一个个体周围的空间大小来控制整个种群的多样性。而NSGA-Ⅲ则是通过分布均匀的参考点来控制种群的整体分布。相比之下, NSGA-Ⅱ以每个个体为基准, 考虑相对位置, 由局部控制整体。NSGA-Ⅲ以绝对均匀分布的参考点为基准, 不受个体间相对位置的影响。此外, 由于NSGA-Ⅱ在进行种群多样性计算时涉及相邻个体之间的距离计算, 受维度影响很大。当优化目标数量增多时, 会大大增加算法耗时。
2 NSGA-Ⅱ和NSGA-Ⅲ的实验对比 2.1 研究区选择拉萨作为研究区进行土地利用优化实验。拉萨市位于青藏高原的南部。作为“世界屋脊”和“世界第三极”, 青藏高原在全球气候变化中起着重要作用[36—37]。此外, 拉萨是西藏自治区的首府, 也是西藏最大、最发达的城市。自2000年实施西部大开发战略实施和2006年青藏铁路建成以来, 拉萨经历了工业化、城市化、旅游业的迅速扩张[38]。根据西藏自治区土地利用总体规划, 西藏的土地利用存在开发利用率低、耕地后备资源少、抗风险能力差、开发利用结构不合理、与经济社会发展的矛盾突出五大问题。由于拉萨重要的地理位置和政治经济地位, 处理好拉萨的土地利用是解决这些问题的一个关键。而拉萨的土地利用最突出的问题是实现生态和和社会经济发展的权衡[39]。
2.2 目标函数和约束条件为了对比NSGA-Ⅱ和NSGA-Ⅲ在处理多目标和超多目标(四个及以上目标[29])问题时的差异, 设计两个目标个数不同的土地利用优化实验。基于上面的讨论, 拉萨市土地利用首先要考虑经济效益和生态效益的最大化。此外城市的紧凑性对资源的调配和资源利用效率有重要影响[30]。城市紧凑性反映的是相同类型的土地利用的聚集程度。城市紧凑性越高, 即同种利用类型的地块越聚集, 资源统一调配越方便, 从而资源利用效率也就越高[40—42]。与此同时, 紧凑性高也能减小通勤距离, 从而减轻交通压力, 减少二氧化碳排放。因此提高城市紧凑性对于提高经济效益和生态效益都有积极的影响。由此, 首先构造一个多目标土地利用优化实验(3目标)。
实验一
目标1：总经济效益最大
|
(1) |
式中, M和N分别为研究区域网格的行数和列数, pk为单位地块土地利用类型k的经济效益系数。xijk表示地块(i, j)的土地利用类型, 如果地块(i, j)的土地利用类型为k, 则xijk=1, 否则为0。在本实验中, 经济效益系数选择各土地利用类型单位面积产出的GDP。
目标2：总生态效益最大
|
(2) |
式中, qk为单位地块土地利用类型k的生态效益系数。在本实验中生态效益系数选择各土地利用类型的单位面积生态系统服务价值。
目标3：城市紧凑性最大
|
(3) |
式中, 
除了建立目标函数, 还需要根据实际情况对拉萨市土地利用优化问题设置约束条件。根据拉萨市《土地利用总体规划(2005—2020)》, 应保护耕地, 协调城乡发展。因此耕地面积不应减少。即
|
(4) |
式中, Lagri为土地利用现状的耕地面积。
同时, 在进行土地利用转换时, 势必要有人力、财力等的花费。为避免劳民伤财, 必须要控制土地利用转换的总成本。因此转换成本需要有一个最大限度值。即
|
(5) |
式中, ks表示土地利用现状中地块(i, j)的土地利用类型, cks, k为土地利用类型ks转换为土地利用类型k的转换成本系数。因为不同土地利用类型之间转换的花费涉及太多因素, 不易计算。为了简便起见, 当ks≠k时, 令cks, k=1, 否则为0, 即以发生转变的地块的数量作为转换成本。Ucost为转换成本的上限, 令其等于总地块数的30%, 即所有发生转换的地块的数量不超过30%。西藏地区生态脆弱, 有许多限制开发的生态功能保护区, 理论上这些区域在优化过程中不能发生改变。但根据中国科学院资源环境科学与数据中心发布的中国生态功能保护区范围(https://www.resdc.cn/data.aspx?DATAID=137), 拉萨市内无生态功能保护区, 因此在实际中不受此因素的影响。此外, 为了使优化结果更接近实际情况, 限制水域不发生改变。
谢高地等[43]将生态系统服务划分为食物生产、原材料生产、水资源供给、气体调节、气候调节、净化环境、水文调节、土壤保持、维持养分循环、维持生物多样性、美学景观11个类型。为了测试两种算法在不同目标数量时的表现, 将最大化每一种生态系统服务分别作为一个目标, 替换实验一中的目标2, 并保留其余目标和约束。由此构造一个超多目标土地利用优化实验(13目标)。
实验二
目标1—11：食物生产、原材料生产、水资源供给、气体调节、气候调节、净化环境、水文调节、土壤保持、维持养分循环、维持生物多样性、美学景观11中生态系统服务价值分别最大化
|
(6) |
式中, qlk为第l种生态系统服务效益系数, 即土地利用类型k的单位地块第l种生态系统服务价值。
目标12和目标13分别同(1)式和(3)式, 两个约束条件同(4)式和(5)式。
2.3 数据准备实验采用2018年拉萨市的土地利用类型图作为优化基准(图 2)。其数据来源为中国科学院资源环境科学数据中心(http://www.resdc.cn)。数据分辨率为1km×1km。土地利用类型包括耕地、林地、草地、水域、建设用地和未利用土地6个一级类型以及25个二级类型。为了简化方便, 本研究只考虑6个一级类型。各种土地利用类型面积如表 1所示。
|
| 图 2 拉萨市土地利用图(2018年) Fig. 2 Land use in Lhasa City 2018 |
| 耕地 Cultivated land |
林地 Forest |
草地 Grassland |
水域 Water |
建设用地 Construction |
未利用地 Unused |
|
| 拉萨市 | 1028 | 3520 | 16344 | 2018 | 87 | 6640 |
经济效益系数即各土地利用类型单位面积产出的GDP。它是根据拉萨的GDP和不同土地利用类型对GDP的相对权重确定的。GDP数据来自统计年鉴。相对权重是使用层次分析法通过7个驱动因子确定的, 这7个驱动因子分别为：海拔、坡度、年平均降水量、归一化植被指数、人口密度、人均GDP和与最近道路的距离。
生态效益系数即各土地利用类型的单位面积生态系统服务价值。中国陆地生态系统服务价值空间分布数据集[44], 计算了全国食物生产、原料生产、水资源供给、气体调节、气候调节、净化环境、水文调节、土壤保持、维持养分循环、生物多样性和美学景观共11种生态服务的价值, 以及总生态系统服务价值。以每一种土地利用类型所有地块的总生态系统服务价值平均值作为实验一目标2的生态效益系数, 每一种土地利用类型所有地块的每一类生态系统服务价值平均值分别作为实验二目标1—11的效益系数。
拉萨市的经济效益系数和各生态效益系数如表 2所示。
| 效益 Benefits |
耕地 Cultivated land |
林地 Forest |
草地 Grassland |
水域 Water |
建设用地 Construction |
未利用 Unused |
| 经济Economic | 2.11×106 | 4.81×105 | 8.87×104 | 2.28×106 | 1.44×107 | 0 |
| 生态Ecological | 4371.6 | 13462.3 | 3512.6 | 40679.3 | 0 | 371.4 |
| 食物生产Food supply | 856.23 | 337.11 | 263.68 | 128.59 | 519.83 | 113.08 |
| 原料生产Raw material supply | 793.84 | 483.62 | 380.98 | 128.16 | 472.17 | 163.86 |
| 水资源供给Water supply | 391.27 | 228.95 | 211.89 | 4262.04 | 136.04 | 239.33 |
| 气体调节Air quality regulation | 2449.85 | 1693.39 | 1346.35 | 453.53 | 1441.18 | 602.98 |
| 气候调节Climate regulation | 5739.01 | 4413.96 | 3482.11 | 1129.91 | 3180.49 | 1489.38 |
| 净化环境Waste treatment | 2193.86 | 1543.23 | 1262.52 | 666.62 | 1266.19 | 672.06 |
| 水文调节Regulation of water flows | 4802.12 | 2923.18 | 2639.58 | 48365.11 | 1681.08 | 1970.02 |
| 土壤保持Erosion prevention | 6695.56 | 17431.02 | 14995.88 | 1475.24 | 3368.69 | 9188.12 |
| 维持养分循环Maintenance of soil fertility | 264.57 | 164.39 | 130.33 | 43.93 | 158.24 | 55.66 |
| 生物多样性Habitat service | 2531.90 | 1867.30 | 1488.72 | 571.75 | 1385.38 | 669.39 |
| 美学景观Cultural & amenity service | 1170.42 | 828.95 | 661.58 | 294.32 | 617.93 | 300.29 |
为了保证对比的可靠性, 对实验所用的NSGA-Ⅱ和NSGA-Ⅲ算法选取相同的选择、交叉、变异算子。此外, 种群的初始化算子对于算法的表现有至关重要的影响。实验采用了一种基于先验知识的初始化算子, 将初始种群中10%的个体设置为土地利用现状, 其它个体随机生成[11]。
基于Python中的多目标优化模块pymoo实现NSGA-Ⅱ和NSGA-Ⅲ算法。在pymoo模块中, 默认种群大小与参考点个数一致时优化效果最好。根据Deb.K等的算法设计[27—28], 综合考虑运算效率, 对于3目标优化问题(实验一), 设置种群大小为153(即参考点个数), 对于13目标优化问题(实验二), 设置种群大小为104(即参考点个数)。最大进化代数为250, 交叉概率为0.9, 变异概率为3.3×10-5。以最后一代种群作为实验得到的最优解。
3 结果与分析 3.1 分析策略为了科学地分析NSGA-Ⅱ和NSGA-Ⅲ的实验结果, 需要一套合理的评价体系。Gao等[33]提出了一个多层次评价体系, 用于评估基于Pareto前沿的算法进行土地利用优化时的性能。在这个体系包括4个层次, 分别是原则层、宏观标准层、微观标准层、指标层。原则层为算法的可用性, 指的是一个产品能被特定用户用于特定目标的程度, 它包括有效性、效率和满意度三个宏观标准。有效性指用户实现指定目标的准确性和完整性, 在多目标优化中为确定Pareto前沿的能力。效率指与用户实现目标的准确性和完整性相关的资源消耗, 在多目标优化中为确定Pareto前沿的资源消耗。满意度指用户对产品的积极态度, 在多目标优化中为用户角度解的优点。每个宏观标准又分别包括两个微观标准。有效性对应的微观标准包括结果是否来自Pareto前沿, 即结果的质量, 和结果是否具有代表性, 即结果的多样性; 效率包括算法运行花费的时间和空间; 满意度包括和现状相比结果优化的程度和约束的违反程度。每一个微观标准都对应一个指标。结果的质量对应指标Q, 其计算方法为最优种群中每一个目标函数的平均函数值比初始种群提高的百分比之和, 反映了和初始种群相比最优种群目标函数提高的程度。结果的多样性对应指标D, 其计算方法为最优种群中每一个目标函数的香农熵比初始种群提高的百分比之和, 反映和初始种群相比, 最优种群的多样性提高程度。时间花费对应指标T, 即运行一次程序花费的时间, 空间花费对应指标R, 用来计算运行过程中额外存档的个体数。优化的程度对应指标O, 计算的是最优种群中每个个体每一个目标函数相比现状提高百分比之和的最大值, 反映了算法对土地利用现状的提升程度。约束的违反程度对应指标V, 反映了每个约束条件被超出的百分比之和。各指标的具体计算公式见文献[33]。各层次关系如表 3所示。
| 原则层Principle | 可用性Usability | ||||||
| 宏观标准层 Macro-criteria |
有效性 | 效率 | 满意度 | ||||
| 微观标准层 Micro-criteria |
结果的质量 | 结果的多样性 | 时间花费 | 空间花费 | 优化的程度 | 约束的违反程度 | |
在本次实验中, 由于两个算法的存档方式(对解的保存方式)是一致的, 所以指标R的大小是相同的, 因此不再进行对比。对于每个实验, 计算NSGA-Ⅲ相比NSGA-Ⅱ各指标提高(或降低)的百分比, 结果如表 4。
| 结果的质量 Quality of results |
结果的多样性 Diversity of results |
时间花费 Time cost/efficiency |
优化的程度 Degree of optimization |
约束的违反程度 Violation of constraints |
|
| 实验一Experiment Ⅰ | 4.1% | -10% | 0.6% | 0.3% | 0 |
| 实验二Experiment Ⅱ | -6.3% | -5.68% | -0.5% | -13% | 0 |
通过对比可以看出, 对于多目标优化, NSGA-Ⅲ在结果的质量和优化的程度方面优于NSGA-Ⅱ, 而在结果的多样性和时间消耗方面逊于NSGA-Ⅱ。对于超多目标优化, NSGA-Ⅲ算法在时间消耗上优于NSGA-Ⅱ, 但其他指标的表现都不如NSGA-Ⅱ。这说明在进行超多目标优化时, NSGA-Ⅲ相比NSGA-Ⅱ有时间优势。对比实验一和实验二的结果, 可以看出随着目标数量的增长, NSGA-Ⅲ对种群多样性保护能力在提高。这反映了NSGA-Ⅱ和NSGA-Ⅲ在种群多样性保护方面的差异, 在目标数较少时, NSGA-Ⅱ种群多样性保护的效果和时间均占优, 但随着目标数量的增多, NSGA-Ⅲ的表现在提高, 并可以超过NSGA-Ⅱ。这与理论分析的结果是一致的。
为了对比两种算法的应用价值, 对于两个实验, 分别选择每种算法求解出的一个最优个体进行分析。由于理论上最后一代的所有个体都是最优解, 逐一对比比较耗时, 需要筛选出最具代表性的方案参与对比。因此, 选择所有目标最平均的最优个体, 即该个体所有目标函数值的方差(先对所有目标函数值进行归一化再求方差)最小。筛选的结果如图 3和图 4所示。
|
| 图 3 实验一优化结果 Fig. 3 Optimization result of experiment Ⅰ |
|
| 图 4 实验二优化结果 Fig. 4 Optimization result of experiment Ⅱ |
对于多目标优化实验一, 两个最优方案的空间分布整体差异不大, 这是对转换成本进行约束的结果。在局部都出现了零散分布的地块, 但相较之下, NSGA-Ⅲ生成的最优方案中, 建设用地以2个以上地块连片出现的情况多于NSGA-Ⅱ的最优方案。考虑到本研究采用的栅格数据分辨率为1km×1km, NSGA-Ⅲ的结果更接近实际情况。
对于超多目标优化实验二, 最优方案整体同样差异不大, 仅是出现零散分布地块。但对比两种算法生成的最优个体, 可以看出NSGA-Ⅲ生成最优方案的空间杂乱程度低于NSGA-Ⅱ。因此, NSGA-Ⅲ产生的最优方案比NSGA-Ⅱ的实用价值更高。通过上述分析, 在当前的实验设定下, 虽然NSGA-Ⅲ在算法的数值结果的表现上不如NSGA-Ⅱ, 但其表现出了更高的应用价值。
4 结论本文对土地利用优化领域常用的多目标遗传算法NSGA系列算法中最流行的版本NSGA-Ⅱ和最先进的版本NSGA-Ⅲ进行了对比。通过分析优化原理的异同, 从理论上对两个算法进行对比。以拉萨市为研究区, 设计多目标(3目标)和超多目标(13目标)土地利用优化实验, 并采用四层架构、六大指标, 对两个算法从实验上进行对比。
理论对比发现, NSGA-Ⅱ和NSGA-Ⅲ的区别在于如何控制种群的多样性, 选择种群密度小的个体进入子代。NSGA-Ⅲ以固定位置的参考点为基准衡量种群密度, 相比以每个个体为基准进行衡量的NSGA-Ⅱ, 更易控制全局多样性, 避免陷入局部均匀全局紧凑的情况。NSGA-Ⅱ中种群多样性的计算受维度影响大, 当维度增加时, 计算繁琐, 耗时大, 减慢搜索过程。
实验对比发现, 两个算法在不同指标上的表现各有优势。与NSGA-Ⅱ相比, 在多目标优化中, NSGA-Ⅲ在结果的质量和优化的程度方面有优势, 而随着目标函数的增加, NSGA-Ⅲ相比NSGA-Ⅱ会在运算时间上占据优势, 且种群多样性保护的效果也在提高。根据对实验得到的最优个体的对比分析, NSGA-Ⅲ生成的最优个体在实际应用价值方面高于NSGA-Ⅱ。因此NSGA-Ⅲ算法在土地利用优化领域具有很大的潜力, 能为规划者提供更有价值的参考。
未来本文的结果可辅助实证研究, 为设计更完善、更接近实际情况的土地利用优化模型提供参考, 并可依据本文得出的NSGA-Ⅱ和NSGA-Ⅲ的特点, 选择合适的算法进行优化, 从而得到科学合理的土地利用规划方案, 为决策提供支持。此外, 还可以进一步对比两个算法的表现, 设计更多不同目标函数下的实验, 为解决土地利用优化实际问题提供更准确的参考。
致谢: 感谢北京师范大学地理科学学部地理数据与应用分析中心地学高性能计算平台支持。| [1] |
谢一茹, 高培超, 王翔宇, 宋长青, 程昌秀, 叶思菁, 沈石. 经济发展预期下的粮食产量与生态效益权衡——黑龙江省土地利用优化配置. 北京师范大学学报(自然科学版), 2020, 56(6): 873-881. |
| [2] |
Stewart T, Janssen R, Herwijnen M. A genetic algorithm approach to multiobjective land use planning. Computers & Operations Research, 2004, 31(14): 2293-2313. |
| [3] |
Huang B, Zhang W T. Sustainable land-use planning for a downtown lake area in central China: multiobjective optimization approach aided by urban growth modeling. Journal of Urban Planning and Development, 2014, 140(2): 04014002. DOI:10.1061/(ASCE)UP.1943-5444.0000186 |
| [4] |
宋长青, 程昌秀, 史培军. 新时代地理复杂性的内涵. 地理学报, 2018, 73(7): 1204-1213. |
| [5] |
程昌秀, 史培军, 宋长青, 高剑波. 地理大数据为地理复杂性研究提供新机遇. 地理学报, 2018, 73(8): 1397-1406. |
| [6] |
Schlager K. A land use plan design model. Journal of the American Institute of Planners, 1965, 31(2): 103-111. DOI:10.1080/01944366508978151 |
| [7] |
宋长青, 程昌秀, 杨晓帆, 叶思菁, 高培超. 理解地理"耦合"实现地理"集成". 地理学报, 2020, 75(1): 3-13. |
| [8] |
Song M J, Chen D M. A comparison of three heuristic optimization algorithms for solving the multi-objective land allocation (MOLA) problem. Annals of GIS, 2018, 24(1): 19-31. DOI:10.1080/19475683.2018.1424736 |
| [9] |
Liu X P, Lao C H, Li X, Liu Y L, Chen Y M. An integrated approach of remote sensing, GIS and swarm intelligence for zoning protected ecological areas. Landscape Ecology, 2012, 27(3): 447-463. DOI:10.1007/s10980-011-9684-1 |
| [10] |
黎夏, 刘小平, 李少英. 智能式GIS与空间优化. 北京: 科学出版社, 2010, 30-35. |
| [11] |
Santé-Riveira I, Boullón-Magán M, Crecente-Maseda R, Miranda-Barrós D. Algorithm based on simulated annealing for land-use allocation. Computers & Geosciences, 2008, 34(3): 259-268. |
| [12] |
Mohammadi M, Nastaran M, Sahebgharani A. Development, application, and comparison of hybrid meta-heuristics for urban land-use allocation optimization: Tabu search, genetic, GRASP, and simulated annealing algorithms. Computers, Environment and Urban Systems, 2016, 60: 23-36. DOI:10.1016/j.compenvurbsys.2016.07.009 |
| [13] |
Li X, Ma X D. An improved simulated annealing algorithm for interactive multi-objective land resource spatial allocation. Ecological Complexity, 2018, 36: 184-195. DOI:10.1016/j.ecocom.2018.08.008 |
| [14] |
王昊煜, 高培超, 谢一茹, 宋长青, 程昌秀, 叶思菁. 基于改进型NSGA-Ⅱ算法的西宁市土地利用多目标优化. 地理与地理信息科学, 2020, 36(6): 84-89. DOI:10.3969/j.issn.1672-0504.2020.06.013 |
| [15] |
Liu Y L, Tang D W, Kong X S, Liu Y F, Ai T H. A land-use spatial allocation model based on modified ant colony optimization. International Journal of Environmental Research, 2014, 8(4): 1115-1126. |
| [16] |
Mi N, Hou J W, Mi W B, Song N P. Optimal spatial land-use allocation for limited development ecological zones based on the geographic information system and a genetic ant colony algorithm. International Journal of Geographical Information Science, 2015, 29(12): 2174-2193. DOI:10.1080/13658816.2015.1070411 |
| [17] |
Liu X P, Li X, Shi X, Huang K N, Liu Y L. A multi-type ant colony optimization (MACO) method for optimal land use allocation in large areas. International Journal of Geographical Information Science, 2012, 26(7): 1325-1343. DOI:10.1080/13658816.2011.635594 |
| [18] |
Liu X P, Ou J P, Li X, Ai B. Combining system dynamics and hybrid particle swarm optimization for land use allocation. Ecological Modelling, 2013, 257: 11-24. DOI:10.1016/j.ecolmodel.2013.02.027 |
| [19] |
Masoomi Z, Mesgari M, Hamrah M. Allocation of urban land uses by multi-objective particle swarm optimization algorithm. International Journal of Geographical Information Science, 2013, 27(3): 542-566. DOI:10.1080/13658816.2012.698016 |
| [20] |
Li F X, Gong Y, Cai L Y, Sun C Y, Chen Y M, Liu Y X, Jiang P H. Sustainable land-use allocation: a multiobjective particle swarm optimization model and application in Changzhou, China. Journal of Urban Planning and Development, 2018, 144(2): 04018010. DOI:10.1061/(ASCE)UP.1943-5444.0000425 |
| [21] |
Jenerette D, Wu J G. Analysis and simulation of land-use change in the central Arizona-Phoenix region, USA. Landscape Ecology, 2001, 16(7): 611-626. DOI:10.1023/A:1013170528551 |
| [22] |
Porta J, Parapar J, Doallo R, Rivera F, Santé I, Crecente R. High performance genetic algorithm for land use planning. Computers, Environment and Urban Systems, 2013, 37: 45-58. DOI:10.1016/j.compenvurbsys.2012.05.003 |
| [23] |
Li X, Parrott L. An improved genetic algorithm for spatial optimization of multi-objective and multi-site land use allocation. Computers, Environment and Urban Systems, 2016, 59: 184-194. |
| [24] |
Song M J, Chen D M. An improved knowledge-informed NSGA-Ⅱ for multi-objective land allocation (MOLA). Geo-Spatial Information Science, 2018, 21(4): 273-287. DOI:10.1080/10095020.2018.1489576 |
| [25] |
Mirjalili S. Evolutionary algorithms and neural networks. Studies in Computational Intelligence, 2019, 780: 43-55. |
| [26] |
Cao K, Huang B, Wang S W, Lin H. Sustainable land use optimization using boundary-based fast genetic algorithm. Computers, Environment and Urban Systems, 2012, 36(3): 257-269. |
| [27] |
Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 1994, 2(3): 221-248. |
| [28] |
Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. |
| [29] |
Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part Ⅰ: solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601. |
| [30] |
Shaygan M, Alimohammadi A, Mansourian A, Govara S, Kalami M. Spatial multi-objective optimization approach for land use allocation using NSGA-Ⅱ. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2014, 7(3): 906-916. |
| [31] |
Mohammadi M, Nastaran M, Sahebgharani A. Sustainable spatial land use optimization through non-dominated sorting genetic algorithm-Ⅱ (NSGA-Ⅱ): (case study: baboldasht district of Isfahan). Indian Journal of Science and Technology, 2015, 8(S3): 118. |
| [32] |
Cao K, Batty M, Huang B, Liu Y, Yu L, Chen J F. Spatial multi-objective land use optimization: extensions to the non-dominated sorting genetic algorithm-Ⅱ. International Journal of Geographical Information Science, 2011, 25(12): 1949-1969. |
| [33] |
Gao P C, Wang H Y, Cushman S, Cheng C X, Song C Q, Ye S J. Sustainable land-use optimization using NSGA-Ⅱ: theoretical and experimental comparisons of improved algorithms. Landscape Ecology, 2021, 36(7): 1877-1892. |
| [34] |
Li L J, Li G S, Cui L L, He L, Chen Y H. Method for modelling ecological competition based on Pareto optimality: a case study of coastal wetlands in Jiangsu Province, China. Ecological Indicators, 2021, 129: 107946. |
| [35] |
Maleki J, Masoumi Z, Hakimpour F, Coello C. Many-objective land use planning using a hypercube-based NSGA-Ⅲ algorithm. Transactions in GIS, 2021, 609-644. |
| [36] |
Qiu J. China: The third pole. Nature, 2008, 454(7203): 393-396. |
| [37] |
Kuang W H. Seasonal variation in air temperature and relative humidity on building areas and in green spaces in Beijing, China. Chinese Geographical Science, 2020, 30(1): 75-88. |
| [38] |
Huang J, Kang S C, Wang S X, Wang L, Zhang Q G, Guo J M, Wang K, Zhang G S, Tripathee L. Wet deposition of mercury at Lhasa, the capital city of Tibet. Science of the Total Environment, 2013, 447: 123-132. |
| [39] |
王元慧, 王昊煜, 宋长青, 王翔宇, 高培超. 面向区域综合发展的系统动力学研究进展及其在青藏高原的应用. 北京师范大学学报(自然科学版), 2022, 58(1): 153-160. |
| [40] |
高培超, 程昌秀, 叶思菁, 沈石, 张红. 空间玻尔兹曼熵的研究进展与应用. 地理学报, 2021, 76(7): 1579-1590. |
| [41] |
Wang X Y, Gao P C, Song C Q, Cheng C X. Use of entropy in developing SDG-based indices for assessing regional sustainable development: a provincial case study of China. Entropy, 2020, 22(4): 406. |
| [42] |
Gao P C, Wang X Y, Wang H Y, Cheng C X. A correction to the entropy weight coefficient method by Shen et al. for accessing urban sustainability[Cities 42 (2015) 186‐194]. Cities, 2020, 103: 102742. |
| [43] |
Xie G D, Zhang C X, Zhen L, Zhang L M. Dynamic changes in the value of China's ecosystem services. Ecosystem Services, 2017, 26: 146-154. |
| [44] |
左玲丽, 彭文甫, 陶帅, 祝聪, 徐新良. 岷江上游土地利用与生态系统服务价值的动态变化. 生态学报, 2021, 41(16): 6384-6397. |