Genetic algorithms using multi-objectives(4)

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

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

willuseasdistributionforthenumberofmutationbygeneration,acurveofparameters(α,β)

f:x→β

withβ∈R+andα∈R+ .

(1)Thus,byusingthistypeofdistribution,weintroducealotofmutationsatthebeginningofthesimulationandfewattheendinordertoavoiddisruptingtheprocessofevolutionbydeeplymodifyingcharacteristicsofchromosomes,andthereforeofindividuals.Toomanymutationsinthesystemswouldinexorablysowtheseedsofchaos.Wehavepreviouslyseenapossibledistribution.Nevertheless,byusingaGaussiandistri-butiontodeterminetheprobabilityofmutation,wekeeptheswitchboardofthegeneticalgorithm[39].4.Thecrossoveroperator

Fromanhistoricalpointofview,geneticalgorithms[27]correspondtoarandomphenomenon,butthemaindifferencecomparedtoaclassicrandommethodisthathere,weconverge,stepbysteptoanoptimum(localorglobal)inthespaceofsolutions[3].Thus,wearenotsubjecttochanceasweareintheformer,totallyrandommethod.A rstcrossingapproachwouldbetoconsideranagentasa“piechart”whereeachslicecorrespondstoacharacter.Byrandomlychoosingtwocutpointsinouragentcomparedtoareferential,wewouldexchangetwopartstoformnewindividuals.However,aproblemarises,astohowdowesetourreferential?Wecannotsetapermanentreferential,be-causeinthiscase,itsupposestoconsideranadjustableindividual.So,anagentisanentitythathasnofacets.Anagentiscomparabletoanindividualpartofanor-ganization.Nevertheless,itisnotpossibletodescribeitasaphysicalindividual(aman).Thereforethis rstapproachisinterestingbutdoesnotgivesatisfaction.Knowingthatnotallagentshavethesamegeneticpatrimony,thatistosaythattheyhavenoequalchro-mosomelengths,andknowingthatanagenthasnofacets,wecanrepresentitasatoroïdalchainofbits: Thisrepresentationdoesnotsupposetheinterven-tionofthenotionoffacetsofanagent.

Wecancrossindividualsofdifferentlengths[20].Itisalwaysnecessarytode neastartingpointforourchromosomeinordertocorrectlyexchangephe-notypes.Whichonedowechoose?Inoursystem,anagentiscomposedoffunctionsofaction,knowledge

andbehavior,thatmakeacertainnumberofpossi-blereferentials.Therefore,thechoiceofareferentialwouldbeaproblem,exceptbyrandomlychoosingit.Amongpossiblefunctions,whatdistributionwemustuse?Intheory,nodistributionisideal,nevertheless,tocontinuewiththiscirclescheme,wewilluseacir-cledistributionorGaussianmethodaccordingtotheprobability.Thus,itispossibletosetareferentialforthecrossing.However,theuseofasimplecrossingdoesnotalwaysgivegoodresults.Consequently,theuseofmultiplecrossingsallowsustomakeabiggermix.Wewillusetheuniformcrossovertoalwayshaveviableindividualsforourrepresentation.However,itisalwayspossibletousethecrossoversde nedbyGoldberg[20]suchastheCX,OXandthePMX[38],thatalwaysgiveviableindividuals.5.The tnessfunction

Inourcase,itisnecessaryforustooptimizeaGanttdiagram[43].Therefore,thelastoperationtoundertakewillhavetocorrespondtotheduedatemi-nuscompletiontime.Itisnecessary,thereforetomin-imizethedelayandtheadvanceofthesetofjobs.Theobjectivewithanadvanceandanulldelayisnearlyimpossible.Inageneralmanner,weallowacertaindelayoradvance.Whenwecalculatethe tnessofanagent,wedetermineitsimpactontheGantt[46].Ofcourseforthesetofjobs,wecanhaveadelayoraweakadvance.Consequently,wenolongerhaveasin-gle tnessfunctionbutmany.Wehaveasmanyobjec-tivesaswehavejobs.Consequently,wehaveacaseof“multi-objectivegeneticalgorithms”[44,45].Forthistypeofproblem,wewillusethebasicconceptsofthemulti-objectiveoptimizationproblem(MOP)[42].5.1.Basicconceptsandde nitions

Thefundamentaldifferencebetweenanoptimiza-tionhavingsimpleormultipleobjectivesisintheideaofthede nitionofanoptimalsolution.Theideaofoptimalityinthemulti-objectivecaseisanaturalex-tensionofwhatwehaveduringanoptimizationforauniqueobjective.

AnMOPcanbede nedasfollows:MOP:minx∈X

f(x),

wheref(x)=(f1(x),...,fn(x))(2)