家居设计系统中基于辅助射线的房间搜索算法

在家居设计系统中,房间的搜索是一个重要的问题,它是正确显示二维户型图以及生成三维虚拟房间的关键。论文以虚拟家居设计系统为应用背景,分析了家居设计过程中房间拓扑图到户型图的转换过程,通过引入辅助射线的概念,提出了一种规范化房间搜索算法,并用图论的理论加以形式化,该算法可以正确地搜索并绘制出房间。该算法在实际应用中取得了较好的效果。     

多段扰动的共享型乌鸦算法

乌鸦搜索算法作为新提出的元启发式智能算法,其寻优方式模拟了乌鸦间相互跟随窃食的行为。为了提高算法的收敛精度、后期搜索能力等,基于传统乌鸦搜索算法提出一种新的混合乌鸦搜索算法,其核心思想是在算法中加入共享机制,改进原始算法中随机追踪的位置更新方式,降低搜索盲目性,提高收敛速度;在不同的迭代阶段对全局最优位置进行大小不同的扰动操作,有效提高了跳出局部最优的概率,保证算法全局搜索能力与局部搜索能力的平衡。最后通过8个基准函数对5种算法搜索性能在10、30、50维的情况下进行对比分析,结果表明该改进算法的综合表现要优于其他算法。     

一种新的块匹配运动估值搜索算法及其硬件结构

针对二维运动估值中的块匹配,提出了一种适于硬件实现的改进快速算法,并给出了在FPGA上实现的具体硬件结构。该算法运算速度快,且硬件实现结构简单。搜索过程中不易陷入局部极小值点,因此产生的运动向量较传统快速搜索算法更加准确。经验证,该算法完全可以满足现代各种视频压缩系统对运动估值和块匹配模块的要求。     

求解可重入并行机调度的混合禁忌搜索算法

为解决带有一台远程服务设备的可重入并行机调度问题,设计了一种混合禁忌搜索算法。针对传统禁忌搜索算法只从单起始点搜索、容易陷入局部最优等缺点,混合禁忌搜索算法设计了一种Restart策略。当传统禁忌搜索算法陷入局部最优时,用Restart策略重新产生初始解以进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。数值实验中将混合禁忌搜索算法与启发式算法CS相比,结果表明该算法具有较高的求解质量,且其计算时间是可接受的。     

一种引入Nelder-Mead算子的改进狼群搜索算法*

为了克服狼群搜索算法(WSA)存在的不足,提出一种新的混合优化算法,称之为引入Nelder-Mead算子的改进狼群搜索算法。该算法使每只狼在搜索中可利用群体信息和个体记忆来指导其搜索猎物,以提高算法的全局搜索能力;让每只狼在搜索中可使用Nelder-Mead方法,以弥补WSA算法在局部搜索能力上的不足。针对12个基准测试实例的实验结果表明, 该算法能够寻得更优的最优解,且鲁棒性更强。     

改进的粒子群算法在VRP中的应用

将粒子群算法和禁忌搜索算法相结合构造禁忌搜索粒子群算法。提出一种对粒子群算法中全局最优解进行禁忌搜索的混合算法,扩展了粒子群算法进化方式。将其用于车辆路径优化问题求解。与基本粒子群算法相比较,结合禁忌搜索算法的粒子群算法明显提高了算法收敛速度和优化性能。     

N皇后问题的快速搜索算法

回溯算法是解决N皇后问题的经典算法,最坏情况下,它的搜索时间和皇后维数N成指数关系,无法满足基于Q_矩阵的LDPC码这种编码方案对码长的要求.介绍了一种解决皇后问题的快速搜索算法,它是使碰撞数最小化的本地搜索算法,这种算法的性能和回溯算法相比有极大的提高,搜索时间和皇后维数N基本成线性关系,并且有较强的灵活性,因而对于Q-矩阵LDPC码这种编码方案而言,快速搜索算法更为合适.     

基于混合遗传算法的水电站优化调度应用研究

在众多解决高维组合优化问题的工具中,遗传算法具有较好的全局搜索能力,而禁忌搜索算法则在局部搜索方面优势明显。本文根据水电站优化调度问题的实际特点,提出了遗传算法与禁忌搜索算法相结合的混合优化算法,采取禁忌搜索算法替换遗传算法变异算子的混合策略。以此算法对一个实例进行了模拟计算和分析。     

