一种基于路径相似度的蚁群算法

提出了路径相似度的概念,并根据较优可行解与最优解的相似度,来进行路径选择和信息素更新,以求能更快加速收敛和防止早熟、停滞现象。该算法根据截之间的相似度,自适应地调整路径选择策略和信息量更新策略。基于旅行商问题的实验验证了算法比一般蚁群算法具有更好的全局搜索能力、收敛速度和解的多样性。

基于双重超像素集的快速路径相似度图像分割算法

为克服基于路径相似度计算时间复杂度高以及基于单一过分割区域集的聚类方法容易导致误合并的缺陷,提出一种结合均值漂移和路径相似度的谱聚类算法.该算法使用超像素构建基于路径相似度的模型来实现加速.首先,利用均值漂移算法对图像进行两次预分割(不同参数),将这些过分割区域视为两组超像素集合,构建基于双重过分割区域集的加权图;之后,使用各超像素的色彩均值和超像素间存在的交叉像素计算初始相似度,再利用路径相似度模型得到基于路径的相似度;最后,采用Multiway Ncut算法进行聚类.通过算法自身参数和图结构实验,测试算法的鲁棒性和稳定性;通过多幅彩色图片的分割实验,表明本文的方法在准确性和时效性方面都具有很好的性能.

结合关键点概率与路径相似度的多路径覆盖策略

利用多种群遗传算法解决多路径覆盖问题,是测试数据自动生成领域一个重要的研究方向.为了提高多路径覆盖测试数据自动生成的效率,提出一种将关键点概率和路径相似度相结合的多路径覆盖策略.首先,将理论路径划分成易覆盖、难覆盖及不可达路径;然后,通过易覆盖路径统计关键点概率,依此概率计算个体对生成测试数据的贡献度,并利用贡献度改进适应度函数,同时根据关键点概率对目标路径进行排序;最后,使用多种群遗传算法生成覆盖目标路径的测试数据,在进化过程中,子种群覆盖当前目标路径后,继续尝试覆盖该目标路径的相似路径.实验结果表明,该方法能够有效地提高多路径覆盖测试数据生成的效率.

基于向量空间模型的路径相似度蚁群算法研究

针对如何根据用户的检索状况来提高信息检索的反应速度及查询的准确性的问题,利用向量空间模型信息检索与路径相似度蚁群算法中利用同一方式——相似度来决定下一步方向的共同特点,提出将一种基于路径相似度的蚁群算法应用于信息检索的方法。采用这种算法在性能和收敛性速度上优于常规算法。

基于全路径相似度的大规模层次分类算法

为快速准确地实现大规模层次分类问题,提出词类区分度概念,并以此作为计算类向量的基础。基于类向量,以改进的Rocchio算法计算待分类文本与目标类的相似度,候选出N个最可能的目标类别;根据目标类别的层次拓扑结构,计算待分类文本与N个目标类别的全路径相似度,确定分类类别。实验结果表明,该方法分类效果优于传统算法,其基于文本类全路径相似度的策略明显改善了单纯基于词类区分度的分类算法。

基于高阶路径相似度的复杂网络链路预测方法

针对目前链路预测方法普遍存在精度不高、效率低等问题,提出了基于高阶路径相似度的复杂网络链路预测方法。首先,利用路径作为判别特征对复杂网络中的缺失链接进行预测,以实现资源的有效分配,并通过惩罚公共近邻对信息泄露进行限制。其次,将高阶路径作为判别特征,对种子节点对间的可用长路径实施惩罚。最后,利用多个真实复杂网络数据集进行数值算例。实验结果表明,与其他基线方法相比,所提方法具有更优的精度与效率。

局部路径相似度的蛋白质链接预测

首先寻找蛋白质交互网络中的社区结构,得到基于节点度的局部路径相似度,然后预测蛋白质之间的链接。在蛋白质交互网络数据集上,与七种经典的链接预测方法进行了比较。

基于POI地标与路径相似度的IP定位研究

由于缺少PlanetLab等公共地标平台,高精度IP定位技术仍然面临着巨大的挑战。为解决这一问题,提出一种基于大规模兴趣点(Point of Interest,POI)地标与路径相似度的IP定位算法,爬取和去噪数字地图上的POI数据并跟踪地标探测路径来收集地标信息。进一步设计了加权二维字符串子序列内核算法挖掘路由路径相似性特征,以及基于半径领域的离群点检测聚类算法来定位目标节点。该算法挖掘了北京市和上海市的2038个和1429个可用地标。实验表明,该算法显著提高了IP定位技术的稳定性与准确性,实现了5.7 km的平均定位误差。

