人工智能算法分析论文

关键词： 算法

人工智能算法分析论文（精选6篇）

篇1：人工智能算法分析论文

5-1 简述机器学习十大算法的每个算法的核心思想、工作原理、适用 情况及优缺点等。1）C4.5 算法：

ID3 算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。ID3 算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。C4.5 算法核心思想是ID3 算法，是ID3 算法的改进，改进方面有： 1）用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2）在树构造过程中进行剪枝 3）能处理非离散的数据 4）能处理不完整的数据

C4.5 算法优点：产生的分类规则易于理解，准确率较高。缺点：

1)在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。2)C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。2）K means 算法：

是一个简单的聚类算法，把n 的对象根据他们的属性分为k 个分割，k < n。算法的核心就是要优化失真函数J,使其收敛到局部最小值但不是全局最小值。

其中N 为样本数，K 是簇数，rnk b 表示n 属于第k 个簇，uk 是第k 个中心点的值。然后求出最优的uk

优点：算法速度很快

缺点是，分组的数目k 是一个输入参数，不合适的k 可能返回较差的结果。

3）朴素贝叶斯算法：

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。算法的基础是概率问题，分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。朴素贝叶斯假设是约束 性很强的假设，假设特征条件独立，但朴素贝叶斯算法简单，快速，具有较小的出错率。在朴素贝叶斯的应用中，主要研究了电子邮件过滤以及文本分类研究。

4)K 最近邻分类算法（KNN）

分类思想比较简单，从训练样本中找出K个与其最相近的样本，然后看这k个样本中哪个类别的样本多，则待判定的值（或说抽样）就属于这个类别。缺点：

1）K 值需要预先设定，而不能自适应

2）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K 个邻居中大容量类的样本占多数。

该算法适用于对样本容量比较大的类域进行自动分类。

5)EM 最大期望算法

EM 算法是基于模型的聚类方法，是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。E步估计隐含变量，M步估计其他参数，交替将极值推向最大。EM 算法比K-means 算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，但比K-means 算法计算结果稳定、准确。EM 经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。

6）PageRank 算法

是google 的页面排序算法，是基于从许多优质的网页链接过来的网页，必定还是优质网页的回归关系，来判定所有网页的重要性。（也就是说，一个人有着越多牛X 朋友的人，他是牛X 的概率就越大。）优点：完全独立于查询，只依赖于网页链接结构，可以离线计算。缺点：1）PageRank 算法忽略了网页搜索的时效性。

2）旧网页排序很高，存在时间长，积累了大量的in-links，拥有最新资讯的新网页排名却很低，因为它们几乎没有in-links。

7)AdaBoost Adaboost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。整个过程如下所示：

1.先通过对N 个训练样本的学习得到第一个弱分类器；

2.将分错的样本和其他的新数据一起构成一个新的N 个的训练样本，通过对这个样本的学习得到第二个弱分类器； 3.将和都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器； 4.如此反复，最终得到经过提升的强分类器。

目前AdaBoost 算法广泛的应用于人脸检测、目标识别等领域。

8）Apriori 算法

Apriori 算法是一种挖掘关联规则的算法，用于挖掘其内含的、未知的却又实际存在的数据关系，其核心是基于两阶段频集思想的递推算法。Apriori 算法分为两个阶段：1）寻找频繁项集

2）由频繁项集找关联规则

算法缺点：

1）在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；

2）每次计算项集的支持度时，都对数据库中的全部记录进行了一遍扫描比较，需要很大的I/O 负载。9）SVM 支持向量机

支持向量机是一种基于分类边界的方法。其基本原理是（以二维数据为例）：如果训练数据分布在二维平面上的点，它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是，通过训练，找到这些分类之间的边界（直线的――称为线性划分，曲线的――称

为非线性划分）。对于多维数据（如N 维），可以将它们视为N 维空间中的点，而分类边界就是N 维空间中的面，称为超面（超面比N维空间少一维）。线性分类器使用超平面类型的边界，非线性分类器使用超曲面。

支持向量机的原理是将低维空间的点映射到高维空间，使它们成为线性可分，再使用线性划分的原理来判断分类边界。在高维空间中是一种线性划分，而在原有的数据空间中，是一种非线性划分。SVM 在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。10）CART 分类与回归树

是一种决策树分类方法，采用基于最小距离的基尼指数估计函数，用来决定由该子数据集生成的决策树的拓展形。如果目标变量是标称的，称为分类树；如果目标变量是连续的，称为回归树。分类树是使用树结构算法将数据分成离散类的方法。优点

1）非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树。2）在面对诸如存在缺失值、变量数多等问题时CART 显得非常稳健。

篇2：人工智能算法分析论文

文章编号:1008-0570(2006)11-2-0244-03

中文核心期刊《微计算机信息》(嵌入式与SOC)2006年第22卷第11-2期

智能机器人路径规划及算法研究

ResearchonPathPlanningandAlgorithmsforIntelligentRobots

(西南科技大学)宋晖张华高小明

SONGHUIZHANGHUAGAOXIAOMING

摘要:路径规划技术是机器人控制技术研究中的一个重要问题,目前的研究主要分为全局规划方法和局部规划方法两大类。在

对一些较有代表性的研究思想及其相关算法分析的基础上,比较各种方法的优缺点,提出了机器人路径规划今后的研究重点。关键词:智能机器人;全局规划;局部规划;优化算法 中图分类号:TP242.6 文献标识码:A

技

1引言 术

自50年代世界上第一台机器人装置诞生以来, 创 机器人的发展经历了一个从低级到高级的发展过程。

第一代示教再现型机器人,可以根据人示教的结果再 新 现出动作,它对于外界的环境没有感知。在20世纪70

