基于随机扰动的FM算法优化

文章针对特大规模集成电路划分时采用传统FM算法容易陷入局部最优和对初始解敏感的缺点,提出了一种基于概率的随机扰动移动元胞选择的优化算法。它以符合平衡约束的最高增益元胞作为基准点,将一定增益值偏差范围内的元胞同时作为算法可能选取元胞,根据增益值偏差大小赋予元胞一定的被选取概率,随机选择元胞进行移动。采用基于随机扰动的FM优化算法对实际电路进行划分,实验结果表明能降低算法进入局部最优的概率,降低算法对初始解的敏感,在lg=3,r=0.3时平均割线数减少了33.9%,但算法平均运行时间增加了40.5%。

VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.

基于Cell对称矩阵结构的电路划分方法

电路划分是超大规模集成电路自动化设计中的一个关键的阶段,同时也是NP-hard组合优化问题.文中基于结点移动的Fiduccia-Mattheyses(FM)算法提出新的cell对称矩阵数据结构,实现一种电路划分方法.首先使用对称矩阵数据结构存储结点和线网信息,然后利用简单的加减运算代替划分过程中结点增益的计算,最后简化原始算法中复杂的判断与计算完成对电路的划分.实验结果表明,与原始FM算法相比,在保证得到等价划分结果的情况下,该方法显著简化了实现过程,并且保持了线性复杂度;对电路实例进行划分,平均切边优化效果达到95.89%.

基于空-地协同的轨迹规划方法

针对车载传感器感知全局环境信息能力不足以及车辆导航规划轨迹的平滑性、安全性的问题,提出一种空-地协同的轨迹规划方法。为此,构筑了无人机全局信息采集平台及地面车辆信息处理平台,其中无人机从空中采集广域地面环境图像信息,并实时回传给地面车辆信息处理平台,采用图像拼接算法构筑全景地理信息图。为了实现车辆导航规划轨迹的平滑性和安全性,提出引入FM^2算法计算全局最佳轨迹。仿真结果表明:空-地协同能够大幅提升地面车辆对全局环境信息的掌控能力,而且FM^2算法保证了全局规划轨迹的平滑性和安全性。

复杂地形下无人机自动巡航轨迹规划研究

为了保证无人机正常飞行并顺利完成预期任务,研究一种复杂地形下无人机自动巡航轨迹规划方法。采用硬件层的COMS传感器采集广域地面环境图像信息,采用软件层的数传图将从硬件层获取的图像信息传输到算法层,该层的图像增强利用基于双三次图像插值的图像增强方法提高所接收图像的像素分辨率,避免复杂地形影响图像质量,通过图像拼接处理增强图像以生成全景地理信息图,在此基础上,利用基于FMM和FM 2算法的无人机自动巡航轨迹规划方法获得最终规划的最优轨迹。实验结果表明,该方法能获得总航程较短的无人机自动巡航轨迹,并能有效规避复杂地形造成的巡航风险。

基于改进机器学习的定向运动推荐及系统构建

为更好地刻画用户向量和活动向量的映射关系,进而提高城市穿越与定向运动推荐的准确率,提出一种基于DSSM-FM的个性化推荐模型。其中,针对传统One-Hot编码存在高维、稀疏和向量间关联性差的问题,运用FM算法替代嵌入层,以此更好地表征特征之间的联系;引入DSSM(Deep Structured Semantic Models,深度语义匹配模型),在FM预训练的基础上,更深入地挖掘特征间的高阶关系,从而更好地挖掘向量隐藏特征。结果表明,与其他算法对比,本研究提出的推荐方案的准确率达89.62%;同时系统应用表明,构建的推荐模型可实现定向运动的推荐。由此得出,本方案可行,可用于定向运动的推荐中。

基于已知地形信息的海底机器人路径规划

路径规划是实现机器人智能化的重要组成部分,规划路径的优劣在很大程度上决定了机器人执行任务的效果.传统的路径规划算法,例如基于图搜索的dijkstra算法和其改进后的A∗算法,以及基于采样的RRT(rapidlyexploring random tree)算法和其改进后的RRT∗算法,仅仅考虑了避障问题;基于插值曲线的算法可以产生较为光滑的轨迹;基于数值优化的算法可以将机器人速度、加速度等加入损失函数,通过优化求解,产生动力学特性较好的轨迹.然而,面对当前越来越精确、丰富的先验地形信息,鲜有算法可以充分利用他们.对此,基于海底数字高程地图(digital elevation map,DEM),提出扩展A∗算法及FM(fast marching)算法改进算法,能够利用先验地形信息提高路径规划的效果.通过仿真分析,对比3种算法:扩展A∗算法、TC FM(terrian cared fast marching)和TC FM∗算法,仿真结果表明,扩展A∗算法求解速度更快、局部规划能力更强,TC FM和TC FM∗算法所求得的路径更短、更光滑.