基于DTW算法的语音识别原理与实现【实用文档】doc

基于DTW算法的语音识别原理与实现【实用文档】doc文档可直接使用可编辑，欢迎下载

基于ＤTW算法的语音识别原理与实现基于DTW算法的语音识别原理与实现【实用文档】doc文档可直接使用可编辑，欢迎下载[摘要]以一个能识别数字0~９的语音识别系统的实现过程为例,阐述了基于DTW算法的特定人孤立词语音识别的基本原理和关键技术。其中包括对语音端点检测方法、特征参数计算方法和DＴＷ算法实现的详细讨论,最后给出了在Matｌab下的编程方法和实验结果.［关键字］语音识别；端点检测;ＭFCC系数;DTW算法［中图分类号］ＴN91２．34[文献标识码]APrｉncipleandReａlizａｔionofSpｅechRｅｃｏgnｉtionＢaseｄonDTWAlｇｏrｉthmAｂstｒａctWithａnｅxampｌeｏｆtherealizatｉoｎofａ0~9identiｆiablespeechrecogｎitioｎsysｔeｍ,theｐapeｒｄesｃribedｔhebasiｃｐrinciplｅsandkeyｔechnologieｓｏｆｉsｏlaｔedworｄspeecｈrecognitionbａsedｏnDＴWalｇorithm,incｌuｄingｍethodofｅndpoinｔdetectiｏn，cａlcuｌａtｉｏｎofchaｒactｅristicpａｒａmｅtｅrs，andimpｌeｍeｎｔatｉonｏfDTWaｌｇorithｍ。PｒograｍｍinｇｍethodunderＭatlaｂanｄexperｉmenｔａlresulｔｓaregivenattheeｎdofｔhepaper。Keｙｗorｄsｐeechrecｏgnition；endpointdｅtｅcｔiｏn；ＭFCCpaｒameter;DTWａｌgoｒｉthｍ引言自计算机诞生以来，通过语音与计算机交互一直是人类的梦想，随着计算机软硬件和信息技术的飞速发展,人们对语音识别功能的需求也更加明显和迫切。语音识别技术就是让机器通过识别和理解过程把人类的语音信号转变为相应的文本或命令的技术,属于多维模式识别和智能计算机接口的范畴[1].传统的键盘、鼠标等输入设备的存在大大妨碍了系统的小型化[１0]，而成熟的语音识别技术可以辅助甚至取代这些设备。在PDA、智能手机、智能家电、工业现场、智能机器人等方面语音识别技术都有着广阔的前景。语音识别技术起源于20世纪50年代，以贝尔实验室的Aｕdry系统为标志［1,８].先后取得了线性预测分析（LP）、动态时间归整（DTW)、矢量量化（VQ）、隐马尔可夫模型（HMM）等一系列关键技术的突破和以IBM的ViaVoiｃｅ、Micｒosｏｆt的VoicｅEｘpｒess[９］为代表的一批显著成果。国内的语音识别起步较晚,198７年开始执行国家８63计划后语音识别技术才得到广泛关注。具有代表性的研究单位为清华大学电子工程系与中科院自动化研究所模式识别国家重点实验室，中科院声学所等[9］.其中中科院自动化所研制的非特定人连续语音听写系统和汉语语音人机对话系统，其准确率和系统响应率均可达9０%以上［1］。常见的语音识别方法有动态时间归整技术(DTW）、矢量量化技术（VＱ）、隐马尔可夫模型（HMM）、基于段长分布的非齐次隐马尔可夫模型（DDBHＭM）和人工神经元网络（ANN)［1，9］。DTW是较早的一种模式匹配和模型训练技术，它应用动态规划的思想成功解决了语音信号特征参数序列比较时时长不等的难题,在孤立词语音识别中获得了良好性能.虽然HMM模型和ＡNN在连续语音大词汇量语音识别系统优于DＴW，但由于DTW算法计算量较少、无需前期的长期训练，也很容易将DTW算法移植到单片机、DSP上实现语音识别且能满足实时性[７]要求，故其在孤立词语音识别系统中仍然得到了广泛的应用。本文将通过能识别数字０～9的语音识别系统的实现过程详细阐述基于ＤTＷ算法的特定人孤立词识别的相关原理和关键技术.语音识别系统概述语音识别系统的典型原理框图[1，9—10]如图1－１所示。从图中可以看出语音识别系统的本质就是一种模式识别系统，它也包括特征提取、模式匹配、参考模式库等基本单元.由于语音信号是一种典型的非平稳信号，加之呼吸气流、外部噪音、电流干扰等使得语音信号不能直接用于提取特征,而要进行前期的预处理。预处理过程包括预滤波、采样和量化、分帧、加窗、预加重、端点检测等。经过预处理的语音数据就可以进行特征参数提取.在训练阶段，将特征参数进行一定的处理之后,为每个词条得到一个模型，保存为模板库。在识别阶段,语音信号经过相同的通道得到语音参数，生成测试模板，与参考模板进行匹配,将匹配分数最高的参考模板作为识别结果。后续的处理过程还可能包括更高层次的词法、句法和文法处理等，从而最终将输入的语音信号转变成文本或命令。图1—１语音识别系统原理框图本文所描述的语音识别系统(下称本系统）将对数字０~９共10段参考语音进行训练并建立模板库,之后将对多段测试语音进行识别测试。系统实现了上图中的语音输入、预处理、特征提取、训练建立模板库和识别等模块，最终建立了一个比较完整的语音识别系统。语音信号预处理语音信号的预处理模块一般包括预滤波、采样和量化、分帧、加窗、预加重、端点检测等.在不同的系统中对各子模块会有不同的要求,如在嵌入式语音识别系统中一般要求有防混叠滤波电路［５］、A/D转换电路和采样滤波电路等，而在计算机上实验时则可由音频采集卡完成，无需实验者亲自动手。语音信号采集在Ｍatlab环境中语音信号的采集可使用wavrecorｄ(n，fs，ch,dtype)函数录制,也可使用Windows的“录音机"程序录制成。wａv文件然后使用wavreａｄ（ｆile)函数读入。为了进行批量的的训练和识别处理，本系统的训练语音和识别语音全部使用“录音机”程序预先录制。如图2－1所示为数字0的训练语音00.wav的信号波形图,第(Ｉ)幅图为完整的语音波形，第（II)、（III）幅图分别为语音的起始部分和结束部分的放大波形图.图２－1语音０0.wav的信号波形图分帧语音信号是一种典型的非平稳信号,它的均值函数u(x)和自相关函数R(xl,x2）都随时间而发生较大的变化[5,9］。但研究发现，语音信号在短时间内频谱特性保持平稳，即具有短时平稳特性。因此,在实际处理时可以将语音信号分成很小的时间段(约10~30ｍｓ[５，7]）,称之为“帧”，作为语音信号处理的最小单位，帧与帧的非重叠部分称为帧移,而将语音信号分成若干帧的过程称为分帧。分帧小能清楚地描绘语音信号的时变特征但计算量大;分帧大能减少计算量但相邻帧间变化不大，容易丢失信号特征。一般取帧长20mｓ,帧移为帧长的1/3～１/２.在Matlａb环境中的分帧最常用的方法是使用函数enframe（x,lｅｎ，inc）,其中x为语音信号，len为帧长，inc为帧移。在本系统中帧长取２40，帧移取８０。预加重对于语音信号的频谱，通常是频率越高幅值越小，在语音信号的频率增加两倍时，其功率谱的幅度下降6dB。因此必须对高频进行加重处理，一般是将语音信号通过一个一阶高通滤波器1-0．937５ｚ-1,即为预加重滤波器。其目的是滤除低频干扰，特别是5０Hｚ到6０Hz的工频干扰，将对语音识别更为有用的高频部分进行频谱提升。在计算短时能量之前将语音信号通过预加重滤波器还可起到消除直流漂移、抑制随机噪声和提升清音部分能量的效果。预加重滤波器在Mａtlab中可由语句x=fiｌter（[１－0．９375]，１，x)实现。加窗为了保持语音信号的短时平稳性，利用窗函数来减少由截断处理导致的Gibbs效应。用的最多的三种为矩形窗、汉明窗（Ｈａmｍing）和汉宁窗(Hanｎinｇ）.其窗函数如下,式中的N为窗长，一般等于帧长。矩形窗：矩形窗：汉明窗(Hamming)：汉宁窗(Hanning)：WR=1(0≤n＜N-1)0(Other)WHM=0.5-0.46cos(2πn/(N-1))(0≤n＜N-1)0(Other)WHN=0.5-0.5cos(2πn/(N-1))(0≤n＜N-1){{{0(Other)(2-1)(2-2)(2-3)窗口的选择非常重要，不同的窗口将使能量的平均结果不同。矩形窗的谱平滑，但波形细节丢失;而汉明窗则刚好相反，可以有效克服泄漏现象，具有平滑的低通特性［4—６］。因此，在语音的时域处理方法中，一般选择矩形窗，而在语音的频域处理方法中，一般选择汉明窗或汉宁窗［５-6]。在Matｌab中要实现加窗即将分帧后的语音信号乘上窗函数,如加汉明窗即为x＝ｘ．＊hamminｇ（N）。本系统中的端点检测采用时域方法故加矩形窗,计算MＦCC系数时加汉明窗。端点检测在基于DTＷ算法的语音识别系统中，无论是训练和建立模板阶段还是在识别阶段，都先采用端点检测算法确定语音的起点和终点。语音端点检测是指用计算机数字处理技术从包含语音的一段信号中找出字、词的起始点及结束点，从而只存储和处理有效语音信号。对汉语来说,还可进一步找出其中的声母段和韵母段所处的位置。语音端点检测是语音分析、合成和识别中的一个重要环节，其算法的优劣在某种程度上也直接决定了整个语音识别系统的优劣。进行端点检测的基本参数主要有短时能量、幅度、过零率和相关函数等。端点检测最常见的方法是短时能量短时过零率双门限端点检测，近年来在此基础上发展出的动态窗长短时双门限端点检测方法[４］也被广泛使用。短时能量语音和噪声的主要区别在它们的能量上,如图3－1(III）和图3-2(IＩＩ)所示。语音段的能量比噪声段的大，语音段的能量是噪声段能量叠加语音声波能量的和。对第ｎ帧语音信号的短时能量Ｅn的定义为：（3-１）xn为原样本序列在窗函数所切取出的第n段短时语音,Ｎ为帧长。因为在计算时使用的是信号的平方,故将Eｎ作为一个度量语音幅度值变化的函数有一个缺陷，即对高电平非常敏感.因此在许多场合会将Eｎ用下式来代替：(3-2)这样就不会因为取平方而造成信号的小取样值的大取样值出现较大差异。本系统中窗函数为WR(见式2—1），N为240。图3-１(I)和图３-2（I）分别为数字0的训练语音0０.wav和数字4的训练语音40．wav的波形，图3-1（III）和图3－2（IＩI)分别为它们的短时能量。图３—１语音00。wav的时域分析参数图3-２语音40。ｗav的时域分析参数短时过零率短时过零表示一帧语音信号波形穿过横轴(零电平）的次数。对于连续语音信号，过零意味着时域波形通过时间轴;而对于离散信号，如果相邻的取样值的改变符号则称为过零。过零率就是样本改变符号次数，定义语音信号寿（m）的短时过零率Zｎ为：（3—3)1(x≥1(x≥0)-1(x≤0)sgn[x]={清音的能量多集中在较高的频率上，它的平均过零率要高于浊音,故短时过零率可以用来区分清音、浊音以及无声。图3—1(II）和图3-２(II）分别为数字０的训练语音00.wav和数字4的训练语音40。wａv的短时过零率。从图中可以看到清音‘s’的过零率明显高于其后的‘i’音,有声段过零率明显高于无声段，但在鼻音阶段过零率迅速滑落到无声水平而能量值则是缓慢下滑。在实际应用时并不能通过式３-3直接计算过零率,因为在无声段噪声使语音波形在０值附近来回摆动，导致计算出的过零率和有声段的区别并不十分明显.比较简单的解决方法是设定一个差的阈值δ,使不仅xn（m)＊xn（m－1）〈0，还要｜xn（m)－ｘn(ｍ-1)|>δ。在本系统中经多次试验取定δ＝0.0１。双门限端点检测双门限端点检测顾名思义需要两级检测，即短时能量检测和短时过零率检测。在开始检测之前需要设定４个门限，即分别为短时能量和短时过零率各设置一个高门限和一个低门限:EＨigh、ELow和ZＨiｇh、ZLow。整个语音端点检测分为四部分:静音段、过度段、语音段、结束段。在静音段中如果能量或过零率有一个超过了其低门限，则认为进入了过度段。在过度段中,由于参数数值较小，还不能确定是否真的进入语音段,只有两个参数的其中一个超越了高门限才被认为是进入语音段。当参数降至低门限则认为进入结束。此外，还有两种可能会引起端点检测的误判：一是短时噪音引起的误判，此时则需要引入最小语音长度门限进行噪声判定，即语音段时间小于一定数值则认定为是噪声,重新回到静音段,本系统设为20ms;二是语音中字与字的时间空隙引起的误判,此时需要设定最大静音长度门限来降低识别的错误率，本系统所训练和识别的都为单字,故无需设置此门限。在双门限端点检测中4个门限的设定至关重要,门限设定的好坏将直接影响端点检测的结果。门限值的设置还没有一个通用可靠的方法，需要根据经验和特定环境进行调整.常见的方法有最大值乘上某个比率、中位值乘上某个比率、最小值乘上某个常数、前三帧平均值乘上某个常数等。本系统中EHigh，ELow，ZHigｈ，ZLow的取值分别为:ＥHiｇｈ=mａx（[mｉn（amp)*10，mｅaｎ（amp）＊０.2,max(ａmｐ)*0.1]）;ZHigｈ=max（［round（max（zcr）＊0.１），5]);ELｏw=miｎ([min(amp)*10，mean（amp）*0.２，mａx(amp)＊0.１]）；ZLoｗ＝mａx（[rｏund（ｍean（zｃr)*０.1)，３］);图３-3和图3—4分别是数字0的训练语音00。wａｖ和数字4的训练语音40。ｗａv的端点检测结果,红线之间的部分为检测出的语音有声段。图３－3语音00。wav的端点检测结果图3-4语音４0。ｗav的端点检测结果语音识别参数提取经过预处理的语音数据就可以进行特征参数提取,特征参数的好坏将直接影响系统的性能和效率,对特征参数的要求包括[9-１0］：提取的特征参数能有效地代表语音特征,具有很好的区分性；各阶参数之间有良好的独立性；特征参数要计算方便,最好有高效的计算方法,以保证语音识别的实时实现。LPC与LPＣＣ系数LPC（ＬiｎｅａrPredｉcｔｉonＣｏeｆficｉenｔ，线性预测系数)模拟人发音器官的声管模型，是一种基于语音合成的参数模型。在语音识别系统中很少直接使用LPC系统,而是由ＬPＣ系数推出的另一种参数LPCC。LPＣC（LineａｒPredictｉｏｎCepsｔruｍCｏeｆficient，线性预测倒谱系数)是LＰC在倒谱域中的表示。该特征是基于语音信号为自回归信号的假设,利用线性预测分析获得倒谱系数。LPCC的优点是计算量小，易于实现，对元音有较好的描述能力,缺点是对辅音描述能力较差.MFＣＣ系数ＬPC模型是基于发音模型建立的，LPCC系数也是一种基于合成的系数，这种参数没有充分利用人耳的听觉特性.实际上，人的听觉系统是一个特殊的非线性系统，它响应不同频率信号的灵敏度是不同的,基本上是一个对数的关系［9—10].近年来，一种能够比较充分利用人耳的这种特殊感知特性的系数得到了广泛应用,这就是Mｅl尺度倒谱系数（Ｍeｌ—scalｅｄCｅpstrumCｏｅｆficiｅｎtｓ，简称ＭFCC）。大量研究表明，MFＣC系数能够比ＬＰCC参数更好地提高系统的识别性能［1０］。MＦCC系数的计算是以“ｂarｋ”为其频率基准的，它和线性频率的转换关系是:（4-1）MFCC系数也是按帧计算的，首先要通过FFT得到该帧信号的功率谱Ｓ(ｎ），转换为Ｍｅl频率下的功率谱。这需要在计算之前先在语音的频谱范围内设置若干个带通滤波器：Hｍ（ｎ)m=0，1,…，Ｍ－1；n=0，1，…，N/2－1（4—2)M为滤波器的个数，通常取24，与临界带的个数一样；N为一帧语音信号的点数，为了计算FFT的方便，通常取2５6.滤波器在频域上为简单的三角形,其中心频率fm在Mel频率轴上是均匀分布的。如图4-1所示为Mel尺度滤波器组,包含24个滤波器，语音信号帧长取为256个点，语音信号的采样频率为８KＨz，。图4-１Mｅl尺度滤波器组带通滤波器的系数事先计算好，在计算MFCC系数是直接使用。MFCC系数的计算过程如下：预处理:确定每一帧语音采样序列的长度(如N=256)，并对每帧序列s（n)进行预加重、分帧和加窗处理;计算离散功率谱:对预处理的每帧进行离散ＦFT变换得到其频谱，再取模的平方作为离散功率谱S(n)；将功率谱通过滤波器组：计算Ｓ(n）通过M个Hｍ（n)后所得的功率值，即计算S(n）和Hm(n)在各离散频率点上的乘积之和，得到M个参数Ｐm,m=0,1，……M-1；取对数:计算Ｐｍ的自然对数，得到Lｍ，m=０，１，……M—1；离散余弦变换：对Lｍ计算其离散余弦变换,得到Dｍ，m＝0，１，……Ｍ－1,舍去代表直流成份的D0，取D1,D2，……，Dk作为MFCＣ参数。具体流程可以用框图４—2表示为：图4—2MFＣC系数计算流程图在Maｔｌaｂ环境中计算M个滤波器的系数可以调用语音工具箱voiｃebox中的函数melbankm(ｍ,n，fs）来实现，其中m为滤波器的个数，n为语音帧长，fs为采样频率。计算mｆcｃ系数的函数为ｍｅlcｅpst(s，ｆs），ｓ为语音信号。ＤＴW算法实现DTW（DynamｉcTimeWarping，动态时间规整）是语音识别中较为经典的一种算法.在实现小词汇表孤立词识别系统时,其识别率及其它指标与HＭM算法实现几乎等同[９]。又由于HＭＭ算法复杂，在训练阶段需要提供大量的语音数据通过反复计算才能得到模型参数，而DTW算法本身既简单又有效,因此在特定的场合下获得了广泛的应用。匹配模式模板匹配方法的语音识别算法需要解决的一个关键问题是说话人对同一个词的两次发音不可能完全相同，这些差异不仅包括音强的大小、频谱的偏移,更重要的是发音时音节的长短不可能完全相同，而且两次发音的音节往往不存在线性对应关系。设参考模板有M帧矢量{R(１）,R（2)，…R（m），…，R（M)},R(m)为第m帧的语音特征矢量，测试模板有Ｎ帧矢量｛T(１）,T（2），…T(ｎ），…，Ｔ（N)}，T(n)是第n帧的语音特征矢量.d(Ｔ(in)，Ｒ(ｉm))表示T中第ｉn帧特征与R中im帧特征之间的距离，通常用欧几里德距离［9－１0］表示。直接匹配是假设测试模板和参考模板长度相等，即iｎ=im；线性时间规整技术假设说话速度是按不同说话单元的发音长度等比例分布的，即。显然，这两种假设都不符合实际语音的发音情况，我们需要一种更加符合实际情况的非线性时间规整技术。如图５-１所示为三种匹配模式对同一词两次发音的匹配距离(两条曲线间的阴影面积)，显然D3〈D2<D1.待测模式待测模式T参考模式Rttttt直接匹配D1(T,R)线性匹配D2(T,R)非线性匹配D3(T,R)图5－1三种匹配模式对比ＤTW算法原理DTＷ是把时间规整和距离测度计算结合起来的一种非线性规整技术，它寻找一个规整函数ｉｍ＝Ф(in）,将测试矢量的时间轴n非线性地映射到参考模板的时间轴m上,并使该函数满足:（５-1)Ｄ就是处于最优时间规整情况下两矢量的距离.由于DTW不断地计算两矢量的距离以寻找最优的匹配路径，所以得到的是两矢量匹配时累积距离最小所对应的规整函数，这就保证了它们之间存在的最大声学相似性。DTＷ算法的实质就是运用动态规划的思想,利用局部最佳化的处理来自动寻找一条路径，沿着这条路径，两个特征矢量之间的累积失真量最小,从而避免由于时长不同而可能引入的误差DTW算法要求参考模板与测试模板采用相同类型的特征矢量、相同的帧长、相同的窗函数和相同的帧移。为了使动态路径搜索问题变得有实际意义，在规整函数上必须要加一些限制，不加限制使用式(5-1）找出的最优路径很可能使两个根本不同的模式之间的相似性很大，从而使模式比较变得毫无意义。通常规整函数必须满足如下的约束条件:边界限制:当待比较的语音已经进行精确的端点检测，在这种情况下，规整发生在起点帧和端点帧之间，反映在规整函数上就是:(5—２)单调性限制由于语音在时间上的顺序性，规整函数必须保证匹配路径不违背语音信号各部分的时间顺序。即规整函数必须满足单调性限制：(5—３）连续性限制有些特殊的音素有时会对正确的识别起到很大的帮助，某个音素的差异很可能就是区分不同的发声单元的依据，为了保证信息损失最小，规整函数一般规定不允许跳过任何一点。即:（5-4)DTW算法的原理图如图５-2,把测试模板的各个帧号n=1～N在一个二维直角坐标系中的横轴上标出，把参考模板的各帧m=1～Ｍ在纵轴上标出，通过这些表示帧号的整数坐标画出一些纵横线即可形成一个网格，网格中的每一个交叉点（ti，rj）表示测试模式中某一帧与训练TTФ(1)=1时间规整函数123inNR12imMФ(N)=M图5-2DTW算法原理图(in,im)(in-1,im)(in-1,im-1)(in-1,im-2)图5-3局部约束路径模式中某一帧的交汇。DTW算法分两步进行，一是计算两个模式各帧之间的距离,即求出帧匹配距离矩阵，二是在帧匹配距离矩阵中找出一条最佳路径。搜索这条路径的过程可以描述如下：搜索从(１，1）点出发，对于局部路径约束如图5-３，点（in,im）可达到的前一个格点只可能是（in—1，iｍ）、（in—１,im－l）和（in－1，ｉm－２）。那么(iｎ,im）一定选择这三个距离中的最小者所对应的点作为其前续格点，这时此路径的累积距离为:Ｄ（iｎ,iｍ）=d（Ｔ（ｉn),R（ｉm))＋min{Ｄ(iｎ—1，ｉm)，Ｄ（in－1，ｉｍ—1）,D(in－1,im-2)｝（5—5)这样从（l，1)点出发（令Ｄ（1,1）=0）搜索,反复递推,直到（N，M）就可以得到最优路径，而且D（N，M)就是最佳匹配路径所对应的匹配距离.在进行语音识别时，将测试模板与所有参考模板进行匹配,得到的最小匹配距离Dｍin(N，M)所对应语音即为识别结果.ＤＴＷ算法改进DＴW算法虽然简单有效,但是动态规划方法需要存储较大的矩阵，直接计算将会占据较大的空间，计算量也比较大。由图5－3的局部路径约束可知DTＷ算法所动态搜索的空间其实并不是整个矩形网格，而是局限于对角线附近的带状区域［9］,如图5－４所示,许多点实际上是达不到的。因此,在实际应用中会将DTW算法进行一些改进以减少存储空间和降低计算量。常见的改进方法有搜索宽度限制、放宽端点限制等。搜索宽度限制以图５－3中的局部约束路径为例,待测模板轴上每前进一帧，对于点(iｎ，im)只需要用到前一列（in-１，im)、（in-l,ｉm—l）和（in-１,im－２)三点的累积距离,也就是iｍ—1和iｍ—2两行的累积距离。整个DＴW算法的计算过程递推循环进行,也就是每一行中的格点利用前两行格点的累积距离计算该点的累积距离的过程。基于这种循环递推计算，只需分配3×N的存储空间重复使用,而不需要保存帧匹配距离矩阵和所有的累积距离矩阵.又由于DTＷ算法的动态搜索宽度局限于对角线附近的带状区域，假设其宽度为width,如图5—4和图５—６,则实际只需分配3×wiｄｔｈ的存储空间即可。图5-4带状搜索区域图５—5搜索宽度限制存储空间放宽端点限制普通DTW对端点检测比较敏感，端点信息是作为一组独立的参数提供给识别算法的。它要求两个比较模式起点对起点,终点对终点，对端点检测的精度要求比较高.当环境噪声比较大或语音由摩擦音构成时,端点检测不易进行，这就要求在动态时间规整过程中给以考虑。放松端点限制方法不严格要求端点对齐，克服由于端点算法不精确造成的测试模式和参考模式起点终点不能对齐的问题.一般情况下，起点和终点在纵横两个方向只要放宽２－3帧就可以，也就是起点可以在(1,1)，(l,2)，(1,3）,（２,1)，(3，l），终点类似。如图5—6.图5-6改进的DTW算法原理图C图5-6改进的DTW算法原理图Ck=(ik,jk)C1=(1,1)CK=(I,J)j=i-rj=i+r时间规整函数widthijt1t2t3titITRr1r2rjrJ在放宽端点限制的DTＷ算法中,累积距离矩阵中的元素(1，l）,（ｌ,2），（l,3），（2，l)，(３,１)不是根据局部判决函数计算得到的，而是直接将帧匹配距离矩阵的元素填入，自动从其中选择最小的一个作为起点,对于终点也是从松弛终点的允许范围内选择一个最小值作为参考模式和未知模式的匹配距离。Ｍａtlaｂ编程结果在音频信号处理方面，Mａtlａb提供了ｗａv文件读写函数和声卡的录音和放音函数,利用这些函数可以实现某些语音信号处理工作。语音工具箱voicｅbox为实现语音识别提供了许多实用函数。为了进行批量的的训练和识别处理，本系统的训练语音和识别语音全部使用“录音机"程序录制。本语音识别系统的文件结构如图6—1所示，其中ｔraｉn文件夹中包含图6-1语音识别系统的文件结构数字０～９的训练语音，ｔest中包含若干测试语音，都分别以相应数字作为文件名的首数字.文件vad。m为端点检测程序，ｍfcc．m计算ＭFＣC系数，tｒaｉn．m为语音训练程序，它将计算得到的特征参数存入ｍｆｃc.mａt作为模板库.dtw．m为DTW算法的实现程序，dtwｔeｓt．m为测试程序。图6-2为4组语音的识别测试结果图，从中得出本语音识别系统的正确识别率为0.825,详细数据如下表：数字012345６78９0～9正确数４244343342３3错误数０2001011027正确率1。０00。５01．001。000.751。0０0．7５0。751。０00.500。825图6-2语音识别测试结果参考文献詹新明,黄南山，杨灿.语音识别技术研究进展[Ｊ]。现代计算机(专业版)，2００8，（09）相征,朗朗，王静．基于基音频能值的端点检测算法［Ｊ]。安徽工程科技学院学报，2008,（09）沈宏余，李英。语音端点检测方法的研究[J］。科学技术与工程,2008,(08)李景川，董慧颖。一种改进的基于短时能量的端点检测算法[J]．沈阳理工大学学报，2008,（０6)蔡妍.语音信号端点检测方法的研究[硕士学位论文］［D］。江南大学，200８吴亚栋.语音识别基础［Ｒ］。上海交通大学计算机系,200７-01吴晓平,崔光照，路康.基于ＤTW算法的语音识别系统实现[J］．电子工程师，2００4，(０7)谭保华，熊健民,刘幺和．语音识别技术概述[J].郧阳师范高等专科学校学报，2004,（0６)朱淑琴。语音识别系统关键技术研究[硕士学位论文][Ｄ]。西安电子科技大学，20０４何强，何英。ＭAＴLＡB扩展编程［M］．清华大学出版社,2002—0６专业综合设计报告课程名称：电子专业综合设计设计名称:基于模拟退火算法的ＴSP算法姓名:学号:班级：电子09０3指导教师：朱正为起止日期：201２。11．1—201２.12．3０专业综合设计任务书学生班级:电子0９03学生姓名：学号：2０09５830设计名称:基于模拟退火算法的ＴSP算法起止日期：2012.11．1—2012。1２.３0指导教师设计要求:旅行商问题，即TＳP问题（TraveｌlingＳａlｅsmａnProｂlem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。此设计是用模拟退火算法来实现ＴＳP问题的寻求最优解。专业综合设计学生日志时间设计内容2012．11。９初步了解模拟退火算法的TＳP算法201２．1１。12设计算法流程、确定解题思路20１2。1１.2０讨论算法流程及解题思路的可行性，为仿真做准备20１2.１2。２运用MATLＡＢ软件进行实验仿真,分析仿真结果2012.12。8整理实验报告2012．12.17答辩专业综合设计考勤表周星期一星期二星期三星期四星期五专业综合设计评语表指导教师评语:成绩：指导教师：年月日一ＴＯC\ｏ＂1—3"＼h\z\uHYPERLINＫ\l”_Tｏc３42１3356１＂设计目的和意义ＰAGEREF_Tｏｃ3421335６１\h5二设计原理PAGEＲＥF_Tｏc34２133562\h52。１模拟退火算法的基本原理.。。。。。..。。．。。.。。.。．.．.．．．.。．。．..。.．。...。．.．。。．。。..．.。.。。．。。．.．.．。.。.。.。．..．。...．.。。..。。..。。..。．.．。.。。.．．。...。。.52。2TSＰ问题介绍.。。。。..．.．。。。.。。。..。．。。..。．．．..。。．.．。。.．。。.。。．.．.。.．。.．.。.。．...．．。．.．．。．。.。。.。.。．。．..．．。．．.。..。。．．...．.。．.。.。。。...．。。．。。..。。。６三详细设计步骤..．．。。.。。.。。．..．..．。。。..．。。..．．。.。．.．...。.。.。.．.．.。...．。...．．..．..。。.。．。.．..．。..。。。．。。。。..。.。...．.。。。。.．．..。。.。.。．.．.．。.。。。.。.．..．．.。．PＡＧＥREF_Ｔoc342133563\h73.1.算法流程83.2模拟退火算法实现步骤PAGＥＲEF_Toc３4213３565＼ｈ８四设计结果及分析9ＨＹPERLＩＮK\l”_Toc3421３3５７3"4．1MAＴＬAB程序实现及主函数．.．．。.。。。．.。.．。．。.。．。.．。．..。.．.。。。.．..．.。。.．。。.．．．。。.．．．.。．．．。.。。．。.．。．...。...．。。.。.。.。．．。..．．．．.。。。..。.。．．．.94.1。1计算距离矩阵。．．。．.。.．。。.。。。..。．。。。。。..．。..．。.。。.。..。。.。。.。。..。..。...。。。。。。.。.。。。．。。...．。.。..。。...。．。.。．．．.。.．。．..．。．．...．。．。９4.1。2初始解..。。。。．．.。.。.．．.。．．。．.。.。．。．..。．．。.。。。.。..。。。．。。..。.．.。.。。。．.。．．．..。．。．。。.。．．.。．.。..。.．.。。..。..。.．。。。.。.．．．.．。。.。。．.１0４.1.3生成新解.．...。．。..。。．。.。。。。。．．.．。..。．。。。。.。..．。。.。．。.。.．.。．．。.。．。．.．．．。。．..．。。．．.。．．．．．．．。．。。..。。．..．。。。..。。.．．。．１04.１．4Ｍetｒｏpolis准则函数..．．。。．。．．。..．.。．。．．．.。。．。.。.．．．．。。。．.。．。..。。。..。。．.．．．．..。.。.．。。。..。．．．.。。。..．．．．．．。.．.．．.10４。1．5画路线轨迹图..。。.．。。..．。．．。。．。。。。．.。.．。。．。..．。。。．．．。。..。．。。.．.。．。．。．。。。．。.．．．。．．．。.。．。。..。.．。。..。.。。.．。.。。.。.．．.．.。.．。．．。．1１4.1.6输出路径函数..．。.．.．。.。...。。。..。.．．..。．。.。。。．.。.。..。。。．.。．。．．。。．。．..。。．。。．。.．..。。。.。。．.。。。。。.。.．．。..。。．。．。。。。.．．124.1．7可行解路线长度函数。。．.。．。．。．。．．.．.。。。.．。．..．。...。。。．。。.．．．．。．．.．。．．.。。.．。.。。．。..。.。。。。。．。。.。..．。.．.。．。...。．．124。１.8模拟退火算法的主函数．。。.。。．。．.．..。。.．.。。。。．.。．.。。。.．..。。。．.．。。．。．。。。。。.。。.．。..．．.．.。。.。。.。。．。．。。。..。.。．。.。.．.．。.．。1３4．2．仿真结果15五HYPＥRLINK\l”_Tｏc3421335７5"体会PAGＥRＥF＿Ｔｏc34２133５75\h18六ＨYPＥＲLINＫ\l"_Toc３４21335７6”参考文献PAGＥREＦ_Tｏc３42133576\ｈ19基于模拟退火算法的TＳP算法一、设计目的和意义旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的NP难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。首先介绍了旅行商问题,给出了其数学描述以及实际应用，进而给出解决TSP的一种比较精确的算法—-模拟退火算法。然后阐述了模拟退火算法的基本原理,重点说明了其基本思想及关键技术。最后运用MATLAB语言实现了该算法，并将其运用到解决旅行商问题的优化之中。数值仿真的结果表明了该方法能够对数据进行全局寻优，有效克服了基于导数的优化算法容易陷入局部最优的问题。了解模拟退火算法的ＴSP算法的基本思路及原理,并应用MATLＡB实现仿真，熟练掌握MATLAB的操作方式及应用,能正确书写报告。二、设计原理２。1模拟退火算法的基本原理模拟退火算法足2O世纪8O年代初提出的一种基于蒙特卡罗(MeｎteCarlo）迭代求解策略的启发式随机优化算法。它通过Metroｐolis接受准则概率接受劣化解并以此跳出局部最优，通过温度更新函数的退温过程进行趋化式搜索并最终进入全局最优解集.其出发点是基于物理中固体物质的退火过程与一搬的组合优化问题之间的相似性.模拟退火法是一种通用的优化算法,其物理退火过程由以下三部分组成。加温过程。其目的是增强粒子的热运动,使其偏离平衡位置。当温度足够高时,固体将熔为液体，从而消除系统原先存在的非均匀状态。等温过程.对于与周围环境交换热量而温度不变的密封系统，系统状态的自发变化总是朝自由能减少的方向进行的，当自由能达到最小时,系统达到平衡状态。冷却过程.使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加热过程对应算法的设定初温，等温过程对应算法的Meｔｒopolｉs抽样过程,冷却过程对应控制参数的下降。这里能量的变化就是目标函数,要得到的最优解就是能量最低态.Metroｐolis准则是SA算法收敛于全局最优解的关键所在,Metｒoｐolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。模拟退火算法为求解传统方法难处理的TSP问题提供了一个有效的途径和通用框架，并逐渐发展成一种迭代自适应启发式概率性搜索算法。模拟退火算法可以用以求解不同的非线性问题，对不可微甚至不连续的函数优化，能以较大的概率求的全局有化解,该算法还具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性，并且能处理不同类型的优化设计变量(离散的、连续的和混合型的），不需要任何的辅助信息，对目标函数和约束函数没有任何要求.利用Metｒｏpolis算法并适当的控制温度下降过程,在优化问题中具有很强的竞争力,此设计即为基于模拟退火算法的TSP算法。SA算法实现过程如下（以最小化问题为例）：（1）初始化：取初始温度T０足够大，令T=T0，任取初始解S1,确定每个T时的迭代次数，即Ｍeｔropｏlis链长L.(2)对当前温度T和k=１，2,……，l，重复步骤(3)~(６）.(3）对当前S1随机扰动产生一个新解S2。(4)计算S2的增量dｆ=ｆ（S2)－f(S1）其中ｆ为S1的代价函数。（５)若ｄｆ<0,则接受S2作为新的当前解，即S1=S2；否则计算S２的接受概率ｅxp(—df/T）,即随机产生(0,1)区间上均匀分布的随机数ranｄ,若ｅxp(—df/T)〉ｒaｎd也接受S2作为新的当前解，S１=S2；否则保留当前解Ｓ1.（6）如果满足终止条件Stop,则输出当前解s1为最优解,结束程序。终止条件Stoｐ通常为:在连续若干个Metｒopｏlis链中新解s2都没有被接受时终止算法，或是设定结束温度。否则按衰减函数衰减T后返回步骤（2）。以上步骤成为Metropoｌｉs过程。逐渐降低控制温度，重复Metrｏｐｏlis过程，直至满足结束准则Ｓtｏp，求出最优解。２。2TSP问题介绍旅行商问题（ＴraveliｎgSalesmａnProｂｌem，简称ＴSＰ）又名货郎担问题，是威廉·哈密尔顿爵士和英国数学家克克曼(T．P。Kｉｒkman)于19世纪初提出的一个数学问题,也是著名的组合优化问题。问题是这样描述的:一名商人要到若干城市去推销商品,已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线,使总的路程（或旅费)最小。TSP刚提出时,不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解,而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题。这个问题数学描述为：假设有ｎ个城市，并分别编号，给定一个完全无向图Ｇ=(V，E),Ｖ=｛1，2，…,n}，n>1。其每一边（ｉ,ｊ）E有一非负整数耗费Ci,j(即上的权记为Ｃｉ,ｊ,ｉ,jＶ)。G的一条巡回路线是经过V中的每个顶点恰好一次的回路。一条巡回路线的耗费是这条路线上所有边的权值之和。TSP问题就是要找出G的最小耗费回路。人们在考虑解决这个问题时,一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合），计算出每条路线的总里程,最后从中选出一条最短的路线。假设现在给定的4个城市分别为A、B、C和D，各城市之间的耗费为己知数，如图１所示。我们可以通过一个组合的状态空间图来表示所有的组合，如图图1顶点带权图图2TSP问题的解空间树从图中不难看出，可供选择的路线共有6条,从中很快可以选出一条总耗费最短的路线：顶点序列为(A，C，B,D,Ａ)。由此推算，若设城市数目为n时,那么组合路径数则为（ｎ-１)!.很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大,组合路线数将呈指数级数规律急剧增长,以至达到无法计算的地步,这就是所谓的“组合爆炸问题”。假设现在城市的数目增为20个，组合路径数则为（２０－1）!≈１.216×1０1７，如此庞大的组合数目，若计算机以每秒检索1０00万条路线的速度计算,也需要花上３86年的时间［6］。三、详细设计步骤3。1算法流程模拟退火算法求解流程框图如图１所示。图3模拟退火算法求解流程框图３．2模拟退火算法实现步骤如下：（1)控制参数的设置需要设置的主要控制参数有降温速率q、初始温度T０、结束温度Tｅnd以及链长L。(2）初始解对于ｎ个城市TSＰ问题，得到的解就是对1～n的一个排序，其中每个数字为对应城市的编号，如对１0个城市的TSP问题{1,2，3，４，5,6，７,８，9,10｝,则|1|10|2|4｜5|6｜8｜7|9|3就是一个合法的解,采用产生随机排列的方法产生一个初始解S.（3）解变换生成新解通过对当前解S1进行变换,产生新的路径数组即新解，这里采用的变换是产生随机数的方法来产生将要交换的两个城市，用二邻域变换法产生新的路径,即新的可行解S２。例如ｎ＝10时，产生两个[1,10]范围内的随机整数ｒ１和r2，确定两个位置,将其对换位置，如r1=4，ｒ2＝7９51638７1042得到的新解为9５１７3８６１04２(4）Meｔropoｌis准则若路径长度函数为（S），新解的路径为（Ｓ2）,路径差为d=(Ｓ2）—（S1),则Ｍｅtropｏliｓ准则为如果dｆ〈0，则以概率１接受新路线,否则以概率eｘp（－df/T)接受新路线。(5)降温利用降温速率q进行降温,即T=qT，若T小于结束温度，则停止迭代输出当前状态，否则继续迭代。四、设计结果及分析4．１MATＬAB程序实现及主函数4。1.１计算距离矩阵利用给出的N个城市的坐标，算出N个城市的两两之间的距离,得到距离矩阵（ＮN).计算函数为Dｉｓｔancｅ，得到初始群种。程序如下functionD=Distanse(a)functionD=Distanse(a)%%计算两两城市之间的距离%输入a各城市的位置坐标%输出D两两城市之间的距离row=size(a,1);D=zeros(row,row);fori=1:rowforj=i+1:rowD(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5;D(j,i)=D(i,j);endend4。1.2初始解初始解的产生直接使用MATＬＡＢ自带的函数ｒandperm，如城市格式为Ｎ个，则产生初始解:S1=randperm（N）；%随机产生一个初始路线S1=randperm（N）；%随机产生一个初始路线4。1。3生成新解解变换生成新解函数为NewAnswer，程序代码如下:functionS2=NewAnswer(S1)functionS2=NewAnswer(S1)%%输入%S1:当前解%%输出%S2：新解N=length(S1);S2=S1;a=round(rand(1,2)*(N-1)+1);%产生两个随机位置用来交换W=S2(a(1));S2(a(1))=S2(a(2));S2(a(2))=W;%得到一个新路线4.１．4Mｅtｒｏｐolis准则函数Mｅtropolis准则函数为Mｅｔｒopolis，程序代码如下:function[S,R]=Metropolis(S1,S2,D,T)function[S,R]=Metropolis(S1,S2,D,T)%%输入%S1：当前解%S2:新解%D:距离矩阵（两两城市的之间的距离）%T:当前温度%%输出%S：下一个当前解%R：下一个当前解的路线距离%%R1=PathLength(D,S1);%计算路线长度N=length(S1);%得到城市的个数R2=PathLength(D,S2);%计算路线长度R2=PathLength(D,S2);%计算路线长度dC=R2-R1;%计算能力之差ifdC<0%如果能力降低接受新路线S=S2;R=R2;elseifexp(-dC/T)>=rand%以exp(-dC/T)概率接受新路线S=S2;R=R2;else%不接受新路线S=S1;R=R1;end4。1.5画路线轨迹图画出给的路线的轨迹图函数为DｒaｗＰaｔh,程序代码如下:functionDrawPath(Chrom,X)functionDrawPath(Chrom,X)%%画路径函数%输入%Chrom待画路径%X各城市坐标位置R=[Chrom(1,:)Chrom(1,1)];%一个随机解(个体)figure;holdonplot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5])plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)fori=1:size(X,1)text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]);endA=X(R,:);row=size(A,1);fori=2:row[arrowx,arrowy]=dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));%坐标转换annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]);endholdoffxlabel('横坐标')ylabel('纵坐标')title('轨迹图')boxon4.1。6输出路径函数将得到的路径输出显示在CommaｎdWindoｗ中,函数名为OuｔpuｔPaｔh.functionp=OutputPath(R)functionp=OutputPath(R)%%输出路径函数%输入：R路径R=[R,R(1)];N=length(R);p=num2str(R(1));fori=2:Np=[p,'—>',num2str(R(i))];enddisp(p)4.1．7可行解路线长度函数计算可行解的路线长度函数为PａｔｈLength，程序代码如下：functionlen=PathLength(D,Chrom)functionlen=PathLength(D,Chrom)%%计算各个体的路径长度%输入：%D两两城市之间的距离%Chrom个体的轨迹[row,col]=size(D);NIND=size(Chrom,1);len=zeros(NIND,1);fori=1:NINDp=[Chrom(i,:)Chrom(i,1)];i1=p(1:end-1);i2=p(2:end);len(i,1)=sum(D((i1-1)*col+i2));end4．１.8模拟退火算法的主函数模拟退火算法参数设置如表一所列.表一参数设定降温速率ｑ初始温度T0结束温度Tend链长L0．910000.001200clc;clear;clc;clear;closeall;%%ticT0=1000;%初始温度Tend=1e-3;%终止温度L=500;%各温度下的迭代次数（链长）q=0.9;%降温速率%%加载数据loadCityPosition1;%%D=Distanse(X);%计算距离矩阵N=size(D,1);%城市的个数%%初始解S1=randperm(N);%随机产生一个初始路线%%画出随机解的路径图DrawPath(S1,X)pause(0.0001)%%输出随机解的路径和总距离disp('初始种群中的一个随机值:')OutputPath(S1);Rlength=PathLength(D,S1);disp(['总距离：',num2str(Rlength)]);%%计算迭代的次数TimeTime=ceil(double(solve(['1000*(0.9)^x=',num2str(Tend)])));count=0;%迭代计数Obj=zeros(Time,1);%目标值矩阵初始化track=zeros(Time,N);%每代的最优路线矩阵初始化%%迭代whileT0>Tendcount=count+1;%更新迭代次数temp=zeros(L,N+1);temp=zeros(L,N+1);fork=1:L%%产生新解S2=NewAnswer(S1);%%Metropolis法则判断是否接受新解[S1,R]=Metropolis(S1,S2,D,T0);%Metropolis抽样算法temp(k,:)=[S1R];%记录下一路线的及其路程end%%记录每次迭代过程的最优路线[d0,index]=min(temp(:,end));%找出当前温度下最优路线ifcount==1||d0<Obj(count-1)Obj(count)=d0;%如果当前温度下最优路程小于上一路程则记录当前路程elseObj(count)=Obj(count-1);%如果当前温度下最优路程大于上一路程则记录上一路程endtrack(count,:)=temp(index,1:end-1);%记录当前温度的最优路线T0=q*T0;%降温fprintf(1,'%d\n',count)%输出当前迭代次数end%%优化过程迭代图figureplot(1:count,Obj)xlabel('迭代次数')ylabel('距离')title('优化过程')%%最优解的路径图DrawPath(track(end,:),X)%%输出最优解的路线和总距离disp('最优解:')S=track(end,:);p=OutputPath(S);disp(['总距离：',num2str(PathLength(D,S))]);disp('')toc４。2仿真结果及分析优化前的一个随机路线图如图4所示：图4总路线距离约为57.00优化以后的最优解路线如下图5：图5该优化路径的总路程近似为30。00，已为最优解。模拟退火算法进化过程图如下图6:由图可以看出,优化前后路径长度得到很大改进，变为原来的52．４％，６5代以后路径长度已经保持不变了,可以认为已经是最优解了.上图为用模拟退火算法解决TSＰ的GUI(GraｐhicｓUserIｎｔerfaｃｅ，图形用户界面）。这是由14个城市构成的一个对称ＴSP实例，利用上述算法对该实例进行模拟退火求解,设定初始温度T0=1０0０，冷却速率为0.9,经过仿真得到的最优解与已知最优解非常接近,所需时间也令人满意。五、体会使用MATIＡB对求解TSP问题的模拟退火算法程序进行了仿真。平均结果表明，首先该算法能够找到ＴSP问题的最优解，说明算法的正确性。其次算法对TSP问题的求解时间并不呈指数增长,说明了算法的有效性.5。1关于MATＬAＢ的体会ＭＡTＬAB是当今科学界最具影响力、也是最具活力的软件,它起源于矩阵运算，并已经发展成一种高度集成的计算机语言。然后,了解到了MATLAB软件的功能。它提供了强大的科学运算、灵活的程序设计流程、高质量的图形可视化与界面设计、便捷的与其他程序和语言接口的功能。我们应该熟练掌握其使用方法。5．2关于基于模拟退火算法的TSP算法的体会模拟退火算法是依据Ｍetｒopolｉs准则接受新解，该准则除了接受优化解外，还在一定的限定范围内接受劣解,这正是模拟退火算法与局部搜索法的本质区别，在避免陷入局部极小值、提高解空间的搜索能力和扩大搜索范围方面具有明显的优越性.本次设计给出了一种TSP的求解算法,并用MATLAB语言编程实现了算法.算法实验结果表明，对大多数组合优化问题而言，模拟退火算法在求最优解和求解时间均达到了满意的结果.利用MAＴLAＢ语言实现的模拟退火程序，能够找到系统的最优解，仿真结果证明了该方法的有效性.采用该方法既可使我们熟悉MATLAB语言,又可以加深对模拟退火算法的认识和理解，以此来设计智能系统。旅行商问题一直都是业界研究的重点,其应用范围广，在许多领域都有其重要的指导意义。随着对ＴSP问题研究的深入,目前已经提出了多种TSP问题的变种，如：多目标TSＰ问题、局部重复路径的TＳP问题、多人TSP问题以及带时间约束的TSP问题等等。TSＰ的算法研究领域中，除非有新的解决组合优化问题的算法框架出现，各种仿自然的算法结合局部优化的算法思想仍将是研究的重点。针对各种模拟退火算法的优劣，如何扬长避短，提高算法的时间效率和寻优能力,目前许多学者致力于各种求解算法的综合集成的研究，如遗传模拟退火算法、模拟退火蚁群算法、混合遗传算法、混合蚂蚁算法等等.结合实际问题设计适当的算法参数和局部优化策略以构造混合算法将是解决TSP的重要途径。客观地说，目前并不存在一种求解ＴSP问题的最佳算法,各个算法都有其应用的局限性:经典算法追求精确解,但是忽略了算法的时空消耗，可行性不高；而现代流行改进算法则是追求近似解，降低了算法的时空消耗，但是在求解结果上往往不能让人满意。我认为今后在TSＰ的算法研究上应该把握3个方面：继续改进已有TSP算法；采用人工智能的思想，创造新的TＳP算法；集合各个算法的优点,进行混合ＴSP算法的研究。目前这些相关方向业界人士都有所涉及,也都取得了一定成效，相信在不久的将来，TＳP问题一定会有更好的解决方案。六、参考文献[1］高海昌，冯博琴,朱莉．只能优化算法求解ＴＳP问题［J］．控制与决策，２0０6,21(0３）：241-247,２52。［2]苗卉，杨韬。旅行商问题(TSＰ)的改进模拟退火算法.微计算机信息（管控一体化），200７，２３（11）:2４1［3］万军洲．基于模拟退火技术的旅行商问题求解算法.软件导刊，２00６，(８）:８８,88-８９.［4]盛国华，陈玉金，改进模拟退火算法求解TSP问题[J］．电脑知识与技术,２00８（15）：1103-1１04，1１03.［5]曲强，陈雪波.基于MATLAB的模拟退火算法的实现.鞍山科技大学学报,2０0３，26（３）：197-１９８[6]冯剑，岳琪，模拟退火算法求解TSＰ问题［Ｊ]。森林工程，２008,24（01)：９４-96。基于RSSI的室内定位算法研究摘要：近年来，随着无线网络的迅速发展,室内定位技术在诸多领域中得到了广泛应用,成为重要的研究对象之一。室内定位技术的核心要素是定位算法。优秀的定位算法，可以有效地降低无线信道的影响，并利用较少的网络资源获取较高的定位精度。论文在研究了基于ＲSSI测距的无线定位算法后，重点研究了基于泰勒级数展开的RSSI测距定位算法,针对传统算法的缺点提出了改进方案。关键词：室内定位RＳSI泰勒级数1.引言现代社会，基于信息技术的发展,导航、定位等信息在人们纷繁庞杂的信息要求中，占据了越来越大的比重。比如航海、军事、智能公交、煤矿等领域均要求室外或者室内导航定位技术。进入二十一世纪以来，由于传统局域网己经不能满足人们的需求，加上无线网络的组网成本大幅下降,无线网络呈现出蓬勃发展的趋势,而人们在使用的同时也越来越不满足于现状，开始对其有了更多更深层次的要求。目前，世界上正在运行的卫星导航定位系统主要是美国的全球定位系统(GlobａlPｏｓｉtiｏｎｉnｇＳｙｓtemＧPS)，但GPS这种定位方法是在室外使用得较多的定位方法,它不适用于室内。针对ＧPS的室内定位精确度偏低、成本较高等缺点,具备低成本、较高定位精度的诸多室内定位技术便应运而生，并在诸多领域正越来越发挥着重要的作用。例如:煤矿企业要实现对井下作业人员的实时跟踪与定位、方便企业对员工的管理与调度,要用到室内定位技术，营救被困人员，室内定位技术可以提供被困人员位置信息,为营救节省大量的时间；在超市等购物中心,室内定位技术可以实现对商品定位、消费者定位、广告发布、地图导航等功能。所以若能实现低成本且高精度的室内定位系统,具有非常重要的现实意义.未来的发展趋势是室内定位技术与卫星导航技术和通信技术有机结合，发挥各项技术自身的优点，不仅可以提供较高的定位精度和响应速度,还可以覆盖较广的范围,真正实现无缝的、精确的定位.２室内定位方法简介所谓室内定位技术是指在室内环境下确定某一时刻接收终端在某种参考系中的位置。在室内环境下,大多采用无线局域网来估计接收终端的位置。一般典型的无线局域网架构中接入点（ＡP，AceｓsPoｉｎt)类似于无线通信网络中的基站,大部分无线局域网都使用RF（RadiｏFｒeｑuｅnｃy）射频信号来进行通信,因为无线电波可穿越大部分的室内墙壁或其它障碍物,已提供更大的覆盖范围。常见的室内定位方法有：（１)ZiｇＢee定位技术ZigＢee是一种新兴的短距离、低速率、低功耗、低成本及网络扩展性强的无线网络技术，它的信号传播距离介于射频识别和蓝牙之间，工作频段有三个——2。4GHｚ(IＳM国际免费频段）和８58/91SMHz，除了可以应用于室内定位，还可以应用于智能家居、环境监测等诸多领域。它有自己的无线电标准IEＥE802．15．4,定位主要是通过在数千个节点之间进行相互协调通信实现的。这些节点以接力的方式通过无线电信号将数据从一个节点传到另一个节点，通信效率非常高，同时，这些节点只需要很小的功率。低功耗与低成本是ZigBee定位技术最显著的优点.(2)室内ＧPＳ定位技术当ＧPS接收机在室内工作时,卫星发送的GPS信号由于受到建筑物的遮蔽会大大衰减，而且不可能像室外一样直接从卫星广播中提取时间信息与导航数据，因此,定位精度会很低。但是，延长在每个码延迟上的停留时间可以有效提高室内信号灵敏度,利用这个特性的室内GPS定位技术则可以解决上述GPS定位的缺陷。室内GPS定位技术利用数十个相关器并行地搜索可能的延迟码提高卫星信号质量以提高定位精度,同时也可以提高定位速度。GＰＳ定位导航信号免费、有效覆盖范围大是室内GPＳ定位技术的优势，但卫星信号在长距离的传播过程中受到的噪声干扰相对较大,导致信号到达地面时较弱，从而不能穿透障碍物，还有较高定位器终端成本等则构成了它的劣势。（3)红外线室内定位技术通过安装在室内的光学传感器接收经过红外线标识调制和发射的红外线进行定位是红外线室内定位技术的基本思想。虽然红外线室内定位技术在理论上具有相对较高的定位精度,但是红外线仅能视距传播、易被灯光或者荧光灯干扰且传输距离较短则是这项技术最为明显的缺点。受这些缺点的制约，它的实际应用前景并不乐观，而且这项技术的应用需要在每个走廊、房间安装接收天线,造价也较高。因此，红外线室内定位技术在具体应用上有非常大的局限性.（4)超声波定位技术超声波定位采用基于时间到达（TimｅＯfArrival,TOA)进行测距，然后选择合适的定位算法利用测得的一组距离值来确定物体的位置。超声波定位系统由若干个参考节点和定位节点组成,定位节点向位置固定的参考节点发射频率相同的超声波信号,参考节点在接收到超声波信号后向定位节点做出回应,由此得到定位节点与各个参考节点之间的距离。当得到三个或者三个以上不同参考节点与定位节点之间的距离测量值时,就可以利用这组距离测量值根据相关定位算法确定出定位节点的位置。虽然超声波定位系统整体结构也比较简单，定位精度比较高,但是，它需要大量的底层硬体设施投资，成本要求非常大，而且超声波受多径效应和非视距传播影响也很大,对定位精度的进一步提高形成了一定的技术瓶颈。(5）蓝牙室内定位技术蓝牙是一种短距离、低功耗的无线传输技术，基于它的室内定位技术是基于接收信号强度指示测距的。通过在室内安装适当数量的蓝牙局域网接入点，再把基础网络的链接模式配置成基于多用户、主设备为蓝牙局域网接入点，就可以计算出定位节点的位置坐标。目前，蓝牙定位技术受到蓝牙信号传播距离短的制约主要应用于小范围定位。由于蓝牙室内定位系统具有设备体积小、易于集成在其它系统中等优点，因此比较容易推广普及.而且,当采用该技术进行室内小范围定位时，蓝牙信号传输不受视距的影响，并且设备很容易就能够被系统发现.其缺点为蓝牙设备的成本比较大,在复杂的空间环境中，蓝牙定位系统受噪声信号干扰大，且稳定性较差。（6）射频识别技术射频识别技术进行定位是利用射频方式进行非接触式双向通信交换数据达到的.此技术成本低，作用距离一般为几十米，可以在非常短的时间内得到厘米级的定位精度信息。目前，理论传播模型的建立、用户的安全隐私和国际标准化等问题是射频识别研究的热点和难点。虽然射频标识技术有自身的优点，但相比于蓝牙定位技术,它不容易被整合到其它系统中。(6)Ｗi—Fi定位技术基于网络节点能够实现自身定位的前提,无线局域网（WLＡN）是一种全新的定位技术，它可以在诸多的应用领域内实现复杂的大范围监测、定位和跟踪任务.现在比较流行的Wi—Ｆi定位是基于IEEE802．11标准、采用经验测试和信号传播模型相结合的一种定位解决方案.该定位系统需要的基站数量比较少,比较容易安装，具有相同的底层无线网路结构，系统定位精度较高。但是，如果定位的测算不是依赖于合成的信号强度图，而是仅仅依赖于哪个Wi—Fi的接入点最近，那么在楼层定位上很容易出错。目前，受到Wi-Ｆi收发器的覆盖范围一般只能达到半径90m以内的区域这一缺点的制约，该系统主要应用于小范围的室内定位。并且,无论是应用于室内定位还是室外定位,太系统对干扰信号的反应都很灵敏，从而影响其定位精度,定位节点的能耗也较高。除了以上提及的定位技术，还有基于光跟踪定位、基于图像分析、电脑视觉、信标定位等室内定位技术。3.无线定位基本方法要实现定位，首先要把移动终端到基站间的距离计算出来。在基于测距的定位方法中，常用的测量两个无线设备间距离的技术大致有以下四种:3.1基于电波传播时间（TOA）若电波从移动终端到基站的传播时间为t，电波传输速度为ｃ,则移动终端位于以基站位置为圆心,以为半径的圆上.如果同时有三个以上的基站收到移动终端的无线信号,则移动终端的二维位置的坐标可由以基站为圆心的三个圆的交点确定。基于TOＡ的无线定位，时间上１的误差将导致定位结果在空间上产生300m左右的误差，因此要求基站拥有非常精确的时钟,收发信号的双方能够精确同步。3。2基于电波传播时间差（TDOA）通过测量无线信号到达基站的时间而不是无线信号到达基站的绝对时间来对移动终端进行定位，从而降低对时间同步的要求.根据信号到达两个基站的时间差，则可以确定移动终端位于以这两个基站为焦点的双曲线上。如果有三个以上的基站，则可以建立起多个双曲线方程,这些双曲线方程的交点就是移动终端的二维坐标位置.3.3基于电波入射角（ＡＯA）在这种方法中基站通过接收机天线阵列测出移动终端发送电波的入射角,并确定一条从基站到移动终端的焦径线。通过多个基站对移动终端无线信号的测量，能够得到多条焦径线,这些直线的交点就是移动终端的位置。由于无线信号具有多径衰落等特性，采用此种方法在障碍物较少的地区可以得到较高的精确度，并且设备复杂价格昂贵。3。４基于信号强度（ＲSSI)无线信号的信号强度随着传播距离的增加而衰减，接收方与发送方离得越近，则接收方的信号强度就越强；接收方离发送方越远,则接收到的信号强度就越弱。根据移动终端测量接收到的信号强度和已知的无线信号衰落模型，可以估算出收发方之间的距离，根据多个估算的距离值，可以计算出移动终端的位置.这一种方法相对简单,不需要对网络添加额外的硬件设备,但是由于影响无线信号强度因素较多，定位精度不是很理想。由于室内定位范围一般相对较小,且现在室内定位一般是利用的高频率的无线电,传播速度为光速,时间上只要稍微出现一点误差,基于时间的测距方法便会产生非常大的误差,而基于ＲSＳI的测距方法则没有这个缺点，且其信号模型在小范围内比较接近理论值，所以室内定位技术一般均是采用基于RＳSI的定位方法。本文档主要探讨的就是