优化算法的MATLAB实现技巧单

1、天津财经大学本科毕业论文中文题目：优化算法的MATLAB实现技巧英文题目：院系名称：专业班级：学号:姓名:指导教师：20XX年x月x日内容摘要第1章引言错误！未定义书签1.1 现代优化计算方法错误！未定义书签1.2 MATLA概述错误！未定义书签1.3 旅行商问题错误！未定义书签第2章禁忌搜索算法的基本思想错误！未定义书签2.1 相关概念介绍错误！未定义书签2.2 局部搜索算法错误！未定义书签2.3 禁忌搜索算法错误！未定义书签第3章MATLA限现TSP问题的实现技巧.错误！未定义书签3.1 重要概念的定义错误！未定义书签3.2 算法中的方法选择问题错误！未定义书签3.3 MATLAB实现技巧

2、错误！未定义书签第4章结果分析错误！未定义书签4.1 错误！未定义书签4.2 错误！未定义书签五、总结与展望错误！未定义书签5.1 总结错误！未定义书签5.2 前景展望错误！未定义书签第1章引言1.1 现代优化计算方法现代优化计算方法(简称优化算法)是一门交叉学科，是以人类等生物的行为方式或物质的运动形态为背景，运用数学抽象方法建立算法模型，再通过计算机的运算来求解组合最优化问题。优化算法涉及到了人工智能、分子运动，遗传学、动物学、神经系统和统计力学等学科的概念和理论，以模型的抽象为其关键点，以数学理论为基础。比较常见的有禁忌搜索、模拟退火、遗传算法、蚁群优化和人工神经网络等算法，这些算法主要

3、是解决优化问题中的难解问题。自20世纪80年代以来计算机的蓬勃发展，这些算法借助计算机得到了快速发展和广泛应用。1.2 MATLAB既述MATLAB是matrix和laboratory两个词的组合，意为矩阵实验室，是由美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB可以进行矩阵运算、绘制数据和函数、实现算法、创建用户界面、连接其他编程语言的程序等操作，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的问题解决方案，代表了当今国际科学计算软件的先进水平。1.3 旅行商问题旅行商问题，即

4、TSP问题(TravellingSalesmanProblem),是数学领域中的著名问题之一。问题概述为：假设有一个旅行商人要拜访n个城市，他必须选择拜访n个城市所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是：所要求得的路径路程为所有路径之中的最小值。文章主要是运用禁忌搜索算法解决TSP问题，详细讲解算法的MATLAB实现技巧，并对算法的优化性能进行分析。首先介绍了禁忌搜索算法的基本思想，以此可以了解算法自身的特点和优势，然后运用禁忌搜索算法解决TSP问题，通过MATLAB实现，最后对优化结果进行分析，拟提出今后研究的方向。第2章禁忌搜索算法的基

5、本思想禁忌搜索算法是优化算法中比较常见的算法，本章先介绍禁忌搜索算法的相关概念，而后将以TSP问题为例介绍局部搜索算法，最后通过局部搜索算法发展到禁忌搜索算法。2.1 相关概念介绍2.2 局部搜索算法2.3 禁忌搜索算法概念：禁忌搜索算法(tabusearch)是局部邻域搜索算法的推广，是人工智能在组合最优化中的一个成功应用。Glover在1986年首先提出这个概念。用一个禁忌表记录已经达到过的局部最优，或达到局部最优的一些过程，在后续搜索中避免或有选择的搜索这些点或过程。算法体现了集中和扩散两个策略：(1)集中：体现在局部搜索。从一点出发在这点的邻域内寻找更好的解以达到局部最优。(2)扩散：

6、通过对禁忌表中点的禁忌，达到一些没有搜索的点，从而实现更大区域的搜索。第3章MATLAB解决TSP问题的实现技巧本章我们将以中国31省会城市的TSP可题为例，运用禁忌搜索算法解决。选取算法实现中重要部分的MATLAB弋码进行详细分析。若需要完整注释代码，请参照附录。3.1 重要概念的定义从第2章中我们了解到，禁忌搜索算法中有几个重要的概念：禁忌表、禁忌表长度、候选解集合、候选集个数、最好候选解集合、最好候选解个数以及所求的最优解、最优值。在后述程序中我们进行如下定义:概念命名作用禁忌表TabuList用来记录该次循环不能交换的禁忌兀素的此时禁忌长度禁忌长度TabuLength用合理的方法确定的

