Hey everyone, I’ve written my first major algorithm in Julia which uses a Genetic Algorithm approach to finding a solution to the Travelling Salesman Problem.
It works fine but next week I will be pitching it aginst other algorithms to see who gets the best solution. Most guys are using existing libraries for GAMS or Python. I’ll be the only representing Julia in the competition.
Because of this competition of course I want to increase the performance. I have followed the suggsted steps in the Performance Tips page and have tried to follow conventions on organizing code.
My code runs comparably lighting-fast when compared to other Optimization software and algorithms. However my Memory allocation is huge
8.789115 seconds (26.65 M allocations: 7.826 GiB, 25.07% gc time)
Can some of you guys with a lot more experience take a quick look and let me know what you think can be done?
This is the output for --track-allocation=user , hope you can take a quick look and let me know what would you do to fix this.
Thanks
- using Random, CSV
- const file = "21_Points.csv"
-
- const pop_size = 20000
- const elites = 200
- const survivors = 9900
- const mutts = 2000
-
- const gens = 2
-
- function generate_distance_matrix(file = "21_Points.csv")
- #Importar datos de Excel
- nodes_import = CSV.read(file, header = true)
-
0 #Definir que hay en cada columna del excel y cuantos nodos hay en total
- num_nodes = size(nodes_import,1)
- idcol = 1
0 Xcol = 2
- Ycol = 3
-
- #Generar la Matriz de distancias a partir del numero de nodos
- distance_matrix = Array{Float64}(undef, (num_nodes, num_nodes))
- #Llenar la matriz de distancias entre todos los puntos usando Pitagoras
0 for n in 1:num_nodes
- for s in 1:num_nodes
0 distance_matrix[n,s] = sqrt((nodes_import[n,Ycol] - nodes_import[s,Ycol])^2 +
0 (nodes_import[n,Xcol] - nodes_import[s,Xcol])^2)
0 end
- end
- #println(pretty_table(nodes_import))
- #println(pretty_table(distance_matrix))
- return distance_matrix
- end
0
- const distance_matrix = generate_distance_matrix("21_Points.csv")
- const num_nodes = size(distance_matrix, 1)
-
- function fitness_function(sequence)
- arcs::Array{Bool,2} = zeros(Bool, num_nodes, num_nodes)
- i = sequence[1]
323299200 for s in 2:length(sequence)
0 j = sequence[s]
0 arcs[i,j] = 1
0 i = j
0 end
0 arcs[i,sequence[1]] = 1
- return sum(arcs.*distance_matrix)
0 end
2206041600
- struct Individual
- generation::Int
- genes::Vector{Int}
- fitness_score::Float64
- end
- Individual(gen, genes) = Individual(gen, genes, fitness_function(genes))
-
- function init_poulation(pop_size)
- population = Array{Individual}(undef,0)
- for i in 1:pop_size
80 push!(population, Individual(1,randperm(num_nodes)))
0 end
6924928 return population
- end
0
- function new_generation!(population, mating_pool, gen)
-
- for p in 1:survivors
- parent1 = mating_pool[p]
0 parent2 = mating_pool[rand(1:survivors)]
0
0 children = Array{Individual,1}(undef, 2)
- cross_parents!(children, parent1.genes, parent2.genes, gen)
18057600
0 population[elites+p] = children[1]
- population[elites+survivors+p] = children[2]
0 end
0
- for m in 1:(mutts÷2)
- mutt_1 = population[rand(elites:pop_size)]
0 mutt_2 = population[rand(elites:pop_size)]
0 mutate_type1!(mutt_1)
0 mutate_type2!(mutt_2)
0 end
0 end
-
- function cross_parents!(children, parent1_genes, parent2_genes, gen)
-
- cross_point = rand(1:num_nodes-1)
- child1_genes = parent1_genes[1:cross_point]
0 child2_genes = parent2_genes[1:cross_point]
35441328
35441328 parent1_left = parent1_genes[cross_point+1:end]
- parent2_left = parent2_genes[cross_point+1:end]
35342624
35342624 ch1_pending = Array{Tuple{Int64,Int64}}(undef,0)
- foreach(l -> push!(ch1_pending,
15048000 (l, findfirst(isequal(l), parent2_genes))),
193167360 parent1_left)
- sort!(ch1_pending, by = e -> e[:][2])
- foreach(p -> push!(child1_genes, p[1]), ch1_pending)
21243648
84618992 ch2_pending = Array{Tuple{Int64,Int64}}(undef,0)
- foreach(l -> push!(ch2_pending,
15048000 (l, findfirst(isequal(l), parent1_genes))),
193167360 parent2_left)
- sort!(ch2_pending, by = e -> e[:][2])
- foreach(p -> push!(child2_genes, p[1]), ch2_pending)
21243648
84618992 children[1] = Individual(gen,child1_genes)
- children[2] = Individual(gen,child2_genes)
6019200 end
6019200
- function mutate_type1!(mutt_1::Individual)
- mutt_gene = rand(1:num_nodes-1)
- i = findfirst(isequal(mutt_gene), mutt_1.genes)
0 j = findfirst(isequal(mutt_gene+1), mutt_1.genes)
0 mutt_1.genes[i] = mutt_gene+1
0 mutt_1.genes[j] = mutt_gene
0 end
0
- function mutate_type2!(mutt_2::Individual)
- mutt_gene = rand(1:num_nodes-2)
- i = findfirst(isequal(mutt_gene), mutt_2.genes)
0 j = findfirst(isequal(mutt_gene+2), mutt_2.genes)
0 mutt_2.genes[i] = mutt_gene+2
0 mutt_2.genes[j] = mutt_gene
0 end
0
- function GA()
- population = init_poulation(pop_size)
- mating_pool = Array{Individual}(undef, survivors)
2848
79312 for g = 2:gens
-
0 sort!(population, by = p -> p.fitness_score)
- mating_pool = population[1:survivors]
1522736
1506928 new_generation!(population, mating_pool, g)
-
0 if (population[1].fitness_score == population[elites].fitness_score) || ((g - population[1].generation) > 6)
- print("Convergencia en la GEN")
0 println(gens)
0 break
0 end
- println(g)
- end
3680
- sort!(population, by = p -> p.fitness_score)
- return population[1]
80144 end
0
- @time winner = GA()
- print(winner)
-