年代后期人们开始研究第二代机器人:带感觉的机器 人,这种机器人是类似人某种感觉的功能,如力觉、触 觉、滑觉、视觉、听觉。第三代机器人是智能机器人阶 段,机器人通过各种传感器获取环境信息,利用人工 智能进行识别、理解、推理并做出判断和决策来完成 一定的任务。这就要求智能机器人除了具有感知环境 和简单的适应环境能力外,还具有较强的识别理解功 能和决策规划功能。（智械科技）Abstract:Pathplanningtechnologyisoneoftheimportantprobleminintelligentrobot.Atpresent,thetworesearchways:oneis globalplanningandtheotherislocalplanning.Onthebasisoftheanalysisofsometypicalideas,methodsandrelatedalgorithms ofpathplanningforintelligentrobot,thispaperproposesthefutureresearchemphasisofrobotpathplanning.Keywords:intelligentrobot,globalplanning,localplanning,optimizationalgorithms

①复杂性:在复杂环境中,机器人路径规划非常 复杂,且需要很大的计算量。

②随机性:复杂环境的变化往往存在很多随机性 和不确定因素。

③多约束:机器人的形状、速度和加速度等对机 器人的运动存在约束。

3全局路径规划

全局规划方法主包括构型空间法、拓扑法、栅格 解耦法、自由空间法、神经网络法等。

3.1构型空间法

构型空间法的基本思想是将机器人缩小为一个 点,根据机器人形状和尺寸将障碍物进行拓展。其中 研究较成熟的有:可视图法和优化算法。

3.1.1可视图法

可视图法中的路径图由捕捉到的存在于机器人 一维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应, 这样路径规划问题就演变为在这些点间搜索路径的 问题。要求机器人和障碍物各顶点之间、目标点和障碍 物各顶点之间以及各障碍物顶点与顶点之间的连线均 不能穿越障碍物,即直线是“可视的”,然后采用某种方 法搜索从起始点到目标点的最优路径,搜索最优路径 的问题就转化为从起始点到目标点经过这些可视直线 的最短距离问题。该法能够求得最短路径,但假设忽略 智能机器人的尺寸大小,使得机器人通过障碍物顶点 时离障碍物太近甚至接触,并且搜索时间长。

3.1.2优化算法 此法可删除一些不必要的连线以简化可视图、缩 短搜索时间,能够求得最短路径。但假设机器人的尺

《 现场总线技术应用200例》 2智能机器人的路径规划技术分类

智能机器人路径规划是指在有障碍物的工作环 境中,如何寻找一条从给定起点到终点适当的运动路 径,使机器人在运动过程中能安全、无碰地绕过所有 障碍物。机器人路径规划问题可以建模为一个有约束 的优化问题,都要完成路径规划、定位和避障等任务。根据机器人对环境信息掌握的程度不同将智能机器 人路径规划分为基于模型的全局路径规划和基于传 感器的局部路径规划。前者是指作业环境的全部信息 已知,又称静态或离线路径规划;后者是指作业环境 信息全部未知或部分未知,又称动态或在线路径规 划。智能机器人路径规划存在以下特点: 宋晖:讲师硕士

基金项目:国家自然科学基金(60404014);

西南科技大学青年基金资助项目(ZK053033)

-244-360元/年邮局订阅号:82-946 您的论文得到两院院士关注 机器人技术

在满足精度要求的情况下,用神经网络来表示环境则 可以取得较好的效果。神经网络在全局路径规划的应 用,将障碍约束转化为一个惩罚函数,从而使一个约 束优化问题转化为一个无约束最优化问题,然后以神 经网络来描述碰撞惩罚函数,进行全局路径规划。

虽然神经网络在路径规划中有学习能力强等优 点,但整体应用却不是非常成功,主要原因是智能机 器人所遇到的环境是千变万化的、随机的,并且很难 以数学的公式来描述。寸大小忽略不计,会使机器人通过障碍物顶点时离障 碍物太近甚至接触,并且搜索时间长。另外的缺点就 是此法缺乏灵活性,即一旦机器人的起点和目标点发 生改变,就要重新构造可视图,比较麻烦。这类算法包 括Dijkstra算法,A*算法等。（智械科技）

3.2拓扑法

拓扑法将规划空间分割成具有拓扑特征子空间, 根据彼此连通性建立拓扑网络,在网络上寻找起始点 到目标点的拓扑路径,最终由拓扑路径求出几何路 径。拓扑法基本思想是降维法,即将在高维几何空间 中求路径的问题转化为低维拓扑空间中判别连通性 的问题。优点在于利用拓扑特征大大缩小了搜索空 间。算法复杂性仅依赖于障碍物数目,理论上是完备 的。而且拓扑法通常不需要机器人的准确位置,对于 位置误差也就有了更好的鲁棒性;缺点是建立拓扑网 络的过程相当复杂,特别在增加障碍物时如何有效地 修正已经存在的拓扑网是有待解决的问题。

3.3栅格解耦法

栅格解耦法是目前研究最广泛的路径规划方法。该方法将机器人的工作空间解耦为多个简单的区域, 一般称为栅格。由这些栅格构成了一个连通图,在这个 连通图上搜索一条从起始栅格到目标栅格的路径,这 条路径是用栅格的序号来表示的。整个图被分割成多 个较大的矩形,每个矩形之间都是连续的。如果大矩形 内部包含障碍物或者边界,则又被分割成4个小矩形, 对所有稍大的栅格都进行这种划分,然后在划分的最 后界限内形成的小栅格间重复执行程序,直到达到解 的界限为止。该法以栅格为单位记录环境信息,环境 被量化成具有一定分辨率的栅格,栅格的大小直接影 响着环境信息存储量的大小和规划时间的长短,栅格 划分大了,环境信息存储量小,规划时间短,分辨率下 降;栅格划分小了,环境分辨率高。

3.4自由空间法

