MEMORIAS DE LA VIII INTERNACIONAL DE INGENIERA MECNICA 18 AL 20 DE MAYO 2011. SAN LUIS POTOS, SLP. MXICO Derechos Reservados 2011, ITSLP ESTIMACIN DEL FRENTE PTIMO DE PARETO EN UN CASO REAL APLICANDO LA TCNICA MOGA 1Ral Leonel Santilln Menchaca, 2Sergio Manuel Ramrez Campos. Departamento de Estudios de Posgrado e Investigacin, Instituto Tecnolgico de Saltillo Venustiano Carranza No. 2400, Col Tecnolgico C.P. 25280, Saltillo, Coahuila, Mxico. Telfono y Fax.(844) 4 38 95 00, webm@its.com raul_santillan@hotmail.com, sramirez@its.mx RESUMEN. Enesteartculosepresentaunaaplicacin delmtodoMOGAMulti-Objective GeneticAlgorithmbasadoenelFrente ptimodePareto(FOP)queatiendeun caso real de planeacin de la produccin en un sistema tipo flow shop donde se procesan guantesdeltexconsiderandodosobjetivos en conflicto: minimizar el nmero de ciclos y maximizarelcumplimientodepedidos,esta situacinimplicaqueunobjetivopuede mejorar a costa de empeorar al otro. Dichas caractersticascorrespondenaunproblema conobjetivosmltiples(Multi-Objective ProblemMOP).Losresultadosmuestran queelmodelogenticodesarrolladologra buenasaproximacionesalFrentedePareto dondesepuedenidentificarsoluciones aceptables para ambos objetivos. ABSTRACT. Thispaperpresentsanapplicationof approximatingtheParetofrontofamulti-criteriaoptimizationproblembysolvinga realcaseofproductionplanningoflatex glovesinaflowshopsystem.Latexgloves areprocessedconsideringtwoobjectivesin conflict:tominimizethenumberofcycles andmaximizethefulfillmentofthedelivery dates. This scenario implies that an objective canimproveatthecostofgettingworseto theother.Thesecharacteristicscorrespond toamulti-objectiveproblem(MOP).The result shows that the developed genetic modelobtainsgoodapproximationsto Paretofrontwhereacceptablesolutionscan be identified for both objectives. INTRODUCCIN En los problemas de optimizacin lo habitual esconsiderarunasrestriccionesyunsolo objetivocomopuedesermaximizarun beneficiominimizarungasto5.Sin embargocomosesabe,enlasempresaslos objetivossonmltiplesyaveces excluyentes.Adems,lamayoradelos problemasdelmundorealgeneralmenteson agranescala,presentannolinealidadesy altaincertidumbre,sonmulti-dimensionales y difciles de modelar.Enparticular,losproblemasde programacinysecuenciacindela produccin de un grupo de mquinas reciben una considerable atencin en la literatura.Ladecisindequtareasdebenasignarsea lasmquinasyenquordensedebende producir,formapartedeunproblema combinatoriocasisiempremuycomplicado y frecuentemente NP complejo9.As, una nueva rea de investigacin llamada OptimizacinEvolutivaconObjetivos Mltipleshacrecidoconsiderablementey estosereflejaconunnotableincremento sobretodoenlosltimos20aosde artculos en revistas internacionales, sesiones enconferenciasespecializadasyalgunos gruposdeinters,desdeTamakietal.9que MEMORIAS DE LA VIII INTERNACIONAL DE INGENIERA MECNICA 18 AL 20 DE MAYO 2011. SAN LUIS POTOS, SLP. MXICO Derechos Reservados 2011, ITSLP hace una revisin muy breve y superficial de algunasdelastcnicasmsimportantes hastaFonsecayFleming3quehacenuna excelentereseadelosprincipales problemas que se enfrentan al tratar de lidiar conobjetivosmltiplesusandounatcnica evolutiva.Entreotrosdesarrollos importantesesteldeZhouetal.15donde exploranlaregularidadquepresentanlas distribucionesdelassolucionesptimasde Paretoconsiderandosolodosobjetivos basndoseenelanlisisdecomponentes principalesyelajustepormnimos cuadrados para construir el modelo. Laumannsetal.6proponenalgunas estrategiasqueayudanaconstruirMOEAs (Multi-ObjetiveEvolutiveAlgorithms)que muestrenpropiedadesdeseablesde convergenciaydiversidadenunasola corrida.Relacionadoconestoltimo,Deby Jain1 aportan dos mtricas normalizadas para medirambaspropiedades(convergenciay diversidad)facilitandounamayorvisinde losMOEAsyunacomparacinentres. Fieldsendetal.2demuestranelimpacto indeseablederestringirelnmerode solucionesenelarchivodeParetoy proponennuevasestructurasdedatos (solucionesdominadasysolucionesno dominadas). Laoptimizacinconobjetivosmltipleses, sinduda,unreadeinvestigacinmuy importantetantoparaloscientficoscomo paralosingenieros,noslodebidoaquela mayoradelosproblemasdelmundoreal tienenobjetivosmltiples,sinotambin porquetodavarestanporresolvermuchas interrogantes en esta disciplina.Esteartculoatiendeuncasorealquese puedeubicardentrodeunsistemade manufacturatipoflowshopdondesehace unaaplicacindelmtodoMOGApara estimarelFOPatravsdeunalgoritmo gentico.Comoyasemencion,se considerandosobjetivosqueestnen conflicto,endondeunodeelloses minimizarelnmerodeciclosyelotroes maximizarelcumplimientoenlasfechasde entrega. INFORMACIN DEL PROCESO Losguantesseformanutilizandomoldesde porcelana(manosizquierdayderecha) llevndolos a travs de un proceso o ciclo en elqueseleagregancapassucesivasde diversas mezclas qumicas introduciendo los moldesentanquesdeinmersin,ademsde someterlos a un secado. La lnea en cuestin consistedeuntransportadorenelcualse montanplatosquecontienenbarras.Para ello, en cada plato se insertan diez barras que contienenlosmoldes.Cincobarras contienenmoldesizquierdosylasotras cincocontienenmoldesderechos.Unavez queunplatoesarmadoconlasdiezbarras, escolocadoenlalneaparasuproceso.La lneasolopuedecontenerunnmero limitado de platos. As, el nmero de moldes quepuedecontenerunabarraesvariableya quedependedeltipodeguanteydesu tamao o talla.Por otro lado, los platos no son iguales entre s,yaqueellotambindependedeltipode guanteydelatalla.Entoncessetieneun inventariolimitadodeplatosporproducto. Eltrminoproductoenesteartculose refiereaunaciertaclasedeguanteyauna talla en particular.Bajoestascondicionessedebedisearun programaeficienteparaatenderuna demanda dada en un cierto periodo, es decir, determinarunasecuenciadeproduccin apropiadaafindesatisfacerlosdos objetivos ya mencionados. Enparticular,lademandaylasfechasde entrega consideradas son las mostradas en la tabla 1 que comprende del 15 de abrilal 30 de abril del 2010 (14 das). MEMORIAS DE LA VIII INTERNACIONAL DE INGENIERA MECNICA 18 AL 20 DE MAYO 2011. SAN LUIS POTOS, SLP. MXICO Derechos Reservados 2011, ITSLP Tabla 1. Demanda de produccin TipoTallaPares# Da de entrega 4978600115-abr 49791000215-abr 497103721315-abr 497102379316-abr 48572942416-abr 48572962417-abr 48582359517-abr 48581457519-abr 48593864619-abr 48595321620-abr 48593271621-abr 485102050721-abr 485105321722-abr 485104581723-abr 48511740823-abr 485115321824-abr 485115321826-abr 485113738827-abr 48371152927-abr 48384311027-abr 483853291028-abr 483922321129-abr 4831025921229-abr 48864901329-abr 488635101330-abr 4841010081430-abr 49578001530-abr Total74,492 OPTIMIZACINDEOBJETIVOS MLTIPLESYFRENTEPTIMODE PARETO Laoptimizacindeobjetivosmltiples, llamadatambinoptimizacinvectorialy optimizacinconcriteriosmltiples,Osyczka10ladefinecomoelproblemade encontrarunvectordevariablesdedecisin que satisfaga las restricciones y optimice una funcinvectorial,querepresentalafuncin objetivo,dondeestasfuncionesobjetivo formanunadescripcinmatemticadelos criterios de desempeo que usualmente estn enconflictoentres.Porlotantooptimizar significaencontrarunasolucinque proporcionevaloresaceptablesparatodos losobjetivos.Matemticamentepuedeser formulado como sigue: Optimizar la funcin vectorial ()(

