Etiqueta: Ciencias de la computación

Búsqueda Tabú

Búsqueda Tabú

La abundancia de problemas de optimización de alto grado de dificultad en el mundo real ha sido una de las causas principales por la que en los últimos años se ha desarrollado un número considerable de técnicas heurísticas que permiten obtener al menos un resultado sub-óptimo en un período de tiempo relativamente corto en problemas que resultaría impráctico resolver mediante “fuerza bruta”, es decir enumerando todas las posibles soluciones para escoger de entre ellas a la mejor.

La búsqueda tabú tiene sus antecedentes en métodos diseñados para cruzar cotas de factibilidad u optimalidad local tratadas como barreras en procedimientos clásicos, e imponer y eliminar cotas sistemáticamente para permitir la exploración de regiones no consideradas en otro caso.. Una característica distintiva de este procedimiento es el uso de memoria adaptativa y de estrategias especiales de resolución de problemas. La búsqueda tabú es el origen del enfoque basado en memoria y estrategia intensiva en la literatura de la meta-heurística, en contraposición con los métodos que no tienen memoria o que sólo usan una memoria débil basada en herencia. La búsqueda tabú es también responsable de enfatizar el uso de los diseños estructurados para explotar los patrones históricos de la búsqueda, de forma opuesta a los procesos que confían casi exclusivamente en la aleatorización.

Los principios fundamentales de la búsqueda tabú fueron elaborados en una serie de artículos a finales de los años 1980 y principios de los años 1990. El destacable éxito de la búsqueda tabú para resolver problemas de optimización duros, especialmente aquellos que surgen en aplicaciones del mundo real, ha causado una explosión de nuevas aplicaciones de este tipo de búsqueda durante los últimos años. La filosofía de la búsqueda tabú es derivar y explotar una colección de estrategias inteligentes para la resolución de problemas, basadas en procedimientos implícitos y explícitos de aprendizaje.

Las técnicas heurísticas más conocidas hoy en día no hacen más que adaptar ideas conocidas desde hace mucho tiempo en otras disciplinas. Por ejemplo, los algoritmos genéticos emulan los mecanismos de la evolución; los métodos de flujo de redes se fundamentan en ideas de la electricidad y la hidráulica, y el “templado simulado” se basa en un proceso físico de la industria metalúrgica. Similarmente, la técnica conocida como búsqueda tabú se basa en ciertos conceptos tomados de la Inteligencia Artificial y se utiliza como una meta-heurística, o una heurística de “alto nivel”, para resolver problemas de optimización combinatoria. Esto significa que la técnica tiene que combinarse con algún otro mecanismo de búsqueda, y lo que hace, básicamente, es evitar que dicho mecanismo quede atrapado en algún óptimo local.

Los orígenes de la búsqueda tabú se ubican a fines de los años 1960 y principios de los años 1970, y se atribuye a Fred Glover, quien desarrolló esta heurística para tratar de resolver problemas de cubierta no lineal, aunque varios de sus principios también fueron delineados independientemente por P. Hansen. La búsqueda tabú surgió como un dispositivo que permitiría implementar una estrategia para resolver problemas de programación entera con restricciones sustitutas, y aunque su planteamiento original ha sufrido varios cambios a través de los años, la idea básica propuesta por Glover ha permanecido intacta desde sus orígenes.

La búsqueda tabú puede verse como una meta-heurística que se superpone a una técnica de búsqueda y que se encarga de evitar que dicha técnica caiga en óptimos locales prohibiendo, o en un sentido más general penalizando, ciertos movimientos. El propósito de clasificar ciertos movimientos como prohibidos es para evitar que se caiga en ciclos durante la búsqueda. Debido a esto, Glover sugiere como nombre alternativo para su método el de búsqueda con “inhibición débil”, ya que los movimientos que se consideran prohibidos constituyen generalmente una pequeña fracción del total de movimientos disponibles, y un movimiento pierde su status de prohibido después de un período de tiempo relativamente corto, volviéndose después nuevamente accesible. A este respecto, este método puede contrastarse con la técnica de ramificación y límites que también prohíbe ciertos movimientos para evitar ciclos, pero lo hace de una manera más rígida, por lo que se le considera como una forma de búsqueda con “inhibición fuerte”. Desde la perspectiva de la inteligencia artificial, la búsqueda tabú trata de emular, de manera somera, el comportamiento de una persona.

