前言：中文期刊網精心挑選了遺傳算法論文范文供你參考和學習，希望我們的參考范文能激發你的文章創作靈感，歡迎閱讀。

遺傳算法論文范文1

關鍵詞遺傳算法；TSP；交叉算子

1引言

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法。總的說來，遺傳算法是按不依賴于問題本身的方式去求解問題。它的目標是搜索這個多維、高度非線性空間以找到具有最優適應值(即最小費用的)的點[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

遺傳算法論文范文2

關鍵詞：自動排課；遺傳算法；求解與優化

中圖分類號：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.

遺傳算法論文范文3

關鍵詞：在線測試；組卷策略；遺傳算法

中圖分類號：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) 定性映射算法。

隨機抽取法根據狀態空間的控制指標，由計算機隨機抽取試題組成試卷。該方法實現最為簡單，不需要很高的技術支持，但具有很大的隨意性和不確定性，使生成的試卷缺少整體性和科學性，組卷的效率也比較低。回溯試探法記錄隨機產生的每一狀態類型，如果搜索失敗則將上次記錄的狀態類型進行釋放,然后采用特定的規律運用新的一種狀態類型進行回溯試探，直到試卷生成成功或退回到起點為止。回溯試探法不適合大型的題庫系統，通常適用于題型和題量都比較小的考試系統。該算法程序實現相對比較復雜，出題的隨機性比較差，試卷生成時間也比較長。定性映射算法提出了一種合理分配不同難度試題的方法[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).

遺傳算法論文范文4

關鍵詞：排課；遺傳算法；哈希圖；時間粒度；適應度函數

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)28-0175-03

The Making Class Schedule System of High School Based on Genetic Algorithms

XIA Xiao-yun1, GAO Wu-jun2

(1.Faculty of Information Engineering,Jiangxi University of Science and Technology, Ganzhou 341000, China;2.Faculty of Science, Jiangxi University of Science and Technology, Ganzhou 341000, China)

Abstract: As the ongoing development in the higher education institutions, the class arrangement model in the management system is also becoming more and more complicated. Course Scheduling is a typical portfolio optimization and uncertainty of scheduling problems, but also a complete problem. Based on the actual situation in high school. In addition, on the basis of GA basic theory, studies how to utilize GA to solve the conflict problem that aroused in schedule arranging system and improve schedule arrangement. We quoted a hash table and time granules, and amend the traditional genetic algorithm chromosome coding models, enhance the flexibility of the model. The practice has proved that GA can simplify the program complexity and shorten the time in generating new perfect schedule. And the curriculum schedule induced by the time code meet the satisfaction of students and teaching staff exactly.

Key words: making class schedule; genetic algorithms; hash map; time granules; fitness function

1 引言

隨著高校規模的擴大，學生人數也逐漸增加，高效教務部門排課問題也變得越來越復雜。高校排課問題是在給定教師資源、教室資源、學生人數和開課計劃的前提下，如何合理安排課表的問題。排課問題是一個NP難問題[1]。對于較為單一的排課問題來說，可以采取啟發式搜索算法找到最優解，而對于復雜的排課問題，該算法很難找到合理和滿意的解。遺傳算法[2]作為一種有效的全局搜索方法，具有良好的并行性，通過對可行解進行選擇、交叉、變異等遺傳算子的作用使種群不斷進化，從而得到全局最優解或近似最優解。基于遺傳算法的魯棒性，適用范圍廣，有組織性、自適應和學習性、并行性等許多有點，其應用范圍也較為廣泛。本論文引入哈希表和時間粒度對編碼模式進行修正，并充分利用遺傳算法特點，給出了排課問題的有效求解方法，對高校教務管理排課研究具有重要的意義。

2 排課問題中的約束條件及優化目標

在實際排課過程中，以某一等長的時間段為課表的時間安排單位，稱之為時間單元[3]。一個可行的課表安排應滿足以下約束條件：課表以一個星期為一周期，一個星期的課表就是一個學期的課表；課表應滿足班級、教師、教室上課不沖突；教室的座位應該滿足上課班級學生的需要；其他一些特殊要求。

高校排課問題實際上是時間表安排的問題[4]。在實際排課過程中，需要考慮到教師、學生、班級、教室、教室的大小、實驗設備等方面的問題。這些條件可以根據重要性將其分為硬件約束和軟件約束。為了更好的解決問題，我們假設硬件約束為：

