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–190181

accordingtotheirobjectives.Thisobjectivehasbeenchosentoobtainsolutionsveryrapidlybecausecal-culationsareverynumerouswithgeneticalgorithms.Alsobecauseitissuf cienttocomparethesealgo-rithmswithothermethodssuchasthegradient,thesimulatedannealing,etc.Geneticalgorithmsenableustoobtainagoodqualitysolutionquicklyandeasilycomparedtootherresearchtechniques[20,26].2.Theselectionfunction

Wecannotusetheclassicselectionfunctionlikeamethodoftheroulettewheel,foritisproportional.Indeed,wewouldtakeanagentasaspeci centitybutwithouttakingintoaccountsomeexteriorpres-suresontheagent:itsenvironmentandthesystem’semergencephenomena.Therefore,theselectionfunc-tionshouldnotonlyconsidertheactionsoftheagent,whethertheseactionsaregoodorbad,butalsothecommunicationsbetweenagents.Wetalkaboutsenses(semanticorlink).Bysenses,wemean:

thesenseofcommunicationwiththeotheragents(networklinks);

thesemanticsofthecommunicationbetweentwoindividuals.

Therefore,ourcrossoverprocesshastotakeintoaccountthesemanticsofcommunication.Butanagent,seenasastructureisacompoundentitymadeofthefollowingelements:functionsofcommunica-tion,functionsofaction,functionsofbehavioralongwithalocalgeneticpatrimony.JustasevolutionaryalgorithmssimulateaDarwinianprocess,MAScansimulatetheevolutionofanucleusoragroupandbyextensionofanorganization.Asocialorganizationmaynotdiversifyandevolvebycloning:inallsocialorganizations(humanoranimal),wehaveacrossoverprocessthattendstopreservethenaturalinheritancebutalsotomakeitmorepowerful.Therefore,ourmulti-agentsystem,byintegratingthisnewconceptofreproductionwithcrossing,willhavetotakeintoaccounttheseparameters.Toachievethis,wecanuseageneticalgorithmswitchboard,asde nedbyHolland[26]oranevolutionarystrategyasde nedbyBäck[2].Bydoingthat,eachagent(individual)willbecharacterizedbyachainofbitswhoselengthwillcorrespondtoamultipleofthenumberofparam-eters.Thischainwillcorrespondtoachromosome

[54]thatwillrepresentthestructureoftheagent.Eachcharacter(action,behaviorandcommunication)composingtheagentwillcorrespondtonumericaldatareferringtorulesdatabase.Atoanaddressdatabase.Sincei,BknowledgejandCkwillreferisan“in nitedimension”,duetothefactthatanagentonlyhaslimitedknowledgeofitsenvironment,theformeronlyhas,apriori, niteknowledge.By niteknowledge,wesupposethatithasa nishednumberofactionsorknowledgeavailable.Especially,atthelevelofrulesofaction,ifonetakesthesetofplace-mentrulesdescribedbyPécuchetetal.[41],wehaveatmostnrules,thereforebyusingassignmenttech-niquescommonlyusedinelectronicandespeciallyintheassignmentmemory,wecanreserveacertainnumberofaddressescorrespondingtorules.There-fore,forabinaryrulecoding,wecanuseacodingon10bits;inthisway,itisalwayspossibletoincreasetheknowledgetothelevelofourdatabase.Neverthe-less,thesizeofourchromosomeisimportantinordertoreducethememoryspace.WeusethecodingofGray.Thus,wecanusegeneticalgorithmsonMAS.3.Themutationfunction

Themutationwillcorrespondtothechangeofabit,thus,wecanuseswitchboardoperators[17,22].Ourconstraintatthemutationlevel,consistsinhav-ingacorrespondencebetweenthebitsstringandthedatabase.Thus,bychangingthevalueofonebit,wecanintroduceanewcharacter.Thiswillhavearepercussionontheenvironment,butespeciallyonitsmembershiptoagroup.Thecommunicationsithasbeenabletohavewithotherelementsofthegroupwill,incontestably,bechanged.Forexample,considerthatthemutationintroducesacertainag-gressivenessattheagentlevel,thencommunicationswiththegrouparegoingtochangeandthegroupconsequently,willprobablylosesomeofitssocialcohesion.Thereforeinordertoavoidthetooabruptupsetofthesocialbalancethatcanexistbetweenin-dividualscomposingagroupandtheorganizationit-self,themutationinterventionsbygeneticalgorithmswillneedtobeweak.Nevertheless,wecanconsiderthatatthebeginningofthesimulationoftheorgani-zation,asatthebeginningofacivilization,progresswasrapidenough.Therefore,atthebeginning,wecanintroduceanimportantnumberofmutations.We