INVESTIGACION DE MODELOS DE ESTADO DEL ARTE EN PROGRAMACION DE MULTIOBJETIVOS

UNIVERSIDAD MEXIQUENSE DEL BICENTENARIO

UNIDAD DE ESTUDIOS SUPERIORES DE ECATEPEC

UNIDAD 5 Introducción a la programación multiobjetivo

1. Conceptos y definiciones de objetivos

1. Investigación de modelos del estado del arte en programación multiobjetivos (sugerencia: algoritmos genéticos, algoritmos de hormiga, redes neuronales, redes de Petri)

Modelos de simulación en la logística.

23 – IL- 271

NOMBRE DE LOS ESTUDIANTES:

Bernabe Serrano Daniel

Mendiola Palestina Víctor Jesús

PROFESORA: MARIA ELIZABETH LARA PUGA

INVESTIGACION DE MODELOS DE ESTADO DEL ARTE EN PROGRAMACION DE MULTIOBJETIVOS

Dentro de la investigación de operaciones, las técnicas clásicas han sido desarrolladas y utilizadas desde hace tiempo, abordando el estudio general de los problemas de optimización con un sólo objetivo y ofreciendo buenos resultados para determinados problemas de ingeniería, negocios, gobierno, economía, ciencias naturales, sociales, etc. Estos problemas se caracterizan por la necesidad de asignar una cantidad limitada de recursos a una colección de actividades; algunos de ellos de calidad, redes de transporte, análisis de colas, horarios de tareas, inversión de capital en selección de portafolios, entrega de servicios de salud, administración de recursos hídricos, programas de obtención de energía, compañías de manufactura, etc.

Muchos de estos problemas que se plantean en la vida real tienen una estructura lógica común, la búsqueda de la mejor solución. Para resolverlos, se han desarrollado algunos procedimientos como la programación lineal, las técnicas de simulación, los métodos heurísticos, programación entera, teoría de redes, control de inventarios, programación dinámica, análisis bayesiano, etc. Algunos de estos métodos consisten en determinar o elegir el valor máximo o el mínimo de una función, eligiendo sistemáticamente los valores de las variables de decisión, en un espacio de búsqueda determinado del problema.

Esto puede ser válido en algunas circunstancias, pero insatisfactorio en otras, cuando es necesario contemplar no sólo un objetivo sino más. A causa de que su aplicación en la realidad de estos problemas es más compleja, se requiere de visiones integrales de todo el sistema; por lo que pensar en soportar las decisiones asociadas a estos con base en un objetivo, sería una consideración demasiado simple.

Más aún si el proceso de toma de decisiones se realiza en un ambiente meramente económico, factores como las características de riesgo e incertidumbre, las altas dinámicas de mercados, la volatilidad en los precios y la presencia de competidores, entre otros, hacen que se requiera de la consideración de múltiples objetivos para apoyar adecuadamente cualquier proceso de toma de decisiones. Por tanto resulta ser extremadamente raro obtener una solución factible la cual simultáneamente optimice todas las funciones objetivo debido a factores como:

• Generalmente la optimización de una de las funciones objetivo puede causar un deterioro en los valores de las otras funciones, de tal forma que optimizar una función implica sacrificar el desempeño de otras.

• Generalmente la optimización de una de las funciones objetivo puede causar un deterioro en los valores de las otras funciones, de tal forma que optimizar una función implica sacrificar el desempeño de otras.

• La programación lineal tradicional es incapaz de dar respuesta a este tipo de planteamientos, es decir los métodos clásicos de programación lineal están enfocados a resolver problemas con un objetivo, y por tanto no son capaces de resolver este tipo de problemas.

Por estas y otras más razones surge la necesidad de considerar más de un objetivo a problemas reales; ya que cuando alguien se enfrenta a un problema, pocas veces es posible evaluar una situación y decidir con base a un criterio único.

A continuación se mencionan algunas de las aplicaciones de la optimización con múltiples objetivos:

[pic 1]

Elementos que conforman la programación multiobjetivo

Se ha incrementado la necesidad de identificar y considerar simultáneamente diversos objetivos en el análisis, así como la solución a problemas con más de un objetivo; motivo por el cual un enfoque más realista y reciente, en las áreas de la

Investigación de operaciones, consiste en la optimización simultánea de varias funciones objetivo denominada programación multiobjetivo.

Ubicación de la programación multiobjetivo

El área de problemas con múltiples objetivos o problemas para la Toma de decisiones multicriterio se suele dividir en dos grandes campos, según las características de los problemas que afronten. El primero es llamado Toma de decisiones multiatributo, el cual trata con problemas que tienen un número finito de posibles decisiones, entre las cuales el que toma la decisión tiene que escoger una, dado un numero de criterios. Por otro lado, está la Programación multiobjetivo, la cual considera problemas de optimización con al menos dos funciones objetivo. El trabajo que se va a desarrollar se centra en este último, concretamente, se analizarán problemas de maximización y/o minimización de una función vectorial lineal cuyo conjunto factible viene definido por funciones también lineales

[pic 2]

                                    División de la toma de decisión multicriterio

La Programación Multiobjetivo (PMO) o también llamada optimización simultánea de varias funciones objetivos, se define como un área de la investigación de operaciones, la cual proporciona métodos útiles y eficientes para la toma de decisiones sobre problemas que incluyen diversidad de objetivos; los cuales hay que tratar de manera conjunta, ya que no es evidente la mejor u óptima alternativa

A diferencia del problema de optimización, en el que sólo existe un valor óptimo; en programación multiobjetivo se busca un conjunto de soluciones eficientes llamado también óptimo de Pareto o conjunto de soluciones no dominadas. En este óptimo de Pareto ninguna solución factible, comparada con otra solución dentro del mismo conjunto, puede mejorar un objetivo sin empeorar simultáneamente otro objetivo. Esto se debe a que muchas veces la ampliación de la idea de optimización multiobjetivo puede ser erróneamente asumida con encontrar una solución óptima a cada función objetivo; ciertamente este concepto es mucho más que esta simple idea.

En el caso de la optimización multiobjetivo, además del conjunto de soluciones eficientes, las funciones objetivo constituyen un espacio multidimensional. Este nuevo espacio se llama espacio objetivo, el cual es una correspondencia del espacio donde se encuentra el conjunto de soluciones eficientes al espacio de las funciones objetivo.

Por tal motivo se pueden hacer notar ciertas diferencias significativas entre los problemas de programación con un objetivo y los problemas con varios objetivos

En un problema general de programación multiobjetivo: si las variables son continuas, las funciones objetivo y las restricciones son lineales entonces el problema es llamado un problema lineal multiobjetivo; si algunas funciones objetivo son no lineales y todas las variables son continuas, entonces es un problema multiobjetivo no lineal continuo; si algunas de las variables pueden tomar valores discretos, es un problema de programación multiobjetivo discreta o entero.

Algoritmos genéticos.

Definición

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuales de ellos deben generar descendencia para la nueva generación.

Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño. Una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos.

...