I recently read an excellent post on genetic algorithms in python, which answered a lot of questions that I had about the method. I recommend reading this post, what I will do here is translate the examples into julia, and augment them,

Let me quote from the article: “The Genetic Algorithm is a stochastic global search optimization algorithm. The algorithm uses analogs of a genetic representation (bitstrings), fitness (function evaluations), genetic recombination (crossover of bitstrings), and mutation (flipping bits).”

Therefore if you intend to use the algorithm, you must translate your data into 0-1 vectors, which I will do using ordinary vectors of Int64 types in julia. Furthermore, from the article:

“The algorithm works by first creating a population of a fixed size of random bitstrings. The main loop of the algorithm is repeated for a fixed number of iterations or until no further improvement is seen in the best solution over a given number of iterations.”

“One iteration of the algorithm is like an evolutionary generation…First, the population of bitstrings (candidate solutions) are evaluated using the objective function. The objective function evaluation for each candidate solution is taken as the fitness of the solution, which may be minimized or maximized…Then, parents are selected based on their fitness. A given candidate solution may be used as parent zero or more times. A simple and effective approach to selection involves drawing k candidates from the population randomly and selecting the member from the group with the best fitness. This is called tournament selection where k is a hyperparameter and set to a value such as 3. This simple approach simulates a more costly fitness-proportionate selection scheme,…Parents are used as the basis for generating the next generation of candidate points and one parent for each position in the population is required,…Parents are then taken in pairs and used to create two children. Recombination is performed using a crossover operator. This involves selecting a random split point on the bit string, then creating a child with the bits up to the split point from the first parent and from the split point to the end of the string from the second parent. This process is then inverted for the second child.”

Got that? It is an excellent description. We have three basic operations, selection of pairs of parents from the population, which is basically random with a bias towards fitness, then breeding/crossover to create a pair of successors each of which has traits of the parents, then mutation.

“For example the two parents : parent1 = 00000 and parent2 = 11111, may result in two cross-over children: child1 = 00011 and child2 = 11100…Crossover is applied probabilistically for each pair of parents, meaning that in some cases, copies of the parents are taken as the children instead of the recombination operator. Crossover is controlled by a hyperparameter set to a large value, such as 80 percent or 90 percent…Crossover is the Genetic Algorithms distinguishing feature. It involves mixing and matching parts of two parents to form children…”

The sets of children will completely replace the population of parents at each iteraction/generation, but we stochastically allow for mutations too:

“Mutation involves flipping bits in created children candidate solutions. Typically, the mutation rate is set to 1/L, where L is the length of the bitstring… Each bit in a binary-valued chromosome typically has a small probability of being flipped. For a chromosome with m bits, this mutation rate is typically set to 1/m, yielding an average of one mutation per child chromosome.”

This is the gist of the article, which I urge you to read. What I will list below is my julia code that corresponds to the author’s python code. I introduce a lot of julian idiomatic code substitutions but try to retain as much of the original python flow. The first example will optimize the negative sum of all of the bits in the data vectors, which the author calls “onemax”.

Using DataFrames,Printf
# Globals
niter=100
nlens=20
npop=100
rcross=0.9
rmut=1.0/nlens

onemax=function(x)
return -sum(x)
end

selection=function(pop,scores,k=3)
selectionidx = rand(1:npop)
for idx in  rand(1:npop,k-1)
 if scores[idx] < scores[selectionidx]
    selectionidx = idx
end
end
return pop[:,selectionidx]
end

crossover=function(p1,p2,rcross)
c1=copy(p1)
c2=copy(p2)
if rand() < rcross
pt = rand(2:length(p1)-1)
c1 = vcat(p1[begin:pt] , p2[pt+1:end])
c2 = vcat(p2[begin:pt] , p1[pt+1:end])
end
return [c1, c2]
end

mutation=function(x,rmut)
for j in 1:length(x)
if rand()< rmut
x[j]=1-x[j]
end
end
end

dif=function(x,y)
tally=0
for i in 1: length(x)
if x[i] != y[i]
tally=tally+1
end
end
return tally
end

