## travelling-salesman-problem## 1.0Implementation of a Genetic Algorithm to solve the Travelling Salesman Problem. ## dependencies
| (this space intentionally left almost blank) | |||||||||

## Travelling Salesman ProblemThis is an alternative implementation in Clojure of the Python tutorial in Evolution of a salesman: A complete genetic algorithm tutorial for Python. I also changed the selection progress to Roulette Selection as shown in Coding Challenge #35.4: Traveling Salesperson with Genetic Algorithm ## The travelling Salesman Problem asks the following question:"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" - Wikipedia This implementation uses a genetic algorithm to find the shortest route between a list of cities. ## Requirements- Neanderthal: math functions
- Clojure.java.io: write data to file
- Clojure.string: join all the data in a single string
| (ns travelling-salesman-problem.core (:gen-class) (:require [clojure.java.io :as io] [clojure.string :as str] [uncomplicate.neanderthal [math :refer [abs sqrt pow]]])) | |||||||||

## RecordsCreate a record for Cities and Individuals. This is the same as creating a class for each one. In Clojure it works as a simple map. | ||||||||||

The City is a point and has 3 keys, a | (defrecord City [name x y]) | |||||||||

The Individual represents the genomes in the Genetic Algorithm.
Each individual has a parent (except on the initial population)
and the The | (defrecord Individual [route total-distance fitness]) | |||||||||

## Utility Functions | ||||||||||

Check if the given directory path exists. | (defn dir? [path] (.isDirectory (java.io.File. path))) | |||||||||

Create a directory. | (defn mkdir [path] (.mkdirs (io/file path))) | |||||||||

If the path doesn't exist, create it. | (defn ensure-directory! [path] (when-not (dir? path) (mkdir path))) | |||||||||

Save the evolution data into a CSV file for statistics purposes. Example path: "./ga_output". | (defn save-historical-data [path file-name data] (ensure-directory! path) (let [d (str/join "\n" data)] (with-open [w (io/writer (str path "/" file-name) :append true)] (.write w d)))) | |||||||||

Calculate the distance between two cities. As the cities are just points, just calculate the distance
between two points with | (defn distance-between-cities [city-pair] (let [city-a (first city-pair) city-b (second city-pair) dist-x (abs (- (:x city-a) (:x city-b))) dist-y (abs (- (:y city-a) (:y city-b)))] (sqrt (+ (pow dist-x 2) (pow dist-y 2))))) | |||||||||

Distance between the first and second city: (distance-between-cities [(first cities) (second cities)]) => 10.04987562112089 | ||||||||||

