基于智能符号回归的路径规划算法均衡控制方法(组图)

中国图像图形学杂志。15、2010年5月资助：国家高技术研究发展计划）；国家自然科学基金委、资源与环境信息系统国家重点实验室自主创新团队计划） 收稿日期： ;返回日期： 第一作者简介：周亮，1984—），男。现为中国科学院地理科学与资源研究所制图与地理信息系统博士研究生。研究方向为交通地理信息系统。: zhoul@lreis。交流。cn 基于智能符号回归的路径规划算法平衡控制方法（资源与环境信息系统国家重点实验室，中国科学院地理科学与资源研究所，北京) 摘要 随着地图网站和在线导航系统的发展，随着多用户网络的普及，对并发旅游信息查询服务的需求越来越大。如何满足多用户并发路径查询效率要求，同时使路径查询精度可控，是网络地理信息服务的瓶颈技术问题。本文提出了一种多用户并发路径查询精度和效率平衡控制方法。采用系统抽样和智能符号回归技术，根据在线路径查询用户规模和系统响应效率容忍阈值的动态变化，它基于经典的路径查询启发式算法。在大样本确定的路径查询严格算法和相应启发式算法得到的系统耗时率和准确率的基础上，实时自动确定启发式路径查询启发式因子权重，有效平衡响应效率多用户并发路径查询的准确性损失。，自适应控制路径查询算法的精度和效率之间的平衡，在精度可预控的前提下，最大限度地提高多用户并发路径查询的效率，缩短用户的路径查询等待时间。在大样本确定的路径查询严格算法和相应启发式算法得到的系统耗时率和准确率的基础上，实时自动确定启发式路径查询启发式因子权重，有效平衡响应效率多用户并发路径查询的准确性损失。，自适应控制路径查询算法的精度和效率之间的平衡，在精度可预控的前提下，最大限度地提高多用户并发路径查询的效率，缩短用户的路径查询等待时间。在大样本确定的路径查询严格算法和相应启发式算法得到的系统耗时率和准确率的基础上，实时自动确定启发式路径查询启发式因子权重，有效平衡响应效率多用户并发路径查询的准确性损失。，自适应控制路径查询算法的精度和效率之间的平衡，在精度可预控的前提下，最大限度地提高多用户并发路径查询的效率，缩短用户的路径查询等待时间。有效平衡多用户并发路径查询的响应效率和准确率损失。，自适应控制路径查询算法的精度和效率之间的平衡，在精度可预控的前提下，最大限度地提高多用户并发路径查询的效率，缩短用户的路径查询等待时间。有效平衡多用户并发路径查询的响应效率和准确率损失。，自适应控制路径查询算法的精度和效率之间的平衡，在精度可预控的前提下，最大限度地提高多用户并发路径查询的效率，缩短用户的路径查询等待时间。

关键字路径规划A算法平衡控制智能符号回归中文图法分类号：P208文献编号：A文章编号：（2010)基于周亮，卢峰，（LREIS，，CAS，），路径./路径, , , , . . 模型 , 可以 , 时间 . , , 路径查询是地图网站、公共旅游信息平台和服务器端导航系统的核心功能。

在多用户环境下，路径查询的响应时间会随着并发用户数的增加而线性增加，用户的平均等待时间也会急剧增加。解决该问题的技术包括服务器硬件升级、网络性能优化算法平衡控制方法803，这些方法存在成本高、约束苛刻、实现困难、灵活性不足等缺点，核心路径查询算法没有优化。目前应用最广泛、最有效的单源最优路径算法是理论上严谨的算法和算法。这些算法虽然结果准确，但时间复杂度基本达到极限，效率提升空间不大。因此，对于多用户并发环境，路径查询采用启发式策略是更好的选择，但会牺牲一定程度的路径查询结果的理论严谨性和准确性，从而获得算法效率的较大提升。但是路径规划方法，在基于启发式策略进行路径查询的多用户并发环境下，如何在启发式策略中量化用户控制因素，在可容忍的精度损失范围内，尽可能提高路径查询效率，或者在精度损失的可容忍范围内。在系统的系统反馈效率下尽可能提高路径查询的准确性是多用户并发环境下启发式路径查询需要解决的瓶颈技术问题。启发式路径搜索使用先验知识来约束解空间，已广泛应用于地理信息系统、人工智能等领域。然而，关于启发式算法启发因子强度对路径搜索效率和准确性的影响的研究很少。

