時間：2022-07-01 00:20:08
引言：易發表網憑借豐富的文秘實踐，為您精心挑選了九篇遺傳算法論文范例。如需獲取更多原創內容，可隨時聯系我們的客服老師。
論文摘要：TSP是組合優化問題的典型代表,該文在分析了遺傳算法的特點后,提出了一種新的遺傳算法(GB—MGA),該算法將基因庫和多重搜索策略結合起來,利用基因庫指導單親遺傳演化的進化方向,在多重搜索策略的基礎上利用改進的交叉算子又增強了遺傳算法的全局搜索能力。通過對國際TSP庫中多個實例的測試,結果表明:算法(GB—MGA)加快了遺傳算法的收斂速度,也加強了算法的尋優能力。
論文關鍵詞：旅行商問題遺傳算法基因庫多重搜索策略
TSP(travelingsalesmanproblem)可以簡述為:有n個城市1,2,…,n,一旅行商從某一城市出發,環游所有城市后回到原出發地,且各城市只能經過一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時間不受限制的話,在理論上這種問題終會找到最優解,但對于稍大規模的TSP,時間上的代價往往是無法接受的。這是一個典型的組合最優化問題,已被證明是NP難問題,即很可能不存在確定的算法能在多項式時間內求到問題的解[1]。由于TSP在工程領域有著廣泛的應用,如貨物運輸、加工調度、網絡通訊、電氣布線、管道鋪設等,因而吸引了眾多領域的學者對它進行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法[2]、螞蟻算法[3]、模擬退火算法、遺傳算法等。
遺傳算法是一種借鑒生物界自然選擇和遺傳機制的隨機化搜索算法,其主要特點是群體搜索策略和群體中個體之間的信息交換,搜索不依賴于梯度信息[4]。遺傳算法主要包括選擇、交叉和變異3個操作算子,它是一種全局化搜索算法,尤其適用于傳統搜索算法難于解決的復雜和非線性問題。遺傳算法雖然不能保證在有限的時間內獲得最優解,但隨機地選擇充分多個解驗證后,錯誤的概率會降到可以接受的程度。
用遺傳算法求解TSP能得到令人滿意的結果,但是其收斂速度較慢,而且種群在交叉算子作用下,會陷入局部解。采用局部啟發式搜索算法等,雖然能在很短的時間內計算出小規模城市的高質量解,一旦城市規模稍大就容易陷入局部最優解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優解,該文采納了文[5]中楊輝提出的基因庫的想法,并結合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用單親演化與群體演化相結合的方式來求解TSP問題。該文根據文[7]中最小生成樹MST(minimumcostspanningtree)的應用,由MST建立TSP的基因庫,保存有希望成為最優解的邊,利用基因庫提高初始群體的質量進行單親演化,然后利用改進后的交叉算子和的多重搜索策略進行群體演化。
1單親演化過程
現有的大多數演化算法在整個演化過程中所涉及的基因,大多來源于個體本身,個體質量的高低決定了算法的全局性能,如果群體中初始個體的適應度都較差,肯定要影響算法的收斂速度,對于規模稍大的TSP尤其明顯[8]。該文為了克服上述弱點,首先利用普里姆算法求出TSP中最小生成樹,并將各個MST中的每一條邊都保存在一個n*(n-1)方陣里面,就構成了一個基因庫,在生成初始群體的時候盡量使用基因庫中的基因片段,來提高整個初始群體的適應度,從而提高算法的效率。
1.1TSP編碼表示
設n個城市編號為1,2,…,n,為一條可行路徑,Pk=Vk1Vk2…Vkn為一條可行路徑,它是1,2,…,n的一個隨機排列,其含意是第k條路徑起點城市是Vk1,最后一個城市是Vkn,則第k條環路的總長度可以表示為:
其中,d(Vki,Vkj)表示城市Vki與城市Vkj之間的距離。在算法中環路Pk的總長d(Pk)用來評價個體的好壞[9]。適應度函數取路徑長度d(Pk)的倒數,f(Pk)=1/d(Pk)。
1.2構建TSP基因庫
對n個編號為1,2,…,n的城市,根據它們的坐標計算各城市之間的歐氏距離d(i,j),i,j=1,2,…,n,得到一個n*n的方陣D={d(i,j)}。然后利用普里姆算法求得該TSP的一棵MST,并將這棵MST中的每一條邊e(i,j)對應地存儲在一個n*(n-1)的方陣M={e(i,j)},即該文的基因庫。由于一個TSP可能有多棵MST,操作可以重復多次,這樣生成的基因庫中的基因就更多,增強了初始群體的全局性。具體算法如下:
VoidMiniSpanTree—PRIM(MGraphG,VertexTypeu){
Struct{
VertexTypeadjvex;
VRTypelowcost;
}closedge[MAX—VERTEX—NUM];
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
if(j!=k)closedge[j]={u,G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=0;i<G.vexnum;++i){
k=minimum(closedge);
printf(closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
1.3單親演化算法
單親演化算法是利用遺傳算法的優勝劣汰的遺傳特性,在單個染色體內以基因重組的方式,使子代在滿足TSP問題的限定條件下進行繁衍,然后保留適應度高的染色體種群,達到優化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯位和基因段倒轉三種操作來實現。基因換位操作是將親代的染色體基因進行對換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式?；蚨五e位操作是隨機確定基因段,也隨機選定錯位位置,整段錯移。基因段倒轉操作則是隨機地確定倒轉基因段的起止位置,倒轉操作是對該段內基因按中垂線作鏡面反射,若段內基因數為奇數時,則中位基因不變。單親演化時可以是單個操作用于單個父代,也可以是幾種操作同時采用。為了編程方便,文中采用基因段倒轉操作。
2群體演化過程
在單親演化算法求得的初始群體基礎上,再利用多重搜索策略并行地進行群體演化,這樣在保證算法的快速收斂的同時也注重了搜索空間的全局性。
2.1交叉算子
該文算子采用一種與順序交叉OX(ordercrossover)法類似的交叉方法[11],即隨機在串中選擇一個區域,例如以下兩個父串及區域選定為:
P1=(12|3456|789)P2=(98|7654|321)
將P2的區域加到P1的前面或后面,P1的區域加到P2的前面或后面,得
M1=(7654|123456789)
M2=(3456|987654321)
在M1中自區域后依次刪除與區域相同的城市碼,得到最終的兩個子串:
S1=(765412389)S2=(345698721)
同時為了能更好地增強算子的全局搜索能力,對該算子作了如下的改進。子代個體的新邊來自:隨機生成和群體中其他個體,其選擇比例由隨機數p和閾值P來決定。如果隨機數p小于閾值P,則子代個體的新邊來自隨機生成,否則就來自群體中的其他個體。
這種改進后的交叉算子在父串相同的情況下仍能產生一定程度的變異效果,這對維持群體的多樣化特性有一定的作用。實驗結果也證實了這種改進算子對于種群的全局搜索能力有一定的提高,避免搜索陷入局部解。
2.2局部啟發式算子
為了增強遺傳算法的局部搜索性能,在算法中引入2-Opt局部搜索算子[12]。該算子通過比較兩條邊并交換路徑以提升算法的局部搜索性能,示例見圖2。
比較子路徑ab+cd和ac+bd,如果ab+cd>ac+bd則交換,否則就不交換。考慮到程序的運行效率,不可能對每對邊都做檢查,所以選取染色體中的一定數量的邊進行比較。2-Opt搜索算子實際上進行的相當于變異操作,同時又不僅僅是簡單的變異,而是提高算法的局部搜索性能的變異操作。
2.3選擇機制和收斂準則
為了限制種群的規模[13],該文采用了聯賽選擇法的淘汰規則。聯賽選擇法就是以各染色體的適應度作為評定標準,從群體中任意選擇一定數目的個體,稱為聯賽規模,其中適應度最高的個體保存到下一代。這個過程反復執行,直到保存到下一代的個體數達到預先設定的數目為止。這樣做可能導致種群過早收斂,因此在收斂準則上要采取苛刻的要求來保證搜索的全局性。
遺傳算法求TSP問題如果不設定終止條件,其演化過程將會無限制地進行下去。終止條件也稱收斂準則,因為多數最優化問題事先并不了解最優的目標函數值,故無法判斷尋優的精度。該文采用如下兩條收斂準則:在連續K1代不再出現更優的染色體;優化解的染色體占種群的個數達K2的比例以上。當兩準則均滿足時,則終止運算,輸出優化結果和對應的目標函數值。由數值實驗表明,添加第2條準則之后,全局最優解的出現頻率將大為提高。
2.4基于多重搜索策略的群體演化算法
由于基因庫的引入,可能降低初始種群的多樣性,為避免算法陷入局部最優解,因此在群體演化中采取多重搜索策略。由Cheng-FaTsai提出的多重搜索策略[6],就是把染色體集中的染色體分成保守型和探索型兩種不同類型的集合,然后針對不同類型的染色體集合根據不同的交叉、變異概率分別進行交叉變異操作,對保守型染色體集合就采用比較低的交叉變異概率,而對探索型染色體集合就采用比較高的交叉變異概率。這種策略對保守型染色體集合的操作最大限度地保留了父代的優秀基因片段,另一方面對探索型染色體集合的操作又盡可能地提高了算法的全局搜索能力。為了提高算法的收斂速度,初始染色體集合該文采用了前面單親演化的結果中的染色體集合,交叉算子則利用的是前面介紹的改進后的算子,改進后的多重搜索策略見下。
3實驗結果與分析
該文的GB—MGA算法由C#編程實現,所有的結果都是在P42.0G微機上完成,并進行通用的TSP庫實驗,選用了具有一定代表性的TSP實例,并把該算法和其他算法做了一個對比。為了減少計算量,程序中的數據經過四舍五入整數化處理,與實數解有一定的偏差,下面給出圖Kroa100的示例。
為了證明該文提出的GB—MGA算法的有效性,將該文算法與典型的遺傳算法GA、單親遺傳算法PGA以及文[5]中楊輝提出的Ge—GA(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都進行了一個對比。
實驗結果證明,該文算法的求解質量要優于GA、PGA、MMGA算法,而求解速度方面則優于Ge—GA算法,特別是對于大規模城市的TSP問題求解效果尤其明顯,具有快速收斂的特性。Ge—GA算法對于中等城市規模的TSP實例求解,其運算時間就大幅度增加,如果把該算法用于求解大規模和超大規模TSP問題,那么時間上的代價就讓人無法忍受。而該文的GB—MGA算法在單親遺傳演化中就使用了基因庫中的優質基因,使得單個個體的進化速度大大提高,從而為進一步的演化提供了條件,群體演化過程的選擇機制和收斂準則的恰當選取使得算法在注重了求解質量的同時兼顧了算法的效率。
4結束語
關鍵詞遺傳算法；TSP；交叉算子
1引言
遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法?？偟恼f來，遺傳算法是按不依賴于問題本身的方式去求解問題。它的目標是搜索這個多維、高度非線性空間以找到具有最優適應值(即最小費用的)的點[1]。
基本遺傳算法是一個迭代過程，它模仿生物在自然環境中的遺傳和進化機理，反復將選擇算子、交叉算子和變異算子作用于種群，最終可得到問題的最優解和近似最優解。
2遺傳算法程序設計改進比較
2.1基本遺傳算法對TSP問題解的影響
本文研究的遺傳算法及改進算法的實現是以C++語言為基礎，在Windows2000的版本上運行，其實現程序是在MicrosoftVisualStadio6.0上編寫及運行調試的。
1)遺傳算法的執行代碼
m_Tsp.Initpop()；//種群的初始化
for(inti=0；i<m_Tsp.ReturnPop()；i++)
m_Tsp.calculatefitness(i)；//計算各個個體的適應值
m_Tsp.statistics()；//統計最優個體
while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)
{
//將新種群更迭為舊種群，并進行遺傳操作
m_Tsp.alternate()；//將新種群付給舊種群
m_Tsp.generation()；//對舊種群進行遺傳操作，產生新種群
m_Tsp.m_gen++；
m_Tsp.statistics()；//對新產生的種群進行統計
}
2)簡單的遺傳算法與分支定界法對TSP問題求解結果的對比
遺傳算法在解決NPC問題的領域內具有尋找最優解的能力。但隨著城市個數的增加，已沒有精確解，無法確定遺傳算法求解的精度有多高。一般情況下，當迭代代數增大時，解的精度可能高，但是時間開銷也會增大。因此可以通過改進遺傳算法來提高搜索能力，提高解的精度。
2.2初始化時的啟發信息對TSP問題解的影響
1)初始化啟發信息
在上述實驗算法的基礎上，對每一個初始化的個體的每五個相鄰城市用分支界定法尋找最優子路徑，然后執行遺傳算法。
2)遺傳算法與含有啟發信息的遺傳算法求解結果的對比
當城市數增至20個時，用分支定界法已經不可能在可以接受的時間內得到精確的解了，只能通過近似算法獲得其可接受的解。試驗設計中算法的截止條件：固定迭代1000代。表2中的平均最優解為經過多次試驗(10次以上)得到的最優解的平均值，最優解的出現時間為最優解出現的平均時間，交叉操作次數為最優解出現時交叉次數的平均值。
表220個城市的TSP問題求解結果數據
算法交叉操作
次數最優解
出現時間平均
最優解
簡單遺傳算法80244.479.4s1641.8
含初始化啟發信息的GA79000.237.4s1398.9
從表2中可以看出，當初始種群時引入啟發信息將提高遺傳算法的尋優能力。同時縮短了遺傳算法的尋優時間和問題的求解精度。
2.3交叉算子對TSP問題解的影響
1)循環貪心交叉算子的核心代碼
for(i=1；i<m_Chrom；i++)
{
flag=0；
city=m_newpop[first].chrom[i-1]；//確定當前城市
j=0；
while(flag==0&&j<4)
{
sign=adjcity[city][j]；//adjcity數組的數據為當前城市按順序排列的鄰接城市
flag=judge(first，i，sign)；//判斷此鄰接城市是否已經存在待形成的個體中
j++；
}
if(flag==0)//如果所有鄰接城市皆在待擴展的個體中
{
while(flag==0)
{
sign=(int)rand()/(RAND_MAX/(m_Chrom-1))；//隨機選擇一城市
flag=judge(first，i，sign)；
}
}
if(flag==1)
m_newpop[first].chrom[i]=sign；
}
2)問題描述與結果比較
下面筆者用經典的測試遺傳算法效率的OliverTSP問題來測試循環貪心交叉算子的解的精度和解效率。OliverTSP問題的30個城市位置坐標如表3所示[2]。
從表4、圖1中可以看到，貪心交叉算子大大提高了遺傳算法的尋優能力，同時也降低了交叉操作次數。在多次試驗中，貪心交叉算子找到的最優解與目前記載的最佳數據的誤差率為2.7%。而部分匹配交叉算子找到的最優解與目前記載的最佳數據的誤差率高達7%。從而可以得到交叉算子對于遺傳算法
2.4并行遺傳算法消息傳遞實現的核心代碼
1)主程序代碼
//接收各個從程序的最優個體
for(i=0；i<slave；i++)
{
MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；
}
//計算接收各個從程序的最優個體的回路距離
for(i=0；i<slave；i++)
{
fitness[i]=0.0；
for(intj=0；j<chrom-1；j++)
fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom[i][j+1]]；
fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom[i][chrom-1]]；
}
//找到最優的個體并把它記錄到文件里
for(i=0；i<slave；i++)
{
if(1/fitness[i]>min)
{
sign=i；
min=1/fitness[i]；
}
}
fwrite(&gen，sizeof(int)，1，out)；
for(i=0；i<chrom；i++)
fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；
fwrite(&fitness[sign]，sizeof(double)，1，out)；
//每九代向從程序發送一個最優個體
if(gen%9==0)
MPI_Bcast(Rchrom[sign]，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；
2)從程序代碼
//將上一代的最優個體傳回主程序
MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；
//每九代接收一個最優個體并將其加入種群中替換掉最差個體
if(gen%9==0)
{
PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；
Tsp.IndiAlternate(Rchrom2)；
}
//進行下一代的計算
Tsp.Aternate()；
Tsp.Generation()；
Tsp.Statistics()；
3)并行遺傳算法的性能
筆者在MPI并行環境下，用C＋＋語言實現了一個解決TSP問題的粗粒度模型的并行遺傳算法。該程序采用的是主從式的MPI程序設計，通過從硬盤的文件中讀取數據來設置染色體長度、種群的規模、交叉概率和變異概率等參數。試驗環境為曙光TC1700機，測試的對象是OliverTSP問題的30個城市的TSP問題。
正如在測試串行遺傳算法所提到的數據結果，并行遺傳算法也沒有達到目前所記錄的最好解，但是它提高了算法的收斂性，并行遺傳算法的收斂趨勢如圖2所示[4]。
圖2遺傳算法的收斂過程
3結束語
本文通過對基本遺傳算法的不斷改進，證明了添加啟發信息、改進遺傳算子和利用遺傳算法固有的并行性都可以提高遺傳算法的收斂性，其中對遺傳算法交叉算子的改進可以大大提高遺傳算法的尋優能力。
參考文獻
[1]劉勇、康立山，陳毓屏著．非數值并行算法－遺傳算法．北京：科學出版社1995.1
[2]IMOliverDJSmithandJRCHolland，Astudyofpermutationcrossoveroperatorsonthetravelingsalesman[C]//ProblemofthesecondInternationalConferenceonGeneticAlgorithmsandTheirApplication，Erlbaum1897：224-230
關鍵詞：遺傳算法，混沌，圖像分割
0引言
遺傳算法是一種全局優化搜索算法，它使用了群體搜索技術，用種群代表一組問題解，通過對當前種群施加選擇、交叉和變異等一系列遺傳操作，從而產生新的一代種群，并逐漸使種群進化到包含最優解或近似最優解的狀態。近幾年來借助于混沌改進遺傳算法的性能是遺傳算法領域研究的熱點之一，遺傳算法和混沌優化的組合,可以使遺傳算法的全局尋優能力，搜索精度，搜索速度等幾方面得到較明顯的改進。
1混沌的特征和蟲口方程
混沌是存在于非線形系統中的一種較為普遍的現象，具有遍歷性、隨機性等特點，混沌運動能在一定的范圍內按照其自身的規律不重復地遍歷所有狀態。因此，如果利用混沌變量進行優化搜索，無疑會比隨機搜索更具有優越性?？萍颊撐?。
描述生態學上的蟲口模型Logistic映射自May于1976年開始研究以來，受到了非線形科學家的高度關注，Logistic映射是混沌理論發展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遺傳算法
基于混沌遺傳算法的二維最大熵算法基本步驟如下：
1.設置混沌遺傳算法的種群規模以及最大進化代數；
2.生成初始群體。隨機產生S 和T ,其中, S ,T ∈(0 ,1) 。然后利用式
計算每個個體的適應值。式（2-1）中的s 和t 分別由以下公式確定：s =(int)( S*255) ，t = (int)(T*255) 。對初始種群執行混沌擾動，如果在C1 步之內找到更優個體，則替換原來的個體，否則保留原個體。科技論文?；煦鐢_動方式按式(1-1)進行。
3.如果當前進化代數大于G，轉步驟5，否則執行變異操作。變異方式按如下公式進行：
其中，fRandom()產生（0,1）之間的隨機數，如果變異后的個體具有更優的適應值,則把該個體加入當前種群；
4.執行混沌操作。如果在C2 步之內找到更優解,則替代原來的個體, 否則保留原個體?；煦鐢_動按公式(1-1)進行。結束后轉步驟6。
5. 在較小范圍內執行混沌擾動。擾動方式：
其中m1,m2為混沌變量，且m1,m2∈（0,1）。如果變異后的個體具有更優的適應值, 則替換原來的個體,否則保留原個體。
6.按規定的種群規模直接選擇最優個體進入下一代。
7.如果滿足終止條件, 返回最優解, 否則從步驟3重復上述過程。
8.利用最優解分割圖像。
3實驗結果與分析
為了檢驗本算法的效果，用文中提出的基于混沌遺傳算法（以下簡稱為B算法） 和基于傳統遺傳算法的二維最大熵算法（以下簡稱為A算法）對Couple.bmp 圖像進行了實驗比較。科技論文。當文中算法和基于傳統遺傳算法的二維最大熵算法中各取最大進化代數為10 時,分割效果如圖3、4所示。
圖1 Couple 原圖圖2 Couple圖像直方圖
圖3 A算法結果圖圖4 B算法結果圖
4結論
混沌遺傳算法是混沌思想與遺傳算法思想的結合，比傳統遺傳算法具有更好的群體多樣性、更強的全局尋優能力。文中將混沌遺傳算法與二維最大熵圖像分割算法結合，應用于圖像分割，對比于基于傳統遺傳算法的二維最大熵算法，文中算法具有更強的穩定性,更快的執行速度，分割效果好。
參考文獻
[1]吳薇，鄧秋霞，何曰光．基于免疫遺傳算法的圖像閾值分割．紡織高?；A科學學報，2004，17(2)：160-163
[2]薛景浩，章毓晉，林行剛．二維遺傳算法用于圖像動態分割．自動化學報，2000，26(5)：685-689
[3]王小平，曹立明．遺傳算法－理論、應用與軟件實現．西安交通大學出版社．2002
【關鍵詞】自動導航小車；路徑規劃；免疫遺傳算法；疫苗
1、引言
目前，為使移動機器人規劃出良好的去去路徑，所用的方法很多，如柵格法[1]、勢場法[2]、可視圖法[3]等。但各種方法有其使用局限。人工智能的發展為AGV的路徑規劃提供了新思路，產生了諸如神經網絡學習法、遺傳算法等方法。這些算法在一定程度上解決了AGV的路徑規劃問題，但也有其缺陷。如神經網絡學習法對于復雜環境難以數學建模，范化能力差；模糊法靈活性差。遺傳算法在迭代過程中，個體在進化過程中不可避免地會產生退化。受生物免疫系統的啟發，論文將免疫引入到遺傳算法中，在保留遺傳算法優點的情況下，利用待求問題的一些特征信息，采用免疫方法所具有的識別、記憶等功能來抑制遺傳算法在進化中所出現的退化現象。本文所設計的基于免疫遺傳算法的AGV路徑規劃方法利用AGV在移動過程中的特殊信息對所選路徑進行優化，可較快地使AGV根據環境信息搜索一種滿意的路徑，提高了AGV路徑規劃的智能性。
2、環境信息建模
對AGV進行路徑規劃前，應解決對其環境信息的描述即環境建模問題。為此，作以下假設[3]：
（1）AGV在二維平面中運動，不考慮其高度方向的信息；（2）規劃環境的邊界及其內所有障礙物（妨礙AGV運動的所有物體）用凸多邊形表示。（3）考慮到AGV的大小等，對環境邊界進行縮小和對障礙物進行擴大時，其縮放量為AGV外形最大尺寸的一半。即AGV為“點機器人”。
至此，AGV的工作空間可描述為：工作平面和障礙物群{Oi|i=1，2…N}。具體到其個障礙物Oi，可描述為Oi={頂點1坐標（xi1， yi1），….. 頂點n坐標（xni， yni）}。為方便數據處理，對多邊形頂點沿順時針方向編號。起點為S，終點為E。工作平面可表示為矩形{（Xmin，Ymin），（Xmax，Ymax）}。
設在AGV的工作環境中有n個已知的障礙物Oi（i=1，2，...，n），對應的頂點數為Si，頂點坐標為（x（i，j），y（i，j））（j=1，2，…Si）。為描述AGV工作環境中的障礙物，采用Dm×m矩陣對環境信息進行描述，其中，m為障礙物頂點總數。定義d（i，j）為：
3、免疫遺傳算法設計
3.1路徑編碼方式
采用免疫遺傳算法求解最優問題的關鍵是對所求問題的解進行編碼。編碼的長度與搜索空間的大小及求解精度有直接關系，也影響算法的效率。對AGV進行路徑規劃時，傳統的二進制或實數編碼方式都不適用。本文設計了一種自適應變長度實數數組編碼方式，即第p代Xp的第k條染色體Xkp的第j位基因Xkp（j）表示為Xkp（j）=|io，xk，yk|T，其中io為障礙物序號，（xk，yk|）為第io號障礙物的某頂點坐標。由于路徑的起點為AGV的起始點，終點為其目標點，在路徑規劃時可省去以縮短染色體的長度。定義，AGV的可能運動路徑由數條直線段組成，相鄰兩直線段的交點稱為AGV的路徑拐點。為使AGV不穿越障礙物運動，基于對工作規劃空間建模時所作的假設，AGV可沿多邊形障礙物的邊界線移動，也可以障礙物的頂點為拐點在自由空間中移動。染色體即AGV的某行路徑Xkp為Xkp={Xkp（1）， Xkp（2），…， Xkp（nkp）}，其中nkp為第p代中第k條染色體的長度，每代中各條染色體長度不同。
3.2適應度函數
在對AGV進行路徑規劃時，其優化目標為在所有可能的運動路徑Xp={Xkp|k=1， 2，…，N}中找出一條最優或次優路徑。設某個體Xkp的路徑長度Dk為：
其中dj為Xk中各直線段軌跡長。因為AGV由一直線軌跡向另一直線軌跡過渡時運動速度的變化會影響其運行時間，因此，在對所選路徑進行評價時，除考慮其總長度外，可要求路徑中的拐點數盡可能的少或AGV的姿態角變化量盡要能的小。本論文的路徑規劃目標是路徑短且拐點較少。定義適應度函數為：
式中，和為調整系數。這里取=0.8，=0.2。N為種群大小，Dj為種群中第j個體的路徑長度，nj為第j個體路徑拐點數。
3.3算法的實現
在進行路徑規劃時，首先判斷AGV從起點向終點沿直線軌跡運動時是否穿越障礙物。若無障礙物，兩點間的連線為AGV的最佳運動路徑，無須進行路徑規劃。否則進行路徑規劃。
免疫遺傳算法中，疫苗是根據待求問題的先驗知識構造的最佳個體基因的估計，抗體是根據疫苗將某個體基因進行修正后所得到的新個體。論文所設計的基于免疫遺傳算法的路徑規劃過程如下：
（1）根據問題從記憶抗體庫中提取問題的抗體P得到初始種群 ，不足N個時在AGV起始點和目標點之間隨機產生N-P條路徑。個體的產生方法是：以包圍AGV的起點、終點和所有在線障礙物的最小矩形為規劃區域，在規劃區域內的障礙物頂點個數為M，在線障礙物為m，則染色體的最大長度為M-m。以規劃區域內的障礙物頂點為被選對象，沿一定的條件隨機選取基因位上的基因組成一條染色體，同用樣的方法產生其它染色體以組成群體。
（2）根據先驗知識抽取疫苗H={h1， h2， …， hm}；
（3）計算第p代種群Ak所有個體的適應度，并進行終止進化判斷。
（4）對當前群體Xp進行遺傳算子操作得到子代群體Bp。進行交叉操作時，采用單點交叉。交叉操作時，兩個個體若有相同的基因（而非等位基因）進行交叉操作。當相同基因位不止一個，隨機選擇其一進行交叉；當無相同基因位則不進行交叉。進行變異操作時，從個體中隨機刪除一基因位或隨機選取一基因位插入一新基因位，或在個體中隨機選取一基因位用另一隨機產生的基因位交換。
（5）對子代Bp進行免疫操作，得到新代Xp+1；接種疫苗和免疫選擇是免疫算法的主要操作，接種疫苗是為了提高個體的適應度，免疫選擇是為了防止個體的退化。接種疫苗即從Bp中按比例K隨機抽取Nk=KN個個體Bip（i=1，2，…，Nk），并按先驗知識修改Bip（這時就變為抗體），使其以較大的概率具有更高的適應度。接種疫苗時，若Bip已經是最佳個體，則其以概率1轉移為Bip。對路徑規劃，接種疫苗就是對所選個體進行判斷：首先，相鄰兩點間能否使AGV無障礙的沿直線運動；其次，任意兩點間能否使AGV無障礙的沿直線運動？條件滿足，則刪除中間點。免疫選擇分兩步完成：免疫檢測和退火選擇。免疫檢測即對抗體進行檢測，若出現適應度下降，此時由父代個體代替其參加競選，退火選擇即以概率P（Bip）在當前子代中進行選擇：
其中，為適應度函數；Tk是單調遞減趨于0的退火溫度控制序列，Tk=ln（T0/k+1），T0=100，p是進化代數[3]。
（6）選擇個體進入新的群體。更新抗體庫，并轉到第（3）步。
4、仿真實驗
仿真是在Matlab6.1上進行的。AGV的工作環境大小為8×6m2，其內有6個形狀各異、排列任意的障礙物（如圖2所示），現欲使AGV從S點無碰撞地運動到E點且使其運動路徑最短，建立如圖4所示的可視圖。其可視矩陣如左圖：
論文采用所設計的路徑規劃方法和現有的遺傳和免疫算法對AGV進行路徑規劃以尋找最佳路徑。取遺傳操作中的交叉概率Pc=0.8，變異概率Pm=0.2，免疫操作中的接種疫苗概率Pv=0.6，初始種群大小為N=20，抗體庫M=5，遺傳代數不超過K=200。圖3為路徑規劃的最佳路徑。進化過程中適應度變化和路徑長度變化如圖4所示。
由仿真結果知，采用免疫遺傳算法進行路徑規劃時，退化現象基本不會發生，再能很快得到問題的最優解。其原因是，利用免疫遺傳算法對AGV進行路徑規劃，一方面利用了遺傳算法的優點，由于是對編碼進行操作，對問題的依賴性小，且操作是并行進行，優化速度快；同時針對遺傳算在進行交叉和變異操作時是以以概率方式隨機地、缺泛指導性地進行導致問題進化時產生退化的現象，采用適當的指導，彌補了遺傳算法的缺點。利用遺傳免疫算法進行優化，在保證算法收斂的前提下，有效地提高計算速度。利用此法對AGV的路徑進行規劃，比其它的方法更有效。
5、結論
論文主要針對環境建模和路徑搜索兩大問題進行了研究?；诳梢晥D環境建模方法優點，完成了對環境信息的建模。并結合遺傳和免疫算法的優點設計了具有精英保留策略的基于免疫遺傳算法的AGV路徑規劃方法。通過比較采用遺傳算法、免疫算法和本論文所設計的免疫遺傳算法對AGV進行路徑規劃結果和效率的比較，分析了所提出的基于免疫遺傳算法的AGV路徑規劃方法的優點。仿真結果表明：
A.本論文采用改進的可視圖法對環境信息進行建模，在改變障礙物位置、形狀、大小和AGV的起點及終點的情況下，均可快速構建AGV的環境信息模型。
B.采用本論文所設計的基于免疫遺傳算法的AGV路徑規劃方法對AGV進行路徑規劃，在速度方面優于傳統的免疫算法和遺傳算法，且系統退化現象基本得到消除。
參考文獻
[1]吳鋒，楊宜民.一種基于柵格模型的機器人路徑規劃算法[J].現代計算機（專業版），2012，4（3），7-9，13.
[2]沈鳳梅，吳隆.基于改進人工勢場法的移動機器人自主導航和避障研究[J].制造業自動化，2013，35 （12），28-30，39.
[3]李善壽，方潛生，肖本賢.全局路徑規劃中基于改進可視圖法的環境建模[J].華東交通大學學報，2008，25（6），73-77.
作者簡介
關鍵詞：自動排課；遺傳算法；求解與優化
中圖分類號：TP301 文獻標識碼：A
排課問題在學校教學管理中十分重要，它是一個有約束的、多目標的組合優化問題，并且已經被證明為是一個NP完全問題。由于涉及信息較多且求解比較復雜資源的最優化配置不容易實現，因此使用計算機對排課信息進行管理，能夠極大地提高學校教務管理的效率，也是各種體制學校管理科學化、現代化的重要條件。現在大多數的排課系統是以編程語言為實現語言，采用各種算法為實現手段，比如遺傳算法、回溯算法、模擬退火算法等。作為對排課問題的探索，本文采用遺傳算法的思想，提出一個課表方案的隨機生成和優化算法，以期能夠較大程度地反映實際排課情況和盡量達到多個目標最優。
1 排課問題分析
1.1 排課問題的因素
從手工排課的過程看出，排課問題需要考慮的條件很多，如周課時設置、課程信息、班級信息、教師信息、教室信息等等。從排課過程可能引起潛在沖突的角度，可以將排課問題涉及的因素考慮如下：
時間：在排課問題中涉及關于時間的概念有學年、學期、周、天、節。
課程：每個課程都有自己的編號、名稱。每個課程都有指定的教師、教室等。某些課程由于上課班級較多難以協調或照顧教師要求等諸如此類原因，應該預先給定時間或教室。
教室：每個教室都有編號、門牌號和名稱。每個教室在同一時間內只能接納一門課程的授課，并且教室容量應該大于等于上課的人數。
班級：每個班級都有編號和名稱。每個班級同一時間只能上一門課程。
教師：每個教師都有編號和姓名。每個教師同一時間只能上一門課程。
1.2 排課過程的約束條件
排課是將教師與學生在時間和空間上根據不同的約束條件進行排列組合，以使教學正常進行。避免排課因素發生沖突是排課問題中要解決的核心問題。只有在滿足全部約束條件和避免沖突的基礎上，才能保證整個教學計劃合理正常進行。而對教師、教室、學生及時間等資源進行最優化組合配置，才能保證充分發揮各資源的優勢和提高教學質量。
排課過程中常見的約束條件如表1所示：
1.3 排課問題的目標實現
排課問題是一個多目標的組合規劃問題，要想制定出一個“合理、實用、有特色”的課表，必須保證所有的約束條件都不發生沖突。一套高質量的課表，在時間、教室資源、課程安排等很多方面都應該做到科學的安排，并且應該具有人性化的考慮。課表編排問題的難點在于：保證課表在時間及人員的分配上符合一切共性和個性要求，在此基礎上，所有的課程都能夠安排合適的時間和教室，使安排方案在各個目標上盡量達到全局最優。
遺傳算法是1975年美國MIChiga大學的John.H.Holland教授及其學生們根據生物進化的模型提出的一種優化算法。作為一種隨機的優化與搜索方法，遺傳算法有兩個主要特性：1智能性。即遺傳算法在確定了編碼方案、適應值函數及遺傳算子以后，算法將利用演化過程中獲得的信息自行組織搜索。適應值大的個體具有較高生存概率，它是具有“潛在學習能力”的自適應搜索技術。2并行性。由于遺傳算法采用種群的方式組織搜索，從而可以同時搜索解空間內的多個區域，并相互交流信息，這種搜索方式使得遺傳算法能以較少的計算獲得較大的收益。正是由于遺傳算法的這兩個特性，使得遺傳算法迅速被運用于求解組合優化的排課問題，且操作簡單，可以更少地依賴于實際問題的情況，實現課表的優化。
2 遺傳算法在課表編排中的應用
2.1 遺傳算法的基本原理
遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。一般的遺傳算法都包含三個基本操作：復制、交叉、變異。
2.1.1 復制，是從一個舊種群中選擇生命力強的個體字符串產生新種群的過程。復制操作過程中，目標函數是該字符串被復制或被淘汰的決定因素。遺傳算法的每一代都是從復制開始的。
2.1.2 交叉，在由等待配對的字符串構成的匹配池中，將新復制產生字符串個體隨機兩兩配對，然后隨機地選擇交叉點，對匹配的字符串進行交叉繁殖，產生一對新的字符串。
遺傳算法的有效性主要來自復制和交叉操作，尤其是交叉在遺傳算法中起著核心的作用。
2.1.3 變異，遺傳算法中，變異就是某個字符串某一位的值偶然的隨機的改變，即在某些特定位置上簡單地把1變成0，或反之。變異操作可以起到恢復字符串字符位多樣性的作用，并能適當地提高遺傳算法的搜索效率。
2.2 遺傳算法在課表編排中的設計
使用遺傳算法編排課表，我們把課程和老師當作同一變量考慮，這樣編排課表只需將教師編碼排入周課表，在以后打印課表時，將教師編碼改為課程名即可。于是我們設計以下步驟：對每一門任課教師進行編碼；使用二維數組來構成初始群體；沖突的檢驗和消除；定義課表的適應度函數(x)(x∈{1,2,…,N}),其中x表示個體在群體中的位置。當函數值為0時，即找到了本次優化過程的最優值；復制操作：按照適配值計算選擇率和期望的復制數；交叉操作：將種群中的個體配對產生的交叉點再分別交換；變異操作：將隨機產生的同列的兩個位置互換；再次進行沖突檢測和消除，直至無沖突存在。
2.3 算法的實現
遺傳算法結束后，可以得到綜合效率函數值最好的個體。根據這個結果，即可生成相應的課程表。系統的流程分為以下幾個主要的過程：（1）初始種群的產生：形成本學期教學信息二維表，對教師編碼；產生染色體。（2）對各類沖突進行檢測，如存在沖突則消除它。（3）計算適應度函數值、期望值及其復制數。（4）進行遺傳操作。（5）可行課程表的產生。
這樣，我們就有了一個課程表的數據庫表。因此，可以打印其中某一班級的課程表或全校的課程表了。
結論
本文采用遺傳算法來對課表編排問題進行求解，是求解這種難解的組合優化問題方法中較明智的選擇，目的是在遺傳算法基礎上提出一個課表方案的隨機生成和優化方案，能夠較大程度地實現課表編排和多個目標的最優化。本文算法對我們這類院系較多、教師工作量大、學科變化較大、不確定性較多的學校能有所借鑒。
參考文獻
[1]安勐.遺傳算法在排課問題求解中的應用[J].銅仁學院學報，2009，11（2）：135-139.
摘 要：文章將遺傳算法應用于倉儲管理調度系統的儲位分配過程，分析了基本遺傳算法應用于儲位分配的優缺點。通過采用精英保留策略，保證了基本遺傳算法設計的多樣性，實現了算法搜索的快速收斂和最優性能保持，克服了基本遺傳算法的“返祖”現象。
關鍵詞：改進遺傳算法；精英保留策略；儲位分配
中圖分類號：F252.13 文獻標識碼：A
Abstract： This thesis applies genetic algorithm into the storage allocation process of warehouse management dispatching system， and analyzes the advantages and disadvantages of applying genetic algorithm into storage allocation. By adopting elitism-reserved strategy， it has ensured the diversity of the basic genetic algorithm design， realized the fast convergence and optimal performance of algorithmic search， and has overcome the“atavism”phenomenon of basic genetic algorithm.
Key words： improved genetic algorithm； elitism-reserved strategy； storage allocation
1 研究背景
隨著經濟的全球化，給很多跨國公司帶來前所未有的發展機遇，也給物流行業帶來新的發展契機。在國內，電商企業如雨后春筍般的發展勢頭一個比一個好，也帶動物流業快速發展，與電商發展亦步亦趨，相輔相成。倉儲是物流的關鍵環節之一，只有擁有先進的倉儲管理系統，具備完善的倉儲調度策略，才能在當前激烈的市場競爭中不斷發展壯大。
眾多學者認為，當前世界經濟處于經濟危機后深度調整中，我國經濟發展也在轉型中跨入新常態。就物流業當前面臨的形勢來看，物流業的地位正處于快速發展機遇期，也意味著這一時期將是我國物流業發展的完善期和物流發展的拓展期。通過研究該領域的動態，不難發現我國物流業有以下幾種發展趨勢：
（1）物流平臺開始嶄露頭角，合同物流或將逐漸退出
為了追求利益的最大化，物流業勢必面向平臺化整合，以替代合同物流。伴隨著電子商務的蓬勃發展，新的互聯網經濟將傳統的TOB業務變革成TOC業務，這種散碎的物流服務是促進物流平臺建設的有利基礎。
（2）在大數據的作用下，物流數據將成為新的價值點
從馬云對菜鳥的定位來看，“菜鳥”通過利用和整合獲得的數據和信息，找到新的物流成本壓縮點。合理分配存儲區域，去除物流發展資源利用不充分的大屏障。
從小的方面來看，做好倉儲內部調度，合理安排貨物儲位也是適應物流業發展的需要。因此本文利用遺傳算法，研究貨物上下架的優化策略，通過改進遺傳算法的搜索策略，快速實現貨物上下架調度。
2 遺傳算法的基本理論
遺傳解釋了生物能夠延續并不斷進化的內在機理及其規律，而遺傳算法正是誕生于生物科學和計算機科學的交叉點。將遺傳進化的某些特質，融合在計算機編程和算法的設計之中，應用于工業控制、管理優化等諸多方面。
2.1 遺傳算法的基本原理
遺傳算法（Genetic Algorithm，GA）是由美國密歇根（Michigan）大學心理學教授、電子工程和計算機科學教授Holland提出的一種隨機自適應全局搜索算法。這種算法模擬的自然界生物遺傳進化過程，對優化問題的最優解（近似解）進行不斷的迭代搜索。算法在維護一個潛在解的集合（群體），對群體進行優化，在優化過程中，算法引入了選擇、交叉、變異等遺傳算子。而遺傳算法在搜索全局最優解過程中，是一個不斷迭代的過程（每次迭代相當于自然界生物遺傳的一次進化），直到算法滿足終止條件為止。
2.1.1 相關概念
（1）染色體
一個染色體是問題的一個有效解。相對于生物群體中的一個個體。遺傳算法的每個染色體，又由多個基因組成。如果將求解問題簡化稱一個y=fx的函數，那么染色體就可以看作變量x的取值。
（2）基因
可以認為是問題的一個有效解的某一維的值。它的改變會改變一個染色體的適應值，但一般不會引起整個種群發生太大變化。如果x的值由一段編碼組成，那么一個編碼序列可以看作是一個基因。
（3）適應值
適應值是用來表征一個染色體在群體中的優劣程度。一般來說，一個染色體的值越大，該染色體離最優解就越“近”。適應值就可以看作是這個函數y=fx的應變量y。
（4）評價函數
評價函數是用來計算一個染色體的適應值的大小，判斷染色體優劣的一個手段。對應一個函數y=fx的對應法則f。
（5）選擇算子
在對群體中若干個染色體進行篩選時，需要依據一定的規則，選出一些適應值較好的染色體進入下一代。那么如何選擇，才能讓更多、（適應值）更好的染色體從當前過度到下一代，同時保證染色體分布不失均勻，這就取決于選擇算子。
（6）交叉算子
在對兩個染色體作用時，交換兩個染色體的部分基因，希望交換后，能從新的得到的染色體中能產生適應值更好的一個或兩個染色體。為此而設計染色體概率性的交換基因片段的一個過程，使得算法能具備良好的全局搜索最優解的能力。
（7）變異算子
對比交叉算子，那么使染色體的某個基因發生變化，可以讓算法具備較好的具備搜索最優解的能力。
通常，傳統方法在求解某類優化問題采用的都是分析問題的某些特質，簡化問題的約束，針對該問題的特質來求解。而Holland教授提出的遺傳算法的基本思想，卻不是去分析待求解問題的特質，而是采用一種泛化的求解原則。
2.2 遺傳算法的基本流程
設計實現遺傳算法，通常有以下幾個比較重要的步驟：
（1）對群體進行初始化：包括選擇適當規模的群體，每個染色體的編碼方式，設計準確的適應度評價函數。
（2）群體適應值評價：用評價函數計算染色體適應值，并按照適應值的優劣，對染色體進行排序。
（3）選擇種群進入下一代：利用設計好的選擇算子，選出適應值較優秀的染色體進入下一代。
（4）交叉操作產生新的染色體：利用交叉算子，產生一些新的染色體。一個染色體通過評價函數的計算，會對應一個適應值。而交叉操作一般設計成不定向的，故交叉操作等可能產生適應值更差的染色體。
（5）變異操作產生新的染色體：利用變異算子，產生一些新的染色體，但是相比較交叉操作，變異后的新染色體，其適應值可能變化不是特別大。
3 遺傳算法的應用于倉儲優化
現代物流的競爭力在于：如何向客戶提供更優質的服務，即服務效率高、物流過程安全。倉儲物流是物流的關鍵環節之一。本文重點研究倉儲物流的優化，將智能算法引入倉儲物流過程中，實現對現有貨位的合理規劃。
現假設需將10個貨物堆放至一個規格為10×20的空貨架中，堆垛機事先通過3D標簽獲得了各類貨物的進出庫頻次和各個貨物的質量。通常來說，我們在貨物入庫時會考慮一些因素：如質量較大的貨物放置在貨架的底層，有利于貨架重心保持穩定。進出庫頻次較高的貨物放置在靠近出入巷道的位置，同時盡量放置在貨架的底層。
貨物的質量和出入庫頻次如表1所示。
3.1 算法實現
（1）種群初始化
初始化產生一個擁有40個個體的種群pop，每個個體的特點就是10個貨物隨機散落在該10×20的貨架中。
5 結 論
對比采用精英保留策略和未采用該策略的10次運行結果，重復10次，計算最佳適應值個體的平均值分別為705.8和765.4，平均減小7.78%。從圖5也能直觀看出，采用精英保留策略得到的最佳適應值個體的優化值基本優于策略使用前的結果值。因此，通過采用精英保留策略來改進遺傳算法，不僅能使得算法在運行過程中絕對收斂（單調趨優），也能改進算法的搜索性能。
參考文獻：
[1] 侯景超. 基于改進遺傳算法的倉儲系統動態貨位優化研究[D]. 沈陽：沈陽工業大學（碩士學位論文），2014.
[2] 張飛超. 基于微遺傳算法的倉儲布局優化方法研究[D]. 錦州：遼寧工業大學（碩士學位論文），2015.
[3] 侯秋琚. 基于遺傳算法的中小型倉儲配送車輛路徑優化策略[J]. 物流技術，2014（11）：210-211，243.
關鍵詞：遺傳算法；肝臟CT圖像；圖像分割；閾值
中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2011)04-0864-02
Research on Liver CT Image Segmentation Based on Genetic Algorithm
KONG Xiao-rong1, SHI Yan-xin2, LIU Peng1
(1.Department of Computer Technology，Inner Mongolia Medical College, Huhhot 010059; 2.Department of Mathematics and Physics, Xi'an Technology University, Xi'an 710032, China)
Abstract: Genetic Algorithm (GA) is a global optimization and random search algorithm based on natural selection and genetic mechanism. It is suited to dealing with the tradition searching algorithms which cannot solve difficult and complicated problem. And it have great potentialities. First, this paper discusses fundamental principle and primary features of Genetic Algorithm. And it emphases on image segmentation based on GA. Then applying genetic algorithm to select theproper threshold, and it uses maximum entropy method to process liver CT images by segmentation methods. It obtains the results by segmentation experimentation and analyses the results.
Key words: genetic algorithm; liver CT images; image segmentation; threshold value
遺傳算法(Genetic Algorithm, GA)的基本思想來源于Darwin的生物進化論和Mendel的群體遺傳學，該算法最早是由美國Michigan大學的John Holland教授于20世紀70年代創建，之后，遺傳算法的研究引起了國際組織及學者的關注。遺傳算法通過模擬生物的遺傳進化過程形成一種全局優化概率搜索算法，提供了一種求解復雜系統優化問題的通用框架，可以不依賴于問題的具體領域[1]。近年來，遺傳算法已被廣泛應用于函數優化、組合優化、生產調度、自動控制、人工智能、人工生命、機器學習、圖像處理和模式識別等多個領域，具有巨大的發展潛力。本文主要介紹遺傳算法在醫學圖像處理方面的應用。
1 遺傳算法的基本原理
遺傳算法是模擬生物進化和遺傳機制發展起來的一種全局優化、隨機、自適應搜索算法。它模擬了自然界遺傳過程中的繁殖、和變異現象，依據適者生存、優勝劣汰的進化原則，利用遺傳算子（即選擇、交叉和變異）逐代產生優選個體（候選解），最終搜索到適合的個體。
遺傳算法的運算對象是由N個個體所組成的集合，稱為群體。遺傳算法的運算過程是一個群體反復迭代的過程，這個群體不斷地經過遺傳和進化操作，每次按照優勝劣汰的進化原則將適應度較高的個體以更高的概率遺傳到下一代，這樣最終在群體中將會得到一個優良的個體，它將達到或接近于問題的最優解[2]。
遺傳算法的求解步驟如下：
1）編碼：定義搜索空間解的表示到遺傳空間解的表示的映射，兩個空間的解需一一對應且編碼盡量簡明。遺傳算法把問題的解也稱為個體或染色體，個體通常由字符串表示，字符串的每一位稱為遺傳因子，多個個體形成一個種群。
2）初始化種群 隨機產生N個個體組成一個種群，此種群代表一些可能解的集合。GA 的任務是從這些群體出發，模擬進化過程進行優勝劣汰，最后得出優秀的種群和個體，滿足優化的要求。
3）設計適應度函數：將種群中的每個個體解碼成適合于計算機適應度函數的形式，并計算其適應度。
4）選擇：按一定概率從當前群體中選出優良個體，作為雙親用于繁殖后代，一些優良的個體遺傳到下一代群體中，適應度越高，則選擇概率越大。進行選擇的原則是適應性強的優良個體將有更多繁殖后代的機會，從而使優良特性得以遺傳。選擇是遺傳算法的關鍵，它體現了適者生存原則。
5）交叉：交叉操作是遺傳算法中最主要的遺傳操作。對于選中的用于繁殖的每一對個體，隨機選擇兩個用于繁殖下一代的個體的相同位置，在選中的位置實行交換。交叉體現了信息交換的思想。
6）變異：從群體中選擇一個個體，對于選中的個體按一定的概率隨機選擇改變串結構數據中某個串的值，即對某個串中的基因按突變概率進行翻轉。變異模擬了生物進化過程中的偶然基因突變現象，遺傳算法中變異發生的概率很低。對產生的新一代群體進行重新評價、選擇、雜交和變異。
7）終止準則：如此循環往復，使群體中最優個體的適應度和平均適應度不斷提高，直至最優個體的適應度滿足某一性能指標或規定的遺傳代數，迭代過程收斂，算法結束。
2 遺傳算法在圖像分割處理中的應用
在圖像處理中，圖像分割是圖像三維重建的基礎，常用的分割方法包括閾值法、邊緣檢測法和區域跟蹤法，其中閾值法是最常用的方法[3]。圖像閾值分割算法是利用圖像中目標物體與背景灰度上的差異，根據圖像灰度值的分布特性把圖像分為不同灰度級的目標區域和背景區域，目前已有模糊集法、共生矩陣法、四元樹法、最大類間方差法、最佳直方圖熵法、最小誤差閾值法等多種閾值分割方法。
遺傳算法在圖像分割中的作用是：幫助現存的圖像分割算法在參數空間內搜索參數，或者在候選的分隔空間內搜索最優的分隔方案[3]。在參數空間內搜索參數主要是指利用遺傳算法的全局搜索特性優化現有的閾值分割算法，用于幫助確定最佳分割閾值。
3 基于遺傳算法的肝臟CT圖像分割
本文基于遺傳算法選取閾值，采用最大熵原則對肝臟CT圖像進行分割。目的是將圖像的灰度直方圖分成兩個或多個獨立的類，使得各類熵的總量最大，根據信息論，這樣選擇的閾值能獲得的信息量最大[4]。在圖像的灰度直方圖中設定一個灰度閾值，可以把圖像分成背景和物體兩類區域，這是一般的單閾值選擇的情況，而設定N個閾值，可以把圖像分成N+1類區域[4]。
最大熵分割方法步驟為：
用p0,p1,…,pn表示灰度級的概率分布，如果把閾值設置在灰度級s，將獲得兩個概率分布，一個包含1到s間的灰度級，另一個包含s+1到n間的灰度級，這兩個分布如下：
其中，與每一個分布相關的熵為：
令: (4)
當該函數取最大值時即為圖像的最佳分割，用此函數作為遺傳算法中的適應度函數。通過遺傳算法的設計步驟，取得最佳閾值，既而對人體肝臟中有病灶組織的CT圖像進行分割，得到下面分割處理實驗結果。
(a) 原圖 (b) 分割結果(c)原圖 (d) 分割結果
圖1 對有病灶肝臟圖像進行分割
通過實驗結果可以看到，基于遺傳算法采用最大熵原則，對人體肝臟CT圖像進行分割，能夠使選取的閾值獲得的信息量比較大，從而原始圖像和分割圖像之間的信息量差異最小。因此分割后的圖像效果明顯，具有一定的優勢[5]。
但由于醫學圖像的復雜性和人體的差異性，對人體同一器官不同狀況的圖像，無法找出一種最為適合的分割方法處理，必須根據具體情況具體分析，針對圖像的特點來選取相應的分割算法，才能較好地解決問題。
參考文獻：
[1] 田瑩,苑瑋琦.遺傳算法在圖像處理中的應用[J].中國圖象圖形學報,2007,12(3):389-396.
[2] Hsieh puted Tomography Principle, Design, Artifacts and Recent Advances（中文翻譯版）[M].北京:科學出版社,2006.
[3] 徐丹霞,郭圣文,吳效明,等. 肝臟CT圖像分割技術研究進展[J].醫療衛生裝備,2009,30(3):34-36.
關鍵詞：在線測試；組卷策略；遺傳算法
中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2011)29-7217-02
Genetic Algorithm Based on the Network Test System Development and Application
GUO Shu-hua
(Guangsha College of Applied Construction Technology, Dongyang 322100, China)
Abstract: Along with the vigorous development of education and network technology, more and more courses are chosen online practice and test, so how to design and develop the online test system is paid more and more attention to. There are many commonly used test paper methods, but this paper mainly studies the test paper method based on genetic algorithm method. The purpose of this article is to realize the functions of testing paper, testing, scoring, test managing, test paper grade managing and other functions, and develop a complete set of network examination system.
Key words: online testing system; maneuvers of composing examination papers; genetic algorithm
如今，計算機技術和互聯網技術的發展日新月異，它們越來越多地滲透到社會各個領域，對當代社會產生著重大影響。隨著計算機等現代科學技術被越來越廣泛地應用以及應用水平的不斷提高，必將大大改變我們的工作方式、學習方式和生活方式。教育如何迎接現代科學技術，如何應用科學技術，以提高教學質量，培養高素質人才，已引起人們的普遍關注。近年來，我國的開放教育和網絡教育正蓬勃發展，越來越多的課程選擇在線進行練習或測試，因此如何設計和開發在線測試系統也受到越來越多的人的關注。
在線測試系統作為網絡教育系統的一個重要組成部分，作為它的一個子系統，是體現網絡教學質量的重要手段，也是實現網絡教育的關鍵環節。而在線考試系統中最重要的一個組成部分就是系統的組卷算法了。隨著信息技術和數據庫技術的高速發展，利用計算機存儲大量的試題信息并結合數據庫技術實現試題的自動組卷功能已成為一項非常實際可行并且應用性極其廣泛的課題。國外和國內的許多科研單位、學校機構等都在對組卷系統進行研究[1]。
本課題主要的研究遺傳算法的思想，并開發一套基于遺傳算法組卷的在線考試系統。系統通過遺傳算法對題庫進行編碼初始化，并通過選擇、交叉、變異的迭代過程進行組卷，同時實現學生測試，教師評分、成績查詢、試卷管理等功能。
1 算法分析
對于組卷系統來講，生成符合系統要求的一套試卷是組卷系統中一項最根本的功能要求，而運用什么樣的算法來實現抽題組卷對這個組卷系統的性能和質量來講是關鍵。自動組卷不但能最有效地把客戶的需求與計算機技術結合在一起，生成符合要求的試卷，且比較客觀、規范，使用起來也最為方便[1]。 目前，自動組卷系統根據其所使用的組卷策略大致可以分為四類[2]：
1) 隨機抽取法；2) 回溯試探法；3) 遺傳算法；4) 定性映射算法。
隨機抽取法根據狀態空間的控制指標，由計算機隨機抽取試題組成試卷。該方法實現最為簡單，不需要很高的技術支持，但具有很大的隨意性和不確定性，使生成的試卷缺少整體性和科學性，組卷的效率也比較低?；厮菰囂椒ㄓ涗涬S機產生的每一狀態類型，如果搜索失敗則將上次記錄的狀態類型進行釋放,然后采用特定的規律運用新的一種狀態類型進行回溯試探，直到試卷生成成功或退回到起點為止。回溯試探法不適合大型的題庫系統，通常適用于題型和題量都比較小的考試系統。該算法程序實現相對比較復雜，出題的隨機性比較差，試卷生成時間也比較長。定性映射算法提出了一種合理分配不同難度試題的方法[2]。這種算法首先要建立一個組卷的數學模型，同時采用多目標優化為選題依據。這種組卷算法在生成試卷的效率和成功率上有比較大的提高，是實現自動組卷的一種新途徑。但是要求建立數學模型，對數學的基礎要求比較高，同時程序結構比較復雜，算法實現比較困難。
遺傳算法（Genetic Algorithm，GA）是Michigan大學的John Holland在20世紀60年代末期到70年代初期借鑒生物界的進化規律而提出來的隨機化搜索方法，主要模擬生物進化論的自然選擇和遺傳學機理搜索出最優解的方法，遺傳算法主要的特點有并行性、通用性、自適應性、全局優化性和收斂速度快等[3]。依據遺傳算法的這些特點，將其應用到考試系統的進行自動組卷，組卷效率和質量有大幅度的提高。
2 遺傳算法研究
2.1 遺傳算法概述
遺傳算法是是近幾年發展起來的一種嶄新的借鑒生物界自然選擇和自然遺傳機制的全局優化算法，它借用了生物遺傳學的觀點，是基于群體進化的一種方法，通過自然選擇、遺傳、變異等作用機制，來提高各個個體的適應度。其思想是從一組隨機產生的初代種群中開始搜索，按照適者生存以及優勝劣汰的原理，根據問題域中個體的適應度挑選個體，并運用遺傳算子進行組合交叉、變異，產生出符合要求的種群或者達到預先設定的迭代次數為止。
遺傳算法提供了一種求解復雜系統問題的通用框架，它不依賴于問題的具體領域[3]，對問題的種類有很強的魯棒性，所以廣泛應用于許多科學，如函數優化，組合優化。此外，也在生產調度問題、自動控制、圖像處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。遺傳算法作為一種有效的強大的隨機搜索方法，有著重要的理論和實際價值。遺傳算法組卷流程圖如圖1所示。
2.2 約束條件
本系統中，編碼方式采用標準的二進制編碼，二進制位串的長度為題庫的題目數，染色體上的每一個基因代表對應的試題是否被挑選：1為該試題被挑選，0為該試題沒有被挑選，那么每一個染色體代表一組選題結果。同時在編碼的過程中將基因按題型有序排序。在初始化編碼時，通過隨機函數產生相應數目的界于1和題目數之間的不同隨機數，再將序號和隨機數相符的基因設置為1，以實現初始編碼。
算法的適應度函數主要通過章節比例約束、難度比例約束、區分度比例約束、時間約束四個約束來實現。
1）章節比例約束的計算公式為：f1= （i為章數，z為應選題目數，Z為總題數）。
2）難度比例的約束公式為：f2= （i為題型數，j為題目數，n為題目難度，N為試卷總難度）。
3）區分度比例約束公式為：f3= （i為題型數，j為題目數，q為題目區分度，Q為試卷總區分度）。
4）時間約束公式為：f4= （i為題型數，j為題目數，s為題目參考時間，S為試卷總時間）。
最后得出目標函數為：f=w1f1+w2f2+w3f3+w4f4（1≤wi≤10）。
2.3 算法實現
遺傳算法使用選擇運算來實現對群體中的個體進行優勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。本系統的選擇算子運用的是基于排序的選擇方法，將群體中的個體按照計算出的適應度排序，并按序分配各自的選擇概率[4]。
算法中交叉算子采用單點交叉算子[4]。所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產生新個體的主要方法。單點交叉的實現方法是在基因串中隨機設定一個交叉點并互換該點的前后兩個個體的部分結構，生成兩個新串。隨機交叉占用時間比較多，當題庫較大時，組卷時間可能偏長。
算法的變異算子采用的是基本位變異算子。所謂變異運算，是指依據變異概率 Pm 將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索[5]。基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變為1；反之，若原有基因值為1，則變異操作將其變為0。本算法中設定Pm為0.1。
3 系統實現
3.1 模塊劃分
根據課題研究分析后，對網絡考試系統的模塊劃分如圖2。
3.2 功能概述
學生訪問考試平臺，需要通過登錄界面，學生進入考試平臺后默認的是瀏覽歷史考試記錄，查詢歷史考試的答題及成績信息。
教師以教師身份登錄考試平臺，系統自動切換到考試評分模塊，教師可以根據需要設置題型題庫，對題庫進行添加、修改、刪除等管理操作,也可以通過考試系統中的“試題組卷”功能進行批量組卷。組卷前需要對試卷名稱、考試時間、試卷份數、題目數、分數、難易度及區分度等試卷參數進行設置，設置完成后點“開始組卷”按鈕系統會自動生成考試試卷并保存在數據庫中。測試后續，教師能對試卷做后期管理，主要有成績查詢、試卷存檔、瀏覽已存檔試卷三個功能模塊。
4 總結
在線考試系統的實質是利用先進的現代計算機技術，用計算機組卷來代替人工活動，解決在傳統的人工考試環境下不能解決的問題，達到提高工作質量和工作效率的目的[5]。
在線考試系統具有降低考試成本，解決繁重的考務工作的優點。利用計算機建立題庫并對其進行管理，是實現教考規范化、標準化的一個重要措施。一方面計算機參與管理題庫、組卷節省了教師的寶貴時間，另一方面使考試更加標準化，更加客觀真實全面地反映教學成果，從而促進教學質量的提高[5]。
參考文獻：
[1] 呂盈.基于B_S架構的遠程考試系統的設計與實現[D].大連:大連理工大學碩士論文,2006.
[2] 劉豐.在線考試系統的設計與研究[D].北京:北京師范大學,2000.
[3] 邱少明.基于ASP的網上考試系統的設計與實現[D].大連:大連理工大學碩士論文,2006.
[4] 夏愛月.基于遺傳算法的自動組卷系統研究與實現[J].電腦編程技巧與維護,2008(10).
關鍵詞：六自由度機械臂 遺傳算法 避碰問題 機械臂設計
1.模型分析
首先對模型進行假設，假設已知機器人初始的位姿和目標點，反解機器人在由初始位姿到達目標點的過程中的各個動作？機器人在初始位姿時的各個連桿的相對空間關系是確定的，那么就可以求出連桿坐標系 和連桿坐標系 之間的奇次變換矩陣，本文在這些奇次變換矩陣，設計了另外得求解方法，即利用非線性規劃模型求出指尖最接近目標點時的旋轉角度，從而可以求出目標點的旋轉角度與初始姿態的旋轉角度之差 。
假設在初始位置與目標位置之間的區域中有若干個已知大小、形狀、方向和位置的障礙物，為了不損壞機器，要求機械臂在運動中始終不能與障礙物相碰（機械臂連桿的粗細自己設定）？由于各個障礙物的大小、形狀、方向和位置是已知的，那么就可以確定障礙物的空間范圍，只要保證機器人各個連桿滑過的空間范圍不與障礙物的空間范圍不相交，那么機械臂就不會與障礙物相碰。
2. 模型建立、求解與結果分析
2.1模型建立與求解方法
針對本模型中的六自由度機械臂，可以首先對六個關節點建立了D-H 四點參數坐標系。
圖6-1 機械臂初始狀態及各個關節點的D-H 四點參數坐標系
然后利用6自由度機械臂的連桿D-H參數，寫出各連桿齊次變換矩陣，將各連桿變換矩陣相乘，可得6自由度機器人的總的變換矩陣，由機械臂運動學正解方程可以得出 ，其中 為機械臂指尖坐標
則有：
…………（1-1）
可以看出機械臂指尖坐標 的3個維度上的坐標均是 的方程，若已知機械臂指尖坐標
，根據機械臂運動學逆解方程，就可以反解出旋轉角度 。
為了達到精準的目的只能盡可能的接近，為求出最接近的終點處的旋轉角度，本文以實際到達點與目標點指尖的距離最小為目標函數，以各個旋轉角度的范圍作為約束條件，建立模型如下：
…………（1-2）
在Matlab軟件下，利用遺傳算法就可以求得最接近目標點的終點的旋轉角度 ，由于模型（6-2）中目標函數相對較復雜，包含有六個變量的，故本文設計了“轉角遺傳算法”來求解這個模型。
2.2具體編碼過程
1）編碼解碼
采用等長的十進制進行編碼：對可選的關節旋轉角的集合進行編碼作為一個基因，六個基因組成一個個體。
2）適應度函數
用適應度函數來評價遺傳算法時，適應度越大，解的質量越好，本題中以機械臂最終到達點與目標點距離最短的方式最優？
3）遺傳算子
a）選擇算子
采用比例選擇方式：
第一步：先計算出群體中所有個體的適應度的總和；
第二步：其次計算出每個個體的相對適應度的大小，它即為各個個體被遺傳到下一代群體中的概率。
b）交叉算子
采用單點交叉算子：
第一步：對每一對相互配對的個體，隨機設置某一基因座之后的位置為交叉點。
第二步：對每一對相互配對的個體，依設定的交叉概率pc在其交叉點處相互交換兩個個體的部分染色體，從而產生出兩個新的個體。
5）運行參數
運用轉角遺傳算法求出機械臂旋轉角度 ，進而可以求出機械臂從初始點到目標點旋轉角度的變化量
，機械臂指尖從一個點移動到另一個點可以由不同的動作組合完成，那么本文就可以建立一個數學模型？為了達到快捷目的，本文在建立模型過程中以機械臂動作個數最少為目標函數，約束條件是機械臂經過動作序列控制后，各個關節旋轉角度之和為旋轉角度的變化量 ，模型如下：
…………（1-3）
以動作幅度 最大為準則求解模型（6-3），得出結果。
3. 結論
（1）在使用四點參數法（D-H法）建立了齊次坐標系的基礎上，確定了連桿參數，得到了六自由度機械臂的正運動學方程，并導出其運動學逆解；并設計了具有良好的適應性、較高準確率和障礙處理功能的“轉角遺傳算法”和“指令系列遺傳算法”。
（2）采用“轉角遺傳算法”解決了機器臂取用工具問題；采用“轉角遺傳算法”和樣條插值解決了沿軌跡焊接問題；采用“指令系列遺傳算法”解決了容器內部焊接可能遇到障礙物問題。
參考文獻：
[1]機器人控制研究 丁學恭 浙江大學出版社 2006 P19
