A Case-Based Reasoning Approach to Formulating University Timetables Using Genetic Algorith

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

ACase-BasedReasoningApproach

toFormulatingUniversityTimetables

UsingGeneticAlgorithms

AliciaGrechandJulieMain

LaTrobeUniversity,Bundoora3086,Australia

{a.grech,j.main}@latrobe.edu.au

Abstract.Thispaperpresentsatechniquetoconstructgenericuni-versitytimetablesusingcase-basedreasoning(CBR)withgenetical-gorithms(GAs).Thecase-basedreasoningmethodologyallowsapastmemoryoftimetablestobestoredandaccessedviaretrievalmecha-nisms, ndingapastsolutionmost ttingtothenewtimetableinputproblem.Intheinstancethatapastsolutionisnotwellsuitedtothenewtimetablerequirements,ageneticalgorithmisemployedtoadaptthepasttimetablesinthecasememory.Thehybridtechniqueusedimple-mentsalearningmechanismtoaidintherevisionandadaptationofnewtimetablesolutions.Thefocusofthistechniqueisafeedbackmechanismwhichallowsthesystemtodiagnosetheviolationofhard-constraints ttedtotimetablecreation.

1Introduction

Theproblemofcreatingavalideducationaltimetableinvolvesschedulinglessons,teachersandroomsintoa xednumberofperiods,insuchawaythatnoteacher,classorroomisusedmorethanoncepertimeperiod[1].Whencreatinganewtimetable,previouspartsoftimetablesareoftenre-used,basedonthefactthatconstraintsinanewtimetableproblemdonotusuallychangesigni cantlyfromapasttimetable[2].Case-basedreasoning(CBR)isamethodologythat ndssolutionstonewproblems,usingsolutionsfrompreviousproblemsaswellastheexperiencedgainedfromsolvingthoseproblems.ThisisamotivatingfactorforapplyingCBRtotimetablecreation.InCBR,pastsolutionsrelatedtoanewproblemareretrievedandifrequired,pastsolutionscanthenbeadaptedtomeetthedemandsofanewproblem.Thecentralprocessestobeexecutedinallcase-basedreasoningmethodshavebeenidenti edbyAamodtandPlaza[3]as:identifythecurrentproblem; ndapastcasesimilartothenewcase(retrieve);usethepastcasetosuggestasolutiontothecurrentproblem(reuse,alsoknownasadaptation);evaluatetheproposedsolution(revise);andupdatethesystembylearningfromexperience(retain).

ThoughtheuseofpastexperienceinsolvingproblemsisanadvantageofCBR,afewphasesaredi culttoengineerintheCBRcycle,especiallyintheretrieveandreusephases.Geneticalgorithms(GAs)areadaptivemethodsR.Khoslaetal.(Eds.):KES2005,LNAI3681,pp.76–83,2005.

cSpringer-VerlagBerlinHeidelberg2005

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

ACase-BasedReasoningApproachtoFormulatingUniversityTimetables77appliedtosolvesearchandoptimisationproblems,basedongeneticprocesses.ApplyingGAsintheCBRadaptationstageacrossvarieddomainshasbeenshowntobeasuccessfulinnovationovertraditionalCBRadaptationtechniques(seesection2).ThisislikelytobesoasCBRadaptationtendstobeverydomainspeci c[4].ThehybridCBR-GAapproachiswell ttedtoatimetablingdomain,asusingaGAtoadaptpreviouscasescanmaketheoutputcasemorenovelthanprevioussolutionswhichmaynot tthenewcaserequirementsclosely.WeapplyaGAattheadaptationstageoftheCBRcycle,exploitingthemutationoperationinorderto ndmorenovelsolutions.AfterapplyingGAadaptation,wecollectknowledgeattherevisestageoftheCBRcycle,withtheintenttofeedthisknowledgebackintoadaptationtoaidin ndinghealthiermutationstoapply.Wealsoperformcasetochromosomemappingmaintenance,includingrepairingsolutionsthatareinanincorrectformatduetounequalchromosomelengths.

2PastApplicationsUsingGAsinCBR

LouisandXuapproachedopenshopschedulingandre-schedulingproblemswithahybridCBR-GAsystem,injectingcasesintoageneticalgorithm’spopulationtospeedupandaugmentgeneticsearch.ThepreliminaryresultsindicatedthatthecombinationofGAswithCBRquickly ndsbettersolutionsthanCBRonitsown[5].DomainscoveredusingtheGAcomponentwithinretrievaloradaptationincase-basedreasoninginclude:tabletformulation[6,7];modellingaCheckersgame[8];OpenShopSchedulingandRescheduling[5];developinglayoutdesignofresidencessotheyconformtotheprinciplesoffengshui[4];andestimatingthe owratesinEstuaries[9].