Es bastante aceptado que los seres humanos poseen un avanzado mecanismo de intuición que permite operar aún con información mínima o nula, pero por lo general suelen introducir un elemento aleatorio en dichas decisiones, lo cual promueve un cierto grado de “inconsistencia” en su comportamiento. La tendencia resultante en estos casos suele desviarse de una cierta trayectoria pre-establecida, lo cual algunas veces puede ser una fuente de errores, pero en otras ocasiones puede llevar a una solución mejor. La búsqueda tabú intenta emular este mecanismo fundamental de la ingenuidad humana, pero sin utilizar elementos aleatorios, sino más bien asumiendo que no hay razón para escoger un movimiento que conduzca a una peor solución, a menos que se esté tratando de evitar recorrer una ruta que ya se examinó previamente. Con esta sola excepción, la técnica buscará, a cada paso, el mejor movimiento posible de acuerdo a la métrica utilizada por el problema en cuestión. Esto hace que la técnica se envíe inicialmente de forma directa hacia un óptimo local, pero eso no importa porque la búsqueda no se detendrá ahí, sino que se reinicializará manteniendo la capacidad inicial de identificación del mejor movimiento posible. Además, se mantiene información referente a los movimientos más recientes en una o más listas tabú, a fin de evitar que una cierta trayectoria previamente recorrida se repita, aunque esta prohibición es generalmente condicional y no absoluta.

La búsqueda tabú se encuentra fundamentada en tres elementos principales: (1) El uso de estructuras flexibles de memoria basadas en atributos. Estas estructuras se encuentran diseñadas para permitir una mejor explotación de los criterios de evaluación y la información histórica de la búsqueda que lo que se conseguiría con estructuras rígidas de memoria, o con sistemas carentes de memoria. (2) Un mecanismo asociado de control. Que se utiliza para emplear las estructuras de memoria, basado en la interacción entre las condiciones que limitan y hacen más flexible el proceso de búsqueda. Este mecanismo se encuentra inmerso en la técnica en forma de restricciones y criterios de aspiración, un criterio de aspiración es aquél que permite que un movimiento pierda su status de “tabú” debido a que proporciona una mejor solución que la actual. (3) La incorporación de memorias de diferente duración. Denominadas de corto a largo plazo, se emplean para implementar estrategias que intensifiquen y diversifiquen la búsqueda. Las estrategias de intensificación refuerzan las propiedades de las combinaciones de movimientos que han demostrado, históricamente, ser buenas, mientras que las estrategias de diversificación dirigen la búsqueda hacia nuevas regiones del espacio de soluciones factibles. Se debe observar que estos dos mecanismos son muy similares al apareamiento y la mutación en los algoritmos genéticos, ya que la primera permite delimitar una cierta región del espacio de búsqueda, mientras que la segunda permite saltar a nuevas regiones del mismo, evitando quedar atrapado en un óptimo local. La parte medular de la búsqueda tabú se localiza en el proceso de memoria de corto plazo, y muchas de las consideraciones estratégicas en las que se fundamenta este proceso reaparecen, amplificadas pero sin mayores modificaciones, en los procesos de memoria de largo plazo.

El marco de memoria adaptativa de la búsqueda tabú no sólo explota la historia del proceso de resolución del problema, sino que también exige la creación de estructuras para hacer posible tal explotación. La historia de resolución del problema se extiende a la experiencia ganada tras resolver múltiples instancias de una clase de problema uniendo la búsqueda tabú con un enfoque de aprendizaje asociado llamado “análisis de objetivo”.

Las listas tabú que contienen atributos pueden ser más efectivas para algunos dominios, pese a que presentan un nuevo problema. Cuando sólo un atributo es marcado como tabú, esto por lo general resulta en que más de una solución es marcada como tabú. Algunas de estas soluciones, que ahora deben ser evitadas, podrían ser de excelente calidad y no serían visitadas. Para mitigar este problema, se introducen los “criterios de aspiración”: estos pueden modificar el estado de tabú de una solución, por lo tanto incluyendo la antes excluida solución en el conjunto de soluciones permitidas. Un criterio de aspiración muy utilizado es admitir soluciones que son mejores que la mejor solución conocida al momento.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Junio 21 de 2010