自由空间法采用预先定义的如广义锥形和凸多 边形等基本形状构造自由空间,并将自由空间表示为 连通图,通过搜索连通图来进行路径规划。自由空间 的构造方法是:从障碍物的一个顶点开始,依次作其 它顶点的链接线,删除不必要的链接线,使得链接线 与障碍物边界所围成的每一个自由空间都是面积最 大的凸多边形;连接各链接线的中点形成的网络图即 为机器人可自由栅格法运动的路线。其优点是比较灵 活,起始点和目标点的改变不会造成连通图的重构, 缺点是复杂程度与障碍物的多少成正比,且有时无法 获得最短路径。

3.5神经网络法

人工神经网络是由大量神经元相互连接而形成 的自适应非线性动态系统,对于大范围的工作环境，《PLC技术应用200例》

4局部路径规划

局部路径规划的主要方法有:人工势场法、模糊 逻辑控制法、混合法、滚动窗口法等。

4.1人工势场法

人工势场法是由Khatib提出的一种虚拟力法。其 基本思想是将智能机器人在环境中的运动视为一种 虚拟人工受力场中的运动。把智能机器人在环境中的 运动视为一种在抽象的人造受力场中的运动,目标点 对智能机器人产生引力,障碍物对智能机器人产生斥 力,最后通过求合力来控制智能机器人的运动。该法结 构简单,便于低层的实时控制,在实时避障和平滑的 轨迹控制方面,得到了广泛应用,其不足在于存在局 部最优解,容易产生死锁现象,因而可能使智能机器 人在到达目标点之前就停留在局部最优点。

4.2模糊逻辑控制算法 模糊方法不需要建立完整的环境模型,不需要进 行复杂的计算和推理,尤其对传感器信息的精度要求 不高,对机器人周围环境和机器人的位姿信息的具有 不确定性、不敏感的特点,能使机器人的行为体现出 很好的一致性、稳定性和连续性,能比较圆满地解决 一些规划问题,对处理未知环境下的规划问题显示出 很大优越性,对于解决用通常的定量方法来说是很复 杂的问题或当外界只能提供定性近似的、不确定信息 数据时非常有效。但模糊规则往往是人们通过经验预 先制定的,所以存在着无法学习、灵活性差的缺点。

技 术 创 新

4.3遗传算法

遗传算法是一种借鉴生物界自然选择和进化机 制发展起来的高度并行、随机、自适应搜索算法,它采 用群体搜索技术,通过选择、交叉和变异等一系列遗 传操作,使种群得以进化。避免了困难的理论推导,直 接获得问题的最优解。其基本思想是:将路径个体表 达为路径中一系列中途点,并转换为二进制串。首先 初始化路径群体,然后进行遗传操作,如选择、交叉、复制、变异。经过若干代进化以后,停止进化,输出当 前最优个体。

遗传算法存在运算时间长,实现路径的在线规划 困难,而且在机器人的路径规划问题中应用存在着个

邮局订阅号:82-946360元/年

-245-机器人技术 中文核心期刊《微计算机信息》(嵌入式与SOC)2006年第22卷第11-2期

体编码不合理、效率低、进化效果不明显等问题。

4.4混合法 混合法是一种用于半自主智能机器人路径规划 的模糊神经网络方法。所谓半自主智能机器人就是具 有在人类示教基础上增加了学习功能的器件的机器 人。这种方法采用模糊描述来完成机器人行为编码,同 时重复使用神经网络自适应技术。由机器人上的传感 器提供局部的环境输入,由内部模糊神经网络进行环 境预测,进而可以在未知环境下规划机器人路径。此 外,也有人提出基于模糊神经网络和遗传算法的机器 人自适应控制方法。将规划过程分为离线学习和在线 学习两部分。该方法是一种混合的机器人自适应控制 方法,可以自适应调整机器人的行走路线,达到避障和 路径最短的双重优化。（智械科技）

(3)多传感器信息融合用于路径规划。单传感器难 以保证输入信息准确与可靠。多传感器所获得信息具 有冗余性,互补性,实时性和低代价性,且可以快速并 行分析现场环境。

(4)基于功能/行为的智能机器人路径规划。基于模 型自顶向下的感知-建模-规划-动作是一种典型慎思 结构,称为基于功能的控制体系结构。基于行为的方 法是一种自底向上的构建系统方法,并与环境交互作 用中最终达到目标。基于功能/行为的机器人控制结构 融合了两者优点,这是研究的新动向之一。

6结语

本文作者的创新点:深入研究了国内外关于机器 人路径规划算法的发展现状、最新进展和各种算法的 优缺点,并对未来机器人路径规划技术的发展趋势进 行了综合分析;指出机器人路径规划技术未来的研究 重点是“仿人、仿生”智能,并还将紧密的结合认知科 学、人工智能、与计算智能的研究成果,提升机器人行 为的智能度。

参考文献:

[1]宗光华.机器人的创意设计与实践[M].北京：北京航空航天大 学出版社,2003.[2]Robin著,杜军平译.人工智能机器人学导论[M].北京：电子工 业出版社，2003.[3]席裕庚,张纯刚.一类动态不确定环境下机器人的滚动路径 规划[J].自动化学报,2002,28.[4]诸静.机器人与控制技术[M].杭州：浙江大学出版社,1991.[5]XuWL,TSOSK.Sensorbasedfuzzyreactivenavigationofa mobilerobotthroughlocaltargetswitching[J].IEEETransactionson Systems,1999，29.[6]KrishnaKM,KalraPK.Perceptionandrememberanceofthe environmentduringreal-timenavigationofamobilerobot[J].RobticsandAutonomousSystems,2001,37.[7]邢军,王杰.神经网络在移动机器人路径规划中的应用研究[J].微计算机信息,2005,22:110-111

[8]Khatib.Real-timeobstacleformanipulatorsandmobilerobot [J].TheInternationalJournalofRoboticResearch.1986,1.[9]薛艳茹,郑冰等.基于模糊控制信息融合方法的机器人导航系 统[J].微计算机信息,2005,22:107-109