geneticopt=function(objective, nlens, niter, npop, rcross, rmut)
# create a population of random candidates
pop=rand(0:1, nlens, npop)
convert(DataFrame,pop)
# initialize search for fittest candidate
best=1
best_eval=objective(pop[:,1])
for gen in 1:niter
  # score all objects in the population
  scores = [objective(pop[:,c]) for c in 1:npop]
  # current best candidate
  for i in 1:npop
      if scores[i] < best_eval
	best=pop[:,i]
        best_eval=scores[i]
      end
   end
   print("gen=",gen,", ","objective(",best',")=", best_eval,"\n")
 # Darwinian evolution towards most fit candidate
  selected = [selection(pop, scores) for j in 1:npop]
  children = DataFrame(Int64.(zeros(nlens,npop)))
  for j in 1:2:npop
    p1=selected[j]
    p2=selected[j+1]
    c=crossover(p1,p2,rcross)
    mutation(c[1],rmut)
    mutation(c[2],rmut)
    children[:,j]=c[1]
    children[:,j+1]=c[2]
   end
   pop=children
end

return best, best_eval
end

If you run this, you will get precisely the output illustrated in the original article, which you must read if you want to see the results of the algorithm.

The second example minimizes f(x,y)=x^2+y^2. both x,y are one the interval [-L,L] and so we will translate x,y into 16-bit formats, which will be little-endian vectors of zeros and ones, and concatenate them into a single 32-dimensional vector. Therefore we can use the codes above with minor modifications if we add encode/decode functions to translate float64 (x,y) into such a bit-vector, and back again.

"""converts an dim*nbit bit array into a dim decimal array in [-L,L]"""
decode=function(bin_rep,dim,nbits,L)
br=[bin_rep[1+i*nbits:(i+1)*nbits] for i in 0:dim-1]
br=bitarr_to_int.(reverse.(br))
return [-L+2*L*br[j]/2^nbits for j in 1:dim]
end

"""converts a dim decimal array in [-L,L] to an dim*nbit bit array"""
encode=function(dec_rep,dim, nbits,L)
drr=[Int.((dec_rep[j] .+L)*(2^nbits)/(2*L))  for j in 1:dim]
drrr=[digits(drr[j],base=2,pad=nbits) for j in 1:dim]
retval=[]
for j in 1:dim
retval=vcat(retval,drrr[j])
end
return retval
end


geneticopt2=function(objective, dim, nbits, L, niter, npop, rcross, rmut)
# create a population of random candidates
pop=rand(0:1, dim*nbits, npop)
convert(DataFrame,pop)
# initialize search for fittest candidate
best=1
best_eval=objective(decode(pop[:,1],dim,nbits,L))
for gen in 1:niter
  # score all objects in the population
  dec=[decode(pop[:,j],dim,nbits,L) for j in 1:npop]
  scores = [objective(dec[c]) for c in 1:npop]
  # current best candidate
  for i in 1:npop
      if scores[i] < best_eval
	best=dec[i]
        best_eval=scores[i]
      end
   end
   print("gen=",gen,", ","objective(",best',")=", best_eval,"\n")
 # Darwinian evolution towards most fit candidate
  selected = [selection(pop, scores) for j in 1:npop]
  children = DataFrame(zeros(dim*nbits,npop))
  for j in 1:2:npop
    p1=selected[j]
    p2=selected[j+1]
    c=crossover(p1,p2,rcross)
    mutation(c[1],rmut)
    mutation(c[2],rmut)
    children[:,j]=c[1]
    children[:,j+1]=c[2]
   end
   pop=children
end
end

geneticopt2(objective2, 2, 16, 0.5, 100, 200, 0.9, 1/32.0)

You need to read the original article to see the output of the python code. The julia output is of course the same.

It was in 1993 that my student Rob C. brought genetic algorithms to my attention. I had little programming experience at that point (FORTRAN, algol, real dinosaurs!) but Rob was an excellent C programmer, and he inspired me to learn C. Rob’s interest was in solving the Traveling Salesman problem using the genetic algorithm. He did so, and wrote a marvelous (undergraduate) thesis on the subject. I case I never said it back in the day, Thanks Rob!