Shiraz University - CSE Dept - Project # 1

Function Optimization Using GA, ES and EP

M.M.Haji
mehdi.haji@gmail.com

Problem Definition:

In this project we use three basic EC techniques (i.e. Genetic Algorithm, Evolutionary Strategy and Evolutionary Programming) to optimize (in this project minimize) several multi-dimensional functions. These functions are good test cases because of their nonlinearity and oscillation around the optimal solutions; so there exists a high probability for each optimization technique to trap into local optima.

De Jong's F1, when x ₁ is held constant at its optimal value (that is 0):

De Jong's F2:

Schaffer F6:

Ackey F1 when x ₁, x ₂ and x ₃ are held constant at their optimal value (that is 0):

Rastrigin F1 when x ₁, x ₂, ..., and x ₈ are held constant at their optimal value (that is 0):

Implementation:

The implementation includes ten java file:

• ECUtilities.java which contains some useful procedures for evolutionary algorithms, such as binary to gray conversion and vice versa.
  
  GAIndividual.java which is an individual of GA, and since the problem is function optimization, the individual is a real string (not binary) representing the values of arguments of the function to be optimized. This class has implemented 1-point and average crossover, and normal and creep mutation operators. To solve various problems (function optimizations), only the evalFitness() function of this class must be changed appropriately. For example to minimize De Jong's F1:
   

  private void evalFitness(){          fitness = 1.0f / (1.0f + genome[0]*genome[0] + genome[1]*genome[1] + genome[2]*genome[2] );     }

  Obviously with this implementation the fitness value of 1.0 corresponds to the optimal solution.

• GAPopulation.java which is a population of GAIndividuals. The main method of this class is generate, which generates a new population from the current population by crossover, mutation and reproduction. The selection method is a tournament selection of size 10. Each GAPopulation evaluates and holds the best, average and worst fitness of its individuals for later purposes.
• GAEvolve.java which is the main class of genetic algorithm. It runs a simple GA with several initial populations and several runs over the same problem (function) to find the solution, and finally makes a M file such that if executed in MATLAB the best fitness versus generation, average fitness versus generation and worst fitness versus generation are plotted. For De Jong's F1 the main method is:
   

  public static void main(String[] args) {            float[] min = new float[]{-5.12f, -5.12f, -5.12f};            float[] max = new float[]{5.12f, 5.12f, 5.12f};            GAEvolve.evolveAndMakeMFile("ga.m",25,300,400,3,70,20,min,max);     }

  The first two lines indicate x ₀, x ₁ and x ₃ must be in range [-5.12,5.12].
  In the third line the evolveAndMakeMFile method is called: the first argument is the M file name that will be generated, the second argument is the number of runs, the third and fourth arguments are the number of generations and population size respectively, the fifth argument is the number of variables of the function to be optimized, the sixth and seventh arguments are cross-over and mutation rate, and the last two arguments specify the range of each variable.
  
  
   

• ESIndividual.java which is an individual of ES. To solve various problems (function optimizations), only the evalFitness() function of this class must be changed appropriately. For example to minimize De Jong's F1:
   

  private void evalFitness(){         fitness = 1.0f / (1.0f + obj_var[0]*obj_var[0] + obj_var[1]*obj_var[1] + obj_var[2]*obj_var[2] );     }

  Obviously with this implementation the fitness value of 1.0 corresponds to the optimal solution.

• ESPopulation.java which is a population of ESIndividuals. The main method of this class is generate, which generates a new population from the current population by crossover and mutation. The (Mu + Lambda) and (Mu , Lambda) strategies are implemented as well. Each ESPopulation evaluates and holds the best, average and worst fitness of its individuals for later purposes.

• ESEvolve.java which is the main class of ES algorithm. It runs the ES algorithm with several initial populations and several runs over the same problem (function) to find the solution, and finally makes a M file in the same way GAEvolve did. For De Jong's F1 the main method is:

  public static void main(String[] args) {            float[] min = new float[]{-5.12f, -5.12f, -5.12f};            float[] max = new float[]{5.12f, 5.12f, 5.12f};            ESEvolve.evolveAndMakeMFile("es.m",25,150,50,100,false,3,0,100,min,max);     }

  As before the first two lines indicate x ₀, x ₁ and x ₃ must be in range [-5.12,5.12].
  In the third line the evolveAndMakeMFile method is called: the first argument is the M file name that will be generated, the second argument is the number of runs, the third argument specifies the number of generations, the fourth and fifth arguments are the values of Mu and Lambda respectively, the sixth argument is a boolean that when is true the algorithm uses the Comma strategy and otherwise uses the Plus strategy (in the above code the Plus strategy will be used because of the sixth argument is false), the seventh argument is the number of variables of the function to be optimized, the eighth and ninth arguments are cross-over and mutation rate, and the last two arguments specify the range of each variable.
  
   