[10]周明,孙树栋.遗传算法原理及应用[M].北京：:国防工业出版 社,2000.[11]KazuoSugihara,JohnSmith.GeneticAlgorithmsforAdaptive MotionPlanningofanAutonomousMobileRobot[A].Proceedings 1997IEEEInternationalSymposiumonComputationalIntelligence inRoboticsandAutomation[C].1997.[12]TsoukalasLH,HoustisEN,JonesGV.Neurofuzzy motionplannersforintelligentrobots

[J].Journalof

Intelligentan-

dRoboticSystems,1997,19.(下转第252页)

《 现场总线技术应用200例》 技 整个控制既基于模型与优化的,又是基于反馈的。基

:首先进行场 术 于滚动窗口的路径规划算法的基本思路景预测,在滚动的每一步,机器人根据其探测到的局 创4.5滚动窗口法

滚动窗口借鉴了预测控制滚动优化原理,把控制 论中优化和反馈两种基本机制合理地融为一体,使得

新 部窗口范围内的环境信息,用启发式方法生成局部子 目标,并对动态障碍物的运动进行预测,判断机器人 行进是否可能与动态障碍物相碰撞。其次机器人根据 窗口内的环境信息及预测结果,选择局部规划算法, 确定向子目标行进的局部路径,并依所规划的局部路 径行进一步,窗口相应向前滚动。然后在新的滚动窗 口产生后,根据传感器所获取的最新信息,对窗口内 的环境及障碍物运动状况进行更新。该方法放弃了对 全局最有目标的过于理想的要求,利用机器人实时测 得的局部环境信息,以滚动方式进行在线规划,具有 良好的避碰能力。但存在着规划的路径是非最优的问 题,即存在局部极值问题。

5智能机器人路径规划技术的展望

随着计算机、传感器及控制技术的发展,特别是 各种新算法不断涌现,智能机器人路径规划技术已经 取得了丰硕研究成果。特别是周围环境已知的全局路 径规划,其理论研究已比较完善,目前比较活跃的领 域是研究在环境未知情况下的局部规划。从研究成果 看,有以下趋势:

(1)智能化的算法将会不断涌现。模糊控制、神经网 络、遗传算法以及它们的相互结合也是研究热点之一。(2)多智能机器人系统的路径规划。随着智能机器 人工作环境复杂度和任务的加重,对其要求不再局限 于单台智能机器人,在动态环境中多智能机器人的合 作与单个机器人路径规划要很好地统一。

-246-360元/年邮局订阅号:82-946 机器人技术 中文核心期刊《微计算机信息》(嵌入式与SOC)2006年第22卷第11-2期

实验,插值A*规划的路径代价大约是A*算法的

0.94,其计算时间是大约A*算法的1.35倍。图11中 展示了在125×75地图,障碍物密度是33.3%,用A*

算法和插值A*算法规划在的路径。图中黑线表示A* 算法规划的路径,红线表示插值A*算法规划的路径。从图中可以看出红线规划的路径不一定从节点的中 间通过,故路径明显的比黑线规划的路径代价少。表1 显示了两种算法比较的结果。

pages3310-3317.[3]K.Konolige.Agradientmethodforrealtimerobotcontrol.In ProceedingsoftheIEEEInternationalConferenceonIntelligent RobotsandSystems(IROS),2000.[4]R.PhilippsenandR.Siegwart.AnInterpolatedDynamic NavigationFunction.InProceedingsoftheIEEEInternational ConferenceonRoboticsandAutomation(ICRA),2005.[5]D.FergusonandA.Stentz.FieldD*:AnInterpolation-basedPath PlannerandReplanner.TechnicalReportCMURI-TR-7-16, CarnegieMellonSchoolofComputerScience,2005.[6]王俭,肖金球,王林芳.一种改进的机器人路径规划蚂蚁算法[J].微计算机信息,2005,5:53

[7]邢军,王杰.神经网络在移动机器人路径规划中的应用研究[J].微计算机信息,2005,11-2:110

作者简介:吕太之,男,1979-10,硕士研究生,高工,研究 方向人工智能与模式识别.E-mail:lvtaizhi@163.com;赵 春霞,女,1964-05,教授(博导),研究方向计算机应用、模式识别与智能系统。

Biography:LvTaiZhi,Male,1979-10,graduatestudent,senior engineer.ThestudydirectionisPatternrecognitionandAI.技 图5用A*算法和插值A*算法在125×75的栅格上规划路径，且每个节点的路径代价不一样。术 表1两种算法的比较结果 创 新

在实际的应用中,可以将实际的环境设置为不 同的路径代价。比如可以将公路设置为1,草地设置 为5,不平坦的路面设置为15,障碍物设置为31。实 验结果显示在此算法尤其适用与地形环境复杂的室 外环境中。（智械科技）

(211170江苏海事职业技术学院信息工程系)吕太之(210094江苏南京南京理工大学计算机学院)赵春霞 通讯地址:(211170江苏省南京市江宁区格致路309 号江苏海事职业技术学院信息工程系)吕太之

(收稿日期:2006.3.28)(修稿日期:2006.4.28)

(上接第246页)

[17]王超.王志良.基于个性和OCC的机器人情感建模研究[J].微 计算机信息，2005,3:180-181

5综述

插值A*算法是在A*算法基础上提出的一种启 发式路径搜索算法。虽然插值A*算法可以节省路径, 但是其计算时间也多与A*算法,当计算资源有限时, 这个算法的优越性就无法体现出来,所以每个算法都 有自己的优缺点,有各自的适用环境。

现在路径规划的算法很多,但是还没有那一个算 法可以处于绝对的地位,可以适用与所有环境。如何 将各种算法结合起来,发挥各个算法的优点,屏蔽各 个算法的缺点,在这个方面还是有很多的理论和实践 值得深入研究。

本文创新点:创造性地将插值算法加入到路径搜 索算法中,使得生成的路径更加平滑,路径代价更小。

参考文献:

