Optimization Algorithms
Internally and Externally MIDAS will employ genetic algorithm nomenclature across all algorithms to ensure consistency and improve readability. Some interchangeable words are:
- iteration <-> generation
- set of solutions created in a generation <-> population
- solution <-> chromosome
- objective function <-> fitness function
GA is an optimization algorithm based on the process of natural selection and the survival of the fittest. GA works by encoding a solution to a problem into a 'chromosome' which is a list of the attributes being optimized. Where each attribute is known as a 'gene'. By encoding a number of solutions, GA can create more optimal solutions by iterating through a process of Evaluation, Selection and Reproduction. Note that a set of chromosomes is a 'population' and each iteration of the optimization is a 'generation'.
During the evaluation step, the algorithm will evaluate the performance of each chromosome through the fitness function. The fitness function is a mathematical function taking into account each of the optimization objectives which is used to compute the scalar fitness value. The fitness value is then used to represent the performance of a chromosome, i.e., how good the chromosome is.
Selection follows evaluation and is the method of pairing chromosomes together for reproduction. Many different selection methods exist, all of which rely on the fitness value of each chromosome. The most common method is the tournament method where two chromosome are randomly selected from the population. From these two, the chromosome with a higher fitness value is selected to be a 'parent'. This process is then repeated with the remaining population to select the second parent. This particular method leans towards paring high performing chromosomes together as parents while also enabling chromosome of different performances to mix. MIDAS contains a number of different selection methods each with unique ways of handling exploration and exploitation.
Once the parent pairs are found, reproduction can occur. During reproduction, the parent chromosomes are mixed to create 'children' which will contain attributes of both parents. Like selection, many different reproduction methods occur which are typically referred to as 'crossover' methods. A popular crossover method is the uniform crossover which sequentially compares the parents chromosomes one gene at a time. When comparing the genes, if two genes at the same location in chromosome are found to be different, then they have a chance to be swapped between the two chromosomes. This chance depends on the user defined crossover rate. After comparing the parent chromosomes and swapping genes, there are now two unique chromosomes which are distinct from the parents and are called 'children'. After all of the children are created, the children become the parents of the next generation and the cycle repeats.
By repeating evaluation, selection, and reproduction over many generations, there is an evolutionary push causing the overall performance of the chromosomes to improve. This process enables GA to create and identify optimal solutions to a problem.
A flow chart of GA is shown below.
SA is an optimization method taking inspiration from the annealing metallurgy process where metal is heated to a high temperature and slowly allowed to cool resulting in lower energy crystalline structures. SA mimics this process through the use of a 'temperature' value which determines the randomness of exploration in a design space. The temperature decreases as the optimization progresses which effectively transitions the algorithm from exploration to exploitation.
SA is initialized either using a provided starting solution or by randomly generating one. This solution is designated as the 'active' solution. At this point the temperature starts at its initialized value. SA then perturbs the active solution and compares its fitness to the fitness of the newly generated solution. This new solution is designated as the 'challenger' solution. From here, three potential pathways emerge. The first being that the challenger is better than the active solution. In this case the challenger becomes the new active solution. The second and third pathways occur only if the challenger is worse than the active solution. In this scenario a probability function is used to determine the percent chance of the challenger replacing the active solution. The probability function depends on the fitness of both solutions as well as the temperature value. If, based on the probability, the challenger solution does not replace the active solution then no changes are made. At this point, regardless of pathway taken, the temperature value is lowered using a temperature update method and the process iterates until a termination criteria is met.
In MIDAS multiple temperature update methods are available which can be used to change the balance of exploration and exploitation. Note that typically SA is used to minimize a 'Cost' function rather than maximizing a fitness function. This change was made in support of MIDAS' modularity where the fitness function module is shared across all of the algorithms. This means that this SA is used slightly different than typical implementations however the optimization dynamics are effectively equivalent.
Due to the sequential nature of the SA algorithm, this optimization methodology is the only methodology in MIDAS which cannot be used in parallel optimizations.
A flow chart of SA is shown below.
PSA is an optimization algorithm which expands upon SA and removes its biggest weakness which is being restricted to serial computations. PSA also makes improvements elsewhere through the use of a solution buffer, global and local temperatures, and the use of parallel threads. PSA has been shown to greatly improve the balance of exploration and exploitation as compared to SA and leads to considerably better optimization results.
PSA is initialized by generating a number of solutions to populate the solution buffer. This buffer is used to store high performing solutions which can be used later during the optimization process. From here multiple SA threads are initialized; the number of threads depending on the number of processors used in the calculation. Each thread selects a solution from the buffer using fitness weighted random probability. This solution is then used as a starting point for the independent SA optimizations. The temperature value in each SA thread is also initialized by the global temperature value. Each SA thread is then allowed to optimize the solution independently updating its local temperature values along the way. Once each SA thread has iterated for the required number of iterations, the best performing solution from each thread is used to update the buffer. During the buffer update process, the oldest and worst performing solutions are replaced by the new solutions. The global temperature is then updated using the same methods as typical SA algorithms. In the next iteration the SA threads will select solutions from the updated buffer and initialize the temperature from the new global temperature value. This process iterates until a termination criteria is met.
While PSA is a parallel algorithm, its parallel implementation is vastly different from other algorithms. All other algorithms in MIDAS are parallelized only in the evaluation step of the optimization where computationally expensive external codes are used. For PSA, entire SA threads are run in parallel where all aspects of the SA optimization are done within the thread including the solution evaluations. This unfortunately means that increasing the number of processors will not speed up the optimization. Increasing the number of processors will instead affect the optimization dynamics as there are more independent SA threads and subsequently more opportunities for exploration.
In the MIDAS yaml input files, the population size determines the number of iterations per SA thread, and the number of generations determines the number of buffer update iterations. The number of SA threads is determined using the --cpus options when running MIDAS. Note that the total number of code executions is the multiplication of the population size, number of generations, and number of threads.
A flow chart of PSA is shown below.
BO is a machine learning based optimization method which leverages a surrogate model to explore the design space of the optimization problem and identify high performance solutions. In particular BO samples the design space to generate data and train a surrogate model. A sampling criterion known as the 'acquisition function' is then optimized to create a new set of samples which are evaluated and added to the training data. After sufficient iterations, the surrogate model becomes accurate enough that the acquisition function can reliably guide sampling toward high-performing regions of the design space.
The MIDAS implementation employs the Gaussian Process machine learning technique as the surrogate model used during the optimization. A number of acquisition functions are available to users, and the gradient based optimization technique L-BFGS-B is used to sample the new evaluation points. MIDAS employs an encoding/decoding scheme to represent discrete categorical solution spaces as continuous spaces allowing the algorithm to optimize over all kinds of optimization problems.
A flow chart of BO is shown below.
GD is a gradient based iterative method for minimizing differentiable multivariate functions. GD optimizes by computing the first-order derivative in each dimension and moving in the direction of steepest descent. GD can be run in two modes, the first being the standard GD configuration and the second being Stochastic Gradient Descent (SGD). SGD differentiates itself from GD by computing the first-order derivatives in a random subset of dimensions rather than all of the available dimensions. This change enables global exploration in the design space rather than a strict local search.
The MIDAS implementation of GD uses numerical differentiation to compute the first-order derivatives. This requires that two evaluations be performed per dimension to compute the gradient. For GD, to ensure that the gradient is computed correctly, any user supplied population size is overwritten to 2d+1 where d is the number of dimensions. SGD leaves more room for flexibility but still requires that the population size be an odd number less than 2d.
Because numerical derivatives are required to perform these optimizations, the GD module in MIDAS is restricted only to numeric optimization types. Like SA, GD is typically formulated as a minimization algorithm. However, since MIDAS only supports maximization problems, the MIDAS implementation of GD is more accurately a 'Gradient Ascent' algorithm.
A flow chart of GD is shown below.
TS is a local search algorithm which is enhanced to conduct global optimizations through the use of a 'tabu list'. It does this by generating 'tabu' moves during the optimization, which constrain the design space exploration and forces the underlying local search algorithm to escape sub-optimal regions. Tabu moves are specific solution perturbations that are blacklisted and cannot be used to update the 'active' solution unless the 'aspiration' criteria is met. The tabu list is a set of tabu moves which is dynamically updated during the optimization.
TS is initialized either using a provided starting solution or by randomly generating one. This starting point is designated as the 'active' solution. After initializing, a population is created by performing perturbations on the active solution. The fitness of these new solutions are then evaluated and the individual with the best fitness is selected to be the new active. Note that when selecting the new active solution, the individual with the best fitness is always selected to be the new active even if the previous active solution has a higher fitness value. As it has been described so far, the optimization process is purely a local search. This process forms the basis of TS.
After every local search iteration, a tabu move is added to the tabu list. The added tabu move is the inverse of the perturbation used go to from the previous active solution to the new active solution. Any tabu moves that have been identified cannot be used to go from the current active solution to the next. Each additional tabu move constrains the solution space and forces the algorithm to explore new solution types. The number of elements in the tabu list is a user defined hyperparameter, and once the list has reached the maximum size the oldest tabu moves will be replaced by new moves.
When iterating, tabu moves are not used to restrict the perturbations used to create new populations of individuals. it is instead used to restrict the valid perturbations when moving from one active solution to the next. In some instances, a tabu move can be bypassed if a potential active solution meets the aspiration criteria. A common aspiration criteria allows a tabu perturbed solution to replace the active solution if the fitness value of the challenger is the highest fitness seen up to this point in the optimization.
A flow chart of TS is shown below.
future work