WIXLIB

Ingeniería Industrial.Actualidad y Nuevas Tendenciasse destruiría demasiado la estructura delproblema, alejándolo de la realidad. A este tipo deproblemas difíciles de resolver se les denota comoNP-hard en el contexto de la complejidadalgorítmica.Por su parte, Hillier y Lieberman (2010) explicanque con frecuencia, los métodos heurísticos serefieren a un algoritmo iterativo novedoso,diseñado para abordar un determinado problemay no necesariamente a una gran cantidad deaplicaciones. Dentro de ese procedimiento, cadaiteración supone la búsqueda de una nuevasolución que eventualmente pudiera ser mejor queunasoluciónencontradapreviamente,repitiéndose durante un tiempo razonable.Una característica fundamental de los métodosheurísticos es que mediante su utilización no segarantiza la solución óptima al problema encuestión, sino más bien una solución factible muybuena, por lo que los métodos heurísticos seconvierten en soluciones ad hoc que buscan mássatisfacer que optimizar; de hecho, Martí (2003)acuña que muchos de los métodos heurísticos sehan desarrollado para darle solución a undeterminado tipo de problema, quedandoprácticamente inhabilitados para su aplicación aotros problemas similares. Los métodos heurísticosproporcionan entonces soluciones heurísticas. Deallí que, tal como lo plantea Luna (2008) lastécnicas de optimización pueden ser de tipoexactas y aproximadas, encontrándose en estasúltimas los métodos de naturaleza heurística.Cuando se desarrollan algoritmos heurísticos, esimportante evaluar que el mismo sea eficiente(esfuerzo computacional realista), bueno (solucióncercana al óptimo) y robusto (baja probabilidad deobtener una mala solución), para lo cual se puedenemplear procedimientos tales como: comparacióncon la solución óptima, comparación con una cota,comparación con un método exacto truncado,comparación con otros heurísticos y análisis delpeor caso (Martí, 2003).Debido a la naturaleza tan diversa de los métodosheurísticos, Martí (2003) señala que resulta difícildar una clasificación completa de los mismos, ymás bien plantea un conjunto de categorías, noAño 7, Vol. IV, N 12ISSN: 1856-8327110excluyentes, en las que se pudieran ubicar losprincipales métodos desarrollados. Estas son:1.Métodos de descomposición: el problema sedescompone en subproblemas más fáciles opiedades o técnicas identificadas de casos máspequeños y sencillos, al problema complejo ogeneral.3.Métodos de reducción: tienen como propósitorestringir o reducir el espacio de soluciones,simplificando así el problema.4.Métodos constructivos: se basan en laconstrucción progresiva de una solución delproblema, mediante la selección de la mejor opciónen iteraciones sucesivas. Dentro de ellos se puedenmencionar: heurísticos del vecino más próximo,heurísticos de inserción, heurísticos basados enárboles generadores, y heurísticos basados enahorros.5.Métodos de búsqueda local: se caracterizan poriniciar con una solución del problema, la cual debeser mejorada progresivamente a lo largo delprocedimiento. Dentro de esta categoría se puedenmencionar: procedimientos de dos intercambio,procedimientos de k intercambio y algoritmo deLin y Kernighan.6.Métodos combinados: De todos los métodosmencionados hasta el momento, los métodosconstructivos y los métodos de búsqueda localmerecen especial atención, debido a que sucombinación ha permitido el surgimiento denuevos métodos heurísticos, llamados métodoscombinados y que constituyen el eslabón entre losmétodos heurísticos y las metaheurísticas. Dentrode estos métodos combinados se puedenmencionar: procedimientos aleatorizados, métodosmulti-arranque y GRASP (Greedy RandomizedAdaptive Search Procedures).No obstante, Rodríguez (2010) sugiere otradivisión para los métodos heurísticos, a los quedenomina también algoritmos rísticas; de esta forma, propone clasificarlos enmétodos constructivos y métodos de búsqueda.Los primeros, definidos como métodos que sonMárquez. Las metaheurísticas: tendencias actuales y su aplicabilidad en ergonomía, p. 108-120

