英文原文EvolutionaryprogrammingofCNCmachinesAbstractThepaperproposesanewconceptforprogrammingofCNCmachines.TheconceptbasedongeneticalgorithmsassuresevolutionarygenerationandoptimizationofNCprogramsonthebasisofCADmodelsofmanufacturingenvironment.Thestructure,undergoingsimulatedevolution,isthepopulationofNCprograms.TheNCprogramscontrolthemachinewhichperformssimpleelementarymotions.Duringtheevolutionthemachinemovementbecomesmoreandmorecomplexandintelligentsolutionsemergegraduallyasaresultoftheinteractionbetweenmachinemovementsandmanufacturingenvironment.TheexamplesofevolutionaryprogrammingofCNClatheandCNCmillingmachinetoolfordifferentcomplexitiesoftheblanksandproductsarepresented.Theproposedconceptshowedahighdegreeofuniversality,efficiency,andreliabilityanditcanbealsosimplyadoptedtootherCNCmachines.2005ElsevierB.V.Allrightsreserved.Keywords:Manufacturingsystems；NCprogramming；CNCmachines；Geneticalgorithm.1.IntroductionSincetheCNCmachinesarealreadypresentinalmostallmanufacturingsystems,theautomaticprogrammingofCNCmachinesbecamewidespreadinthelasttwodecades1,4,6,7.Thus,nowadaysnumerouscommercialprogrammingsolutions,includingautomaticgenerationofNCprograms,areavailable.Thesolutionsdifferinreliability,ef-ficiency,flexibilityanduniversality.Sofar,ithasnotbeenpossibletotraceauniversalsolutionfortheprogrammingofNCmachines.Inthispaperweusedthegeneticalgorithms(GA)2basedapproachforprogrammingofCNClatheandmillingmachinetool.TheproposedconceptcanbeadoptedalsotootherCNCmachinesforexamplecoordinatemeasuringmachines5,weldingmachines,laserandplasmacuttingmachines4,robotsandmanipulators.Theconceptimitatesthenaturalevolutionoflivingorganisms,whereinthestrugglefornaturalresourcesthesuccessfulindividualsgraduallybecomemoreandmoredominant,andadaptabletotheenvironmentinwhichtheylive,whereasthelesssuccessfulonesarepresentinthenextgenerationsrarely.IntheproposedconcepttheNCprograms,representedasweightedgraphs,undergoadaptation.Duringthesimulatedevolutionmoreandmoresuccessfulorganisms(theNCprograms)emergeonthebasisofgivendataonmanufacturingenvironment.Researcheshaveshownthattheproposedconceptisuniversal,flexible,reliable,andefficient.Forthepapertobeself-containedthebasictermsonturningandmillingprocessesarestatedinthebeginningoftheSection2.Afterwardstheideaoftheproposedconceptispresented.Thecoding(i.e.,genotype)oftheindividualNCprogram(organism),theevaluationoforganisms,andthegeneticoperationsusedaredescribed.Sections3and4showfunctioningoftheproposedsystem.TheexamplesofprogrammingofCNClatheandCNCmillingmachinetoolfordifferentcombinationsofexactingnessoftheblankandproductaregiven.Section5summarizesthemaincontributionsoftheperformedresearchandalsogivesguidelinesforfurtherresearches.2.ProgrammingofCNClatheandmillingmachinetoolwithGATheobjectiveofturningandmillingprocessistoassurerelativemotionofthetoolwithrespecttotheworkpiece.Theconsequenceoftherelativemotionismovingofthetoolreferencepointand,consequently,formingofthedesiredshapeoftheproduct.Thetoolmovementconsistsoftheworkingandfeedingmotions.Machiningofmaterialtakesplaceinseveralcutswhoseoptimumsequenceisknowningeneralonlyforverysimpleproducts.Eachworkingmotiontakesoffacertainquantityofmaterialandthusitproducesthecuttings.2.1.MainalgorithmThebasicideaoftheproposedconceptwillbedemonstratedonsimpleexamples.Figs.1and2showtheblank,productandtherelevantchipsinturningandmillingprocess,respectively.Theareaofthepossibletool(blade)motionisdiscretizedintosquaresincaseofturningandboxesincaseofmilling.Thetoolofonesquarethicknessinturningcanmovediscretelyup,down,toleftandtoright,whereasitcutsonlytorightordownwards.Incaseofmillingthetoolcanmoveandcutinthepositiveandnegativedirectionsofaxesx,yandz.Duetothediscretizationofthemachiningfieldthetoolreferencepointisinthemiddlebottomofthecuttingtool(Figs.1and2).Thematerialtobetakenoffisdividedintoseveralcutsconsistingofchips.Forexample,thecut-1inthebottomdiagramofFig.1consistsofninechips,thecut-2andthecut-3consistoffourchipseach,thecut-4oftwochips,etc.DiagramsattherightofFig.1showthetypesofmachining.Duetothediscretenatureofthesystemitispossibletoselecthorizontal,verticalorcombinedcuts.Fig.3showsthemainalgorithmforprogrammingoftheCNCmachinetoolinthepseudocode.Firstitisnecessarytoenterthedataontheblankandproduct.Intheproposedconceptenteringiseffectedautomatically,directlyfromtheCADmodulesoftheblankandproduct.Theinputofthedesiredtypeofmachiningfollows.Thenthesystemdividesthemachiningareaintothedesirednumberofsquares(turning)orboxes(milling).Attheendofthedatainputitisnecessarytodefinethestartingandfinalpointofthetoolmotionandthetoolreferencepoint.FromnowonthesystemiscapableofautonomousgeneticallybasedgeneratingandoptimizingtheNCprogramsthroughseveralgenerationst.TheBooleanvariableknownNCprogramdecideswhetherthesolutionfrommachiningpreviouslyperformedshouldbeusedfortheinitialpopulationortheinitialpopulationshouldbeinitializedcompletelyatrandom.Eachchromosome(organism)inthepopulationP(t)representsacollision-freeoranon-collisionfreeNCprogram.Ofcourse,intheinitialgenerationmostoftheprogramsarenoncollision-free.EachNCprogramconsistsoffeedingmotionbetweentheinitialpointandtheinitialcut,feedingandworkingmotionsbetweencutsandfeedingmotionbetweenthefinalcutandfinalpointofthetool.Theevolutionarydevelopmentofsolutionstarts,whenthechromosomeshavebeenevaluated.Greaterprobabilityofparticipatinginthegeneticoperationsofselectionandchangingisassignedtothesolutionsbettersolvingtheproblem.Selectionassuressurvivalofmoresuccessfulmembersofpopulationandtheirprogressinunchangedformintothenextgeneration.Changinginfluencesoneorseveralorganismsandcreatesfromthemtheiroffspring.Afterselectionandchanginganewgenerationisobtainedwhichhastobeevaluated,too.Theprocessisrepeateduntiltheterminationconditionoftheprocesshasbeenful-filled.Thatcanbethegreatestspecifiednumberofgenerationsorsufficientqualityofsolutions.2.2.Initialstructure:codingofNCprogramTherandomlygeneratedcollision-freeandnon-collisionfree(i.e.feasibleandinfeasible)NCprogramscanberepresentedbyaweightedgraph(Fig.4).Theverticesofthegraphsareworkingmotions(cuts),andtheedgesbetweenthepointsarethefeedingmotions.Eachvertexofthegraphisconnectedtoallotherverticesofthegraph.Thepointsandcorrectionsinthegraphareweighted.Thesequenceofgenes(i.e.cuts)representstheblademotionfromcuttocut.Inthegraphthetwopermanentgenes(vertices)aretheinitialandfinalpointoftheblademotion,markedwithSandE,respectively.Theintermediatevertices(e.g.cut-1,cut-4)representthecutssubjectedtomachining.Atfirst,thetoolmoveswiththefeedingmotionfromtheinitialpointSuptothefirstcut,thenitproceedswiththefeedingmotionuptothenextcut,itmachinesitandsoon,untilithasmachinedallcuts.Finally,withthefeedingcutitreachesthefinalpointE.TherandomlygeneratedNCprogramsdifferinthenumberoftherequiredtoolstepsandinthenumberofcollisionsbetweenthetoolandtheworkpiece.Beforeintroducingletusdefinetwoimportantterms:consistencyofcutsandconsistencyofchips.Acutisconsistentifatleastonechipinthecutstickstotheworkpiece.Achipisconsistentifitstillstickstotheworkpiece(i.e.totheconsistentcut).Verifyingofcutsandchipsisveryimportant,sinceduetofastlychangingenvironment(i.e.workpiece)itisnecessarytocheckcontinuouslywhichworkpieceareashavealreadybeenmachinedornot.2.3.EvaluationofpopulationTheaimofthecombinatorytaskistofindsuchapaththroughtheweightedgraphwiththeinitialpointSandfinalpointEthatwillcontainallpointsinthegraphandsothatthesumofweights(attheedgesandvertices)andofweightednumberofcollisionswillbeminimum.Inotherwordsthismeansthatitisnecessarytofindtheoptimumcollision-freeNCprogram.If,forexample,thepaththroughthegraphinFig.4isequaltothelist:S,cut-1,cut-2,cut-3,cut-4,cut-5,cut-6,cut-7andE,thesumoftheweightsatconnectionsandpointsisasfollows:EvalNCx=_wNCx=wS-1+wcut-1+w12+wcut-2+w23+wcut-3+w34+wcut-4+w45+wcut-5+w56+wcut-6+w67+wcut-7+w7-E+fH,(1)whereNCxisthexthNCprogram,wS-1thelengthoffeedingmotionfrominitialpointSuptothefirstcuttingofcut-1,wcut-1thelengthofworkingmotionofconsistentcut-1,wijthelengthoffeedingmotionbetweentheconsistentcut-1,wi-EthelengthofworkingmotionfromthelastcuttingofthelastconsistentcutiuptopointE,ftheimpactfactor,andHthenumberofcollisions.ThemostdemandingoperationoftheevaluationoftheNCprogramisthedeterminationofthetoolpathlength,consistencyofcutsandcuttingsandnumberofcollisions.Duetoch