Computación

Computación

Una computadora es simplemente cualquier dispositivo que pueda calcular. El nombre se deriva del latín computare, que significa contar o calcular, y se aplica adecuadamente a un ábaco en la antigüedad y a una máquina sumadora en la actualidad. La computadora fue el elemento tecnológico más importante que afectó a la sociedad en la década de los años 1960 y surge de la necesidad de encontrar formas eficientes de manipular información para representar hechos o situaciones reales. En otras palabras, el hombre no ha parado de crear máquinas, dada su continua necesidad de transmitir y tratar información. Se entendió, entonces, que el término computación se refería al conjunto de conocimientos, técnicas y formas de uso relativas a computadoras en general. Sin embargo, también se creó el término informática, para referirse a la ciencia encargada del estudio y desarrollo de las computadoras y de los métodos para procesar la información. El término informática se creó en Francia el año 1962, y procede de la contracción de la palabra: Información automática. En general, se entiende por informática a la ciencia que estudia el tratamiento automático y racional de la información.

La computación o ciencia de la computación, es el estudio de los fundamentos teóricos de la información y el cómputo, así como las técnicas prácticas para su implementación y uso en sistemas de cómputo. Es descrita con frecuencia como un estudio sistemático de los procesos algorítmicos que crean, describen y transforman la información. De acuerdo con Peter J. Denning, la cuestión fundamental en que se basa la ciencia de la computación es, ¿Qué puede ser eficientemente automatizado?. La ciencia de la computación tiene muchos sub-campos; algunos de los cuales como los gráficos por computadora, se especializan en calcular resultados específicos, mientras que otros como la teoría de complejidad computacional, estudia las propiedades de los problemas computacionales. Incluso otros sub-campos se enfocan en desafíos para el cómputo aplicado. Por ejemplo, la teoría de los lenguajes de programación estudia aproximaciones para describir cálculos, mientras que la programación de computadoras aplica específicamente lenguajes de programación para resolver problemas específicos, y la interacción hombre-computadora se enfoca en hacer que tanto las computadoras como sus programas o aplicaciones sean útiles, usables y accesibles de manera universal para toda la humanidad.

El concepto de “computación” refiere al estudio científico que se desarrolla sobre sistemas automatizados para el manejo de la información, lo cual se lleva a cabo a través de herramientas pensadas para tal propósito. Es de este modo, que aparecen conceptos como la computadora personal, tecnología computacional, Informática e Internet, que se vinculan entre sí en el marco del procesamiento y movilidad de la información. La ciencia de la computación supone un área muy profunda de análisis, que tiene sus orígenes en 1920, cuando “computación” hacía referencia a los cálculos generados por la propia persona. Luego, con la llegada de las computadoras personales, la historia y el significado de este concepto se ampliarían sobre nuevos horizontes, distinguiendo los algoritmos que forman parte del desarrollo asociado a la solución lógica de los problemas. En una síntesis bastante apretada, “computación” implica las órdenes y soluciones dictadas en una máquina, que comprenden el análisis de los factores involucrados sobre este proceso, dentro de los cuales aparecen los lenguajes de programación. De este modo, se automatizan tareas, generando datos concretos de manera ordenada.

La computación es la disciplina que busca establecer una base científica para resolver problemas mediante el uso de dispositivos electrónicos y sistemas computacionales. La computación es el estudio de métodos algorítmicos para representar y transformar la información, incluyendo su teoría, diseño, implementación, aplicación y eficiencia. Las raíces de la computación se extienden profundamente en la matemática y la ingeniería. La matemática imparte el análisis del campo y la ingeniería imparte el diseño. La computación se define como el conjunto de conocimientos científicos y técnicos, entre los cuales se encuentran las bases teóricas, métodos, metodologías, técnicas, y tecnologías, las cuales en su conjunto hacen posible el procesamiento automático de los datos mediante el uso de computadoras, para producir información útil y significativa para el usuario. En contraposición con lo mencionado, la computación no es: (1) conocer que computadora comprar, (2) arreglar computadoras, (3) editar y procesar textos, (4) instalar software, (5) navegar por la Web, (6) manejar paquetes de software comercial, (7) diseñar aplicaciones basadas en la Web, (8) conocer diferentes lenguajes de programación, (9) administrar cabinas con el servicio WWW de Internet, (10) diseñar soluciones graficas.