Ingeniería Industrial.Actualidad y Nuevas Tendenciascapaces de construir una solución a un problemadado, en función a distintas estrategias tales como:voraz, de descomposición, de reducción y demanipulación del modelo. Mientras que losmétodos de búsqueda parten de una soluciónfactible dada y a partir de ella se intenta mejorarla.Como se aprecia, esta clasificación no es más queuna estructuración diferente de la presentada porMartí (2003), donde más bien se intentadiscriminar entre método y estrategia.MetaheurísticasUna metaheurística “es un método de solucióngeneral que proporciona tanto una estructurageneral como criterios estratégicos para desarrollarun método heurístico específico que se ajuste a untipo particular de problema” (Hillier y Lieberman,2010, p. 598). La metaheurística nace con elpropósito de evitar tener que comenzar de cerocada vez que se presente un problema cuyomodelo no puede ser tratado por los métodosconvencionales, para encontrar una soluciónóptima. De acuerdo con estos autores, la principalventaja de una metaheurística bien diseñada, esque permite moverse relativamente rápido haciasoluciones muy buenas, proporcionando unaforma muy eficiente de resolver problemascomplicados. Entre tanto, la principal desventaja esque no existe garantía de que la mejor solución quese obtenga, sea una solución óptima o incluso queesté cerca de serlo.Por su parte, para Herrera (2009) lasmetaheurísticas son algoritmos aproximados depropósito general que consisten en procedimientositerativos que guían una heurística subordinada,combinando distintos conceptos para explorar yexplotar adecuadamente el espacio de búsqueda.En otras palabras, tal como lo explica Martí mente se ubican por encima de losmétodos heurísticos, dado que guían su diseñopara la resolución de problemas difíciles deoptimización combinatoria, en los cuales losmétodos clásicos no son efectivos. Lasmetaheurísticas combinan diferentes conceptos dela inteligencia artificial, la evolución biológica y losAño 7, Vol. IV, N 12ISSN: 1856-8327111mecanismos estadísticos (Osman y Kelly, citadosen Martí, 2003) y suelen basarse en los métodosheurísticos constructivos y de búsqueda localmencionados anteriormente. En este sentido,Rodríguez (2010) plantea que las metaheurísticascombinan ideas que provienen de cuatro camposde investigación diferentes: de las técnicas dediseño de algoritmos que resuelven una colecciónde problemas, de los algoritmos específicosdependientes del problema a resolver, de fuentesde inspiración del mundo real, y de métodosestadísticos.Generalmente, la creación de métodos heurísticoses un proceso que conjuga dos ación(explotación del espacio) referida al esfuerzoempleado en la búsqueda en la región actual, y ladiversificación (exploración del espacio) vinculadaal esfuerzo empleado en la búsqueda en regionesdistantes del espacio; por lo que debe buscarse elequilibrio entre ambas, para lograr buenassoluciones en poco tiempo (Herrera, 2009).En la actualidad se conocen varias metaheurísticasque se han desarrollado exitosamente en laresolución de determinados problemas, talescomo: los algoritmos voraces, la ascensión decolinas, el recocido simulado, colonias dehormigas, algoritmos de enjambre, la búsquedatabú, los algoritmos genéticos, los algoritmosmeméticos, entre otros.No obstante, aunque suele ser una tarea pocosencilla, algunos autores han recopilado algunasformas en las que se pudieran clasificar lasmetaheurísticas; en este sentido autores comoDuarte (2007) o, Blum y Roli (2003) presentan lassiguientes taxonomías clásicas:1.Atendiendo a la inspiración:a.Natural: se basan en un símil real (biológico,social, cultural)b.Sin inspiración: se obtienen directamente de suspropiedades matemáticas2.Atendiendo al número de soluciones:a.Poblacionales: buscan el óptimo a través de unconjunto de solucionesb.Trayectoriales: trabajan con una solución quemejoran iterativamenteMárquez. Las metaheurísticas: tendencias actuales y su aplicabilidad en ergonomía, p. 108-120

