羅樂霞

（福建船政交通職業(yè)學院信息工程系，福州350007）

0 前言

傳統(tǒng)的畢業(yè)設計選題分配是將試題隨機分配給學生，或者是讓學生在眾多選題中選擇自己心儀的題目，這往往導致學生分配的題目不理想，難以發(fā)揮出其真正的實力，同時選題與學生一對一的關系，一個選題被一個學生選擇后其他學生不能再次選擇，這就導致其他學生選擇題目的范圍越來越窄，有悖于公平、公正評估學生學習效果的意愿。因此，本文對畢業(yè)設計選題分配算法進行研究與設計，提出根據教師評定的課題難易程度與課題類型的權重分配及學生成績與學生自我評價值的權重分配［1］，采用優(yōu)化后的高維數據［2］的SA－KM聚類算法［3］，根據教師評估和學生意愿進行分配，大大提高了學生畢業(yè)設計的水平。

1 設計構思

本文所設計的畢業(yè)設計選題分配系統(tǒng)算法采用二分圖數學理論，將教師賦予學生期望值課題與學生志愿選擇課題分別設為X、Y2個集合，如圖1所示。

將教師賦予學生期望值課題與學生志愿選擇課題數學轉化為一個帶權的二分圖，其中X值為教師賦予學生期望值，Y值為學生志愿選擇值，采用最優(yōu)匹配算法對權值進行優(yōu)化，獲得最大權值，即為畢業(yè)設計選題分配最優(yōu)結果。

圖1 教師賦予學生期望值課題X與學生志愿選擇Y二分圖

該算法描述了以權重分配為基礎的二分搜索條件查找，為實現教師為學生所設置的課題與學生擅長或者是與學生興趣相匹配，符合學生真實能力評測要求的畢業(yè)設計選題分配算法，建立教師出題與學生選題之間的邏輯關系，如圖2所示。

圖2 教師出題與學生選題的邏輯關系

算法數據庫主要包含2大類數據項：一是以學生為主體的學生信息表，二是以選題為主體的課題信息表。學生信息表主要包括：興趣愛好、技巧能力、考試成績評估、自我評價；課題信息表主要包括：課題介紹、課題要求、課題類型、課題難度。

2 KM選題分配算法

采用KM算法［4］進行選題分配計算，該算法為求完備匹配下的最大權匹配問題［5］。

對于具有二部劃分（X1，Y2）的加權完全二分圖，其中 X1＝ ｛x1，x2，x3，…，xn｝，Y2＝ ｛y1，y2，y3，…，yn｝，邊＜xi，yj＞具有權值Wi，j。該帶權的二分圖中一個與總權值最大的完美匹配，就是最佳匹配設計。

設L（x）表示結點x的標記量，如果對于二部圖中的任何邊 ＜x，y ＞，都有L（x）＋L（y）＞＝Wx，y，我們稱L為二部圖的可行頂標。

設G（V，E）為二部圖，G′（V，E′）為二部圖的子圖。如果對于G′中的任何邊＜x，y＞滿足L（x）＋L（y）＝＝Wx，y，我們稱G′（V，E′）為G（V，E）的等價子圖。

定理：設L是二部圖G的可行頂標。若L等價子圖GL有完美匹配M，則M是G的最佳匹配。

證明：由于GL是G的等價子圖，M是GL的完美匹配，所以，M也是G的完美匹配。又由于對于匹配M的每條邊e，都有e∈E（GL），而且M中每條邊覆蓋每個頂點正好一次，所以W（M）＝?aW（e），e∈M＝?aL（x），x∈V。另一方面，對于G的任何完美匹配 M′有W（M′）＝?aW（e），e∈M′＜＝?aL（x），x∈V，于是W（M）＞＝W（M′），即M是G的最優(yōu)匹配。

由上述定理，我們可以通過不斷修改可行頂標，得到等價子圖，從而求出最佳匹配。設X為畢業(yè)設計題目，Y 值為學生，題目集合X ＝ ｛X1，X2，...，Xm｝，學生集合Y ＝ ｛Y1，Y2，...Yn｝，根據教師賦予學生課題期望值與學生志愿選擇課題意愿值建立權值二分圖，其中權值為二維矩陣W［m］［n］的值，教師賦予學生課題期望與學生志愿選擇課題意愿不相關聯權值等于0，相關聯權值的試題顯示給學生進行篩選。

3 選題分配算法優(yōu)化

KM算法進行選題分配計算不足之處在于全局搜索能力較弱，其在初始聚類中隨機選擇選題，并沒有對初始聚類進行優(yōu)化，局限于部分選題最優(yōu)匹配。同時KM算法收斂時間較長，在試題分類中無法達到最優(yōu)的選題分類效果。因此，本文提出SA－KM選題分配算法，首先對聚類初始中心進行全局智能搜索，再通過KM算法進行聚類，進而能夠獲得全局搜索的最優(yōu)聚類劃分，從而提高畢業(yè)選題的快速搜索速度，減少利用KM算法進行選題搜索的盲目性，提高畢業(yè)設計選題分配的聚類劃分質量。