La historia de la computación puede remontarse a cientos de años atrás, cuando se creaban máquinas para ayudar en tareas de cálculo, tales como el ábaco. La primera calculadora mecánica fue creada el año 1623 por Wilhelm Schickard, además Charles Babbage diseñó la máquina diferencial en la época victoriana. Todas las máquinas se limitaban a realizar una sola tarea, o como mucho, algún subconjunto de todas las posibles tareas. Las nuevas y poderosas computadoras comenzaron a ser desarrolladas durante la década de los años 1940, que es también cuando comenzó a hacerse evidente que las computadoras podían usarse para mucho más que simples cálculos matemáticos. La masificación de la computación llegó de la mano de las computadoras personales a principios de los años 1980, y el acceso a la información mundial de la mano de Internet, que comenzó su éxito en los años 1990.

Los datos son en general cifras originales, tomados de diversas fuentes que, solos, tienen poco significado. El dato es un concepto básico o elemental, como los nombres de las cosas o las cantidades: un precio, una fecha, el nombre de una persona, etc. La información se refiere a datos “ya trabajados” y con un orden y significado útil para la persona que los recibe. Los datos una vez procesados se convierten en información provechosa. En general se entiende por información a toda forma de representación de hechos, objetos, valores, ideas, etcétera, que permite adquirir el conocimiento de las cosas y la comunicación entre personas. En otros términos, la información es un conjunto de datos convertidos en una forma útil o inteligible como, por ejemplo, un documento impreso, un recibo, etc. Para que una computadora pueda procesar datos es necesario suministrarle las instrucciones adecuadas, para el manejo de esos datos, las cuales deben de ser proporcionadas en forma de programas. Un programa, entonces, es la secuencia de instrucciones que se dan a una computadora para realizar un proceso determinado.

Antes de realizar un programa, previo a la fase de automatización, y producto del análisis hecho al problema planteado, debe realizarse un algoritmo, que no es otra cosa que el conjunto de operaciones necesarias para transformar los datos iniciales en los resultados que se desean obtener en un determinado trabajo. Un algoritmo puede ser elaborado de forma gráfica o escrita y una vez que éste es traducido a un lenguaje de programación es que se denomina programa. Al conjunto de uno o varios programas que realizan un determinado trabajo completo se le denomina aplicación informática.

El término sistema informático se utiliza para nombrar al conjunto de elementos necesarios para la realización de aplicaciones. Un sistema informático puede entenderse como la unión de tres elementos básicos, el hardware, el software y el personal informático, cuya principal finalidad es el procesamiento de datos.

Al cierre se menciona que las computadoras se pueden clasificar en: (1) Analógicas. Las que tienen la capacidad de medir o comparar según un patrón preestablecido. Procesan datos continuos, es decir, manejan señales eléctricas analógicas proporcionales a medidas físicas de tipo continuo y suelen aplicarse para controlar procesos y en determinados problemas de simulación para usos médicos, científicos, meteorológicos, etc. Su programación está plasmada en los circuitos que lo integran y produce sus resultados en forma gráfica. (2) Digitales. Este tipo de computadora maneja señales eléctricas de tipo digital, como datos representados por medio de valores discretos, y por lo tanto opera con información discreta en el tiempo. Procesa los datos siguiendo las especificaciones de un programa por medio de lenguajes y su utilización comprende cualquier tipo de trabajos. (3) Híbridas. Es la combinación de los dos anteriores. Suelen estar constituidas por una computadora digital que procesa información analógica, para lo cual tiene sus entradas y salidas controladas por medio de convertidores analógico-digital o digital-analógico.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Enero 18 de 2010