• EPIndividual.java which is an individual of EP and is similar to ESIndividual.

• EPPopulation.java which is a population of EPIndividuals.

• EPEvolve.java that is the main class of EP algorithm and is similar to ESEvolve.

Download class files here: ECUtilities.class, GAIndividual.class, GAPopulation.class, GAEvolve.class, ESIndividual.class, ESPopulation.class, ESEvolve.class, EPIndividual.class, EPPopulation.class, EPEvolve.class.

Compile and Run:

To compile and run the program, java 2 complier must be installed on your system. If so, execute the following commands:
 

Results:

GA on De Jong's F1:

runs = 25
generations = 300
population size = 400
cross-over rate = 70
mutation rate = 20
best individual = [-1.8104166E-4, 2.0238012E-4, 1.9333512E-4]
function value = 0.0

ES (mu + lambda) on De Jong's F1:

runs = 25
generations = 150
mu = 50
lambda = 100
cross-over rate = 0
mutation rate = 100
best individual = [3.5803027E-5, 1.455153E-4, -1.474504E-4]
function value = 0.0

EP on De Jong's F1:

runs = 25
generations = 50
mu = 100
best individual = [-0.0014037113, -0.010541787, 9.688381E-4]
function value =  1.1408329E-4

GA on De Jong's F2:

runs = 25
generations = 300
population size = 400
cross-over rate = 70
mutation rate = 20
best individual = [0.92901266, 0.86223257]
function value = 0.005

ES (mu + lambda) on De Jong's F2:

runs = 25
generations = 150
mu = 50
lambda = 100
cross-over rate = 0
mutation rate = 100
best individual = [1.0000187, 1.0000305]
function value = 0.0

EP on De Jong's F2:

runs = 25
generations = 150
mu = 100
best individual = [1.0009778, 1.0023032]
function value =  1.2993812E-5

GA on Schaffer F6:

runs = 25
generations = 300
population size = 400
cross-over rate = 70
mutation rate = 20
best individual = [-0.66895545, -3.066477]
function value =  .01

ES (mu + lambda) on Schaffer F6:

runs = 25
generations = 150
mu = 50
lambda = 100
cross-over rate = 0
mutation rate = 100
best individual = [-3.1198633, -0.34239888]
function value = 0.009715795516

EP on Schaffer F6:

runs = 25
generations = 150
mu = 200
best individual = [-1.4643227, -2.7757885]
function value =  0.0097159

GA on Ackey F1 (5 dimensional):

runs = 25
generations = 300
population size = 400
cross-over rate = 70
mutation rate = 20
best individual = [-5.0991774E-5, -1.7507374E-4, -7.83205E-5, -1.5050918E-4, -3.7178397E-6]
function value = 4.46319580078125E-4

ES (mu + lambda) on Ackey F1 (5 dimensional):

runs = 25
generations = 150
mu = 50
lambda = 100
cross-over rate = 0
mutation rate = 100
best individual = [1.2647838E-6, 4.5080992E-7, 6.039528E-9, -2.9687908E-7, -7.887053E-7]
function value =  1.9073486328125E-6

EP on Ackey F1:

runs = 25
generations = 300
mu = 200
best individual = [0.02244251, 0.008399729, 0.013339171, 0.014297446, -0.0040695854]
function value =   0.0661373

GA on Rastrigin F1 (10 dimensional):

runs = 25
generations = 300
population size = 400
cross-over rate = 70
mutation rate = 20
best individual = [0.0011808425, 8.550286E-5, -0.001330167, 1.0236353E-4, -2.48909E-4,
                          -3.503561E-4, -2.907291E-4, -1.8841028E-4, -1.982525E-4, 2.3342669E-5]
function value = 6.90460205078125E-4

ES (mu + lambda) on Rastrigin F1 (10 dimensional):

runs = 25
generations = 250
mu = 200
lambda = 300
cross-over rate = 0
mutation rate = 100
best individual = [0.995562, 0.0012131229, 2.5612157E-4, -0.98916, 0.9956671,
                          1.9909033, 0.002642206,  0.0053935437, -0.9915468, 1.991358]
function value =  11.9567

EP on Rastrigin F1 (10 dimensional):

runs = 25
generations = 300
mu = 200
best individual = [0.07367469, -1.0541013, 0.014264069, 0.95182097, -0.96396834,
                          -0.96741545, -1.8013868, 0.121750146, 0.022928316, 0.08587444]
function value =    20.8765