算法分析講課大綱動態(tài)規(guī)劃之求矩陣連乘積問題(完整版)實(shí)用資料

算法分析講課大綱動態(tài)規(guī)劃之求矩陣連乘積問題（完整版）實(shí)用資料(可以直接使用，可編輯完整版實(shí)用資料，歡迎下載）

第一小節(jié)動態(tài)規(guī)劃問題算法分析講課大綱動態(tài)規(guī)劃之求矩陣連乘積問題（完整版）實(shí)用資料(可以直接使用，可編輯完整版實(shí)用資料，歡迎下載）——最短路徑問題一在正式提出動態(tài)規(guī)劃法前我們先看一個數(shù)學(xué)例子：例1：在x+x2+x3+…+xn=a是約束條件下，求的極大值.令(0)令且可得ax=x,所以x=a/2故同理令所以ax=2x,x=a/3所以f3(a)=用數(shù)學(xué)歸納法可以證明：fn(a)=,x1=x2=x3=…=xn=證明：1：n=1…2：設(shè)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的結(jié)果，f3又利用f2的結(jié)果。。。。。。類似于游戲中的一個勇士打敗了一些敵人后得到一件武器，然后去打敗另一個強(qiáng)大一些的對手，得到一件更好的武器，接著打敗更強(qiáng)大的敵人。。。。。最后取得勝利。。。在實(shí)際生活中，有這么一類問題，它們的活動過程可分為若干個階段，而且在任一階段后的行為僅依賴于第I階段的過程狀態(tài)，而與I階段之前的過程如何達(dá)到這種過程如何達(dá)到這種狀態(tài)的方式無關(guān)，這樣的過程就構(gòu)成了一個多階段決策過程。在50年代，貝爾曼（RichardBellman）等人根據(jù)這類問題的多階段決策的特性，提出了解決問題的“最優(yōu)性原理”從而創(chuàng)建了最優(yōu)化問題的一種最新的算法設(shè)計(jì)方法——動態(tài)規(guī)劃。分治法和動態(tài)規(guī)劃法的比較動態(tài)規(guī)劃算法與分治法類似，其根本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解，與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的.以從16個數(shù)據(jù)中找出最大者為例，說明分治法的“靜”和動態(tài)規(guī)劃法的“動”的區(qū)別。下面我們以具體的例子來說明如何運(yùn)用動態(tài)規(guī)劃算法來求解問題，并分析可用動態(tài)規(guī)劃算法解的問題的所應(yīng)具備的一般特征。對教材68頁上的里子給予簡要說明（因?yàn)闀系奈淖謹(jǐn)⑹鲇行┖旎逎?，對符號的說明不清晰）y1O1OAF下面精講一個例子21223C2G3L4Q5TC34123DHMR22134323介紹這個圖的特點(diǎn)…..從而說明從O到A的最短路徑必由7段而不是更多或更少段組成。其行進(jìn)路線必然是x和y單調(diào)遞增的（非嚴(yán)格單調(diào)）。從O(0,0)到U（4，3）點(diǎn)的每一條路徑對應(yīng)于由4個x上的和3個y上的字符構(gòu)成的字符串，這種字符串的數(shù)目為C=35.如果采用窮舉法進(jìn)行搜索，需要進(jìn)行35*6=210次加法，34次比較。下面我們采用動態(tài)規(guī)劃法來解決這一問題。令O為起點(diǎn)到U的最短距離為Do，以A為起點(diǎn)到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共進(jìn)行了29次加法，12次比較。由Do=1+DB=11回溯，可得到最短路徑為O—>B-D->HL—>P-S-UO-B-E-H-L-P-S-U推廣到x軸m段y軸n段的情形：用動態(tài)規(guī)劃法需要做2mn+（m+n-2）次加法，mm次比較；而如果用窮舉法，需要次加法，次比較。若m=n,動態(tài)規(guī)劃法要做2n2+2n-2次加法，n2次比較，因此復(fù)雜度為O(n2);而窮舉法需要次加法，次比較，>O(n2n+1)。第二小節(jié)動態(tài)規(guī)劃問題——貨郎擔(dān)問題動態(tài)規(guī)劃方法的思想---動態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。貨郎擔(dān)問題：

---某售貨員要到若干個村莊售貨，各村莊之間的路程是已知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個村莊售一次貨然后返回商店，問他應(yīng)選擇一條什么路線才能使所走的總路程最短？實(shí)質(zhì)---從某點(diǎn)出發(fā),遍歷其余點(diǎn),再回到原點(diǎn),求總路徑消耗最少的路線.[例]設(shè)共有4個要經(jīng)過的點(diǎn)---1，2，3，4---各個點(diǎn)之間的花費(fèi)如下：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出發(fā),經(jīng)過頂點(diǎn)集合V中的點(diǎn)各一次,再回到點(diǎn)V1的最短路徑.動態(tài)規(guī)劃函數(shù):T(vi;V)=min{dij+T(vj;V-{vj})}(vj屬于V)T(vi;V):就是從V中任何一點(diǎn)vi出發(fā),經(jīng)過V中的點(diǎn)各一次,再回到點(diǎn)vi的最短路徑.Dij:表示從點(diǎn)vi出發(fā),到某點(diǎn)vj的耗費(fèi)(有方向性).注:這是一個遞歸定義的函數(shù),關(guān)鍵是每次的函數(shù)T(vi;V)它所處理的點(diǎn)集逐漸減少.3.)實(shí)例:(如上圖)求從v1出發(fā)的貨郎擔(dān)問題.解: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)}//實(shí)例意義:初始的貨郎擔(dān)問題是從點(diǎn)v1出發(fā),涉及其余3點(diǎn)v2,v3,v4;那按照動態(tài)規(guī)劃“分而治之”的思想(這里就是把問題規(guī)?？s小,而問題的數(shù)量可多一些),我們可先計(jì)算分別從v2,v3,v4出發(fā),涉及(v2,v3,v4)三點(diǎn)的三條貨郎擔(dān)路線的路耗,再各自加上相應(yīng)的dij,這樣,最后就得到3個總路耗,再做一個min運(yùn)算,就可求出初始問題的解.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第三小節(jié)動態(tài)規(guī)劃問題——投資問題一問題描述：投資問題就是考慮如何把有限資源分配給若干個工程的問題。二給定條件：1.資源總數(shù)（設(shè)為a）2.工程個數(shù)（設(shè)為n） 3.每項(xiàng)工程投資的利潤（不同數(shù)目的投資所獲得的利潤不同），用向量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項(xiàng)工程能獲得的最大利潤。四問題分析：=1\*romani）若Gi是x的線性函數(shù)，則為線性規(guī)劃問題。=2\*romanii）若Gi不是線性函數(shù)，則要用動態(tài)規(guī)劃求最佳分配。用總量為a的資金在n個項(xiàng)目上進(jìn)行投資以取得最大的利潤，可以轉(zhuǎn)化為下述的問題：將總量資金a分為兩部分z(0≦z≦a)及a-z，分別用在第n個項(xiàng)目及剩下的n-1個項(xiàng)目上進(jìn)行投資，獲得的最大利潤G(a)=max(第n個項(xiàng)目上資金量為z的利潤與用a-z的資金在n-1個項(xiàng)目上投資的最大利潤之和)。這樣問題就轉(zhuǎn)化為”求用a-z的資金在n-1個項(xiàng)目上投資的最大利潤”，與我們的原問題”求總量為a的資金在n個項(xiàng)目上進(jìn)行投資以取得最大的利潤”性質(zhì)完全一致，僅僅是問題的規(guī)模比原問題少了一個項(xiàng)目，如此將問題的規(guī)模細(xì)化下去，一直到項(xiàng)目數(shù)為1為止，則問題迎刃而解。我們在對原問題進(jìn)行”分而治之”的過程當(dāng)中，最終實(shí)現(xiàn)了最優(yōu)化的求解。五問題解決方案： 設(shè)fi(x)：前i個項(xiàng)目共投資資金x所產(chǎn)生的最大利潤；di(x)：產(chǎn)生fi(x)在項(xiàng)目i上的資金數(shù)。由上分析可給出投資問題的動態(tài)規(guī)劃函數(shù)方程：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)=產(chǎn)生fi(x)的z值i=2,3…..n;六問題舉例： 設(shè)有8（萬元）的投資可分給3個項(xiàng)目，每個項(xiàng)目的利潤函數(shù)如下表（一）所示：表（一）利潤函數(shù)表x012345678G1(x)G2(x)G3(x)0515408090959810005154060707374750426404550515253解題步驟：第1步：設(shè)項(xiàng)目1是可用于投資的唯一項(xiàng)目，把x萬元投資到項(xiàng)目1，利潤為f1(x)=G1(x) 這就得到表（二）的最后一行的值，投資到項(xiàng)目1的最優(yōu)數(shù)量為d1(x)=xx=0,1……8；第二步：設(shè)資金8萬元可投資到項(xiàng)目1和項(xiàng)目2。由第1步已知任意數(shù)量的資源投資到項(xiàng)目1所產(chǎn)生的最優(yōu)，所以下到各種和式中的最大值就是目前情況下的最大利潤：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萬元投資于項(xiàng)目1和2，所能獲得的最大利潤f2(8)及投資到項(xiàng)目2的最優(yōu)數(shù)量分別為：f2(8)=max[G2(z)+f1(8-z)]=140z=0,1……8d2(8)=4；第三步：假設(shè)以任意x(≠8)萬元投資到項(xiàng)目1和2，對每個x值，計(jì)算從項(xiàng)目1和2所產(chǎn)生的最優(yōu)利潤，即：f2(x)=max[G2(z)+f1(x-z)]z=0,1……x;投資到項(xiàng)目2的數(shù)量為d2(x)=產(chǎn)生f2(x)的z值。得到所表（二）的結(jié)果。第四步：將8萬元投資于3個項(xiàng)目，這就是原問題。則f3(8)應(yīng)取下述各量的最大值：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萬元以最優(yōu)方式投資到3個項(xiàng)目時所獲得的最大利潤及投資到項(xiàng)目3的分別為：f3(8)=G3(0)+f2(8)=140d3(8)=0；表（二）向項(xiàng)目1，2投資所到的利潤表x012345678f1(x)d1(x)f2(x)d2(x)05154080909598100012345678051540809095120140012300034因?yàn)閐3(8)=0；故剩下8萬元要最優(yōu)的投資到項(xiàng)目1和2中。由表（二）易知，當(dāng)項(xiàng)目1和2可用時，d2(8)=4表示投資到項(xiàng)目2的最優(yōu)數(shù)量，因此項(xiàng)目1應(yīng)投資剩下的4萬元。第四小節(jié)動態(tài)規(guī)劃問題——矩陣連乘積問題一、求矩陣的連乘積1、一個實(shí)際的例子（體現(xiàn)了乘積順序?qū)仃囘B乘的重要性）a)例子在講這個問題之前先舉個例子——M＝A*B*C，其中A=(aij)10*100B=(bij)100*5C=(cij)5*50根據(jù)矩陣乘法的結(jié)合律，則有M＝（A*B）*C和M＝A*（B*C）兩個方案但是可以發(fā)現(xiàn)他們所做的乘法的次數(shù)是不相同的以M＝（A*B）*C為例令A(yù)B=M‘=(m’ij)10*5，因此m’ij＝（其中,I=1,2……10；j＝1，2……5）故計(jì)算AB共進(jìn)行了10*5*100=5000次乘法M=M‘C＝（其中,I=1,2……10；j＝1，2……50）故計(jì)算M‘C共進(jìn)行了10*5*50=2500次乘法總共需要5000＋2500＝7500次乘法同理，M＝A*（B*C）方案需要100*5*50+10*100*50=25000+50000=75000次乘法，兩者相差近十倍！??！B）結(jié)論不難得出，矩陣相乘的結(jié)合方式對計(jì)算結(jié)果所需要的乘法操作總數(shù)有很大的影響。但是M相乘的個數(shù)增多至n個，求出所有的可能結(jié)合方式的乘法操作次數(shù)，再從中找出操作次數(shù)最小的結(jié)合方式，其工作量是驚人的@!對于n個矩陣的連乘積，設(shè)有P（n）個不同的計(jì)算次序。由于我們可以先在第k和k＋1個矩陣之間將原矩陣序列分為兩個矩陣子序列，k＝1，2，……n－1。然后分別對這兩個矩陣子序列完全加括號。最后對所得結(jié)果加括號，得到原矩陣序列得一種完全加括號方式。由此，可以得到關(guān)于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）＝這樣的話這種枚舉的方法實(shí)際上是不可能的。這里用動態(tài)規(guī)劃的方法可以提供一種O（n3）的算法。如果可以找出乘法次數(shù)最少的的結(jié)合方式來計(jì)算的話，那么就減少了不少工作量。2、動態(tài)規(guī)劃法求解的方案（還是以一個實(shí)際的例子來講動態(tài)規(guī)劃法的算法）a）算法分析舉例最佳的乘積方案是（A1A2……Ai）（AI＋1AI＋2……An）則A1A2……Ai和AI＋1AI＋2……An必須達(dá)到最佳。令mij為計(jì)算乘積AIAI＋1……Aj的最少乘法數(shù)，顯然有mij＝mii＝0，I，j＝1，2……n其中mik是求AIAI＋1……Ak乘積時最佳方案的乘積數(shù)目，m會＋1；j是求Ak＋1Ak＋2……Aj乘積時的最佳方案的乘積數(shù)，AIAI＋1……Ak是ri*rk+1階矩陣，Ak＋1Ak＋2……Aj是rk+1*rj+1矩陣，rirk+1rj+1是求（AIAI＋1……Ak）（Ak＋1Ak＋2……Aj）所需的乘數(shù)法利用上式將之變?yōu)槎喽闻袥Q即可以計(jì)算以下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）算法時間空間復(fù)雜性分析計(jì)算順序是沿著對角線進(jìn)行的。如果編程的話，程序如下（！c＋＋程序只供參考，不作為講課內(nèi)容）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;}}}}計(jì)算量主要取決于程序中對r，I，k的三重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O（1），而三重循環(huán)的總次數(shù)為O(n3),由此該算法的計(jì)算時間上界為O(n3)，算法所占用的空間顯然為O(n2)，顯然比窮舉搜索法有效的多。二、動態(tài)規(guī)劃的基本要素（綜合講過的幾個例子,總結(jié)算法的基本要素）從以上的最優(yōu)計(jì)算次序的動態(tài)規(guī)劃算法可以看出，這些算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。從一般意義上講，問題所具有的這兩個重要的性質(zhì)是該問題可用動態(tài)算法求解的基本要素。1最優(yōu)子結(jié)構(gòu)設(shè)計(jì)動態(tài)規(guī)劃算法的第一步通常是要刻畫最優(yōu)解的結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)解子結(jié)構(gòu)性質(zhì)提供了該問題可用動態(tài)規(guī)劃求解的重要線索。比如，在矩陣連乘積最優(yōu)解計(jì)算次序問題中，我們注意到，若A1、A2……An的最優(yōu)完全加括號方式在Ak和AK＋1之間將矩陣鏈斷開，則由此確定的子鏈A1、A2……Ak和AK＋1、AK＋2……An得完全加括號方式也最優(yōu)。即該問題具有最優(yōu)解子結(jié)構(gòu)性質(zhì)。在分析該問題得最優(yōu)解導(dǎo)出得其子問題得解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出一個比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。在動態(tài)規(guī)劃算法中，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠自底向上的方法遞歸的從子問題地最優(yōu)解逐步構(gòu)造出整個問題地最優(yōu)解。同時，它也使我們能在相對小的子問題空間中考慮問題。例如，在矩陣連乘積最優(yōu)解次序問題中，子問題空間是輸入地矩陣鏈的所有不同子鏈組成的。所有不同子鏈的個數(shù)為O（n2），因而子空間規(guī)模為O（n2）2重疊子問題可用動態(tài)規(guī)劃算法求解問題應(yīng)具備地另一基本要素是子問題地重疊性質(zhì)。在用遞歸算法自頂向下解此問題時。每次產(chǎn)生地子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。多態(tài)規(guī)劃算法正式利用了這種子問題地重疊性質(zhì)，對每個問題只解一次，爾后將其解保存在一個表格中，當(dāng)再次需解此問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常，不同地子問題個數(shù)隨輸入問題地大小呈多項(xiàng)式增長。因此，用動態(tài)規(guī)劃算法通常只需多項(xiàng)式時間，從而得較高得解題效率。例如，搜索法和動態(tài)規(guī)劃求解矩陣連乘法（這里略去具體……）由此可以看出，在解某個問題得直接遞歸算法所產(chǎn)生得遞歸數(shù)中，相同的子問題反復(fù)出現(xiàn)，并且不同子問題的個數(shù)又相對減少時，用動態(tài)規(guī)劃算法是有效的三、分治法和動態(tài)規(guī)劃法的比較動態(tài)規(guī)劃算法與分治法類似，其根本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解，與分治法不同的是，適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。(!!這里嚴(yán)求真已經(jīng)提過了)若用分治法來求解這類問題，則分解得到的子問題數(shù)目太多，以至于最后解原問題需耗費(fèi)指數(shù)時間。然而，不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時，有些子問題被重計(jì)算了很多次。如果我們保存已解決子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時間的算法。為了達(dá)到這個目的，我們可以用一個表來記錄所有已解決的子問題的答案。不管該子問題以后是否被用到，只要被計(jì)算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但他們具有相同的填表格式。!!!!!!！另外提一下（－因?yàn)榈谖逯艿恼n上，石浩講分治法求矩陣乘積時說無法看出分治法體現(xiàn)在哪里,后來在一本書上看到如下的解釋－）分治法中的矩陣乘法即Strassen矩陣乘法中。其分之思想是，將冪為2的矩陣A，B，C中每一個矩陣都分成4個大小相等的子矩陣，每個矩陣都是(n/2)*(n/2)的方陣，由此可將方程C＝AB重寫為＝分治法的基本思想是將一個矩陣為n的問題分解為k個規(guī)模較小的子問題，這些子問題的解合并得到原問題的解。參考資料：《算法分析與設(shè)計(jì)》周培德機(jī)械工業(yè)出版社（教材）《計(jì)算機(jī)算法設(shè)計(jì)與分析》王曉東電子工業(yè)出版社《算法與復(fù)雜性》盧開澄高等教育出版社《計(jì)算機(jī)算法導(dǎo)引－設(shè)計(jì)與分析》盧開澄清華大學(xué)出版社《計(jì)算機(jī)算法基礎(chǔ)》余祥宣崔國華鄒海明華中科技大學(xué)出版社一種改進(jìn)的蟻群算法求解TSP問題及實(shí)驗(yàn)結(jié)果分析何開成（四川大學(xué)電子信息學(xué)院四川成都610064）摘要：首先對蟻群算法的基本模型進(jìn)行介紹，其次針對算法容易陷入局部最優(yōu)解，在算法中加入擾動量，擴(kuò)大搜索范圍，從而有效控制算法陷入局部最優(yōu)解。針對蟻群算法收斂速度慢，利用蟻群在最差路徑上的信息，對蟻群算法信息素更新規(guī)則上進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，提出的改進(jìn)蟻群算法有效的避免程序過早的陷入局部最優(yōu)解，同時提高蟻群算法的速度。關(guān)鍵詞：蟻群算法；擾動量；算法改進(jìn)；局部最優(yōu)解中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A文章編號：1671－7597（2021）0820071－021蟻群算法基本模型許多種類的螞蟻在食物搜索過程中都存在釋放信息素和信息素引導(dǎo)的現(xiàn)象。Deneubourg利用一個簡單的試驗(yàn)?zāi)Ｐ驼f明了這種以自組織為基礎(chǔ)的路徑選擇方式。在此模型中，蟻穴和食物之間被一座有兩個等長支路的橋所分離。開始時，由于兩條支路上都沒有信息素分布，螞蟻們將按照相同的概率進(jìn)行路徑選擇。引入隨機(jī)波動后，將有一條路徑上通過的螞蟻會更多一些，這將增加該路徑上的信息素濃度，于是就會引導(dǎo)更多的螞蟻選擇這條路徑。在Deneubourg設(shè)計(jì)的試驗(yàn)中，遺留在路徑上的信息素濃度與經(jīng)過的螞蟻數(shù)量成正比，而且不考慮信息素的揮發(fā)問題。在這種簡化的模型中，螞蟻選擇路徑的依據(jù)就是己經(jīng)過該路徑的螞蟻總數(shù)。設(shè)減和盡雙為第i個螞蟻經(jīng)過橋之后，分別選擇了路徑A和B的螞蟻數(shù)。則第i+l只螞蟻選擇路徑A和B是，由于構(gòu)造型算法優(yōu)化質(zhì)量較差，迄今為止已開發(fā)了許多性能較好的改進(jìn)型搜索算法，主要有：模擬退火算法，禁忌搜索算法，Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化算法，蟻群算法，遺傳算法，混合優(yōu)化策略。3蟻群算法求解旅行商問題模型以求解平面上n個城市的旅行商問題為例說明蟻群系統(tǒng)的基本模型。旅行商問題就是給定n個城市的位置和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當(dāng)一次且只有一次的最短路線。其圖論描述為：給定圖（V，A），其中v為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的連接距離，要求確定一條長度最短的回路，即遍歷所有頂點(diǎn)一次且只有一次的最短回路。為了更好地說明問題，首先引入如下記號M：蟻群中螞蟻數(shù)量；bi（t）：t時刻位于城市i的螞蟻的個數(shù)，i和j之間的距離；nij：邊（i，j）的能見度，城市i和j之1/diji，j）上的信息素軌跡強(qiáng)度；k在邊（i，jk的轉(zhuǎn)移概率，j是尚未訪問的城市。每只螞蟻都是具有如下特征的簡單實(shí)體；1）在從城市派到城市j的運(yùn)動過程中或是在完成一次循環(huán)后，螞蟻在邊（i，j）上釋放一種物質(zhì)，成為信息素軌跡；2）螞蟻按概率選擇下一個將要訪問地城市，這個概率是城市間的距離和連接兩城市的路徑上存有的軌跡量的函數(shù)；3）為了滿足問題的約束條件，在完成一次循環(huán)以前，不允許螞蟻選擇己經(jīng)選擇過的城市。=C（C為常數(shù)）。螞蟻k（k=1，2，3，…，m）在運(yùn)動過程中根據(jù)各條路徑上的信息素量決定轉(zhuǎn)移方向。蟻群系統(tǒng)使用隨機(jī)比例轉(zhuǎn)移規(guī)則進(jìn)行狀態(tài)的轉(zhuǎn)移。轉(zhuǎn)移規(guī)則給出了位于城市i的螞蟻kk在城市i選擇城市j的轉(zhuǎn)移概率式中：allowed={0，1，k下一步允許選擇的城市。經(jīng)過n個時刻，當(dāng)m只螞蟻都經(jīng)過一次搜索周期后，在路徑上的信息素量的改變根據(jù)下面式子進(jìn)行更新：上述公式對這種選擇方式進(jìn)行了量化。參數(shù)n決定了選擇函數(shù)的非線性度，n較大時，只要一條路徑上的信息素濃度稍高于另外一條路徑，則下一只螞蟻選擇前一路徑的概率就會更大。參數(shù)k反映了未標(biāo)記路徑的吸引力，k越大，則進(jìn)行非隨機(jī)化選擇所需的信息素濃度要求越高。這種概率表達(dá)方式是實(shí)際的螞蟻路徑選擇試驗(yàn)推導(dǎo)而來的。比較適合試驗(yàn)需要的參數(shù)設(shè)置是n=2和k=20。2旅行商問題旅行商問題（TravelingSalesmanProblem，簡稱TSP）即給定n個城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當(dāng)且僅當(dāng)一次的最短路線。其圖論描述為：給定圖G=（V，A），其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的邊集，設(shè)D=（dij）是由頂點(diǎn)i和頂點(diǎn)j之間的距離所組成的距離矩陣，要求確定一條長度最短的Hamilton回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短距離。旅行商問題可分為如下兩類：1）對稱旅行商問題（dij=diji，j=1，2，3，…，n）；2）非對稱旅行商問題（dijdiji，j=1，2，3，…，n）。非對稱旅行商問題較難求解，我們一般是探討對稱旅行商問題的求解。若對于城市V={v1，v2，v3，…，vn}的一個訪問順序?yàn)門={t1，t2，t3，…ti，…，tn}，其中tiV（i=1，2，3，…，n），且記tn+1=t1，則旅行商問題的數(shù)學(xué)模型為：4蟻群算法的缺點(diǎn)旅行商問題是一個典型的組合優(yōu)化問題，并且是一個NP完全難題，是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn)。因此，快速、有效地解決旅行商問題有著重要的理論價值和極高的實(shí)際應(yīng)用價值。基于旅行商的問題特性，構(gòu)造型算法成為最先開發(fā)的求解算法，如最近鄰點(diǎn)、最近合并、最近插入、最遠(yuǎn)插入、最近添加、貪婪插入等。但蟻群算法最主要的缺點(diǎn)是求解速度慢。很多學(xué)者對此進(jìn)行了研究，提出了多種改進(jìn)方法，但不論采用那種具體方法，都可歸結(jié)為通過提高螞蟻每次周游的質(zhì)量來提高蟻群算法的求解速度。之所以都采用這種方法，就是由于基本蟻群算法求解速度慢的一個重要原因是螞蟻每次周游得到的信息沒有被充分地利用起來。這主要體現(xiàn)在各條路徑上的信息量更新規(guī)則上。由上面對蟻群算法的介紹可知，螞蟻在周游過程中，會使它經(jīng)過的路徑上的信息量減少，同時，增強(qiáng)螞蟻周游的信息沒有充分地利用起來。實(shí)際上，每只螞蟻周游的信息也是很有用的。蟻群算法求解速度慢的另一個重要原因是螞蟻獲取的信息與實(shí)際情況會有一些差異，這會對螞蟻產(chǎn)生誤導(dǎo)，而蟻群算法排除誤導(dǎo)的速度較慢。蟻群算法求解過程是一個正反饋過程。螞蟻的第一次周游時，由于各路徑上的信息量相同，螞蟻選擇城市是隨機(jī)的。這一次選擇會使一些不是最優(yōu)的路徑上的信息量偏大。以后的螞蟻就會根據(jù)這個不正確的信息選擇以后的路徑，這些不是最優(yōu)的路徑被螞蟻選擇的可能性將很大，這會導(dǎo)致這些較差的路徑上的信息量不斷增大。經(jīng)過這樣一個正反饋過程，路徑上的信息量就具有了很大的誤差而導(dǎo)致算法難以找到較優(yōu)解。蟻群算法在一定程度上可通過信息量的揮發(fā)過程以及螞蟻周游的下一個城市的隨機(jī)選擇過程來排除具有較大誤差的信息。但是，信息量揮發(fā)過程是緩慢的。而且在揮發(fā)過程中，很可能會有許多螞蟻再次經(jīng)過這條路徑，并有可能使這條路徑上的信息量增大。一次通過選擇城市隨機(jī)性來削減誤差僅在算法剛運(yùn)行不久，各條路徑上的信息量相差不是很大的情況下才可能起到一定作用。由于這兩種排除誤差的方法均不能較快地排除誤差，也導(dǎo)致了蟻群算法求解速度慢，并且增加了算法陷入局部最優(yōu)的可能性。5蟻群算法的改進(jìn)1）加入擾動的改進(jìn)針對蟻群算法容易陷入局部最優(yōu)解，這里引入?yún)?shù)q0，螞蟻k從i城市選擇下一個城市j時，首先產(chǎn)生一個[0，l]均勻分布的隨機(jī)數(shù)q，當(dāng)q小于常數(shù)q0時，螞蟻根據(jù)先驗(yàn)知識即：能見度選擇下一個城市。公式（1）改進(jìn)為：③依狀態(tài)轉(zhuǎn)移規(guī)則選擇下一結(jié)點(diǎn)；④重復(fù)步驟③，直至每只螞蟻均形成一條完整路徑，即遍歷所有結(jié)點(diǎn)；⑤更新最優(yōu)解；⑥進(jìn)行信息素更新；⑦判斷是否滿足算法終止條件：若滿足，則算法終止；否則，轉(zhuǎn)步驟②。6實(shí)驗(yàn)結(jié)果及分析本文利用MATLAB仿真平臺對典型的旅行商問題OdysseyofUlysses進(jìn)行進(jìn)行了仿真實(shí)驗(yàn)，已知OdysseyofUlysses問題的最優(yōu)解是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，原始蟻群算法與改進(jìn)蟻群算法分別周游10次，50次，100次所得到的最優(yōu)解對比如下表：加入擾動參數(shù)q，每隔一定時間，螞蟻在選擇下一個城市時，只根據(jù)能見度選擇，這樣可以排除因?yàn)橄伻核惴ㄕ答亴?dǎo)致的較大誤差解，擴(kuò)大了解的搜索范圍，有效避免了蟻群算法過早陷入局部最優(yōu)解。2）信息素更新規(guī)則的改進(jìn)蟻群算法最主要的缺點(diǎn)是求解速度慢。由于基本蟻群算法求解速度慢的一個重要原因是螞蟻每次周游得到的信息沒有被充分地利用起來。這主要體現(xiàn)在各條路徑上的信息量更新規(guī)則上。由上面對蟻群算法的介紹可知，螞蟻在周游過程中，會使它經(jīng)過的路徑上的信息量減少，同時，增強(qiáng)螞蟻在最短路徑上的信息。這一過程利用了螞蟻周游最短路徑的信息。但其它螞蟻周游的信息沒有充分地利用起來。實(shí)際上，每只螞蟻周游的信息也是很有用的。本文充分利用螞蟻在最差路徑上的信息對蟻群算法的信息素更新規(guī)則做了改進(jìn)，在規(guī)則中引入了最差路徑信息量減少參數(shù)w，改進(jìn)后公式（2）調(diào)整為：從實(shí)驗(yàn)結(jié)果對比來看，改進(jìn)后的蟻群算法在100次周游下已經(jīng)找到問題的最優(yōu)解，而原始的蟻群算法雖然在加大周游次數(shù)可以逐步接近最優(yōu)解，但是他的收斂性不好，容易陷入局部最優(yōu)解，所以，加大周游次數(shù)對求解旅行商最優(yōu)解的意義不大。而改進(jìn)的蟻群算法正是對原始蟻群算法的收斂速度慢，容易陷入最優(yōu)解這兩個方面進(jìn)行了改進(jìn)，改進(jìn)后的蟻群算法能夠擴(kuò)大最優(yōu)解的搜索范圍，有效地避免算法過早陷入局部最優(yōu)的情況的出現(xiàn)。實(shí)驗(yàn)結(jié)果證明：改進(jìn)后的蟻群算法無論是最優(yōu)解的方面還是在收斂速度方面都比原始蟻群算法要好。7結(jié)論蟻群算法最大的缺點(diǎn)就是收斂速度慢，容易陷入最優(yōu)解，這也是限制它應(yīng)用的最大瓶頸。本文針對蟻群算法收斂速度慢、容易過早陷入局部最優(yōu)的缺點(diǎn)提出了一種新的改進(jìn)算法。實(shí)驗(yàn)證明了這種改進(jìn)的有效性和正確性。表示揮發(fā)系數(shù)，Q為信息量增加常數(shù)，w為信息量減少常數(shù)。3）算法實(shí)現(xiàn)MATLAB是一個可視化的計(jì)算程序，被廣泛地使用于從個人計(jì)算機(jī)到超級計(jì)算機(jī)范圍內(nèi)的各種計(jì)算機(jī)上。它包括命令控制、可編程，有上百個預(yù)先定義好的命令和函數(shù)。這些函數(shù)能通過用戶自定義函數(shù)進(jìn)一步擴(kuò)展。MATLAB有許多強(qiáng)有力的命令。正因?yàn)镸ATLAB具有這么多的優(yōu)點(diǎn)，特別是在數(shù)值計(jì)算方面的獨(dú)到性，本文利用MATLAB平臺進(jìn)行仿真實(shí)驗(yàn)。其程序步驟如下：①初始化信息素分布；②將每只螞蟻隨機(jī)置于任一個結(jié)點(diǎn)上；參考文獻(xiàn)：[1]吳斌、傅偉鵬、鄭毅、劉少輝，史忠植一種基于群體智能的Web文檔聚類算法計(jì)算，機(jī)研究與發(fā)展，2021，39（11）：1429～1435.[2]吳啟迪、汪鐳，智能蟻群算法及應(yīng)用[M].上海：上海科技教育出版社，2021.4.[3]黎鎖平、張秀媛、楊海波，人工蟻群算法理論及其在經(jīng)典TSP問題中的實(shí)現(xiàn)[J].交通運(yùn)輸系統(tǒng)工程與信息，2007，2（2）：73～76.一種基于動態(tài)多維矩陣編碼的組卷遺傳算法王力1陳郁明2(1.貴州大學(xué)電子科學(xué)與信息技術(shù)學(xué)院,貴州貴陽550003(2.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴州貴陽550003摘要:提出動態(tài)多維矩陣表示解(染體色的遺傳算法,并針對這種染色體在交叉、變異和選擇等遺傳算子的實(shí)現(xiàn)進(jìn)行了研究。運(yùn)行結(jié)果表明,算法運(yùn)行效率較好,有很好的實(shí)用價值。關(guān)鍵詞:多維矩陣染色體;遺傳算法;自動組卷中圖法分類號:TP399文獻(xiàn)標(biāo)識碼:BAGeneticAlgorithmbased-ondynamicmultipledimensionmatrixcodingWangLi1,CHENYuming2(1.SchoolofElectronicScienceandInformationTechnologyGuizhouUniversityGuiyang5500032.SchoolofComputerScienceandTechnology,Guizhou,Guiyang550003Abstract:Thegeneticalgorithmwasproposedbyusingmultipledynamicdimensionmatrixestorepresentsolution(chromosome.Andrealizationofgeneticoperatorssuchascrossover、mutationandselection,andsoonwasexplored.Theoperationresultrevealsthatthealgorithmhasabetterefficiencyandthereforeitisofbetterpracticalvalue.Keywords:dynamicmultipledimensionchromosome;geneticalgorithm;automaticgeneratingtestpaper1引言遺傳算法(GeneticAlgorithm,簡稱GA是一種演化算法,從提出至今不過50年時間。與爬山算法、模擬退火算法和禁忌算法等一樣都屬啟發(fā)式搜索算法[1]。目前遺傳算法在函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器人學(xué)、圖像處理[4][5]和自動編程等諸多領(lǐng)域已經(jīng)得到成功應(yīng)用。在教育領(lǐng)域中,有大量的研究者把遺傳算法用于自動排課、自動組卷[2][3]、學(xué)生成績數(shù)據(jù)挖掘分析等,并且取得成功。很多自動組卷遺傳算法都基于線性二進(jìn)制串[2]或整數(shù)編碼[3]實(shí)現(xiàn)染色體,本文先介紹了三維矩陣試卷模型,然后提出了一種新的編碼方式——動態(tài)多維矩陣表示GA的解(染色體,以及交叉算子、變異算子和選擇算子的實(shí)現(xiàn)。2試卷模型構(gòu)成試卷是長度為n的一維向量(123,,,...,nttttπ,其中ti是試卷的第i道題在試題庫中的編號,并且每道題目具有題型、知識點(diǎn)、分?jǐn)?shù)、難度系數(shù)等多個屬性。向量π中,按題型可把題目分為m類,按照知識點(diǎn)也可把題目分成k類。因此,可以把試卷看成一個三維向量Amnk,m表示題型數(shù)量,n表示知識點(diǎn)數(shù)量,k為某題型中每個知識點(diǎn)試題數(shù),題庫中不同的題型和知識點(diǎn)k值不同。矩陣中的元素aijr表示題型i及知識點(diǎn)j的第r道題的題目編號。設(shè)Q[1..n,1..m,1..k]中元素qijr保存題目aijr的分?jǐn)?shù),設(shè)x[1..n,1..m,1..k]為一標(biāo)志數(shù)組,試卷滿足如下公式:???=未被選中題目被選中,題目ijrijra,0a1],,[rjiX∑∑∑====minjkrrjiQrjixZ111],,[],,[n為題型數(shù),m為知識點(diǎn)數(shù),k為某題型和知識點(diǎn)對應(yīng)的題目數(shù)。3組卷遺傳算法3.1動態(tài)多維矩陣染色體數(shù)據(jù)結(jié)構(gòu)編碼是運(yùn)用GA時要解決的首要問題,也是設(shè)計(jì)GA的一個關(guān)鍵步驟。針對具體應(yīng)用問題,如何設(shè)計(jì)一種完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)之一,也是遺傳算法的一個重要研究方向?？紤]使用三維矩陣(設(shè)為Cmnk作為染色體。其中,題型數(shù)為m,知識點(diǎn)數(shù)為,某題型和知識點(diǎn)題目數(shù)為k。設(shè)預(yù)組試卷只有選擇題、填空題和解答題3類題型,涉及4個知識點(diǎn),圖2.1為該染色體對應(yīng)的“動態(tài)三維矩陣”。00第二面:填空題??????????????00001001101第三面:解答題??????????????010*********圖3.1染色體構(gòu)成示例以第一面選擇題為例,第一行表示題庫中知“識點(diǎn)1”滿足條件的題目只有2道,并且沒有一道被選中,第二行表示“知識點(diǎn)2”滿足條件的題目數(shù)有4道,但只有第1道被選到試卷中。由于每道題型、每個知識點(diǎn)的題目數(shù)不一樣多,有時可能沒有題目,因此在設(shè)計(jì)時用動態(tài)三維數(shù)組實(shí)現(xiàn)染色體。Chro:ArrayofArrayofArrayofbyte;本文所提的“動態(tài)三維矩陣”并不是傳統(tǒng)意義的三維矩陣,實(shí)際上是類似于三維矩陣的特殊的數(shù)據(jù)結(jié)構(gòu)。3.2染色體適應(yīng)度函數(shù)適應(yīng)度用于表示解的質(zhì)量,GA通過計(jì)算種群的每個個體適應(yīng)度,然后根據(jù)適應(yīng)度值的大小確定個體與解的逼近程度。為了得到個體適應(yīng)度,必須構(gòu)造相應(yīng)適應(yīng)度函數(shù),但是適應(yīng)度函數(shù)并不是顯而易見的或由問題自動給出的,而是與問題的目標(biāo)相關(guān)的,一個解如果完全滿足目標(biāo),它就應(yīng)該有最好的適應(yīng)值。自動組卷的目標(biāo)就是要使總分、題目數(shù)、難度系數(shù)等每項(xiàng)組卷指標(biāo)的誤差ξi最小,可以對每項(xiàng)指標(biāo)設(shè)定一個權(quán)值Wi,表示對試卷的影響程度的估計(jì)。個體i適應(yīng)度函數(shù)可表示為:∑==niiiWif1*(ξ,n為組卷指標(biāo)數(shù)f(i的值越小表明個體i適應(yīng)環(huán)境越強(qiáng)。因此,自動組卷問題變成了對函數(shù)f(i求極小值的問題。為了方便,把求極小值問題變成求極大值問題,函數(shù)變?yōu)?∑=?=niiiWCif1*(ξ,C為一常數(shù),保證f(i為大于零的正數(shù)3.3選擇算子設(shè)計(jì)采用輪盤賭選擇算法,即某個染色是否被選中根據(jù)指針在輪盤上拔動位置來選擇。設(shè)每個個體的適應(yīng)度值對應(yīng)輪盤的每一格,可以知道輪盤上格子距離最大的一格,即表示適應(yīng)度值大的個體,其被選中的概率也大。個體在輪盤中格子大小(概率按下式計(jì)算:∑==NjijfifP1((,N為種群大小,且11=∑=NiiPPi表示個體i被選中概率,被選中的概率越大,則在輪盤賭中,賭贏的概率越大。為了模擬輪盤,還要計(jì)算每個個體的累積概率,公式如下:∑?=iiipiFF1][由計(jì)算機(jī)產(chǎn)生一個[0,1]之間的隨機(jī)數(shù)r,該數(shù)對應(yīng)輪盤指針停放的位置,如果[](1rFFkkN<=<=<=時,表示選中個體k進(jìn)入下一代。為了確保最優(yōu)個體能進(jìn)入下一代,在進(jìn)化過程中,始終保存最優(yōu)個體,如果最優(yōu)個體的適應(yīng)度值小于本代最優(yōu)個體,則把最優(yōu)個體代替本代最差個體,否則把本代最優(yōu)個體當(dāng)作最優(yōu)個體進(jìn)入下一代。3.4交叉算子設(shè)計(jì)對于N個體的種群,以概率Pc(<0.95隨機(jī)地選擇兩個個體進(jìn)行交叉,方法是對三維“矩陣”的面(題型維或面中的行(知識點(diǎn)維進(jìn)行整體交叉,隨機(jī)生成兩個隨機(jī)數(shù)(,1,1uvumvn<=<=<=<=,分別表示對兩個個體的第u面到最后一面進(jìn)行交叉,根據(jù)需要,也可根據(jù)指定的條件再對該面的第v行進(jìn)行交叉。交叉結(jié)果保證了每種題型的題目數(shù)不發(fā)生變化,知識點(diǎn)的題目數(shù)也不發(fā)生變化。3.5變異算子設(shè)計(jì)變異算子可以增加種群的多樣性,對于防止種群的早熟有著極其重要的作用。在變異概率Pm(<=0.2作用下,利用隨機(jī)函數(shù)產(chǎn)生三個整數(shù)(,1,1uvumvn<<=<=<=和(1wwk<<=,表示在第u面第v位實(shí)施變異操作,即把0變1或把1變成0,由于操作將導(dǎo)致題目數(shù)增1或少1的情況發(fā)生,同時把第u面第w位取反,要注意的是第v,第w位異或結(jié)果必須為1。當(dāng)以滿足分?jǐn)?shù)優(yōu)先為前提進(jìn)行自動組卷操作時,只需要簡單地把變異位取反即可。3.6停機(jī)條件