Conjuntos Aproximados

Conjuntos Aproximados

Con la revolución digital capturar información es fácil y almacenarla es extremadamente barata. Para los científicos los datos representan observaciones cuidadosamente recogidas de algún fenómeno en estudio; en los negocios, los datos guardan informaciones sobre mercados, competidores y clientes; en procesos industriales, recogen valores sobre el cumplimiento de objetivos; pero, en general, los datos en bruto raramente son provechosos. Su verdadero valor radica en la posibilidad de extraer información útil para la toma de decisiones o la exploración y comprensión de los fenómenos que dieron lugar a los datos. Con el crecimiento actual de los volúmenes de información en las bases de datos, tanto científica como corporativa, la necesidad de determinar qué información es realmente importante se convierte en un reto para los desarrolladores con fines de facilitar las tareas para la minería de datos y el aprendizaje automático. Por tanto, el pre-procesamiento de los datos es esencial en un problema real de cualquier rama de la ciencia: informática, medicina, economía, finanzas, industria, medio ambiente, entre otras.

Una herramienta matemática muy potente para la clasificación, selección y análisis de datos, es la teoría de conjuntos aproximados, propuesta por el profesor polaco Z. Pawlak y su equipo en el año 1982. La filosofía de los conjuntos aproximados se basa en asumir que existe información asociada con cada objeto del universo del discurso. Un conjunto de entrenamiento se representa por una tabla donde cada fila representa un objeto y cada fila un atributo, a este conjunto se le llama sistema de información, más formalmente, es un par ordenado de un conjunto no vacío y finito de objetos llamado universo y un conjunto no vacío y finito de atributos. El modelo de los conjuntos aproximados posee importantes ventajas en el análisis de datos. La principal se basa únicamente en los datos originales y no requiere de información externa para obtener conocimiento sobre el sistema, de forma que no es necesario hacer suposiciones sobre este; la otra ventaja importante consiste en que esta herramienta permite analizar atributos tanto cuantitativos como cualitativos.

Con frecuencia se almacenan grandes volúmenes de información en bases de datos con diferentes objetivos; estos pueden ser adquiridos de mediciones obtenidas por expertos humanos o de representaciones de hechos específicos de problemas de la vida cotidiana. Una base de datos puede contener cierta cantidad de atributos que son redundantes u objetos que se encuentran repetidos en distintos niveles de esta, pero sobre todo sucede que contiene información insuficiente o incompleta. La teoría de conjuntos aproximados emerge desde el contexto del aprendizaje supervisado, donde los conjuntos de datos se refieren a un universo de objetos descritos por un conjunto de atributos y cada objeto pertenece a una clase predefinida por uno de los atributos, llamado atributo de decisión. Para una aproximación inicial, considere que cada conjunto de datos está representado por una tabla, donde cada fila constituye un caso, un evento, un paciente o simplemente un objeto; y cada columna, un atributo que puede ser una variable, una observación, una columna, una propiedad, etc., tal que posee un valor específico para cada objeto. A esta tabla se le denomina sistema de información.

Un sistema de información es un par compuesto por un conjunto finito no vacío llamado el universo y un conjunto finito no vacío de rasgos. Los elementos del universo son llamados objetos. Un sistema de decisión es un par compuesto por el universo y un atributo de decisión. Los conceptos básicos de la teoría de los conjuntos aproximados son las aproximaciones inferiores y superiores de un subconjunto que es conjunto propio del universo. Estos conceptos fueron originalmente introducidos con referencia a una relación de indiscernibilidad. Dicha relación es una relación binaria definida sobre el universo, la cual representa la indiscernibilidad, se dice que esta relación, en función de un elemento del universo, significa el conjunto de objetos los cuales son indiscernibles a dicho elemento.

La teoría de conjuntos aproximados es adecuada para problemas que pueden ser formulados cómo tareas de clasificación y ha ganado un significante interés científico como estructura de minería de datos y descubrimiento de conocimiento. La base de la teoría de los conjuntos aproximados está en la suposición de que cada objeto del universo de discurso tiene rasgos característicos, los cuales son presentados por conocimiento acerca del objeto. Los objetos que tienen las mismas características son indiscernibles. La teoría ofrece herramientas matemáticas para descubrir patrones escondidos en los datos, identifica dependencias parciales o totales, es decir relaciones causa–efecto, elimina redundancia en los datos, proporciona aproximaciones a valores nulos, datos perdidos, datos dinámicos etc.