3ApplicationoftheTimetablingProblem

UsingCBR-GA

Thegoalofthisworkwastoimplementacase-basedreasonertosolvenewproblemsinvolvingUniversitytimetables,thenadaptunsatisfactoryretrievedsolutionsusingaGA,feedingknowledgelearntfromtheGAadaptationbackintofutureadaptations.Ourimplementationdomainfocusesoncreatingtimeta-blesforLaTrobeUniversity’sDepartmentofComputerScienceandComputerEngineering.Duetothesizeandcomplexityofthetimetablingproblem,thescopeandsizeoftheproblemdomainhasbeenreducedusingsomeconstraints.Aprototypecase-basedreasonernamedCBR-GAALTA(CBRGeneticAlgo-rithmAdaptiveTimetablingLearningApplication)wascreatedthathandlestimetableschedulecases.

Therequirementsforanewtimetablearrivesintheformofa‘newcase’totheCBRsystem,specifyingthenumberoflabs,lectures,andproblemclassesrequiredplustheexpectedclasssizes.Thepurposeofthecase-basedreasoneristoretrieveatimetablefromacase-baseofprevioustimetables,thatmatchesthenewcaseascloselyaspossible.Ifthissolutionisinsu cientitshouldbeadapted,creatingatimetablethatisadjustedtosuittheinputrequirements.

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

78AliciaGrechandJulieMain

4CreatingTimetableswithCBRandGAs

ManyissuesarerelatedtoimplementingthecentralprocessesexecutedinthegeneralfourstepCBRcycle.Themajorissuesassociatedwithexecutingthecentralprocessesinclude:appropriatelyrepresentingacase;properlyindexingandstoringcasesinacasememory(casebase);andassigningrelevancefunc-tions.Eachprocessincludesarangeoftasksthatmustbeengineeredtowardsthespeci cationsofatimetablingdomain.

Thereasoningprocessisheavilydependentonthestructureandcontentofthecollectionofcasesstored[3,10].Forourapplicationtothetimetablingdo-main,acaserepresentsanentiresolutiontoatimetable,forallsubjectsonalldaysoftheweek.ThisimpliesthatthecontentofacaseistheSubjectname,Lecturer,RoomandLessonforasmanysubjectLessonsthatexistwithinatimetableforaregularschoolweek.Basedonthis,timetableobjectsarecom-posedofthesefourotherobjectscontainingtheinformationmostrelevanttoatimetable.Eachoftheobjectscontainattributesthatmakethetimetablero-bust,andareparamounttoawell-de nedcaseusingrelevant,traceabledata.Figure1isaUMLrepresentationofatimetablecase,displayingallobjectsandattributesstoredwithinatimetable.

Fig.1.ObjectOrientedCaseFormat.

Toretrievepastcases,apartialproblemdescriptionentersthesystemintheformofanewcase.Retrievalendswhenapastcasehasbeenfoundthatbestmatchesthenewcase.Eachcaseinthecasememoryistestedforarelevancefactorwithrespecttothenewinputproblem,wheretherelevancefactorindicatestheclosenessinsimilaritybetweencasesincasememoryandthenewinputcase.

Apointawardingschemewasdevelopedtoevaluatearelevancefactor.Toawardrelevance,tenrelevancemetricsweredevelopedandarecalculatedacrossthenewcase,y,andforthecomparisonpastcase,x.Thisschemerewardspastcaseswithverysimilarcontenttothenewcase,andpunishespastcaseswithlesssimilarcontent.

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

ACase-BasedReasoningApproachtoFormulatingUniversityTimetables79Therelevancemetriccanbemathematicallyexplainedas:

Relevance=10

p=1PMp

WherePMistheamountofpointsawardedfortheperformancemetric,p.

Iftheretrievedsolutionisnotdetailedenoughtobeasolutionforthenewproblem,thenmodi cation(adaptation)maybeneeded.Inthiswork,theuseofaGAtoadaptcaseswillminimisetheburdenonretrievaltechniques,aswellascreatenovelcasesthatareuniqueandnotrepetitive[8].

Revisionofcasesallowslearningfromfailure.Ifanincorrectcasesolutionisgeneratedduringthereusestage,thesolutioncanberevisedand xed[11].Atretaintheuserdecideswhethertoaddasolutiontothecasebase,orwhethertorejectit.Retainalsogivetheuseranopportunitytoaddanyextradomainrulestothesystemthatwentunnoticedbeforeevaluationofthecurrentsolution.Thisallowsnewrulestobeusedforvalidatingsolutionsnexttimethesystemisrun.

