Viajero ieee
Páginas: 6 (1490 palabras)
Publicado: 7 de noviembre de 2009
Algoritmos Genéticos y el Problema del Agente Viajero
Estudiante Ingeniería, jenjarfar @hotmail.com
RESUMEN: En el presente documento se expondrá el tema de los algoritmos genéticos y se demostrara como las técnicas utilizadas por la naturaleza para la evolución de los seres vivos, puedes ser aplicadas en la obtención de soluciones a problemas usuales con cierto grado de complejidad, de loscuales podríamos decir en cierto momento que son imposibles de resolver.
Abstract- The present paper will outline the issue of genetic algorithms and demonstrate the techniques used by nature for the evolution of living beings, can be applied in obtaining solutions to the usual problems with any degree of complexity, of which might say at some point that are impossible to solve.
PALABRASCLAVE- Algoritmos Genéticos, Técnicas utilizadas en la lógica desarrollada en el Programa.
I. INTRODUCCIÓN
Se plasmo el presente documento con la finalidad de comprobar que los algoritmos genéticos tienen un gran campo de aplicación y que su aporte en la evolución no solo es geneática, si no además puede ser tecnológica, contribuyendo al desarrollo de la inteligencia artificial, laoptimización de recurso y tiempo en procesos de fabricación.
El problema del agente viajero, radica en hallar la ruta en que un viajero debe transitar un numero de ciudades desde un punto de partida establecido, para que la distancia recorrida sea mínima, y no deberá repetir ciudad dentro del recorrido.
Los Algoritmos Genéticos usan una semejanza 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, este fundamento es el que permite que dicho algoritmo sea el de mejor aplicación a la hora de encontrar la solución optima de recorrido para el agente viajero. Ya que contamos con una serie de posibles soluciones (población), de las cuales solo una cumple con las condicionesnecesarias.
Por otra parte encontraremos en el presente documento una breve explicación de los fundamentos de los algoritmos génicos, para dilucidar su origen y la evolución con respecto a las aplicaciones que se han descubierto a través de los años.
La tercera parte se explicara la estructura lógica con la que cuenta el programa que se desarrollo en lenguaje C++, como apoyo a este documento, allíveremos como las
técnicas que utiliza la naturaleza para su evolución son aplicadas para encontrar la mejor ruta que deba tomar el agente viajero.
II. ALGORITMOS GENÉTICOS
Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico.
• Inicialización: Se genera aleatoriamente la población inicial, que estáconstituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema.
• Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.
• Condición de término El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce.Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación.
Cruzamiento: El cruzamiento es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
Mutación: modifica al azar partedel cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
Reemplazo: una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.
[pic]
Fig. 1 secuencia de un algoritmo genético.
II A. APLICACIÓN ALGORITMOS GENÉTICOS....
Estudiante Ingeniería, jenjarfar @hotmail.com
RESUMEN: En el presente documento se expondrá el tema de los algoritmos genéticos y se demostrara como las técnicas utilizadas por la naturaleza para la evolución de los seres vivos, puedes ser aplicadas en la obtención de soluciones a problemas usuales con cierto grado de complejidad, de loscuales podríamos decir en cierto momento que son imposibles de resolver.
Abstract- The present paper will outline the issue of genetic algorithms and demonstrate the techniques used by nature for the evolution of living beings, can be applied in obtaining solutions to the usual problems with any degree of complexity, of which might say at some point that are impossible to solve.
PALABRASCLAVE- Algoritmos Genéticos, Técnicas utilizadas en la lógica desarrollada en el Programa.
I. INTRODUCCIÓN
Se plasmo el presente documento con la finalidad de comprobar que los algoritmos genéticos tienen un gran campo de aplicación y que su aporte en la evolución no solo es geneática, si no además puede ser tecnológica, contribuyendo al desarrollo de la inteligencia artificial, laoptimización de recurso y tiempo en procesos de fabricación.
El problema del agente viajero, radica en hallar la ruta en que un viajero debe transitar un numero de ciudades desde un punto de partida establecido, para que la distancia recorrida sea mínima, y no deberá repetir ciudad dentro del recorrido.
Los Algoritmos Genéticos usan una semejanza 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, este fundamento es el que permite que dicho algoritmo sea el de mejor aplicación a la hora de encontrar la solución optima de recorrido para el agente viajero. Ya que contamos con una serie de posibles soluciones (población), de las cuales solo una cumple con las condicionesnecesarias.
Por otra parte encontraremos en el presente documento una breve explicación de los fundamentos de los algoritmos génicos, para dilucidar su origen y la evolución con respecto a las aplicaciones que se han descubierto a través de los años.
La tercera parte se explicara la estructura lógica con la que cuenta el programa que se desarrollo en lenguaje C++, como apoyo a este documento, allíveremos como las
técnicas que utiliza la naturaleza para su evolución son aplicadas para encontrar la mejor ruta que deba tomar el agente viajero.
II. ALGORITMOS GENÉTICOS
Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico.
• Inicialización: Se genera aleatoriamente la población inicial, que estáconstituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema.
• Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.
• Condición de término El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce.Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación.
Cruzamiento: El cruzamiento es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
Mutación: modifica al azar partedel cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
Reemplazo: una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.
[pic]
Fig. 1 secuencia de un algoritmo genético.
II A. APLICACIÓN ALGORITMOS GENÉTICOS....
Leer documento completo
Regístrate para leer el documento completo.