7、不能执行交换的长度候选集个数CandidateNum即全部邻域解的个数，预设一个充分大的数候选解集合Candidates用来记录此时全部候选解的集合最好候选解个数BestCandidateNum用合理的方法确定一个每次进入循环的候选解个数最好候选解集合BestCandidate每次循环从候选解集合中用合理的方法筛选出最有可能成为最优解的解集合最优解BSF用来记录当前执行结果的最优解，即该问题当前的最小路径最优值BestL用来记录当前最优解对应的最优值，即该问题当前的最小路径长度3.2 算法中的方法选择问题在用MATLABW决TSP'可题时，还有一些算法中如何选择和实现的问题，如下：问题

8、1:选择什么为禁忌的对象？问题2:禁忌的长度如何选取？问题3:候选集合如何选取？问题4:终止原则怎样给出？问题5:如何利用更多的信息？这些问题会在本章中一一解决。3.3MATLA政现技巧我们先来简单分析这个问题，我们的目标是求解中国31个省会城市的TSP'可题，即我们需要给定31个城市的位置坐标数据，然后通过编程运算，返回出最优解和最优值。明确了数据输入和结果输出，我们就开始解决这个问题。首先用MATLAB建立一个函数文件，函数名命名为TabuSearch（禁忌搜索），这个函数有两个返回参数，分别命名为BestShortcut和theMinDistance,即该问题的最短路径（最优解）

9、和最小距离（最优值）。（对应代码行4）首先定义一个Clis佚巨阵用于记录城市坐标数据，然后定义一个城市数目变量CityNum,调用MATLAB43的siz时令CityNum=size（Clist,1）,求该TSP可题的规模，即城市数目，本题中为31。后期若所求城市数量和城市位置坐标发生改变，则只需对Clist中的数据进行修改。（对应代码行8到15）初始化一个行列均为CityNum的全零矩阵dislist（即31*31矩阵），用于记录31个城市中每两个城市之间的距离。运用数学中两点间距离公式，通过两层循环计算相应两个位置上的距离并将结果记录到dislist矩阵中。（对应代码行16到23）现在我们

10、要对3.1.1中定义的一些重要概念进行初始化。（对应代码行24到32）将禁忌表TabuList初始设定为城市数目阶零向量（即31*31矩阵），后续禁忌对象将填入该矩阵，那么禁忌对象如何选择？对应3.2.2中的问题1。上章中选择城市顺序对换作为禁忌对象目的是希望不再考虑某组顺序的对换，以避免不会有更好解出现，及又回到原有解这两种可能情况。本章中的禁忌对象沿用这种选取方法，即将两个城市顺序对换作为禁忌对象。问题2中禁忌的长度如何选取？禁忌长度的选择有很多种，长度过短会造成循环，过长会造成算法的记忆存储量增加。因此，一种禁忌长度的选择，要保证禁忌长度既不太长，也不太短。本章中用公式（3.1）定义禁忌

11、长度，即（31*（31-1）/2）开平方再取整，得21。TabuLength=round（CityNum*（CityNum-1）/2F0.5）（3.1）前面定义时提到，要将候选集个数CandidateNum,预设为一个充分大的数，本问题中我们设为200。同时初始化候选解集合Candidates为一个CandidateNum行，CityNum列的零矩阵（即200*31矩阵）。这里需要说明一下，问题3"候选集如何选取”中的候选集并非指本段提到的候选解集合Candidates,而是指后文会提到白最好候选解集合BestCandidate,因为在禁忌搜索算法中，候选集是一个不断更新并逐渐向包含

12、最优解的集合靠近的集合，而Candidates是包含所有解的一个集合，BestCandidate才是一个变动筛选更优候选解的集合，后文将具体分析BestCandidate是如何进行选取的。随机产生一个CityNum长的向量S0乍为初始解，将S0的值赋给最优解向量BSF,并将最优彳KBsetL初始化为正无穷。现在来解决问题4,终止原则怎样给出？禁忌搜索是一个启发式算法，在可接受的计算时间内，应该使所求解尽量接近最优解。本题中我们设置一个计时器和一个计数器。计数器令循环计数变量p初始值为1,规定终止参数StopL的值为80*CityNum,每执行一次循环，p的值加1,设置一个长度为p的向量ArrB