()

()

()) donde (

) que satisfaga las restricciones de desigualdad m

( ) y las restricciones de igualdad p

( ) En el caso que no exista un solo punto en el quef(x)alcancesuptimoseutilizael concepto de optimalidad del Frente de Pareto segnMiettinen7.Esteconceptoestbasado enlarelacindedominancia,lacualqueda definida como sigue:

*+

(

)

(

) *+

(

)

(

) La notacin

se lee como la solucin x1 domina a la solucin x2. La solucin x1 es indiferente a x2 si ninguna deellasdominaalaotra.Lasmejores solucionesdeunproblemamulti-objetivo estnrepresentadasporelsubconjuntode solucionesnodominadodetodaslas solucionesfactibles;aestaimagensele conoce el Frente de Pareto.Lainterpretacingeomtricadelas solucionesptimasdeParetoparaun problemadedosobjetivossemuestraenla figura 2. MEMORIAS DE LA VIII INTERNACIONAL DE INGENIERA MECNICA 18 AL 20 DE MAYO 2011. SAN LUIS POTOS, SLP. MXICO Derechos Reservados 2011, ITSLP Figura 2.Soluciones ptimas de Pareto en un problema de dos objetivos. MTODO MOGA Ishibuchietal.8 aplicaronelmtodoMOGA aunaprogramacinflowshoputilizando sumasponderadasparacombinarobjetivos mltiplesdentrodeunobjetivosimple(ver ecuacin 1). ()

