{"id":198108,"date":"2025-10-10T06:08:00","date_gmt":"2025-10-10T05:08:00","guid":{"rendered":"https:\/\/liora.io\/en\/?p=198108"},"modified":"2026-02-06T07:41:28","modified_gmt":"2026-02-06T06:41:28","slug":"all-about-genetic-algorithms","status":"publish","type":"post","link":"https:\/\/liora.io\/en\/all-about-genetic-algorithms","title":{"rendered":"Optimizing a tourist route with a genetic algorithm: use case in the Morvan"},"content":{"rendered":"<b>As their name suggests, optimization algorithms are designed to find an optimal (or ideally the best) solution to a problem, according to specific criteria or objectives.<\/b>\n\n<b>Among <a href=\"https:\/\/liora.io\/en\/boosting-business-with-3-essential-machine-learning-algorithms\">the many optimization algorithms available<\/a>, some are inspired by nature: these are known as biomimetic algorithms. They may draw from the collective intelligence of insects (swarm optimization) or the principles of natural selection, as seen in genetic optimization algorithms (also referred to as evolutionary algorithms).<\/b>\n\nThe <b>principles of natural selection<\/b>, which primarily derive from <b>Darwin&#8217;s theory<\/b>, focus on selecting the most well-adapted individuals, enabling species to evolve over generations.\n\nIn the realm of <b>genetic algorithms<\/b>, the data for our problem are organized in the form of a vector that represents the genome of different individuals. The aim is to create an initial population of individuals and then <b>select the best ones<\/b>, generation after generation. This selection is based on rating criteria, with the highest-rated individuals chosen for the next generation.\n\nTo illustrate this article, consider the example of a vacationer planning to spend 10 days in the Morvan Regional Natural Park in Burgundy. The goal is to visit cities boasting the most historical points of interest while covering the fewest kilometers. On the third and eighth days, accommodations must include a hotel with at least a 3-star rating.\n\nThere are certainly more sophisticated turnkey libraries available to implement these algorithms, but the code example developed here will help clarify their basic mechanisms.\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>The Data<\/h2>\nFor data collection, I sourced historical points of interest (POIs) for each town in the park from OpenStreetMap. Information from the French government provided the locations of 3-star or better hotels and the geographical coordinates of town centers for calculating distances.\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\/9\/2025\/07\/image6.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image6.png 774w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image6-300x79.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/9\/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=\"\/en\/courses\/data-ai\/data-scientist\">Learn to use Python<\/a><\/div><\/div>\n\n<h2>Creating the Initial Population<\/h2>\nIf our goal were to directly find the <b>optimal solution to the problem<\/b>, it would involve evaluating all possible combinations and assessing their effectiveness in solving the problem. Unfortunately, current computational capabilities don&#8217;t allow for this with complex problems. Hence, we need to form a population large enough to be a <b>representative sample<\/b>, yet not so large as to excessively prolong computation times. A potential compromise could be a smaller population size in exchange for increasing the <b>number of iterations<\/b> (or generations). This step involves some experimentation, and multiple tries may be necessary to find a satisfactory compromise. I opted for an initial population of 1500 individuals.\n\nRegarding each individual&#8217;s genetic traits, the solution is straightforward: the genome is randomly generated from various values.\n\nIn our scenario, a function generates random lists based on the INSEE codes of the various municipalities in the Morvan park.\n<h2>Evaluating Individuals<\/h2>\nOnce the first generation of the population is established, each individual must be evaluated to select the best ones.\n\nHere, no one-size-fits-all solution exists; each problem requires its own evaluation strategy to identify the top performers. Once evaluation is complete, the process of selecting and forming new generations begins.\n\nIn my case, the two evaluation criteria are the total distance traveled and the total number of points of interest on the route. To avoid routes with few kilometers but lacking points of interest (or the reverse), I chose to group the most efficient routes in terms of both mileage and points of interest by decile. Thus, routes rated 2 belong simultaneously to the second deciles of these two categories. Routes rated 10 include, beyond their deciles, all routes not meeting this dual decile requirement.\n\nAs the accommodation criterion inevitably changes with iterations, I decided not to include it as a pure rating criterion but rather use it as a filter within my data frames.\n\n<a href=\"\/en\/courses\/data-ai\/data-scientist\">\nTraining in Data Science\n<\/a>\n<h2>Selection and Creation of the Next Generation<\/h2>\nAt this stage, two strategies are available: <b>Elitism or fusion<\/b>. In both scenarios, the aim is to develop a new generation that matches the previous generation in terms of the number of individuals.\n\nWith <b>elitism<\/b>, evaluation occurs first, and the genomes of the most highly-rated individuals are directly reused for the subsequent generation. The remainder of the population is filled with <b>individuals generated through crossover<\/b> (as in sexual reproduction) or mutations.\n\nIn <b>fusion<\/b>, the new generation (equivalent in number to the previous one) is created first via crossover and mutations. Selection is then applied to retain only <b>the highest evaluated individuals<\/b> up to the previous generation&#8217;s numbers.\n\nFor my project, I chose the elitist system, adhering to the old saying that you don&#8217;t change a winning team. More seriously, each system offers its own pros and cons. While fusion can expand genetic diversity among individuals, elitism can preserve the best-adapted individuals. This quality persuaded me to choose elitism. For the cohort, I selected 20% of the best individuals in the population as the elite to guide the next generation. Generally, the proportion of elites ranges between 5% and 20%; I opted for the higher range.\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\/9\/2025\/07\/image5.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image5.png 716w, https:\/\/liora.io\/app\/uploads\/sites\/9\/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=\"\/en\/courses\/data-ai\/data-analyst\">Training in Data Analysis<\/a><\/div><\/div>\n\n<h2>Crossover and Mutation<\/h2>\nThese natural processes enable the <b>creation of new individuals<\/b> whose <b>distinctive genome traits<\/b> might better adapt them to their environment. Being better adapted, these individuals will have <b>a higher probability of survival<\/b>, hence reproduce and pass on their genes.\n\nIn genetic algorithms, the concept is similar. <b>The top-evaluated individuals are selected for the subsequent generation<\/b> and in turn have a greater chance of propagating their traits.\n\nCrossover recreates the mechanics of sexual reproduction. Genes from both parents are blended to form a new, unique genome.\n\n<img decoding=\"async\" width=\"800\" height=\"305\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image2.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image2.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image2-300x114.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image2-768x293.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n\nIn some models, the suggestion is to combine genomes segment by segment (by halves or gene pairs). For my approach, I favored a method more akin to nature, handling it gene by gene.\n\nIn my setup, the crossover function for individuals is combined with a small degree of mutation. Theoretically, at any point, selection happens only between the genes of each parent. With this system, the same city could end up appearing twice in the same route, which is undesirable. Therefore, I added a restriction to prevent this scenario.\n\n<a href=\"\/en\/courses\/data-ai\/data-scientist\">\nMastering data science\n<\/a>\n\nIn nature, there are also <b>mutation processes<\/b> where an individual&#8217;s genome changes independently of any <b>reproductive process<\/b>. This mechanism enhances <b>genetic diversity<\/b> by introducing novel genetic solutions.\n\nThree mutation possibilities may occur.\n<h3>Insertion: a gene moves to insert after another<\/h3>\n<img decoding=\"async\" width=\"800\" height=\"307\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image7.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image7.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image7-300x115.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image7-768x295.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n<h3>Permutation (or swap): two genes exchange their positions<\/h3>\n<img decoding=\"async\" width=\"800\" height=\"303\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image1.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image1.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image1-300x114.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image1-768x291.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n<h3>Sequence inversion: the order of part of the genome is reversed<\/h3>\n<img decoding=\"async\" width=\"800\" height=\"312\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image3.png\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image3.png 800w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image3-300x117.png 300w, https:\/\/liora.io\/app\/uploads\/sites\/9\/2025\/07\/image3-768x300.png 768w\" sizes=\"(max-width: 800px) 100vw, 800px\">\n\nThe percentage of mutations typically comprises 5% of new individuals, though I have observed mutation rates reach up to 10%. Since the <b>elitist system<\/b> tends to diminish genetic diversity, I maintained this 10% figure as a form of balance.\n\n<a href=\"\/en\/courses\/data-ai\/\">\nLearn all about data science\n<\/a>\n<h2>Iteration of the Process and Solution<\/h2>\nBy repeating <b>the process of selecting and building new generations<\/b>, we gradually produce individuals whose attributes are increasingly better suited to resolving the problem at hand.\n\nThe dilemma arises as to when the process should be halted. This depends on our constraints.\n\nIf time is limited, iterations can be stopped after a set duration. Alternatively, we might aim to attain a threshold tied to a criterion (an optimal distance for our journey, for instance, or ensuring each city visited has a minimum number of points of interest). In a trial mode, iterations can be conducted repeatedly, analyzing when iterations no longer yield <b>significant improvement<\/b>. A cap on the number of iterations can then be defined.\n\nFor this exercise, to avoid overly long computation times, I settled on 200 iterations.\n<h2>Conclusion<\/h2>\nAs with many areas, nature once again proves to be a rich source of inspiration. This straightforward example illustrates how <b>complex issues can be optimized by drawing insights from natural solutions<\/b> that have evolved over hundreds of millions of years.\n\nUltimately, after 200 iterations, I established the following itinerary:\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>totaling 154 km and incorporating 115 points of interest along the way.\n\nBy increasing the number of iterations, I could have further refined the solution, but the primary aim of this script is more educational rather than performance-driven. I aimed to avoid excessively extending the computational execution times.\n\nFor reference, utilizing <a href=\"https:\/\/liora.io\/en\/pandas-the-python-library\">Pandas dataframes<\/a> isn&#8217;t optimal for performance, but again, the core objective of this script is explanatory.\n\n<a href=\"\/en\/courses\/data-ai\/\">\nStart your data science training\n<\/a>\n\nYou can view my complete code on my <a href=\"https:\/\/github.com\/julio24048\/meileuritineraire\">Git repo<\/a>.","protected":false},"excerpt":{"rendered":"<p>As their name suggests, optimization algorithms are designed to find an optimal (or ideally the best) solution to a problem, according to specific criteria or objectives. Among the many optimization algorithms available, some are inspired by nature: these are known as biomimetic algorithms. They may draw from the collective intelligence of insects (swarm optimization) or [&hellip;]<\/p>\n","protected":false},"author":78,"featured_media":198110,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"_acf_changed":false,"editor_notices":[],"footnotes":""},"categories":[2433],"class_list":["post-198108","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-ai"],"acf":[],"_links":{"self":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/198108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/comments?post=198108"}],"version-history":[{"count":5,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/198108\/revisions"}],"predecessor-version":[{"id":205509,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/posts\/198108\/revisions\/205509"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/media\/198110"}],"wp:attachment":[{"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/media?parent=198108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/liora.io\/en\/wp-json\/wp\/v2\/categories?post=198108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}