(cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 165 — #1 (cid:2) (cid:2) PesquisaOperacional(2014)34(2):165-187 ©2014BrazilianOperationsResearchSociety PrintedversionISSN0101-7438/OnlineversionISSN1678-5142 www.scielo.br/pope doi:10.1590/0101-7438.2014.034.02.0165 AGENETICALGORITHMFORTHEONE-DIMENSIONAL CUTTINGSTOCKPROBLEMWITHSETUPS SilvioAlexandrede Araujo1*,KellyCristina Poldi2 and Jim Smith3 ReceivedAugust1,2013/AcceptedOctober29,2013 ABSTRACT.Thispaperinvestigatestheone-dimensionalcuttingstockproblemconsideringtwoconflict- ing objectivefunctions: minimization ofboththenumberof objectsandthenumberof different cutting patternsused.Anewheuristicmethodbasedontheconceptsofgeneticalgorithmsisproposedtosolvethe problem.Thisheuristicisempiricallyanalyzedbysolvingrandomlygeneratedinstancesandalsopracti- calinstancesfromachemical-fibercompany.Thecomputationalresultsshowthatthemethodisefficient andobtainspositiveresultswhencomparedtoothermethodsfromtheliterature. Keywords:integeroptimization,cuttingstockproblemwithsetups,geneticalgorithm. 1 INTRODUCTION Thecuttingstockproblemhasbeenintensivelyresearched duetoitshighimportanceinseveral industrialprocesses (see, for instance Dyckhoffet al., 1997; Wang & Wa¨scher, 2002; Poldi& Arenales,2006,2010;Oliveira&Wa¨scher,2007;Morabitoetal.,2009).Itconsistsoffindingan optimizedwayofcuttingobjectsofknowndimensionintosmalleritemsinordertomeetagiven demand. In general, the objective to be optimized is related to the minimization of the waste of material. However, accordingtoFoerster & Wa¨scher (2000),insome real-wordproblems it is not appropriate to consider the minimization of the waste of material as a single objective, becauseitisonlypartofthetotalrelevantcostsinthecuttingprocess. In many industries, such as, wood, glass, paper, fiber and steel industries, the profitabilityof thecuttingprocess canbe affected bythenumberoftimesone hastoswitchbetween different cuttingpatternsinordertosatisfythedemand. Forinstance,thepositionsofthecuttingknives in themachine may need tobe adjustedfor each changeover. Such adjustments ofteninterrupt *Correspondingauthor 1Universidade Estadual Paulista-UNESP, Departamento de Matema´tica Aplicada-DMAp, Rua Cristo´va˜o Colombo, 2265,15054-000Sa˜oJose´doRioPreto,SP,Brazil. E-mail:[email protected] 2UniversidadeFederaldeSa˜oPaulo-UNIFESP,InstitutodeCieˆnciaeTecnologia-ICT,RuaTalim,330,12231-280Sa˜o Jose´dosCampos,SP,Brazil. E-mail:[email protected] 3UniversityoftheWest ofEngland,FacultyofEnvironmentandTechnology,BS161QYBristol, UnitedKingdom. E-mail:[email protected] (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 166 — #2 (cid:2) (cid:2) 166 AGENETICALGORITHMFORTHEONE-DIMENSIONALCUTTINGSTOCKPROBLEMWITHSETUPS productionandmayimposeasetupcosteverytimeadifferentpatterniscut. Inthesesituations, in order to reduce costs, it is desirable to have a cutting plan made of fewer different cutting patterns. So, in additionto the minimizationof the waste of material, the minimizationof the numberofdifferentcuttingpatternsisoftenconsideredasasecondcriterion. Yanasse & Limeira (2006) highlighted the importance of bi-criteria decision problems when setupcosts are significantwhencompared tomaterial costs.However, sincethisbi-criteriaob- jective function is typically nonlinear and discontinuous it makes the problem more difficult to solve. In this paper, to address the one-dimensional cutting stock problem with conflicting objectivesasamulti-objectiveproblem,weproposeaGeneticAlgorithm(GA)toobtainasetof non-dominatedsolutionssothatthedecisionmakercantakeabetterdecision. In the next section we present the mathematical model, and in Section 3 we review previous research. In Section 4 the proposed multi-objective genetic algorithmis detailed. The compu- tationalresults are presented in Section 5 and inSection 6 we conclude the paper and present possiblefutureresearch. 2 MATHEMATICALMODELING We considertheone-dimensionalcuttingstockproblemofcuttingobjectsofknowndimension into smaller items. This is common in many industries where objects, such as pipes, rolls of materials,etc,isproducedinfixedlengthsbysomemachinery,butmaybesoldtocustomersin quantitiesofsmallerlengths. Thisrequiresthatthestockobjectsbecut,whichistypicallydone by a cutting machine with blades that may be set in different positions. Each combination of blade positionsonthecuttingmachine is knownas a cuttingpattern.The taskthen consistsof selecting and applyingone or more cuttingpatternsto objectsto produce a number ofsmaller sizeditemsinordertomeetagivendemand. Clearlytherearemanywaysofaccomplishingthis, and doing so efficiently requires the optimizationof two conflicting objective functions: min- imizationof boththenumber of objectscut (which effectivelyminimizes the amount ofwaste – known as “trim loss”) and of different cutting patterns used (which reduces the amount of production time spent while cutting machines are reset). According to the typologyproposed by Wa¨scher et al. (2007)the problemstudiedinthispaper is an extensionof the One Dimen- sionalSingleStockSizeCuttingStockProblem(1D-SSSCSPwithsetups),whichrequiresthata weaklyheterogeneousassortmentofsmallitemsbecompletelyallocatedtoaselectionoflarge identicalobjectsoffixed dimension. This problemcan beformulatedas an integerlinearopti- mizationproblemasfollows. Considertheparameters: • m: numberoftypesofitems(e.g. numberofdifferentsizesofferedforsale); • n:numberoffeasiblecuttingpatterns; • l : lengthofitemtypei,i =1,...,m; i • b :demandforitemtypei,i =1,...,m; i • L:lengthofobject; PesquisaOperacional, Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 167 — #3 (cid:2) (cid:2) 167 SILVIOALEXANDREDEARAUJO,KELLYCRISTINAPOLDI and JIMSMITH • a = (a ,a ,...,a )T: vectorcorrespondingtothe jthcuttingpattern, j = 1,...,n, j 1j 2j mj where a is the number of items of type i (i = 1,...,m) in the jth cutting pattern. ij (cid:2) Moreover, a vector a is a feasible cutting pattern if and only if m l α ≤ L, with j i=1 i ij α ≥0andinteger. ij Let x be the number of objects to be cut according to the jthcutting pattern, j = 1,...,n, j thebi-criteriamathematicalmodelcanbestatedas: minimize: (f (x), f (x)) (1) 1 2 (cid:3)n subjectto: α x ≥b , i =1,..., m (2) ij j i j=1 x ∈ N, j =1,...,n. (3) j The setofconstraintsrepresented byEq.(2)ensuresthatthetotalamountofitemsproducedat leastmeetsthedemand,i.e.,theinequalityallowsoverproduction. ThesetofconstraintsEq.(3) ensuresthatthenumberofobjectstobecutisnon-negativeandinteger. Theobjectivefunction inEq.(1)minimizesbothobjectives f (x)and f (x). 1 2 Yanasse & Limeira (2006)consider both the minimizationof the number of objects to be cut, (cid:2) givenby f (x) = n x andtheminimizationofthenumberofdifferentcuttingpatterns: 1 j=1 j (cid:4) (cid:3)n 1, ifx >0, j =1,...,n f (x) = δ(x ), where δ(x )= j (4) 2 j j 0, otherwise. j=1 Umetani et al. (2003), Lee (2007) and Golfeto et al. (2009b) consider f (x) as Eq. (4), and 2 f (x)astheratio(percentage)ofthetotaltrimlosstothetotallengthofthedemandeditems: 1 (cid:5) (cid:6) (cid:2) (cid:2) 100 L n x − m l b j=1 j i=1 i i f (x) = (cid:2) . (5) 1 m l b i=1 i i Inthefirstpartofthecomputationalresultspresentedinthispaperwe considerthemathemati- calmodelEqs.(1)-(3)withtheobjective f (x)asinEq.(5)and f (x)asinEq.(4).Inthesecond 1 2 partweconsider f (x)asinYanasse&Limeira(2006)and f (x)asinEq.(4). 1 2 3 PREVIOUSRESEARCH There are some papers in the literature that consider the minimization or the reduction of the numberofsetups.Inthissectionwepresentsomeofthesepapersandhighlightwithboldletters, thesolutionmethodsthatwillbeusedincomparisonsmadeonSection5. Haessler (1975)proposeda patterngeneratingheuristicthatsequentiallyadds newcuttingpat- ternstothecurrentsolutionuntilalldemandismet. Ineachstep,theprocedureselectsacutting pattern, whose trimloss is small and frequency (number oftimes this cuttingpatternis cut) is PesquisaOperacional,Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 168 — #4 (cid:2) (cid:2) 168 AGENETICALGORITHMFORTHEONE-DIMENSIONALCUTTINGSTOCKPROBLEMWITHSETUPS high. Farley & Richardson (1984)modeled a pattern minimizationcutting stock problem as a fixed charge problem, andused the simplex methodto replace basic variables (the cuttingpat- terns)bysurplusvariablestoreducethenumberofpatterns.Anapproachsimilartotheapproach proposedinHaessler(1975)wasconsideredinHaessler&Sweeney(1991). Diegel etal. (1993)presented aprocedure toidentifya pairofpatternsinacuttingplanwhich can be replaced by a single cutting pattern. Foerster & Wa¨scher (2000) proposed the solution method KOMBI, whichgeneralizes thisprocedure based on theobservationthatwhencutting patterns are to be combined, totalfrequency of the new cuttingpatterns has tobe equal to the totalfrequencyoftheinitialonesinordertokeepthematerialinputconstant. Vanderbeck (2000) proposed an exact method for the pattern minimization problem which is formulated as a quadratic integer programming problem. Kolen & Spieksma (2000)presented a branch-and-boundalgorithmthatproduces the Pareto optimalsolutionsfora set ofsmall in- stancesoftheproblem. Umetani et al. (2003) proposed a formulation and an Iterated Local Search (ILS03) for min- imizing the number of stock objects while using at most a predetermined number of different cuttingpatterns. The localsearch algorithmuses the neighborhoodobtainedby perturbingone cuttingpattern in the current set of patterns, where the perturbationsare done by utilizingthe dualsolutionoftheauxiliaryLinearProgramming(LP)problem.Umetanietal.(2006)extended thepreviouspaperandproposedalocalsearchalgorithm(ILS06)thatalternatelyusestwotypes oflocalsearchprocesseswiththe1-addneighborhoodandtheshiftneighborhood,respectively. Toimprovetheperformanceofthelocalsearch,theauthorshaveincorporatedLPtechniquesto reduce thenumber of solutionsin each neighborhood.Asensitivityanalysis techniqueand the dual simplexmethod have been introducedto solvea large number ofassociated LP problems quickly.Throughcomputationalexperiments,theauthorsclaimthattheirnewalgorithmobtains solutionsofbetterqualitythanthoseobtainedbyotherexistingapproaches. Yanasse & Limeira (2006) suggested a HybridHeuristic (HH) to obtaina reduced number of differentpatternsincuttingstockproblems. Initially,theygeneratecuttingpatternswithlimited waste thatfulfillthedemands of atleast twoitemswhen thepatternsare repeated, butwithout overproducinganyoftheitems. Theproblemisreducedandaresidualproblemissolved. Then, patternreductiontechniques(localsearch)areappliedstartingwiththegeneratedsolution. Lee (2007)proposeda localsearch heuristic, called Crawla, whichis based onInteger Linear Programming(ILP).Theheuristicholisticallyintegratesthemasterandsubproblemoftheusual pricedrivenpattern-generationparadigm,resultinginaunifiedmodelthatgeneratesnewcutting patterns in situ. The method spends some time to generate new columns, but guarantees that new columns give an integer LP improvement (rather than the continuous LP improvement soughtbytheusualpricedrivencolumngeneration). Moretti& Salles Neto(2008)solved anonlinearcuttingstockproblemthatconsiders themin- imization of, both, the number of objects and setup. They used a linearization of the problem andacolumngenerationprocedure. ThemasterissolvedbyanAugmentedLagrangianmethod. Aheuristicisappliedtoobtainanintegersolution. PesquisaOperacional, Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 169 — #5 (cid:2) (cid:2) 169 SILVIOALEXANDREDEARAUJO,KELLYCRISTINAPOLDI and JIMSMITH Alves & Valerio de Carvalho(2008)proposeda branch-and-price-and-cutalgorithmtoexactly solve the pattern minimization problem. Alves et al. (2009) solved this problem with column generation and described different strategies to strengthen the formulation considered in their paper. Highqualitylowerboundswere derived fromthenew integer programmingmodel, and alsofromaconstraintprogrammingmodel. Golfetoetal.(2009a)presenteda symbioticapproach thatco-evolves a populationofpotential cutting patterns alongside a population of plans using those patterns. However they combine the multipleobjectivesintoa scalar functionviaa weightedsumapproach. They presented the methods Symbio1, Symbio5 and Symbio10, where the weight for minimizationof the waste is always 1 and the weights for setup minimizationis respectively, 1, 5 and 10. As they have subsequentlyshown(Golfetoetal., 2009b)thatthe Pareto frontis non-convex, a “true” multi- objective approach that maintains an approximation to the Pareto front can potentially find a more diverse setofsolutions. InGolfetoetal. (2009b),theyextended thepreviousmethodby considering a multi-objectiveapproach that uses a niche strategy to evaluate the solutionsand gives a set of non-dominatedsolutions,which are notevaluated by a common scalar function. ThissolutionmethodiscalledSymbio. Cerqueira&Yanasse(2009)introducedaheuristicapproachthatproducesasolutiontotheone- dimensionalcuttingstock problemwitha reduced number ofdifferentpatternsinthesolution. The method proposed begin separating the items in two disjointed groups, according to their demands. Patterns are generated with items of these groups and those with limited waste are accepted. Aresidualproblemissolvedwithitemswhosedemandsarenotsatisfiedand,withthe solutionobtained,theyapplyapatternreducingprocedureoftheliterature. Cui&Liu(2011)presenteda sequentialheuristicprocedure, where a setofitemsare cutfrom objectsofthesamelengthtominimizetheobjectcost,withasecondaryobjectivebeingtoreduce the pattern count of the cutting plan. The procedure generates the current pattern to produce some items, and continues until all items are fulfilled. The algorithm uses a set of candidate items for generating the current pattern and another set of candidate patterns from which the currentpatternisselected. Itgeneratescandidatepatternsusingthecandidateitems,determines theestimatedcutting-plancostofeachpatternusingalook-aheadstrategy,andselectsthepattern of the minimum cost as the current pattern. Based on computationalresults, the authorsargue thatthealgorithmisefficient. Mobasher & Ekici (2013) considered the cutting stock problem with setup cost, developed a mixedintegerlinearprogramandanalyze aspecialcase oftheproblem.Motivatedbythisspe- cial case, they propose two local search algorithms and a column generation based heuristic algorithm.Computationalresultsarepresentedusinginstancesfromtheliterature. Henn & Wa¨scher (2013) presented a recent review on cutting stock problem with setup and pointedoutinterestingdirectionforfutureresearch. For mostofthecases, heuristic(ratherthanoptimal)methodswere proposed,since ithasbeen shown that pattern minimization in cutting stock problem is NP-hard (McDiarmid, 1999; Yanasse & Limeira, 2006). Most of these papers solve the pattern minimization problem in a PesquisaOperacional,Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 170 — #6 (cid:2) (cid:2) 170 AGENETICALGORITHMFORTHEONE-DIMENSIONALCUTTINGSTOCKPROBLEMWITHSETUPS singleor intwostages (Alves et al., 2009). Inthe former, one triestofind a cuttingplan with the best balance between waste and the number of different patterns. In the latter, the pattern minimizationproblemissolvedbyassumingthatnomorethanagivennumberofobjectscanbe used. Usually,thisnumberisobtainedbysolvingastandardcuttingstockproblem. Infact, onlytwopapersintheliteraturetakethemulti-objectiveapproach. The approachtaken by Kolen& Spieksma (2000)solves only small instances of the problem. The multi-objective approach described in Golfeto et al. (2009b) is potentiallymore robust; however the authors report thata drawback of theirmethod is the computationaltime, commenting thatittookbe- tween 60and 80minutestoruneach instance oftheproblem.We hypothesizethatalarge part of thiscomes from the complex representation of plans, which contains not justthe choice of patterns but also the frequency in which they are used. This creates a far larger search space, andmeansthat(i)largerpopulationsarerequiredtoadequatelysamplethesearchspace, (ii)us- agepatternsmustbeevolved(acomplexnonlinearmapping),ratherthancalculatedviasimpler heuristics,and(iii)alargepartofthesearchspace isinfeasible,andthecrossoverandmutation operatorstheyusearenotspecializedtoavoidsuchregions. Eachofthesefactorsincursitsown computationalburden. We hypothesize that the use of a simpler representationcombined with heuristicstodetermineusagepatternscanavoidmuchofthiscomputationaloverhead. 4 SOLUTIONMETHOD Whenanoptimizationprobleminvolvesmorethanoneobjectivefunction,thetaskoffindingone ormoresolutionsisknownasmulti-objectiveoptimization(Ehrgott,2005;Steuer,1985). Although single-objective optimization problems may have a unique optimal solution, multi- objective optimizationproblems typicallypresent a possibly uncountableset of solutionsthat, whenevaluated,producevectorswhosecomponentsrepresenttrade-offs(conflictingscenarios) inobjectivespace. Adecision maker thenchooses an acceptable solution(orsolutions)byse- lectingoneormoreofthesevectors(VanVeldhuizen&Lamont,2000). 4.1 Multi-objectiveOptimization Consider, withoutlossof generality, theminimizationof q components, f , k = 1,...,q of a k vectorfunctionfofadecisionvariablevectorxinauniverseS,where f(x)=(f (x), f (x),..., f (x)). 1 2 q Then, a decisionsolutionvectorx ∈ Sissaidtodominatey ∈ Sifandonlyiff(x)≤f(y) and f(x) (cid:5)= f(y) (i.e., f (x) = f (y) for all k and f (x) < f (y) for at least one k); thisis called k k k k Pareto dominance.A solutionvector issaid tobe non-dominatedifitisnotdominatedbyany otherfeasiblevector. Adecisionvectorx∈ SissaidtobeParetooptimalifandonlyifthereis noy∈ Sforwhichf(y)dominatesf(x)accordingtothedefinitionabove. The Paretooptimalset isthesetofallnon-dominatedsolutionvectors. Thesurface formedby thecorrespondingpointsinobjectivefunctionspaceiscalledtheParetofront. PesquisaOperacional, Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 171 — #7 (cid:2) (cid:2) 171 SILVIOALEXANDREDEARAUJO,KELLYCRISTINAPOLDI and JIMSMITH Figure1illustratestheseideasforatwo-objectivecase. SolutionCdominatesEandFbecause theirobjectivevaluesforboth f and f aregreater thanthoseforC.Meanwhile,theobjective 1 2 values for A and B are smaller than those for solution C, and so both A and B dominate C. HoweverneitherGnorDdominate,oraredominatedby,C. Figure1–Paretodominance. In the presence of multiple Pareto optimal solutions, it is not possible to prefer one solution over the other. In the absence of other information all Pareto optimal solutions are equally important, and in a typicalreal worldsituationthe decision making process may take account of many factors which are time-dependent, subjective, or otherwise hard to quantify. Hence, heuristicsformulti-objectiveoptimizationhave twogoals: 1)tofindaset ofsolutionsasclose as possibletothe Paretofrontand 2)tofindas diverse a setofsolutionsas possible.Taken to- gether thisusuallymeans thatheuristicstrytoproducean approximationtothePareto frontin whichsolutionsaresparselyspaced. AccordingtoFonseca&Fleming(1995),conventionaloptimizationtechniques,suchasgradient- basedandsimplex-basedmethodsaredifficulttoextendtothetruemulti-objectivecase,because they were not designed with multiple solutions in mind. In contrast to this, it has long been recognized that the population-based algorithms are potentially well-suited to multi-objective optimization. Over the last two decades, Evolutionary Algorithm (EA) techniques have received much at- tentionas optimizationtechniques (Michalewicz, 1994; Hertz & Kobler, 2000; Beasley, 2002; Fogel, 2005; Eiben & Smith, 2010). EAs are stochastic optimization methods inspired by Darwin’s theory of natural selection that iteratively refine a (usually fixed size) “population”, whichisa multisetofrepresentationsofcandidate solutionsofthesearch space. Startingfrom a randomly-generated initialpopulation, individualsare probabilisticallyselected according to theirfitness(quality)toactas “parents”, from whichnew “offspring”(candidate solutions)are generatedusingsimplifiedabstractionsofgeneticrecombinationandmutation.Theoffspringin turn have their fitness evaluated and the cycle completes by selecting a next generation from the unionof the current generation and the offspring, typically takingintoaccount age and/or quality. PesquisaOperacional,Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 172 — #8 (cid:2) (cid:2) 172 AGENETICALGORITHMFORTHEONE-DIMENSIONALCUTTINGSTOCKPROBLEMWITHSETUPS ThusanEvolutionaryAlgorithm’sevolvingpopulationcansearchformultiplesolutionsinparal- lel,potentiallyexploitingsimilaritiesavailableinthefamilyofpossiblesolutionstotheproblem. So,themoststrikingdifferencetoclassicaloptimizationalgorithmsisthatEAsusesapopulation ofsolutionsineachiterationinsteadofasinglesolution.Ifanoptimizationproblemhasasingle optimum,thenviageneticdrift,allEApopulationmemberswillconvergeto(anapproximation of) that optimalsolution.However, if an optimizationproblemhas multipleoptimalsolutions, anEAcanbeusedtoapproximatemultipleoptimalsolutionsinitsfinalpopulation;thisability to find multiplesolutionsmakes EAs uniquein solvingmulti-objectiveoptimizationproblems (Deb,2011). TheVectorEvaluatedGeneticAlgorithm(VEGA)sub-dividethepopulation,usingdifferentob- jectivestoawardfitnesstodifferentsub-populations(Schaffer,1985).Goldberg(1989)suggested usingtheconcept ofdomination,whichwasadoptedand refined bymany differentimplemen- tationsofMulti-objectiveOptimizationEvolutionaryAlgorithms(MOEAs), suchas theMulti- objectiveGeneticAlgorithm(MOGA)(Fonseca &Fleming,1993),theNon-dominatedSorting Genetic Algorithm(NSGA)(Srinivas& Deb, 1994)and the Niched Pareto Genetic Algorithm (NPGA)(Hornetal.,1994).TheliteratureonMOEAisnowextensiveandgoodsurveyscanbe foundinChinchuluun&Pardalos(2007),Coello(2000),Ehrgott&Gandibleux(2000),Gonget al. (2009)andZhouetal.(2011). 4.2 AMulti-objectiveGeneticAlgorithmforthe1D-SSSCSPwithSetups InthisstudyweproposeaGeneticAlgorithm(GA)tosolvethebi-criteriaproblemwhichmin- imizes both the waste of material and the number of different cutting patterns. The algorithm was adapted fromAraujoetal. (2011)inordertodealwiththetwoconflictingobjectivefunc- tions.Moreover,thatpaperconsideredminimizingthewasteofmaterialfortheOneDimensional MultipleStockSizeCuttingStockProblem(1D-MSSCSP)(Wa¨scheretal.,2007)underthecon- ditionthatproductionexactlymetdemand. Inthispaperwesignificantlyextendtheheuristicto tackleamulti-objectiveversionoftheOneDimensionalSingleStockSizeCuttingStockProb- lem(1D-SSSCSP)andwealsoallowinequalities–thatistosayweallowforoverproductionof items,withtheexcess quantitiestreatedaswaste. Wefirstdiscussthewaythatfitnessisassignedtoacandidatesolutioninthecontextofthecur- rentpopulation,thentheselectionprocessesviawhichindividualsareselectedforreproduction and survival.Next, we discuss the representationand the recombinationoperator thatworkon thatrepresentationtocreate new offspring,andfinallytheprocessviawhichtherepresentation ofasolutionistransformedintoacandidatesolution. Rank-based fitness assignment function: Fonseca & Fleming (1993) provide this non- dominatedclassification ofa GA population.Consideran individualwhichisdominatedbyη i individuals in the current population. It is given a rank τ = 1 + η , so all non-dominated i i solutionsare givenrank 1, and the rest are rankedaccording to how many solutionsdominate them. Notethatthisisbiasedinfavorofsolutionsinsparselypopulatedregions. PesquisaOperacional, Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 173 — #9 (cid:2) (cid:2) 173 SILVIOALEXANDREDEARAUJO,KELLYCRISTINAPOLDI and JIMSMITH The ideaofusingtherankingratherthanrawfitnessvaluestodetermineselectionprobabilities has been shown to combat premature convergence. In this case a simple linear ranking tech- niqueisusedtoassigneffectivefitness.Ifμ(τ )denotesthenumberofsolutionswithrankτ in i i populationoftotalsize P,thenthefitnessofanyindividualisgivenby: τ(cid:3)i−1 F = P − μ(k)−0,5(μ(τ )−1) i =1,...,P. (6) i i k=1 Equation(6)associates thesame fitnessforevery solutionofthesame rank.Topromotediver- sityamongthenon-dominatedsolutions,thisfitnessisthenmoderated topreferentiallyreward solutions that are dissimilar to others of the same rank. Let σ be a parameter that defines share how far apart two individualsmust be in order for them to decrease each other’s fitness. The regionwithinradiusσ ofasolutioniscalleditsniche. Foreachsolutioni and j ofthesame share rank,calculatethesharingfunctionvaluewhichisgivenby: ⎧ (cid:10) (cid:11) ⎨ β 1− dij , ifd ≤σ Sh(dij)=⎩ σshare ij share (7) 0, otherwise whereβ isaparameter, typicallyβ ∈ [1,2],andd isthedistancebetweenthesolutionsi and ij j.ThedistancemetricusedisthenormalizedEuclideandistanceinobjectivefunctionspace: (cid:12) (cid:13) (cid:5) (cid:6) d =(cid:13)(cid:14)(cid:3)q fki − fkj 2 (8) ij fmax− fmin k=1 k k where q isthenumberofobjectives, fmax and fmin are themaximum andminimumobjective k k function value of the kth objective considering the current population, and fi is the objective k functionvalueofthekthobjectiveofthesolutioni. Weevaluatethenichecountforsolutioni,nc asfollows: i μ(cid:3)(τi) nc = Sh(d ), i =1,...,P. (9) i ij j=1 Then,wecomputethesharedfitness: F(cid:6) = Fi . (10) i nc i Thus,whencomparingtwosolutionsofthesamerank,theonefromthelesscrowdedregionwill haveahighersharedfitness. Finally,topreservethesameaveragefitnessforallsolutionsofthe samerankandmaintainselectionpressure,wescalethesharedfitnessasper: F(cid:6)(cid:6) = (cid:2)Fiμ(τi) F(cid:6). (11) i μ(τ) (cid:6) i i F k=1 k PesquisaOperacional,Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “main” — 2014/7/1 — 13:27 — page 174 — #10 (cid:2) (cid:2) 174 AGENETICALGORITHMFORTHEONE-DIMENSIONALCUTTINGSTOCKPROBLEMWITHSETUPS Parent selection: given the fitness scheme above we select individuals to be parents using fitness-proportionateselection,implementedviathe“roulettewheel”algorithm.Thisisconcep- tuallythesame as spinninga one-armedroulettewheel, where thesizes oftheholesreflect the selectionprobabilities(Eiben&Smith,2010). Populationreplacement strategy: a steady-statemodel isused wherebyonenew individual is generated per iteration. If this is better than the worst individualof the current population, then the latter is eliminated and the new individualis included in the sorted populationin the correctposition. Representation: consider an individualas a feasible solutionfor the cutting stock problem. The individual is made up of a number of genes, each of which represents a cutting pattern (a ) and also the number of times it is cut (x ). Therefore, an individual is represented as a j j matrixwhereacolumnrepresentsacuttingpattern(andthenumberoftimesitiscut). Weallow individuals to contain different numbers of patterns, so the number of columns in the matrix representinganindividualcan be different,butthenumber ofrowsineach matrixisthesame: equal to the number of different items (m) plus one row containing the number of times the cuttingpatternisused. Creation of initial population: in order to generate the initial population an adaptation of the simple Repeat Exhaustion Reduction (RER) Heuristic (Hinxman, 1980) is used. It can be summarizedasfollows. Step1: Constructacuttingpatterna . j Step2:Applythiscuttingpatternasmanytimesaspossible(i.e.,determinex ),withoutexceed- j ingthedemandforanyitem. Step 3: Update thedemand and repeat steps 1 and2 untilthe demand is fullymet (we have a feasibleintegersolution). Inordertoassistevolutionarysearchtheinitialpopulationshouldsamplethesearchspace, soit isimportanttogenerateindividualswithdifferentcharacteristics. Twodifferentapproacheswere used to construct a cuttingpattern in Step 1. Each of these ranks items in a differentway and thenselectsitemstogointothecuttingpatternaccordingtothisrank: RER 1: Rank items according to the First Fit Decreasing (FFD) heuristic (Johnson, 1974; Wa¨scher&Gau,1996). RER2:Rankitemsrandomlyand,onceanitemischosen,determinethenumberoftimesitwill beincludedonthecuttingpatternaccordingtotheminimumvaluebetweentheremainingspace andapercentageoftheitem’sdemand. Thispercentageisrandomlychosen, between10%and 100%oftheitem’sdemandandisfixedtoevery itemthatwillbeincludedonthesame cutting pattern. The ideaistohaveitemswithsimilardemandonthecuttingpatternanditwillhelpin reducingthenumberofdifferentcuttingpatterns. PesquisaOperacional, Vol. 34(2),2014 (cid:2) (cid:2) (cid:2) (cid:2)