()

()

() (1) Donde

()

()

()sonlasfunciones objetivoy

sonlospesos correspondientesalosobjetivosque satisfacen la condicin de la ecuacin 2.

(2)

Unavezquelospesossondeterminadosla direccindebsquedaesfija.Paraquela bsquedadelassolucionesptimasde Paretoseantantascomoseanposibles,la direccindebsquedadebesercambiada variasveceshastabarrertodoelespaciode soluciones. Por lo tanto los pesos tienen que sercambiadosrepetidasveces.Lospesos consistenennmerosaleatoriosyson generados segn la ecuacin 3.

(3) Donde

sonnmerosaleatorios enelintervalo(0,1).Elconceptode optimalidaddeParetoseaplicapara determinarqusoluciones,delas encontradasenunbarrido,pudieran perteneceralfrenteptimodePareto.El algoritmo MOGA se muestra en la figura 3. Figura 3. Pasos del mtodo MOGA. MODELO MOGA DISEADO El mtodo MOGA es iterativo y el detalle de cadapasoseexplicaacontinuacin. Paso1:Codificacindelcromosoma.El primerpasoeslarepresentacinadecuada deloqueesunasolucinalproblemadado medianteuncromosoma.Paraellodebe explicarse el significado de un gen. Debido a queunoomsproductosutilizanunacierta configuracindetanquesdeinmersin, entonces,ungenserelconjuntode productosquetienenunamisma configuracindetanques.Porlotanto,un cromosomaestarcompuestoporlosgenes necesarios para cubrir toda la demanda de un periodo.Deaququelalongituddeun cromosoma sea variable. Regin FactibleSoluciones ptimas de ParetoMEMORIAS DE LA VIII INTERNACIONAL DE INGENIERA MECNICA 18 AL 20 DE MAYO 2011. SAN LUIS POTOS, SLP. MXICO Derechos Reservados 2011, ITSLP Cabeaclararqueunaconfiguracinde tanquesserefiereaunciertonmero(t)de tanques,conunaciertamezclacontenidaen cada uno de ellos. A partir de la demanda se identifica un conjunto (c) de configuraciones de tanques requeridos. Paso2:Generacindelapoblacininicial mediante un mecanismo que asegure que las solucionesconsideradassontomadas aleatoriamentedeluniverso.Paraellose sigue el siguiente algoritmo 12: 1.Seforma,alazar,lai-sima configuracin de tanques CTi a partir del conjunto c donden i s s 1 . Hacer k =1. 2.Seseleccionalak-simademandayse verifica si su CTk es igual a la CTi donde n k s s 1 . 3.Si se cumple el paso 2 se contina en el paso5.Encasocontrariohacerk=k+ 1 e ir al paso 4. 4.Sin k s continuarenelpaso2.Encaso contrario sedescarta la CTi actual, sehacei=i+1ysecontinaenel paso 1.5.Se selecciona la k-sima demanda como factibledeprogramaryseeliminadel conjuntooriginaldedemandahaciendo n = n - 1. 6.Siyaseseleccionaronndemandas,se detieneelalgoritmo.Deotraformase contina en el paso 2. Unavezquesegeneraelnmerode soluciones deseado, se dispone de una pobla-cininicialcompuestadepindividuoso soluciones factibles.Paso3:Evaluarlafuncinobjetivo.La funcinobjetivototalestconstituidaporla combinacinlinealdelafuncionesobjetivo (verecuacin1)dondelospesosson asignados aleatoriamente (ver ecuaciones 2 y 3).Comoyasemencion,losobjetivos considerados son:

