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
Fiveselectionmechanismsareimplemented:Roulette-Wheelselection:
Withthisverytraditionalprocedure([8]),theprob-abilityforarcaitobepickedisproportionaltoits tness:
p(ai)=
f(ai)
j=if(aj)Thismethodhastheadvantagetobeentirelyauto-maticandverysensitiveto tnessvariation.Ontheotherhand,ifanarcbecomesreallypreponderenttheothershavereallyfewchancestobeselected.Besides,onehasnocontrolovertheselectionpres-sure.
Rankingbasedselection:
Inthiscase,probabilityisreverselyproportionaltothearc’srank.Theselectionprocessisagainentirelyautomatic,butitcancelstheundesirableeffectsoflargediscrepanciesin tnessvalues.Asasideeffect,subtledifferencesintroducedbygradualreleaseofpheromonesmightnotbetakenintoaccount.Rankingselectionwithmanualthresholds:
Thisre nementofthepreviousmethodallowsthedesignertomanuallysettheprobabilitiesforanarctobeselectedcorrespondingtoitsrank.Thismethodgivescompletecontrolbutnecessitatesheavyandprobablynontrivialparameterisation.Tournamentselection:
s1outgoingarcsarerandomlychosenoutofthetotalnumberofoutgoingarcsandthebestoneisselected.Thismethodisef cientandgivescontroloverselectionpressurewithasingleparameter.StochasticTournamentselection:
Theworstarcisselectedbydefault.s1challengersaregoingtotriedinarow.Ifthechallenger’s tnessishigher,itreplacesthecurrentlyselectedarcwithprobabilitys2.Using2parameters,thismethodgivesamorere nedcontrolovertheselectionpressure.TheprosandconsofthevariousselectionproceduresarequitewellknowninthecontextofGeneticAlgorithms(seeforexample[9]).Althoughmostprosandconsremainthesameitisimportanttounderstandthatthechoiceoftheseselectionsschemeisextremelyimportantinthepresentedsystem.
Thechoiceoftheselectionschemeandpressurescondi-tions:
Reactivity
sconditionsthespeedwithwhichanarc,whichemergesasexcellent,reachesthestatewhereitissystematicallysuggestedtostudents.Inotherwords,thehighertheselectionpressure,thefasteransuc-cessfulpathisgoingtotakeoveritsneighbours.Controllingthevelocityofsuchsystemisreallyafundamentalissue:atooreactivesystemwouldbechaoticandwouldn’tmakeanysensewhileatooreluctantsystemwouldnotre ectanyofthedynamictheinformationbroughtbystudents.
Control
Thissystemisinteractiveandassuch,needspar-ticularcareregardingthewayitisparameterizable.Manyparametersallowformorefreedombutre-quiremoreeffortsontimespentoncalibration.Therangeofimplementedselectionproceduresgoesfromentirelyautomatictocompletelytunablewiththepossibleintermediatestepsof1or2parameters.Signal
Inthisalgorithm,arcs’ tnessisare nedquantityconstantlyandsmoothlyupdatedbytinystigmergicinformation.Choosingrank-basedmethodsmightleadtogreatinformationloss,unlesslarge tnessdiscrepanciesareobserved.
Theselectionproceduremustthereforebecarefullychosenandtunedtogettheappropriateamountofspeed,controlandinformation.Asacompromise,mostthepresentedex-perimentswererealisedwithastochastictournamentforthereasonthatitisreactive,tunableandsaferegardinganotyetproperlycalibrated tnessfunction.
VI.CONDUCTEDEXPERIMENTS
Thedescribedsystemhasnotyetbeentriedonlinewiththe10000studentsofParaschool.Itisthereforenecessarytomakesureasmuchaspossiblethatexpectedbehaviouroccurbeforelargescalereal-worldtestsareconducted.A.SimulationHypotheses
Amodelofuserpopulationhasbeenderivedtoconductsimulationtests:
Eachant,representingavirtualstudent,isgivenacertainlevel,representedbya oatingpointnumbersituatedbetween0.0and1.0.Thisvalueisnormallydistributedoverthepopulationofstudentswithmean0.5andstandarddeviation1/3.
Eachexerciseisassignedadif cultyvalue,alsobetween0.0and1.0.Whenanantarrivesatagivennode,ifitslevelallowsittovalidatethenode(level>dif culty),itsucceeds,otherwise,itfails.Pheromonesarereleasedaccordingly.
Generalcalibrationofthealgorithmisperformedona“real”graph,i.e.correspondingtoanactualpartoftheParaschoolwebsite(the“Vectors”chapterofamathematicscourseforhighschoolstudentsaroundage14).ArcsbetweennodesandcorrespondingweightshavebeenassignedbytheParaschoolpedagogicalteam.
Thesamplecaseisthereforerealistic(20nodes,47arcs)andconstitutesameaningfulstructureinrealsize.B.AnElementaryTestCase
Severalfeaturesareexpectedfromtheantcolony.Inpartic-ular,itshouldbeabletocorrectinappropriatearcpedagogicalweightvalues.
Toinvestigatethisproperly,afteraroughcalibrationandobservationprocessconductedontherealsizedgraphmen-tionedabove,experimentsaremadeonareducedgraphthatexhibitssuchasituation,asillustratedby gure1.After
热门文档