某些課程需要安排在特定的教室。

同一時間，同一個教師，同一個學生，同一個教室不允許同時上一門以上課程。

教室必須有足夠的座位容納學生。

對于需要試驗設備的課程，教室需要有相應的配套設備。比如計算機課需要電腦。

硬件約束條件是在排課過程中必須滿足而無法變更的約束條件。

軟件約束為：

安排教師喜歡的特定時間上課。

安排教師喜歡的特定教室上課。

在相應的時間或教師給學生或老師安排特定的課程。

軟件約束條件是在排課過程中可以滿足但又可以不完全滿足的約束條件。

排課問題[5-7]的關鍵就是為了解決課程安排對時間和空間資源的有效利用并避免相互沖突。排課的優化目標就是使得各類沖突為零，并且盡可能滿足教師、學生的要求，達到較好的教學效果 。

3 用遺傳算法解決排課問題

3.1 排課問題中的對象描述

1）教師

■

2）學生組（大班）

■

3）教室

■

4）課程

■

5）教學班

■

3.2 染色體編碼及適應度函數

為了更靈活的進行染色體編碼，我們假定每周上課時間為周一至周五共五天，而每天從上午9點至晚上9點共十二個小時。規定一小時為一時間片段。我們可以定義一個大小為12*5*教室數量的向量，并使用哈希表存放上課的班級、時間及教室。

遺傳算法的進化過程是以每個個體的適應度值為依據來選取下一代種群的。適應度函數設定的好壞直接影響到遺傳算法的收斂速度和能否找到最優解。本文中，我們僅考慮硬件約束方面的因素，在本研究中,適應度函數的設計思想是由于課表問題的優化目標有多個，同時約束也有多個，因此采用多目標化和適應度函數相結合的個體適應度評價函數[8]。

每個教學班級有0――5的得分；

如果教學班級使用矛教室，就增加分值；

如果上課教室需要電腦并且安排上課的教室里有電腦，或者上課教室不需要電腦，就增加分值；

如果安排上課的教室沒有足夠的座位，就增加分值；

如果教師在上課時間沒有其它的課程，我們再一次增加分值；

如果學生在上課時間沒有其它的課程，我們就增加分值；

如果教學班級在任一時間間隔點破壞了上述規則，不再增加分值。

因此，我們可以定義適應度的計算公式如下：

■

其中， schedule_score代表所有教學班級總得分數， Maximum_score=教學班級數*5，適應度值為0~1之間的單精度浮點型值。

3.3 交叉和變異操作

交叉操作就是對選取的兩個父個體哈希表中數據進行組合，然后根據新的哈希表中的內容創建向量。交叉操作對隨機產生的部分父個體哈希圖進行分裂。分裂的部分由染色體特征中交叉點的數量決定。最終從父個體交替復制到新的染色體中，形成新的向量。

變異操作是很簡單的。它是隨機的選取課程然后隨機的放入所選擇的時間段。課程隨機移動的數量由變異的染色體特征決定。

4 結論

本文在對遺傳算法研究的基礎上設計實現了高校智能排課系統。并對傳統的編碼模式進行了有效的改進。從排課的結果分析得出所編排的課程表滿足排課原則，有效解決沖突問題，課時安排比較均勻。并且這種編碼模式具有較高的擴展性，算法的性能有待于進一步提高。

參考文獻：

[1] GAREY M R, JOHNSON D S, Compute and Intractability: A guide to the theory of NP completeness[M].San Francisco: W.H.Freeman & Co Ltd,1979.

[2] 周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業出版社,1999.

[3] SAFAAI D,SIGERU O. Incorporating constrain propagation in genetic algorithm for university timetable planning[J].Engineering Application of Artificial Intelligence,1999,12(3):241-253.

[4] 滕姿,鄧輝文,楊久俊.基于遺傳算法的排課系統的設計與實現[J].計算機應用,2007,27(12):199-204.

[5] 蘇仰娜.基于遺傳算法的優化排課系統[J].河南大學學報:自然科學版,2005,35(3):47-50.

[6] 楊宇.高校排課系統理論研究與開發遺傳算法在課表問題中的應用[M].北京:北京理工大學出版社,2003:35-67.

遺傳算法論文范文5

關鍵字：遺傳算法；機器學習；人工生命；人工神經網絡；神經網絡拓撲結構

中圖分類號：TP183文獻標識碼：A文章編號：1009-3044(2008)27-2040-03

