Type assertion might narrow the types. Because compare is only meaningful between Int, so we can narrow type to Int before comparing. This might be better than invoke <(::Union{Nothing,Int},Union{Nothing,Int}).
Edit: compiler is good at optimizing, I guess compiler can do union splitting on this case, so adding type assertion might not be quite useful here.
Follwing your suggested approach for the cross_parents function did indeed reduced memory allocation to about half but doubled run time. That is why I decided to stick to existing approach.
After follwing most tips performance is amazing 0.926318 seconds (3.88 M allocations: 485.378 MiB, 10.53% gc time)
Here is the most up to date code:
- using Random, CSV, DataFrames
- const file = "21_Points.csv"
-
- const pop_size = 20000
- const elites = 200
- const survivors = 9900
- const mutts = 5000
- const gens = 50
-
- function generate_distance_matrix(file = "21_Points.csv")
- #Importar datos de Excel
0 nodes_import = CSV.read(file, header = true)
-
- #Definir que hay en cada columna del excel y cuantos nodos hay en total
0 num_nodes = size(nodes_import,1)
- idcol = 1
- Xcol = 2
- Ycol = 3
-
- #Generar la Matriz de distancias a partir del numero de nodos
0 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
0 for s in 1:num_nodes
0 distance_matrix[n,s] = sqrt((nodes_import[n,Ycol] - nodes_import[s,Ycol])^2 +
- (nodes_import[n,Xcol] - nodes_import[s,Xcol])^2)
- end
- end
- #println(pretty_table(nodes_import))
- #println(pretty_table(distance_matrix))
0 return distance_matrix
- end
-
- const distance_matrix = generate_distance_matrix("21_Points.csv")
- const num_nodes = size(distance_matrix, 1)
-
- function fitness_function(path)
- return distance_matrix[path[end],path[1]] +
- sum(distance_matrix[path[i-1],path[i]] for i = 2:num_nodes)
- end
-
- 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)
160080 population = Vector{Individual}(undef,pop_size)
0 for i in 1:pop_size
6080000 population[i] = Individual(1,randperm(num_nodes))
- end
0 return population
- end
-
- function new_generation!(population, mating_pool, gen)
-
0 for p in 1:survivors
0 parent1 = mating_pool[p]
0 parent2 = mating_pool[rand(1:survivors)]
-
0 for (c,I) in enumerate(cross_parents(parent1.genes, parent2.genes, gen))
0 if c == 1
0 population[elites+p] = I
0 elseif c == 2
0 population[elites+survivors+p] = I
- else
0 print("Error")
- end
- end
- end
-
0 for m in 1:(mutts÷2)
0 mutt_1 = population[rand(10:pop_size)]
0 mutt_2 = population[rand(10:pop_size)]
0 mutate_type1!(mutt_1)
0 mutate_type2!(mutt_2)
- end
- end
-
- function cross_parents(parent1_genes, parent2_genes, gen)
-
0 cross_point = rand(1:num_nodes-1)
-
131947200 ch1_genes = similar(parent1_genes)
131947200 ch2_genes = similar(parent2_genes)
23284800 ch1_genes[1:cross_point] = @view parent1_genes[1:cross_point]
23284800 ch2_genes[1:cross_point] = @view parent2_genes[1:cross_point]
0 parent1_left = @view parent1_genes[cross_point+1:end]
0 parent2_left = @view parent2_genes[cross_point+1:end]
-
130339920 ch1_pending = similar(parent1_left, Tuple{Int, Int})
130339920 ch2_pending = similar(parent2_left, Tuple{Int, Int})
-
-
0 for (index, value) in enumerate(parent1_left)
0 ch1_pending[index] = (value, findfirst(isequal(value), parent2_genes)::Int64)
- end
43035072 sort!(ch1_pending, by = last)
0 for (index, (value, _)) in enumerate(ch1_pending)
0 ch1_genes[cross_point+index] = value
- end
-
0 for (i, v) in enumerate(parent2_left)
0 ch2_pending[i] = (v, findfirst(isequal(v), parent1_genes)::Int64)
- end
43035072 sort!(ch2_pending, by = last)
0 for (i,(v, _)) in enumerate(ch2_pending)
0 ch2_genes[cross_point+i] = v
- end
-
46569600 return (Individual(gen,ch1_genes), Individual(gen,ch2_genes))
- end
-
- function mutate_type1!(mutt_1::Individual)
0 mutt_gene = rand(1:num_nodes-1)
0 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
- end
-
- function mutate_type2!(mutt_2::Individual)
0 mutt_gene = rand(1:num_nodes-2)
0 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
- end
-
- function GA()
2560 population = init_poulation(pop_size)
79312 mating_pool = Array{Individual}(undef, survivors)
-
0 for g = 2:gens
-
0 partialsort!(population, survivors, by = p -> p.fitness_score)
2352 mating_pool = @view population[1:survivors]
-
0 new_generation!(population, mating_pool, g)
-
0 if (population[1].fitness_score == population[elites].fitness_score) || ((g - population[1].generation) > 6)
0 print("Convergencia en la GEN")
0 println(g)
0 print("TODOS ELITES IGUALES")
- break
- end
0 if ((g - population[1].generation) > gens/5)
0 print("Convergencia en la GEN")
0 println(g)
0 print("SIN CAMBIOS en x GENS x = ")
0 println(gens/5)
- break
- end
9968 println(g)
- end
-
80144 sort!(population, by = p -> p.fitness_score)
0 return population[1]
- end
-
0 @time winner = GA()
- print(winner)
-
Huh, that’s very surprising to me 
Is the CSV file you’re using publicly available? I’d like to play around with it a little, if that’s possible.
This are the points I was using (they are actually 23 
haha) They are random coordinates between 1 and 100.
ID,X coordinate,Y coordiante
1,64,74
2,53,63
3,53,20
4,98,53
5,90,97
6,43,44
7,48,46
8,87,55
9,58,45
10,40,82
11,43,13
12,23,74
13,12,80
14,65,7
15,64,99
16,11,74
17,55,98
18,65,99
19,92,17
20,96,11
21,67,68
22,24,79
23,17,32
1 Like
Additionally, Julia arrays are column-major, so iterating the first dimension should take place in the innermost loop:
for s in 1:num_nodes
for n in 1:num_nodes
distance_matrix[n,s] = sqrt((nodes_import[n,Ycol] - nodes_import[s,Ycol])^2 +
(nodes_import[n,Xcol] - nodes_import[s,Xcol])^2)
end
end
4 Likes