Articulo Problema De La Mochila

ABSTRACTS

En este artículo ofrece otra perspectiva sobre el algoritmo genético aplicado a la Inteligencia Artificial. Proporciona una descripción todo proceso de resolución y optimización del para problema mochila. A pesar de ser un problema relativamente simple, esta situación se presenta con cierta frecuencia en los ámbitos económico e industrial, donde la mochila suele representar la restricción presupuestaria y donde la utilidad de los objetos seleccionados se equipara a un beneficio económico por adquirir o llevar a cabo ciertas acciones. Para la experimentación y resultados de este algoritmo se ocupa dos problemas en base a los cuales se desarrollaran pruebas con el fin de demostrar cual es la mejor optimización, es decir cual es su mejor beneficio dependiendo a el tamaño de las generaciones que se le aplique a estos mismos.

Keywords : algoritmo genético, problema de la mochila

INTRODUCCION

PLANTEAMIENTO DEL PROBLEMA

El planteamiento del problema es aparentemente sencillo se disponen de N número de generaciones, y N número de tamaño de población, N número de probabilidad de cruza y N número de probabilidad de mutación. El objetivo final es que partiendo primer número de generaciones se obtenga en mejor beneficio no sobrepasando la capacidad.

Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos. Descendientes de los anteriores. Los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción.

De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras del espacio de búsqueda y la población convergerá hacia una solución óptima del problema.

MARCO TEORICO

Los Algoritmos Genéticos son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo delas generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y las supervivencia de los más fuertes, postulados por Darwin. Por imitación de es te proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación.

Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño. Una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos .

El problema de la mochila, comúnmente abreviado por KP es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. 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 uno de los 21 problemas NP-completos de Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972. Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en un artículo de George Mathews Ballard.

Si bien la formulación del problema es sencilla, su resolución es más compleja. Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un gran tamaño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación.

ESTADO DEL ARTE

Como es de sobra conocido, las metodologías asociadas a los conjuntos difusos se han apoyado prácticamente siempre en las que existían. Sin embargo esto no ha dado con los Sistemas Basados en Reglas,

Según J.L Verdegay y E.R. Vergara, el problema de la mochila consiste en llevar una mochila de forma que se optimice el valor de los objetos transportados, respetando una limitación de capacidad. Este problema es NP-completo, es decir, que no se conoce un algoritmo polinomial, que obtenga su solución óptima. En estas circunstancias, el uso de los algoritmos aproximados, o heurísticas, es muy interesante porque permiten obtener soluciones que si bien no son óptimas, si están cercanas a ellas. De cara a su solución, también es una alternativa, tato para

...