基数约束投资组合问题的一种混合元启发式算法求解

针对资产数目和投资资金比例受约束的投资组合选择这一NP难问题,基于混沌搜索、粒子群优化和引力搜索算法提出了一种新的混合元启发式搜索算法。该算法能很好地平衡开发能力和勘探能力,有效抑制了算法早熟收敛现象。标准测试函数的测试结果表明混合算法与标准的粒子群优化和引力搜索算法相比具有更好的寻优效率;实证分析进一步对混合算法与遗传算法及粒子群优化算法在求解这类投资组合选择问题的性能进行了比较。数值结果表明,混合算法在搜索具有高预期回报的非支配投资组合方面表现更好,取得了更为满意的结果。     

基于混合负载平衡的并行启发式搜索算法

在分析了迭代加深启发式搜索(Iterative Deepening A*)算法及其可并行性后,提出了一种新的基于混合负载平衡的并行迭代加深启发式搜索算法。该算法综合了静态负载平衡和动态负载平衡的优点,可以在多结点的并行搜索计算中获得很高的加速比和效率。给出了该算法的Java RMI实现。通过在72个结点的并行机上的试验表明,该算法可以极大地提高并行搜索算法的加速度和效率。     

多机器人协同搜索目标源及几何图形部署

近60年来,机器人已经快速发展,然而就目前的机器人作为自主个体的应用来看,几乎所有的机器人在完成任务的过程中,都是不能缺少位置信息的。但是当今世界有越来越多艰难的任务需要多个智能机器人在不了解位置信息的情况下协同进行作业,例如水下打捞作业。针对这一情况,利用已有的单机器人的极值控制算法结合反应对流扩散方程以及多机器人的协同控制算法仿真实现多机器人协同搜索光源,并且使多机器人在点光源周围的部署成一定的几何图形,如圆、椭圆等以便完成相应的任务。为了验证算法的有效性和可操作性,采用7个机器人进行协作搜索光源过程仿真并给出仿真结果。     

一类非完整轮式机器人的编队一致性

讨论了一类具有非完整约束和有向通信拓扑的轮式机器人的编队一致性问题.基于Zipf分布设计了带有耦合权重的编队一致性协议,减少了机器人间的信息交换,降低机器人编队在复杂的通讯环境中对所有机器人状态信息的依赖程度.将多机器人系统的编队一致性问题转化为误差系统的稳定性分析问题,给出了机器人形成编队的一致性条件,并利用图论和李亚诺夫稳定性理论证明在该条件下可实现系统编队收敛到期望的队形和虚拟领导者的运动规律上的目标.仿真实验和实物实验验证了所设计编队一致性协议的有效性.     

Performance of a class of multi-robot deploy and search strategies based on centroidal voronoi configurations

This article considers a class of deploy and search strategies for multi-robot systems and evaluates their performance. The application framework used is deployment of a system of autonomous mobile robots equipped with required sensors in a search space to gather information. The lack of information about the search space is modelled as an uncertainty density distribution. The agents are deployed to maximise single-step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for sequential deploy and search (SDS) and combined deploy and search (CDS) strategies. Completeness results are provided for both search strategies. The deployment strategy is analysed in the presence of constraints on robot speed and limit on sensor range for the convergence of trajectories with corresponding control laws responsible for the motion of robots. SDS and CDS strategies are compared with standard greedy and random search strategies on the basis of time taken to achieve reduction in the uncertainty density below a desired level. The simulation experiments reveal several important issues related to the dependence of the relative performances of the search strategies on parameters such as the number of robots, speed of robots and their sensor range limits.     

多机器人主—从行星式编队控制

研究了二阶积分器描述的多机器人主—从行星式编队控制问题,提出了将多机器人编队分解为每个机器人对各自具有时变速度的虚拟机器人的跟踪控制,使得每个机器人相对于虚拟机器人的位置与速度跟踪误差收敛为零且彼此不相碰撞,此时编队系统收敛到理想队形.在统一的算法框架下,分别实现了跟随者以领航者为中心的公转运动编队(revolution formation,RF)模式和跟随者与领航者保持期望距离、期望速度的编队(desiredformation,DF)模式.公转运动编队(RF)模式适用于异构多机器人系统的环境探索任务;保持期望距离、期望速度的编队(DF)模式适用于自主水下机器人(AUV)、无人机(UAV)等合作与协调任务.应用李亚普诺夫稳定性理论对控制算法的稳定性进行了分析,并通过计算机仿真验证了该方法的有效性.     

