混合astar算法

龙源期刊网

基于遗传算法的混合花粉算法

作者：吴文斌 刘志锋 魏振华

来源：《电脑知识与技术》2017年第30期

摘要：花粉算法具有所用参数少，易调节，搜索路径优等特点，已运用于很多工程优化问题。但是存在易过早收敛、收敛速度慢和易陷入局部最优等不足，为了解决这些不足，对花粉算法做一些改进。在算法初期引入混沌序列做初始化，并在较优位置引入遗传算法的改进交叉和变异策略，提出一种基于遗传算法的混合花粉算法（Hybrid flower pollen algorithm Based on

Genetic Algorithm）。对HGFPA 算法与FPA算法通过优化问题中4个典型复杂测试函数进行仿真实验对比，结果表明HGFPA 算法的收敛速度与精度均优于 FPA 算法。

关键词：混沌理论；遗传算法；混合花粉算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2017）30-0173-03

Hybrid Flower Pollen Algorithm Based on Genetic Algorithm

WU Wen-bin， LIU Zhi-feng， WEI Zhen-hua

（Information Engineering Institute， East China University Of Technology， Nanchang

330013， China）

Abstract： The pollen algorithm has many characteristics，such as less parameters、easy

adjustment and excellent search path，and has been applied to many engineering optimization

AStar算法总结与实现（附Demo）

关于A Star Algorithm

A star算法最早可追溯到1968年，在，是把启发式⽅法（heuristic approaches）如BFS，和常规⽅法如Dijsktra算法结合在⼀起的算法。有点不同的是，类似BFS的启发式⽅法经

常给出⼀个近似解⽽不是保证最佳解。然⽽，尽管A star基于⽆法保证最佳解的启发式⽅法，A star却能保证找到⼀条最短路径。

公式表⽰为：f(n)=g(n)+h(n)

f(n)是节点n从初始点到⽬标点的估价函数

g(n)是在状态空间中从初始节点到n节点的实际代价

h(n)是从n到⽬标节点最佳路径的估计代价

观察A*寻路算法的运⾏轨迹

假设起点为A（浅蓝⾊的个字） 终点为B（深蓝⾊的格⼦）

红⾊代表该格⼦为障碍物

地图为20x20的格⼦

显⽰FGH值的格⼦代表经过A*算法搜索并⽣成路径的格⼦

有透明度变化的格⼦代表该格⼦有被搜索。

绿⾊格⼦代表的是搜索完成后A*得到的最优的路径

A直接抵达B的情况下

A越过直线障碍到达B

A越过U型障碍到达B

B为障碍物所包围着，A到达不了B的情况下

总结与思考

由4组图可以得到

1.A*的消耗是⼀个及其不稳定的过程，消耗的最⼩值不低于直线路径上的消耗，消耗的最⼤值不⾼于遍历整张地图的消耗。

2.A*的消耗主要在搜索的搜索格⼦，以及对其FGH的操作上。

3.由1，2可以得出，在对运⾏速率和效率有要求的场景下，A*可能不是⼀个⽐较好选择。

算法步骤

横向纵向的格⼦的单位消耗为10，对⾓单位消耗为14。

定义⼀个OpenList，⽤于存储和搜索当前最⼩值的格⼦。

定义⼀个CloseList，⽤于标记已经处理过的格⼦，以防⽌重复搜索。

开始搜索寻路

1.将起点加⼊OpenList

2.从OpenList中弹出F值最⼩的点作为当前点

3.获取当前点九空格（除去⾃⼰）内所有的⾮障碍且不在CloseList内的邻居点

4.遍历上⼀步骤得到的邻居点的集合，每个邻居点执⾏以下逻辑

使⽤AStar算法实现⾃动寻路详解

@⽬录

前些⽇⼦我有兄弟给我打电话，问我会不会⼈⼯智能，来实现⼀个机器⼈在仓库⾃动寻路的功能。因为没有接触过这样的场景，

