算法分析讲课大纲动态规划之求矩阵连乘积问题(完整版)实用资料

算法分析讲课大纲动态规划之求矩阵连乘积问题（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）

第一小节动态规划问题算法分析讲课大纲动态规划之求矩阵连乘积问题（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）——最短路径问题一在正式提出动态规划法前我们先看一个数学例子：例1：在x+x2+x3+…+xn=a是约束条件下，求的极大值.令(0)令且可得ax=x,所以x=a/2故同理令所以ax=2x,x=a/3所以f3(a)=用数学归纳法可以证明：fn(a)=,x1=x2=x3=…=xn=证明：1：n=1…2：设fn(a)=,x1=x2=x3=…=xn=成立，则fn+1(a)=max(+fn(a-x))=max()令y=y’==所以nx=a-x,(n+1)x=ax=fn+1(a)=+n=我们刚才的解题策略是：“摸着石头过河”，f2利用f1的结果，f3又利用f2的结果。。。。。。类似于游戏中的一个勇士打败了一些敌人后得到一件武器，然后去打败另一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人。。。。。最后取得胜利。。。在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段后的行为仅依赖于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（RichardBellman）等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理”从而创建了最优化问题的一种最新的算法设计方法——动态规划。分治法和动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的.以从16个数据中找出最大者为例，说明分治法的“静”和动态规划法的“动”的区别。下面我们以具体的例子来说明如何运用动态规划算法来求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。对教材68页上的里子给予简要说明（因为书上的文字叙述有些含混晦涩，对符号的说明不清晰）y1O1OAF下面精讲一个例子21223C2G3L4Q5TC34123DHMR22134323介绍这个图的特点…..从而说明从O到A的最短路径必由7段而不是更多或更少段组成。其行进路线必然是x和y单调递增的（非严格单调）。从O(0,0)到U（4，3）点的每一条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C=35.如果采用穷举法进行搜索，需要进行35*6=210次加法，34次比较。下面我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do，以A为起点到U的最短距离为DA---,用dij表示（i,j）边的长度。显然Ds=dsu=2,Dt=dTU=3,DQ=min{2+2,5+3}=4DP=1+Ds=1+2=3DR=3+DT=3+3=6DL=min{Dlq+DQ,dLP+DP}=min{4+DQ,2+Dp}=min{4+4,2+3}=5Dk=3+Dp=3+3=6DM=min{2+DQ,4+DR}=min{2+4,4+6}=6DN=4+DR=4+6=10DF=2+DK=2+6=8DG=min{1+DK,3+DL}=min{1+6,3+5}=7DH=min{1+5,1+6}=6DJ=min{3+DM,3+DN}=min{3+6,3+10}=9DC=min{2+DF,2+DG}=min{2+8,2+7}=9DD=min{4+DG,2+DH}=min{4+7,2+6}=8DE=min{1+DH,2+DJ}=min{1+6,2+9}=7DA=min{3+DC,2+DD}=min{3+9,2+8}=10DB=min{2+DD,3+DE}==min{2+8,3+7}=10Do==min{1+DB,2+DA}=min{1+10,2+10}=11共进行了29次加法，12次比较。由Do=1+DB=11回溯，可得到最短路径为O—>B-D->HL—>P-S-UO-B-E-H-L-P-S-U推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+（m+n-2）次加法，mm次比较；而如果用穷举法，需要次加法，次比较。若m=n,动态规划法要做2n2+2n-2次加法，n2次比较，因此复杂度为O(n2);而穷举法需要次加法，次比较，>O(n2n+1)。第二小节动态规划问题——货郎担问题动态规划方法的思想---动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。货郎担问题：

