【正文】 成了上述兩種的優(yōu)點(diǎn)克服了它們的缺點(diǎn)，因此本文釆用競(jìng)爭(zhēng)選擇法. 其中競(jìng)爭(zhēng)選擇法是釆用適應(yīng)度比例法進(jìn)行選擇，交叉后產(chǎn)生下一代，再利用最佳個(gè)體保留法將上一代的最佳個(gè)體直接保存下來，然后從新群體中淘汰一個(gè)適應(yīng)度最差的個(gè)體，提高了問題求解的收斂速度，體現(xiàn)了遺傳算法自適應(yīng)環(huán)境的能力. 在對(duì)染色體進(jìn)行交叉時(shí),對(duì)于由整數(shù)編碼的染色體，交叉操作會(huì)形成染色體中的非法基因，即重復(fù)基因. 所以實(shí)現(xiàn)染色體交叉要將重復(fù)的基因清除. 只使用一種交叉方法容易引起過早收斂，即“早熟”. 依據(jù)選擇性集成思想 ,等概率使用兩點(diǎn)交叉法和區(qū)域交叉法這兩種交叉方法，擴(kuò)大遺傳算法的搜索范圍，避免過早收斂. 在染色體的變異中，與交叉方法一樣，如果使用一種變異方法，同樣可能會(huì)引起“早熟”. 為了避免過早收斂，依據(jù)選擇性集成思想選擇鄰居交換變異和兩點(diǎn)交換變異這兩種個(gè)性好且差異性較大的變異方法，等概率使用以擴(kuò)大搜索范圍. 模型建立 從起點(diǎn)站到終點(diǎn)站不轉(zhuǎn)車，則雙種群遺傳算法的流程如下：（1）產(chǎn)生鄰接矩陣鄰接矩陣的MATLAB程序?qū)崿F(xiàn)見附件一. （2）基于站點(diǎn)序號(hào)的編碼一般來說種群規(guī)模越大越容易收斂到最優(yōu)解，但是要保證其初始種群中的每個(gè)個(gè)體都是互異的，m不能設(shè)置過大，否則無法產(chǎn)生初始種群，且m過大其收斂速度必然降低，也會(huì)消耗更多的計(jì)算資源,并基于一般遺傳算法中初始群體大小的選擇，本文中取m=30. 公汽路線問題中每一種起點(diǎn)站到終點(diǎn)站的方案對(duì)應(yīng)于解空間的一個(gè)解 ，解空間中的數(shù)據(jù)是遺傳算法的表現(xiàn)形式，從表現(xiàn)到基因型的映射稱為編碼. 最初遺傳算法是采用二進(jìn)制編碼方法，但在大量實(shí)際問題中，二進(jìn)制編碼操作不簡(jiǎn)便，不易進(jìn)行變異交叉操作，易產(chǎn)生大量非可行解，所以針對(duì)特殊的問題，可以靈活采用不同的編碼方法. 本文在公汽線路求解中，采用基于站點(diǎn)序號(hào)的實(shí)數(shù)編碼，將染色體定義為公汽線路的一條解路線中的站點(diǎn)號(hào)序列，在MATLAB中為一個(gè)沒有重復(fù)數(shù)字的行向量來表示. 設(shè)有n個(gè)站點(diǎn)的某個(gè)全排列為，則個(gè)體的染色體表示為，n=3957. （3）產(chǎn)生初始群體種群中每一個(gè)體為n（3957）個(gè)站點(diǎn)的一個(gè)全排列，隨機(jī)生成m（m=30）個(gè)1～n 的隨機(jī)排列，得到m個(gè)個(gè)體的初始種群，m為種群大小，n為染色體長(zhǎng)度. 生成初始群體的具體算法的MATLAB程序?qū)崿F(xiàn)見附件二. A、B初始群體的數(shù)據(jù)矩陣為，由于數(shù)據(jù)太多，文中就不給出數(shù)據(jù)（其結(jié)果可運(yùn)行程序得出）. （4）適應(yīng)度函數(shù)與染色體的選擇在遺傳算法進(jìn)行搜索時(shí)只以適應(yīng)度函數(shù)為依據(jù)，利用種群中個(gè)體每個(gè)的適應(yīng)度值來進(jìn)行搜索，適應(yīng)度值是進(jìn)化時(shí)優(yōu)勝劣汰的依據(jù)，應(yīng)用中總是根據(jù)問題的優(yōu)化指標(biāo)來定義. 對(duì)于公汽線路問題，以個(gè)體對(duì)應(yīng)路線所發(fā)的時(shí)間之和作為個(gè)體適應(yīng)度，其適應(yīng)度越小,表明該個(gè)體越優(yōu). 則該個(gè)體對(duì)應(yīng)為：其中（3（分鐘））表示相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)，表示站點(diǎn)和之間的距離，表示起始點(diǎn)與終點(diǎn)站之間的距離.一般來說，選擇算子設(shè)計(jì)使得個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小有關(guān). 適應(yīng)度是越高越好，而在公汽線路問題中，如果適應(yīng)度是所經(jīng)過的對(duì)應(yīng)路線所花的時(shí)間之和，路線所花時(shí)間之和是越小越好，為了使公汽線路問題的適應(yīng)度與一般遺傳算法中的適應(yīng)度一致. 這里用選擇概率來進(jìn)行衡量. 則每個(gè)個(gè)體的選擇概率（適應(yīng)度比例）就是每個(gè)個(gè)體的適應(yīng)度與所有個(gè)體適應(yīng)度的總和之比，即：其中表示所有個(gè)體適應(yīng)度的總和. 但當(dāng)路徑所花時(shí)間非常大(例如：10000)，這樣其適應(yīng)度比例的最高數(shù)據(jù)位將在小數(shù)點(diǎn)后的第四位，這樣不利于計(jì)算，為此要進(jìn)行尺度變換. 為確保適應(yīng)度有兩位整數(shù)，此處將適應(yīng)度放大倍數(shù)L(本題中 L=lOOO) 因此適應(yīng)度比例的表達(dá)式為：遺傳算法中選擇算子設(shè)計(jì)經(jīng)典的是用適應(yīng)度成比例的概率方法 ，但是這里存在的問題是由于許多個(gè)體的適應(yīng)度比例很小幾乎沒有機(jī)會(huì)復(fù)制個(gè)體，從而被過早地淘汰. 這樣整個(gè)群體多樣性就無法得到保證，這里采用一種新的賭輪選擇算子——離散賭輪選擇，將有效地避免了這個(gè)問題. 在本題中是由30個(gè)個(gè)體構(gòu)成初始群體，即：，其所占的適應(yīng)度比例分別是，在保持這個(gè)比例的情況下對(duì)這個(gè)取值范圍放大1000倍. 按照順序在1～1000內(nèi)分別占不同的區(qū)間，當(dāng)隨機(jī)函數(shù)產(chǎn)生1～1000以內(nèi)的時(shí)，即使是適應(yīng)度比例最小的也有可能被選中，從而較好的保持了群體的多樣性. 由上所述則可選擇出適應(yīng)力強(qiáng)的，淘汰適應(yīng)力弱的個(gè)體從而得到總體適應(yīng)能力強(qiáng)的群體. 經(jīng)過選擇算子得出總體適應(yīng)能力強(qiáng)的A、B群體數(shù)據(jù)矩陣為，因數(shù)據(jù)量太大，文中就不給出具體數(shù)據(jù). （5）交叉重組依據(jù)選擇性集成思想 ,等概率使用兩點(diǎn)交叉法和區(qū)域交叉法這兩種差異性較大的交叉方法，擴(kuò)大遺傳算法的搜索范圍，避免過早收斂. 其中，兩點(diǎn)交叉法是先隨機(jī)設(shè)定兩個(gè)基因交叉位置，將父輩兩個(gè)個(gè)體在這兩個(gè)交叉點(diǎn)之間的基因鏈碼相互交換，從而形成新的個(gè)體；區(qū)域交叉法是隨機(jī)在染色體中選擇一個(gè)交叉區(qū)域，將第二條染色體的交叉區(qū)域加在第一條染色體的前面，第一條染色體的交叉區(qū)域加在第二條染色體的前面，在交叉區(qū)域后依次刪除與交叉區(qū)域相同的基因，得到最后的兩條子染色體. 將第（3）步得到的關(guān)于A，B種群的數(shù)據(jù)分別用兩種交叉算法來實(shí)現(xiàn)操作. 其中一半數(shù)據(jù)用兩點(diǎn)交叉法，另一半的數(shù)據(jù)用區(qū)域交叉法來進(jìn)行染色體的交叉重組. 其具體算法的MATLAB程序?qū)崿F(xiàn)見附件四. 經(jīng)過交叉重組得出的A、B群體數(shù)據(jù)矩陣為，因數(shù)據(jù)量太大，文中就不給出具體數(shù)據(jù). （6）染色體的變異為了避免過早收斂，依據(jù)選擇性集成思想選擇鄰居交換變異和兩點(diǎn)交換變異這兩種個(gè)性好且差異性較大的變異方法，等概率使用以擴(kuò)大搜索范圍. 其中，鄰居交換變異是產(chǎn)生一個(gè)隨機(jī)數(shù)，將該數(shù)對(duì)應(yīng)的基因和其后的基因交換；若該數(shù)對(duì)應(yīng)的基因是染色體中的最后一個(gè)基因，則將該基因與染色體的第一個(gè)基因交換；兩點(diǎn)交換變異是先產(chǎn)生兩個(gè)不同的隨機(jī)數(shù)，確定兩個(gè)交換點(diǎn)，然后對(duì)個(gè)體在此兩點(diǎn)的基因進(jìn)行交換. 經(jīng)過染色體變異得出的A、B群體數(shù)據(jù)矩陣為，因數(shù)據(jù)量太大，文中就不給出具體數(shù)據(jù). （7）種群交叉將兩個(gè)種群中的最優(yōu)解取出，再在每個(gè)種群中隨機(jī)選取n個(gè)染色體，將這n+1個(gè)染色體互換，進(jìn)入對(duì)方種群. 經(jīng)過種群交叉得出的A、B群體數(shù)據(jù)矩陣為，因數(shù)據(jù)量太大，文中就不給出具體數(shù)據(jù). （8）最佳個(gè)體保留法 要把群體中適應(yīng)度最高的個(gè)體不經(jīng)過配對(duì)交叉直接復(fù)制到下一代中，然后從新群體中淘汰一個(gè)適應(yīng)度最差的個(gè)體. 分別對(duì)A、B進(jìn)行獨(dú)立的操作. 經(jīng)過最佳保留法選擇后得出的A、B群體數(shù)據(jù)矩陣為，因數(shù)據(jù)量太大，文中就不給出具體數(shù)據(jù). （9）迭代的結(jié)束條件 在本文中，采用進(jìn)化的代數(shù)N作為循環(huán)迭代過程的結(jié)束，如果等于N，則算法結(jié)束，輸出適應(yīng)值最高的解；否則，繼續(xù)重復(fù)上述過程. 重復(fù)步驟（3），（4），（5），（6），（7），（8）依次進(jìn)行循環(huán)迭代，本題中設(shè)定迭代次數(shù)為N=1000. 最后得到30個(gè)近似的最優(yōu)解. 以上（2）—（9）流程的MATLAB程序?qū)崿F(xiàn)見附件二. （10）結(jié)果選出這30個(gè)近似最優(yōu)解中以時(shí)間作為權(quán)值最小的那一組解作為題設(shè)中要求的近似最優(yōu)解. 其中滿足要求的基因鏈碼（站點(diǎn)數(shù)）的順序即是顧客所需從起始點(diǎn)到終點(diǎn)站的路線 從起點(diǎn)站到終點(diǎn)站轉(zhuǎn)一次車從起點(diǎn)站到終點(diǎn)站轉(zhuǎn)一次車遺傳算法流程中基于站點(diǎn)序號(hào)的編碼，交叉重組，染色體的變異，種群交叉，迭代的結(jié)束條件和結(jié)果的原理與從起點(diǎn)站到終點(diǎn)站不轉(zhuǎn)車相同. 只有在適應(yīng)度函數(shù)與選擇流程中每一個(gè)個(gè)體所對(duì)應(yīng)的適應(yīng)度函數(shù)處有所改變，其函數(shù)為：其中5（分鐘）表示公汽換乘公汽一次耗時(shí)(其中步行時(shí)間2分鐘).除這之外，這一流程中的其他的原理沒變. 從起點(diǎn)站到終點(diǎn)站轉(zhuǎn)兩次車從起點(diǎn)站到終點(diǎn)站轉(zhuǎn)兩次車遺傳算法流程中基于站點(diǎn)序號(hào)的編碼，交叉重組，染色體的變異，種群交叉，迭代的結(jié)束條件和結(jié)果的原理與從起點(diǎn)站到終點(diǎn)站不轉(zhuǎn)車相同. 只有在適應(yīng)度函數(shù)與選擇流程中每一個(gè)個(gè)體所對(duì)應(yīng)的適應(yīng)度函數(shù)處有所改變，其函數(shù)為： 其中（分鐘）表示公汽換乘公汽兩次耗時(shí)(其中步行時(shí)間分鐘).除這之外，這一流程中的其他的原理沒變. 模型求解 由程序運(yùn)行最終得出：找不一條路線使從起點(diǎn)站到終點(diǎn)站不轉(zhuǎn)車. 從起點(diǎn)站到終點(diǎn)站轉(zhuǎn)一次車 。11起始站第一次路線中轉(zhuǎn)站第二次路線終點(diǎn)站S3359L436S3695L217S1828S0008L200S3092L282S0073S0971L013S2607L377S0485S0087L454S1893L209S3676。clc。i3=zeros(3958,3958)。 a2=data(find(data(:,1)==i1)+2,i2)。 (i4i2)==0 %a1不為空值時(shí)，把i3矩陣賦值 i3(a2,a1)=0。 (i4i2)==1 i3(a2,a1)=3。 (i4i2)1 i3(a2,a1)=inf。 a4=data(find(data(:,1)==i1)+3,i2)。 (i4i2)==0 %a1不為空值時(shí)，把i3矩陣賦值 i3(a3,a4)=0。 (i4i2)==1 i3(a3,a4)=3。 (i4i2)1 i3(a3,a4)=inf。 i3(j1,j2)~=3 i3(j1,j2)=inf。 end endend 附件二%遺傳算法流程實(shí)現(xiàn)%clear。M=30。popm1=zeros(M,num)。 %隨機(jī)產(chǎn)生一個(gè)由自然數(shù)1到num 組成的全排列endpopm2=zeros(M,num)。 %隨機(jī)產(chǎn)