毕业论文答辩
机器人路径规划蚁群算法
姓名:陈俊吉
指导老师:朱庆保
研究内容
蚂蚁算法的基本原理
各类蚁群算法的实施与比较
机器人路径规划蚁群算法及其编程实现和仿真实验
研究目标及方法
目标:机器人在有障碍物的工作环境中工作时,通过两组蚂蚁相向搜索,优化寻找出一条从给定起始点到终止点的较优的运动路径,使机器人在运动过程中能安全,无碰撞地绕过所有的障碍物,且所走路径最短.
方法:用两组蚂蚁分别以机器人出发点和目标点为出发点,按照一定的概率搜索算法相向搜索.本课题要研究这一概率搜索算法及其编程实现,并用C语言给出仿真结果.
蚂蚁算法的基本原理
生物学的研究表明:虽然单个蚂蚁的能力非常有限,但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力.这种能力是靠其在所经过的路径上留下的一种挥发性分泌物,即信息素(pheromone)来实现的.蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的信息素选择其要走的路径,其选择一条路径的概率与该路经上分泌物的强度成正比.因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可能性就越大.蚂蚁的个体之间通过这种信息的交流寻求通向食物的最短路径.
各类蚁群算法的实施与比较
TSP问题
即旅行商问题,有n个城市,为旅行商选择一条经过各城市一次且仅一次的回路,使其路径长度最短.
AS算法与ACS改进算法
体现在后续算法中,这里略
算法分析

步骤1:在屏幕上画一个10*10的栅格,格子的号码从1到100.栅格障碍物的号码随机生成(设有20个障碍物),并按照生成的号码在图中用阴影表示.

步骤2:设定起点和终点的位置:begin=5,end=99.因为障碍物是随机生成的,所以设定的起点和终点有可能与障碍物的号码冲突.为了避免出现这样的情况,需用另外的函数来检测,如果设定的起点或者终点恰好就是随机生成的障碍物时,就要再重新设定起点和终点的方格号码.为了便于后续距离的计算,将终点end转换为横纵坐标:横坐标endx=(end-1)/Y+1;纵坐标endy=(end-1)%Y+1.

算法分析

步骤3:初始化.将每两个方格之间的信息素初始化为一个很小的常数值:hormone[i][j]=hormone[j][i]=0.5;起点和终点处均放置一定数量的蚂蚁(本程序中分别放两只),并将它们固定地分配到起点和终点地四周(一个方格放一只).对于每一只蚂蚁,将它们所在的方格号码加到禁忌表中.
算法分析

步骤 4:下一步要走的方格的选择.每只蚂蚁在自己领接的(8个)非障碍物的格子中(c[i][k]!=0)选择下一步要走的方格.同样运用ACS算法中选择结点的方法:
算法分析

q0也是初始设定的参数,temp1是一个0到1之间的随机数.如果temp1,按照最大信息素选择j,否则计算转移概率,按赌轮盘规则选择j,同时将j加入到禁忌表中.
f2是当前点转移到方格j的启发函数.如果是起点的蚂蚁,它的启发函数就是它领接的各点到终点的距离的倒数,f2=1/dij.终点的蚂蚁就恰好相反.
设x,y分别表示将要走的点的横纵坐标,距离
算法分析

步骤5:信息素局部更新.每只蚂蚁走完一步后,用下式更新该边上的信息素.

lk是蚂蚁k从起点到当前方格所走过的路径长度.
算法分析

下一页