How can a genetic algorithm optimize a neural network's weights without knowing the search volume?

Question

I've implemented a genetic algorithm trained neural network with a mutation operator like so:

def mutation(chromosome, mutation_rate):
  for gene in chromosome:
    if random.uniform(0.00, 1.00) <= mutation_rate:
      gene = random.uniform(-1.00, 1.00)

And chromosomes are initialized randomly initially:

def make_chromosome(chromosome_length):
  chromosome = []
  for _ in range(chromosome_length):
    chromosome.append(random.uniform(-1.00, 1.00))
  return chromosome

When performing crossover, offspring chromosomes can only ever have genes within the interval [-1, 1] because parent chromosomes also only have genes in that interval. When an offspring is mutated, it likewise keeps its genes within that interval.

This seems to work for some problems but not others. If a neuron's optimal weights are within [-1, 1], then the genetic algorithm works, but what if a neuron's optimal weights are within a different interval?

For example, if I trained a network using backpropagation with termination condition of classification error below 5%, I can look at the network weights and see values like -1.49, 1.98, 2.01, etc. My genetic algorithm could never produce those genes because genes are initialized within [-1, 1] and crossover and mutation cannot produce genes outside of that range either.

It seems I need to define the search space better, something like so:

# search space boundaries
S_MIN = -1.00
S_MAX = 1.00

# in mutation()
gene = random.uniform(S_MIN, S_MAX)

# in make_chromosome()
chromosome.append(random.uniform(S_MIN, S_MAX))

I can then set the search space boundaries based on the problem. But how do I determine the search space? This information isn't known a priori and is found through training the network. But if the training requires the search space be known, I'm then at a standstill.

I could set the search space as arbitrarily large (eg. assuredly larger than necessary), but then the algorithm converges slowly. I need to know at least a ballpark figure of the search space for the genetic algorithm to be efficient.

With backpropagation, the search space isn't known a priori and it doesn't matter, but for GA it does.

Answer 1

This seems to be a restatement of the core challenge of reinforcement learning with neural networks. You have a loss function that numerically quantifies how good the possible actions are in the current local of the solution space, such that when the action is taken will move you closer/further away from the global optima (the answer). {i.e. gradients w.r.t. loss function}

Before you start you cannot know where exactly the answer lies so you have an exploration policy that you define as part of the algorithm. This drives the exploration of the possible solution space guided by how much improvement certain actions have in moving closer to the answer as defined by the loss function.

At the outset the exploration is very aggressive and makes bold moves so that it can quickly explore the solution space. Then as areas of the solution space present as more promising the exploration becomes less bold in an attempt to converge on the solution.

In your case the exploration policy would vary the mutation size, mutation rate and the cross over of the chromosomes. The mutation size and rate would represent move size within a local and the crossover would represent a dimensional transposition in solution space.

So rather than have max/min you would have a starting position in solution space and assuming uniformly scaled and normalised solution space features a best guess would be any random spot in unit space.

The exploration policy would then select mutation size, rate and cross over to be initially aggressive to explore widely. Selection of subsequent generations would prefer ones that were closer to the answer and with a less aggressive exploration strategy. So the latter generations would tend to be closer to the ‘answer’ and also with a less aggressive exploration strategy and would thus tend to converge.

This article has a more formal review of the concepts.

https://towardsdatascience.com/reinforcement-learning-demystified-exploration-vs-exploitation-in-multi-armed-bandit-setting-be950d2ee9f6

Answer 2

Here's a story. There was once a presentation, probably of this paper, for genetic algorithms to configure the inputs, outputs, and architecture for indoor flight. That is, it hooked up stupid sensors to those floating indoor blimps and made them explore rooms while optimizing for straight and level flight.

The "genes" in this case were:

• Choosing two or three input values from a list of responses to standard imaging processing filters (vertical edge detection, low contrast, line detection, etc.)
• Choosing two output connections from a a list of standard voltage profiles for each engine (hard ramp/slow ramp/immediate to 0%, 50%, 100%, -50%, -100%, etc.)
• Choosing connections between nodes in a two level neural network, each layer having only five nodes. For example, "input 2 attaches to node 3 in layer 1". Only some fraction (30%?) of connections would be allowed.

So, one DNA consisted of two input nodes, fifty connections, and two output nodes. A population starts with a hundred random DNA choices, runs the blimps which trains the neural nets selected, calculates the level flight time, and breeds. By breed, I mean it kills the lowest scoring half and creates mutated copies of the winners. Success happened.

Now, relating to your problem.

You need to be very clear on what can be your genes. Some good choices might be:

• Network architecture, as in the above story
• Hyper parameters for knock-out, learning rates, restarts, loss functions, and more.
• Initial weight distributions, actually more parameters, including some for adding occasional wild weights.
• Wild kicks to one parameter or another, meaning picking an axis or two to search with wild values or with fine grain precision.

Also remember that mutation and cross breeding are different. You should allow wild mutations sometimes. A common tactic to to breed about 70% (make a copy, swapping some genes) and mutating about 30% (copy a survivor and make random changes).

As is often with quick advice, I'm guessing what's not said in your description. If I'm totally off base on what you are doing, pretend its on base; you are likely to be the one to solve your problem.