()

()Dado que f1 se desea minimizar y f2 se desea maximizar,sellevacabouna normalizacin para que la funcin de aptitud puedasercalculadaconvalores adimensionales.Enamboscasos,seestim lamediayladesviacinestndar(con algunas corridas previas) con lo cual se hizo la siguiente transformacin:

11 11minsx xf= (4) 22 22maxsx xf= (5) Donde

= media del nmero de ciclos

= nmero de ciclos de una corrida i

= media del ndice de cumplimiento

= ndice de cumplimiento de una corrida i El ndice de cumplimiento se calcula a partir de las fechas de entrega de cada demanda i y delaprioridadindividual(olaimportancia) quelacompaaasignealamisma.Para ello,sedeterminalaprioridaddeentrega (pei)ordenandolademandaprimerode mayoramenorprioridadindividualyluego delafechamsprximaalamslejanade vencimientoobteniendoelordenamiento deseable(od). Debe hacerse notar que puede haberdemandasconigualprioridadde entrega. Una vez que se obtiene una solucin dada,segeneraunordenamiento(ox) yse comparan ambos. Unejemplodelordenamientodeseable(od) de13demandasseraelsiguiente: 1112234455678 y un ordenamiento derivado deunasolucin(ox)pudieraser 4111543522867.staltimaserieimplica quelaprimerdemandaquesevaaatender tieneunaprioridaddeentregade4.Al compararambasseriesseobservaquesolo dosposicionesconcuerdan:lasegundayla tercera. Entonces, el ndice de cumplimiento sera2/13.As,elndicedecumplimiento est determinado por la ecuacin 6. MEMORIAS DE LA VIII INTERNACIONAL DE INGENIERA MECNICA 18 AL 20 DE MAYO 2011. SAN LUIS POTOS, SLP. MXICO Derechos Reservados 2011, ITSLP dcnnx =2(6) donde nd = nmero de demandas consideradas y nc = nmero de posiciones correctas. Paso 4: Identifica y guarda las soluciones no dominadas.Elpseudo-cdigo12semuestra enseguidaendondelasimilitudestdada porladistanciaEuclidianadelasfunciones de aptitud. for cada individuo o en la poblacin de hijos do if(odominaaunindividuoenlapoblacinde padresp)and(onoestdominadoporninguna solucindelarchivo)and(onoessimilara ninguna solucin del archivo)agregueoal archivo else descarte o end if end for for cada solucin en el archivo do if la solucin a1 domina a a2 then remueva a2 end if end for Paso5:Determinarelrangooposicinde cadaindividuo.Acadaindividuodela poblacin se le asigna un rango de acuerdo a suaptitudafindeidentificarlamejor solucin. Paso 6: Seleccin. Se seleccionan al azar dos solucionesparaformarcadapareja.Este procesoserepitehastaformarlasparejas requeridasdeacuerdoalatasade reproduccin (tR) fijada. Paso7:Cruzamiento.Sesigueelsiguiente algoritmo11: 1.Seseleccionaelk-simogendonde l k s s 1 yl eslalongitudmenorde ambos padres. 2.Se genera un nmero entero aleatorio R tal que2 1 s s R . 3.Si R=1 se seleccionaelgenk del padre P1,encasocontrarioseeligeelgenk del padre P2. 4.Elgenseleccionadoenelpaso3 constituye el k-simo gen del hijo.5.Se hace k = k + 1 y sil k sse contina enelpaso1.Encasocontrariotermina el algoritmo. Enseguida se inicia el proceso de reparacin verificandosielhijoesfactibleono.Para ellosecompruebasiexistenproductos duplicados y en su caso los elimina. Luego si faltanproductoslosbuscaenambospadres ylosincorporaalhijo.Secontinan seleccionandootrasparejashastacompletar la tasa de reproduccin establecida. Paso8:Mutacin.Seprocedealamutacin dadaunatasatmcuyovalorserecomienda15 alrededorde0.2.Sitm =0.2implicaqueel 20%delapoblacinactualsemutar.Una mutacinseobtienedeacuerdoconel siguiente algoritmo12: 1.Segeneraunnmeroaleatorioritalque 1 0