-
目前，世界上仍然存在较多边界争端[1, 2]。在当今和平与发展的时代主题下，通过武力并不能彻底解决上述问题，相反，谈判划界成为一种可靠有效的手段[3]。随着计算机、GIS及空间决策支持等技术的发展，争议区划界方法由基于纸质地图的手工划界发展到计算机辅助划界，大大提高了划界进程及科学性。目前，陆地边界争议区划界线的自动生成方法主要包括基于二分法的争议区自动分割[4]与基于遗传算法的多目标方案线诱导法[5]。前者能够基于面积比例对争议区进行精确划分，但是没有顾及资源与划界法理(即针对由民族、宗教等因素形成的特殊区域的处理)，而且只能在局部区域考虑到实际地形的影响；后者能够兼顾双方面积比例及划界法理的影响，且可以顾及某方综合资源占有量(简称资源利益)最大化的利益诉求，但是对于实际地形仍然考虑不足且效率不够理想。由于实际地形不仅具有天然的区域分割作用，而且容易管理以及阻挡攻击[6, 7]，因此，需要对陆地边界争议区划界线的自动生成展开进一步研究。
如果选取争议区内部若干地性线作为划界线，并且同时考虑划界法理、双方面积比例及资源利益诉求等约束信息，那么上述问题便可迎刃而解。因此，关键是选取哪些地性线构造划界线，此时即为组合优化问题[8-10]。鉴于此，本文针对模拟退火算法中缓慢退火方式与快速退火方式的优缺点，设计了并行模拟退火机制，将上述两种退火方式相结合，在降温过程中对全局最优解进行快速充分搜索，并通过实验对上述方法的可靠性及性能进行分析。本文以甲乙双方划界为例进行研究(不涉及政治因素)，且甲方具有资源利益最大化诉求。
-
模拟退火算法[11-13]是基于Monte-Carlo迭代求解策略的一种随机寻优算法，根据Metropolis准则对每次迭代结果的接受与否进行判断。其求解过程如下。
1) 设置初始温度Tk，生成初始解Xk，k=0。
2) 重复以下过程，直至接受新解。
(1) 根据当前解Xk生成新解X′，并计算其目标函数值的差值Δf= f(X′)-f(Xk)；
(2) 按照概率min{1，exp(-Δf/Tk)}>random[0, 1]接受新解，其中，random[0, 1]是介于0和1之间的随机数；
3) 进行降温，令T+1=F(Tk)，Xk+1=X′，k←k+1。若满足收敛条件，则求解过程结束，否则执行步骤2)。其中，F(Tk)为降温函数。
在退火过程中，Metropolis准则不仅接受优质解，且以概率exp(-Δf/Tk)接受劣质解。因此，只要初始温度足够高，退火过程足够慢，该算法就可以概率性地跳出局部极值收敛于全局最优解[14]。
-
由于原始地性线(本文主要指山脊、山谷线)并不相交，为了对由其构成的划界线进行评价，需要将目标地性线连接成单条曲线，此处基于栅格地性线中的悬挂特征栅格进行反向追踪，使地性线彼此相连形成地性线网络，具体过程见文献[15]。同时，针对地性线网络构建拓扑关系，并基于划界法理对拓扑关系进行特殊处理。
-
为了便于对划界线进行搜索及编码表示，本文在“链-节点”及“节点-链”拓扑关系的基础上构建了“点-点”一次邻接关系(简称“点-点”邻接关系)，其中，彼此邻接的两个点必须是同一弧段的首末端点。如图 1所示，与点2邻接的点包括点1、3、4，与点6邻接的点只有点5。
图 1 “点-点”邻接关系
Figure 1. Point-Point Adjacency Relationship
“点-点”邻接关系构建过程如下：依次对地性线进行遍历，假设当前地性线为H，在拓扑点容器中根据点坐标查询与H首末点对应的拓扑点对象(图 2)，若不存在，则根据相应点构造新的拓扑点并插入容器中；然后在与H首(末)点相邻接的拓扑点集合(图 2中的arr_Pts数组)中分别将末(首)点对应的拓扑点编号予以保存。
图 2 邻接点类
Figure 2. Adjacency Point Class
由于任何一条地性线都可以由它的首末端点来唯一标识，因此，图 1中由地性线a、c、e、g构成的划界线可以由编码“1-2-4-5-6”来表示。与编码过程相对应，在解码阶段，可以根据点对1与2、2与4、4与5、5与6查询相应的地性线获得划界线的定位信息。
-
根据划界法理可知，由于历史、民族、宗教以及军事战略目的等因素，争议区中往往存在不可分割区域(如民族聚居地)和双方的必争区域(如战略高地)[5]。在划界过程中，应该确保划界线避开上述特殊区域，并将必争区域划归相应国家。为了简化问题并提高划界线生成效率，本文首先计算出必争区域与相应国家之间的最短直线路径P，然后查询与P及上述两种特殊区域相交的地性线集合R，并将R中的每条地性线“断开”(将相应拓扑点的邻接关系予以解除)，如图 3所示。此时，基于“点-点”邻接关系搜索划界线时，能够避开地性线集合R，实现对上述两种区域的正确处理。
图 3 顾及划界法理的特殊处理
Figure 3. Extra Disposal of Point-Point Adjacency Relationship Based on Delimitation Laws
-
初始解生成是指基于“点-点”邻接关系随机搜索从划界起点到划界终点的有序拓扑点串，其中，划界起点与划界终点是距离双方领土主张线的两交点最近的拓扑点。为了便于对任意两点间的点串进行随机搜索时所遇环路进行有效处理，本文构造了嵌套栈，包含内栈与外栈。外栈由容器mstack与栈顶索引T来模拟，用于存储内栈；内栈用于存储外栈中与其前一个内栈栈顶相关的拓扑点。初始解搜索过程如下(mstack[i]与mstack[i][t]分别为外栈中的第i个内栈及其栈顶)：
1) 利用起点构造内栈并将其插入外栈中，T=0；
2) 判断mstack[T]是否为空：若为空，则弹出mstack[T-1][t]，且将mstack[T]从外栈中弹出，T=T-1，重复步骤2)，否则，执行步骤3)；
3) 判断mstack[T][t]的邻接点集R′中是否存在终点：若存在，则将所有mstack[j][t]依次输出(j∈[0, T])，并连同终点共同作为初始解，结束搜索；否则，从R′中将mstack[j][t](避免产生环路，j∈[0, T])及悬挂拓扑点去除，然后对R′中的拓扑点随机排列后构造新的内栈插入外栈中，执行步骤2)。
根据上述步骤，对图 1中从点1到点6的初始解搜索过程见图 4。此外，由当前解X生成新解X′的过程与此类似：首先从X中随机选择两点O、P，基于上述步骤获得从O到P的点串L，然后用L替换X中的相应点串L′，获得X′。其中，L不包含X中除L′以外的任何点，避免X′中产生环路。
图 4 初始解搜索
Figure 4. Searching for Initial Solution
-
全局最优解不仅需要对特殊区域进行正确处理，还需要顾及双方面积比例及甲方资源利益最大化诉求。其中，经过§2.2对“点-点”邻接关系处理后，由此生成的任一划界线都能够避开特殊区域且将必争区域划归相应国家，因此，目标函数主要对划界双方所得区域面积和资源进行评价。
本文通过式(1) 对方案线l进行评价，分子为甲方所得面积比例差异，分母为甲方区域对应的资源利益。式中，ro和rs分别为甲方约定所得面积与实际所得面积分别与争议区总面积的比值；Wi为第i种资源的重要性权值(主要基于熵权_AHP模糊综合评价法[5]并结合相关资源开采的经济效益[16]等因素来确定)；Ri为甲方所得第i项资源量的归一化值。因此，如果甲方所得面积比例与约定比例之间的差异越小，且所得资源利益越大，那么目标函数值就会越小，此时，方案线对甲方越有利。
$$ f\left( l \right) = |{r_o} - {r_s}|/\sum\limits_{i = 2}^n {\;{W_i}{R_i}} $$ (1) -
模拟退火算法的全局搜索性能与退火速度密切相关，且同一温度下的充分搜索非常重要。鉴于缓慢退火方式可以对全局最优解进行充分搜索(但收敛速度较慢)，快速退火方式能够较快收敛(但有可能得不到全局最优解)，对此，本文将上述两种退火方式相结合，构造了图 5所示的并行模拟退火算法，从而对全局最优解进行快速充分搜索。其基本流程如下。
图 5 并行模拟退火流程
Figure 5. Parallel Simulated Annealing Algorithm
1) 生成初始解作为当前解，给定初始温度T0；
2) 判断当前温度Tk是否小于最低温度Tf：若满足，则输出最优解并结束搜索，否则, 转到步骤3)；
3) 同时启动3个线程，每个线程均重复如下操作：由当前解生成新解，计算其目标函数值，并判断是否接受新解，若接受，则更新当前解，且当累计接受次数等于m时进行降温，转向步骤2)；否则继续执行上述操作。其中，如果上述3个线程均连续m次未接受新解，则输出最优解结束搜索。
其中，上述3个线程共享当前解及当前温度。线程1、2、3的降温方式分别由式(2)~式(4) 确定，前两者分别为缓慢降温与快速降温，后者降温方式介于前两者之间。此外，本文算法同时采用最优保留策略，即在步骤3) 中每次接受新解时，将截止当前目标函数值最小的解进行保存，最终，算法结束时的当前最优解对甲方最有利。
$$ {T_1}\left( k \right) = \frac{{{T_0}}}{{\ln \left( {2 + k} \right)}} $$ (2) $$ {T_2}\left( k \right) = \frac{{{T_0}}}{{{1 + k} }} $$ (3) $$ {T_3}\left( k \right) = \frac{{{T_1}\left( k \right) + {T_2}\left( k \right)}}{2} $$ (4) -
为了验证本文方法的可靠性及性能，采用C#语言基于ArcEngine平台对缓慢模拟退火、快速模拟退火及本文并行模拟退火3种方法生成划界线进行编码实现，并通过实验对其进行对比分析。
-
本文以国外某处争议区为例，搜集并模拟了相关实验数据，如图 6所示。其中，争议区通过矢量化获得，面积为3 953 km2；特殊区域为模拟数据；地性线网络为利用文献[17]方法从DEM数据中提取及后续处理获得，包括351条地性线，由于划界线精度取决于地性线网络，鉴于高分辨率DEM数据存在的细部噪音不利于地性线的提取，基于综合考虑，本文选取30 m DEM数据(http://gdem.ersdac.jspacesystems.or.jp/)；资源数据为模拟数据。假设甲乙双方约定面积比例为1:1，且甲方重点关注争议区内的水资源、石油、天然气及稀有金属等资源，其重要性权值由相关领域专家打分处理获得，水资源为0.105 3;石油为0.362 8；天然气为0.244 6;稀有金属为0.287 3。
图 6 实验结果
Figure 6. Result of Experiment
实验中，本文分别基于上述3种方法生成划界线。经多次调试，各参数设置如下：T0=20;Tf=1.0×10-6; m=10，生成的最优划界线Q见图 6。由于本文方法迭代次数较多，此处仅选取部分中间结果列于表 1，其中，面积值和各项资源值均为甲方所得部分与争议区总量的比值，综合资源值为甲方所得各项资源值与其重要性权值的加权总和。
表 1 本文方法部分迭代过程
Table 1. Part of the Iterative Process
迭代次数 面积 水资源 石油 天然气 稀有金属 综合资源值 目标函数值 0 0.435 5 0.747 3 0.154 4 0.320 4 0.196 3 0.269 5 0.239 4 10 0.451 1 0.570 4 0.312 2 0.393 8 0.526 4 0.420 9 0.116 2 20 0.531 7 0.612 5 0.472 3 0.523 5 0.452 1 0.493 8 0.064 2 30 0.522 6 0.631 9 0.594 6 0.572 3 0.580 1 0.588 9 0.038 4 40 0.512 4 0.581 7 0.573 6 0.502 5 0.683 7 0.588 7 0.021 1 50 0.502 8 0.522 7 0.543 8 0.454 2 0.622 1 0.542 2 0.005 2 60 0.501 5 0.493 6 0.584 2 0.530 4 0.646 8 0.579 5 0.002 6 70 0.500 6 0.470 3 0.601 7 0.557 9 0.659 2 0.593 7 0.001 0 80 0.500 2 0.463 8 0.612 5 0.560 4 0.665 7 0.599 4 0.000 3 90 0.500 2 0.463 8 0.612 5 0.560 4 0.665 7 0.599 4 0.000 3 -
由图 6可知，划界线Q完全由地性线构成，能够与实际地形完全吻合。在划界法理方面，划界线Q没有穿过特殊区域，而且将必争区域划归到相应国家。在利益分配方面，由表 1可知，算法开始时，甲方在区域面积和各项资源(水资源除外)方面均处于劣势，尽管水资源所占比例较大，但其重要性较低，对综合资源值贡献不大；随着算法逐步展开，甲方所得面积比例逐渐趋向约定面积比例，且所得重要性较高的各项资源量普遍增大，重要性较低的水资源占有量则逐渐降低，因为各项资源的空间分异特征不同，且限于双方面积比例约束，当重要性程度不同的各项资源分布区域存在冲突时，算法优先顾及对甲方综合资源值贡献较大的资源项；最终，经过多次迭代，划界线的目标函数值达到最小并趋于稳定，此时获得最优划界线。可知，该划界线对甲方十分有利，除水资源外，其所得各项重要性较高的资源均明显大于乙方，能够有效维护甲方的划界利益。
在算法性能方面，如图 7所示，缓慢模拟退火经过多次较小跳跃后最终收敛于全局最优解(对应的目标函数值为min)，但其收敛速度比较慢，迭代次数平均为200次左右；快速模拟退火经过多次较大跳跃后快速收敛(平均迭代次数为100次左右)，但不能保证每次都收敛于全局最优解(图 7(b)中绿色折线所示)；本文并行模拟退火具备前两种退火方式的优点，较大跳跃与较小跳跃交替进行(图 7(c)绿色折线所示)，并快速收敛于全局最优解，平均迭代次数为几十次。
综合考虑算法结果及性能可知，本文方法是可行的，可为甲方划界工作提供技术支持。
图 7 3种退火方式的性能比较
Figure 7. Comparison of Capability About Different Annealing Ways
-
本文提出了一种基于并行模拟退火算法的划界线自动生成方法。实验表明，该方法可以对全局最优划界线进行快速充分搜索，且最优划界线不仅能够顾及双方面积比例、实际地形及特殊区域，还可以保证某方资源利益最大化，从而为该方划界工作提供重要参考。由于本文方法每次由当前解生成新解时仍然具有一定盲目性，下一步将结合其他启发式算法(如粒子群优化算法)进一步提高划界线的生成速度。
Automatic Generation of Land Delimitation Line Based on Parallel Simulated Annealing Algorithm
-
摘要: 针对当前陆地边界争议区自动划界方法考虑因素不全的现状，提出了一种基于并行模拟退火算法的陆地划界线自动生成方法。首先根据地性线网络构造“点-点”邻接关系，并基于划界法理对其进行特殊处理。然后，设计模拟退火过程中划界线的编码方式、目标函数及初始划界线的生成。最后，结合不同退火方式的优点构建并行模拟退火算法对全局最优划界线进行快速充分搜索。实验结果表明，该方法不仅能够顾及划界双方约定的面积比例、实际地形及特殊区域的影响，而且可以满足相应划界方综合资源占有量最大化的利益诉求，有效维护该方的划界利益。Abstract: Concerning that current automatic delimitation of land border dispute areas neglects some important factors, this essay puts forward a new automatic generation method of land delimitation line based on parallel simulated annealing algorithm. Firstly, "point-point" topological relationship is built up based on terrain line network and disposed according to delimitation laws. Secondly, coding and estimation of delimitation line is needed for simulated annealing algorithm, as well as generation of initial delimitation line. Thirdly, parallel simulated annealing algorithm need to combine different ways of annealing to search for the best delimitation line fast and fully. The experiment shows that this method can not only take area ratio decided by related countries, terrain and special areas into account, but also ensure that one could get the biggest resource profit, which can protect its delimitation profit in a better way.
-
图 3 顾及划界法理的特殊处理
Figure 3. Extra Disposal of Point-Point Adjacency Relationship Based on Delimitation Laws
表 1 本文方法部分迭代过程
Table 1. Part of the Iterative Process
迭代次数 面积 水资源 石油 天然气 稀有金属 综合资源值 目标函数值 0 0.435 5 0.747 3 0.154 4 0.320 4 0.196 3 0.269 5 0.239 4 10 0.451 1 0.570 4 0.312 2 0.393 8 0.526 4 0.420 9 0.116 2 20 0.531 7 0.612 5 0.472 3 0.523 5 0.452 1 0.493 8 0.064 2 30 0.522 6 0.631 9 0.594 6 0.572 3 0.580 1 0.588 9 0.038 4 40 0.512 4 0.581 7 0.573 6 0.502 5 0.683 7 0.588 7 0.021 1 50 0.502 8 0.522 7 0.543 8 0.454 2 0.622 1 0.542 2 0.005 2 60 0.501 5 0.493 6 0.584 2 0.530 4 0.646 8 0.579 5 0.002 6 70 0.500 6 0.470 3 0.601 7 0.557 9 0.659 2 0.593 7 0.001 0 80 0.500 2 0.463 8 0.612 5 0.560 4 0.665 7 0.599 4 0.000 3 90 0.500 2 0.463 8 0.612 5 0.560 4 0.665 7 0.599 4 0.000 3 
下载: 导出CSV
-
[1] Finnemore M. National Interests in International Society[M]. Ithaca:Cornell University Press, 1996 [2] Klotz A. Norms Reconstituting Interests:Global Racial Equality and U S Sanctions against South Africa[J]. International Organization, 1995, 49(3):451-478 doi: 10.1017/S0020818300033348 [3] 赵军喜. 面向数字边界的地理空间元数据研究[D]. 郑州: 信息工程大学, 2008 Zhao Junxi. Research on Geospatial Metadata Oriented to Digital Boundary[D]. Zhengzhou:Information and Engineering University, 2008 [4] 曹一冰. 陆地国界辅助划界技术研究[D]. 郑州: 信息工程大学, 2011 CaoYibing. Research on Auxiliary Demarcation Technology of Land Borders[D]. Zhengzhou:Information and Engineering University, 2011 [5] 武丽丽. 基于六角格的初始划界方案线辅助生成技术研究[D]. 郑州: 信息工程大学, 2013 http://cdmd.cnki.com.cn/Article/CDMD-90005-1013353742.htm Wu Lili. Research on the Auxiliary Generation of Initial Delimitation Line Based on Hexagon[D]. Zhengzhou:Information and Engineering University, 2013 http://cdmd.cnki.com.cn/Article/CDMD-90005-1013353742.htm [6] 总参谋部军训部.世界军事地理[M].北京:八一出版社, 1993 The General Staff Department of Military Training of China. World Military Geography[M]. Beijing:Eight One Press, 1993 [7] 杨勉.边界与领土, 意味着什么[J].世界知识, 2011(5):20-23 http://www.cnki.com.cn/Article/CJFDTOTAL-SJZS201105008.htm Yang Mian. What Boundary and Territory Means[J]. World Knowledge, 2011(5):20-23 http://www.cnki.com.cn/Article/CJFDTOTAL-SJZS201105008.htm [8] 吴浩扬, 常炳国, 朱长纯, 等.基于模拟退火机制的多种群并行遗传算法[J].软件学报, 2000, 11(3):416-420 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200003020.htm Wu Haoyang, Chang Bingguo, Zhu Changchun, et al. A Multigroup Parallel Genetic Algorithm Based on Simulated Annealing Method[J]. Journal of Software, 2000, 11(3):416-420 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200003020.htm [9] 刘耀林, 夏寅, 刘殿锋, 等.基于目标规划与模拟退火算法的土地利用分区优化算法[J].武汉大学学报·信息科学版, 2012, 37(7):762-765 http://ch.whu.edu.cn/CN/abstract/abstract248.shtml Liu Yaolin, Xia Yin, Liu Dianfeng, et al. Optimization of Land Use Zoning Based on Goal Programming and Simulated Annealing[J].Geomatics and Information Science of Wuhan University, 2012, 37(7):762-765 http://ch.whu.edu.cn/CN/abstract/abstract248.shtml [10] 马小姝, 李宇龙, 严浪.传统多目标优化方法和多目标遗传算法的比较综述[J].电气传动自动化, 2010, 32(3):48-50 http://www.cnki.com.cn/Article/CJFDTOTAL-DQCD201003013.htm Ma Xiaoshu, Li Yulong, Yan Lang. Comparison Review of Traditional Multi-objective Optimization Methods and Multi-objective Genetic Algorithm[J]. Electric Drive Automation, 2010, 32(3):48-50 http://www.cnki.com.cn/Article/CJFDTOTAL-DQCD201003013.htm [11] 康立山.非数值并行算法(第1册)——模拟退火算法[M].北京:科学出版社, 2003 Kang Lishan. Non-numerical Parallel Algorithm(Vol.1)——Simulation Annealing Algorithm[M]. Beijing:Science Press, 2003 [12] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by Simulated Annealing[J].Science, 1983(220):671-680 https://www.researchgate.net/publication/220118677_Optimization_by_Simulated_Annealing [13] Aerts J, Heuvelink G B M. Using Simulated Annealing for Resource Allocation[J].International Journal of Geographical Information Science, 2002, 16(6):571-587 doi: 10.1080/13658810210138751 [14] 李精忠, 吴晨琛, 杨泽龙, 等.一种利用模拟退火思想的线状要素Morphing方法[J].武汉大学学报·信息科学版, 2014, 39(12):1446-1451 http://ch.whu.edu.cn/CN/abstract/abstract3139.shtml Li Jingzhong, Wu Chenchen, Yang Zelong, et al. A Morphing Method for Linear Features Based on Simulated Annealing[J]. Geomatics and Information of Wuhan University, 2014, 39(12):1446-1451 http://ch.whu.edu.cn/CN/abstract/abstract3139.shtml [15] 黄培之, 刘泽慧.基于地形梯度方向的山脊线和山谷线的提取[J].武汉大学学报·信息科学版, 2005, 30(5):396-399 http://ch.whu.edu.cn/CN/abstract/abstract2180.shtml Huang Peizhi, Liu Zehui. Extraction of Ridge and Valley from DEM Based on Gradient[J]. Geomatics and Information of Wuhan University, 2005, 30(5):396-399 http://ch.whu.edu.cn/CN/abstract/abstract2180.shtml [16] 黄晓东.多金属矿开采的经济性评价[J].南方冶金学院学报, 2003, 24(4):5-8 http://www.cnki.com.cn/Article/CJFDTOTAL-NFYX200304001.htm Huang Xiaodong. The Economic Analyzing of Multi-metal Ore Mining[J]. Journal of Southern Institute of Metallurgy, 2003, 24(4):5-8 http://www.cnki.com.cn/Article/CJFDTOTAL-NFYX200304001.htm [17] 孔月萍, 方莉, 江永林, 等.提取地形特征线的形态学新方法[J].武汉大学学报·信息科学版, 2012, 37(8):996-999 http://ch.whu.edu.cn/CN/abstract/abstract294.shtml Kong Yueping, Fang Li, Jiang Yonglin, et al. A New Method of Extracting Terrain Feature Lines by Morphology[J]. Geomatics and Information of Wuhan University, 2012, 37(8):996-999 http://ch.whu.edu.cn/CN/abstract/abstract294.shtml -
点击查看大图
图(7) / 表(1)
计量
- 文章访问数: 1032
- HTML全文浏览量: 75
- PDF下载量: 400
- 被引次数: 0