Calculate the total distance of the route. | (defn total-distance [route] (let [city-pairs (mapv #(vector %1 %2) (butlast route) (rest route)) first-city (first route) last-city (last route) distances (map distance-between-cities city-pairs) ;; As city-pairs is a sequence of pairs from the first city to the last, ;; it misses the last pair which is last-city -> first-city. To make ;; this last calculation, calculate the distance between the last city ;; and the first to conclude the full circuit and sum it to the total. last-city-distance (distance-between-cities [last-city first-city])] (+ (reduce + distances) last-city-distance))) | |||||||||

Total distance of the cities-list: (total-distance cities) => 921.6346703083029 | ||||||||||

Calculate the fitness based on the route total distance. As distance decreases, fitness increases. 1 is the absolute best value. | (defn fitness [total-dist] (/ 1.0 (+ 1 (pow total-dist 8)))) | |||||||||

Fitness of the cities-list: (fitness (total-distance cities)) => 0.0010850286260015397 | ||||||||||

Normalize fitness based on the sum of fitness of the population. This makes each fitness value correspond to a probability. | (defn normalize-fitness [individual population] (let [fit (:fitness individual) fitness-sum (reduce + (map :fitness population))] (assoc-in individual [:fitness] (/ fit fitness-sum)))) | |||||||||

Generate a random route. | (defn generate-route [city-list] (shuffle city-list)) | |||||||||

Generate the initial population for the genetic algorithm with random routes. | (defn generate-initial-population [population-size cities-list] (repeatedly population-size (fn [] (let [route (generate-route cities-list) distance (total-distance route) fit (fitness distance)] (Individual. route distance fit))))) | |||||||||

Select a pair of parents from the population | (defn select-parents [population] (loop [pop population parent-pairs []] (if (empty? pop) parent-pairs (recur (drop 2 pop) (conj parent-pairs (take 2 pop)))))) | |||||||||

Combine the cities not present in the first route with the cities of the second route. | (defn combine-routes [first-route second-route] (let [fr-cities (set (map :name first-route))] (loop [sl second-route new-route first-route] (if (empty? sl) (do new-route) (let [city (first sl) is-present (contains? fr-cities (:name city))] (if is-present (recur (rest sl) new-route) (recur (rest sl) (conj new-route city)))))))) | |||||||||

## ElitismSelect the best performing individuals. | ||||||||||

With a random probability, pick the best individuals more often and the worse individuals less often. | (defn roulette-selection [population] (let [r (rand) pop (filter #(> (:fitness %) r) population)] (if (empty? pop) (rand-nth population) (rand-nth pop)))) | |||||||||

Select the population based on roulette selection. | (defn selection [population population-size] (loop [cnt 1 pop []] (if (> cnt population-size) pop (let [selected-individual (roulette-selection population)] (recur (inc cnt) (conj pop selected-individual)))))) | |||||||||

## CrossoverCombine a pair of individuals into a new one | ||||||||||

Generate a new individual based on 2 parents. Select a random number of genes of parent 1 and fill with genes from parent 2. | (defn crossover [parent-pair cities-list] (let [[parent-1 parent-2] parent-pair] (if parent-2 (let [route-1 (vec (take 10 (:route parent-1))) route-2 (:route parent-2) new-route (combine-routes route-1 route-2) distance (total-distance new-route) fit (fitness distance)] (Individual. new-route distance fit)) (let [route (generate-route cities-list) distance (total-distance route) fit (fitness distance) new-parent (Individual. route distance fit)] (crossover [parent-1 new-parent] cities-list))))) | |||||||||

Crossover the population to generate new individuals. | (defn crossover-population [population cities-list] (map #(crossover % cities-list) (select-parents population))) | |||||||||

## MutationChange the genes of an individual. | ||||||||||

Swap the order of two elements randomly for an individual given a probability. | (defn swap-cities [individual mutation-rate] (if (< (rand) mutation-rate) (let [i (:route individual) r1 (rand-int (count i)) r2 (rand-int (count i)) first-city (nth i r1) second-city (nth i r2) s1 (assoc i r1 second-city) s2 (assoc s1 r2 first-city) distance (total-distance s2) fit (fitness distance)] (Individual. s2 distance fit)) individual)) | |||||||||

Mutate each individual of a population. | (defn mutate-population [population cities-list mutation-rate] (map #(swap-cities % mutation-rate) population)) | |||||||||

## Genetic AlgorithmThe algorithms works as follows: - Start with a random initial-population - Normalize the fitness values - Start a new generation - Select the best individuals - Crossover the individuals - Mutate them - Loop | ||||||||||

Generate a new generation of a given population. A new generation is created based on selected individuals, which are crossed in pairs and then mutated. | (defn new-generation [population cities-list global-best population-size mutation-rate] (let [pop (conj population global-best) ; with this, new generations will ; not forget the best individual normalized-population (map #(normalize-fitness %1 pop) pop) selected-population (selection normalized-population (* 2 population-size)) crossed-population (crossover-population selected-population cities-list)] (mutate-population crossed-population cities-list mutation-rate))) | |||||||||

Run the genetic algorithm. | (defn genetic-algorithm [initial-population cities-list generations population-size mutation-rate print-progress] (loop [generation 1 population initial-population historical-best-distance [] historical-distance [] historical-fitness [] global-best (first population)] (let [current-generation (map #(normalize-fitness %1 population) population) ;; Dont use normalized fitness values to select the best performing ;; individual as it is a percentage of the current population ;; and does not reflect the global best value. sorted-gen (sort-by :fitness population) gen-best (last sorted-gen)] (if print-progress (println (str "Generation: " generation ", Best distance: " (:total-distance gen-best) ", Best fitness: " (:fitness gen-best)))) (if (= generation generations) {:population current-generation :historical-best-distance historical-best-distance :historical-distance historical-distance :historical-fitness historical-fitness :global-best global-best} (recur (inc generation) (new-generation current-generation cities-list global-best population-size mutation-rate) (conj historical-best-distance (:total-distance global-best)) (conj historical-distance (:total-distance gen-best)) (conj historical-fitness (:fitness gen-best)) (if (> (:fitness gen-best) (:fitness global-best)) gen-best global-best)))))) | |||||||||

## Variables | ||||||||||

Number of iterations | (def generations 10000) | |||||||||

Number of individuals in each generation | (def population-size 500) | |||||||||

Rate at which the cities in a route will be swapped | (def mutation-rate 0.1) | |||||||||

All the cities to find the route for. | (def cities [(City. "1" -100 0) (City. "2" 100 0) (City. "3" 0 100) (City. "4" 0 -100) (City. "5" -90 10) (City. "6" -80 20) (City. "7" -70 30) (City. "8" -60 40) (City. "9" -50 50) (City. "10" -40 60) (City. "11" -30 70) (City. "12" -20 80) (City. "13" -10 90) (City. "14" 10 90) (City. "15" 20 80) (City. "16" 30 70) (City. "17" 40 60) (City. "18" 50 50) (City. "19" 60 40) (City. "20" 70 30) (City. "21" 80 20) (City. "22" 90 10) (City. "23" 90 -10) (City. "24" 80 -20) (City. "25" 70 -30) (City. "26" 60 -40) (City. "27" 50 -50) (City. "28" 40 -60) (City. "29" 30 -70) (City. "30" 20 -80) (City. "31" 10 -90) (City. "32" -10 -90) (City. "33" -20 -80) (City. "34" -30 -70) (City. "35" -40 -60) (City. "36" -50 -50) (City. "37" -60 -40) (City. "38" -70 -30) (City. "39" -80 -20) (City. "40" -90 -10)]) | |||||||||

## Main Function | ||||||||||

Run the genetic algorithm, print the best results and save the evolution-data. | (defn -main [& args] (println "\nStart Genetic Algorithm") (let [initial-population (generate-initial-population population-size cities) ga (genetic-algorithm initial-population cities generations population-size mutation-rate true) best (:global-best ga)] (save-historical-data "./ga_output" "historical-best-distance.csv" (:historical-best-distance ga)) (save-historical-data "./ga_output" "historical-distance.csv" (:historical-distance ga)) (save-historical-data "./ga_output" "historical-fitness.csv" (:historical-fitness ga)) (println "Lowest Distance: " (:total-distance best)) (println "Best Route: " (map :name (:route best))) (println "Route size" (count (map :name (:route best)))) (println "Best Fitness: " (:fitness best)))) | |||||||||

Execute code in REPL: (-main) | ||||||||||