Heurística de Mejoramiento

Heurística de Mejoramiento

En la siguiente tarea se muestra un problema de distribución, que consta de minimizar la distancia recorrida entre 4 diferentes máquinas y sus ubicaciones, obteniendo la mejor solución posible mediante la “Heurística de mejoramiento”.

Con el fin de resolver problemas complicados con eficiencia, en ocasiones es necesario comprometer algunos requisitos de optimalidad y construir una estructura de control que no garantice encontrar la mejor respuesta pero que casi siempre encuentre una buena solución. De esta forma, surge la idea de heurística. La palabra heurística viene de la palabra griega heuriken que significa “descubrir”, que es también origen de eureka, derivado de la famosa exclamación de Arquímedes, heurika (“lo encontré”).

Podemos definir una heurística como una técnica que aumenta la eficiencia de un proceso de búsqueda, posiblemente sacrificando demandas de completitud. Las heurísticas son como los guías de turismo: resultan adecuados en el sentido de que generalmente suelen indicar las rutas interesantes; son malos en el sentido de que pueden olvidar puntos de interés para ciertas personas. Al usar buenas heurísticas se pueden expresar buenas (aunque posiblemente no óptimas) soluciones a problemas difíciles, como el del viajante de comercio. Una función heurística es una correspondencia entre las descripciones de estados del problema hacia alguna medida de deseabilidad, normalmente representada por números. Quiere decir que mensura cada estado del problema (solución) y dice qué tan cerca de la solución óptima está. El propósito de una función heurística es el de guiar el proceso de búsqueda en la dirección más provechosa sugiriendo qué camino tomar cuando hay más de uno disponible. Cuanto más exactamente estime la función heurística los méritos de cada nodo del árbol (o grafo) que representa al problema, más directo será el proceso de solución. En general, hay que hacer una ponderación entre el costo de evaluación de una función heurística y el ahorro de tiempo de búsqueda que proporciona la función.

A continuación, se presentan 4 maquinas y sus lugares a ocupar:[pic 1]

Tomando en cuenta que “r” representa las máquinas y “d” el lugar, obtenemos la siguiente función:

[pic 2]

Con la ayuda de las siguientes matrices sustituimos las “r” y “d” por el valor que le corresponda según las coordenadas que indiquen la “r” y la “d”: [pic 3]

[pic 4]

Una vez realizada esta ecuación dividimos el resultado final entre dos ya que se repiten las mediciones dos veces, arrojando el resultado final.

[pic 5]

Arrojando como mejor resultado, que se recorrerán 166 (unidades de distancia) con esta distribución.

...