4.1UsingaGeneticAlgorithmforCaseAdaptation

Ageneticalgorithmmimicsgeneticprocessesofbiologicalorganisms,usingprin-ciplesofnaturalselectionand‘survivalofthe ttest’toevolvesolutionstorealworldproblems,whensuitablyencoded[12,13].GeneralissuesassociatedwithintegratingaCBRcyclewithaGAforadaptationareencodingacasetoaGAchromosome;determiningaparentselectionscheme;determininga tnessfunctioncorrelatingtorelevanceintheCBRprocess;andsettingGAmainpa-rameters.TheGAimplementedforcaseadaptationfollowsthestepsofasimpleGA.DetailsofthiscyclecanbefoundinMitchell[14].Forourapplication,themainparameterstorunaGAhavebeensetatthevalueslistedinTable1.ThecrossoverprobabilityissettoastandardvalueforaGA[14],thoughthemuta-tionprobabilityissetatahighervaluethanusual(0.001isastandardvalueforPm[14]).Thisprobabilityhasbeensethighertoallowtheapplicationtofullytestthepotentialformutationstothoroughlyexaminethesearchspace.Thisgivesourapplicationtheopportunitytogreatertestlearningthroughmutations,allowinglearningtobefedbackintocasereuse.

Table1.GAMainParameters.

GAParameter

SizeofPopulation

NumberofGenerations

CrossoverProbability(Pc)

MutationProbabilityPm)AssignedValue751000.70.01

InordertotranslateaCBRcasetoaGAchromosome,amappingneededtobeestablishedtoallowgeneticoperations(crossoverandmutation)tobeper-formed.Whenmappingthetimetablecasetoachromosome,thetypicalbit

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

80AliciaGrechandJulieMain

stringorintegerrepresentationwasnotsu cient,asthetimetablecaseusesrichsymbolicnotation.Thechromosomemappingneededgenes(encoding‘traits’withintheproblem)andalleles(‘settings’foreachofthetraits)tobeextractedfromthecaseinformation,thenencodedintoconsecutiveblocksofvectorspaces.Subjectlessonswerethegenesforourchromosomemapping,withtheallelesinthegenesbeingtheattributeswithinasubjectlesson.WithreferencetoFigure1,eachgenecontainsSubject,Lesson,LecturerandRoominformation.Thealle-lesweresettoeachattributeofthisobject,suchasthesubjectCode,lessonType,buildingetc.Thesequenceofgenescontinuesuntilallsubjectlessonswithinatimetablecaseareencodedintothechromosome.Adecisionwasmadetoallowchromosomestobeofunequallengthinsteadofa xedlength,allowingformoreopen-endedevolutionandalsoaccommodatingthetimetablingdomain.Inthetimetablingdomain,di erenttimetablesarelikelytohaveadi erentnumberofsubjectlessons,sohavingchromosomesofunequallengthisgenerallyunavoid-able.TheinitialpopulationofchromosomesfortheGAisasetofcandidatesolutionsfedfromtheCBRcasememoryintotheinitialGApopulation.

AfterencodingaCBRcaseintoaGAchromosome,theGA tnessfunc-tionwasevaluated.TheGA tnessismappedbacktoCBRrelevance,ensuringthatrelevanceismaintainedifasolutionchromosomeisacceptedattheCBRretainphase.TheselectionschemeimplementedfortheadaptationGAinCBR-GAALTAistheTournamentSelectionalgorithm[14].TournamentSelectionistheleastcomputationallyexpensiveselectionmethod,andwaschosentoal-leviatesomeofthecomputationalcostlinessoftheCBRadaptationtask.ThereplacementpolicyemployedinCBR-GAALTAisSteadyStatereplacement[14].5ResearchObjectives

ThisworkintroducesaschemeinwhichinformationisgatheredattheCBRrevisephase,andisfedbackintotheCBRreusephase.Theaimofourre-searchistocollectknowledgeattherevisestageoftheCBRcycle,andthenfeedthisknowledgebackintoGAadaptationtoaidin ndinghealthiermu-tationstoapply.TosuccessfullymeshtheCBRcasemappingtochromosomemappingswithintheGA,weneededtodevelopa‘repair’mechanismtomain-taingeneswithinchromosomesremainedintherequiredcaseformat.Wealsoevaluatedetrimentalmutationvaluesandavoidillegalmutationparametersbyplacingboundsonmutablevaluesduringadaptation.Anyotherillegalmutationproblemsaremonitoredthroughthefeedbackrepairprocedure.