The Application of Genetic Algorithm to the Artificial Intelligence

WANG Hui

(Xinjiang Petroleum Institute, Urumqi 830000, China)

Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short),the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning, Parallel Processing, artificial Life, and the integration of evolutionary rules and strategies. At last, the application of GA to artificial neural networks is discussed, especially the application of GA to the study of neural networks weight and the neural network topology.

Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology

1 遺傳算法簡介

遺傳算法是模仿生物遺傳學和自然選擇機理，通過人工方式構造的一類優化搜索算法，與傳統數學模型截然不同，它為那些難以找到傳統數學模型的難題找出了一個解決方法。遺傳算法借鑒了生物科學中達爾文的物競天擇、適者生存的進化準則，1975年，Michigan大學Holland教授根據這一規律首次提出了遺傳算法（genetic algorithm，簡稱GA），其基本思想是力求充分模仿這一自然尋優過程的隨機性、魯棒性和全局性。這是一種新型的全局優化搜索算法，因為其直接對結構對象進行操作，不存在求導和函數連續性的限定等數學問題，魯棒性強、隨機性、全局性以及適于并行處理，已廣泛應用于神經網絡、計算機科學、優化調度、運輸問題、組合優化、機器學習、信號處理、自適應控制和人工生命等領域，并且遺傳算法在實際應用中也取得了巨大成功。

2 基本遺傳算法

遺傳算法的工作過程本質上就是模擬生物的進化過程。首先，要規定一種編碼方法，使得你的問題的任何一個潛在可行解都能表示成為一個“數字”染色體。然后，創建一個由隨機的染色體組成的初始群體（每個染色體代表了一個不同的候選解），并在一段時期中，以培育適應性最強的個體的辦法，讓它們進化，在此期間，染色體的某些位置上要加入少量的變異。

遺傳算法是一種基于空間搜索的算法，它的求解可以看成是最優化過程。遺傳算法的最大優點就是，你不需要知道怎么去解決一個問題，你需要知道的僅僅是用什么樣的方式對可行解進行編碼，使得它能被遺傳算法機制所利用。遺傳算法并不能保證所得到的解是最優解，但可以將誤差控制在容許的范圍內。遺傳算法具有以下特點：

1） 遺傳算法是對參數集合的編碼而非針對參數本身進行優化；

2） 遺傳算法是從問題解的編碼組開始而非從單個解開始搜索；

3） 遺傳算法利用目標函數的適應度這一信息而非利用導數或其他輔助信息來指導搜索；

4） 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規則進行隨機操作。

那么下面對基本遺傳算法給出一個求解步驟：

1） 定義一個目標函數；

2） 將可行解群體在一定的約束條件下初始化，每一個可行解用一個向量x來編碼，稱為一條染色體，向量的分量代表基因，它對應可行解的某一決策變量；

3） 計算群體中每條染色體xi(i＝1，2，…，n)所對應的目標函數值，并以此計算適應值Fi，按Fi的大小來評價該可行解的好壞；

4） 以優勝劣汰的機制，將適應值差的染色體淘汰掉，對幸存的染色體根據其適應值的好壞，按概率隨機選擇，進行繁殖，形成新的群體；

5） 通過雜交和變異的操作，產生子代。雜交是隨機選擇兩條染色體（雙親），將某一點或多點的基因互換而產生兩個新個體，變異是基因中的某一點或多點發生突變；

6） 對子代群體重復步驟(3)～(5)的操作，進行新一輪遺傳進化過程，直到迭代收斂（適應值趨穩定）即找到了最優解或準最優解。

3 遺傳算法的發展動向

GA在應用方面的取得了較豐碩的成果，其主要應用領域在于函數優化，機器人學，設計，組合優化，信號處理，人工生命等，此外遺傳算法還有幾個引人注目的新動向。

3.1 基于GA的機器學習

這一新的研究方向把GA從歷史離散的搜索空間的優化搜索算法擴展到具有獨特的規則生成功能的嶄新的機器學習算法，這一新的學習機制對于解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望，GA作為一種搜索算法從一開始就與機器學習有密切聯系。分類器系統是第一個基于GA的機器學習系統。基于GA的概念學習是近幾年機器學習領域的一個較為引人注目的研究方向。還有一些嵌入領域知識的基于GA的機器學習的研究。

3.2 并行處理的GA