Ingeniería Industrial.Actualidad y Nuevas Tendencias3.Atendiendo a la función objetivo:a.Estáticas: no hacen ninguna modificación sobrela función objetivo del problemab.Dinámicas: modifican la función objetivodurante la búsqueda4.Atendiendo a la vecindad:a.Una vecindad: utilizan exclusivamente unaestructura de vecindadb.Varias vecindades: modifican la estructura devecindad5.Atendiendo al uso de memoria:a.Sin memoria: se basan exclusivamente en elestado anteriorb.Con memoria: utilizan una estructura dememoria para recordar la historia pasadaPor su parte, Herrera (2009) presenta una posibleforma de clasificación de las metaheurísticas:1.Basadas en métodos constructivos: las cualesparten de una solución inicial vacía y se vanagregando componentes hasta construir unasolución. En este grupo se pueden mencionar:GRASP, optimización basada en colonias dehormigas.2.Basadas en trayectorias: utilizan como heurísticasubordinada cualquier algoritmo de búsquedalocal, que sigue una trayectoria en el espacio debúsqueda, mediante iteraciones que tratan deremplazar una solución inicial por otra de mejorcalidad. Allí se encuentran: búsqueda local,templado simulado, búsqueda tabú, búsquedalocal iterativa, entre otras.3.Basadas en poblaciones: el proceso contemplamúltiples puntos de búsqueda en el espacio, queevolucionan en paralelo. Dentro de ellas están:algoritmos genéticos, algoritmos meméticos,algoritmos basados en nubes de partículas,búsqueda dispersa, entre otros.Melián et al. (2003) más bien las clasifican enfunción del tipo de procedimientos a los que serefiere, asemejándose más a la categorización delos métodos heurísticos presentada anteriormente.De esta forma, mencionan que los tiposfundamentales son las metaheurísticas para losmétodos de relajación, las metaheurísticas para losprocesos constructivos, las metaheurísticas para lasbúsquedas por entornos y las metaheurísticas paraAño 7, Vol. IV, N 12ISSN: 1856-8327112los procesos evolutivos, y señala como otros ón y las de memoria a largo plazo. Enla Tabla 1 se resumen las diferentes formas declasificar las metaheurísticas de acuerdo a losautores citados.Por otro lado, no debe dejarse de mencionar lasmetaheurísticas inspiradas en distintos fenómenosde la naturaleza tales como las redes neuronales,las colonias de hormigas, las bandadas de aves obancos de peces, los cuales han dado origen ametaheurísticas como las redes neuronalesartificiales, los sistemas de hormigas, o laoptimización de partículas inteligentes.Tabla 1. Formas de clasificación de lasmetaheurísticasCriterioFuente de inspiraciónCantidad de solucionesFunción objetivoCantidad devecindadesUso de memoriaEstrategia seguidaTipo deprocedimientos referidosTipo de MetaheurísticaFenómenos naturalesSin icaUna vecindadVarias vecindadesSin memoriaCon memoriaMétodo constructivoBasada en trayectoriasBasada en poblacionesPara métodos de relajaciónPara procesos constructivosPara búsquedas por entornoPara procesos evolutivosDe descomposiciónDe memoria a largo plazoComo se puede apreciar, no existe una clasificaciónrigurosa ni totalmente aceptada respecto a la grandiversidad de metaheurísticas desarrolladas, las cualespresentan diferencias en cuanto a su naturaleza,estrategia seguida, estructuración, o número desoluciones consideradas a la vez; lo que hace que enalgunos casos las categorías planteadas no seanexcluyentes, permitiendo que un mismo método pudieraincluirse en más de una categoría. Además, como ya seha planteado la esencia de la metaheurística es guiar eldesarrollo de métodos heurísticos que permitan darlesolución a un problema determinado, y facilitar la tomade decisiones.Márquez. Las metaheurísticas: tendencias actuales y su aplicabilidad en ergonomía, p. 108-120

