Algoritmos Heurísticos

Algoritmos heurísticos

INTELIGENCIA ARTIFICIALIntegrantes: Cesar Alejandro Escalante Delgado #20110472 Ivette Mireya Peña Zuñiga #20110376 Edgar Oswaldo Montero Comparán #20110334

Algoritmo

Un algoritmo es un grupo de indicaciones definidas, ordenadas y acotadas para solucionar un problema, hacer un cálculo o desarrollar una labor. O sea, un algoritmo es un método paso a paso para lograr un fin.En programación, un algoritmo implica el paso anterior a ponerse a redactar el código. Primero debemos descubrir la manera de obtener la solución al problema (definir el algoritmo informático), para después, por medio del código, poder indicarle a la máquina qué actividades deseamos que lleve a cabo.

Heurística

La palabra heurística se refiere a un grupo de técnicas, de reglamentos o de métodos que se emplean para resolver cualquier tipo de problema. Su origen es el griego heuriskein y su significado, de acuerdo con su proveniencia es inventar o hallar. Esto nos lleva a concluir que el razonamiento son formas en las que los humanos pueden resolver diferentes dificultades de todo tipo utilizando diferentes métodos como la creatividad, el pensamiento horizontal o el pensamiento divergente basados en la experiencia de cada persona, pero también en la experiencia de los demás para encontrar la mejor solución al problema. Los principios heurísticos, deben ver con las recomendaciones que se facilitan para hallar de forma directa, la iniciativa de solución.

Heurística

Hay dos interpretaciones para el concepto heurístico. T. Nicholson: “Procedimiento para resolver problemas por medio de un método intuitivo en el que la estructura del problema puede interpretarse y explotar inteligentemente para obtener una solución razonable”. H. Müller-Merbach: “En investigación operativa, el término heurístico normalmente se entiende en el sentido de un algoritmo iterativo que no converge hacia la solución (óptima o factible) del problema”.

HEURÍSTICA

Una definición que apoya la 2da interpretación: Russell et al.: “Actualmente, el término heurística se utiliza más bien como adjetivo para referirse a cualquier técnica que permita mejorar el desempeño del caso promedio en una tarea de resolución de problemas, aunque no necesariamente permita mejorar el desempeño del peor de los casos. Específicamente en el área de los algoritmos de búsqueda, se refiere a una función mediante la cual se obtiene una estimación del coste de una solución”.

ALGORITMO heurístico

La heurística es la forma de encontrar o diseñar un algoritmo que tenga velocidad suficiente para ser ejecutado en tiempo y forma. Esto se asocia, por ejemplo, al software que se encarga de detectar el spam en los correos electrónicos. En palabras simples, un algoritmo heurístico es un grupo de indicaciones definidas, ordenadas y acotadas para encontrar soluciones a un problema de forma rápida usando un determinado raciocinio en base a la experiencia. Un algoritmo heurístico que es capaz de producir una solución aceptable a un problema en muchos escenarios prácticos, en la moda de una heurística general, pero para el cual no hay prueba formal de su corrección.

La heurística en LA INTELIGENCIA ARTIFICIAL

En programas de IA, las funciones o algoritmos heurísticos son:

• Usadas para medir qué tan lejos está un nodo de su estado meta.
• Utilizadas para comparar dos nodos, encontrando si uno es mejor que otro.

propiedades

Son propiedades de los procedimientos heurísticos:

• No respaldan que esté una solución, aunque existan resoluciones.
• Si encuentran una solución, no se asegura que ésta tenga las mejores propiedades (que sea de longitud mínima o de coste óptimo).
• En algunas ocasiones, encontrarán una solución (aceptablemente buena) en un tiempo razonable
• Generalmente, los procedimientos heurísticos son preferibles a los procedimientos no informados en la solución de inconvenientes difíciles para los que una averiguación intensa necesitaría una época bastante enorme.

La heurística en informática

Existen métodos heurísticos (también llamados algoritmos aproximados, procedimientos inexactos, algoritmos basados en el conocimiento o simplemente heurísticas) de diversa naturaleza, por lo que su clasificación es bastante complicada. Bransford y Stein en 1984 formularon el método heurístico que fue nombrado como IDEAL, traido asi como acrónimo de los siguientes puntos:

• Identificar el problema
• Definir el problema
• Explorar las estrategias viables
• Avanzar en las estrategias
• Lograr la solución y volver a evaluar los efectos de las actividades.

HISTORIA

Anterior a este suceso, en 1957, el matemático Polya había creado un método heurístico para resolver problemas en el cual, según Polya, intervienen cuatro operaciones mentales:

• Entender el problema
• Trazar un plan
• Ejecutar el plan
• Revisar