并行處理的GA的研究不僅是GA本身的發展，而且對于新一代智能計算機體現結構的研究都是十分重要的，GA在操作上具有高度的并行性，許多研究人員都正在搜索在并行機上高效執行GA的策略。近幾年也發表了不少這方面的論文，研究表明，只要通過保持多個群體和恰當地控制群體間的相互作用來模擬并執行過程，即使不使用并行計算機，我們也能提高算法的執行效率。在并行GA的研究方面，一些并行GA可以分為兩類：一是粗粒度并行GA，它主要開發群體間的并行性，如Coboon分析了在并行計算機上解圖劃分問題的多群體GA的性能；另一類是細粒度并行GA，它主要開始一個群體中的并行性，如Kosak將群體中的每個個體映射到一個連接機的處理單元上，并指出了這種方法對網絡圖設計問題的有效性。

3.3 GA與人工生命的滲透

人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統特有行為的人造系統。人工生命與GA有密切的關系，基于遺傳算法的進化模型是研究人工生命現象的重要理論基礎，雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將得到更為深入的應用和發展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供了一個有效的工具，人工生命的研究也必將促進遺傳算法的進一步發展。

3.4 GA與進化規則及進化策略的結合

GA，進化規則及進化策略是進化計算的三個主要分支，這三種典型的進化算法都以自然界中生物的進化過程為自適應全局優化搜索過程的借鑒對象，所以三者之間有較大的相似性，但三種算法又是從不完全相同的角度出發來模擬生物的進化過程，分別是依據不同的生物進化背景，不同的生物進化機制而開發出來的，所以又有差異。但在進化計算領域內更重要的工作是生物的進化機制，構造性能更加優良且適應性更加廣泛的進化算法。

4 基于遺傳算法優化神經網絡的應用研究

神經網絡和遺傳算法目標相近而方法各異。因此，將這兩種方法相互結合，必能達到取長補短的作用。近年來,在這方面已經取得了不少研究成果，形成了以遺傳算法與神經網絡相結合的進化神經網絡(ENN)。遺傳算法在神經網絡中的應用主要是用遺傳算法學習神經網絡的權重和學習神經網絡的拓撲結構兩個部分。

4.1 遺傳算法學習神經網絡的權重

而最主要的是學習神經網絡的權重，也就是用遺傳算法來取代一些傳統的學習算法 。目前廣泛研究的前饋網絡中采用的是Rumel hart等人推廣的誤差反向傳播（BP）算法，BP算法具有簡單和可塑的優點，但是BP算法是基于梯度的方法，這種方法的收斂速度慢，且常受局部極小點的困擾，采用遺傳算法則可把神經網絡的結構優化和權值學習合并起來一起求解，克服了BP算法的缺陷，是神經網絡權值學習的有效方法。

遺傳算法學習神經網絡權值的算法步驟如下：

1） 隨機產生一組分布，采用某種編碼方案對該組中的每個權值（或閾值）進行編碼，進而構造出一個個碼鏈（每個碼鏈代表網絡的一種權值分布），在網絡結構和學習算法已定的前提下，該碼鏈就對應一個權值和閾值取特定值的一個神經網絡；

2） 對所產生的神經網絡計算它的誤差函數，從而確定其適應度函數值，誤差與適應度成反比關系；

3） 選擇若干適應度函數值最大的個體，直接遺傳給下一代（精英保護策略）；

4） 利用交叉和變異等遺傳操作算子對當前一代群體進行處理，產生下一代（新一代）群體；

5） 重復步驟2～4，使初始確定的一組權值分布得到不斷的進化，直到訓練目標得到滿足或者迭代次數達到預設目標為止。

4.2 遺傳算法學習神經網絡的拓撲結構

神經網絡結構包括網絡的拓撲結構（連接方式）和接點轉移函數兩方面。利用遺傳算法設計神經網絡可根據某些性能評價準則如學習速度，泛化能力或結構復雜程度等搜索結構空間中滿足問題要求的最佳結構。利用遺傳算法設計神經網絡的關鍵問題之一仍然是如何選取編碼方案。

遺傳算法學習神經網絡結構的算法步驟如下:

1） 隨機產生若干個不同結構的神經網絡，對每個結構編碼，每個碼鏈對應一個網絡結構，N個碼鏈構成種群。

2） 利用多種不同的初始連接權值分別對每個網絡進行訓練。

