规划算法（通用11篇）
规划算法 篇1
1 动态规划基本概念
在现实生活中, 有一类活动的过程, 由于它的特殊性, 可将过程分成若干个互相联系的阶段, 在它的每一阶段都需要做出决策, 从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定, 它依赖于当前面临的状态, 又影响以后的发展。当各个阶段决策确定后, 就组成一个决策序列, 因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程, 这种问题称为多阶段决策最优化问题。这种多阶段最优化决策解决问题的过程就称为动态规划。
2 动态规划基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中, 可能会有许多可行解。每一个解都对应于一个值, 我们希望找到具有最优值的解。动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解。与分治法不同的是, 适合于用动态规划求解的问题, 经分解得到子问题往往不是互相独立的。若用分治法来解这类问题, 则分解得到的子问题数目太多, 有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 这样就可以避免大量的重复计算, 节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到, 只要它被计算过, 就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样, 但它们具有相同的填表格式。
3 动态规划适用的情况
任何思想方法都有一定的局限性, 超出了特定条件, 它就失去了作用。同样, 动态规划也并不是万能的。适用动态规划的问题必须满足以下三点:
3.1 最优化原理 (最优子结构性质)
一个最优化策略具有这样的性质, 不论过去状态和决策如何, 对前面的决策所形成的状态而言, 余下的诸决策必须构成最优策略。简而言之, 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
3.2 无后向性
将各阶段按照一定的次序排列好之后, 对于某个给定的阶段状态, 它以前各阶段的状态无法直接影响它未来的决策, 而只能通过当前的这个状态。换句话说, 每个状态都是过去历史的一个完整总结。这就是无后向性, 又称为无后效性。
3.3 子问题的重叠性
动态规划算法的关键在于解决冗余, 这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术, 它在实现的过程中, 不得不存储产生过程中的各种状态, 所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受, 而搜索算法在时间上却无法承受, 所以舍空间而取时间。
4 求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题, 一般由初始状态开始, 通过对中间阶段决策的选择, 达到结束状态。这些决策形成了一个决策序列, 同时确定了完成整个过程的一条活动路线 (通常是求最优的活动路线) 。动态规划的设计都有着一定的模式, 一般要经历以下几个步骤:初始状态—决策1—决策2—……—决策n—结束状态。
4.1 划分阶段
按照问题的时间或空间特征, 把问题分为若干个阶段。在划分阶段时, 注意划分后的阶段一定要是有序的或者是可排序的, 否则问题就无法求解。
4.2 确定状态和状态变量
将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然, 状态的选择要满足无后效性。
4.3 确定决策并写出状态转移方程
因为决策和状态转移有着天然的联系, 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策, 状态转移方程也就可写出。但事实上常常是反过来做, 根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
4.4 寻找边界条件
给出的状态转移方程是一个递推式, 需要一个递推的终止条件或边界条件。
一般, 只要解决问题的阶段、状态和状态转移决策确定了, 就可以写出状态转移方程 (包括边界条件) 。实际应用中可以按以下几个简化的步骤进行设计:
(1) 分析最优解的性质, 并刻画其结构特征。
(2) 递归的定义最优解。
(3) 以自底向上或自顶向下的记忆化方式 (备忘录法) 计算出最优值。
(4) 根据计算最优值时得到的信息, 构造问题的最优解。
5 动态规划实现的说明
动态规划的主要难点在于理论上的设计, 也就是上面4个步骤的确定, 一旦设计完成, 实现部分就会非常简单。使用动态规划求解问题, 最重要的就是确定动态规划三要素:
(1) 问题的阶段。
(2) 每个阶段的状态。
(3) 从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化, 从这个角度来说, 动态规划往往可以用递归程序来实现, 不过因为递推可以充分利用前面保存的子问题的解来减少重复计算, 所以对于大规模问题来说, 有递归不可比拟的优势, 这也是动态规划算法的核心之处。
确定了动态规划的这三要素, 整个求解过程就可以用一个最优决策表来描述, 最优决策表是一个二维表, 其中行表示决策的阶段, 列表示问题状态, 表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值 (如最短路径, 最长公共子序列, 最大价值等) , 填表的过程就是根据递推关系, 从1行1列开始, 以行或者列优先的顺序, 依次填写表格, 最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
6 动态规划算法基本框架
代码如下所示:
摘要：本文通过系统的介绍动态规划算法的基本概念、基本思想、适用情况分析、基础求解步骤、实现的说明和算法的基本框架, 对动态规划算法进行了总结和概述。
关键词：算法,动态规划,最长公共子序列
参考文献
[1]网上的文献 (举例:最长公共子序列-动态规划-算法导论实践[EB/OL].http://hi.baidu.com/jiaxiaobosuper/item/5f0e7510979bb0413b176e4b, 2011-03-27.
[2]Wang Xiaodong.Design and analysis of computer algorithms[Z].Beijing:Publishing House of electronics industry, 2012.王晓东.计算机算法设计与分析.北京:电子工业出版社, 2012.
规划算法 篇2
机械臂运动路径规划的算法设计
我们对题目中所给的特定的六自由度机械手臂设计一整套通用的算法.让它能够实现点到点移动,有障碍的曲线跟踪,和避障点对点移动三种基本功能.并能自动生成控制台所需要的指令序列,最后我们会对模型的.适用范围和准确性进行评价.
作 者：朱猛 邓国兴 姜宇 ZHU Meng DENG Guo-xing JIANG Yu 作者单位：华南理工大学,计算机科学与工程学院,广州,510006 刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY 年，卷(期)：2008 38(14) 分类号：O1 TH12 关键词：齐次坐标变换 避障问题 路径规划 曲线跟踪 人工势场 机械优化设计智能机器人避障路径规划算法研究 篇3
最后，验证基于Bug算法的几种路径规划方法，将避障实时性，环境的适应性、规划路径的优化性作为算法性能指标，进行仿真实验与对比实验分析。结果验证了算法的有效性。
关键词：智能机器人；避障；MATLAB仿真；路径规划
1 绪论
智能机器人避障算法的研究对于推进机器人领域的应用和发展具有重要的意义。随着计算机技术、传感器技术、控制技术的发展，智能机器人的避障技术已经取得了丰硕的研究成果，其应用领域不断的扩大，应用复杂程度也越来越高，因此对其关键技术提出了更高要求，相应的方法也更加成熟。
本文通过查阅文献资料，对目前智能机器人的发展动态有了一定了解。对现阶段机器人避障的一些常用方法做了研究，然后设计了不同算法在未知环境下的避障仿真实验来验证本文所设计的算法的可行性。路径规划要求机器人能够在较短的时间内，感知到范围尽可能大的区域，从而找到最近的路径使机器人能够沿着最优路径运动到终点，并避开障碍物。
2 基于动态窗口的避障算法及仿真
2.1 概述
机器人局部路径规划的方法很多，动态窗口法就是其中的一种，其主要是在速度（v，w）空间中采样多组速度，并模拟机器人在这些速度下一定时间内的轨迹。在得到多组轨迹以后，对这些轨迹进行评价，选取最优轨迹所对应的速度来驱动机器人运动。该算法突出点在于动态窗口这个名词，它的含义是依据移动机器人的及速度性能限定速度采样空间在一个可行的动态图范围内。
2.1.1 机器人的运动模型
在动态窗口算法中，要模拟机器人的轨迹，需要知道机器人的运动模型。它采用的是假设两轮移动机器人的轨迹是一段一段的圆弧或者直线（选择速度为0），一对（Vt，Wt）就代表一个圆弧的轨迹。具体推导如下：
在这里，假设不是全向运动机器人，它做圆弧运动的半径为：
2.1.2 速度采样
机器人的轨迹运动模型有了，根据速度就可以推算出轨迹。因此只需采样很多速度，推算轨迹，然后评价这些轨迹好不好就行了。
速度如何采样是动态窗口的核心：在速度（v，w）的二维空间中，存在无穷多组速度。但是根据机器人本身的限制和环境限制可以将采用速度控制在一定范围内：
移动机器人受自身最大速度最小速度的限制：
移动机器人受电机性能的影响：
由于电机力矩有限，存在最大的加速度限制，因此移动机器人轨迹前向模拟的周期内，存在一个动态窗口，在该窗口内速度是机器人能够实际达到的速度：
其中是机器人的当前速度，其他标志对应最大加速度和最大减速度。
基于移动机器人安全的考虑：
为了能够在碰到障碍物前停下来，因此在最大速度条件下，速度有一个范围：
为了简化每组速度对应轨迹的计算，该算法假设机器人在往前模拟轨迹的这段时间内速度不变，直到下一时刻采样给新的速度命令。
2.2 评价函数
在采样的速度组中，有若干组轨迹是可行的，因此采用评价函数的方式为每条轨迹进行评价。采用的评价函数如下：
2.3 方位角评价函数
方位角评价函数是用来评价机器人在当前设定的采样速度下，达到模拟轨迹末端时的朝向和目标之间的角度差距。
若采用的方式来评价，也就是越小，评价得分越高。
2.4 空隙
代表机器人在当前轨迹上与最近的障碍物之间的距离。如果在这条轨迹上没有障碍物，那就将其设定一个常数。
2.5 速度
Velocity（v，w）用来评价当前轨迹的速度大小。总结起来三者构成的评价函数的物理意义是：在局部导航过程中，使得机器人避开障碍，朝着目标以较快速度行驶，缺一不可。
2.6 matlab仿真（图1）
3 Bug2避障算法的研究与仿真
3.1 未知环境下基于Bug算法的移动机器人路径规划研究改进
在未知环境下的移动机器人路径规划己经有一些成熟实用的算法。这里介绍的爬行虫Bug算法就是一例。本章在已有的Bug族算法基础上，对传统Bug算法进行了改进，提高了Bug算法路径规划的优化性和实时性。
3.2 Bug2算法原理
Bug2算法在Bugl算法基础上进行改进，引入了从起点到终点的直线M。具体思想如下：
3.2.1 沿着直线M向障碍物移动，直到发生以下两种情况：
①到达终点，结束算法；
②遇见障碍物，标记为，转到3.2.2。
3.2.2 沿着障碍物左边移动，直到发生以下三种情况：
①到达终点，结束算法；
②找到一个点，满足条件，且该点在M上，则转到3.2.1；
③机器人回到相遇点，则表示机器人绕行一周，终点不可到达。
可知Bug2算法在Bugl算法上对从Hl运动到Hl的路径循环进行了改进，但是机器人的运动方向是固定的初始值，即算法规定为沿障碍物左边移动，那么在所有的沿障碍物移动的状态中，机器人都是向障碍物左方移动。
3.3 算法设计
本文提出的路径规划算法可在线运行，进行实时运动规划，对未知环境下的
机器人路径规划，该算法具有很好的环境适应性。
3.4 Bug2算法仿真（图2）
4 总结与展望
本论文在许许多多机器人研究者的研究经验与研究成果之基础上，综合相关的理论基础知识，对智能机器人进行了相关的研究。主要针对其避障控制算法及路径规划方案作了一定的研究和探讨，提出了相对有效的模糊控制算法和田埂式路径规划方案，并经过一系列的仿真实验来对本文中使用的算法和方案的稳定性及可行性进行验证。对于本研究课题，本人主要做了以下工作：
①综述智能机器人国内外研究及应用现状，了解到智能机器人在完成任务的过程中遇到障碍物或者落差区域时容易发生碰撞和跌落，而且其清洁路径不能做到全覆盖，重复率也较高。因此，本文将智能机器人的研究方向确定为避障和全覆盖路径规划这两个方面。
②简要论述了模糊控制算法，而且将其应用至智能机器人的避障控制之中，并且设定了模糊控制器以及模糊规则，使其适应于本文中所研究的智能机器人，让智能机器人在执行任务过程中能够避开障碍物并防止跌落，并且对本论文中提出的避障控制进行算法有效性仿真实验，证明了该算法是有效且可靠的。
③简要介绍路径规划的原理及分类，并就比较经典的算法作出了简要描述。研究了基于栅格地图法的田埂式路径规划方案，描述了该方案中的环境地图构建，运行模式，死角解决方案，并针对该方案进行了不同环境不同障碍物分布情况下的仿真实验，分别对比了无障碍环境下，有障碍无死角环境下，有障碍及简单死角环境下，有障碍及复杂死角环境下，有障碍及多种死角环境下的仿真实验结果，均验证了本论文所设计的路径规划方案能使智能机器人做到区域环境全覆盖并己最短路径跳出死角，提升了机器人清洁工作的完整性与高效性。
在本课题的研究过程中，一些不足之处也显现出来。例如栅格大小的划分是一个难点，栅格太大容易使准确率降低，影响机器人清洁效果，栅格太小会使算法复杂，导致运行速度过慢，也会对智能机器人的清洁效果有影响。另外，本文中所研究的都是静态障碍物，忽略了动态障碍物的研究，生活中的小动物和可动型玩具等也是机器人清洁工作中极易遇到的障碍物，因此，动态障碍的研究是很有必要的。这些问题都将是以后的研究工作中需要继续解决的。
在未来，智能机器人以及其他家用型机器人将会愈来愈频繁的进入到人类的生活和工作中，所以对于它们的研究很有必要性，且在很长一段时间内都将是一个热点。避障控制与路径规划更将是研究工作中的重中之重，未来的研究成果必将会在这两个方向突飞猛进，同时提高智能机器人的工作效率，避障运行的灵活性都将是研究热点。
DC规划的分支算法 篇4
DC规划是优化问题中最重要的一类, 为了更好地估计DC规划的最优值点, 很多文章[1—5]对其进行了各方面的研究。在结合已有的局部收敛算法及DCA算法的基础上讨论了DC规划的线性上下界, 并提出了分支算法, 这使得DC规划能做到全局收敛, 在许多工程问题中常会碰到类似求全局解问题。因此, 对DC规划全局解的研究具有十分重要的意义。
考虑带一般约束的DC规划的最优解问题
其中yl和yu分别是定义域的上下界, fj (y) 为目标函数, 也是DC函数, 称
为fj (y) 的DC分解, 其中Υj (y) 和Χj (y) 均为定义在Rn上的凸函数。
1 DC规划的线性上、下界
结合凸函数的性质, 提出用线性函数近似代替DC函数的思想。
定理1对任意y, y Y, y= (y1, …, yn) T∈Y, 则线性函数
满足:y∈Y, Χjl (y) ≤Χj (y) ≤Χju (y) , 其中Χju (y) 是Χj (y) 在Y上的闭包, Χjl (y) 是Χj (y) 的切平面, 且与Χju (y) 平行, 而y0满足:
证明因为函数Χjy在Y上是凸函数, 因此Χj (y) 在y, y上的凹包为
即为连接两点 (y, Χj (y) ) , (y, Χj (y) ) 的线段, 而与这条线段相平行的Χj (y) 的切线, 其切点 (y0, Χj (y0) ) 满足
则相应的切线为:
再根据Χjy的几何性质, 令
所以有
因为Υj (y) 是凸函数, 则
所以fj (y) =Υj (y) -Χj (y) ≥Υj (yk) +[Υj (yk) , y-yk]-Χju (y) 。
(y) 。
则得到了问题 (DCP) 的松弛线性规划 (DCP 1) :
2 分支算法
为了找出DC规划的全局最优解, 可以考虑在线性化的基础上再缩短约束区间, 随着区间的变小, 最终总可以收敛到全局最优解。
2.1 双分规则
考虑任一结点子问题, Y′=y′, y′Ψ, 令p=argmax y′i-yi′:i=1, …, n, 但是p不一定唯一, 从而将小区间yp′, y′p分为yp′, yp′+2 y′p和yp′+y′p
, y′p两部分, 对于其它i p的小区间
2
yi′, y′i, 保持原样, 并不分为两部分。由上面的规则得到两个新的区间。
令β (Yk) 表示问题 (DCP 1) 在区间Yk上的最优值, yk=yYk表示相应的最小值点。
2.2 分支算法
令β (Yk) 表示问题 (DCP) 在区间Yk上的最优解, yk=y (Yk) 表示相应的最小值点。
S0:初始化
令k=0, 所以活动结点的集合为Q0=Y0, 上界α=∞, 可行点的集合F=。
给定参数ε>0, 求解 (DCP 1) , 得到其在y0=y (Y0) 处的最优目标值为β0=β (Y0) , 更新F和α, F=F∪{y0}, α=f0 (y0) , 若α≤β0+ε, 则算法停止, y0是问题的最优解, 否则, 执行S1.
S1:选择Yk的中点ymid, 令F=F∪ymid, 定义上界α=ym∈iFnf0 (y) , 若F≠, 则最好的可行点为
S2:由分支规则, 对区间Yk分块, 可以得到两个新的子超矩形, 称包含这新的子超矩形的集合为Sk.对每一个Y∈Sk, 计算ym∈iYngj (y) , 若ym∈iYngj (y) >α, 则从Sk中删去相应的Y, 令Sk=Sk Y, 考虑Sk中另一元素。若Sk≠, 求解相应的 (DCP1) , 得到β (Y) 以及相应的y (Y) , 对任意Y∈Sk。若β (Y) >α, 令Sk=Sk Y, 否则S1中更新α, F和b的值。
S3:剩余的分块集为Qk= (Qk Yk) ∪Sk, 给定一个新的下界βk=Ym∈iQnkβ (Y) .
S4:令Qk+1=Qk Y:α-β (Y) ≤ε, Y∈Qk, 若Qk+1=, 则算法停止, α为问题 (DCP) 的最优值, b为其最优解, 否则令k=k+1, 转入S5。
S5:选择一活动结点满足
3 算法的收敛性
引理1考虑问题 (DCP) 和 (DCP1) , 在算法执行的第k步迭代中, 对任意Y∈Ok, 设Y={y:li≤yi≤ui, i=1, …, n}, λ= (λ1, …, λn) , 其中λi=uili, i=1, …, n, 又对任意y∈Y, 记Dj (y) =fj (y) -gj (y) , j=0, 1, …, m, 则Dj (y) 在Y上的最大值Dj.max (y) 满足λ※li m0+Dj.max (λ) =0, j=0, 1, …, m。
证明由线性化技术, 得到
Χju (y;Y) ,
其中
所以
Χju (y;Y) -Χj (y) ,
则
Χj (ui) -Χj (li)
Χj (li) -Χj (y0) -λi (li-y0) 。由中值定理
其中ξ∈Y, 则有
其中y0∈Y, 且y0满足
所以
令Ya表示聚点的集合, D (≠) 为问题 (DCP) 的可行域, Y*=aryg∈mDinf0 (y) 。
定理2节2.2的算法满足下面的性质:
(1) 算法S2步中分块集的细分在Y0上是穷举的;
(2) 在S2步中被选择用来进行分块的集合的边界在逐步得到改进;
(3) 问题 (DCP 1) 中使用的线性子函数gj (j=0, 1, …, m) 在Y0上是严格一致的, 并且算法或者在有限步终止, 得到问题 (DCP) 的最优解, 或者产生一分枝定界树的无穷序列, 满足β:=kli※m∞βk=ym∈iDnf0 (y) , Ya Y*。
证明对于算法的每一次迭代, k=0, 1, …, 假设下面为真:
很显然{βk}是一非下降序列, 且有界, 因此{βk}存在极限
又yk是在紧集上的序列, 因此它存在收敛子序列, 对任意y∧∈Ya, 存在序列yr yk, 且r※lim∞yr=y∧, 由给定的算法以及参考文献[5], 性质1和性质2成立, 根据引理1, 性质3也是满足的, 因而, 由性质1和性质2, 存在一下降序列Yq Yr, 其中Yr∈Qr, 且yq∈Yq, βq=β (Yq) =g0 (yq;Yq, σ) , qli※m∞yq=y∧, 由性质3, 得到qli※m∞βq=β=f0 (y∧) 。
因为Y0是闭集, 因此y∧∈Y0, 假设y∧D, 则肯定存在某个j (=1, 2, …, m) , 使得
gj (y∧) =δ+tj>tj。对某个j=1, …, m, 因为gj是连续的, 则序列gj (yq) ※gj (y∧) , 由收敛性的定义, 存在qδ, 使得当q>qδ时, gj (yq) -gj (y∧) <δ, 因此当q>qδ时, gj (yq) >tj, 这表示问题 (DCP 1) 是不可行的, 则违背了假设yq=y (Yq) , 矛盾, 因此y∧∈D。所以β=f0 (y∧) =ym∈iDnf0 (y) , y∧∈Y*。
4 数值例子
考虑问题
通过C++编程, 得到问题的最优解为x1=0.997 122 35,
参考文献
[1]Tao P D, An L T H.Convex analysis approach to DC programming:Theroy, algorithms and applications.Acta Mathematica Vietnamica, 1998;22 (1) :289—355
[2]An L TH, Tao P D.A combined D.C.optimization-ellipsoidal branch and bound algorithm for solving nonconvex quadratic programming problems, Journal of Combinatorial Optimization, 1998;2:9—28
[3]An L TH, Tao P D.A branch and bound method via DC optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems.Journal of Global Optimization, 1998;13:171—206
[4]An LTH, Tao P D, Hao D N.Solving an Inverse problem for an ellip-tic equation by DC programming.Journal of Global Optimization, 2003;25:407—423
规划算法 篇5
求解随机凸规划概率约束问题的对偶算法
1 引言 随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的.求解非常困难.如果目标函数是线性的,问题的求解就比较容易.[5]给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法[3]和切平面算法[6]是比较有效的.
作 者：唐恒永 赵传立 Tang Hengyong Zhao Chuanli 作者单位：沈阳师范大学数学与系统科学学院,沈阳,110034刊 名：高等学校计算数学学报 ISTIC PKU英文刊名：NUMERICAL MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES年，卷(期)：30(2)分类号：O221.5关键词：
规划算法 篇6
关键词： 蚁群算法； 信息素策略； 能见度
中图分类号： TP 391.4文献标志码： Adoi： 10.3969/j.issn.10055630.2015.03.016
Abstract： The highthroughput monoclonal colony selection instrument is a highend equipment applied to biological cell engineering which contains the technologies of optical imaging， image recognition and automatic control. For the 12×8 probe array and the targets in random order， only the optimization of selected path and order can improve the throughput. Thus， this paper presents the principle of the basic ant colony algorithm and optimizes the selection path based on the algorithm. Then results of the experiment prove the method can greatly improve the selection efficiency.
Keywords： ant colony algorithm； pheromone update strategy； visiability
引言单克隆菌落挑选仪是集光学成像、图像识别和自动控制等技术于一身，应用于生物工程领域的一种高端仪器，在我国处于起步研制阶段。在经过诱变和培养的数以万计的菌株中，仅有百分之几是符合要求的高性能菌株。传统的挑选菌株方式是通过目视菌落形态颜色等特征，人工方式取出优质菌株，该方法不仅重复性差，而且效率极低。为了提高挑选效率和可靠性，美国、德国、瑞士等国相继开发出基于光学成像和图像识别技术的单克隆菌落挑选仪。其工作原理是对菌落图像进行分析，通过分析菌落形态、大小、圆度、长短径比和颜色等特征，进而标记出高性能菌落[12]，并利用机械手带动探针实现菌落的挑取和转移。单克隆菌落挑选仪的一个重要考核指标是单位时间内能完成的操作数量（即通量），通量与机械手行走的路径直接相关。因此为了实现高通量，需要找到最科学合理的挑选路径，这也是仪器研发面临的重要问题之一。图1菌落挑选仪探针阵列
Fig.1Probe array on selection instrument菌落挑选仪探针阵列如图1所示，机械手末端为12×8的探针阵列，菌落目标则随机分布在圆形培养皿区域内。随机械手移动到相应位置，探针逐一伸出，每根探针挑取一个目标后，一次性放入标准96孔深孔板。在设计初期，每次挑选匹配间隔距离最小的探针和菌落目标，以期通过减小单次运动量缩短总路径长度，该方法称为最近点法。最近点法是一种贪心算法，单次运动量对路径优化具有启发性，但不是决定性的。针对这一典型的组合优化问题，本文使用蚁群算法进行优化。
1蚁群算法及其在路径优化中的实现
1.1蚁群算法蚁群算法是一种模拟蚂蚁群体觅食行为的仿生优化算法[3]，觅食过程中，虽然每只蚂蚁的智能和认知水平有限，但是通过个体与个体之间基于生物化学物质的通信，相互影响，最终能适应苛刻的环境，解决复杂的问题，这是一种群体智能。图2为反映群体智能的双桥实验。
如图2（a）所示蚁穴A与食物D之间存在障碍，起初蚁穴中的蚂蚁随机地寻找能绕过障碍搬运食物的路径，同时在这些路径上留下能被同伴嗅觉捕捉的信息素。不同的路径长度不一，如图（b）中的ABD、ACD，蚂蚁往返在较短的路径上将留下更多的信息素，随着信息素的浓度的差异，大多数的蚂蚁将选择较短的路径如图（c）所示。蚁群算法即仿照蚂蚁群的这种行为特征，利用一组数据作为算子间通信的生物信息素，启发算法进行寻优搜索，可以解决复杂的组合优化问题。假设有n个目标地点，开始有m只蚂蚁随机地分布在n个地点上，记t时刻i到j的路径lij上的信息素强度为τij（t），在t+1时刻，m只蚂蚁各自向下一目标移动，为了防止蚂蚁反复经过同一目标，需设置禁忌表tabu，记录已经去过的目标，随移动进程变动。蚂蚁k在t时间内选择i到j的路径lij的概率可以根据路径上的信息素计算出[4]Pkij（t）=[τij（t）]α·[ηij（t）]β∑sallowedk[τis（t）]α·[ηis（t）]βjallowedk
0else（1）式中：allowedk表示蚂蚁k下一步允许选择的目标，即全部目标集合C减去k的禁忌表集合；α为信息启发因子，表征信息素在路径选择时的作用；β为期望启发因子，表征距离启发因素（能见度）在路径选择时的作用；ηij为启发函数，是路径长度dij的倒数。每次蚂蚁完成了一条路径，就会更新各处的信息素。遍历过n个城市后在路径lij上的信息素为τij（t+n）=ρτij（t）+Δτij（2）
Δτij =∑mk=1Δτkij（3）式中，ρ为挥发系数，Δτij为在该次移动中由其他蚂蚁留下的信息素，Δτkij为蚂蚁k在路径lij上留下的信息素。根据基本的信息素策略[3]，信息素表达式为Δτkij=QLk第k只蚂蚁经过路径lij
nlc202309011923
0第k只蚂蚁并未经过路径lij（4）式中，Q为为信息素强度，Lk为蚂蚁走过的长度。
1.2蚁群算法在挑选仪单克隆菌落挑选仪优化中的实现蚁群算法可用在求解旅行商问题，旅行商问题（travelling salesman problem，TSP）即为一名旅行商需要去拜访若干城市，寻找只拜访各城市一次后返回出发点的最短路线的问题。其数学模型描述[5]为C={c1，c2，…，cn}为城市，L={lijci，cjC} 是集合C中元素两两之间的路径集合，dij为lij长度。G=（C，L）是一个有向图，求解旅行商问题是从G中找到长度最短的Hamilton圈。区别于传统旅行商问题，在对挑选仪进行优化时，需要做以下处理：（1）在对挑选仪路径优化时，相对目标移动的不是一个点，而是矩形探针阵列（以下称运动针盘），算法中的每次移动取决于运动针盘上要使用的探针p以及目标菌落t，组合集合C={（p，t）p∈P，t∈T}（P，T分别为96枚探针的集合和96处菌落目标的集合），由于探针和菌落均不重复使用，故约束任意两个C的元素ck=（pi，ti）和cl=（pj，tj），有pi≠pj且ti≠tj。（2）运动针盘安装在正交的二维导轨组成的机械手上，由伺服电机驱动，以脉冲信号控制。在常加速度模式下，伺服电机接收到指定脉冲信号开始以a=0.3 g起步加速，加速至预先设定的工作速率vm，脉冲停止时开始减速刹车[6]。在统计行程时依据机械手运动的两个特点①两条导轨分别由各自电机驱动，定位时间由两条导轨中行程长的一维决定；②电机的行程和时间对应关系可视为为线性关系t=vma+svm。（3）蚁群算法工作建立在个体通信的基础上，对于大规模TSP问题，使用蚁群算法会产生极其庞大的运算开销，本文研究的探针与目标组合数达到了962，完整的信息素记录可能多达几千万组，因此平衡通信开销和搜索空间的充分性是改进蚁群算法的必要工作。算法工作者为改进蚁群算法提出了多种信息素更新策略[7]。在解决本问题时，引入能见度阈值的概念，运动针盘可选路径很多时（如在最开始的几步），决定运动方向前先根据各目标位置进行初步过滤，忽略运动跨度较大的路径上的信息素，这种跨越必然是不合理的。一种阈值设置方法Qd=w（dmin+dmax），其中系数w∈（0，1），dmin、dmax分别为未使用的各探针与各目标的距离的最小、最大值。此外，在算法程序中设置信息素字典动态记录路径被采用的概率，信息素持续挥发值小于一定值时，将此记录删除以节省存储空间。
2模拟仿真实验
2.1实验设计本文根据蚁群算法编写了优化程序，并设计了仿真实验测试优化效果。在直径9 cm的区域内随机生成96个点作为菌落目标，探针排列为12列8行，相邻间隔9 mm，在菌落区域移动仿真图见图3。根据菌落挑选仪在图像捕获时刻的位置关系，将两者初始相对位置设定为常数。目标排列的形状与探针形状相符的程度决定着最优解的大小，极端情况下，目标排列与探针阵列完全相同，则整个挑选过程只需一次移动。为了减少“巧合”造成的影响，实验通过对多组目标优化，分析最优解的收敛情况。
2.2实验结果实验参数[89]中α=2.5、β=4.5、ρ=0.5、Q=400、m=20。绘制出平均路径长度收敛曲线如图4，由图中可见，算法在1次迭代将最优解值收敛到415 mm，在5次内开始优于最近点法，随迭代次数增加，收敛逐渐趋于平缓。图5反映了不同样本分别用最近点法和蚁群算法优化最终结果的差异。经过蚁群算法优化，路径总长度相比最近点法得到进一步缩短，而且没有因样本差异产生显著波动。
3结论本文针对单克隆挑选仪研发中遇到的挑选路径优化问题，结合机械手运动特点，将探针与目标组合，构成抽象城市的概念，根据蚁群算法，对最优挑选步骤进行了启发式优化，并采取适当的信息素策略控制运算规模。模拟实验结果表明，蚁群算法的应用有效地减少了菌落挑选探针的移动距离，从而提高了仪器通量。参考文献：
[1]周莹莉，曾立波，刘均堂，等.基于图像处理的菌落自动计数方法及其实现[J].数据采集与处理，2003，18（4）：460464.
[2]陈东科.加强形态学检查提高细菌鉴定的准确性[J].实验与检测医学，2012，30（5）：419422.
[3]ERIC B，MARCO D，GUY T.Swarm intelligence：from natural to artificial systems[M].Oxford：Oxford University Press，1999.
[4]李士勇，陈永强，李研.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.
[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.
[6]黄兆斌，黄云龙，余世明.几种步进电机加减速方法的对比研究及其应用[J].机电工程，2011，28（8）：951974.
[7]岑宇森，熊芳敏，曾碧卿.基于新型信息素更新策略的蚁群算法[J].计算机应用研究，2010，27（6）：20802083.
[8]詹士昌，徐婕，吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报，2003，19（5）：381386.
[9]吴春明，陈治，姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报，2006，（8）：15301533.
（编辑：张磊）
线性规划求解算法研究 篇7
在经济管理、交通运输、工农业生产等经济活动中, 提高经济效果是人们不可缺少的要求, 而提高经济效果一般通过两种途径:一是技术方面的改进, 例如改善生产工艺, 使用新设备和新型原材料.二是生产组织与计划的改进, 即合理安排人力物力资源。线性规划所研究的是:在一定条件下, 合理安排人力物力等资源, 使经济效果达到最好。一般地, 求线性目标函数在线性约束条件下的最大值或最小值的问题, 统称为线性规划问题。满足线性约束条件的解叫做可行解, 由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的3要素。线性规划是运筹学的一个重要分支, 自1947年 乔治·伯纳德·丹兹格 (G.B.Dantzig, 1914—2005) 提出了一般线性规划问题求解的方法——单纯形法之后, 线性规划在理论上趋向成熟, 在实用中日益广泛和深入。
1 线性规划——数学模型
要对实际规划问题作定量分析, 必须先加以抽象, 建立数学模型。在建立线性规划模型时, 需要有关的专业知识, 并要有一定的经验和技巧。建立线性规划模型包括:①明确问题的目标和划定决策实施的范围 (包括时间界限) , 并将目标表达成决策变量的线性函数, 称为目标函数;②选定决策变量和参数。决策变量就是待决定的问题的未知量, 一组决策变量的取值即构成一个规划方案。决策变量的选定往往需要对问题进行仔细的分析;③建立约束条件。问题的各种限制条件称为约束条件。每一个约束条件均表达成决策变量的线性函数应满足的等式或不等式。约束条件往往不止一个, 通常表达成一组线性等式或不等式。线性规划问题就是在决策变量满足一组约束条件的情况下使目标函数达到极大值或极小值。 一般线性规划模型的形式为:
max (或min)
undefined
s.t.
undefined
式中max表示求极大值;min表示求极小值;s.t.表示受约束于或约束条件是;Z为目标函数;xj为决策变量;aij, bi和cj分别为消耗系数、需求系数和收益系数, 在具体的线性规划问题中具有不同的经济学意义, 一般都是已知实数。在线性规划中满足约束条件的一组数 (x1, x2, …, xn) 称为问题的一个可行解, 全体可行解构成的集合称为问题的可行域。在可行域上使目标函数取得极大值 (或极小值) 的可行解称为问题的最优解, 对应的目标函数值称为最优值。
2 线性规划——应用问题
在工业、农业、商业、行政、军事、公用事业等各个领域, 存在着大量的线性规划问题。有些规划问题本身是非线性的, 但往往可以通过改变标度或采用分段线性化等方法, 转化为线性规划模型。
用线性规划求解的典型问题有运输问题、生产计划问题、配套生产问题、下料和配料问题等。
(1) 运输问题。
某产品有n个产地, m个销地。已知各产地的产量和各销地的销量, 以及各产地到各销地的单位运价, 问如何安排各产地到各销地的运量, 使总的运费为最少?
(2) 生产计划问题。
用m种资源生产m种产品。已知各种产品每生产一单位可得的利润和所需的各种资源的数量, 以及各种资源的限额。问如何计划各种产品的生产量, 使总的利润为最大?
(3) 配套生产问题。
用若干台机床加工某种产品的各种零件。已知各机床加工不同零件的效率。问如何分配各机床的任务, 在零件配套的前提下使一个生产周期内的产量最高?
(4) 下料问题。
将一批固定规格的条材或板材裁剪成具有规定尺寸的若干种毛坯, 并已设计出若干种下料方式。问采用哪种下料方式, 能使各种毛坯满足所需数量, 又使总的用料最省?
(5) 混合配料问题。
用n种原料配制某些含有m种成分的产品。已知各种成分在各种原料中的单位含量, 以及各种原料的单价和限额。问怎样混合调配, 在满足产量要求和产品所含各种成分的要求下使成本为最低?
3 单纯性算法基本步骤
(1) 把线性规划模型变成它的标准形式。
(2) 确定初始基可行解, 建立初始单纯形表。
(3) 检查对应于非基变量的检验数λj, (j∈N) ;若所有这些λj均小于零, 则已得到最优解, 停止计算, 否则转入下一步。
(4) 在所有的λj>0中, 若有一个λk在单纯形表上对应的列向量的全部元素yik≤0 (i=1, 2, …, m) , 则此问题无解, 停止计算;否则转入下一步。
(5) 根据max{λj>0|j∈N}=λk, 即确定λk对应的非基变量λk为进基变量;再根据
undefined
确定基变量xr为离基变量。
(6) 基可行解的转换运算, 即实施行变换, 将单纯形表上xk对应的列向量变换为单位向量, 其中包括将λk变换为0, 而原yrk变换为1, 称元素yrk为变换轴心。
4 单纯形法的进一步讨论
现在已有单纯形法的标准软件, 可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度, 又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题, 也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解, 但实用价值不大。以下一个例子通过图解法求解, 可以理解线性规划的更多概念。
例如, 某工厂生产A, B两种产品, 已知生产A1kg, 耗煤9t, 耗电4kw, 用劳力3个工;生产B1kg, 耗煤4t, 耗电5kw, 用劳力10个工。已知生产1kg A的利润是500元, 生产1kg B的利润是900元。现根据工厂条件, 只能提供煤360t, 电力200kw, 劳力300个工。问如何安排两种产品的生产量, 才能使总的利润最大。
设A, B 的产量分别为x1, x2 (千克) , 则上述问题的线性规划模型是:
max Z=5x1+9x2
s.t. 9x1+4x2≤360
4x1+5x2≤200
3x1+10x2≤300
x1≥0, x2≥0
此问题的可行域为图中的多边形区域, 即阴影部分。目标函数的等值线为平行于直线 l的平行直线族。将直线l向右上方平行移动, 对应的目标函数值逐渐增大, 在即将脱离可行域之际, 它与可行域的交点便对应于问题的最优解。由此可知, 在可行域的顶点B 处, 目标函数达到最大值。因此, 问题的最优解为:x1=20千克, x2=24千克, 最大总利润为3.16万元。
摘要：线性规划 (Linear programming, 简记为LP) 模型是运筹学中的一个重要内容, 其基本解法——单纯形方法 (Simplex method) 则是处理运筹学模型的一种主要方法, 用于如何对有限的资源做出最佳方式的调配和最有利的使用, 以便最充分地发挥资源的效能去获取最佳经济效益。就一般线性规划问题求解方法——单纯形法作了详尽的综述。对线性规划进行了概述, 具体从线性规划发展简史、线性规划问题的数学模型和线性规划常见的一些应用3个方面进行了较详尽的综述;进行了单纯形法的概述, 这一部分主要涉及了单纯形法解题的基本步骤以及对单纯性算法作了进一步的讨论。
关键词：运筹学,线性规划,单纯性法
参考文献
[1]G.Dantzig, Linear Programming and Extensions Princeton Univer-sity Press, Princeton, NewJersey, 1963.
[2]S.Gass, Linear Programming, 4thed, McGraw-Hill, NewYork, 1975.
[3]L.S.Srinath, LinearProgramming:PrinciplesandApplications, Mac-millanPress, NewYork, 1983.
[4]胡清淮, 魏一鸣.线性规划及其应用[M].北京:科学出版社, 2004.
自主车辆路径规划算法研究 篇8
路径规划是自主车辆导航的最基本任务[1]。其目的是在特定环境中,按照一定的评价标准或者按照某一性能指标搜索出一条从起始状态到目标状态的最优或近似最优的路径。自主车辆的路径规划主要分为两大类型:环境信息已知全局路径规划和环境信息未知或部分未知的路径规划[2]。目前,对于路径规划应用较为典型方法有可视图法、拓扑法、人工势场法、蚁群算法等。但这些方法在大范围内求解最优路径时就会表现出缺乏灵活性和足够的鲁棒性的缺点。为此,学者们提出了更多新的解决方法,使自主车辆从单纯的路径规划逐渐发展为路径全局搜索、路径优化的问题。
本文在自主车辆无需经过特定点时,应用A*算法,自行建立地图信息,并对原始A*算法进行了技巧性改进,使车辆可以在有效时间内搜索到一条近似优化路径,且不会出现路径长度计算失效,以保证算法的灵活性和准确性;同时当车辆需要经过特定点时,应用Hopfield神经网络思想对算法进行改进,使车辆从起始点到终止点并再次返回起始点时,能够搜索到一条最优路径。最后通过仿真实验验证了算法的有效性。
1 无特定点的车辆路径规划
在常规行驶中,车辆遇到的实际情况会远远超过所预设的理想情况,例如,控制车辆从起始点到目标点不需要经过特定点时,采用全局搜索的方法找到一条最优(距离最短或消耗最小)路径。当车辆行驶在地图信息已知且无须经过特定点时,路径规划采用经典的全局搜索A*算法为最优。
1.1 A*算法改进
A*算法的最大特点是估价函数的建立。在经典的A*算法中,估价函数的表达式为:
式(1)中:f(n)是节点n从初始点到目标点的估计代价,称为估价函数;g(n)是起点到节点n的最短路径值;h(n)是从节点n到目标节点最短路径的估计代价,称为启发函数。
鉴于A*算法存在着随着搜索区间的增大,内部存储数据增加,最终导致路径搜索时间过长、实时性无法保证的问题[5,6],本文在传统A*算法估计函数建立的基础之上将估计函数改进。引入一个权值ω(n),其作用是:当车辆接近目标点时,降低启发函数的重要性,增加路径真实代价的相对重要性,即防止出现h(n)将远远大于g(n)的情况。
其表达式为:
式(2)中:ω(n)是节点n到目标节点启发函数引入的权值。
A*算法能否保证车辆找到一条优化路径,关键在于启发函数h(n)的选取。
1.2 启发函数h(n)选取改进
启发函数h(n)的选取,实际上就是距离的计算。通常在A*算法计算距离时,可以采用平方欧几里得距离(square Euclidean Distance)和欧几里得距离(Euclidean Distance)。
传统算法中,启发函数h(n)选取平方欧几里得距离,主要会出现以下三种明显错误:
(1)出现计算单位失效,路径长度计算错误;
(2)h(n)将远远大于g(n),并且会因为启发式函数评估值过高而停止计算;
(3)对于更长的距离,选取平方欧几里得距离,只会出现f(n)靠近g(n)这种极端情况,车辆会停止计算距离而提前结束路径点的搜索。
为了修正传统算法中存在的这种误差,本文采用欧几里克距离计算h(n),其表达式为:
式(3)中:d是启发系数;n.x和n.y是起始点的横坐标、纵坐标;g.x和g.y是下个目标节点的横坐标、纵坐标。
为了防止以上阐述几点错误的出现,权值ω(n)的选取不能太大,避免出现h(n)将远远大于g(n);也不能选取过小,忽略了h(n)的大小。所以本文中选取ω(n)值为0.8。.
1.3 A*算法流程图
算法在Matlab下主要包括四部分:(1)节点坐标的更新;(2)进入估计函数计算部分;(3)判断计算点是否为最佳节点;(4)如果不是最佳节点,放弃该点后继续寻找下个点。算法流程如图1所示。
2 特定点的车辆路径规划
当车辆从起始点到终止点要经过特定的点时,由于搜索区间增大、搜索点大量增加,A*算法这种经典的启发式搜索法就不再适用。而Hopfield神经网络具有分布式存储、存储与计算相结合的优点,能使搜索速度加快。
2.1 算法原理
Hopfield神经网络是1982年美国物理学家Hopfield首先提出来的。与之前存在的BP前行神经网络的特点不同,它采用反馈连接,考虑输出与输入在时间上传输延迟,所以它表示的是一个动态过程。反馈神经网络由于其输出端有反馈到其输入端,Hopfield网络在输入的激励下,会产生不断的状态变化。当有输入之后,可以求取出Hopfield的输出,这个输出反馈到输入从而产生新的输出,这个反馈过程一直进行下去。如果Hopfield网络是一个能收敛的稳定网络,则这个反馈与迭代的计算过程所产生的变化越来越小,一旦到达了稳定平衡状态,Hopfield网络就会输出一个稳定的恒值,可以求取出Hopfield的输出[3,4]。Hopfield网络一般分为离散型和连续型两种,本文采用的Hopfield网络为连续型网络,其结构如图2所示。
对网络第i个神经元,采用微分方程建立输入输出关系:
以及定义的李雅普诺夫函数:
由式(4)、式(5)可得:
式(6)中:ωij为神经元i和j的连接权值;ui为第i个神经元的输入;vi为第i个神经元的输出;Ii为第i个神经元的外加偏置电流;Ri为第i个神经元的电阻;Ci为第i个神经元的电容。
2.2 算法推导
Hopfield网络已经用于解决一些不同的组合优化问题,现已证明Hopfield网络是一种李雅普诺夫渐进稳定过程。Hopfield网络一般用能量函数来描述,能量函数的最低值表示最优解[7]。
对于车辆到达终点要经过n个目标点的路径规划问题,映射成为一个神经网络的动态过程,可以引入TSP的理念,采用换位矩阵构成一个n×n的矩阵,如表1所示。在该矩阵中各行各列只有一个元素为1,其余为0,采用Oxi表示神经元的输出,ixi表示为相应的输入。
神经网络的能量函数是与目标函数(最短路径)相对应的。同时,考虑到有效路径选取的实际意义,即就是在构成的换位矩阵中,每行、列都只能有一个1。因此,能量函数应该包含目标项(目标函数)和约束项(换位矩阵)两部分内容。
针对Hopfield神经网络方法在求解上存在局部极小、不稳定等问题,本文引用改进后的能量函数,由式(5)可得:
同理,由式(6)可以推导出,路径规划网络的动态方程为:
3 Matlab仿真及结果分析
文中选用的自主车辆为四轮农夫车,属于实验室专用车辆,它是一种场地特种车辆,行驶速度较低,适合校园及其它非结构化道路行驶。车辆的制动、加速踏板和转向走在驾驶舱呈开放状态,且车辆已经过了车体改装。下文以此车建立模型进行仿真实验来验证算法。
3.1 无特定点路径寻优仿真
假设车辆初始坐标(0,0),终止坐标为(0.9,0.9),初始速度为0 m/s,启发系数d=1.8,权值ω=0.8。在自行生成不规则地图的基础上,无特定点路径寻优仿真如图3所示。图3(a)为选取欧几里克距离(square Euclidean Distance)的实际仿真结果,图3(b)为选取平方欧几里得距离(square Euclidean Distance)的实际仿真结果。图中的“o”代表了搜索过程中输出的最佳节点。
仿真结果分析:两种距离下的算法都能达到搜索路径的目的。图3(a)输出的最佳节点较多,搜索结果要明显优于图3(b);同时由于选取Square Eucl-idean Distance所存在计算失衡问题,图3(b)中的路径距离计算结果也出现了明显错误。
3.2 特定点路径寻优仿真
选取6个坐标点代表实际中车辆要经过的特定点:D1(0.1,0.6),D2(0.2,0.3),D3(0.4,0.1),D4(0.5,0.5),D5(0.7,0.2),D6(0.8,0.4),能量函数初始值A=200,D=200,迭代次数num=20 000,采样时间间隔0.000 1。经过特定点路径寻优仿真如图4所示。图4(a)为优化前的仿真路径,图4(b)为采用神经网络优化后的仿真路径,图4(c)为能量函数变化曲线。
仿真结果分析:图4(a)中原始路径的长度Length＿init=2.361 4 m,而利用神经网络优化以后所得到的实际路径如图4(b)所示Length＿end=1.867 4 m,比优化以前路径长度明显缩短了21%。图4(c)中能量函数E在经过20 000次的迭代循环后,单调递减最终达到稳态,且E的最小点对应问题的最优解。
4 结论
(1)在无需经过特定点的路径规划中,全局路径搜索选取了较小的启发函数,扩展的节点虽然有所增加,搜索效率也相对降低,但从路径的准确性上得到了保证;在估价函数中增加权值,降低启发函数重要性的同时增加路径的真实性。
(2)在经过特定点的路径规划中,利用Hopfield神经网络的理念和能量函数,把车辆路径规划寻优问题的目标函数转换成网络的能量函数,把问题的变量对应于网络的状态,解决了车辆在行驶空间各站点的路径规划问题,使总距离达到最短,能量达到最小且稳定。
通过改进后算法的仿真实验,证明了算法的可行性和有效性,使车辆的路径寻优效果得到明显提高。
参考文献
[1]纪寿文,王荣本.国内外智能车辆研究进展.中国交通研究与探索(上册),第三届全国交通领域青年学者会议,1999
[2]王艳平.移动机器人路径规划方法研究.电脑与电信,2009;(1):66—68
[3]李国勇.神经模糊控制理论及应用.北京:电子工业出版社,2009
[4]张丽霞,赵又群.Hopfield神经网络算法求解路网最优路径.哈尔滨工业大学学报,2009;(40):222—224
[5]贾庆轩,陈钢,孙汉旭,等.基于A*算法的空间机械臂避障路径规划.机械工程学报,2010;46(13):109—115
[6] Chabini I,Lan S.Adaptations of the A*algorithm for the computa-tion of fastest paths in deterministic discrete-time dynamic networks.IEEE Transactions on Intelligent Transportation Systems,2002;3(1):60—74
基于A*的路径规划算法研究 篇9
路径规划是机器人系统领域中的一个重要分支, 也是机器人导航中最重要的任务之一。路径规划是指移动机器人根据环境信息搜索一条从起点到目标点的无碰路径, 该路径的优略直接影响机器人搜索的时间复杂度和空间复杂度, 所以求解一条最优或较优的路径是至关重要的, 评价路径的常用标准有工作代价、行走路线、行走时间等。目前求解路径规划的方法有很多种, 其中基于A*的路径规划[1]方法被广泛应用, 本文就基于A*的路径规划算法进行研究, 对各种算法进行讨论比较, 最后对该问题进行总结。
2 基于A*的路径规划方法
常见的经典路径规划方法有Dijkstra算法[2]、Floyd算法[3]及启发式搜索算法, 在启发式搜索算法中以启发信息为引导, 不仅可以提高搜索效率, 还可以减少问题的复杂性。A*算法在启发式搜索中应用比较广泛, 本部分以A*算法为基础, 总结几种基于A*算法的路径规划的方法。
2.1 A*搜索算法
A*算法是目前较为流行的路径规划算法之一。作为启发式搜索的一种, 同样需要选取估价函数, 估价函数的使用可以省略大量的无意义搜索, 提高搜索效率。在基于A*的路径规划中, 对位置的估价十分重要, 采用不同的估价就会有不同的效果, 在此每个位置的评估估价可以用如下的估价函数来表示:
其中f (n) 表示对到达目标节点的总代价的一种估计, 即算出的最优路径, g (n) 表示从初始节点到任意节点n的实际路径代价, h (n) 是从节点n到目标节点的最优路径的估计代价, 即按某一策论计算出的估计值, 从这个估价函数可以看出, 搜索的启发信息由h (n) 体现出来, 如果估价值h (n) 与实际值越接近, 说明估价函数取得越好。
2.2 单向搜索
在A*算法执行的过程中用到OPEN表 (用于存放搜索到的但非最小代价节点的集合) 和CLOSE表 (用于存放已经搜索过的代价最小节点的集合) , 假设起点和终点分别用V和S表示, Vi表示节点V到S间的任意一点, fi表示该节点的评估估价。其基本步骤如下所示:
(1) 将开始节点放到OPEN表中, 转到 (2) ;
(2) 从OPEN表中取出一个代价最小的节点, 并从OPEN表中删除该节点;若Vj是目标节点, 则转到 (5) ;若不是, 转到 (3) ;
(3) 计算Vk的估价值fk, 若Vk不在OPEN表中也不在CLOSE中, 将其插入OPEN表中;若Vk在OPEN表中, 与OPEN表中已有的该节点的对应节点Vk′的估价值fk′进行比较, 若Vk<Vk′, 更新OPEN表中Vk节点的估价值;若Vk在CLOSE中, 与CLOSE表中已有的该节点的对应节点记为Vk′的估价值fk′进行比较, 若Vk<Vk′, 更新CLOSE表中Vk节点的估价值, 并将此节点从CLOSE表移入OPEN表中;
(4) 将Vj节点插入到CLOSE表中, 转到 (2) ;
(5) 若终点S已在OPEN表中, 表明已找到最短路径, 并将S放入到CLOSE表中, 并从V开始顺序搜索CLOSE表, 直到S, 即为所要求的最短路径。
2.3 双向搜索
在障碍物少的情况下, 传统的A*算法虽能找到一条从起点到目标点的最短路径, 但搜索时会过多的扩展节点数量, 导致搜索效率不高, 且占用较大的内存资源, 另外有时在搜索过程中也会把最优路径弃掉。为了提高A*算法的使用效率, 提出双向A*搜索算法[4]。该方法不仅采用从起始节点向目标节点的正向搜索, 同时采用从目标节点向起始节点的逆向搜索, 当两个方向的搜索生成同一子结点时终止此搜索过程。
利用VC++6.0环境编写程序进行双向A*搜索算法与单向A*搜索算法比较, 在求解出的最短路径节点数相同的情况下, 双向A*搜索算法的扩展节点个数远远少于单向A*搜索算法, 提高了约50%的搜索空间, 双向A*搜索算法的运行时间也比单向A*搜索算法少得多, 确实提高了求解的效率。
2.4 二次搜索
由于在传统的A*算法中存在无法绕过未知障碍物及没有考虑机器人的宽度信息两个问题, 提出A*算法的二次搜索方法[5], 此方法首先根据已知环境信息规划出一条从起点到目标点的路径, 并让机器人按照该路径移动, 若在移动过程中遇过先前未知的障碍物, 则实时提取机器人所在位置的环境信息并反馈到机器人的控制系统以便确认障碍物在栅格中的位置, 之后更新环境信息, 将机器人所在位置作为新的起点, 重新利用A*搜索算法规划出当前位置到目标点之间的路径, 这条新的路径与之前路径合并成为最终的完整的从起点到目标点的规划路径。
该方法解决了机器人路径规划中的未知障碍物问题, 也拓宽了原算法的适用范围, 提高了机器人的智能水平和实时路径规划能力。但是如果机器人在遇到未知障碍物之前能对环境信息进行采样, 提早发现未知障碍物, 则能规划出全局上更优的路径。
3. 各算法的比较
A*算法可以利用空间的全局信息, 选择合适的估计函数, 调整搜索的方向, 减少搜索的节点个数, 找到较优的从起点到目标点得路径规划。与经典的Dijkstra算法和算法相比, 在路径相同的情况下, A*算法节省了大量的时间, 提高了求解的效率。
A*搜索算法与改进的双向A*搜索算法相比, 在求解出的最短路径节点数相同的情况下, 双向A*搜索算法的扩展节点个数和时间都远远少于单向A*搜索算法, 提高了求解的效率。但是在双向搜索中, 当前向搜索与后向搜索相遇时会终止搜索, 所以该算法搜索的结果有事未必是最短的。算法A*搜索算法与A*的二次搜索算法相比, 解决了A*搜索算法在搜索过程中不能处理未知障碍物问题, 拓宽了A*算法的适用范围。
4. 结论
本文就目前应用比较广泛的启发式搜索算法———A*搜索算法及其执行过程进行分析, 并对该算法的改进算法双向搜索和二次搜索算法进行分析研究, 分析其存在的优缺点。双向A*搜索算法提高了求解的效率, 但有时求解出的路径不是最优势的, 如果考虑前向 (或者后向) 搜索状态的当前结点已经在后向 (或者前向) 搜索状态的已搜索结点表, 仍继续搜索, 如果没有更优路径, 则选择原来路径, 这样能找到一条更优路径, 但会占用大量的时间, 故该问题有待进一步的研究。A*二次搜索算法增加了未知障碍物的情况, 拓宽了算法适应的范围, 如果机器人能在遇到未知障碍物之前尽早发现障碍物, 则能规划出全局上更优的路径。
参考文献
[1]张海涛, 程荫杭.基于A算法的全局路径搜索.微计算机信息.2007 (23) :238.240.
[2]桂莲.基于Dijkstra算法的最短路径的实现.青海大学学报 (自然科学版) 2007 (2) :98.102.
[3]王秀珍, 凡世宁.两种最短路径Dijkstra算法与Bellman.Ford算法的比较.黑龙江农垦师专学报.2002 (2) :75—77.
[4]常青, 杨东凯, 寇艳红, 张其善.车辆导航定位方法及应用.北京:机械工业出版社, 2004:32.40.
规划算法 篇10
动态规划策略是一种将复杂的问题分解为更小的、相似的子问题, 并存储子问题的解而避免计算重复的子问题, 以解决最优化问题的算法策略。
动态规划主要应用于最优化问题, 这类问题会有多种可能的解, 每个解都有一个值, 而动态规划找出其中最优解。在求解的过程中, 动态规划也是通过求解局部子问题的解达到全局最优解, 允许这些子问题不独立, 也允许其通过自身子问题的解作出选择, 对每一个子问题只解一次, 而且把结果保存起来, 避免重复计算来提高效率。即动态规划算法的有效性依赖于问题本身具有的两个重要性质:最优子结构性质和子问题重叠性质。
动态规划策略解决问题的基本步骤:
1) 找出最优解的性质, 并刻划其结构特征;
2) 递归地定义最优值;
3) 以自底向上的方式计算出最优值;
4) 根据计算最优值时得到的信息, 构造最优解。
2. 动态规划方法解决英文文档排版问题
2.1 英文文档排版问题
给定有n个英文单词组成的一篇文章, 每个单词的长度 (即字符个数) 分别为l1, l2, ……ln。现要将该段文章“漂亮”地排版出来。排版规则:排版时每行最多打印M个字符;每一行行首不得留空格;单词与单词之间至少有一个空格;单词不允许被打破。
解决方法:如果在某一行中安排单词i到单词j, 则按排版规则, 这一行中恰好打印个字符 (包括这j-i+1个单词间的j-i个空格) 。多余的空格数为。除文章最后一行外, 希望每行多余的空格数尽可能少。本算法中, 以各行 (最后一行除外) 的多余空格数的立方和达到最小作为“漂亮”的标准。
2.2 最优解的结构
记s (i) 为由单词i到单词n所组成的文章的各行 (除最后一行) 的多余空格数的立方和, b (i) 记载单词的前进位置。例如对由单词3到单词n所组成文章的排版, 若b (3) =10, 单词3到单词10构成一行, 单词11到单词b (11) 构成一行……。
s (i) 的计算方式如下:假定单词i最多可与单词j构成一行 (j>=i) , t为i到j间的任意整数, 如果从t位置分割, 即单词i到单词t作文一行, 而从单词t+1到单词n构成文章的剩余行。
可以证明, 问题的关键在于:如果计算出的s (i) 是单词i到单词n漂亮排版的各行 (除最后一行) 的多余空格数的立方和, 则s (t+1) 是单词t+1到单词n漂亮排版的立方和。因而文章排版问题的最优解包含着其自身子问题的最优解。这种最优子结构性质是问题可以用动态规划方法来求解的最重要特征。
2.3 利用递归来定义最优值
若计算s (i) (1<=i<=n) 的最小值为c[i], 则原问题的最优值为c[1]。显然, 如果单词Fi (1<=Fi<=n) 到单词n可以构成一行, 而单词Fi-1到单词n则超过一行, 显然c[i]=0 (Fi<=i<=n) ;对于1<=i<=Fi-1, 若单词i最多可与单词j构成一行 (j>=i) , t为i到j的任意整数, 如果从t位置分割, 即单词i到单词t作文一行, 而从单词t+1到单词n构成文章的剩余行。c (i) 为所有t取值的的立方和最小者。递归式如下:
另外, 用p[i]记载每次c[i]断开的位置, 求出c[1]后, 从p[1]向后退, 就可以知道漂亮排版中每行单词的开始位置和结束位置, 从而能够实现漂亮的排版。
2.4 计算最优值
如果直接用c[i]的计算公式, 进行递归计算需要耗费指数计算时间。然而不同的子问题的个数只是n的线性次。用动态规划方法求解, 可按照其递归式以自底向上的方式来计算。在计算过程中, 保存已解决的子问题解。因而每个子问题只计算一次, 在后面需要时只要查找一下, 通过这种方法避免了大量的重复计算, 因而得到多项式时间的算法。下面给出计算c[i]的动态规划算法:
经过分析可以得出, 算法的空间复杂度为用O (n) , 时间复杂度O (n2) 。
2.5 构造最优解
通过上面算法, c[1]保存了单词1到单词n所组成的文章的各行 (除最后一行) 的多余空格数的最小立方和。还有一个问题, 这些单词怎样分行, 构成一片漂亮文章呢?p[i]中已经保存了构造最优解所需要的信息, 从p[1]出发, 单词1到单词p[1]构成一行, 单词p[1]+1到单词p[p[1]+1]构成一行……即得出问题的一个最优解。算法描述如下:
2.6 进一步讨论
如果希望排版的效果不仅是各行 (最后一行除外) 的多余空格数的立方和达到最小, 还能够实现如同中文排版的两端对齐效果。只需要增设一个Space数组, Space[i]保存的是在漂亮排版下, 单词i所在行的多余空格数。这样, 在漂亮排版时, 只要将每行的多余空格均匀分配在该行的若干单词间。
3. 结束语
算法在c语言环境下得到验证, 运行结果证明了算法设计是可行的, 正确的获得了漂亮的排版效果。
动态规划方法中, 每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后, 才能做出选择, 所以动态规划算法通常是以自底向上的方式解各子问题的解, 进而求出原问题的解。实际求解过程中, 子问题会有大量的重复, 而动态规划就是对重复出现的子问题, 只在第一次遇到时进行求解, 并把解保存起来, 让以后再遇到时直接引用, 不必重新求解。
摘要：动态规划策略是求解最优化问题的一种方法, 该文主要研究其求解问题的基本思想及具体步骤, 详细分析其用于英文文档的排版问题上的算法设计, 并给出其算法实现。
关键词：动态规划,漂亮排版,最优子结构
参考文献
[1] (美) Cormen T.H..算法导论[M].北京:机械工业出版社, 2006.
[2]王晓东.计算机算法设计与分析[M].北京:清华大学出版社, 2010.
[3] (沙特) M.H.Alsuwaiyel.算法设计技巧与分析[M].北京:电子工业出版社, 2004.
[4] (美) Kleinberg J..算法设计[M].北京:清华大学出版社, 2007.
规划算法 篇11
关键词：木块移动,状态,动作,偏序规划
1 问题的描述
人工智能领域规划问题的求解就是要寻找一个动作序列, 可以使问题从起始状态到达目标状态。“木块移动”问题就是其中的一个经典问题, 问题描述如下:
如图1所示, 在台子 (TABLE) 上放着A, B, C三个木块, 初始状态下A在TABLE上, C在A上, B在TABLE上;目标状态下, C在TABLE上, B在C上, A在B上。要求机器人在一次只能移动一个木块的前提下完成从初始状态到目标状态问题的求解, 也就是要找到一个动作序列, 使TABLE、A、B、C四者的状态从初始状态转化为目标状态[1]。
2 规划问题求解算法的比较
在“木块移动”此类问题的求解过程中, 找到达到一定目标的动作序列的过程称之为规划。可以将规划问题转换为“问题求解”问题:已知初始状态, 在可以选择的动作序列树上进行搜索去发现一条较短的路径来解决问题, 但是这种解决方式不是最好的方法。逻辑为规划问题的求解提供了一个很好的描述状态集合的方法, 这样就可以使用状态相关集合的逻辑描述明确地表达规划问题, 使用一阶逻辑机制来进行规划处理, 这是一种经典的规划方法——情景演算。然而在情景演算中将特定的规划问题转换为定理证明问题效率很低。
在实际应用中, 规划问题被限定在一定范围内, 如子问题独立性假设即问题是可以分解的, 因此可以利用规划问题的特殊性来寻求一个更为专用的解决方法——偏序规划算法。在这种解决方法中寻找状态描述和动作描述的联合, 以任意的顺序向规划中添加顺序, 并假设子问题独立性, 同时限制描述目标、动作和状态的表示方法——STRIPS表示法。
3 STRIPS表示法和偏序规划
在STRIPS表示法中, 状态采用常数文字的合取;目标采用文字的合取;动作是由前提和效果来表示, 其中前提指能够采用这个动作的条件, 效果指动作发生后状态的变化。
在“木块移动”问题中, 对象有木块A、B、C、TABLE, STRIPS表示:
初始状态:on (A, T) ∧on (C, A) ∧on (B, T) ∧clear (C) ∧clear (B)
目标状态:on (A, B) ∧on (B, C) ∧on (C, T) ∧clear (A)
动作:
Move (b, x, y) :将木块b从x上移到y上。
前提:on (b, x) , clear (b) , clear (y) , block (y)
效果:on (b, y) , clear (x) , -on (b, x) , -clear (y)
Move T (b, x) :将木块b从x上移到TABLE上
前提:on (b, x) , clear (b)
效果:on (b, Table) , clear (x) , -on (b, x)
其中谓词on (x, y) 表示对象x在对象y上, 谓词clear (x) 表示对象x上没有其他对象, 谓词block (y) 表示y不是TABLE对象。
规划算法求解过程中就是添加动作的过程。偏序规划算法从目标状态开始采用逆向搜索方式进行动作的添加;添加的动作所产生的效果是可以达到部分目标或者可以达到其它动作的前提条件, 同时判断选取的动作是否造成冲突, 并通过升级或降级的方式来解决冲突, 若冲突无法解决则选择其他动作。由于在动作选择过程中已经加入了解决了冲突保持了一致性, 因此判断算法结束的条件为目标状态是否全部满足。具体算法描述如下:
首先构造初始规划, 初始规划包含两个初始动作, 分别称为Start和Finish动作。其中, 初始状态是Start动作的效果, 目标状态是Finish动作的前提条件, 将目标状态作为所有的开放前提。然后选择一个尚未满足的前提条件C作为子目标, 在规划中选择一个Si或找到一个效果中包含条件C的新步骤Si, 如果不存在这样的步骤Si, 则算法失败;为了进行扩展和保持一致性采取以下的方式:将因果链和序约束添加到规划中, 如果动作Si不在规划中, 则将Si添加到规划中, 同时添加序约束和。在这个过程中, 添加一个动作S可能对原有的因果链造成威胁, 因此需要排除威胁, 而排除威胁的方法有两种提升动作S或降低动作S, 即通过添加序约束或添加序约束来解决, 如果两种方法都导致规划失败, 则选择其他的动作C。循环上述过程直到所有的开放前提都满足。
4 问题的偏序规划算法实现
实现此类算法首先需要解决状态数据的存储然后是规划动作的存储, 本文中采用单链表结构存储各种数据。从上节分析中可以看到状态数据、动作中的前提、效果数据均采用的谓词表示, 因此这类数据的存储可以统一处处理为基本谓词的存储。如主要谓词结构On数据结构设计如下:
该结构中包含m_x和m_y两个数据域, 分别存放谓词中的两个变量, 程序中使用On作为此结构的数据类型。
规划动作结构定义中包含m_operator、m_x、m_y、m_z四个数据域, 存放步骤集合中的每一个动作, 如:Move (x, y, z) 或Move T (x, y) , 其中m_operator存放动作名称”Move”或”Move T”, m_x、m_y、m_z存放动作中的变量, 如果步骤为”Move T”则m_z中存放非法变量’*’, 程序中使用Result作为此结构的数据类型其定义如下:
在算法实现过程中使用数据实体On Sorce On, Goal On;分别描述初始规划中Start中的的On谓词集合以及Finish中On谓词集合;使用Clear Sorce Clear, Goal Clear;分别描述初始规划中Start中的的Clear谓词集合以及Finish中Clear谓词集合;使用Result result;描述规划中的动作集合。
在规划算法中主要选择动作过程的实现, 根据上节对于算法的描述, 使用Choose Operator函数实现选择动作操作, 算法部分主要代码实现如下:
使用Visual C++6.0实现, 对于本文第一节描述的初始状态和目标状态, 程序运行时, 分别输入初始状态下各个谓词实体中的前提条件和目标状态下各个谓词实体中的子目标, 通过计算规划中的动作实现结果如下图所示, 此结果和预期结果一致:
在实验中, 验证各种测试数据的输入, 从输出结果看不仅给出了规划中所需的动作, 而且还按照移动顺序给出了规划动作的输出, 测试结果与预期结果一致。但是在数据输入时需要明确写出初始与目标之间显著的不同, 若给出的目标谓词过少, 体现不了前后的变化, 会导致程序无结果输出, 如初始化谓词On集合有On (c, b) 、On (b, a) 、On (a, T) , 初始化谓词Clear集合有Clear (c) 、Clear (T) ;目标谓词On集合只给出On (c, b) , 则程序无结果, 此类情况需要改进输入数据, 增加On (b, T) 谓词, 则可以给出正确的输出结果, 实现了“木块移动”问题的求解。
5 结论
本文以“木块移动”问题的解决需求为基础介绍了人工智能中规划问题的求解, 研究了该问题的偏序规划问题的求解, 分析并实现了规划求解过程中的状态和动作数据结构的存储, 同时实现了规划动作选择算法, 通过数据验证了算法的实现, 达到了预期效果。
参考文献