Heurísticas y el problema del agente viajero
Uno de los problemas más famosos y difíciles en la teoría de optimización, es del problema del agente viajero (TSP). El interés en el estudio de técnicas para su solución es motivado por la enorme cantidad de aplicaciones prácticas de problemas de toma de decisiones donde éste aparece como subestructura. En este artículo se hace una breve reseña de los métodos de aproximación (heurísticas) más relevantes que se han propuesto para intentar encontrar soluciones factibles de alta calidad.
El problema del Agente Viajero (mejor conocido por TSP, por sus siglas en inglés; Traveling Salesperson Problem), el cual es un problema clásico de optimización combinatoria, una de las subdisciplinas de la investigación de operaciones (IO). Señalamos cómo las aplicaciones de IO se encuentran en prácticamente todos los niveles y en todo tipo de industrias, y cómo una utilización adecuada de las técnicas de IO dándole soporte al complejo proceso de toma de decisiones que enfrentan las empresas, puede tener un impacto económico significativo.
el TSP se formula de la siguiente manera. Un agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar al punto de partida. Un recorrido con estas características, es llamado dentro de este contexto un tour
Garantías de Desempeño.
Hemos mencionado que no es posible garantizar que los dos métodos anteriormente descritos produzcan buenas soluciones.
Metaheurísticas
Las metaheurísticas son una clase de métodos de aproximación, que se diseñan para atacar problemas difíciles para los cuales las heurísticas de propósito especial han fracasado en dar resultados efectivos y eficientes. Las metaheurísticas proporcionan marcos generales que permiten crear nuevos híbridos combinando diferentes conceptos derivados de las heurísticas clásicas, la inteligencia artificial, la evolución biológica, los sistemas neuronales, la mecánica estadística y el psicoanálisis freudiano.
Referencias:
http://yalma.fime.uanl.mx/~roger/work/Papers/article/article-inge-2000.pdf
el TSP se formula de la siguiente manera. Un agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar al punto de partida. Un recorrido con estas características, es llamado dentro de este contexto un tour
Algoritmos para la solución del TSP
Heurísticas de Propósito Especial
Se llaman de propósito especial, porque explotan la estructura y características particulares de cada problema. La primera familia de esta clase de heurísticas que describiremos pertencen a las heurísticas de tipo miope (greedy en inglés), son llamadas así porque sólo se preocupan por hacer lo mejor que pueden localmente, sin ver más allá de un cierto entorno muy cercano.- El vecino más cercano: Se trata de un procedimiento constructivo, se parte de elegir un vértice inicial
- La inserción más cercana: Este procedimiento es también constructivo, pero en contraste con el anterior, en el cual se tiene un camino, y sólo al final se completa un tour, aquí tenemos subtours, los cuales van creciendo hasta completar un tour que abarque todos los vértices. Iniciemos con un subtour.
Garantías de Desempeño.
Hemos mencionado que no es posible garantizar que los dos métodos anteriormente descritos produzcan buenas soluciones.
Metaheurísticas
Las metaheurísticas son una clase de métodos de aproximación, que se diseñan para atacar problemas difíciles para los cuales las heurísticas de propósito especial han fracasado en dar resultados efectivos y eficientes. Las metaheurísticas proporcionan marcos generales que permiten crear nuevos híbridos combinando diferentes conceptos derivados de las heurísticas clásicas, la inteligencia artificial, la evolución biológica, los sistemas neuronales, la mecánica estadística y el psicoanálisis freudiano.
Referencias:
http://yalma.fime.uanl.mx/~roger/work/Papers/article/article-inge-2000.pdf
Sistemas de Produccion
Esta es la definición de los sistemas de producción de acuerdo al documento de la Universidad Tecnológica Nacional Facultad Santa Fe:
este es la definición del portal de la UDIMA:
Referencia:
http://www.adeudima.com/?page_id=367
http://www.frsf.utn.edu.ar/matero/visitante/bajar_apunte.php?id_catedra=204&id_apunte=3673
Una de las definiciones de la teoría general de sistemas dice que los sistemas son conjuntos de componentes que interaccionan unos con otros, de tal forma que cada conjunto se comporta como una unidad completa. También los sistemas se identifican como conjuntos de elementos o entidades que guardan estrechas relaciones entre sí y que mantienen al sistema directa o indirectamente unido de modo más o menos estable y cuyo comportamiento global persigue, normalmente, algún tipo de objetivo, por ejemplo, optimizar la producción. Un sistema puede ser abierto o cerrado. Los sistemas cerrados (o mecánicos) funcionan de acuerdo con predeterminadas relaciones de causa y efecto y mantienen un intercambio predeterminado también con el ambiente, donde determinadas entradas producen determinadas salidas. En cambio un sistema abierto (orgánico) funcionan dentro de relaciones causa-efecto desconocidas e indeterminadas y mantienen un intercambio intenso con el ambiente. En realidad las empresas son sistemas completamente abiertos con sus respectivas dificultades. Las empresas importan recursos a través de sus entradas, procesan y transforman esos recursos y exportan el resultado de ese procesamiento y transformación de regreso al ambiente a través de sus salidas. La relación entradas/salidas indica la eficiencia del sistema. Un sistema de producción es entonces la manera en que se lleva a cabo la entrada de las materias primas (que pueden ser materiales, información, etc.) así como el proceso dentro de la empresa para transformar los materiales y así obtener un producto terminado para la entrega de los mismos a los clientes o consumidores, teniendo en cuenta un control adecuado del mismo.
este es la definición del portal de la UDIMA:
Conjunto de procesos, procedimientos, métodos o técnicas que permiten la obtención de bienes y servicios, gracias a la aplicación sistemática de unas decisiones que tienen como función incrementar el valor de dichos productos para poder satisfacer unas necesidades.en si los sistemas de producción son procesos y métodos para obtener un bien o un servicio, según sea el caso, pueden ser abiertos o cerrados.
Referencia:
http://www.adeudima.com/?page_id=367
http://www.frsf.utn.edu.ar/matero/visitante/bajar_apunte.php?id_catedra=204&id_apunte=3673
Problemas y espacio de estados
Definición del problema como búsqueda en un espacio de estados.
Aqui se describira el esquema llamado espacio de estados para representar problemas.
Un espacio de estados es un grafo cuyos nodos corresponden a estados del problema, de esta manera y usando este esquema, la solución a los problemas se convierte en la búsqueda de rutas óptimas dentro del grafo.
Aqui se mostraran ejemplos de formulación de problemas utilizando la aproximación de espacio de estados
El problema de los bloques
El problema consiste en encontrar un plan para reordenar la pila de bloques
las restricciones al problema son las siguientes: solamente podemos mover un bloque cada vez; un bloque puede levantarse únicamente cuando no tiene nada encima; el bloque levantado puede colocarse sobre el piso ó sobre otro bloque.
Para resolver el problema se requiere encontrar una secuencia de movimientos válidos que hagan la conversión. Es decir, podemos entender el problema como una exploración de alternativas posibles; en el estado inicial únicamente tenemos una alternativa: colocar el bloque C sobre el piso. Luego del primer movimiento encontramos ahora tres alternativas: poner el bloque A sobre el piso, colocar el bloque A sobre C y, poner el bloque C sobre A.
Este tipo de análisis está basado en el manejo de dos tipos de conceptos: estados del problema y, movimientos válidos que nos hagan pasar de un estado del problema a otro estado del mismo.
en ésta figura, los nodos corresponden a estados posibles del problema y los arcos corrresponden a transiciones válidas entre estados posibles; el problema de encontrar un plan de solución es equivalente a encontrar un camino entre un nodo inicial (estado inicial) y un nodo meta (estado final).
Referencia:
INTAR2014
INTAR2014
Introducción a la Inteligencia Artificial
CONCEPTO DE INTELIGENCIA ARTIFICIAL (I.A.)
Empezaremos con la siguiente pregunta, ¿qué es la Inteligencia Artificial? es un concepto difícil de definir, ya que no hay un concepto concreto sobre que es la inteligencia, pero puede ser catalogada como una rama de la ciencia que se dedica a desarrollar el proceso del pensamiento humano para implementarlo en un ente artificial. Para lograrlo, el estudio de de la I.A. se basa principalmente en 2 áreas, lo que es el cuerpo humano (el estudio de la inteligencia) y el ordenador electrónico, ya que para poder reproducirlo, es necesario conocer el mismo.
Actualmente, el centro del desarrollo de esta rama de la ciencia, es desarrollar sistemas de procesamiento de datos capases de imitar la inteligencia humana, con tareas que requieran de aprendizaje, solución de problemas y decisiones. Estos sistemas, al ser desarrollados pueden ser insertados en computadoras, robots u otros sistemas brindándoles la capacidad de "Pensar".
Teniendo en cuenta lo que es la Inteligencia Artificial, podemos darnos cuenta que esta tecnología avanza a "pasos agigantados", tiene distintas aplicaciones en varias áreas de estudio, hasta el punto de encontrarla en nuestra vida diaria, las aplicaciones mas significativas donde se le puede dar un buen uso a la I.A. o donde es mas requerida, es en las áreas donde hay un gran riesgo para el ser humano o donde se requiera Medicina con su amplia rama de cirugías, también en Ingeniería es muy requerida, porque permite entregar información vital sobre el área de trabajo, para que el ingeniero pueda tomar una mejor decisión y optimizar su trabajo.
Referencias:
Actualmente, el centro del desarrollo de esta rama de la ciencia, es desarrollar sistemas de procesamiento de datos capases de imitar la inteligencia humana, con tareas que requieran de aprendizaje, solución de problemas y decisiones. Estos sistemas, al ser desarrollados pueden ser insertados en computadoras, robots u otros sistemas brindándoles la capacidad de "Pensar".
Referencias:
http://inteligencia-artificial-delabarrita.blogspot.mx/
Subscribe to:
Comments (Atom)
0 comments