Abstract — An attempt is made to apply Ant Colony Optimization (ACO) heuristics to an E-learning problem: the pedagogic material of an online teaching website for high school students is modelled as a navigation graph where nodes are exercises or lessons
IV.IMPLEMENTATIONOFTHEANTCOLONY:
ALGORITHMICOVERVIEW
Allnodes(htmlpages)ofthenewParaschoolsoftwarenowcontainanewACO-poweredNEXTbuttonthatleadstheuseralonganarcchosenbyaselectionalgorithm(seesectionV),basedontheprobabilityassociatedwiththearc.Thisprobabilityiscomputedbytakingseveralfactorsintoaccountinthedesignofaweighted tnessfunctiondescribedinthenextsection.Thesefactorsarethefollowingandplayatboththeindividualandcollectivelevels:A.PedagogicWeights:W
Thispedagogicalweightisthemainvalueofeacharc.Itisimplementedasastatic(i.e.“global”)variable(W),accessibletoallants.(W)issetbytheParaschoolteachersandre ectstherelativeimportanceofthearcsthatcomeoutofaparticularnode.Inotherwords,theteachersencouragethestudentstogotowardsuchorsuchexerciseaftersuchorsuchlessonbygivingthecorrespondingarcahigherweight.ThisvaluationofthegraphdescribesthepedagogicstructurethatwillbeoptimizedbytheACOalgorithmB.Pheromones:SandF
Therearetwokindsofpheromonesthatcanbereleasedonarcstore ectstudents’activity:
S:successpheromone.
This oatingpointvalueisincrementedbyants/studentsontheadequateincomingarcswhentheyaresuccessfulincompletingthecorrespondingexercise.
F:failurepheromone.
ThislastvalueisS’scounterpartforfailure.Thesepheromonesarereleasednotonlyonthearcthatledtheanttothatnodebutalsoonpreviousonesintheant’shistorywithdecreasingamplitude.Thisismeanttore ectthefactthattheoutcomeofaparticularnode(exercise)isin uencedbyallthenodes(lessons,exercises)theantwentthroughbeforebutwithanin uencethat,ofcourse,diminisheswithtime.Forobviouspragmaticalreasons,this´’backpropagation`‘ofpheromonereleaseislimitedinscope(atypicalvalueof4hasbeenagreedupon).Toillustratethis,letusconsideranantthatwentthroughnodesA,B,C,D,E,FandthatreachesnodeG.WhenitvalidatesnodeGwithsuccess,1unitofsuccesspheromoneisdroppedonarc(F,G),1/2unitonarc(E,F),1/3ofaunitonarc(D,E)and1/4onarc(C,D).Inaddition,toallowfordynamicadaptabilityofthesepheromoneamounts(SandF),evaporationisperformedonaregularbasis,usuallyeveryday,byreducingSandFinagivenproportionτtypicallyaround0.999:
St=τ St 1;Ft=τ Ft 1
(1)
.
C.PersonalHistory:H
Thisvariablebelongstoeachant,andbearsinformationonvisitednodes.Eachtimeanodeisvalidated,ahistoryvariableH,speci c=0.5toifeachitisant,asuccess,iscreated,tohstoredindatabaseandsettoh1usedasmultiplicative2=0.75ifitisafailure.Thisvaluewillbelaterfactortoreducetheprobabilitytovisitthatnodeagain.Wheniteventuallyhappens,HisagainmultipliedbyhHevaporatesandtendtogobackto1orh1with2.JustlikeSandF,time,following:
Ht=Ht 1(1+
1 Ht 11 e τx
Ht 11+e τx
)(2)
whereτisaconstantusedtotunetheevaporationspeedandxistheamountoftimeelapsedsincethelastvisittothatnode.τshouldbecalibratedtocorrespondtothevolatilityofthestudents’memory:
τ=
11+αxln(1 α)(3)with
α=
Ht Ht 11 Ht 1
(4)
Providedonede neswhat“forgettinganexercise”means,forinstanceifitsHvalue,fromHt 1,=this0.5gives(onevisitα≈withsuccess),growsbacktoHt 1=0.92.2andthepedagogicteamthenonlyhastoestimatethetimeittakesto“forgetanexercise”:oneweekforexample(x=604800sec.givesτ≈3.6E 6
V.SELECTIONPPROCEDURES:CONTROLANDSPEEDOF
THEDECISIONPROCESSThissectiondescribeshowanarcisselectedwhenauserpressesontheACO-poweredNEXTbutton.ThepurposeoftheACOalgorithmistoallowforanappropriatebalancebetweenthefactorsthatshoulddictateanidealpedagogicstructuration:teachers’opinion,collectiveexperienceandin-dividualhistory.Foreacharca,thisbalanceisrepresentedbya“ tness”value:
f(a)=H(ω1W+ω2S ω3F)
Thehigherthisvalue,themore“desirable”thecorrespondingarcwillbeandconsequentlythemorelikelywillitbeforittobesuggestedtostudents.Oneseesthatanarcisdesirablewhen:
itsendingnodewasnotvisitedorvisitedalongtimeago(Hcloseto1)
itthere’sisencouragedbyprofessors(highW)
littlefailureanatmospherehappenedofaroundsuccessthataroundarc(lowthatFarc)
(highS) Onealsocannoticethattherelativein uencesofthedifferentfactorscanbetunedbytuningtheωAfteranodehasbeenvalidated,theivalues.
outgoingarcsaresortedaccordingtothiscomputed tnessvalue.OnearcispickedamongthewholelistfollowingoneoftheselectionproceduresdescribedbelowandissuggestedtothestudentthroughtheNEXTbutton.
热门文档