羅樂霞

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

0 前言

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

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

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

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

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

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

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

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

2 KM選題分配算法

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

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

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

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

定理：設(shè)L是二部圖G的可行頂標(biāo)。若L等價(jià)子圖GL有完美匹配M，則M是G的最佳匹配。

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

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

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

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

3.1 SA－KM算法思想

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

圖3 SA－KM算法思想

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

3.2 SA－KM選題分配算法

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

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

4 算法實(shí)驗(yàn)結(jié)果分析

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

4.1 收斂時(shí)間比對(duì)分析

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

圖4 收斂時(shí)間的比對(duì)分析

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

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

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

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

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

5 結(jié)語

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

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

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

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

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

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