3） 計算在每個對應碼鏈下神經網絡的誤差函數，利用誤差函數或其他策略（如網絡的泛化能力或結構復雜度）確定每個個體的適應度函數。

4） 選擇若干適應度函數值最大的個體構成父本。

5） 利用交叉，變異等遺傳操作算子對當前一代群體進行處理，產生新一代群體。

6） 重復上述2）-5）步驟，直到群體中的某個個體（對應一個網絡結構）能滿足要求為止。

5 結束語

遺傳算法作為一種新型的全局優化搜索算法，由于其直接對結構對象進行操作，不存在求導和函數連續性的限定，又具有魯棒性強、隨機性、全局性以及適于并行處理的優點，在人工神經網絡的應用上展現了它的獨特魅力與優勢，但同時，它在理論和應用技術上也存在著許多不足和缺陷，比如相對鮮明的生物基礎，其數學基礎顯得極為薄弱，尤其是缺乏深刻且具有普遍意義的理論分析。隨著理論研究的深入，可以肯定，作為一種高效并行的全局搜索方法，遺傳算法以其特有的算法特點使其在許多實際問題中的應用會越來越廣；同時，廣泛的數學方法和強大的計算機模擬工具的出現，必將使遺傳算法的研究取得長足的進展。

參考文獻：

[1] 蔡自興. 人工智能及其應用[M]. 3版.北京：清華大學出版社，2003.

[2] 王風琴. 基于遺傳算法的神經網絡優化[J].燕山大學學報，2001，25（3）：234-239.

[3] 陳國良. 遺傳算法及其應用[M].北京：人民郵電出版社，1999.

[4] 陳穎琪. 進化計算與神經網絡的結合[J].紅外與激光工程，1999，（4）：8-11，35.

[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.

[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE

[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE

[8] 楊旭東，張彤. 遺傳算法應用于系統在線識別研究[J].哈爾濱工業大學學報， 2000，32（1）：102-104.

[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.

[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79, 1994.

[11] Kao T, Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System, Man. And Cybernetris-Part B: Cybernetics 1996,26.

遺傳算法論文范文6

關鍵詞：遺傳算法，自動組卷，算子

 

1．引言

隨著因特網技術以及教育網絡技術的不斷發展，越來越多的學校和機構開始采用網絡考試的考核形式，而在網絡考試中采用組卷形式的優劣與否將直接影響到試卷的質量與考試的成效。傳統的網絡考試中，學生只是隨機的從已有的幾套試卷中抽取一套，這樣會導致試卷的維護成本變高，同時試卷的重復率相對較大。當前較為先進的組卷方式，是隨機從已有的試題庫中按照考試的各項要求，如題型、考核點分布、難度、分值等因素選擇相應的題目自動組卷，組卷靈活，試卷的維護相對容易，這種方式已經被廣泛地應用到各種網絡考試系統當中。自動組卷技術實現的關鍵是組卷算法的選擇與實現，它將直接影響到組卷的質量。本文主要介紹的是使用遺傳算法進行自動組卷的思路與具體的實現。

2．常用的自動組卷算法

當前使用較多的自動組卷算法主要有三種。第一種是基于隨機抽題的算法，它根據問題空間的一些指標，從試題庫中隨機地抽取一道試題放入待生成的試卷中，此過程不斷重復，直到組卷完畢或無法從題庫中抽取滿足條件的試題為止。該組卷方法的重復率高，組卷成功率非常低，即使組卷成功，花費時間也較長。第二種是基于回溯試探法的算法，它是將隨機抽題算法產生的第一狀態類型記錄下來，當搜索失敗時釋放上次記錄的狀態類型，然后再根據一定的規律變換出一種新的狀態類型進行試探。該算法的不足之處在于當試卷總題量較大時，狀態類型的變換便成為一個巨大的數字。因此這種方法只適用于狀態類型和試卷總題量都較少的題庫系統。第三種是基于遺傳算法的組卷算法，它可以從群體中選擇更滿足條件的個體，具有很強的智能性。同時它能根據不同的環境產生不同的后代，具有動態性，自適應性，從而能滿足試題庫容量、覆蓋面不斷變化的要求。

3．遺傳算法數據模型的建立

自動組卷時會根據組卷的原則對試卷的質量提出很多方面的要求，即試題的控制指標，如每種題型包含的題目數量、每種題型所占分數、每道試題的難度系數等。因此，在組卷之前應該為自動組卷建立模型。其模型如下圖所示：