[1]E.Dijkstra.Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik,1:269-271,1959.[2]A.Stentz.Optimalandefficientpathplanningforpartially-knownenvironments.InIEEEInt.Conf.Robot.&Autom.,1994，-252-360元/年邮局订阅号:82-946

作者简介:宋晖(1974-),男,陕西周至人,西南科技大学 计算机学院讲师,硕士,主要研究方向:机器人控制技术 和嵌入式系统.E-mail:songh717@163.com;张华:(1969-),男,四川绵阳人,西南科技大学工程技术中心教授, 博士,主要研究方向:模式识别与智能系统、图像处理 与虚拟现实技术。

(621010四川绵阳西南科技大学计算机学院)宋晖 高小明

(621010四川绵阳西南科技大学工程技术中心)张华

(CollegeofComputer,ScienceSouthwestUniversityofScience &Technology,MianyangSichuan621010,China)SongHui GaoXiaoming

(Thecenterofengineerandtechnology,SouthwestUniversity ofScience&Technology,MianyangSichuan621010,China)ZhangHua

通讯地址:(621010四川绵阳四川省绵阳市西南科技 大学计算机学院)宋晖

(收稿日期:2006.3.28)(修稿日期:2006.4.25)

篇3：人工智能算法分析论文

在人工智能领域, 提供的每种问题求解方法, 都需要某种对解答的搜索, 从提出问题 (即初始状态) 到问题的解决 (即目标状态) , 有个求解的过程, 也就是搜索过程。用于搜索的方法主要有两大类:一类是盲目搜索, 另一类是启发式搜索。盲目搜索是指在不具有对待定问题的任何有关信息的条件下, 按固定的步骤进行的搜索, 如深度优先搜索和广度优先搜索;启发式搜索是指在搜索中加入了与问题有关的启发性信息, 这些信息可以指导搜索朝着最有希望的方向前进, 加速问题的求解过程, 并找到最优解, 譬如A*算法。本文针对上述几种搜索算法, 对八数码问题进行了求解, 并进行了比较, 力求更快速、更高效地找到问题的解答。

1 八数码问题的描述

所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8, 其中一个单元格是空的。将任意摆放的数码盘 (称初始状态) 逐步摆成某种给定的数码盘的排列 (称目标状态) , 如图1所示。

对于以上问题, 我们可以把数码的移动等效成空格的移动。如图1的初始排列, 数码7右移等同于空格左移。那么对于每一个排列, 可能的一次数码移动最多只有4种, 即空格左移、空格右移、空格上移、空格下移。最少有两种 (当空格位于方阵的4个角上时) 。所以, 问题就转换成如何从初始状态开始, 使空格经过最小的移动次数最后使排列变成目标状态。

2 八数码问题的求解算法

2.1 盲目搜索

常见的盲目搜索算法有宽度优先搜索和深度优先搜索。

(1) 宽度优先搜索算法———扩展当前节点后生成的子节点总是置于OPEN表的后端, 即OPEN表作为排队表使用, 先进先出 (FIFO) , 使搜索优先向横广方向发展。

(2) 深度优先搜索算法———扩展当前节点后生成的子节点总是置于OPEN表的前端, 即OPEN表作为栈表使用, 后进先出 (FILO) , 使搜索优先向纵深方向发展。

2.2 启发式搜索

启发式搜索算法的基本思想是:定义一个评价函数 (Evaluation Function) f, 对当前的搜索状态进行评估, 找出一个最有希望的节点来扩展。

先定义下面几个函数的含义:

式中g* (n) 表示从初始节点s到当前节点n的最短路径的耗散值;h* (n) 表示从当前节点n到目标节点g的最短路径的耗散值;f* (n) 表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。

评价函数的形式可定义如 (2) 式所示:

其中n是被评价的当前节点。f (n) 、g (n) 和h (n) 则分别表示是对f* (n) 、g* (n) 和h* (n) 3个函数值的估计值。

利用评价函数f (n) =g (n) +h (n) 来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中, 如果对所有的x,

成立, 则称h (x) 为h* (x) 的下界, 它表示某种偏于保守的估计。采用h* (x) 的下界h (x) 为启发函数的A算法, 称为A*算法。

针对八数码问题我们可以将其启发函数设计如下:

其中g (n) 根据具体情况设计为d (n) , 意为n节点的深度 (从起始节点到当前节点n已经走得步数)

h (n) 根据具体情况设计为p (n) , 其可以有两种设计思路:

(1) 放错位的数码个数;

(2) 放错位的数码与其正确的位置距离之和。

启发函数中, 应用的启发信息 (问题知识) 愈多, 扩展的节点数就越少。其搜索的范围就愈小, 搜索速度就越快。显然, (1) 中的启发式函数就不够贴切, 从而在搜索过程中“不够精确的”地选用了多余节点加以扩展。而 (2) 中设计的启发函数h (n) 更接近于h* (n) , 因为其更接近实际移牌的情况, 利用的更多的信息, 自然扩展的节点就会更少, 搜索效率会更高, 后面的程序验证可以说明这一点。

由 (1) 和 (2) 两种思路而设计的启发函数, 都符合A*的条件算法的条件。现仅以思路 (2) 加以说明:由于实际情况中, 一个将牌的移动都是单步进行的, 没有交换牌等这样的操作。所以要把所有的不在位的将牌, 移动到各自的目标位置上, 至少要移动从他们各自的位置到目标位置的距离和这么多次, 所以最优路径的耗散值不会比该值小, 因此该启发函数h (n) 满足A*算法的条件。

3 程序实现

本文采用VC++6.0基于对话框的程序设计, 在图形界面上显示出八数码格局并可以随意调整格数码位置。确定初始状态格局后, 分别有“深度优先”、“广度优先”、“A*算法 (放错位的数码个数) ”、“A*算法 (放错位的数码与其正确的位置距离之和) ”等算法供选择。点击搜索按钮, 开始执行搜索, 成功或失败后提示, 并显示其生成节点个数与以遍历节点个数。其中在“A*算法 (按不在位的距离和评估) ”算法搜索成功后, 在树控件中显示, 搜索最佳路径的遍历生成树。

