基于SA－KM 算法的畢業(yè)設(shè)計選題分配

羅樂霞

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

0 前言

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

1 設(shè)計構(gòu)思

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

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

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

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

圖2 教師出題與學生選題的邏輯關(guān)系

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

2 KM選題分配算法

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

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

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

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

定理：設(shè)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)匹配。

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

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

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

3.1 SA－KM算法思想

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

圖3 SA－KM算法思想

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

3.2 SA－KM選題分配算法

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

最優(yōu)權(quán)值匹配

4 算法實驗結(jié)果分析

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

4.1 收斂時間比對分析

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

圖4 收斂時間的比對分析

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

4.2 選題結(jié)果對比分析

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

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

圖5 選題結(jié)果比對分析

5 結(jié)語

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

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

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

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

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

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