lunes, 22 de septiembre de 2014

Heurísiticas para la solución de problemas


Los factores que pueden hacer interesante la utilización de algoritmos heurísticos para la resolución de un problema responden a diversas circunstancias, algunas de estas circunstancias son anotadas por Díaz y sus colegas, en el libro publicado el año 1996 titulado “Optimización heurística y redes neuronales en dirección de operaciones e ingeniería”, como las siguientes: (1) Cuando no existe un método exacto de resolución. Ofrecer entonces una solución aceptablemente buena resulta de interés, frente a no presentar ninguna alternativa. (2) En el momento que es innecesaria la solución más favorable. Existen casos en que no se justifica el costo en tiempo y dinero para hallar una solución óptima que, por otra parte, no representará un beneficio importante con respecto a otra que sea simplemente satisfactoria. (3) Cuando los datos son poco fiables, o bien si el modelo ha simplificado fuertemente la realidad. En estas situaciones carece de interés la búsqueda de una solución exacta, dado que de por sí ésta no será más que una aproximación. (4) Cuando limitaciones de tiempo, memoria, espacio para almacenamiento de datos, etc., obligan al empleo de procedimientos de respuesta rápida, aún a costa de la precisión. (5) Como paso intermedio en la aplicación de otro método. A veces se usan soluciones heurísticas como punto de partida de algoritmos exactos.

Yepes Piqueras, en la tesis doctoral anotada, menciona que una ventaja importante que presentan las heurísticas, respecto a las técnicas que buscan soluciones exactas, es que, por lo general, brindan una mayor flexibilidad en el manejo de las características del problema. Además, pueden ofrecer más de una solución, lo cual amplía las posibilidades de elección, sobre todo cuando existen factores que no han sido incorporados al esquema teórico, pero que también deben considerarse. El investigador Ho, en el artículo publicado el año 1994 titulado “Heurísticas: Reglas del sentido común y la proposición 80/20”, atribuye el éxito de las heurísticas a la aplicación de la regla ochenta-veinte, el ochenta por ciento de la riqueza la posee el veinte por ciento de la población, unos pocos proveedores son responsables de la mayoría de los problemas de la calidad y de los retrasos en las entregas, etc. La distribución desigual ha sido propuesta como un Principio Universal: “Pocos vitales y muchos triviales”, propuesta descrita en el libro de Juran, publicada el año 1951 con el título “Manual de control de calidad”. De este modo, las heurísticas evalúan normalmente un número reducido de opciones que permiten la exploración de las soluciones más interesantes.

Díaz y sus colegas, en el libro citado anteriormente, mencionan que las técnicas heurísticas se pueden agrupar de diversas formas: Métodos constructivos, de descomposición, de reducción, de manipulación del modelo y de búsqueda local. (1) Heurísticas de construcción de soluciones factibles. Los métodos constructivos se basan en añadir paulatinamente componentes individuales a la solución, hasta que se obtiene una opción viable. Uno de los más populares lo constituyen los algoritmos voraces “greedy”, que construyen paso a paso la solución buscando el máximo beneficio en cada etapa. (2) Heurísticas de descomposición. Basándose en el principio de “divide y vencerás”, fragmenta el problema en otros más pequeños de forma que al resolverlos todos se obtenga una solución para el problema global. En algunos casos los problemas se resuelven en cascada, es decir, el resultado de unos son datos de los siguientes, mientras que en otras situaciones los subproblemas se consideran independientes entre sí. (3) Heurísticas de reducción. Estos métodos simplifican el problema tratando distinguir alguna característica que presumiblemente deba poseer la solución óptima. (4) Heurísticas de manipulación del modelo. Se trata de simplificar el esquema teórico para encontrar los valores de las variables de decisión con mayor facilidad, deduciendo, a partir de ella, la solución del problema original. Como posibles estrategias se puede ampliar o reducir el espacio de las opciones. (5) Heurísticas de búsqueda local. Los métodos clásicos de mejora iterativa o de búsqueda local constituyen una clase de heurísticas que se basan en la exploración del entorno asociado al “vecindario” de una solución. Este ámbito está formado por las opciones generadas por una alteración de la solución actual. Mediante estos movimientos se pasa iterativamente de una solución a otra mientras no se cumpla un determinado criterio de terminación. Un procedimiento de búsqueda local queda completamente determinado al especificar un movimiento y el criterio de selección de una solución dentro del entorno.

No hay comentarios:

Publicar un comentario en la entrada