Recocido Simulado

Optimización de la Heurística del Recocido Simulado sobre el Problema de la Mochila
Manlio Tulio Guerrero Cruz
Ingeniería En Sistemas Computacionales, Alumno Grupo de Maestría Politécnica de Victoria. Manlio18@gmail.com

Resumen. Abstract.
El objetivo de este artículo es describir los resultados obtenidos de la experimentación de optimización de la heurística del problema de la Mochilaimplementando la heurística del algoritmo Recocido Simulado creando así una Metaheurística y alcanzar una solución que se acerque mas o llegue a la función objetivo o solución optima del problema de la mochila. Finalmente, se muestra el empleo del algoritmo para 'aproximar' la solución objetivo del algoritmo de la mochila así como la experimentación y resultados obtenidos Palabras clave: RecosidoSimulado, Problema de la Mochila The aim of this paper is to describe the results of experimentation optimization heuristic knapsack problem implementing the simulated annealing heuristic algorithm creating a metaheuristic and reach a solution that is closer or get to the objective function or solution optimal knapsack problem. Finally, it shows the use of the algorithm for "approximate" of the targetsolution algorithm and experimentation backpack and results

Keywords: Simulated annealing, knapsack problem

Introducción.
En algoritmia, el problema de la mochila es un problema de optimización combinatoria. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos.Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo. El problema de la mochila es un problema de optimización combinatoria ya que trata de elegir la mejor combinación de una lista de objetos y a la vez que se optimice un objetivo este tipo de problemas se clasifica como un problema NP-Completo. Es posible resolverlo de forma exacta utilizando Branch &Bound pero como el tiempo en computación es exponencial tendríamos un tiempo considerablemente alto. Podemos tener buenas soluciones en un tiempo razonable utilizando alguna heurística. En este caso aplicaremos Recocido Simulado (SA: Simulated Annealing), el cual se describe a continuación. El recocido simulado es un algoritmo heurístico estocástico de aproximación a la solución óptima, fundado enuna analogía del comportamiento de sistemas termodinámicos simples, y viene siendo utilizado en ciertos problemas de ingeniería.

El algoritmo de recocido Simulado Funciona de la siguiente manera: Este algoritmo inicia con una solución inicial Valida, con un costo y Volumen asociado, después se genera una nueva solución, dicha solución se acepta si el nuevo costo mejora y la suma de sus pesos norebasa la capacidad de la mochila, de lo contrario se puede aceptar con cierta probabilidad y se penaliza el costo. La probabilidad de aceptar una solución que empeore la solución por el algoritmo de está dada por la distribución de Boltzmann P(aleatorio < e(nuevaS – actualS)/T ) Para temperaturas muy altas, observamos que e(nuevaS – actualS)/T tiende a ser 1, de lo contrario cuando tenemos bajastemperaturas la probabilidad de aceptar una solución que empeora nuestra función objetivo tiende a ser cero.

siguientes líneas abra dos columnas en al que la primera columna representa el peso del objeto y la segunda el costo del objeto el numero de filas será desde 1 hasta n objetos Al final el programa manda escribir la mejor solución con un formato de arreglo binario donde los unos denotanque el objeto que se encuentra en esa posición esta adentro de la Mochila en la siguiente línea se escribe el valor de la solución inicial y el valor de la mejor solución. El algoritmo de la mochila se construyo de la siguiente manera: Primeramente obtenemos el numero de objetos ya sea desde archivo o aleatoriamente y los almacenamos en dos arreglos arreglo costos y arreglo pesos del tamaño de...