Optimization

The purpose of the optimization is to find the mitigation value in every node of the decision tree that maximizes the current utility

\[x^*= \operatorname*{arg\,max}_x U(x)\]

Our approach to solving this problem is to use the genetic algorithm (GA) combine with a gradient search (GS) method. The GA is used to search the state space globally and to find good initial points for the GS, which applies a gradient descent algorithm to multiple initial points.

Genetic Algorithm (GA)

The GA is an evolutionary algorithm, inspired by the evolution of species in nature. The evolution process starts from a population of vectors with uniformly distributed [0, bound] random elements. For each generation, the evolution steps are:

  1. Select the individuals to perform cross-over and mutation.
  2. Cross over among the selected candidate.
  3. Mutate result as offspring.
  4. Combine the result of offspring and parent together. And selected the top 80 percent of original population amount.
  5. Random Generate 20 percent of original population amount new individuals and combine the above new population.

The mutation and cross-over methods are choosen to fit the optimization problem of the EZ-Climate model. The GA class can be found at ezclimate.optimization.GeneticAlgorithm.

Gradient Search (GS)

The GS uses the gradient descent algorithm and the numerical gradient to find the optimal mitigation points. Moveover, it uses the Adaptive Moment Estimation (Adam) learning rate together with an accelarator scaler to update the points. Adam is a method that computes adaptive learning rates for each parameter. In addition to storing an exponentially decaying average of past squared gradients, Adam also keeps an exponentially decaying average of past gradients. The accelerator is used to amplify low gradient values of mitigation values in nodes in the end of the tree, and thus reduce computation time. The run() method takes initial_point_list and topk as arguments, runs the gradient descent optimization of the topk first elements of the initial_point_list, and picks the resulting point with the highest utility. The GS class can be found at ezclimate.optimization.GradientSearch.

GA and GS together

An example of how to use the GeneticAlgorithm and GradientSearch can be found here. The GradientSearch.run() takes the last generation population of the GeneticAlgorithm.run() as the initial_point_list argument and performs the gradient descent optimization with these as intial guess.