限于篇幅本文仅给出启发式搜索算法实现, 盲目搜索算法类似可以实现。启发式搜索算法分别用两种启发函数方法实现, 其中函数AX_search () 表示启发函数为:放错位的数码个数。函数AXX_search () 表示启发函数为:放错位的数码与其正确的位置距离之和。

其中函数AXX_search () 函数关键实现语句如下:

AX_search () 代码结构与此函数相同, 只是在EightGame对象的f赋值时调用的函数不同而已。

4 程序运行结果与分析说明

用A*算法 (启发函数为思路为放错的数码的个数) 实现八数码问题的运行界面如图2所示, 其它算法运行结果图限于篇幅, 此处略去。

针对如图1所示的初始状态和目标状态, 程序分别使用不同的深度优先搜索、广度优先搜索和启发式搜索算法 (两种不同的启发函数) 实现八数码问题的任务。表1分别反映了这几种算法在解决八数码问题时的运行结果参数:

从表1的数据可以看出, 当初始状态和目标状态一致时, 实验运行结果显示, 如果采用深度优先算法, 节点有可能一直漫无目的的扩展下去, 如果不加层数溢出限制很难在短时间内找出解。而如果采用宽度优先算法, 理论上可以找到解, 但如果初始节点与目标节点差距过大, 在短时间内也不能有效求解, 而采用A*算法远远优于盲目搜索, 并且估价函数的选择更能体现出算法的搜索效率。

备注:“耗时”只有在相同的计算机软硬件条件下才有参加意义

而对比A*算法中两种启发函数, 因为使用“放错位的数码与其正确的位置距离之和”作为启发函数比使用“放错的数码个数”作为启发函数, 应用的启发信息 (问题知识) 更多, 所以其搜索的范围就愈小, 搜索速度就越快, 自然扩展的节点数就越少。

5 结束语

通过分析不同搜索算法和不同估价函数对程序效率的影响, 可以为实际设计搜索算法和估价函数的选择提供参考依据。搜索算法作为计算机科学的一个重要的研究领域, 在当前搜索引擎迅猛发展的环境下, 搜索所需要的有效而实用的搜索策略将会越来越得到人们的重视, 其研究的重要意义也日趋明显。

参考文献

[1]马少平, 朱小燕.人工智能[M].北京:清华大学出版社, 2004.

[2]詹志辉.通过八数码问题比较搜索算法的性能[J].计算机工程与设计, 2007 (6) .

篇4：基于遗传算法的人工智能分析

关键词：遗传算法；人工智能；全局运动估计；应用分析

中图分类号：TP18 文献标识码：A 文章编号：1007-9599 （2013） 01-0240-02

所谓人工智能，就是人工的方法通过计算机实现智能化功能，或者说是人们使用机器模拟人类的智能。由于人工智能是在机器上实现的，所以又称为机器智能。从另一个角度来看，人工智能是研究怎样使计算机来模仿人脑从事的推理、证明、识别、理解、设计、学习、思考、规划及问题求解等思维活动，来解决人类专家才能处理的复杂问题。人工智能的算法很多，包括遗传算法、进化算法、蚁群算法和专家系统、神经网络等。

1 遗传算法

遗传算法的思想是先确定编码方案，对待寻优的缺陷特征参数进行编码，按一定规模初始化种群，种群中的每一个各体就代表了一个可能的解；然后根据适应度值函数计算每一个各体的适应度值并依此决定遗传操作。根据预先确定好的种群选择方案，按一定的概率对种群进行交叉、变异得到下一代，直到遗传算法的终止条件得到满足。与传统的优化算法相比，具有的优缺点如下：

1.1 遗传算法优点。不是从单个点，而是从多个点构成的群体开始搜索。之所以说是从多点而不是从单点出发，那是因为整个算法的开始是从一个初始种群开始搜索演练最优解，是从多个点开始搜索进化寻找，这样的做的一个好处是避免局部寻找最优解，从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。同时也缩短了整个搜寻额时间，整体上效率更高、结果更接近最优解。

实现简单，没有复杂的数学计算，在算法中，一般都有大量且复杂的计算作为整个算法的支撑，同时数学计算也是一步比较耗资源和时间的操作，然后在遗传算法中，在搜索最优解过程中，只需要由目标函数值转换得来的适应度信息再加上简单的比较，而不需要导数等其它辅助信息，操作流程也比较简单，没有过多的转换控制操作，中间也没有多少中间变量，算法具有较强的自适应性。

搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具，因为是在整个求解空间中探索最优解，所以，基本上不会陷入局部最优解中去。

在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，可以将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。

但是，传统的遗传算法同样拥有缺陷。

1.2 遗传算法缺点。首先，传统的遗传算法编码和解码比较复杂，因为传统的遗传算法的染色体是用二进制编制的，一个染色体就是一串0和1组成的位串或是字符串，在进化前需要做复杂的编码工作，而在得到最优解后还要做复杂的解码工作，比较繁琐和复杂，在遗传操作过程中也不易掌控，容易出错；其次，算法对初始种群的选择有一定的依赖性。

2 遗传算法在人工智能领域的应用

遗传算法在人工智能的众多领域便得到了广泛应用[2]。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。

另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。

因为遗传算法是模拟生物的进化过程的一类人工智能算法，所以，在算法的初始阶段，应该给一个初始种群给算法来进化演练。

因此，第一步是初始化种群，在初始化种群时，种群的大小要设计科学，这样才能最大力度的发挥遗传算法的性能。

在初始化种群后，就要开始进入遗传演练阶段，遗传的第一步操作是对种群的每个个体计算适应度，然后进入遗传演练。

在演练过程中，模仿生物的进化过程，有双亲结合产生下一代个体，为了能够保证种群的多样化和过早的收敛于某一个局部最优解，有了变异操作。