但是⾃⼰⼜⽐较对此兴趣，所以就看了⼀些⾃动寻路的算法，⽐如：基于⼆叉树的深度优先遍历、D Star、A Star算法，其中我

感觉A Star算法最好。下⾯我给⼤家介绍⼀下，⾸次实现的语⾔是Java，但是Java不太直观，⼜不想使⽤Java的图形界⾯，所以

就使⽤JS+HTML来实现的，⾸先展⽰⼀下效果图。效果图如下：

1、什么是A Start算法

A*搜索算法是求出在⼀个⼆维平⾯中从起点到终点最低运算代价的算法，它可以算出A点到B点的最短距离，也就是最优路径。常见的应有

主要是在游戏中，⼈物的⾃动寻路；机器⼈探路；交通路线导航等。

2、A Star算法的原理和流程

2.1 前提

在讲述A Star算法之前，需要声明下列这些属性：

（1）从起点开始扩散的节点；

（2）最短距离计算公式：F = G + H；

（3）欧⼏⾥得距离计算公式：p = $\sqrt (x_2 - x_1)^2+(y_2 - y_1)^2$（其实就是勾股定理）；

（4）OPENLIST 和 CLOSELIST；

上⾯的属性和公式不懂没关系，下⾯我会对他们⼀⼀进⾏详细介绍。⾮常简单！

2.1.1 从起点开始扩散的节点

我们在HTML页⾯上使⽤横和 竖画出来的格⼦。所谓扩散就是以 起点 为基点向上、下、左、右四个放向进⾏扩散，这些扩展的节点就是可

以⾛的“路”。如下图所⽰黄⾊的⽅格就是扩散的点：

PS:A Star有四个⽅向和⼋个⽅向的扩散。扩展四个⽅向的节点就是⽬前我们所说的；⼋个⽅向是还包含了，上左、上右、下左、下右四个

⽅向的节点。我们通篇使⽤的是四个⽅向的扩展。

2.1.2 最短距离计算公式：F = G + H如何在扩散的节点中找到最优也就是最短的⼀条路呢？就需要⽤到这个公式：F=G+H。那么这个公式⾥⾯的属性都代表什么意识呢？下⾯我

混合高斯模型算法原理

混合高斯模型是一种经典的背景建模算法，用于背景相对稳定情况下的运动目标检测。它由单高斯模型发展而来，对于多模态的背景有一定的鲁棒性，如：树叶晃动、水纹波动等。在介绍混合高斯模型前，首先介绍单高斯模型。

1. 单高斯背景模型：

单高斯模型将图像中每一个像素点的颜色值看成是一个随机过程，并假设该点的像素值出现的概率服从高斯分布。该算法的基本原理就是对每一个像素位置建立一个高斯模型，模型中保存该处像素的均值和方差。如，可设),(yx处像素的均值为),(yxu，方差为),(2yx，标准差为),(yx。由于随着视频图像序列的输入，模型参数不断更新，所以不同时刻模型参数有不同的值，故可将模型参数表示为三个变量tyx,,的函数：均值),,(tyxu、方差),,(2tyx、标准差),,(tyx。用单高斯模型进行运动检测的基本过程包括：模型的初始化、更新参数并检测两个步骤。

1）模型初始化

模型的初始化即对每个像素位置上对应的高斯模型参数进行初始化，初始化采用如下公式完成：

initstdyxinitstdyxyxIyxu_)0,,(_)0,,()0,,()0,,(22 （1）

其中，)0,,(yxI表示视频图像序列中的第一张图像),(yx位置处的像素值，initstd_为一个自己设的常数，如可设20_initstd。

2）更新参数并检测

每读入一张新的图片，判断新图片中对应点像素是否在高斯模型描述的范围中，如是，则判断该点处为背景，否则，判断该点处为前景。假设前景检测的结果图为output，其中在t时刻),(yx位置处的像素值表示为),,(tyxoutput，),,(tyxoutput的计算公式如下：

otherwisetyxtyxutyxItyxoutput,1)1,,()1,,(),,(,0),,( （2）