Efficient terrain coverage for deploying wireless sensor nodes on multi-robot system

Coverage and connectivity are the two main functionalities of wireless sensor network. Stochastic node deployment or random deployment almost always cause hole in sensing coverage and cause redundant nodes in area. In the other hand precise deployment of nodes in large area is very time consuming and even impossible in hazardous environment. One of solution for this problem is using mobile robots with concern on exploration algorithm for mobile robot. In this work an autonomous deployment method for wireless sensor nodes is proposed via multi-robot system which robots are considered as node carrier. Developing an exploration algorithm based on spanning tree is the main contribution and this exploration algorithm is performing fast localization of sensor nodes in energy efficient manner. Employing multi-robot system and path planning with spanning tree algorithm is a strategy for speeding up sensor nodes deployment. A novel improvement of this technique in deployment of nodes is having obstacle avoidance mechanism without concern on shape and size of obstacle. The results show using spanning tree exploration along with multi-robot system helps to have fast deployment behind efficiency in energy.     

改进的多移动机器人混合编队方法

在复杂环境下,针对Leader-Follower法和基于行为法相结合的多机器人混合编队方法配置参数难的问题,引入粒子群优化(PSO)算法,对5种行为参数进行在线优化,进而改进了传统的混合编队方法,使多机器人编队效果更优。同时通过仿真实验结果验证了所提出算法的可行性,且达到了实验预期的优化效果。     

基于QoE的无人机网络部署和缓存策略优化方法

为了最大限度提升用户的体验质量,设计了一个使用支持缓存的无人机进行辅助通信的蜂窝网络模型。该模型使用无人机通信和边缘缓存相结合的方式来进行流量卸载,通过联合优化无人机部署,缓存放置和用户关联以实现用户QoE的最大化,并使用平均意见得分来对其进行评估。基于问题定义,提出了一个无人机部署、缓存放置和用户关联的联合优化算法,以最大化MOS。该联合算法使用K-means聚类算法为用户创建基于用户位置的无人机部署集群,使用基于罚函数的凸优化算法以获得缓存放置策略,使用贪心算法以获得对用户的关联策略。多次仿真实验验证了所提出算法的有效性和可行性。实验结果表明,与三种基准算法相比,所提出的联合优化算法在MOS、回程流量卸载率和内容访问时延三方面均具有更好的性能。     

改进布谷鸟搜索算法在多机器人任务分配及路径规划中的应用

针对多机器人任务分配及路径规划问题,提出一种改进布谷鸟搜索算法求解多机器人任务分配及路径规划方法。根据任务点的环境信息和在其中寻找最佳机器人位置建立数学模型,并使用改进布谷鸟搜索算法求解任务分配及路径规划。改进的策略中融合了遗传算子、2-opt、模拟退火算法的Metropolis准则和插入、交换、逆序方法。不同规模的仿真实验表明,该方法能有效实现多机器人任务分配及路径规划问题,并为多机器人的续航能量提供科学依据。     

无线传感网络中有向性传感节点的覆盖问题

覆盖问题是无线传感网中最根本的问题之一,它在很大程度上影响到传感的质量。目前有关覆盖问题的研究大多集中于探讨全向性传感节点的覆盖问题,这些方法并不适用于如视频传感这类方向性的传感节点。提出了一个新的(k,ω)-夹角覆盖问题,探讨有向性的传感节点的覆盖问题,为了用最少的传感节点(k,ω)-夹角覆盖所有的目标,提出了一个贪心算法来解决这个问题。另外还提出了三个贡献度函数用于计算每个位置的贡献度,算法根据每个位置所提供的贡献度来决定传感节点的部署位置。仿真结果显示了算法的特性和性能的提升。     

Distributed control of multi-robot systems using bifurcating potential fields

The distributed control of multi-robot systems has been shown to have advantages over that of conventional single-robot systems. These include scalability, flexibility and robustness to failures. This paper considers pattern formation and reconfigurability in a multi-robot system using a new control algorithm developed through bifurcating potential fields. It is shown how various patterns can be achieved autonomously through a simple free parameter change, with the stability of the system proven to ensure that desired behaviours always occur.