---某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短？实质---从某点出发,遍历其余点,再回到原点,求总路径消耗最少的路线.[例]设共有4个要经过的点---1，2，3，4---各个点之间的花费如下：1--->2:10;1--->3:15;1--->4:20;2--->1:5;2--->3:9;2--->4:10;3--->1:6;3--->2:13;3--->4:12;4--->1:8;4--->2:8;4--->3:9;（最短路径：1--->2--->4--->3--->1））11234 2 4 5 6 7 5 8 5 8 7 8 5 3.问题的解决问题的描述:T(V1;V)---表示从V1出发,经过顶点集合V中的点各一次,再回到点V1的最短路径.动态规划函数:T(vi;V)=min{dij+T(vj;V-{vj})}(vj属于V)T(vi;V):就是从V中任何一点vi出发,经过V中的点各一次,再回到点vi的最短路径.Dij:表示从点vi出发,到某点vj的耗费(有方向性).注:这是一个递归定义的函数,关键是每次的函数T(vi;V)它所处理的点集逐渐减少.3.)实例:(如上图)求从v1出发的货郎担问题.解:T(v1;V)=T(v1;v1,v2,v3,v4) =min{d12+T(v2;v3,v4), d13+T(v3;v2,v4),d14+T(v4;v2,v3)}//实例意义:初始的货郎担问题是从点v1出发,涉及其余3点v2,v3,v4;那按照动态规划“分而治之”的思想(这里就是把问题规模缩小,而问题的数量可多一些),我们可先计算分别从v2,v3,v4出发,涉及(v2,v3,v4)三点的三条货郎担路线的路耗,再各自加上相应的dij,这样,最后就得到3个总路耗,再做一个min运算,就可求出初始问题的解.T(v2;v3,v4)=min{d23+T(v3;v4),d24+T(v4;v3)}T(v3;v4)=d34+T(v4,@)T(v4;v3)=d43+T(v3,@)T(v4,@)=d41T(v3,@)=d31T(v3;v4)=d34+d41=6+9=15T(v4;v3)=d43+d31=8+8=16T(v2;v3,v4)=min{d23+d34+d41,d24+d43+d31} =min{7+6+9,6+8+8}=22同理:T(v3;v2,v4)=min{d32+d24+d41,d34+d42+d21} =min{5+6+9,6+5+4}=15T(v4;v2,v3)=min{d42+d23+d31,d43+d32+d21} =min{5+7+8,8+5+4}=17则最后:T(v1;v1,v2,v3,v4)=min{d12+T(v2;v3,v4),d13+T(v3;v2,v4),d14+T(v4;v2,v3)}=min{2+22,5+15,8+17}=20所选的路线是:1->3->4->2->1第三小节动态规划问题——投资问题一问题描述：投资问题就是考虑如何把有限资源分配给若干个工程的问题。二给定条件：1.资源总数（设为a）2.工程个数（设为n） 3.每项工程投资的利润（不同数目的投资所获得的利润不同），用向量Gi(1≦i≦n)表示。 n三问题求解：求出一个a的分划x1,x2,…..,xn,0≦xi≦a,且∑xi≦a,使得以下式表示的利润为最大： i=1 n G(a)=∑Gi(xj)0≦xj≦a i=1 其中Gi(xj)是把资源xj分配给第I项工程能获得的最大利润。四问题分析：=1\*romani）若Gi是x的线性函数，则为线性规划问题。=2\*romanii）若Gi不是线性函数，则要用动态规划求最佳分配。用总量为a的资金在n个项目上进行投资以取得最大的利润，可以转化为下述的问题：将总量资金a分为两部分z(0≦z≦a)及a-z，分别用在第n个项目及剩下的n-1个项目上进行投资，获得的最大利润G(a)=max(第n个项目上资金量为z的利润与用a-z的资金在n-1个项目上投资的最大利润之和)。这样问题就转化为”求用a-z的资金在n-1个项目上投资的最大利润”，与我们的原问题”求总量为a的资金在n个项目上进行投资以取得最大的利润”性质完全一致，仅仅是问题的规模比原问题少了一个项目，如此将问题的规模细化下去，一直到项目数为1为止，则问题迎刃而解。我们在对原问题进行”分而治之”的过程当中，最终实现了最优化的求解。五问题解决方案： 设fi(x)：前i个项目共投资资金x所产生的最大利润；di(x)：产生fi(x)在项目i上的资金数。由上分析可给出投资问题的动态规划函数方程：f1(x)=G1(x);d1(x)=xx=0,1……afi(x)=max[Gi(z)+fi-1(x-z)]z=0,1……x;x=0,1……adi(x)=产生fi(x)的z值i=2,3…..n;六问题举例： 设有8（万元）的投资可分给3个项目，每个项目的利润函数如下表（一）所示：表（一）利润函数表x012345678G1(x)G2(x)G3(x)0515408090959810005154060707374750426404550515253解题步骤：第1步：设项目1是可用于投资的唯一项目，把x万元投资到项目1，利润为f1(x)=G1(x) 这就得到表（二）的最后一行的值，投资到项目1的最优数量为d1(x)=xx=0,1……8；第二步：设资金8万元可投资到项目1和项目2。由第1步已知任意数量的资源投资到项目1所产生的最优，所以下到各种和式中的最大值就是目前情况下的最大利润：G2(0)+f1(8)=0+100=100G2(1)+f1(7)=5+98=103 G2(2)+f1(6)=15+95=110 G2(3)+f1(5)=40+90=130 G2(4)+f1(4)=80+60=140 G2(5)+f1(3)=70+40=110 G2(6)+f1(2)=73+15=88 G2(7)+f1(1)=74+5=79 G2(8)+f1(0)=75+0=75可见将8万元投资于项目1和2，所能获得的最大利润f2(8)及投资到项目2的最优数量分别为：f2(8)=max[G2(z)+f1(8-z)]=140z=0,1……8d2(8)=4；第三步：假设以任意x(≠8)万元投资到项目1和2，对每个x值，计算从项目1和2所产生的最优利润，即：f2(x)=max[G2(z)+f1(x-z)]z=0,1……x;投资到项目2的数量为d2(x)=产生f2(x)的z值。得到所表（二）的结果。第四步：将8万元投资于3个项目，这就是原问题。则f3(8)应取下述各量的最大值：G3(0)+f2(8)=0+140=140G3(1)+f2(7)=4+120=124 G3(2)+f2(6)=26+96=126 G3(3)+f2(5)=40+90=130 G3(4)+f2(4)=45+80=125 G3(5)+f2(3)=50+40=90 G3(6)+f2(2)=51+15=66 G3(7)+f2(1)=52+5=57 G3(8)+f2(0)=53+0=53 因此将8万元以最优方式投资到3个项目时所获得的最大利润及投资到项目3的分别为：f3(8)=G3(0)+f2(8)=140d3(8)=0；表（二）向项目1，2投资所到的利润表x012345678f1(x)d1(x)f2(x)d2(x)05154080909598100012345678051540809095120140012300034因为d3(8)=0；故剩下8万元要最优的投资到项目1和2中。由表（二）易知，当项目1和2可用时，d2(8)=4表示投资到项目2的最优数量，因此项目1应投资剩下的4万元。第四小节动态规划问题——矩阵连乘积问题一、求矩阵的连乘积1、一个实际的例子（体现了乘积顺序对矩阵连乘的重要性）a)例子在讲这个问题之前先举个例子——M＝A*B*C，其中A=(aij)10*100B=(bij)100*5C=(cij)5*50根据矩阵乘法的结合律，则有M＝（A*B）*C和M＝A*（B*C）两个方案但是可以发现他们所做的乘法的次数是不相同的以M＝（A*B）*C为例令AB=M‘=(m’ij)10*5，因此m’ij＝（其中,I=1,2……10；j＝1，2……5）故计算AB共进行了10*5*100=5000次乘法M=M‘C＝（其中,I=1,2……10；j＝1，2……50）故计算M‘C共进行了10*5*50=2500次乘法总共需要5000＋2500＝7500次乘法同理，M＝A*（B*C）方案需要100*5*50+10*100*50=25000+50000=75000次乘法，两者相差近十倍！！！B）结论不难得出，矩阵相乘的结合方式对计算结果所需要的乘法操作总数有很大的影响。但是M相乘的个数增多至n个，求出所有的可能结合方式的乘法操作次数，再从中找出操作次数最小的结合方式，其工作量是惊人的@!对于n个矩阵的连乘积，设有P（n）个不同的计算次序。由于我们可以先在第k和k＋1个矩阵之间将原矩阵序列分为两个矩阵子序列，k＝1，2，……n－1。然后分别对这两个矩阵子序列完全加括号。最后对所得结果加括号，得到原矩阵序列得一种完全加括号方式。由此，可以得到关于P（n）得递归式如下：P（n）=1,n=1时P（n）＝，n>1时解此递归方程可得，P（n）＝C（n－1）其中，C（n）＝＝P（n）=P(1)P(n-1)+P(2)P(n-2)+……＋P（n－1）P（1）P（2）＝1P（n）＝这样的话这种枚举的方法实际上是不可能的。这里用动态规划的方法可以提供一种O（n3）的算法。如果可以找出乘法次数最少的的结合方式来计算的话，那么就减少了不少工作量。2、动态规划法求解的方案（还是以一个实际的例子来讲动态规划法的算法）a）算法分析举例最佳的乘积方案是（A1A2……Ai）（AI＋1AI＋2……An）则A1A2……Ai和AI＋1AI＋2……An必须达到最佳。令mij为计算乘积AIAI＋1……Aj的最少乘法数，显然有mij＝mii＝0，I，j＝1，2……n其中mik是求AIAI＋1……Ak乘积时最佳方案的乘积数目，m会＋1；j是求Ak＋1Ak＋2……Aj乘积时的最佳方案的乘积数，AIAI＋1……Ak是ri*rk+1阶矩阵，Ak＋1Ak＋2……Aj是rk+1*rj+1矩阵，rirk+1rj+1是求（AIAI＋1……Ak）（Ak＋1Ak＋2……Aj）所需的乘数法利用上式将之变为多段判决即可以计算以下4个矩阵为例A1＝30*35，A2＝35*15，A3＝15*5，A4＝5*10n＝4为例m12＝30*35*15=15750＝30*35*15=15750m23＝35*15*5=2625m34＝15*5*10=750m13＝min{m12+30*15*5,m23+30*35*5}=min{15750+2250,2625+5250}=7875m24＝min{m23+30*5*10,m34+35*15*10}=min{2625+1750,750+5250}=4375m14＝min{m12+m34+30*15*10,m24+30*35*10,m13+30*5*10}=min{15750+4500,4375+10500,7875+30*5*10}=9375故最佳方案为：（（A1（A2A3））A4）J=1234J=1234I=1I=12340m12m13m140m23m240m340B）算法时间空间复杂性分析计算顺序是沿着对角线进行的。如果编程的话，程序如下（！c＋＋程序只供参考，不作为讲课内容）voidMatrixChain(intp,intn,intn*m,int**s){for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i=i++){intj=I+r-1;m[i][j]=m[i+1][j]+P[i-1]*p[i]*p[j];s[i][j]=I;for(intk=i+1;k<j;K++){intt=m[i][k]+m[k+1][j]+p[I-1]*p[k]*p[j];if(t<m[i][j]{m[i][j]=t;s[I][j]=k;}}}}计算量主要取决于程序中对r，I，k的三重循环。循环体内的计算量为O（1），而三重循环的总次数为O(n3),由此该算法的计算时间上界为O(n3)，算法所占用的空间显然为O(n2)，显然比穷举搜索法有效的多。二、动态规划的基本要素（综合讲过的几个例子,总结算法的基本要素）从以上的最优计算次序的动态规划算法可以看出，这些算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题所具有的这两个重要的性质是该问题可用动态算法求解的基本要素。1最优子结构设计动态规划算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优解子结构性质提供了该问题可用动态规划求解的重要线索。比如，在矩阵连乘积最优解计算次序问题中，我们注意到，若A1、A2……An的最优完全加括号方式在Ak和AK＋1之间将矩阵链断开，则由此确定的子链A1、A2……Ak和AK＋1、AK＋2……An得完全加括号方式也最优。即该问题具有最优解子结构性质。在分析该问题得最优解导出得其子问题得解不是最优的，然后再设法说明在这个假设下可构造出一个比原问题最优解更好的解，从而导致矛盾。在动态规划算法中，问题的最优子结构性质使我们能够自底向上的方法递归的从子问题地最优解逐步构造出整个问题地最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。例如，在矩阵连乘积最优解次序问题中，子问题空间是输入地矩阵链的所有不同子链组成的。所有不同子链的个数为O（n2），因而子空间规模为O（n2）2重叠子问题可用动态规划算法求解问题应具备地另一基本要素是子问题地重叠性质。在用递归算法自顶向下解此问题时。每次产生地子问题并不总是新问题，有些子问题被反复计算多次。多态规划算法正式利用了这种子问题地重叠性质，对每个问题只解一次，尔后将其解保存在一个表格中，当再次需解此问题时，只是简单地用常数时间查看一下结果。通常，不同地子问题个数随输入问题地大小呈多项式增长。因此，用动态规划算法通常只需多项式时间，从而得较高得解题效率。例如，搜索法和动态规划求解矩阵连乘法（这里略去具体……）由此可以看出，在解某个问题得直接递归算法所产生得递归数中，相同的子问题反复出现，并且不同子问题的个数又相对减少时，用动态规划算法是有效的三、分治法和动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。(!!这里严求真已经提过了)若用分治法来求解这类问题，则分解得到的子问题数目太多，以至于最后解原问题需耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重计算了很多次。如果我们保存已解决子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，我们可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但他们具有相同的填表格式。!!!!!!！另外提一下（－因为第五周的课上，石浩讲分治法求矩阵乘积时说无法看出分治法体现在哪里,后来在一本书上看到如下的解释－）分治法中的矩阵乘法即Strassen矩阵乘法中。其分之思想是，将幂为2的矩阵A，B，C中每一个矩阵都分成4个大小相等的子矩阵，每个矩阵都是(n/2)*(n/2)的方阵，由此可将方程C＝AB重写为＝分治法的基本思想是将一个矩阵为n的问题分解为k个规模较小的子问题，这些子问题的解合并得到原问题的解。参考资料：《算法分析与设计》周培德机械工业出版社（教材）《计算机算法设计与分析》王晓东电子工业出版社《算法与复杂性》卢开澄高等教育出版社《计算机算法导引－设计与分析》卢开澄清华大学出版社《计算机算法基础》余祥宣崔国华邹海明华中科技大学出版社一种改进的蚁群算法求解TSP问题及实验结果分析何开成（四川大学电子信息学院四川成都610064）摘要：首先对蚁群算法的基本模型进行介绍，其次针对算法容易陷入局部最优解，在算法中加入扰动量，扩大搜索范围，从而有效控制算法陷入局部最优解。针对蚁群算法收敛速度慢，利用蚁群在最差路径上的信息，对蚁群算法信息素更新规则上进行改进。实验结果表明，提出的改进蚁群算法有效的避免程序过早的陷入局部最优解，同时提高蚁群算法的速度。关键词：蚁群算法；扰动量；算法改进；局部最优解中图分类号：TP301文献标识码：A文章编号：1671－7597（2021）0820071－021蚁群算法基本模型许多种类的蚂蚁在食物搜索过程中都存在释放信息素和信息素引导的现象。Deneubourg利用一个简单的试验模型说明了这种以自组织为基础的路径选择方式。在此模型中，蚁穴和食物之间被一座有两个等长支路的桥所分离。开始时，由于两条支路上都没有信息素分布，蚂蚁们将按照相同的概率进行路径选择。引入随机波动后，将有一条路径上通过的蚂蚁会更多一些，这将增加该路径上的信息素浓度，于是就会引导更多的蚂蚁选择这条路径。在Deneubourg设计的试验中，遗留在路径上的信息素浓度与经过的蚂蚁数量成正比，而且不考虑信息素的挥发问题。在这种简化的模型中，蚂蚁选择路径的依据就是己经过该路径的蚂蚁总数。设减和尽双为第i个蚂蚁经过桥之后，分别选择了路径A和B的蚂蚁数。则第i+l只蚂蚁选择路径A和B是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：模拟退火算法，禁忌搜索算法，Hopfield神经网络优化算法，蚁群算法，遗传算法，混合优化策略。3蚁群算法求解旅行商问题模型以求解平面上n个城市的旅行商问题为例说明蚁群系统的基本模型。旅行商问题就是给定n个城市的位置和两两城市之间的距离，要求确定一条经过各城市当一次且只有一次的最短路线。其图论描述为：给定图（V，A），其中v为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的回路，即遍历所有顶点一次且只有一次的最短回路。为了更好地说明问题，首先引入如下记号M：蚁群中蚂蚁数量；bi（t）：t时刻位于城市i的蚂蚁的个数，i和j之间的距离；nij：边（i，j）的能见度，城市i和j之1/diji，j）上的信息素轨迹强度；k在边（i，jk的转移概率，j是尚未访问的城市。每只蚂蚁都是具有如下特征的简单实体；1）在从城市派到城市j的运动过程中或是在完成一次循环后，蚂蚁在边（i，j）上释放一种物质，成为信息素轨迹；2）蚂蚁按概率选择下一个将要访问地城市，这个概率是城市间的距离和连接两城市的路径上存有的轨迹量的函数；3）为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择己经选择过的城市。=C（C为常数）。蚂蚁k（k=1，2，3，…，m）在运动过程中根据各条路径上的信息素量决定转移方向。蚁群系统使用随机比例转移规则进行状态的转移。转移规则给出了位于城市i的蚂蚁kk在城市i选择城市j的转移概率式中：allowed={0，1，k下一步允许选择的城市。经过n个时刻，当m只蚂蚁都经过一次搜索周期后，在路径上的信息素量的改变根据下面式子进行更新：上述公式对这种选择方式进行了量化。参数n决定了选择函数的非线性度，n较大时，只要一条路径上的信息素浓度稍高于另外一条路径，则下一只蚂蚁选择前一路径的概率就会更大。参数k反映了未标记路径的吸引力，k越大，则进行非随机化选择所需的信息素浓度要求越高。这种概率表达方式是实际的蚂蚁路径选择试验推导而来的。比较适合试验需要的参数设置是n=2和k=20。2旅行商问题旅行商问题（TravelingSalesmanProblem，简称TSP）即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：1）对称旅行商问题（dij=diji，j=1，2，3，…，n）；2）非对称旅行商问题（dijdiji，j=1，2，3，…，n）。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V={v1，v2，v3，…，vn}的一个访问顺序为T={t1，t2，t3，…ti，…，tn}，其中tiV（i=1，2，3，…，n），且记tn+1=t1，则旅行商问题的数学模型为：4蚁群算法的缺点旅行商问题是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决旅行商问题有着重要的理论价值和极高的实际应用价值。基于旅行商的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但蚁群算法最主要的缺点是求解速度慢。很多学者对此进行了研究，提出了多种改进方法，但不论采用那种具体方法，都可归结为通过提高蚂蚁每次周游的质量来提高蚁群算法的求解速度。之所以都采用这种方法，就是由于基本蚁群算法求解速度慢的一个重要原因是蚂蚁每次周游得到的信息没有被充分地利用起来。这主要体现在各条路径上的信息量更新规则上。由上面对蚁群算法的介绍可知，蚂蚁在周游过程中，会使它经过的路径上的信息量减少，同时，增强蚂蚁周游的信息没有充分地利用起来。实际上，每只蚂蚁周游的信息也是很有用的。蚁群算法求解速度慢的另一个重要原因是蚂蚁获取的信息与实际情况会有一些差异，这会对蚂蚁产生误导，而蚁群算法排除误导的速度较慢。蚁群算法求解过程是一个正反馈过程。蚂蚁的第一次周游时，由于各路径上的信息量相同，蚂蚁选择城市是随机的。这一次选择会使一些不是最优的路径上的信息量偏大。以后的蚂蚁就会根据这个不正确的信息选择以后的路径，这些不是最优的路径被蚂蚁选择的可能性将很大，这会导致这些较差的路径上的信息量不断增大。经过这样一个正反馈过程，路径上的信息量就具有了很大的误差而导致算法难以找到较优解。蚁群算法在一定程度上可通过信息量的挥发过程以及蚂蚁周游的下一个城市的随机选择过程来排除具有较大误差的信息。但是，信息量挥发过程是缓慢的。而且在挥发过程中，很可能会有许多蚂蚁再次经过这条路径，并有可能使这条路径上的信息量增大。一次通过选择城市随机性来削减误差仅在算法刚运行不久，各条路径上的信息量相差不是很大的情况下才可能起到一定作用。由于这两种排除误差的方法均不能较快地排除误差，也导致了蚁群算法求解速度慢，并且增加了算法陷入局部最优的可能性。5蚁群算法的改进1）加入扰动的改进针对蚁群算法容易陷入局部最优解，这里引入参数q0，蚂蚁k从i城市选择下一个城市j时，首先产生一个[0，l]均匀分布的随机数q，当q小于常数q0时，蚂蚁根据先验知识即：能见度选择下一个城市。公式（1）改进为：③依状态转移规则选择下一结点；④重复步骤③，直至每只蚂蚁均形成一条完整路径，即遍历所有结点；⑤更新最优解；⑥进行信息素更新；⑦判断是否满足算法终止条件：若满足，则算法终止；否则，转步骤②。6实验结果及分析本文利用MATLAB仿真平台对典型的旅行商问题OdysseyofUlysses进行进行了仿真实验，已知OdysseyofUlysses问题的最优解是75.6651。我们分别取NC=10，m=50，a=l=2，p=0.3，Q=1，W=4，q0=0.1。a=l；NC=50，m=50，a=l=2，p=0.3，Q=1，W=4，q0=0.1，。a=l；NC=100，m=50，a=l，p=0.3，Q=1，W=4，q0=0.1a=l，原始蚁群算法与改进蚁群算法分别周游10次，50次，100次所得到的最优解对比如下表：加入扰动参数q，每隔一定时间，蚂蚁在选择下一个城市时，只根据能见度选择，这样可以排除因为蚁群算法正反馈导致的较大误差解，扩大了解的搜索范围，有效避免了蚁群算法过早陷入局部最优解。2）信息素更新规则的改进蚁群算法最主要的缺点是求解速度慢。由于基本蚁群算法求解速度慢的一个重要原因是蚂蚁每次周游得到的信息没有被充分地利用起来。这主要体现在各条路径上的信息量更新规则上。由上面对蚁群算法的介绍可知，蚂蚁在周游过程中，会使它经过的路径上的信息量减少，同时，增强蚂蚁在最短路径上的信息。这一过程利用了蚂蚁周游最短路径的信息。但其它蚂蚁周游的信息没有充分地利用起来。实际上，每只蚂蚁周游的信息也是很有用的。本文充分利用蚂蚁在最差路径上的信息对蚁群算法的信息素更新规则做了改进，在规则中引入了最差路径信息量减少参数w，改进后公式（2）调整为：从实验结果对比来看，改进后的蚁群算法在100次周游下已经找到问题的最优解，而原始的蚁群算法虽然在加大周游次数可以逐步接近最优解，但是他的收敛性不好，容易陷入局部最优解，所以，加大周游次数对求解旅行商最优解的意义不大。而改进的蚁群算法正是对原始蚁群算法的收敛速度慢，容易陷入最优解这两个方面进行了改进，改进后的蚁群算法能够扩大最优解的搜索范围，有效地避免算法过早陷入局部最优的情况的出现。实验结果证明：改进后的蚁群算法无论是最优解的方面还是在收敛速度方面都比原始蚁群算法要好。7结论蚁群算法最大的缺点就是收敛速度慢，容易陷入最优解，这也是限制它应用的最大瓶颈。本文针对蚁群算法收敛速度慢、容易过早陷入局部最优的缺点提出了一种新的改进算法。实验证明了这种改进的有效性和正确性。表示挥发系数，Q为信息量增加常数，w为信息量减少常数。3）算法实现MATLAB是一个可视化的计算程序，被广泛地使用于从个人计算机到超级计算机范围内的各种计算机上。它包括命令控制、可编程，有上百个预先定义好的命令和函数。这些函数能通过用户自定义函数进一步扩展。MATLAB有许多强有力的命令。正因为MATLAB具有这么多的优点，特别是在数值计算方面的独到性，本文利用MATLAB平台进行仿真实验。其程序步骤如下：①初始化信息素分布；②将每只蚂蚁随机置于任一个结点上；参考文献：[1]吴斌、傅伟鹏、郑毅、刘少辉，史忠植一种基于群体智能的Web文档聚类算法计算，机研究与发展，2021，39（11）：1429～1435.[2]吴启迪、汪镭，智能蚁群算法及应用[M].上海：上海科技教育出版社，2021.4.[3]黎锁平、张秀媛、杨海波，人工蚁群算法理论及其在经典TSP问题中的实现[J].交通运输系统工程与信息，2007，2（2）：73～76.一种基于动态多维矩阵编码的组卷遗传算法王力1陈郁明2(1.贵州大学电子科学与信息技术学院,贵州贵阳550003(2.贵州大学计算机科学与技术学院,贵州贵阳550003摘要:提出动态多维矩阵表示解(染体色的遗传算法,并针对这种染色体在交叉、变异和选择等遗传算子的实现进行了研究。运行结果表明,算法运行效率较好,有很好的实用价值。关键词:多维矩阵染色体;遗传算法;自动组卷中图法分类号:TP399文献标识码:BAGeneticAlgorithmbased-ondynamicmultipledimensionmatrixcodingWangLi1,CHENYuming2(1.SchoolofElectronicScienceandInformationTechnologyGuizhouUniversityGuiyang5500032.SchoolofComputerScienceandTechnology,Guizhou,Guiyang550003Abstract:Thegeneticalgorithmwasproposedbyusingmultipledynamicdimensionmatrixestorepresentsolution(chromosome.Andrealizationofgeneticoperatorssuchascrossover、mutationandselection,andsoonwasexplored.Theoperationresultrevealsthatthealgorithmhasabetterefficiencyandthereforeitisofbetterpracticalvalue.Keywords:dynamicmultipledimensionchromosome;geneticalgorithm;automaticgeneratingtestpaper1引言遗传算法(GeneticAlgorithm,简称GA是一种演化算法,从提出至今不过50年时间。与爬山算法、模拟退火算法和禁忌算法等一样都属启发式搜索算法[1]。目前遗传算法在函数优化、组合优化、生产调度、机器人学、图像处理[4][5]和自动编程等诸多领域已经得到成功应用。在教育领域中,有大量的研究者把遗传算法用于自动排课、自动组卷[2][3]、学生成绩数据挖掘分析等,并且取得成功。很多自动组卷遗传算法都基于线性二进制串[2]或整数编码[3]实现染色体,本文先介绍了三维矩阵试卷模型,然后提出了一种新的编码方式——动态多维矩阵表示GA的解(染色体,以及交叉算子、变异算子和选择算子的实现。2试卷模型构成试卷是长度为n的一维向量(123,,,...,nttttπ,其中ti是试卷的第i道题在试题库中的编号,并且每道题目具有题型、知识点、分数、难度系数等多个属性。向量π中,按题型可把题目分为m类,按照知识点也可把题目分成k类。因此,可以把试卷看成一个三维向量Amnk,m表示题型数量,n表示知识点数量,k为某题型中每个知识点试题数,题库中不同的题型和知识点k值不同。矩阵中的元素aijr表示题型i及知识点j的第r道题的题目编号。设Q[1..n,1..m,1..k]中元素qijr保存题目aijr的分数,设x[1..n,1..m,1..k]为一标志数组,试卷满足如下公式:⎩⎨⎧=未被选中题目被选中,题目ijrijra,0a1],,[rjiX∑∑∑====minjkrrjiQrjixZ111],,[],,[n为题型数,m为知识点数,k为某题型和知识点对应的题目数。3组卷遗传算法3.1动态多维矩阵染色体数据结构编码是运用GA时要解决的首要问题,也是设计GA的一个关键步骤。针对具体应用问题,如何设计一种完美的编码方案一直是遗传算法的应用难点之一,也是遗传算法的一个重要研究方向。考虑使用三维矩阵(设为Cmnk作为染色体。其中,题型数为m,知识点数为,某题型和知识点题目数为k。设预组试卷只有选择题、填空题和解答题3类题型,涉及4个知识点,图2.1为该染色体对应的“动态三维矩阵”。00第二面:填空题⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛00001001101第三面:解答题⎟⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎜⎝⎛010*********图3.1染色体构成示例以第一面选择题为例,第一行表示题库中知“识点1”满足条件的题目只有2道,并且没有一道被选中,第二行表示“知识点2”满足条件的题目数有4道,但只有第1道被选到试卷中。由于每道题型、每个知识点的题目数不一样多,有时可能没有题目,因此在设计时用动态三维数组实现染色体。Chro:ArrayofArrayofArrayofbyte;本文所提的“动态三维矩阵”并不是传统意义的三维矩阵,实际上是类似于三维矩阵的特殊的数据结构。3.2染色体适应度函数适应度用于表示解的质量,GA通过计算种群的每个个体适应度,然后根据适应度值的大小确定个体与解的逼近程度。为了得到个体适应度,必须构造相应适应度函数,但是适应度函数并不是显而易见的或由问题自动给出的,而是与问题的目标相关的,一个解如果完全满足目标,它就应该有最好的适应值。自动组卷的目标就是要使总分、题目数、难度系数等每项组卷指标的误差ξi最小,可以对每项指标设定一个权值Wi,表示对试卷的影响程度的估计。个体i适应度函数可表示为:∑==niiiWif1*(ξ,n为组卷指标数f(i的值越小表明个体i适应环境越强。因此,自动组卷问题变成了对函数f(i求极小值的问题。为了方便,把求极小值问题变成求极大值问题,函数变为:∑=−=niiiWCif1*(ξ,C为一常数,保证f(i为大于零的正数3.3选择算子设计采用轮盘赌选择算法,即某个染色是否被选中根据指针在轮盘上拔动位置来选择。设每个个体的适应度值对应轮盘的每一格,可以知道轮盘上格子距离最大的一格,即表示适应度值大的个体,其被选中的概率也大。个体在轮盘中格子大小(概率按下式计算:∑==NjijfifP1((,N为种群大小,且11=∑=NiiPPi表示个体i被选中概率,被选中的概率越大,则在轮盘赌中,赌赢的概率越大。为了模拟轮盘,还要计算每个个体的累积概率,公式如下:∑−=iiipiFF1][由计算机产生一个[0,1]之间的随机数r,该数对应轮盘指针停放的位置,如果[](1rFFkkN<=<=<=时,表示选中个体k进入下一代。为了确保最优个体能进入下一代,在进化过程中,始终保存最优个体,如果最优个体的适应度值小于本代最优个体,则把最优个体代替本代最差个体,否则把本代最优个体当作最优个体进入下一代。3.4交叉算子设计对于N个体的种群,以概率Pc(<0.95随机地选择两个个体进行交叉,方法是对三维“矩阵”的面(题型维或面中的行(知识点维进行整体交叉,随机生成两个随机数(,1,1uvumvn<=<=<=<=,分别表示对两个个体的第u面到最后一面进行交叉,根据需要,也可根据指定的条件再对该面的第v行进行交叉。交叉结果保证了每种题型的题目数不发生变化,知识点的题目数也不发生变化。3.5变异算子设计变异算子可以增加种群的多样性,对于防止种群的早熟有着极其重要的作用。在变异概率Pm(<=0.2作用下,利用随机函数产生三个整数(,1,1uvumvn<<=<=<=和(1wwk<<=,表示在第u面第v位实施变异操作,即把0变1或把1变成0,由于操作将导致题目数增1或少1的情况发生,同时把第u面第w位取反,要注意的是第v,第w位异或结果必须为1。当以满足分数优先为前提进行自动组卷操作时,只需要简单地把变异位取反即可。3.6停机条件