3.1 SA－KM算法思想

SA－KM算法在搜索過程中如果發(fā)現新的最優(yōu)匹配結果則無條件地替換原來的搜索結果，如果未發(fā)現最優(yōu)匹配結果則接受原有的搜索結果。在畢業(yè)設計選題分配算法中，該算法跳出了教師與學生的選題分配權重的交集，豐富了選題內容。SAKM算法核心思想如圖3所示。

圖3 SA－KM算法思想

在畢業(yè)設計選題分配系統(tǒng)中，教師出題與學生選題可根據權重建立初始聚類中心，進而提高了學生選題的效率，避免了學生選題的盲目性，并減少了KM算法的迭代次數，提高了算法的計算效率。SA－KM算法跳出了KM算法只在權重交集中搜索畢業(yè)設計選題的局部框架，面向全局搜索獲取最佳選題，當學生在全局搜索中找到新的最優(yōu)解，則將最新解作為新的權重交集。SA－KM算法擴大了畢業(yè)設計選題的搜索范圍，并提高了選題的搜索能力，當產生最新解時，更換權重匹配結果，提高學生自主選擇的能力。

3.2 SA－KM選題分配算法

SA－KM聚類評價是為了提高教師出題權重與學生選題權重的聚類劃分質量，設題目集合X＝｛X1，X2，...，Xm｝，學生集合Y＝｛Y1，Y2，...Yn｝，聚類劃分為Pq＝｛P1，P2，...Pq｝，其中Pi為第i個集合。選題集合評價為

最優(yōu)權值匹配

4 算法實驗結果分析

基于以上算法的思路，我們開發(fā)了相應的畢業(yè)論文管理系統(tǒng)，在福建船政職業(yè)技術學院計算機網絡技術專業(yè)2012級學生的畢業(yè)論文選題中進行了測試應用，選取100名畢業(yè)生為分析對象，題目102個，為算法的實驗提供了部分數據信息。

4.1 收斂時間比對分析

將畢業(yè)設計KM選題分配算法與SA－KM選題分配算法進行收斂時間的比對分析，分析結果如圖4所示。

圖4 收斂時間的比對分析

選題分配算法中，其收斂時間隨著選題聚類的數目增加而延長，由圖4所示，采用SA－KM算法的收斂時間明顯比KM算法要短，這是因為SAKM算法首先通過匹配概率搜索快速找到聚類中心，從而規(guī)避了KM算法在局部最優(yōu)解的問題上迂回搜索，在確定聚類中心后，再進行KM算法進行聚類劃分，降低了KM算法的盲目聚類性。

4.2 選題結果對比分析

在匹配過程中，將教師出題權重值與學生選題權重值按比例劃分，分別為1∶9、1∶8、1∶7、1∶6、1∶5、1∶4、1∶3、1∶2、1∶1分析 KM 選題分配算法與SAKM選題分配算法在不同比例下的選題滿意度，分析測試結果如圖5所示。

由圖5所知，教師出題權重值與學生選題權重值在2∶8、3∶7范圍內更容易選擇出較為理想的畢業(yè)設計課題。同時，由于SA－KM選題分配算法所聚類的搜索能力更強，選題匹配評價更加客觀、全面，更容易與師生意愿值匹配，選題成功率更高，更加人性化。

圖5 選題結果比對分析

5 結語

目前對本選題算法進行了實現，在福建船政職業(yè)技術學院計算機網絡技術專業(yè)2012級學生的畢業(yè)論文選題中進行了測試應用，在學生預選題目的智能匹配采用SA－KM算法完成最優(yōu)匹配，證明了以上提出的算法有利于提高教師學生整體滿意度和選題效率，同時降低了選題過程的工作量，達到了預期效果。

［1］楊勝超，張瑞軍.基于二分圖最優(yōu)匹配算法的畢業(yè)論文選題系統(tǒng)［J］.計算機系統(tǒng)應用，2008，17（7）：14－17.

［2］陳黎飛.高維數據的聚類方法研究與應用［D］.廈門：廈門大學，2008：4－6.

［3］李梓，于海濤，賈美娟.基于改進模擬退火的優(yōu)化K－means算法［J］.計算機工程與應用，2012，48（24）：77－80.

［4］孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學報，2008，19（1）：48－61.

［5］首翠香，陳宮.基于KM算法的畢業(yè)設計選題系統(tǒng)設計與實現［J］.軟件導刊，2012，11（8）：75－77.