Pohl 提出了启发式搜索误差分析的概念。他以启发因子/2的值为界，详细讨论了启发因子增加或减少时启发式算法搜索过程的变化过程。Pearl从理论上分析了启发式因素对算法结果的影响，讨论了启发式搜索的复杂度和精度之间的关系，以及回溯方法的平均复杂度的比较。等人提出了一套可接受启发式算法的抽象方法，试图从理论上研究算法的准确性，但效果一般。以上研究均是从理论角度出发，在实际问题中难以实施和应用。算法的评价函数的构造给出了不同情况下评价函数的构造应考虑的因素，而对于包含权重系数的评价函数，权重系数的取值只是由下式得到的经验值实验，对实际操作的参考意义有限。高松等人。使用统计抽样的方法定量研究启发式算法的效率和准确率之间的关系，但使用的多项式拟合方法不可靠，需要先验知识和大量人工干预。作为启发式路径搜索算法的典型代表，提出了启发式算法和评价函数系统算法的效率和准确性，并提出了一种基于智能符号回归模型的方法。在统计抽样的基础上，确定效率、准确性和启发式算法。因素之间的量化函数关系，科学引导算法的效率和精度，路径规划中常用的n)，以牺牲可接受性为代价来换取搜索效率。

另一种形式的评估函数是通过调整 τ 来改变启发式搜索的权重。非常大的 τ 将过分强调启发式部分路径规划方法，而非常小的 τ 将强调搜索的广度优先性质。即增大τ会提高算法的效率，但可能找不到最优解。减小 τ 将扩大搜索空间并增加找到最优解的概率。但是算法的效率与τ不是线性相关的，效率的提升也不是无限的。根据算法的性质，当满足可接受性时，算法必须能够找到最优解路径，算法的效率随着τh的增加而增加，并且精度始终没有损失。当 τh 的可接受性不能满足时，算法的效率仍然会随着 n) 的增加而增加，但准确率开始下降。算法的效率。效率E和精度如何随τ的变化而变化，是否存在极值，是否存在平衡点等，很少定量研究。本文的主要内容是定量研究算法的效率、准确率和启发式因子τ之间的关系，为解决多用户环境下的路径查询效率问题提供思路和方法。二、均衡模型的求解方法 1、在符号回归法的研究中，建立函数模型的本质是进行符号回归。目标是找到一个可以很好地拟合给定数据的符号函数。该过程包括确定数学函数的形状、确定函数中的数值常数和系数。传统的曲线拟合方法，如最小二乘法，首先需要根据专业知识、理论推导或以往经验确定变量之间的函数关系，从而预先确定方程的结构形式（线性形式、对数形式） ，或多项式，然后执行参数估计。

但在实践中往往难以准确确定方程的结构形式，因此传统的曲线拟合存在一定的局限性。在平衡控制模型中，采用遗传规划算法作为智能符号回归方法。遗传编程（GP）是一种符合一些客观标准程序的进化方法。基本思想是：随机生成一个适合给定问题环境的初始种群，即在空种群中搜索每个个体作为树形结构，对每个个体进行计算。根据达尔文的进化原理，选择遗传算子、交叉、变异等）对种群进行迭代优化，直到在某一代找到最优解或近似最优解。符号回归问题中遗传编程的优点是不需要给出特定的函数形式来获得拟合的函数表达式，并且当初始种群足够大且交叉和变异概率设置合理时，它不会落入局部 优化遗传规划算法得到的结果不是常数。检验标准为函数表达式的适应度，满足适应度的结果为有效结果。样本空间的大小决定了拟合结果与实际函数的差距，而拟合本身只能找到有效解，而不是唯一解。因此，使用遗传规划算法进行符号回归是一个平衡模型求解步骤。通过算法的特点和 Pearl、Pohl 等人的工作。10211, 18，可知评价函数部分的取值在一定范围内。算法满足可接受性，则可以找到最短路径，即精度无损。