5.1FeedbackfromReviseintoReuse

Theobjectiveofthisresearchistoimplementanewlearningmethodthat ltersinformationlearntinrevisebackintoreuse.Inorderforinitiallearningtoarise,rulesareinputtothesystemexplainingillegalvaluesandcircumstanceswithinatimetable.Examplesofthetypesofrulesare:theclasssizemustbelessthantheroomsize;aclassshouldnotstartbefore8amorafter9pm;alessonduration

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

ACase-BasedReasoningApproachtoFormulatingUniversityTimetables81

Fig.2.RevisionFeedback ow.

cannotbeequaltozerohours,etc.Theserevisionrulesareprovidedandinputbysystemusers.

RevisionrulesaremaintainedattherevisionstageoftheCBRcycle,butarefedbackintotheapplicationattheGAadaptationstage,allowingthesystemtolearnwhichmutationsarenotfavourabletouse.Therulesarealsousedtocheckthatcoresubjectsarenotrunningconcurrently,andthatanyrequirementswithinanincompatiblesubjectlistareconsidered,beforeallowingtheexpertstoassessthetimetable.Whenthechromosomerepairmechanismisapplied,systemusersarealertedtoproblemsremainingwithinthechromosomestructure.Atthispoint,itisuptotheusertoevaluateandtrialthesolutionintherealworld.Dependentontheapplicationofthesolution,theuserwillchoosetoretainthesolutionornot.

6ExperimentswithVariedCaseBases

TheCBRsystemwastestedusingthreedi erentcasebases,eachcontaining8cases.ThethreecasebasesarecalledCaseBase1(containinglowrelevancecases),CaseBase2(containingaveragerelevancecases)andCaseBase3(con-taininghighrelevancecases).

Withinthesecasebasedatasets,fourdi erenttypesoftestswereconductedtoevaluatethee ectofmutationson tness.Alltestswereconductedover10runsoftheGAadaptation,withaveragestakenacrosstherunstoyieldresults.Thetestswererunwiththefeedbackmechanism(fromsection5.1)activated(WL)anddeactivated(WOL).Theusercandecidewhethertorunthesystemwithorwithoutlearning.Table2showsallresultsforallexperiments.TheGAparametersremainthesameasinTable1(exceptwhenmutationvaluesarebeingchangedinTest3).Test1testsgeneraladaptationwiththeGA,whileinTest2wevarytheprobabilityofmutation,testinghowwelltheGAreactstovaryingthePm.InTest3,wetestiftherelevanceisbetterwhenmutationsareactuallypresent,whereTest4concentratesonhowrelevantcasesarewhenweretainanadaptedcase.

6.1DiscussionofResults

TheresultsdisplayedinTable2arethegroundsfordiscussionofthelearn-ingfeedbackbuiltintoCBR-GAALTA.Forgeneralproductionof tnesswhilerunningtheGAadaptation,thefeedbackmechanismhasnodirecte ecton

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

82AliciaGrechandJulieMain

Table2.ResultsofGAadaptationusingthreeseparatecasebases.

TestNumberCase-Base1Case-Base2Case-Base3

WOLWLWOLWLWOLWL

Test1-GeneralCBRadaptation27.3526.0030.9031.1533.7033.10Test2-E ectofchangingGAMutationProbability

MutationProbability=0.125.5528.0526.4529.6030.7536.50MutationProbability=0.0127.7526.9031.0030.8029.5532.15MutationProbability=0.00127.1526.5030.5532.1532.7532.15Test3-Relevancebasedonpresenceofmutations

AverageRelevanceWithMutations24.8529.3529.6229.0033.0035.13AverageRelevanceWithoutMutations30.0026.9029.6729.5833.4034.91Test4-Relevancewithretainingadaptedsolutions

AverageRelevanceWithMutations28.2529.3533.8733.0036.5036.00AverageRelevanceWithoutMutations23.0027.8334.0035.0037.2037.20producingchromosomesthatexhibitimproved tness.Howeverwhentestingtheviabilityofchromosomeswithvariedmutationsduringtesttwo,resultsbe-came tterasPmincreased.Wefoundthatwhenthereisahigherchanceofmutationsoccurring,amechanismthatlearnswhichmutationsadverselya ectchromosome tnessisdesirable.Theseresultsareconsistentacrossallcasebaseimplementations.

Testthreeindicateshowwellthelearningmechanismoperateswhenmuta-tionsarepresentintheadaptation.Interestingresultsoccurwhencomparingthethreecasebases.Whenthelearningmechanismisactivated,mutationsgen-erallyproducedhigher tnesssolutions,withtheexceptionofCaseBase2.Thisdemonstratedtousthatalearningmechanismbene tsaverage tness,maintain-ingthatmutationdoesnotadverselya ecttherelevanceofadaptedsolutions.

