Genetic algorithms using multi-objectives(9)

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

187

Fig.6.Representationofthecontract-netprotocolinanagent.

Amachinecanacceptmanycontractscorrespond-ingtothesamejob,butnegotiatedbydifferentNAswhichhavedifferentstrategies.Then,thecontractideologyis“thestrongestwins”sinceacontractcanbebrokenbybothpartners[21].However,wecanproposetwotypesofagents:aforwardplacingandabackwardplacingagent.Moreover,therearesomeworkshopconstraintssince,wehavegenericma-chines,groupsofmachinesandspecializedmachines.Wecanconsiderthatwehave“groupofmachines”agentswhichwillproposethedifferentjobsto

themachinestheyrepresent.Atthislevel,wecanoperateaparallelcomputationonthemachinesandso,ontheGanttdiagram(Fig.7).Nevertheless,forthemoment,weconsiderthattheDAJcanonlyprocessonejob.Anintermediateagentinchargeofchoosingthenum-berofjobscanbeproposed.Resultscorrespondingtothisapproacharegiveninthefollowingdiagram(Fig.8)whichgivesthevalueoftheeconomicfunc-tion(minimizationofthetardinessandtheadvance)accordingtothenumberofagentsandthenumberofgeneticoperationsusedbyagents.

9.GoingdeeplyintotherelationshipsofGAandMAS

TheuseofGAinMASisthebeginningofwhatcanbeaninterestingresearcharea.Thereareclearlytwokindsofapproaches,the rstiscentralized,inotherwords,someofthegeneticisoutsidetheagent.Thefunctionofselectionisagoodexampleofsuchfeatureout-of-the-agent[18,55].

However,webelievethatifonewantstocompletelymergetheGAandMAS(Fig.9),wemustmaketheagentacompletelyautonomousgeneticentity.Bythis,wemeanthatnotonlythegeneticpatrimonymustbe“onboard”butalsothefunctionsofselectionandcrossing.Anagentmustchoosewhichotheragentitwantstoreproducewith[55].Thelocationofthefunctionofmutationisnotclearlyknownsinceitis

Fig.7.Contract-netstructurebetweenthedifferentlevelrepresen-tations.