在遗传操作过程中，如果某一代中有个体符合最优解的特征，那么整个演练过程就可以提前结束了，否则，遗传演练会一直进行下去，知道收敛于某一个最优解或是到达最大遗传代数。

3 遗传算法的全局运动估计

运动估计是连续图像运动中图像量化的过程，全局运动一般是指相关相机的运动。一个图像序列全局运动的出现被认为是有意的，例如对于平移、缩放等；或无意的，例如手颤抖或相机摆放不稳等。后者的全局运动容易产生影响视频质量的不利因素，如抖动。从压缩的角度来看，这种易抖动的运动会造成不必要的高比特率，因此需要抑制。视频的稳定化方法意在减少这种采用全局运动估计（GME）方法的视频序列所产生的抖动。

基于特征的方法为保证GME的鲁棒性需要特征提取与选择具有一致性。提取的过程包括识别潜在的兴趣点，基于纹理结构相关标准如角落和边缘，强调区分物理真实对象。然后基于他们的跟踪能力选择较好的特征。跟踪能力的性能取决于后续帧中的弹性变形、闭塞等。因为本身是相对成熟的特征跟踪，在特征提取与选择过程中全球运动估计的鲁棒性至关重要。我们指出，在运动的像素组中出现的信息对应不同的真实结构，如深度不连续，也可以很好的对应相机的运动。这种经典的方法可能涉及潜在信息的损失，同时，选择程序的跟踪能力和异常值滤除能力可能与相机的运动不相关。

通过一种新的遗传算法（GA）的方法，它结合了特征提取与选择的过程。这种方法有效地学习最佳特征，即跟踪过程中的群像素，结果的有效性在全局最大运动估计中得到体现。这种方法与经典的算法不同，事实上我们的做法是基于盲目的结构内容特性，而不是任意的子像素的全局运动评估。这种方法特别适用于视频稳定的过程。

4 展望

根据上述在人工智能方面，基于遗传算法的特征提取与选择在全球运动估计中的应用，我们可以看出通过选择一个合适的适应度函数，直接与估计的鲁棒性进行比较，该方法可以确保视频图像的增强性能，特别是应用于视频稳定。

随着科技的不断发展，更为新颖的人工智能算法在进行全面的发展，其中数据挖掘与网络智能、人工神经元网络和贝叶斯网络数据挖掘是一种从大型数据库或数据仓库中提取隐藏的预测性信息的技术，它能挖掘出数据间潜在的模式，找出最有价值的信息和知识，指导商业行为或辅助科学研究。仿照生理网络结构的非线性预测模型，通过学习进行模式识别。神经网络最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试神经的计算模拟。神经网络是一组连接的输入/输出单元——神经元，其中每个连接都与一个权相对应。贝叶斯信任网描述一组随机变量的联合概率分布，它是用有向的无环图来表示的，联合空间中的每一变量在贝叶斯网中是用节点来表示的，节点的值可以是两值或多值。

这些研究方法将继续使得人工智能的发展更为迅速，并且得到在实际中的广泛应用。

参考文献：

[1]Holland J.Adaptation in Natural and Artificial Systems[M].Michigan：University of Michigan Press，2002.

[2]任江涛，黄焕宇，孙婧昊.基于相关性分析及遗传算法的高位数据特征选择[J].计算机应用，2006，6（26）：1404.

篇5：人工智能算法分析论文

以前写的帖子有很多人都说是在打酱油，好吧，我承认，但是前提是你已经成为一个合格的SEOER。

下面准备了三篇会在这几天发出来，也可能会多个一两篇，看在写的时候能想到的吧。

先说下我自己理解的百度排名算法的三大指标吧。

一、百度核心--超链算法

百度搜索引擎创建的核心就是超链算法这是无容质疑的，即使百度在先阶段在怎么调整也是以其为核心。

超链算法的基本原理是在某次搜索的所有结果中，被其他网页用超链指向得越多的网页，其价值就越高，就越应该在结果排序中排到前面。当然这里面不是很简单的说有超链就能排名好，友情链接也可以形成超链，单链接也是超链等等。。什么样的投票效率最高的呢?相关性，单向，用户自然引导点击浏览锚文本等等。。。

二、用户体验度

说起用户体验度不能说不说的就是快速提升网站关键词排名进首页前三位的软件们，开始关注这类软件是因为我有几个关键词一直很稳定的第一位后来到了二三位，分析首位网站基本和我的站点是没有什么竞争力度的，但是却是超过了我，然后看到这类软件，这就是用户体验度的比重在排名里面占有的部分，近来两个月百度更新了用户体验度的比重就会导致模拟用户点击类的软件大大的失去了效果，

用户体验度可以说自从搜索引擎创建之日就有的，搜索引擎创建的目的就是让使用它的人找到自己想要的东西，每个搜索关键词的用户通过搜索引擎跳转进入这个网站进行深层次的访问越高就说明这个站点对这个关键词的搜索用户越有帮助，因为搜索引擎无法判定页面内容只能在用户的访问中进行分析，那么这就需要我们的站点内容丰富而又与关键词相关，我们也可以看出百度推出了自己的浏览器，分析工具等等也是在部署这个用户体验度。

三、站点友好度

上面两条说了基本我们可以看的到摸得着的东西，第三条来说下站点与搜索引擎之间的友好度。

篇6：字典II 算法分析

字典II 算法分析

。写此文，只是看看它的注册方式而已。

字典II是一个共享软件，如果您需要使用它的全部功能，测需要进行注册。这种注册是免费的。您只要发一封标题为“注册”的电子邮件到作者信箱中即可收到以同样方式发回的注册码。为了给作者少添点麻烦，还是自己解决吧。

作用：生成字典档文件。

1、输入用户名和注册码后，启动TRW，设中断BPX HMEMCPY 再回到程序中，按确定，拦截成功。