Estos sucesos formaron la base del análisis de todo método heurístico que busca una solución rápida y concisa a la problemática que se le está planteando.

MÉTODOS CONSTRUCTIVOS

Métodos constructivos: Procedimientos que son capaces de construir una solución a un problema dado. La forma de construir la solución depende de la estrategia seguida. Las estrategias más comunes son: Estrategia voraz: Partiendo de una semilla, se va creando paso a paso una solución probable. En cada paso se incorpora un componente constituyente de esa solución, que se caracteriza por ser el que genera una optimización más alta en la solución parcial para aquel paso concreto. Esta clase de algoritmos se plantea que poseen una perspectiva "miope" debido a que escogen la mejor elección presente sin que les importe que ocurrirá en el futuro.

MÉTODOS CONSTRUCTIVOS

Estrategia de descomposición: Se divide sistemáticamente el problema en subproblemas más pequeños. Este proceso se repite (generalmente de manera recursiva) hasta que se tenga un tamaño de problema en el cual la solución a dicho subproblema es trivial. Luego el algoritmo combina las resoluciones conseguidas hasta que se tenga la solución al problema original. Los algoritmos más representativos de los procedimientos de descomposición son los algoritmos de divide y vencerás tanto en su versión precisa como aproximada .

MÉTODOS CONSTRUCTIVOS

Métodos de reducción: Identifican propiedades que tienen dentro las resoluciones buenas conocidas y se asume que la solución óptima además las va a tener. Así se puede minimizar extremadamente el espacio de averiguación. Métodos de manipulación del modelo: Consisten en simplificar el modelo del problema original para obtener una solución al problema simplificado. A partir de esta solución aproximada, se extrapola la solución al problema original. Entre estos métodos se pueden destacar: la linealización, la agrupación de variables, introducción de nuevas restricciones, etc.

Métodos de búsqueda

Métodos de búsqueda: Parten de una solución factible dada y a partir de ella intentan mejorarla. Estrategia de búsqueda local 1: Parte de una solución factible que la mejora progresivamente. Para ello examina su vecindad y selecciona el primer movimiento que produce una mejora en la solución actual (first improvement).

Métodos de búsqueda

Estrategia de búsqueda local 2: Parte de una solución factible que la mejora progresivamente. Para ello examina su vecindad y todos los posibles movimientos seleccionando el mejor movimiento de todos los posibles, es decir aquel que produzca un incremento (en el caso de maximización) más elevado en la función objetivo (best improvement). Estrategia aleatorizada: Para una solución factible dada y una vecindad asociada a esa solución, se seleccionan aleatoriamente soluciones vecinas de esa vecindad.

Los algoritmos heurísticos no tienen ningún mecanismo que les posibilite huír de los óptimos locales. Para resolver este problema se introducen otros algoritmos de averiguación más capaces que eviten en el tamaño de lo viable permanecer atrapados en óptimos locales. Dichos algoritmos de averiguación más capaces, llamados metaheurísticas, son métodos de elevado grado que guían a algoritmos heurísticos conocidos evitando que éstos caigan en óptimos locales

BIBLIOGRafía

Antonacci, M. (2020, 20 abril). Qué es Heurística - Definición, Significado y Concepto. La definición. Recuperado 16 de agosto de 2022, de https://ladefinicion.com/heuristica/ de Vega, R. M. (2022, 23 junio). Qué es un algoritmo informático: características, tipos y ejemplos. Profile Software Services. Recuperado 16 de agosto de 2022, de https://profile.es/blog/que-es-un-algoritmo-informatico/ R. (2021, 12 febrero). Heurística. Concepto de - Definición de. Recuperado 16 de agosto de 2022, de https://conceptodefinicion.de/heuristica/ [Resuelta] algorithm | ¿Cuál es la diferencia entre un. (s. f.). iteramos. Recuperado 16 de agosto de 2022, de https://www.iteramos.com/pregunta/21531/cual-es-la-diferencia-entre-un-heuristico-y-un-algoritmo#:%7E:text=Un%20algoritmo%20es%20un%20conjunto,descubrimiento%20para%20alcanzar%20una%20soluci%C3%B3n. Rodríguez Ortiz, C. (2009). Capítulo 2 descripción algorítmica. En A. Duarte Muñoz & J. J. Pantrigo Fernández (Eds.), Algoritmos heurísticos y metaheurísticos para el problema de localización de regeneradores.: Vol. (ed., pp. 13–15). Escuela Técnica Superior de Ingeniería Informática. https://burjcdigital.urjc.es/bitstream/handle/10115/4129/memoriaPFC%20Carlos%20Rodr%C3%ADguez.pdf?sequence=1&isAllowed=y