Ingeniería Industrial.Actualidad y Nuevas TendenciasPrincipales aplicacionesLas metaheurísticas, tradicionalmente se han venidoutilizando e implementando en la resolución deproblemas de optimización combinatoria, definidos porMartí (2003) como aquellos problemas de optimizacióncaracterizados por presentar un conjunto amplio deposibles soluciones, en los que resulta prácticamenteimposible evaluar todas las soluciones para hallar lasolución óptima.Debido a su similitud con diferentes situaciones, con eltranscurrir de los años se han venido popularizando unconjunto de problemas de optimización combinatoriaampliamente aplicables en determinados contextos.Dentro de estos problemas clásicos o estructurados,señalados por autores como Duarte (2007) y Martí(2003), se encuentran el problema del viajante decomercio o agente viajero, el problema de la mochila, elproblema de la ordenación lineal, el problema deasignación cuadrática, el problema del cubrimiento oempaquetado de conjuntos, o el problema deenrutamiento de vehículos, por nombrar los máscomunes.No obstante, éstos no son los únicos problemas, sino quepor el contrario se pueden identificar fácilmente unagran cantidad de problemas de optimización tanto en laciencia como directamente en la industria. En laIngeniería Industrial es común encontrarse antesituaciones que exigen determinar camino más corto,plan de mínimo costo, asignación óptima, secuenciaóptima, distribución de recursos a mínimo costo, entreotros (Herrera, 2009).En la revisión documental efectuada, se obtuvo que eltipo de problema más común está referido a laprogramación o secuenciación de operaciones deproducción (scheduling) y sus derivaciones, el cual fueAño 7, Vol. IV, N 12ISSN: 1856-8327tratado en el 29,1% de los casos. Resalta dentro de estegrupo los casos de secuenciación en configuraciones deproducción tipo Job Shop o taller, caracterizados porproducir pequeños lotes de una variedad amplia deproductos.El enrutamiento de vehículos en sus diferentes versionesfue analizado en el 17,6% de los artículos consultados yconstituye el segundo tipo de problema más repetitivo, yno sólo incluye la distribución a nivel industrial, sinocasos de flota de buses escolares y servicios derecolección. En tercer lugar figura el problema deasignación de recursos con un 8,5%; mientras queproblemas como el clásico agente viajero y lalocalización de plantas fueron abordados en el 5,0% delos casos.Se pueden mencionar otros tipos de casos o ad, inventarios, entre otros. Así mismo, cabereseñar que algunos de los trabajos revisados noabordaron problemas o casos reales sino ejemplos oproblemas hallados en la literatura y que permitenvalidar nuevas estrategias o parámetros.Tendencias actualesComo resultado de la revisión de los artículosconsultados, fue posible detectar que en los últimos diezaños ha prevalecido el uso de los algoritmosbioinspirados como método de resolución de problemasde optimización, tal como se muestra en la Tabla 2. Allíse señala el porcentaje de artículos (sobre la base de 340trabajos) en los que fue utilizada una determinadametaheurística, bien de forma individual o encombinación con otra.Tabla 2. Relación de artículos por tipo de metaheurística utilizadaMetaheurísticaAlgoritmos genéticos / Algoritmos evolutivosBúsqueda tabúOptimización por colonia de hormigasRecocido simuladoProcesos aleatorizados y adaptativos de búsqueda vorazBúsqueda de vecindad variableBúsqueda localOptimización por enjambre de partículasBúsqueda dispersaColonia artificial de abejasRedes neuronales artificialesBúsqueda armónicaAlgoritmos meméticosAlgoritmo de la luciérnagaOtras metaheurísticas113Siglas en inglésCantidadPorcentajeGA / ,51,20,92,6Márquez. Las metaheurísticas: tendencias actuales y su aplicabilidad en ergonomía, p. 108-120

