{"id":181145,"date":"2025-10-07T07:30:00","date_gmt":"2025-10-07T06:30:00","guid":{"rendered":"https:\/\/liora.io\/es\/?p=181145"},"modified":"2026-02-06T09:46:02","modified_gmt":"2026-02-06T08:46:02","slug":"optimizar-un-recorrido-turistico-con-un-algoritmo-genetico-caso-de-uso-en-el-morvan","status":"publish","type":"post","link":"https:\/\/liora.io\/es\/optimizar-un-recorrido-turistico-con-un-algoritmo-genetico-caso-de-uso-en-el-morvan","title":{"rendered":"Optimizar un recorrido tur\u00edstico con un algoritmo gen\u00e9tico: caso de uso en el Morvan"},"content":{"rendered":"<b>Como su nombre indica, los algoritmos de optimizaci\u00f3n tienen como objetivo encontrar una buena soluci\u00f3n (idealmente la mejor) a un problema, en funci\u00f3n de ciertos criterios u objetivos espec\u00edficos.<\/b>\n\n<b>Entre <a href=\"https:\/\/liora.io\/es\/que-es-un-algoritmo\">los muchos algoritmos<\/a> de optimizaci\u00f3n disponibles, algunos de ellos se inspiran en lo que ya existe en la naturaleza: son los algoritmos biomim\u00e9ticos. Pueden inspirarse en la inteligencia colectiva de los insectos (optimizaci\u00f3n por enjambre) o en los mecanismos de la selecci\u00f3n natural, como en los algoritmos de optimizaci\u00f3n gen\u00e9tica (tambi\u00e9n llamados evolucionistas).<\/b>\n\nLos <b>mecanismos de la selecci\u00f3n natural<\/b> (derivados notablemente de <b>la teor\u00eda de Darwin<\/b>) tienen como objetivo seleccionar a los individuos mejor adaptados para permitir que la especie mejore a lo largo de las generaciones.\n\nEn el caso de los <b>algoritmos gen\u00e9ticos<\/b>, los datos de nuestro problema se almacenan en forma de un vector que representa el genoma de los diferentes individuos. Se trata de constituir una poblaci\u00f3n inicial de individuos y luego <b>seleccionar los mejores<\/b>, generaci\u00f3n tras generaci\u00f3n. Esta selecci\u00f3n se realiza seg\u00fan criterios de puntuaci\u00f3n, los individuos mejor puntuados son seleccionados para la pr\u00f3xima generaci\u00f3n.\n\nPara ilustrar este art\u00edculo, tomar\u00e9 el ejemplo de un turista que desea pasar 10 d\u00edas en el parque natural regional del Morvan en Borgo\u00f1a. Quiere visitar las ciudades que ofrecen m\u00e1s puntos de inter\u00e9s hist\u00f3ricos recorriendo la menor cantidad de kil\u00f3metros. En los d\u00edas tres y ocho, quiere pasar la noche en un hotel de al menos 3 estrellas.\n\nExisten, por supuesto, librer\u00edas llave en mano m\u00e1s sofisticadas para utilizar estos algoritmos, pero el ejemplo de c\u00f3digo desarrollado aqu\u00ed permitir\u00e1 comprender los mecanismos b\u00e1sicos.\n\n<style><br \/>\n.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{color:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}<\/style>\n<h2>Los datos<\/h2>\nPara alimentar mis datos, recuper\u00e9 en OpenStreetMap los puntos de inter\u00e9s (POI) hist\u00f3ricos de cada municipio del parque. Los datos gubernamentales franceses me permitieron conocer la ubicaci\u00f3n de los hoteles de 3 estrellas o m\u00e1s, as\u00ed como las coordenadas geogr\u00e1ficas del centro de la ciudad con vistas a los c\u00e1lculos de distancia.\n\n<style><br \/>\n.elementor-widget-image{text-align:center}.elementor-widget-image a{display:inline-block}.elementor-widget-image a img[src$=\".svg\"]{width:48px}.elementor-widget-image img{vertical-align:middle;display:inline-block}<\/style>\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"774\" height=\"204\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image6.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image6.png 774w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image6-300x79.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image6-768x202.png 768w\" sizes=\"(max-width: 774px) 100vw, 774px\">\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center\"><div class=\"wp-block-button \"><a class=\"wp-block-button__link wp-element-button \" href=\"https:\/\/liora.io\/es\/formacion-data-scientist\">Aprender a utilizar Python<\/a><\/div><\/div>\n\n<h2>Constituci\u00f3n de la poblaci\u00f3n inicial<\/h2>\nSi quisi\u00e9ramos encontrar directamente la <b>soluci\u00f3n \u00f3ptima al problema<\/b>, deber\u00edamos considerar todas las combinaciones posibles y evaluar c\u00f3mo responden al problema. Desafortunadamente, las capacidades de c\u00e1lculo actuales no lo permiten para problemas algo complejos. Es por eso que hay que constituir una poblaci\u00f3n cuyo volumen sea lo suficientemente grande como para constituir una <b>muestra representativa<\/b>, pero no demasiado grande para no alargar excesivamente los tiempos de c\u00e1lculo. Un compromiso posible puede ser compensar una poblaci\u00f3n m\u00e1s peque\u00f1a aumentando el <b>n\u00famero de iteraciones<\/b> (o generaciones). Esta etapa implica cierta dosis de empirismo y se pueden intentar varias pruebas hasta llegar a un buen compromiso. He elegido una poblaci\u00f3n inicial de 1500 individuos.\n\nEn cuanto a las caracter\u00edsticas gen\u00e9ticas de cada individuo, la soluci\u00f3n es extremadamente simple: el genoma se constituye de manera aleatoria a partir de los diferentes valores.\n\nEn nuestro caso, utilizamos una funci\u00f3n de generaci\u00f3n de listas aleatorias a partir de los c\u00f3digos INSEE de los diferentes municipios del parque del Morvan.\n<h2>Evaluaci\u00f3n de los individuos<\/h2>\nUna vez constituida la primera generaci\u00f3n de la poblaci\u00f3n, cada individuo debe ser evaluado para que los mejores puedan ser seleccionados.\n\nAqu\u00ed, no hay una soluci\u00f3n general, cada problem\u00e1tica requiere su propio m\u00e9todo de evaluaci\u00f3n para la selecci\u00f3n de los mejores individuos. Una vez realizada la evaluaci\u00f3n, el proceso de selecci\u00f3n y constituci\u00f3n de las nuevas generaciones podr\u00e1 llevarse a cabo.\n\nEn mi caso, los dos criterios de puntuaci\u00f3n son la distancia total recorrida y el n\u00famero total de puntos de inter\u00e9s del recorrido. Para evitar tener recorridos con pocos kil\u00f3metros, pero sin muchos puntos de inter\u00e9s (o viceversa), he decidido agrupar por deciles los recorridos m\u00e1s eficientes tanto en t\u00e9rminos de kilometraje como de puntos de inter\u00e9s. As\u00ed, los recorridos puntuados con 2 pertenecen a ambos segundos deciles de estas dos categor\u00edas. Los recorridos puntuados con 10 agrupan, adem\u00e1s de sus deciles, todos los recorridos que no cumplen con este requisito de doble pertenencia a los deciles anteriores.\n\nComo el criterio relacionado con los alojamientos en hoteles necesariamente iba a cambiar en funci\u00f3n de las iteraciones, decid\u00ed no retenerlo como criterio puro de puntuaci\u00f3n pero lo utilizo como filtro en mis dataframes.\n\n<a href=\"https:\/\/liora.io\/es\/formacion-data-scientist\">\nCursos en Ciencia de Datos\n<\/a>\n<h2>Selecci\u00f3n y constituci\u00f3n de la pr\u00f3xima generaci\u00f3n<\/h2>\nEn este punto, se pueden seguir dos estrategias. <b>Elitismo o fusi\u00f3n<\/b>. En ambos casos, el objetivo es obtener una nueva generaci\u00f3n cuyo n\u00famero de individuos sea igual a la generaci\u00f3n anterior.\n\nEn el caso de <b>el elitismo<\/b>, la evaluaci\u00f3n se lleva a cabo primero, y luego los genomas de los individuos mejor puntuados se retoman directamente para la pr\u00f3xima generaci\u00f3n. El resto de la poblaci\u00f3n se completar\u00e1 con <b>individuos resultantes de cruces<\/b> (como ocurre con la reproducci\u00f3n sexual) o de mutaciones.\n\nEn el caso de la <b>fusi\u00f3n<\/b>, la nueva generaci\u00f3n (con el mismo n\u00famero de individuos que la anterior) se crea primero mediante cruces y mutaciones. La selecci\u00f3n se lleva a cabo posteriormente y solo <b>los individuos mejor evaluados son retenidos<\/b> en el n\u00famero de efectivos de la generaci\u00f3n anterior.\n\nEn el marco de mi proyecto, he optado por el sistema elitista siguiendo el viejo adagio seg\u00fan el cual no se cambia un equipo que gana. M\u00e1s seriamente, cada sistema presenta sus propias ventajas e inconvenientes. Si la fusi\u00f3n permite aumentar la diversidad gen\u00e9tica de los individuos, el elitismo permite preservar a los individuos mejor adaptados. Es esta cualidad la que me decidi\u00f3 a elegir el elitismo. Para la cohorte, he seleccionado al 20% de los mejores individuos de la poblaci\u00f3n como \u00e9lite para la selecci\u00f3n de la pr\u00f3xima generaci\u00f3n. Se acepta en general que la proporci\u00f3n de \u00e9lites puede estar entre el 5% y el 20%, yo he elegido el extremo alto de ese rango.\n<figure>\n\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"716\" height=\"409\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image5.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image5.png 716w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image5-300x171.png 300w\" sizes=\"(max-width: 716px) 100vw, 716px\"><figcaption>Elitisme vs fusion<\/figcaption><\/figure>\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center\"><div class=\"wp-block-button \"><a class=\"wp-block-button__link wp-element-button \" href=\"https:\/\/liora.io\/es\/formacion-data-analyst\">Curso en An\u00e1lisis de Datos<\/a><\/div><\/div>\n\n<h2>Cruce y mutaci\u00f3n<\/h2>\nEstos dos procesos naturales permiten la <b>creaci\u00f3n de nuevos individuos<\/b> cuyas <b>caracter\u00edsticas propias de su genoma<\/b> les permitir\u00e1n potencialmente estar mejor adaptados a su entorno. Al estar mejor adaptados, estos individuos tendr\u00e1n <b>m\u00e1s posibilidades de sobrevivir<\/b> y, por lo tanto, de reproducirse y transmitir sus genes.\n\nEn el caso de los algoritmos gen\u00e9ticos, la l\u00f3gica es similar. <b>Los individuos mejor evaluados son seleccionados para la generaci\u00f3n siguiente<\/b> y posteriormente tendr\u00e1n m\u00e1s probabilidades de transmitir sus caracter\u00edsticas.\n\nEl cruce consiste en retomar los mecanismos de la reproducci\u00f3n sexual. Los genes de los dos ascendientes se mezclan para constituir un nuevo genoma \u00fanico.\n\n<img decoding=\"async\" width=\"800\" height=\"305\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image2.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image2.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image2-300x114.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image2-768x293.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n\nEn algunos modelos, se propone mezclar los genomas parte por parte (mitad o en pares de genes). En mi caso, he privilegiado un enfoque similar al existente en la naturaleza, gen por gen.\n\nEn mi caso, la funci\u00f3n de cruce de los individuos viene acompa\u00f1ada de una peque\u00f1a dosis de mutaciones. En teor\u00eda, en un lugar dado, la selecci\u00f3n se realiza \u00fanicamente entre el gen de cada padre. Con este sistema, una misma ciudad podr\u00eda aparecer dos veces en el mismo recorrido, lo cual no es deseable. Por lo tanto, he implementado una restricci\u00f3n para evitar este fen\u00f3meno.\n\n<a href=\"https:\/\/liora.io\/es\/formacion-data-scientist\">\nDominar la ciencia de datos\n<\/a>\n\nEn la naturaleza, tambi\u00e9n existen <b>procesos de mutaci\u00f3n<\/b>. El genoma de un individuo se modificar\u00e1 independientemente de todo <b>proceso de reproducci\u00f3n<\/b>. Este mecanismo permite <b>aumentar la variabilidad gen\u00e9tica<\/b> provocando soluciones gen\u00e9ticas in\u00e9ditas.\n\n3 posibilidades de mutaciones pueden ocurrir.\n<h3>Inserci\u00f3n: un gen se desplaza para insertarse despu\u00e9s de otro<\/h3>\n<img decoding=\"async\" width=\"800\" height=\"307\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image7.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image7.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image7-300x115.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image7-768x295.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n<h3>P\u00e9rmutaci\u00f3n (o intercambio): dos genes permutan su lugar<\/h3>\n<img decoding=\"async\" width=\"800\" height=\"303\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image1.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image1.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image1-300x114.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image1-768x291.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n<h3>Inversi\u00f3n de secuencia: el orden de una parte del genoma se invierte<\/h3>\n<img decoding=\"async\" width=\"800\" height=\"312\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image3.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image3.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image3-300x117.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/7\/2025\/07\/image3-768x300.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n\nEl porcentaje de mutaciones suele representar el 5% de los nuevos individuos, pero he podido observar tasas de mutaciones de hasta el 10%. Dado que el <b>sistema elitista<\/b> tiende a reducir la variabilidad de los genomas, he elegido este valor del 10% como compensaci\u00f3n.\n\n<a href=\"https:\/\/liora.io\/es\/formacion-data-scientist\">\nAprenda todo sobre la ciencia de datos\n<\/a>\n<h2>Iteraci\u00f3n del proceso y soluci\u00f3n<\/h2>\nAl iterar <b>el proceso de selecci\u00f3n y constituci\u00f3n<\/b> de las nuevas generaciones, se obtendr\u00e1 progresivamente individuos cuyas caracter\u00edsticas permitir\u00e1n responder cada vez mejor al problema dado.\n\nLa pregunta que se plantea ahora es cu\u00e1ndo detener el proceso. Esto depende de nuestras restricciones.\n\nSi tenemos un tiempo limitado, podemos detener las iteraciones despu\u00e9s de un cierto tiempo de ejecuci\u00f3n. Tambi\u00e9n se puede intentar alcanzar un umbral correspondiente a un criterio (un n\u00famero de kil\u00f3metros ideal para nuestro trayecto, por ejemplo, o que cada ciudad visitada tenga un n\u00famero m\u00ednimo de puntos de inter\u00e9s). En modo experimental, se pueden lanzar iteraciones repetidamente y analizar el momento en que las iteraciones ya no aportan una <b>mejora significativa<\/b>. Luego, se fija un n\u00famero l\u00edmite de iteraciones.\n\nEn el marco de este ejercicio, para no tener tiempos de c\u00e1lculo excesivamente largos, me he conformado con 200 iteraciones.\n<h2>En conclusi\u00f3n<\/h2>\nComo en muchos \u00e1mbitos, la naturaleza una vez m\u00e1s es una gran fuente de inspiraci\u00f3n. Este ejemplo simple permite comprender c\u00f3mo se pueden <b>optimizar problemas complejos inspir\u00e1ndose en soluciones naturales<\/b> adoptadas desde hace cientos de millones de a\u00f1os.\n\nDespu\u00e9s de 200 iteraciones, obtuve el siguiente recorrido:\n\n<i>Glux-en-Glenne, Roussillon-en-Morvan, Alligny-en-Morvan, Anost, Quarr\u00e9-les-Tombes, Saint-L\u00e9ger-Vauban, Avallon, V\u00e9zelay, Bazoches, Pierre-Perthuis\u2026 <\/i>para un total de 154 km y un total de 115 puntos de inter\u00e9s en el recorrido.\n\nAl aumentar el n\u00famero de iteraciones podr\u00eda haber mejorado a\u00fan m\u00e1s la soluci\u00f3n, pero el objetivo de este script es m\u00e1s explicativo que de rendimiento. No quise alargar demasiado los tiempos de c\u00e1lculo para la ejecuci\u00f3n.\n\nPara tu informaci\u00f3n, el uso de <a href=\"https:\/\/liora.io\/es\/pandas-python\">dataframes Pandas<\/a> no es \u00f3ptimo en t\u00e9rminos de rendimiento, pero nuevamente, el objetivo principal de este script es ser explicativo.\n\n<a href=\"https:\/\/liora.io\/es\/nuestros-cursos-de-data\">\nIniciar la formaci\u00f3n en ciencia de datos\n<\/a>\n\nPuedes encontrar mi c\u00f3digo completo en mi <a href=\"https:\/\/github.com\/julio24048\/meileuritineraire\">repositorio de git<\/a>.","protected":false},"excerpt":{"rendered":"<p>Como su nombre indica, los algoritmos de optimizaci\u00f3n tienen como objetivo encontrar una buena soluci\u00f3n (idealmente la mejor) a un problema, en funci\u00f3n de ciertos criterios u objetivos espec\u00edficos. Entre los muchos algoritmos de optimizaci\u00f3n disponibles, algunos de ellos se inspiran en lo que ya existe en la naturaleza: son los algoritmos biomim\u00e9ticos. Pueden inspirarse [&hellip;]<\/p>\n","protected":false},"author":74,"featured_media":181147,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"_acf_changed":false,"editor_notices":[],"footnotes":""},"categories":[2440],"class_list":["post-181145","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-ia"],"acf":[],"_links":{"self":[{"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/posts\/181145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/users\/74"}],"replies":[{"embeddable":true,"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/comments?post=181145"}],"version-history":[{"count":5,"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/posts\/181145\/revisions"}],"predecessor-version":[{"id":183204,"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/posts\/181145\/revisions\/183204"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/media\/181147"}],"wp:attachment":[{"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/media?parent=181145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/liora.io\/es\/wp-json\/wp\/v2\/categories?post=181145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}