13、estL,并将每次循环彳#到的最优值BestL记录在相应位置。即当p值大于80*31时，默认循环更新最优解次数足够多，我们有理由认为此时求得的最优解集已足够包含最优解，此时的最优值即为ArrBestL中的最小值，最优解为最优值对应的解。在求得最优解的同时，若计时器计算的时间已超过一个可以接受的范围，那么该程序也是不合理的。（对应代码行37至IJ45,152到153）现在我们需要编写一个目标值函数，求解每一个解S0的目标值，即当前解S0的距离。初始DistanV=0,用n返回s的长度（本题n=31）。初始i=1,当i<n-1时执行循环，每次循环DistanV加上此时s的位置到s下一个位置的

14、距离，循环执行30次结束。最后DistanV的值再加上从最后一个城市位置返回初始位置的距离，即为所求目标值。（对应代码行178到186）t70EfunctionF=Fun(dislj.stjs)3t#ciik<DEFunJfU>*目标值的数，求解mSif应的距离】二9-DistanV：。；ISO-n=Eize(Sj2):-fori=l：(n-l)182-DistanV=Di£tanV+disliEt(sCi)j;1S3end184-PistanV=DistanV;+dLslLstCsfn)s11t);185-F=DistanV.在上章禁忌搜索算法的思想中我们提到，要建立一

15、个位置对换表格，通过比较对换后的目标值，使目标值下降，或者虽然当前目标值上升，但有可能跳出局部最优解。现在我们来建立这个对换表格。（对应代码行47到73）建立对换表格A,初始化为Candidates行，2列的零矩阵（即31*2矩阵）。初始化一个循环变量i=1。Setp1:当循环变量i不超过候选集个数CandidateNum,进行循环，执行Setp2。Setp2:先从0到31随机生成一个正整数集M（a,b）。若2加，重新执行Setp1;若a和b不相等,向量A的第i行第1列记录a和b中较大的数，第2列记录较小的数。如果是初始循环，即i=1,定义变量isa=0,执行Setp4;否则执行Setp3。S

16、etp3:初始化循环变量j=1,当j不超过i-1时，执行判断，如果矩阵A的第i行和第j行相等，令isa=1,跳出循环，执行Setp4;否则isa=0。Setp4:如果isa为0,将i值加1,返回Setp1;否则直接返回Setp1。注释：1、Setp2中生成M的目的是随机生成两个城市，放在一个行向量里，要求a和b不相同,是要求用于交换的两个城市不能相同。2、变量isa的作用是判断当前新生成的用于交换的两个城市和已经生成的城市是否重复,若重复，则取消记录，跳转下一次循环。3、循环结束后会得到一个对换表格A,共Candidates行，每行有两个随机生成的城市,且各行均不相同。ifiClercs；Sa