随着启发式因子τ值的增加，算法路径搜索结果的准确性会有所下降。因此，需要根据系统采样集计算最短路径搜索过程中启发式搜索算法和理论上严谨算法的系统耗时与结果精度的比值；根据结果​​进行符号回归得到平衡的控制函数模型，并利用该函数模型指导启发式算法评价函数系数的设置。具体步骤如下：选择样本并设置样本空间大小，系统地对路网中的所有路段进行采样，得到路段对作为路径搜索的结束段。提取的路段应满足：作为起始路段，其出度应大于0；作为终止路段，其入度应大于定义的启发式算法的时间消耗比E，并且将精确启发式路径规划算法的精度P定义为获得的最优路径成本（例如，路径长度）分别使用理论严谨算法和启发式算法， 分别是理论严谨算法和启发式算法所花费的 CPU 时间。使用经典算法，计算每个样本路径搜索的耗时比（反映算法的效率）和耗时算法的精度。使用启发式算法对样本空间中的每个样本路段逐步计算样本空间中的每个样本路段，并计算样本空间中每个样本路段的路径成本；输入符号回归的值。

设置智能符号回归法的控制参数，定义搜索空间和解数。执行以获得满足精度要求的解决方案。/效率平衡控制模型，选择合适的启发式因子。使用该算法查询单个用户所需的估计时间为 。在具体实现中，通过算法得到每个样本对之间的紧最优路径后，可以计算出起点到终点的曼哈顿距离。当前环境下，系统计算所有用户查询所需时间。该算法可以满足时间要求。这时候就不需要使用有损精度算法了，否则去上一步计算预估计启发因子τ的值，步骤如下： 计算估计效率 根据 τ2E 函数关系，计算启发因子 τ 的算法 平衡控制方法 805 1 平衡模型 求解过程 图 1 流程图模型 根据 τ2P 函数关系，计算精度计算预估计启发式算法。1 实验环境以北京城市路网为基础数据。该网络包括 33 402 个节点和 53 997 个路段。实验机配备P4双核 CPU和G内存。在实验中。评估函数使用曼哈顿距离。当算法在实验中计数时，启发因子τ的值以1结束，增量步长为0104。在实验中，遗传规划算法用于符号回归，遗传规划用于解决符号回归问题，包括以下基本要素：定义终止集），确定适应度值终止准则ln，exp，sqrt，sin， cos，基本包括常用和常用的函数形式，可以满足各种曲线拟合的要求；经过一次数学运算后，常数可以是 1 到 10 之间的任何数字。提高了遗传规划算法的迭代效率，迭代收敛速度快，拟合精度得到保证。适应值终止准则ln、exp、sqrt、sin、cos的确定，基本包括常用和常用的函数形式，可以满足各种曲线拟合的要求；经过一次数学运算后，常数可以是 1 到 10 之间的任何数字。提高了遗传规划算法的迭代效率，迭代收敛速度快，拟合精度得到保证。适应值终止准则ln、exp、sqrt、sin、cos的确定，基本包括常用和常用的函数形式，可以满足各种曲线拟合的要求；经过一次数学运算后，常数可以是 1 到 10 之间的任何数字。提高了遗传规划算法的迭代效率，迭代收敛速度快，拟合精度得到保证。