Testfourrecords tnessbasedonfeedinglearntinformationfromanadaptedsolutionbackintothereuse.Feedingpreviouslyrepairedsolutionsbackintoalearningmechanismallowedthesolutionstocontinuerepairing,improvingoversolutionswherenomutationsoccurred.

7Conclusions

ThispaperhasshownthatifusingaGAforadaptationinaCBRcycle,feed-ingknowledgefromtherevisiontoadaptationstagescanbene tthehealthofsolutions.Tocreatemorenovelsolutionsduringadaptation,wefocusedontheimportanceofmutationsandlearningwhichmutationsarebesttouse.Alearn-ingfeedbackmechanismwasdevelopedtofeedknowledgelearntintherevisestageoftheCBRcycle,intoaCBR-GAadaptationstage.Wefoundthatwhenthereisahigherchanceofmutationsoccurring,usingamechanismthatlearnswhichmutationsadverselya ectchromosome tnessisdesirable.

Abstract. This paper presents a technique to construct generic university timetables using case-based reasoning (CBR) with genetic algorithms (GAs). The case-based reasoning methodology allows a past memory of timetables to be stored and accessed via retri

ACase-BasedReasoningApproachtoFormulatingUniversityTimetables83References

1.Abramson,D.,Abela,J.:Aparallelgeneticalgorithmforsolvingtheschooltimetablingproblem.In:DivisionofInformationTechnology,Melbourne(1992)

2.Burke,E.K.,MacCarthy,B.,S.Petrovic,R.Qu:Case-basedreasoningincoursetimetabling:Anattributegraphapproach.InAha,D.,I.Watson,eds.:ICCBR.Volume2080ofLNAI.,BerlinHeidelberg,Springer-Verlag(2001)90–104

3.Aamodt,A.:Case-basedreasoning:Foundationalissues,methodologicalvariations,andsystemapproaches.In:AICOM.(1994)39–58

4.deSilvaGarza,A.G.,Maher,M.L.:Anevolutionaryapproachtocaseadapta-tion.In:ProceedingsofThirdInternationalConferenceonCase-BasedReasoning.(1999)162–172

5.Louis,S.,Xu,Z.:Geneticalgorithmsforopenshopschedulingandre-scheduling.InCohen,M.,Hudson,D.,eds.:11thInternationalConferenceonComputersandtheirApplications.(1996)

6.Jarmulak,J.,Craw,S.,Rowe,R.:Self-optimisingCBRretrieval.In:Proceedings12thIEEEInternationalConferenceonToolswithArti cialIntelligence.(2000)376–383

7.Jarmulak,J.,Craw,S.,Rowe,R.:GeneticalgorithmstooptimiseCBRretrieval.InBlanzieri,E.,Portinale,L.,eds.:EWCBR.Volume1898ofLNAI.,Springer-VerlagBerlinHeidelberg(2000)136–147

8.Oppacher,F.,Deugo,D.:Integratingcase-basedreasoningwithgeneticalgorithms.InCercone,N.,Gardin,F.,eds.:ComputationalIntelligenceIII,ElsevierSciencePublishers(1991)103–114

9.Pasone,S.,Chung,P.W.,Nassehi,V.:Case-basedreasoningforestuarinemodeldesign.InCraw,S.,Preece,A.,eds.:ECCBR.Volume2416ofLNAI.(2002)590–603

10.Main,J.,Dillon,T.S.,Shiu,S.C.:Atutorialoncasebasedreasoning.SoftCom-

putinginCaseBasedReasoning(1999)1–28

11.Leake,D.B.,ed.:CBRinContext:ThePresentandFuture.In:Case-basedRea-

soning:Experiences,LessonsandFutureDirections.MenloPark:AAAIPressMITPress(1996)1–25

12.Beasley,D.,Bull,D.,Martin,R.:Anoverviewofgeneticalgorithms:Part1,

fundamentals.UniversityComputing(1993)58–69

13.Wah,B.W.,Ieumwananonthachai,A.:Teacher:Ageneticsbasedsystemforlearn-

ingandgeneralizingheuristics.InPal,S.,Dillon,T.,Yeung,D.,eds.:SoftCom-putinginCase-BasedReasoning,Springer-VerlagLondon,UK(2001)179–211

14.Michell,M.:AnIntroductiontoGeneticAlgorithms.MITPress(1996)

本文来源：https://www.bwwdw.com/article/3u44.html