Los pasos seguidos en la estructura de conjuntos aproximados son los siguientes: (1) Selección. El vehículo básico para la representación de datos en la estructura de la teoría de conjuntos aproximados es plano, tablas de datos en dos dimensiones. Esto no implica que la tabla sea una simple tabla física, una tabla puede ser una vista lógica entre algunas tablas adyacentes. Una tabla adecuada es seleccionada para análisis subsecuentes. Las columnas de las tablas son llamadas atributos, las filas objetos, y las entradas en la tabla son los valores de los atributos. (2) Pre-procesamiento. Si la tabla seleccionada contiene “huecos” en forma de valores perdidos o entradas de celdas vacías, la tabla puede ser preprocesada de varías formas para llenar o completar la tabla. (3) Transformación. Los atributos numéricos pueden ser discretizados, es decir el uso de intervalos o rangos en vez de los valores de los datos exactos. (4) Minería de datos. En la metodología de los conjuntos aproximados, se producen conjunciones de proposiciones elementales o reglas si-entonces. Esto se realiza en un proceso de dos etapas, en el cual subconjuntos de mínimos atributos son primero calculados antes de que los patrones o reglas sean generados. (5) Interpretación y evaluación. Los patrones individuales o reglas pueden ser ordenados por alguna medida de “bondad” y manualmente inspeccionados. Conjuntos de reglas pueden ser empleados para clasificar nuevos casos y registrar el desempeño de la clasificación.

La “teoría de los conjuntos aproximados” se confirma frecuentemente como una herramienta matemática para el análisis de objetos descritos vagamente. El adjetivo vago se refiere a la calidad de la información, significa inconsistencia o ambigüedad, las cuales obedecen a la granulación de la información en un sistema de conocimiento. La filosofía de los conjuntos aproximados está basada en el supuesto de que cada objeto en el universo está asociado a cierta cantidad de información expresada por medio de algunos rasgos usados para la descripción del objeto. Los objetos que tienen la misma descripción son indiscernibles con respecto a la información disponible. La relación de indiscernibilidad modela la indiscernibilidad de objetos, ésta constituye la base matemática de la teoría de los conjuntos aproximados. La relación de indiscernibilidad induce una partición del universo en bloques de objetos indiscernibles, llamada conjuntos elementales que pueden ser usados para construir conocimiento sobre un mundo real o abstracto.

En la teoría clásica de los conjuntos aproximados, la relación de indiscernibilidad es definida como una relación de equivalencia, que es reflexiva, simétrica y transitiva. Esta relación induce una partición del universo en clases de equivalencia correspondientes a la relación de un elemento del universo. Este enfoque clásico de la teoría de los conjuntos aproximados es extendido mediante la aceptación que objetos que no son indiscernibles pero si suficientemente cercanos o similares puedan ser agrupados en la misma clase. El objetivo es construir una relación de indiscernibilidad prima a partir de la relación de indiscernibilidad original pero relajando las condiciones originales para la indiscernibilidad. Esta relajación puede ser realizada de muchas formas, así como pueden ser dadas muchas definiciones posibles de similitud. Sin embargo, la relación indiscernibilidad prima debe satisfacer algunos requerimientos mínimos. Si la relación de indiscernibilidad es una relación de indiscernibilidad definida en el universo, la relación de indiscernibilidad prima es una relación de similitud extendida, entendiéndose que cualquier clase de similitud puede ser vista como un agrupamiento de clases de indiscernibilidad y la relación de indiscernibilidad prima induce un cubrimiento del universo. Cuando una relación de similitud es usada en lugar de una relación de indiscernibilidad, otros conceptos y propiedades de la teoría de conjuntos aproximados: medidas de aproximación, reducción y dependencia, se mantienen válidos.

 

Guillermo Choque Aspiazu
http://www.eldiario.net/
Agosto 4 de 2008

Translate »