实验中遗传规划算法使用的参数如表1所示。 1遗传规划算法参数表。GP种群大小300终结者集合迭代次数150选择方法精英选择方法交换概率75函数符号集sin、cos、ln、exp、sqrt变异概率样本大小50 50适应度计算公式2实验结果实验结果如表2所示。可以看出，当算法的启发因子τ小于014时，算法满足可接受性，可以找到理论上的最短路径。当 τ 大于 014 时，算法无法满足可接受性，无法找到理论上的最短路径。此时，算法会损失精度，必须使用分段拟合。该算法的实验结果如表所示。76618 4、拟合误差分别为4134%、0157%、2140%，误差均在5%以内。误差计算为变量的数量。根据需要的效率提升值，查询τ2E函数关系，可以得到τ对应的值，然后通过τ2P函数关系，反查精度损失值，检查精度损失是否在可控范围内此时。如图5所示，当算法的计算时间要求为严格算法的1415%时，τ值为0153，算法准确率为9611%。第806卷15通过实验可以看出，该算法的效率和准确率与其评价函数有函数关系。

根据算法的可接受性满足的条件，即当前节点到终端节点的距离估计值不大于真实值，此时算法可以找到最小代价路径。平衡模型中n)的形式为曼哈顿距离，泛函形式算法满足可接受性，需要满足01412。实验中τ的临界值为014，符合理论推导。算法的效率与启发式因子呈正相关，准确率与启发式因子呈负相关。值得注意的是，该算法在效率提升近100%的情况下仍能保证准确率无损0136)。当准确率损失为 80% 时，900%的效率提升在实际应用中非常有意义。从τ2E的函数曲线可以看出，在算法不满足可接受性后，随着启发因子τ的增大，算法效率迅速提高，并很快趋于稳定，证明所采用的函数形式有效避免不适当的 n) 对搜索的影响。对于指定的路网，在线用户数、效率和准确性要求、用户查询路径长度等都会影响均衡模型的应用效率。当并发路径查询很少时，在满足路径查询效率要求的前提下，可以使用精度无损的算法。随着并发路径查询的增加，当算法不再能满足效率要求时，算法可以在精度损失可控的范围内大幅度提高效率。当并发路径查询的数量不断增加时，效率和准确性之间的平衡无法满足，算法将不再适用。这时可以使用层次推理等多级路网路径规划算法。

启发式路径搜索算法的效率和准确性的平衡控制应根据路网的特点进行定量分析。本文合理拟合了算法平衡控制方法807启发式路径搜索算法的效率和精度之间的函数关系。在每次路径搜索查询之前，可以根据并发用户响应效率和准确性的要求，预先动态确定算法中的启发式。计算因子的值，同时计算计算结果的精度，从而在精度损失可控的范围内最大化多用户并发路径搜索的效率；或者在效率不变的前提下，尽量减少路径搜索精度的损失。对于给定的道路网络数据集，只需一次预计算即可获得路线搜索效率和准确性的平衡控制曲线。本文方法同样适用于其他路径启发式搜索算法的精度-效率平衡控制过程。本文的方法可以进一步改进。例如，在采样路段时，不使用系统提取，根据查询频率对路段进行排序，可以进一步提高方法的准确性。策略选择时，可根据道路类型调整预先估计的算法时间。让路径搜索方法具有自适应性和智能性将是接下来的研究方向之一。参考文献（ ），孙燕，甘宁．[ : , 2003, 35 分布式网络环境中的负载均衡原理与算法，四川大学学报（工学版）2003，35．， 陈 。基于，2001 基于万维网的网络计算模式计算机工程与应用性能分析，2001，杨，iaYan。,2005, 27 62264.[蔡建宇, 杨树强, 贾岩, 等。计算机工程与科学, 2005, 27 Nian'ning. 学习路径 k , 2004. [倪安宁. 交通网络分析中最短路径并行算法的研究与实现 吉林：吉林大学，2004.，即陆峰。mdk , 2006, 11 基于队列的交通网络最短路径优化算法 中华图像图形学杂志, 2006, 11: ,1984, 14. , 2008 该算法的启发式值应用于福建计算机，