基于路径相似度的台风路径预测研究

因为受到诸多物理因子的综合影响,台风运动轨迹变得极其复杂,运动轨迹和物理因子之间呈现高度非线性。因此,正确预测台风的未来轨迹对于风险评估具有极其重要的意义。本文通过建立一个基于路径相似度的模型来对台风路径进行预测。

基于路径相似度的并行程序多路径覆盖调度序列排序

测试是提高软件可靠性的重要方法.消息传递并行程序中存在的不确定通信语句,使得进程执行顺序具有不确定性,这增加了测试该类程序的难度.鉴于进程执行顺序对目标路径覆盖难易程度的影响,本文研究消息传递并行程序多路径覆盖调度序列排序方法,以提高多路径覆盖测试数据生成的效率.首先,在每个调度序列下,以每个采样的程序输入执行程序,生成路径覆盖矩阵;然后,针对每条目标路径,分别计算与路径覆盖矩阵中每条路径的相似度,生成多个路径相似度矩阵;接着,基于这些路径相似度矩阵的特征量,评价调度序列的性能,并依此对调度序列排序;最后,基于调度序列排序集,使用随机采样法,生成覆盖所有目标路径的测试数据,并使用缺陷检测平均百分比(average percentage of faults detected,APFD)指标评估调度序列排序集.将所提方法应用于9个基准并行程序中,并与随机方法和传统方法进行比较.实验结果表明,所提方法对路径覆盖率没有影响,但显著减少了被测程序执行次数和运行时间.

基于路径搜索的相似度计算的协同过滤推荐方法

协同过滤被广泛的应用在推荐系统中,传统计算相似度使用皮尔森相关系数,余弦相似度、Jaccard相似度等方法,但在处理稀疏数据时,其准确度不理想。针对这一问题,提出一种基于路径搜索的相似度计算方法,能够反映用户或项目之间间接关系。实验结果表明,相比传统的相似度计算方法,该方法在准确度上有较好的提升。

基于变步长双层蚁群算法的机器人路径规划

针对双层蚁群(double layer ant colony optimization,DACO)算法在移动机器人路径规划中收敛速度慢、路径质量差的问题,提出了一种变步长双层蚁群(variable step size double layer ant colony optimization,VDACO)算法。首先,将蚁群均分为寻路层蚂蚁与寻优层蚂蚁进行变步长寻路。针对寻路层蚂蚁,考虑最优移动方向和终点距离改进启发函数,并设计变步长回溯-剪枝策略帮助蚂蚁快速跳出死锁。寻路层蚂蚁寻路完成后,利用Floyd算法正-反向搜索寻路层关键点路径,基于关键点路径构建寻优层寻路环境;寻优层蚂蚁在此环境中进行自适应变步长寻路。最后,基于最优路径相似度改进信息更新机制,差异化更新不同质量的路径节点。仿真结果表明,与其他改进蚁群算法相比,VDACO算法在不同规模栅格环境下路径长度更短且收敛速度更快。

基于动态半马尔可夫路径搜索模型的DTN分簇路由方法

在容迟网络环境下,文中提出一种基于动态半马尔可夫路径搜索模型的分簇路由方法 CRSMP(Clustering Routing method based on Semi-Markov process and Path-finding strategy),该方法既考虑了节点拥有的社会属性所导致的分簇问题,又考虑到节点间未来一段时间内的最大相遇概率以及对应的相遇时间,结合分簇结果和相遇情况生成动态路由表,完成一种单副本的路由方法.该方法首先依据节点间路径的相似程度进行分簇,然后运用半马尔可夫模型预测节点间未来某一时刻的相遇概率,依据源节点和目的节点所在的分簇确定可以应用到路由中的节点集合,最后根据路径搜索策略找到最优路径,生成与当前时刻有关的动态路由表.仿真结果表明CRSMP在缓存较小的情况下投递成功率远高于DirectDeliveryRouter、FirstContactRouter和SimBetRouter三种单副本路由方式以及Spray and Wait、Epidemic和Prophet三种多副本路由协议.在10M缓存下的CRSMP有着与500M缓存下的Epidemic相近的路由性能.进一步在真实数据集上进行测试,测试结果表明CRSMP算法依然有着较好的路由性能.

广州市中产阶层日常活动时空路径的特征及影响因素

