李浩君,岳 磊,張鵬威,楊 琳
1(浙江工業(yè)大學(xué) 教育科學(xué)與技術(shù)學(xué)院,杭州 310023)
2(杭州市電子信息職業(yè)學(xué)校,杭州 310021)
隨著互聯(lián)網(wǎng)的發(fā)展以及人工智能、大數(shù)據(jù)等新興技術(shù)與教育的深度融合,在線學(xué)習(xí)已成為當(dāng)今時(shí)代的應(yīng)用新常態(tài).協(xié)作學(xué)習(xí)是在線學(xué)習(xí)中最有效的學(xué)習(xí)模式之一,而形成最優(yōu)在線學(xué)習(xí)群體是進(jìn)行協(xié)作學(xué)習(xí)的基礎(chǔ)和前提,形成符合教師的教學(xué)要求且滿足學(xué)習(xí)者需求的在線學(xué)習(xí)群體,可以有效改善在線協(xié)作學(xué)習(xí)過(guò)程中的學(xué)習(xí)體驗(yàn)和學(xué)習(xí)效率.
在線學(xué)習(xí)群體的形成是在線協(xié)作學(xué)習(xí)領(lǐng)域的重要研究?jī)?nèi)容,吸引了眾多學(xué)者對(duì)在線學(xué)習(xí)群體形成開(kāi)展研究.Abnar[1]、Sun[2]等探討了在線學(xué)習(xí)群體形成發(fā)展的生命周期;Ho[3]、Zheng[4]等優(yōu)化了在線學(xué)習(xí)群體的形成過(guò)程;Graf[5]、Yannibelli[6]等研究了影響在線學(xué)習(xí)群體形成的相關(guān)因素等,其主要應(yīng)用到聚類算法、近似算法、自學(xué)習(xí)算法等方法,但上述方法存在著噪聲敏感、結(jié)果不穩(wěn)定、收斂速度慢、運(yùn)算量大等缺點(diǎn).鑒于在線群體形成問(wèn)題本質(zhì)上是不同特征人群的組合優(yōu)化問(wèn)題;而元啟發(fā)式算法將隨機(jī)搜索算法與局部搜索算法相結(jié)合,被眾多學(xué)者認(rèn)為符合組合優(yōu)化的求解問(wèn)題.粒子群算法和遺傳算法作為常見(jiàn)的元啟發(fā)式算法,前者具有參數(shù)少、收斂速度快的優(yōu)勢(shì),后者具有編碼特征與在線學(xué)習(xí)群體形成問(wèn)題參數(shù)設(shè)置高度吻合的優(yōu)勢(shì),因此將兩者應(yīng)用于在線學(xué)習(xí)群體形成問(wèn)題的求解策略中.有學(xué)者使用粒子群算法解決分組問(wèn)題:Matheus等人在粒子群優(yōu)化算法的基礎(chǔ)上,融入了學(xué)習(xí)者的知識(shí)水平和興趣愛(ài)好,以形成大規(guī)模在線開(kāi)放課程的合作小組[7].Lin等人提出了一種改進(jìn)的粒子群優(yōu)化算法,不僅可以幫助教師規(guī)劃不同類型的協(xié)作學(xué)習(xí)過(guò)程,而且構(gòu)建的協(xié)作學(xué)習(xí)組具有良好的結(jié)構(gòu)性[8].Zheng等人以離散粒子群優(yōu)化算法為基礎(chǔ)來(lái)構(gòu)造異構(gòu)在線學(xué)習(xí)群體,該算法考慮了性別差異和人格類型的異質(zhì)性[9].也有學(xué)者使用遺傳算法解決分組問(wèn)題:Utomo等人提出了利用遺傳算法動(dòng)態(tài)組建學(xué)生團(tuán)體的方法,實(shí)證研究表明該方法能夠公平地組成項(xiàng)目團(tuán)隊(duì)[10].Chen等提出了一種基于遺傳算法的懲罰函數(shù)組學(xué)習(xí)群體形成方法,該方法考慮了學(xué)生知識(shí)水平、學(xué)習(xí)角色的異質(zhì)性以及學(xué)習(xí)組成員之間社會(huì)互動(dòng)的同質(zhì)性,以生成能夠平衡學(xué)習(xí)特征的協(xié)作學(xué)習(xí)組[11].
上述對(duì)學(xué)習(xí)群體形成問(wèn)題求解的方法較多采用單目標(biāo)優(yōu)化的方式,對(duì)個(gè)別在線學(xué)習(xí)群體在優(yōu)化過(guò)程中獲得的適應(yīng)度值控制有限.而在線學(xué)習(xí)群體形成問(wèn)題本質(zhì)上是多目標(biāo)優(yōu)化問(wèn)題,因此采用單目標(biāo)優(yōu)化方式求解會(huì)存在著難以解決多目標(biāo)問(wèn)題復(fù)雜性和分組問(wèn)題全局最優(yōu)性等局限.因此,近年來(lái)有學(xué)者嘗試從多目標(biāo)視角進(jìn)行求解來(lái)優(yōu)化最優(yōu)在線學(xué)習(xí)群體的形成過(guò)程,Miranda等人基于遺傳算法,通過(guò)考慮組內(nèi)同質(zhì)性、組內(nèi)異質(zhì)性和同理心3個(gè)方面優(yōu)化在線群體的形成過(guò)程[12].Lin等利用遺傳算法和相似度排序技術(shù)進(jìn)行方法改進(jìn),以促進(jìn)多目標(biāo)學(xué)習(xí)群體分組的優(yōu)化[13].Moreno提出一種基于遺傳算法的方法來(lái)實(shí)現(xiàn)同質(zhì)群體和異質(zhì)群體,該方法的主要特點(diǎn)是允許考慮盡可能多的學(xué)生特征,將分組問(wèn)題轉(zhuǎn)化為多目標(biāo)優(yōu)化問(wèn)題[14].Garshasbi等人提出了多目標(biāo)非支配排序遺傳算法,該算法能夠同時(shí)滿足預(yù)先定義的多個(gè)目標(biāo),提高最優(yōu)學(xué)習(xí)群體形成過(guò)程的有效性和準(zhǔn)確性[15].目前,多目標(biāo)優(yōu)化算法已經(jīng)成功解決了數(shù)字圖像水印質(zhì)量[16]、衛(wèi)星周期性持續(xù)觀測(cè)[17]、有效產(chǎn)品率提高[18]、通信系統(tǒng)中用戶功率優(yōu)化控制[19]、搜索定位精度[20]等多個(gè)領(lǐng)域的多目標(biāo)優(yōu)化問(wèn)題,但采用多目標(biāo)優(yōu)化方式對(duì)在線學(xué)習(xí)群體形成方法開(kāi)展的相關(guān)研究仍然較少,是未來(lái)在線學(xué)習(xí)群體形成領(lǐng)域的重要應(yīng)用研究方向.
針對(duì)上述問(wèn)題,本文首先根據(jù)學(xué)習(xí)者多項(xiàng)特征構(gòu)建在線學(xué)習(xí)群體形成模型MOLGFM,學(xué)習(xí)者特征匹配是形成在線學(xué)習(xí)群體形成的前提;其次,基于在線學(xué)習(xí)群體形成模型,設(shè)計(jì)整合多目標(biāo)粒子群算法和遺傳算法的多目標(biāo)優(yōu)化算法GAMOPSO,提出多目標(biāo)優(yōu)化視角下在線學(xué)習(xí)群體形成方法GAMOPSO-FA,從而形成最優(yōu)在線學(xué)習(xí)群體;最后,與1種隨機(jī)方法、1種單目標(biāo)進(jìn)化算法、1種經(jīng)典聚類算法和3種多目標(biāo)進(jìn)化算法進(jìn)行對(duì)比分析,驗(yàn)證GAMOPSO-FA方法在在線學(xué)習(xí)群體形成過(guò)程中的可行性與有效性.
在線學(xué)習(xí)群體形成是指根據(jù)收集到的在線學(xué)習(xí)者相關(guān)數(shù)據(jù),向?qū)W習(xí)者推薦滿足其特征需求的學(xué)習(xí)群體.多目標(biāo)優(yōu)化視角下在線學(xué)習(xí)群體形成是指將在線學(xué)習(xí)群體形成問(wèn)題以多目標(biāo)問(wèn)題的形式進(jìn)行優(yōu)化求解,從而形成最優(yōu)在線學(xué)習(xí)群體.根據(jù)已有研究,本文在求解在線學(xué)習(xí)群體形成問(wèn)題時(shí)考慮的學(xué)習(xí)者特征有:性別(S)、位置(L)、認(rèn)知水平(C)、學(xué)習(xí)風(fēng)格(M)、學(xué)習(xí)時(shí)間(T)、興趣偏好(HP)和學(xué)習(xí)偏好(LP)等.
在分析學(xué)習(xí)者的學(xué)習(xí)風(fēng)格時(shí),依據(jù)Kolb的學(xué)習(xí)風(fēng)格分類理論,分為聚合型、同化型、發(fā)散型、調(diào)節(jié)型4種[21],表示為M={M1,M2,M3,M4}.在分析學(xué)習(xí)者的興趣愛(ài)好時(shí),將興趣愛(ài)好分為興趣偏好和學(xué)習(xí)偏好兩部分[22],表示為HL={HP,LP},其中,興趣偏好有音樂(lè)、財(cái)經(jīng)、科技、旅游、讀書(shū)、游戲、電影、動(dòng)漫、體育9類,表示為HP={HP1,HP2,HP3,HP4,HP5,HP6,HP7,HP8,HP9};學(xué)習(xí)偏好指學(xué)習(xí)者偏愛(ài)使用的學(xué)習(xí)資源類型,分為視頻、圖片、文字、音頻4類,表示為L(zhǎng)P={LP1,LP2,LP3,LP4}.
通過(guò)對(duì)學(xué)習(xí)者的特征進(jìn)行分析,根據(jù)其特征采用“組間同質(zhì),組內(nèi)異質(zhì)”的分組模式.“組間同質(zhì)”可以使各學(xué)習(xí)群體公平合理的競(jìng)爭(zhēng):“組內(nèi)異質(zhì)”可以使學(xué)習(xí)群體成員合理分工,互幫互助.在整體考慮學(xué)習(xí)群體互補(bǔ)性和親密性的基礎(chǔ)上,決定以多目標(biāo)優(yōu)化為視角,在融合求解后形成最優(yōu)在線學(xué)習(xí)群體.
基于2.1節(jié)中所提出的原則和需求,構(gòu)建多目標(biāo)優(yōu)化視角下在線學(xué)習(xí)群體形成模型MOLGFM,如圖1所示.
圖1 在線學(xué)習(xí)群體形成模型MOLGFMFig.1 Online learning group formation model MOLGFM
多目標(biāo)優(yōu)化視角下在線學(xué)習(xí)群體形成模型屬于三元組結(jié)構(gòu),包含3個(gè)子目標(biāo)函數(shù),即保證組內(nèi)互補(bǔ)的學(xué)習(xí)者特征函數(shù)f1、保證組內(nèi)親密的學(xué)習(xí)者特征函數(shù)f2以及保證組間公平的學(xué)習(xí)者特征函數(shù)f3,如表達(dá)式(1)所示.三者共同決定所形成的在線學(xué)習(xí)群體能否滿足要求.子目標(biāo)函數(shù)f1表示性別、認(rèn)知水平、學(xué)習(xí)風(fēng)格等特征在形成的在線學(xué)習(xí)群體內(nèi)部的差異,如表達(dá)式(2)所示;子目標(biāo)函數(shù)f2表示興趣愛(ài)好、學(xué)習(xí)時(shí)間、位置等特征在形成的在線學(xué)習(xí)群體內(nèi)部的差異,如表達(dá)式(3)所示;子目標(biāo)函數(shù)f3表示形成的各在線學(xué)習(xí)群體間的整體差異,如表達(dá)式(4)所示.
minimizeF(x)=(f1,f2,f3)
(1)
f1=(maxMSE(S,C,M))+(minError(S,C,M))
(2)
f2=(minMSE(HL,T,L))+(minError(HL,T,L))
(3)
f3=(minMSE(Gg)|i)+(minError(Gg)|i)
(4)
為了檢驗(yàn)在線學(xué)習(xí)群體形成問(wèn)題是否是多目標(biāo)優(yōu)化問(wèn)題,同時(shí)分析所提出的各子目標(biāo)函數(shù)之間是否存在沖突性.通過(guò)隨機(jī)初始化學(xué)習(xí)者的各項(xiàng)特征值,然后求解得到3個(gè)子目標(biāo)函數(shù)的值及變化狀態(tài),最后判斷3個(gè)子目標(biāo)函數(shù)的最小值所對(duì)應(yīng)的自變量是否為同一個(gè).經(jīng)檢驗(yàn)發(fā)現(xiàn),3個(gè)子目標(biāo)函數(shù)不存在在一個(gè)解上均達(dá)到最優(yōu)的情況,因此可認(rèn)為在線學(xué)習(xí)群體的形成問(wèn)題是多目標(biāo)優(yōu)化問(wèn)題.然后對(duì)各子目標(biāo)函數(shù)的變化狀態(tài)進(jìn)行分析,在不同子目標(biāo)函數(shù)上解的變化狀態(tài)是截然不同的,因此可認(rèn)為各子目標(biāo)函數(shù)之間是存在沖突性的.
首先將X個(gè)學(xué)習(xí)者分成Y組,學(xué)習(xí)者總?cè)后w由數(shù)組A表示,具體如表達(dá)式(5)所示.
A={A1,A2,A3,…,AX}
(5)
(6)
(7)
學(xué)習(xí)群體形成問(wèn)題是將定量的學(xué)習(xí)者分成指定個(gè)數(shù)的等量在線學(xué)習(xí)小組,每組學(xué)習(xí)者數(shù)量的個(gè)數(shù)為:X/Y.在初始學(xué)習(xí)群體形成后,所有學(xué)習(xí)者都應(yīng)用明確的標(biāo)準(zhǔn)進(jìn)行評(píng)估,因此,需要定義相應(yīng)的適應(yīng)度函數(shù)來(lái)對(duì)學(xué)習(xí)者進(jìn)行更加精確的分組.有學(xué)者提出可利用各在線學(xué)習(xí)群體的各項(xiàng)特征均值與學(xué)習(xí)者總?cè)后w的各項(xiàng)特征均值之差來(lái)衡量分組[15].
(8)
(9)
(10)
(11)
表達(dá)式(11)在最小化學(xué)習(xí)群體總誤差時(shí)并不能保證最小化每組在線學(xué)習(xí)群體的誤差.因此,在解決在線學(xué)習(xí)群體形成問(wèn)題時(shí),既要考慮學(xué)習(xí)群體的總誤差,又要考慮各學(xué)習(xí)群體中的各特征誤差.這便需要計(jì)算各在線學(xué)習(xí)群體與學(xué)習(xí)者總?cè)后w的百分比偏差,如式(12)和式(13)用于計(jì)算第g組的均方誤差和總偏差百分比.
(12)
(13)
(14)
(15)
3.2.1 粒子進(jìn)化狀態(tài)
圖2 粒子進(jìn)化狀態(tài)示意圖Fig.2 Schematic diagram of particle evolution state
3.2.2 GAMOPSO算法的偽代碼表示
開(kāi)始
輸入:種群規(guī)模N、最大迭代次數(shù)T
慣性權(quán)重ω,認(rèn)知系數(shù)C1,C2,C3
外部檔案Archive數(shù)量;
for t=1:MaxIt
for m=1:noP
calculate the fitness function;
選擇交叉粒子
計(jì)算粒子X(jué)m與各粒子之間的距離,選擇離Xm遠(yuǎn)的粒子X(jué)n作為交叉粒子
設(shè)定閾值H=0.5
if H<0.5
Delete Xn;
else
Xn→交配池;
end
粒子交叉生成中間粒子
Xm=[A,B;C,D]交叉Xn=[E,F;G,H]
Caculate fitness
else
end
中間粒子變異生成新粒子
將非劣解放入外部檔案并維護(hù);
采用輪盤賭策略從外部檔案中選擇全局最優(yōu);
慣性權(quán)重ω、個(gè)體認(rèn)知系數(shù)C1、社會(huì)認(rèn)知系數(shù)C2、探索認(rèn)知系數(shù)C3自適應(yīng)更新;
達(dá)到最大迭代次數(shù);
輸出:Pareto Optimality
結(jié)束
在GAMOPSO算法中,將多目標(biāo)粒子群算法中的粒子賦予遺傳算法中染色體的結(jié)構(gòu).以多目標(biāo)優(yōu)化為視角,融合遺傳算法和多目標(biāo)粒子群算法對(duì)算法改進(jìn)設(shè)計(jì).在前期依靠GA的交叉變異和全局探索能力以保證種群個(gè)體的多樣性,提供初步的優(yōu)化結(jié)果,保留全局捜索的優(yōu)勢(shì),在算法運(yùn)行的后期轉(zhuǎn)為執(zhí)行MOPSO,強(qiáng)化局部開(kāi)發(fā),提高收斂速度和計(jì)算精度.
3.3.1 編碼設(shè)置
遺傳算法需要將輸入特征進(jìn)行編碼,并將其轉(zhuǎn)換為問(wèn)題潛在解的染色體結(jié)構(gòu)來(lái)實(shí)現(xiàn)初始化.因此需要設(shè)計(jì)一個(gè)合適的染色體結(jié)構(gòu)來(lái)將學(xué)習(xí)者按預(yù)定需求分組為最優(yōu)學(xué)習(xí)群體.在定義染色體結(jié)構(gòu)的過(guò)程中,還需定義在線學(xué)習(xí)群體形成的組數(shù)和每組學(xué)習(xí)者數(shù)量,且應(yīng)保持兩者均不發(fā)生變化,因此本文將定量的學(xué)習(xí)者聚類到等大的學(xué)習(xí)群體中.
3.3.2 種群初始化
隨機(jī)產(chǎn)生初始種群需要預(yù)先設(shè)定染色體數(shù)目.新一代種群通過(guò)遺傳算子動(dòng)態(tài)調(diào)整基因值產(chǎn)生并進(jìn)化.每個(gè)學(xué)習(xí)者在每次迭代過(guò)程中可以通過(guò)遺傳算子改變其在染色體中的位置,從而形成最優(yōu)在線學(xué)習(xí)群體.因此,在種群初始化時(shí),染色體結(jié)構(gòu)中的數(shù)字應(yīng)以隨機(jī)分布.
3.3.3 適應(yīng)度函數(shù)計(jì)算
初始種群產(chǎn)生后,所有染色體粒子都應(yīng)用適應(yīng)度函數(shù)進(jìn)行精確評(píng)估.基于第2.3節(jié)中提出的多目標(biāo)在線學(xué)習(xí)群體形成函數(shù)求解計(jì)算每個(gè)學(xué)習(xí)群體序列在各個(gè)目標(biāo)函數(shù)上的適應(yīng)度值,以此檢驗(yàn)形成的在線學(xué)習(xí)群體是否符合需求.
3.3.4 遺傳算子應(yīng)用
為使形成的在線學(xué)習(xí)群體序列更好地滿足要求,可以應(yīng)用遺傳算子交叉和變異來(lái)進(jìn)行調(diào)整.對(duì)于最優(yōu)學(xué)習(xí)群體形成問(wèn)題,相關(guān)研究者應(yīng)用了一種順序交叉算子來(lái)產(chǎn)生后代[23],其主要過(guò)程是:首先,選擇父代1,并隨機(jī)選擇交點(diǎn),將得到的子字符串直接復(fù)制到子代1的相同位置.然后,將選擇的父代1基因在父代2中指定.最后,按順序?qū)⒏复?中未指定的基因在子代1中的空缺位置進(jìn)行填補(bǔ).而在最優(yōu)學(xué)習(xí)群體形成過(guò)程中,某些基因的隨機(jī)改變并不能保證新染色體的再現(xiàn),需要及時(shí)處理置換型染色體的突變,交換突變常被用來(lái)解決該問(wèn)題,即一個(gè)候選染色體的兩個(gè)隨機(jī)基因同時(shí)被選擇并交換其值,以此產(chǎn)生新的置換型染色體.
學(xué)習(xí)者在進(jìn)行在線學(xué)習(xí)時(shí)往往具有時(shí)間限制,因此應(yīng)該在保證在線學(xué)習(xí)群體滿足需求的前提下,盡可能縮短形成時(shí)間,從而使學(xué)習(xí)者有更多的時(shí)間完成在線協(xié)作學(xué)習(xí)任務(wù).形成的在線學(xué)習(xí)群體既能保證各學(xué)習(xí)群體中學(xué)習(xí)者之間互補(bǔ),又能確保在線學(xué)習(xí)群體間學(xué)習(xí)者之間的親密度,還能確保各在線學(xué)習(xí)群體之間的整體水平一致,公平合理的開(kāi)展組間競(jìng)爭(zhēng).本文在MOLGFM模型的基礎(chǔ)上,將遺傳算法與多目標(biāo)粒子群算法融合優(yōu)化形成GAMOPSO算法,并在此基礎(chǔ)上提出多目標(biāo)優(yōu)化視角下的在線學(xué)習(xí)群體形成方法GAMOPSO-FA,使其更好地解決在線學(xué)習(xí)群體的形成問(wèn)題.模型求解的具體流程如圖3所示.
圖3 MOLGFM模型求解流程Fig.3 MOLGFM model solving process
特征參數(shù)定義是建立多目標(biāo)優(yōu)化視角下在線學(xué)習(xí)群體形成模型的第一步,在2.1節(jié)中對(duì)模型中的各個(gè)參數(shù)進(jìn)行定義.在2.2節(jié)中對(duì)多目標(biāo)在線學(xué)習(xí)群體形成模型的整體框架進(jìn)行介紹,是否符合所定義的三維目標(biāo)是在線學(xué)習(xí)群體能否形成的核心.在2.3節(jié)中根據(jù)模型對(duì)多目標(biāo)在線學(xué)習(xí)群體形成函數(shù)進(jìn)行設(shè)計(jì).
在使用GAMOPSO算法對(duì)在線學(xué)習(xí)群體形成模型進(jìn)行求解時(shí),將與在線學(xué)習(xí)群體形成模型匹配度高的學(xué)習(xí)群體序列篩選出來(lái),當(dāng)?shù)h(huán)結(jié)束時(shí),將其輸出.由于學(xué)習(xí)者分組依靠所形成的學(xué)習(xí)群體序列,因此外部檔案中存儲(chǔ)的粒子將直接影響在線學(xué)習(xí)群體形成的分組結(jié)果,也將進(jìn)一步影響在線協(xié)作學(xué)習(xí)的效率和效果.因此要對(duì)外部檔案的存儲(chǔ)與管理進(jìn)行維護(hù),設(shè)定檔案大小為M,當(dāng)超過(guò)M值時(shí)便對(duì)其進(jìn)行更新和維護(hù).
本文所用編程平臺(tái)為 Matlab R2018a,硬件環(huán)境為intel處理器i5-4200M,操作系統(tǒng)為 windows 7,內(nèi)存4GB,主頻2.50GHz.
以MOLGFM模型為核心,利用Huband等人總結(jié)的七個(gè)測(cè)試函數(shù)TQ1-TQ7[24]來(lái)檢驗(yàn)所提GAMOPSO算法的性能.將本文提出的GAMOPSO算法與MOPSO(Multi-objective Particle Swarm Optimization)[25]算法、MOEA/D(Multi-objective Evolutionary Algorithm based on Decomposition)[26]算法、NSGA-III(Nondominated Sorting Genetic Algorithm-III)[27]算法做對(duì)比分析,通過(guò)收斂性[28]、多樣性[29]、成功率[30]、尋優(yōu)時(shí)間和時(shí)間復(fù)雜度來(lái)驗(yàn)證各在線學(xué)習(xí)群體形成算法的性能.
4.2.1 收斂性分析
逆世代距離IGD[28]是通過(guò)計(jì)算在真實(shí) Pareto前沿面上的每個(gè)點(diǎn)射向算法而獲取到的個(gè)體集合之間的最小距離和來(lái)評(píng)價(jià)算法的收斂性能,其值越小,算法收斂性能越好.計(jì)算公式如式(16)所示:
(16)
其中,P*表示的是均勻分布在真實(shí) Pareto 面上的點(diǎn)集,P表示的是算法在測(cè)試函數(shù)中搜索到的最優(yōu)非劣解集,d(v,P)表示個(gè)體v到種群P的最小歐式距離,v∈p*, |P*|為分布在真實(shí) pareto面上的點(diǎn)集個(gè)體數(shù).
表1是4種算法在7個(gè)測(cè)試函數(shù)上獲得的IGD均值和方差.從表中均值數(shù)據(jù)分析,MOPSO算法僅在測(cè)試函數(shù)TQ7上獲得最優(yōu)均值,MOEA/D算法和NSGA-III算法均未獲得最優(yōu)均值,而本文所提GAMOPO算法在TQ1至TQ6這6個(gè)測(cè)試函數(shù)上都獲得最優(yōu)均值,說(shuō)明GAMOPSO算法表現(xiàn)出較好的收斂性.從表1中方差數(shù)據(jù)分析,NSGA-III算法和MOEA/D算法均未獲得最優(yōu)方差,MOPSO算法在測(cè)試函數(shù)TQ3和TQ5上獲得最優(yōu)方差,而本文所提GAMOPO算法在測(cè)試函數(shù)TQ1、TQ2、TQ4、TQ6以及 TQ7上均獲得最優(yōu)方差,說(shuō)明所提算法GAMOPSO具有良好的穩(wěn)定性.這是因?yàn)镚AMOPSO算法將多目標(biāo)粒子群算法和遺傳算法進(jìn)行融合,解決了種群多樣性差,容易陷入局部最優(yōu),運(yùn)行時(shí)間長(zhǎng)等問(wèn)題,從而有效提升了GAMOPSO算法的整體優(yōu)化性能.
表1 4種算法的收斂性指標(biāo)均值和方差Table 1 Mean and variance of the convergence index of the four algorithms
4.2.2 多樣性分析
多樣性指標(biāo)可以用來(lái)測(cè)量非支配解集的多樣性情況,包括不是Pareto最優(yōu)集合的解集[31],其值越小,算法的多樣性越好.計(jì)算公式如式(17)所示:
(17)
表2是4種算法在7個(gè)測(cè)試函數(shù)上獲得的Delta指標(biāo)均值和方差.從表2中均值數(shù)據(jù)分析,MOPSO算法在測(cè)試函數(shù)TQ2和TQ4上獲得最優(yōu)均值,NSGA-III算法和MOEA/D 算法均未在測(cè)試函數(shù)上獲得最優(yōu)均值,而本文所提GAMOPSO算法在TQ1、TQ3、TQ5、TQ6和TQ7這4個(gè)測(cè)試函數(shù)上均得到最優(yōu)均值,說(shuō)明所提GAMOPSO算法具有較好的多樣性.從表中方差數(shù)據(jù)分析,GAMOPSO算法在測(cè)試函數(shù)TQ1至TQ3以及TQ5至TQ7上均獲得最優(yōu)方差,具有較好的穩(wěn)定性.這是因?yàn)镚AMOPSO算法將遺傳算法與多目標(biāo)粒子群算法相融合,改進(jìn)了兩者各自的不足,突出了兩者的結(jié)合優(yōu)勢(shì).通過(guò)圖4的5個(gè)二目標(biāo)測(cè)試函數(shù)圖像可看出GAMOPSO算法在二目標(biāo)測(cè)試函數(shù)上均能找到較好的Pareto前沿,且獲得的二目標(biāo)解在Pareto前沿圖像上均具有較好的分布,說(shuō)明GAMOPSO算法的分布性能優(yōu)于其他3種對(duì)比算法.通過(guò)圖5上的兩個(gè)三目標(biāo)測(cè)試函數(shù)圖像可看出,GAMOPSO算法得到的三目標(biāo)解大部分位于Pareto前沿面上.因此,GAMOPSO算法在7個(gè)測(cè)試函數(shù)中整體表現(xiàn)優(yōu)異.
表2 4種算法的多樣性指標(biāo)均值和方差Table 2 Mean and variance of the diversity index of the four algorithms
圖4 GAMOPSO算法在5個(gè)二目標(biāo)測(cè)試函數(shù)上解的分布圖Fig.4 Distribution diagram of GAMOPSO algorithm on five two-objective test function
圖5 GAMOPSO算法在2個(gè)三目標(biāo)測(cè)試函數(shù)上解的分布圖Fig.5 Distribution diagram of GAMOPSO algorithm on two three-objective test function
4.2.3 成功率分析
算法的成功率是指算法尋優(yōu)精度達(dá)到指定精度的次數(shù)與總尋優(yōu)次數(shù)之比.本文通過(guò)公式(18)計(jì)算指定精度AC的數(shù)值[28].
(18)
4種算法達(dá)到成功率和AC值的次數(shù)分別如表3至表6所示,從表中數(shù)據(jù)分析,GAMOPSO算法在7個(gè)測(cè)試函數(shù)上成功率均為80%以上,且均高于其他3種對(duì)比算法.這是因?yàn)镚AMOPSO算法融合遺傳算法和多目標(biāo)粒子群算法后實(shí)現(xiàn)算法全局搜索與局部開(kāi)采的平衡,因此,GAMOPSO算法獲得了較高的成功率.
表3 MOPSO算法的測(cè)試結(jié)果Table 3 MOPSO algorithm test results
表4 MOEA/D算法的測(cè)試結(jié)果Table 4 MOEA/D algorithm test results
表5 NSGA-III算法的測(cè)試結(jié)果Table 5 NSGA-III algorithm test results
表6 GAMOPSO算法的測(cè)試結(jié)果Table 6 GAMOPSO algorithm test results
4.2.4 尋優(yōu)時(shí)間分析
算法的尋優(yōu)時(shí)間即運(yùn)行一次算法求解問(wèn)題所用的時(shí)間.采用不同算法解決在線學(xué)習(xí)群體形成問(wèn)題時(shí),既要考慮各個(gè)算法形成在線學(xué)習(xí)群體的匹配性,同時(shí)也要考慮各個(gè)算法形成在線學(xué)習(xí)群體所用的時(shí)間,以大量時(shí)間為代價(jià)來(lái)提升精度的優(yōu)化算法方式并非完全可取.因此,可通過(guò)尋優(yōu)時(shí)間來(lái)進(jìn)一步分析,表3到表6中呈現(xiàn)了4種算法的尋優(yōu)時(shí)間均值.圖6以曲線對(duì)比圖的形式可以更加直觀的顯示.從圖6可看出,MOPSO算法在測(cè)試函數(shù)上所用時(shí)間最少.由于GAMOPSO算法增加了遺傳變異算子,因此所用時(shí)間略多于MOPSO算法.
圖6 4種算法尋優(yōu)時(shí)間分布圖Fig.6 Four algorithms to optimize the time distribution map
4.2.5 時(shí)間復(fù)雜度分析
設(shè)N為群體規(guī)模,總目標(biāo)數(shù)為M,外部檔案大小為(1/2)*N;GAMOPSO算法循環(huán)一次的主要復(fù)雜度估計(jì)如下:
1)初始生成種群的復(fù)雜度為O(MN);
2)粒子適應(yīng)度計(jì)算的復(fù)雜度為O(MN);
3)選擇交叉粒子的復(fù)雜度為O(MN2-MN);
4)生成中間粒子的復(fù)雜度為O(N(N-1));
5)中間粒子變異成新粒子復(fù)雜度為N;
6)非劣解生成與外部檔案維護(hù)的復(fù)雜度為O(M*(N2/2)).
綜上所述,GAMOPSO算法的時(shí)間復(fù)雜度如表達(dá)式(19)所示:
O(MN+MN+MN2-MN+N2-N+N+M*(N2/2))
=O(MN+MN2+N2)=O((M+1)N2)
(19)
根據(jù)文獻(xiàn)[26-28]可知,MOPSO算法、MOEA/D算法和NSGA-III算法的時(shí)間復(fù)雜度分別為O(MN2)、O(MTN2)和O(N2logM-2N).MOEA/D算法中的T為鄰域大小.由上述分析可知,GAMOPSO算法的復(fù)雜度略大于MOPSO算法,但小于MOEA/D算法;說(shuō)明所提算法的時(shí)間復(fù)雜度在可接受范圍內(nèi),GAMOPSO算法在提高性能的同時(shí),并不會(huì)以耗費(fèi)大量的時(shí)間為代價(jià).
在實(shí)驗(yàn)中,將多目標(biāo)優(yōu)化算法GAMOPSO構(gòu)成的GAMOPSO-FA方法與進(jìn)化算法中的隨機(jī)方法[32]和單目標(biāo)PSO-FA方法[33]、傳統(tǒng)的K-means聚類算法[34]以及第4.2節(jié)中的對(duì)比算法MOPSO、MOEA/D和NSGA-III構(gòu)成的在線學(xué)習(xí)群體形成方法,從公平性、互補(bǔ)性、親密性三方面對(duì)在線協(xié)作學(xué)習(xí)群體形成結(jié)果進(jìn)行對(duì)比分析.由于K-means聚類算法按照歐式距離值進(jìn)行分類,每次分類數(shù)目不一定,即形成的各在線學(xué)習(xí)群體中人數(shù)不一定,為了保證學(xué)習(xí)群體人數(shù)相等,本文根據(jù)誤差從小到大的順序,逐個(gè)中心點(diǎn)分配固定數(shù)目的點(diǎn),直至數(shù)目相等,確保形成的每個(gè)在線學(xué)習(xí)群體中人數(shù)相同.
4.3.1 數(shù)據(jù)集
本實(shí)驗(yàn)主要驗(yàn)證所提方法在小規(guī)模問(wèn)題上的優(yōu)化效果,適合小班化在線協(xié)作學(xué)習(xí)群體的形成.選擇一個(gè)包含30名學(xué)習(xí)者(編號(hào)為S1-S30)七項(xiàng)特征信息的模擬數(shù)據(jù)集,主要目標(biāo)是將學(xué)習(xí)者分成6個(gè)5人學(xué)習(xí)小組,在滿足預(yù)定的“組間同質(zhì),組內(nèi)異質(zhì)”原則的基礎(chǔ)上增加組內(nèi)親密度、互補(bǔ)度以及組間公平性.基于多目標(biāo)優(yōu)化視角下的在線學(xué)習(xí)群體形成模型,需考慮七項(xiàng)特征的取值范圍如表7所示,30名學(xué)習(xí)者各項(xiàng)特征值如表8所示.
表7 學(xué)習(xí)者特征的取值范圍Table 7 Range of learner characteristics
表8 學(xué)習(xí)者7項(xiàng)特征數(shù)據(jù)表Table 8 Learner′s seven characteristics data table
4.3.2 實(shí)驗(yàn)參數(shù)
本文所用到的實(shí)驗(yàn)參數(shù)設(shè)置如表9所示.
表9 所用實(shí)驗(yàn)參數(shù)表示及取值Table 9 Expression and value of experimental parameters used
4.3.3 評(píng)價(jià)指標(biāo)
1)公平性
由于在線協(xié)作學(xué)習(xí)過(guò)程中各學(xué)習(xí)群體間要開(kāi)展組間競(jìng)爭(zhēng),要保障在線協(xié)作學(xué)習(xí)群體的組間公平性,應(yīng)最大程度的確保各在線學(xué)習(xí)群體之間彼此相似,形成的各在線學(xué)習(xí)群體間應(yīng)保證學(xué)習(xí)者的各項(xiàng)特征處于相對(duì)平衡狀態(tài),即所形成的各在線學(xué)習(xí)群體內(nèi)學(xué)習(xí)者特征均值與學(xué)習(xí)者總體特征均值盡量一致.
2)互補(bǔ)性
為更好的讓在線協(xié)作學(xué)習(xí)群體內(nèi)成員間互幫互助,保證組內(nèi)異質(zhì)性,發(fā)揮“森林效應(yīng)”,應(yīng)將不同認(rèn)知水平和學(xué)習(xí)風(fēng)格的學(xué)習(xí)者混合分組,實(shí)現(xiàn)學(xué)習(xí)群體成員間特征互補(bǔ),即形成的在線學(xué)習(xí)群體內(nèi)部應(yīng)包含具有不同特征的學(xué)習(xí)者,在完成協(xié)作學(xué)習(xí)任務(wù)時(shí),各類型學(xué)習(xí)者的多種思考方式在組內(nèi)交互碰撞,實(shí)現(xiàn)頭腦風(fēng)暴,提高協(xié)作學(xué)習(xí)的效率效果,促進(jìn)學(xué)習(xí)者多種能力的培養(yǎng).
3)親密性
為解決學(xué)習(xí)者在學(xué)習(xí)群體內(nèi)歸屬感低的問(wèn)題,將具有相同興趣愛(ài)好、學(xué)習(xí)時(shí)間等特征的學(xué)習(xí)者劃分到同一小組,不僅能夠增加在線學(xué)習(xí)群體內(nèi)成員間的互動(dòng),提升學(xué)習(xí)群體內(nèi)成員間親密度,而且能夠方便教師有針對(duì)性的制定教學(xué)目標(biāo),從而更好凸顯協(xié)作學(xué)習(xí)的優(yōu)勢(shì),呈現(xiàn)出在線協(xié)作學(xué)習(xí)的最佳效果.
4.3.4 實(shí)驗(yàn)結(jié)果
基于隨機(jī)方法、單目標(biāo)PSO-FA方法、K-means聚類方法以及多目標(biāo)粒子群MOPSO-FA(Multi-objective Particle Swarm Optimization-Formation Approach)方法、分解類多目標(biāo)MOEA/D-FA(Multi-objective Evolutionary Algorithm based on Decomposition-Formation Approach)方法、多目標(biāo)遺傳NSGA-III-FA(Nondominated Sorting Genetic Algorithm-III-Formation Approach)方法和本文所提出的多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體分組結(jié)果及各學(xué)習(xí)群體中各個(gè)特征的均值和誤差結(jié)果如表10至表16所示.
表10 隨機(jī)方法形成的學(xué)習(xí)群體結(jié)果Table 10 Learning group results generated in a random method
表11 單目標(biāo)PSO-FA方法形成的學(xué)習(xí)群體結(jié)果Table 11 Learning group results generated by single-target PSO-FA method
表12 K-means聚類方法形成的學(xué)習(xí)群體結(jié)果Table 12 Learning group results generated by K-means clustering method
1)公平性分析
學(xué)習(xí)群體的組間公平性體現(xiàn)在:學(xué)習(xí)群體劃分后應(yīng)保障各在線學(xué)習(xí)群體間學(xué)習(xí)者的特征均值與學(xué)習(xí)者的總體特征均值盡量維持一致,即基于性別、認(rèn)知水平、學(xué)習(xí)風(fēng)格特征的各學(xué)習(xí)群體間沒(méi)有顯著差異,從而確保各學(xué)習(xí)群體間水平一致.通過(guò)表8及表10至表16可知,在性別特征方面,隨機(jī)方法、單目標(biāo)PSO-FA方法、K-means聚類方法、多目標(biāo)粒子群MOPSO-FA方法、多目標(biāo)遺傳NSGA-III-FA方法均出現(xiàn)性別比例1:4或4:1的在線學(xué)習(xí)群體,分解類多目標(biāo)MOEA/D-FA方法更是出現(xiàn)性別比例為0:5的在線學(xué)習(xí)群體,而多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體性別比例均為2:3或3:2,在性別比例方面相對(duì)平衡;在認(rèn)知水平特征方面,隨機(jī)方法出現(xiàn)83.6、63.4,單目標(biāo)PSO-FA方法出現(xiàn)79.8,K-means聚類方法出現(xiàn)67.4,多目標(biāo)粒子群MOPSO-FA方法出現(xiàn)80.4和67.6,分解類多目標(biāo)MOEA/D-FA方法出現(xiàn)62.8和83.8,多目標(biāo)遺傳NSGA-III-FA方法出現(xiàn)63.6、66.8和89.2等與總體認(rèn)知水平均值72.5相差較大的在線學(xué)習(xí)群體,而多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體認(rèn)知水平均值在總體認(rèn)知水平均值72.5上下浮動(dòng),所形成的在線學(xué)習(xí)群體在認(rèn)知水平特征上整體處于相對(duì)公平的狀態(tài);在學(xué)習(xí)風(fēng)格特征方面,隨機(jī)方法、K-means聚類方法以及多目標(biāo)遺傳NSGA-III-FA方法獲得的結(jié)果較佳,所形成的各組在線學(xué)習(xí)群體學(xué)習(xí)風(fēng)格均值與總體均值2.73相對(duì)接近,而單目標(biāo)PSO-FA方法、多目標(biāo)粒子群MOPSO-FA方法、分解類多目標(biāo)MOEA/D-FA方法、多目標(biāo)遺傳NSGA-III-FA方法及多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體均存在同組中相同學(xué)習(xí)風(fēng)格者較多的現(xiàn)象.總體來(lái)看,多目標(biāo)GAMOPSO-FA方法優(yōu)于其他對(duì)比方法,形成的各最優(yōu)在線學(xué)習(xí)群體特征值更加接近,具有較高的公平性,能夠更好地開(kāi)展組間競(jìng)爭(zhēng).
表13 多目標(biāo)MOPSO-FA方法形成的學(xué)習(xí)群體結(jié)果Table 13 Result of learning group formed by multi-objective MOPSO-FA method
表14 多目標(biāo)MOEA/D-FA方法形成的學(xué)習(xí)群體結(jié)果Table 14 Result of learning group formed by multi-objective MOEA/D-FA method
表15 多目標(biāo)NSGA-III-FA方法形成的學(xué)習(xí)群體結(jié)果Table 15 Results of learning group formed by multi-objective NSGA-III-FA method
表16 多目標(biāo)GAMOPSO-FA方法形成的學(xué)習(xí)群體結(jié)果Table 16 Learning group results generated by Multi-objective GAMOPSO-FA method
2)互補(bǔ)性分析
學(xué)習(xí)群體的組內(nèi)互補(bǔ)性體現(xiàn)在:形成的在線協(xié)作學(xué)習(xí)群體內(nèi)部成員間在認(rèn)知水平與學(xué)習(xí)風(fēng)格特征上的差異程度.針對(duì)認(rèn)知水平特征,通過(guò)表8及表10至表16可知,隨機(jī)方法形成的第2、4、5組,單目標(biāo)PSO-FA方法形成的第4、6組,K-means聚類方法形成的第2、3、4組,多目標(biāo)粒子群MOPSO-FA方法形成的第4組,分解類多目標(biāo)MOEA/D-FA方法形成的第2、6組,多目標(biāo)遺傳NSGA-III-FA方法形成的1、3、4、5組,學(xué)習(xí)群體成員之間存在整體認(rèn)知水平較高或較低的現(xiàn)象,互補(bǔ)性不夠突出;而多目標(biāo)GAMOPSO-FA方法形成的每個(gè)在線學(xué)習(xí)群體內(nèi)學(xué)習(xí)者認(rèn)知水平差異程度相對(duì)較大,認(rèn)知水平高的學(xué)習(xí)者可以幫助指導(dǎo)認(rèn)知水平低的學(xué)習(xí)者,互補(bǔ)性較強(qiáng).針對(duì)學(xué)習(xí)風(fēng)格特征,隨機(jī)方法和K-means聚類方法形成的第6組,多目標(biāo)粒子群MOPSO-FA方法和多目標(biāo)遺傳NSGA-III-FA方法形成的第1、4組學(xué)習(xí)群體內(nèi)僅有兩種學(xué)習(xí)風(fēng)格的學(xué)習(xí)者,單目標(biāo)PSO-FA方法、分解類多目標(biāo)MOEA/D-FA方法和多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體內(nèi)均含3種及以上學(xué)習(xí)風(fēng)格類型的學(xué)習(xí)者.總體來(lái)看,多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體能夠凸顯出較強(qiáng)的互補(bǔ)性,有利于更好地集思廣益,開(kāi)拓思路.
3)親密性分析
學(xué)習(xí)群體的組內(nèi)親密性體現(xiàn)在:形成的在線協(xié)作學(xué)習(xí)群體內(nèi)部成員間在興趣偏好、學(xué)習(xí)偏好、學(xué)習(xí)時(shí)間、位置等特征上的相似程度.通過(guò)表8及表10至表16可知,隨機(jī)方法形成的在線學(xué)習(xí)群體僅在學(xué)習(xí)偏好特征上的組內(nèi)差異性較小,單目標(biāo)PSO-FA方法、多目標(biāo)粒子群MOPSO-FA方法、分解類多目標(biāo)MOEA/D-FA方法形成的在線學(xué)習(xí)群體僅在學(xué)習(xí)時(shí)間特征上組內(nèi)差異性較小,K-means聚類方法形成的在線學(xué)習(xí)群體在學(xué)習(xí)時(shí)間和學(xué)習(xí)偏好上組內(nèi)差異性不明顯,而多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體在興趣愛(ài)好、學(xué)習(xí)偏好、學(xué)習(xí)時(shí)間等特征上均表現(xiàn)出較小的組內(nèi)差異性,具有明顯的組間親密性.以多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體為例,在學(xué)習(xí)偏好特征方面,第1、2組傾向于文字類學(xué)習(xí)資源,第3、6組傾向于視頻類學(xué)習(xí)資源,第4組傾向于音頻類學(xué)習(xí)資源,第5組傾向于圖片類學(xué)習(xí)資源;在學(xué)習(xí)時(shí)間方面,第1、2、3、5組均傾向于在上午學(xué)習(xí),第4組傾向于在下午學(xué)習(xí),第6組傾向于在晚上學(xué)習(xí).總體來(lái)看,多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體在多個(gè)特征上具有組間親密性,有利于更加順利的開(kāi)展完成在線在協(xié)作學(xué)習(xí)任務(wù).
通過(guò)上述分析可發(fā)現(xiàn),GAMOPSO-FA方法的各項(xiàng)特征誤差值均較低,說(shuō)明該方法的擬合實(shí)驗(yàn)數(shù)據(jù)能力強(qiáng),具有較好表現(xiàn).以多目標(biāo)GAMOPSO-FA方法形成的在線學(xué)習(xí)群體不僅優(yōu)于傳統(tǒng)的進(jìn)化算法,而且也優(yōu)于基本的聚類算法,說(shuō)明多目標(biāo)GAMOPSO-FA方法在在線學(xué)習(xí)群體形成方面具有較大優(yōu)勢(shì).
本文以多目標(biāo)優(yōu)化為視角解決在線學(xué)習(xí)群體形成問(wèn)題,建立多目標(biāo)優(yōu)化視角下在線學(xué)習(xí)群體形成MOLGFM模型.在總結(jié)在線學(xué)習(xí)群體形成影響因素的基礎(chǔ)上,設(shè)計(jì)融合遺傳算法與粒子群算法的多目標(biāo)優(yōu)化算法GAMOPSO,提出多目標(biāo)優(yōu)化視角下的在線學(xué)習(xí)群體形成方法GAMOPSO-FA.通過(guò)對(duì)包含30名學(xué)習(xí)者特征信息的數(shù)據(jù)集進(jìn)行分析,發(fā)現(xiàn)GAMOPSO-FA方法能夠以較少時(shí)間為代價(jià)形成具有組間親密性、組間互補(bǔ)性及組間公平性的最優(yōu)在線學(xué)習(xí)群體,證明GAMOPSO-FA方法在在線學(xué)習(xí)群體形成方面具有良好的性能.未來(lái)通過(guò)對(duì)學(xué)習(xí)者特征的豐富和完善以及學(xué)習(xí)者數(shù)量的擴(kuò)大,將進(jìn)一步驗(yàn)證所提方法的可行性,進(jìn)而提高形成方法的穩(wěn)定性和適用性,形成更加合理的在線協(xié)作學(xué)習(xí)群體.