Evolutionary algorithms (EAs)¶

Materials¶

Grekousis, George, and Ye Liu. "Where will the next emergency event occur? Predicting ambulance demand in emergency medical services using artificial intelligence." Computers, Environment and Urban Systems 76 (2019): 110-122.

Introduction¶

Evolutionary algorithm (EA) is a subset of evolutionary computation, it inspired by biological evolution, such as reproduction, mutation, recombination, and selection.

Features¶

1. Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape.
2. In most real applications of EAs, computational complexity is a prohibiting factor.
3. Fitness approximation is one of the solutions to overcome this difficulty.

Implementation¶

Here is an implementation of a single-objective genetic algorithm

• Step One: Generate the initial population of individuals randomly. (First generation)
• Step Two: Repeat the following regenerational steps until termination:
  1. Evaluate the fitness of each individual in the population (time limit, sufficient fitness achieved, etc.)
  2. Select the fittest individuals for reproduction. (Parents)
  3. Breed new individuals through crossover and mutation operations to give birth to offspring.
  4. Replace the least-fit individuals of the population with new individuals.

Examples¶

1. Generate the initial population of N individual MLP ANNs randomly.
2. Train, validate, and test the MLP ANNs of the generation using early stopping and L1 regularization, and calculate the cost function for each one of them (MSE). Sort the ANNs by MSE in ascending order.
3. Select the top X% of the ANNs (with less MSE). Randomly select additional (X/2)% ANNs
4. Apply a mutation operator with a probability of Y% a. Mutation is used to randomly change the values of some hyperparameters of a fraction (Y%) of the selected ANNs
5. Apply a recombination operator with a probability of Z% to give birth to offspring. a. In particular, for any given set of two ANNs, we name the first ANN the “father” and the second the “mother.” b. The first child inherits the same hyper-parameter values for the learning rate, the L1, and the momentum from the mother and inherits the rest from the father. c. The second child inherits the same hyper-parameter values for the learning rate, the L1, and the momentum from the father, and in- herits the rest from the mother.
6. Replace the worst ANNs of the population with the offspring and create a new generation.
7. Go to step 2 or stop when nothing further can be improved to minimize the MSE or when the total number of generations is reached