17、ndidat±1(1111+2卜制蜡11个号能阵，-ar.d二.-川亡*1=mn£工andidatHun%当微坏变里不擅迈愈UJS茹(Coiuli<lati避心循环LtyUunKrHidL>7'*的Ti就*情忙,+一向至g：，椒联上36Mt£n的目的是I®机主或两个抽布，放在一个行向直身Jif融口果两千城市不相同A（i.l）-imiKCD.Kil!>）;%区大邺小的旭席帮列在向醐弟工行ifi-的口累是利瑞f后环第一次运行而坏:33口；男起女交里。4口（此时可以自桂跳转到罂面5行（蜡-wa：i<1n*杏期farj-lii-苒

18、川；到51后开Lfh（i,l）-=A<j>tiCjf2）如罩一A的算行和*j行相.LfJft-1：版工bH上帮.出画：is玲。;JS晋'ikts为。endendendifsa伽累”西口CRP诵由）i=i*i：*3谑科五里1mi*回班山遢坏再告口匕工姻HI，叵到山工工借*End73-切尚北I-X广；】行晶印结年后芸得到一个惟选恁合小Candidates'均不附同）（触的H机生或两个城市完成了对换表格的建立，我们现在解决提出的问题3,候选集合如何选取？前面我们已经分析过了，这里的候选集合是我们定义的最好候选解集合BestCandidateo先来解释下，为什么要定义Bes

19、tCandidate。在上章讲述的禁忌搜索算法的思想中，候选解集合的选取可以大到全部邻域集合本身，使得计算量增加但是比较的范围增大；也可以小到只有一个元素，使计算量减小但是可比较的范围也减小。在本章的问题中，我们将候选解集合Candidates定义为此时全部候选解的集合，但由于数据较多，计算量和计算时间过大。因此，我们需要选择一种合理的方式从Candidates中选择出合适数量的优质解组成集合BestCandidate。那么我们采用什么方法呢？本题中的方法是：先用Candidates中的全部候选解逐个调用对换表格A中的数据进行交换，将得到的解填入BestCandidate中，当BestCand

20、idate中已满时，将后来的解顺次刷新之前较差的解，从而得到最好候选解集合BestCandidate。下面我们来实现这个过程：（对应代码行74到107）我们将最好候选解个数BestCandidateNum设为100,即保留前100个最好候选解。将最好候选解集合BestCandidate初始化为BestCandidateNum行,4列的矩阵（即100*4矩阵）。期裂变晕的作雨品当前知果得到一个以前出现过由川工,门行，则期满记录，制转下一次宿F初始化目标值列F为零列向量，共BestCandidateNum歹U。Setpl:初始化循环变量i=1,当i不超过BestCandidateNum时，执行循环

21、。把候选解集Candidates中的第i行放入当前解S0中，将候选解集的第i行第A(i,1)位置和A(I,2)位置交换(即将交换表格A中第i行的a和b值交换)，调用函数Fun计算当前候选解集的第i行对应解的目标值。如果i<=BestCandidateNum,执行Setp2,否则执行Setp3。Setp2:将此时的候选解填入BestCandidate中，第1列记录序号i,第2列记录目标值F(i),第3、4列记录当前交换的位置a和b,如下表，返回Setp1。iF(i)a->A(i,1)b->A(i,2)1F(1)A(1,1)A(1,2)2F(2)A(2,1)A(2,2)Setp3

22、:初始化循环变量j=1,当j不超过BestCandidateNum时，执行判断，如果当前候选解集合的第i行对应解白目标值<BestCandidate中第j行第2歹U存放的目标值，执行Setp4,否则将j值加1,继续循环。Setp4:将BestCandidate表中第1列更新为i值，第2列更新为此时的F(i)值，第3列更新为a值，第4列更新为b值。返回Setp1。注释：Setp1中的判断表示，当BestCandidateNum未填满时，执行Setp2,将候选解填入BestCandidate;填满时执行Setp3,比较当前候选解的目标值和表中已有候选解的目标值，若更优则更新。T7-fcr询&

23、quot;4ndi'li7(匚由电谢刃:IB制fl?第亶的有:！行前夺二F-CniLdatcdCAdELmpIl)=MICIL<is.耳也为苗。上书三二，L»mR'ffl位宣的烧击支搐町皿珏丁显宗持金帽需力加0!b5;M皿印文丽;rBlK3行电了厘艮邙国X餐M-ip：11.当II/it而鼻的73田吟自IHUNB7-I3/打七匚-duWr<W3rar7UlJ.di-rl(uj.fTI束Ef1!门，丁一7g-ErrtCandLdartelJ-i.,黑Iff并海序号晶-andi.Jats2J=f111.h.：,s1m的金-斤在丁目力也ta-JKEGk&g

24、t.lJHmhJJhfi用。上行体国才酊上野的E.总Mt.|i.?ki；世-静L»£18，E二叨dimrHu*行已H死勾茫占安萨木/二甲il文的杵堇广用加-foej=l;&-si:C3ndi.d.i+-lfiii!L*JSiSiE»-TtL-and-,ds*r*i,rf号IEH-LfFai<：Ek-4Ttui41teCj.r2l口母门。川三柒事科知小。酗自373a耽闾第；MHE帆d就前后算出(打近1如1R-的WUFtliM小11吨.的=mA"/DC-醇-B«tCendtUT""：<1=1-4<1l&

25、lt;ib1JJ：的-|LQt-静W皿-endLK-nlLlH1fl买里aLM加LOS血中仃sameHilliTteB:小政力号号12'J:3kfantan:shrt134srt:匚皿1111HI?w=rend现在禁忌搜索算法中候选解集合BestCandidate建立完成，我们要通过循环开始求解最优解。首先将BestCandidate中的解按照目标函数的值从小到大排序。逐个比较BestCandidate中解的目标函数值和最优值BestL的大小，若当前解目标函数值更小，就刷新最优解；若BestL更小，就继续循环，直到满足计数器的计数变量p不小于终止参数StopL,最后，建立向量ArrBe

26、stL(p),并将当前一次计数循环中最优值记录到ArrBestL向量的第p个位置。同时，每次循环后将禁忌表中所有非零的位置都减一，并将当次循环已执行过交换的两个城市计入禁忌表TabuList。下面我们来实现这个过程：(对应代码行105到153)Setp1:执行判断，如果BestCandidate(1,2)<BestL,就刷新最优值BestL为BestCandidate(1,2),同时通过前述序号i追溯S0为Candidates(BestCandidate(1,1),:)对应的解，刷新最优值BS西S0,执行Setp2;否则执行Setp6oSetp2:初始化循环变量m=1,当m不超过City

27、Num时，执行Setp3;否则执行Setp5。Setp3:初始化循环变量n=1,当n不超过CityNum时，执行Setp4;否则n值加1,返回Setp2。Setp4:执行判断，如果禁忌表TabuLis环为空，就将TabuList中每一位元素值减1,n值加1,返回Setp3循环；否则直接返回Setp3oSetp5:将当次循环已执行过交换的两个城市计入禁忌表TabuList:,并将记录值TabuLength。Setp6:初始化循环变量i=1,当i不超过BestCandidateNum时，执行判断，如果当前行的兑换城市并未出现在禁忌表中，通过前述序号i追溯S0为Candidates(BestCand

28、idate(1,1),:)对应的解。执行Setp2;否则i值加1,返回Setp6执行循环。注释：1、首先判断BestCandidate中解的目标函数值和最优值Best而大小，若BestCandidate小，就从Setp1执行，更新最优值和最优解；否则从Setp6执行，期待跳出局部最优解，得到更优值。2、Setp1中通过最好候选解集合BestCandidate第1列来取得序号i值，追溯到候选解集合Candidates中，从而得到当前最优值对应的最优解。Lg钥"殖皿匕1a川(el«拈总不(的觇如匕IF弱目标嘈口骷：累列的百匕从小到大坪,利J1刖同史，N后H率1列二配如间里L10

29、-.IL.Lridiji=(RtEtC皿；UM*以就LL3)£凯传/口出。寸(骨讯由侪躺目用循序的f氨加付晤I臣大群电；J):UMH中时上jt1排席记显车弓|向宣；)L15-a)1通，将索引号己应的匚*必如“里用住行揖出来C走总'忖弓|号聿不需应的年，国俄营短一列所表不的存言不是毛弓,"MalC幽壮idat斫SB®或声朗上樟作相当于小目标埴出1闰土的唧牛市：fif排列Ew与tCandi日hMLJS-ABeamditoetCicBestL记录当前/野第，5特为5，无声式)*帕里福坪巾的最辩解好于当前，时以下,用弟L19-Eestl=：B-=rirtCsndi

30、idate2J:?tie-32)m利LEJ-SO=Cazididartes：-Sest,CandidarteflI,i)3e5tCamdide1,.翁行第:列t£K7!hididM一中生成二口甜菊竹工口一吗刷尚层说解LZZ-|_|白七AhUitKlnLS-_JfozLS4-ifTfilHAist%njOIT一43#为心t件里:f*万旭L石-IbuLlalliiv.ti'l=tabulxsllill.1,L%=ffldL£-Hlss-endLift-Liullit'£veICkridi.dM%v3L9ntCin必缶七11.4D!*%jLtMth.A记

31、录里河el«3间串出叶巾的霞虾斛，布行于百mIf林，刚作网副dfTthiiListIEs*finddat-fi.3.P-strandidBte,41.=0%蚱科力圻二可小”的坨市二寸存余出现本蕈忌去巾£=C3ndzIeTe:CE*-st7ardidarte-:i,）P:|；Tii当7?彳理由丁勺R6卜：111t亩!%*81CEndL-dat-srznJstT（zJ疗）N£Dxnatte11axidj.da.te（ii.:>工当工W；*星?axv±idalellun.）MCati-dxda%:黑5、雏工rf厘示符MW口HvNun£Fr烹'.nmEH£ffivftCuididvti.1）*,*t?'J）KEgCEtetCir4idtU/】八：，"匚M=l+Ci.ty>iwi."forJi