2、按F10直到第二次回到程序中是慢走。看到如下程序。

0167:00401BC6 CALL 0046

0167:00401BCB MOV EAX[EBP+78]

0167:00401BCE LEA ESI[EBP+5C]

0167:00401BD1 PUSH EBX

0167:00401BD2 PUSH BYTE -01

0167:00401BD4 PUSH DWORD B1

0167:00401BD9 PUSH EAX

0167:00401BDA CALL EDI

0167:00401BDC MOV ECX[ESI+1C]

0167:00401BDF PUSH EBX

0167:00401BE0 PUSH EBX

0167:00401BE1 PUSH DWORD B7

0167:00401BE6 PUSH ECX

0167:00401BE7 CALL EDI

0167:00401BE9 LEA EDX[ESP+84]

0167:00401BF0 PUSH BYTE +64

0167:00401BF2 PUSH EDX

0167:00401BF3 MOV ECXESI

0167:00401BF5 CALL 00420016

0167:00401BFA LEA EDI[ESP+20]

0167:00401BFE OR ECXBYTE -01

0167:00401C01 XOR EAXEAX

0167:00401C03 REPNE SCASB

0167:00401C05 NOT ECX

0167:00401C07 DEC ECX

0167:00401C08 JZ NEAR 00401E24

0167:00401C0E LEA EDI[ESP+84]

0167:00401C15 OR ECXBYTE -01

0167:00401C18 REPNE SCASB

0167:00401C1A NOT ECX

0167:00401C1C DEC ECX

0167:00401C1D JZ NEAR 00401E24

0167:00401C23 LEA EDI[ESP+20]

0167:00401C27 OR ECXBYTE -01

0167:00401C2A XOR ESIESI

0167:00401C2C REPNE SCASB

0167:00401C2E NOT ECX

0167:00401C30 DEC ECX

0167:00401C31 JZ 00401CAC

上面的代码是什么意思，你自己看吧。重点是下文。

0167:00401C33 MOVSX EDIBYTE [ESP+ESI+20]取用户名中的一个字节，

0167:00401C38 MOV EAXEDI做为被除数

0167:00401C3A MOV ECX0A除数

0167:00401C3F CDQ

0167:00401C40 IDIV ECX

0167:00401C42 MOV ECXEDX余数传给ECX。

0167:00401C44 AND EDX80000001进行与运算，

0167:00401C4A JNS 00401C51不为负就跳。

0167:00401C4C DEC EDX

0167:00401C4D OR EDXBYTE -02

0167:00401C50 INC EDX

0167:00401C51 JNZ 00401C69不为零就跳

0167:00401C53 MOV EAXEDI否则重新赋值再次进行计算。

0167:00401C55 MOV ECX1A此次除数被换成1A，

0167:00401C5A CDQ

0167:00401C5B IDIV ECX

0167:00401C5D ADD DL41余数与DL相加得出注册码

0167:00401C60 MOV [ESP+ESI+0148]DL把注册码存入[ESP+ESI+0148]中。

0167:00401C67 JMP SHORT 00401C97

0167:00401C69 MOV EAXECX把余数传给EAX

0167:00401C6B MOV EBX03

0167:00401C70 CDQ

0167:00401C71 IDIV EBX

0167:00401C73 TEST EDXEDX

0167:00401C75 JNZ 00401C8D不为零就跳，用上面的结果ECX＋31得出注册码。

0167:00401C77 MOV EAXEDI如果为零重新赋值计算。

0167:00401C79 MOV ECX1A除数

0167:00401C7E CDQ

0167:00401C7F IDIV ECX

0167:00401C81 ADD DL61 余数DL与61相加得出注册码

0167:00401C84 MOV [ESP+ESI+0148]DL

0167:00401C8B JMP SHORT 00401C97

0167:00401C8D ADD CL31得出注册码

0167:00401C90 MOV [ESP+ESI+0148]CL

0167:00401C97 LEA EDI[ESP+20]你所输入的用户名串地址。

0167:00401C9B OR ECXBYTE -01

0167:00401C9E XOR EAXEAX

0167:00401CA0 INC ESI

0167:00401CA1 REPNE SCASB

0167:00401CA3 NOT ECX

0167:00401CA5 DEC ECX

0167:00401CA6 CMP ESIECX ESI是循环的次数。 ECX是用户名的总的位数，

0167:00401CA8 JC 00401C33有进位（也就是没有循环完毕）就跳进行下一轮计算。

0167:00401CAA XOR EBXEBX

0167:00401CAC PUSH EBP

0167:00401CAD LEA ECX[ESP+EC]

0167:00401CB4 MOV [ESP+ESI+014C]BL

0167:00401CBB CALL 00401EB0

0167:00401CC0 MOV [ESP+01B4]EBX

0167:00401CC7 LEA ESI[ESP+84]假码。

0167:00401CCE LEA EAX[ESP+0148]真码

至此就可以结束了，下文是进行比较。

0167:00401CD5 MOV DL[EAX]

0167:00401CD7 MOV CLDL

0167:00401CD9 CMP DL[ESI]

0167:00401CDB JNZ 00401CF9

0167:00401CDD CMP CLBL

0167:00401CDF JZ 00401CF5

0167:00401CE1 MOV DL[EAX+01]

0167:00401CE4 MOV CLDL

0167:00401CE6 CMP DL[ESI+01]

0167:00401CE9 JNZ 00401CF9

0167:00401CEB ADD EAXBYTE +02

0167:00401CEE ADD ESIBYTE +02

0167:00401CF1 CMP CLBL

0167:00401CF3 JNZ 00401CD5

0167:00401CF5 XOR EAXEAX

0167:00401CF7 JMP SHORT 00401CFE

0167:00401CF9 SBB EAXEAX

0167:00401CFB SBB EAXBYTE -01

总结：用户名有几位，注册码就有几位。举例。

用户名：abcde

密码：8UvW2