对广州36个中产阶层聚居区881个中产阶层进行工作日与休息日活动日志问卷调查的基础上,运用时间地理学和多层次聚类方法,探讨中产阶层日常活动时空路径的特征及影响因素。研究发现中产阶层工作日活动路径根据就业地不同而呈现差异化的路径形态,可聚成无工作的直线路径和有工作但通勤距离不同的曲线路径等5类;休息日活动路径根据活动距离和活动持续时间不同而呈现多样化的路径形态,可聚成近家型活动的短距离曲线路径、购物与用餐为主的中短距离曲线路径、购物与外出办事为主的中长距离曲线路径和休闲与用餐为主的长距离曲线路径等6类。此外,不同自然、社会经济和环境属性的中产阶层活动路径特征各不相同。个体特征、城市空间结构、产业和制度因素综合作用于中产阶层的日常行为,导致中产阶层日常活动时空路径呈现独特特征。研究有助于揭示中产阶层的日常活动规律,为提高城市社会经济活力和完善城市精细化管理提供参考。

基于优化成熟度的自适应蚁群优化算法

分析了蚁群算法局部信息素更新系数与全局信息素更新系数对算法寻优能力与收敛速度的关系,定义平均路径相似度(ATS)来表征寻优过程的成熟程度,并据此自适应调整信息素更新系数,提高算法收敛速度并避免陷入局部最优.经过与典型蚁群算法在多个旅行商问题测试用例上进行收敛速度与全局寻优能力的全面比较,证明了新的算法具有较好的效果.

基于优化成熟度的自适应蚁群优化算法

通过深入分析蚁群算法中信息素更新系数对算法寻优能力与收敛速度的影响,定义了平均路径相似度(ATS)来表征寻优过程的成熟程度,据此自适应调整信息素更新系数,以提高算法收敛速度,并避免陷入局部最优.经过与典型蚁群算法在多个旅行商问题测试用例上进行比较,表明新算法具有更好的效果.

复杂网络链接预测的路径抽样方法

链接预测问题在社会学、人类学、信息科学以及计算机科学等各个领域都受到了广泛的关注.在许多现实应用中,只需要对用户感兴趣顶点的相似度进行预测,而不需要预测复杂网络中的所有顶点.提出一种快速的以路径相似度为基础的方法来预测指定的顶点对间的链接.在该方法中,首先定义顶点之间的路径相似度的概念,然后对给出的节点对之间构造一个的路径的集合,通过设定该集合适当的大小,可以将相似度的误差限制在一个给定的阈值范围内.由于只要计算相关路径的个数,因此该算法可以大大减少计算时间.以对单个节点的路径抽样方法为基础,提出了整个网络的链接预测算法.通过在实际网络上的实验结果表明,本算法与其他方法相比,在更短的时间可以获得更高精度的结果.

基于优化成熟度的自适应蚁群优化算法

分析了蚁群算法局部信息素更新系数与全局信息素更新系数对算法寻优能力与收敛速度的关系,定义平均路径相似度(ATS)来表征寻优过程的成熟程度,并据此自适应调整信息素更新系数,提高算法收敛速度并避免陷入局部最优。经过与典型蚁群算法在多个旅行商问题测试用例上进行比较,表明该算法效果更好。

基于位置近邻的RFID路径聚类算法

随着物联网技术的广泛应用,每天有大量RFID数据产生,如何从海量的位置数据信息中提取知识亟待解决。为了解决这一问题,考虑采用路径聚类的方法。为了确定路径之间的近邻关系,提出一种RFID位置模型LM(Location Model),利用该模型分析位置之间的相互联系,并提出一种RFID路径相似度计算算法,在此基础之上进行了路径聚类。经实验对比结果表明,基于位置近邻的RFID路径聚类算法可以更好的聚集相似路径,同时具有较低的时间复杂度和较高的准确率。

基于自适应粒子群优化算法的测试数据扩增方法

针对在回归测试中原有测试数据集往往难以满足新版本软件测试需求的问题,提出一种基于自适应粒子群算法(APSO)的测试数据扩增方法。首先,根据原有测试数据在新版本程序上的穿越路径与目标路径的相似度,在原有的测试数据集中选择合适的测试数据,作为初始种群的进化个体;然后,利用初始测试数据的穿越路径与目标路径的不同子路径,确定造成两者路径偏离的输入分量;最后,根据路径相似度构建适应度函数,利用APSO操作输入分量,生成新的测试数据。该方法针对四个基准程序与基于遗传算法(GA)和随机法的测试数据扩增方法相比,测试数据扩增效率分别平均提高了约56%和81%。实验结果表明,所提方法在回归测试方面有效地提高了测试数据扩增的效率,增强了其稳定性。