Ingeniería Industrial.Actualidad y Nuevas TendenciasDe esta forma, resalta en primer lugar el uso de losalgoritmos genéticos (GA) como la metaheurísticapreferida por los investigadores; la misma fueutilizada en el 27,1% (92) de los casos. El tipo deproblema que ha sido abordado de forma másrepetitiva por los algoritmos genéticos es el deprogramación de la producción, específicamenteen lo referente a la asignación y secuenciación delas operaciones del proceso, tanto en sistemas deproducción tipo taller como en líneas deproducción. En este sentido se pueden reseñartrabajos como los de Correa et al. (2008), D’Armas(2010), Debels y Vanhoucke (2007), Magalhães(2009), Mateo y D’Armas (2008), Ramírez et al.(2009), Ramírez et al. (2011), Taheri y Zomaya(2009), Toro et al. (2006), y Zinflou et al. (2010).En segundo lugar, como las metaheurísticas másrecurrentes en los trabajos consultados, seencuentra la búsqueda tabú (TS), figurando en el22,4% (76) de las investigaciones. Al igual que en elcaso de los GA, también se ha empleado tanto deforma individual como en combinación con otrasmetaheurísticas, para tratar problemas de diferenteíndole, aunque resaltan los casos de enrutamientode vehículos, secuenciación o programación de laproducción y localización de instalaciones(Caramia y Giordani, 2009; Gagné et al., 2005;Hernández et al., 2006; Li et al., 2009; Liu y Kozan,2012; Martins et al., 2003; Moreno et al., 2005;Wassan et al., 2008).La optimización por colonia de hormigas (ACO)constituye la tercera metaheurística más utilizadaen los artículos encontrados, tal como lo refleja el15,0% (51) de las referencias. En este caso, losproblemas más recurrentes siguen siendo el desecuenciación o programación, enrutamiento devehículos y el agente viajero (Allaoua y Gasbaoui,2009; Ke et al., 2010; Li et al., 2009; Merkle yMiddendorf, 2003; Sadjadi et al., 2008; Surekha,2010; VAsko et al., 2011). Esta metaheurísticapertenece a la categoría de los algoritmosbioinspirados que buscan replicar fenómenos ocomportamientos de la naturaleza para la soluciónde problemas cotidianos, y la misma está inspiradaen el comportamiento que siguen las hormigas almomento de buscar sus alimentos.Año 7, Vol. IV, N 12ISSN: 1856-8327114Seguidamente, con 14,7% y 11,8% de artículos,continúan el recocido simulado (SA) y los procesosaleatorizados y adaptativos de búsqueda voraz(GRASP), respectivamente (Baesler et al., 2008;Barros y Moccellin, 2003; Bautista et al., 2008;Bermeo y Calderón, 2009; Escobar et al., 2011;Hernández et al., 2011; Peixoto y Barbieri, 2011).La práctica de combinar dos o más metaheurísticascomo estrategia para alcanzar mejores solucionesen tiempos más cortos se ha venido convirtiendoen una importante tendencia para resolverdiversos problemas de optimización. Al respecto,en la revisión efectuada se hallaron 57 trabajos(16,8%) que incluyen metodologías híbridas ohibridación, es decir, se incorpora unametaheurística como apoyo a otra metaheurísticaprincipal, por lo general para formar la poblacióninicial y así reducir el tiempo que implica arrancarcon una población al azar; tal es el caso de Báez etal. (2008) quienes utilizaron ANN para lageneración de los valores iniciales que luego seránmejorados mediante GA.Así mismo, otro ejemplo de hibridación es laestrategia implementada por Toro y Granada(2005) para resolver un problema de asignacióngeneralizada, la cual consistió en abordar la etapade mutación del GA a través del SA. Por su parte,González y González (2007) probaron unametaheurística híbrida para la solución de unproblema de enrutamiento de vehículos, la cualconsiste en utilizar un algoritmo genético paraconformar clústeres de los clientes, seguido de unalgoritmo de búsqueda tabú para hallar la rutadentro de cada clúster, encontrando mejoras hastade un 23% respecto al empleo de sólo GA.Soto et al. (2008) abordaron el problema deenrutamiento de vehículos mediante unametaheurística híbrida conformada por GA paraclasificar y ACO para optimizar localmente cadasub-ruta, obteniendo soluciones cercanas a lasóptimas conocidas.Otra tendencia importante de mencionar en eltema de las metaheurísticas es la de paralelismo oparalelización, referida al uso compartido ysimultáneo de recursos computacionales, de formaque se puedan ejecutar tareas pequeñas de unMárquez. Las metaheurísticas: tendencias actuales y su aplicabilidad en ergonomía, p. 108-120

Ingeniería Industrial.Actualidad y Nuevas Tendenciasproblema más grande en varios computadores oprocesadores, en especial en aquellos problemasintensivos en tiempos de cómputo y enrequerimientos de memoria. Su ventaja viene dadaademás por la posibilidad de utilizar diferentesestrategias y valores de los parámetros de formasimultánea, para lograr una mayor diversidad yexploración del espacio de búsqueda (Lüer et al.,2009; Alfonso et al., 2010).Para Alfonso et al (2010) el paralelismo junto a lahibridación constituyen dos de las ramas másexitosas para la construcción de algoritmoseficientes. La mezcla de ambas estrategias, es decir,utilizar modelos paralelos donde se usandiferentes procedimientos de búsqueda paraexplorar el espacio de soluciones, da origen a unametaheurística heterogénea paralela.No obstante, aun cuando muchos investigadorescontinúan transitando en el camino del desarrol

Ingeniería Industrial. Actualidad y Nuevas Tendencias ISSN: 1856-8327 revistaiiaynt@gmail.com Universidad de Carabobo Venezuela Márquez Gómez, Mervyn Las metaheurísticas: tendencias actuales y su aplicabilidad en la ergonomía Ingeniería Industrial. Actualidad y Nuevas Tendencias, vol. IV, núm. 12, enero-junio, 2014, pp. 108-120 .