Internship Lecture 2: Discrete optimization (GA) / Continuous optimization (scipy optimize / torch optimize) / Bayesian optimization (optuna)

This is the second internship course. Last time we looked lightly at machine learning and neural network models. This time we will review optimization.

Optimization can be divided into two main types. One is "discrete optimization," in which values are not continuous, and the other is "continuous optimization," in which values are continuous.

Discrete optimization" takes discrete values at intervals and cannot be differentiated. Discrete Optimization is used for "combinatorial optimization problems," in which the best choice is selected from a large number of alternatives.

Continuous optimization (mathematical optimization) can be differentiated because the values are continuous. Although there are other ways to solve the problem without differentiation, it is mainly used to optimize models for machine learning and quantum computation.

In addition to that, you will learn roughly three types of optimization, including Bayesian optimization, which is used in machine learning parameter search.

Discrete Optimization
Genetic Algorithms (GA), Tabu Search, Simulated Annealing, etc. are well-known here. Often, calculations are performed using meta-heuristics methods, and algorithms such as quantum annealing and QAOA are used to deal with quantum. A cost function is set and the computation is done in the direction of minimizing it, for example. Minimization can be, for example, the shortest distance a car can travel or the most efficient schedule. In this lesson, we will learn GA.

Genetic Algorithm."
Description from wikipedia.

A genetic algorithm is a meta-heuristic algorithm that searches for approximate solutions, proposed by John H. Holland of the University of Michigan in 1975. Like artificial life, it uses chance factors to influence computer control; it is one of the four main evolutionary algorithms and the most commonly used of them.

The "Genetic Algorithm" Flow

Genetic algorithms are generally implemented in the following flow. In the following, the number of individuals is N and the maximum number of generations is G.

1.Prepare two sets that contain N individuals in advance. These two sets are called "current generation" and "next generation.
2.Generate N individuals randomly in the current generation. Calculate the degree of adaptation of each individual in the current generation using an evaluation function, and with a certain probability, perform one of the following three actions and store the results in the next generation.

A. Select two individuals to mate.
B. Select one individual to mutate.
C. Select one individual and copy it as is.

Repeat the above until there are N individuals in the next generation. When the number of individuals in the next generation reaches N, transfer all the contents of the next generation to the current generation.

• Repeat the above steps up to the maximum number of generations G, and finally output the individual with the highest degree of adaptation in the current generation as the solution.

We will immediately try to implement it using vcopt, a python package for genetic algorithms our intern made.

First, load the tool.

Next, set the evaluation function for optimization. We are basically heading in the direction of minimizing this value. In this case we looked at a simple quadratic function.

Next, set the range of parameters to search for。

Then execute it immediately. The arguments are set in the following order: parameter search range, evaluation function, and target. The target is set to -9999 this time because we want to make it small.

When x=0, the minimization proceeds to y=0 and some value is obtained. In this way, the evaluation function and range of values are set, and the process proceeds in python following the genetic algorithm procedure to output a solution.

Continuous Optimization
This method optimizes models for machine learning, etc. The gradient method, which calculates the slope of a function so that it advances toward a lower value, is well-known. Other methods that do not use gradients are sometimes used because they are easier to use. It is also used in quantum computation in a method called quantum-classical hybrid. In this article, we will look at scipy.optimize.minimize, which is available in a library called scipy. We will also look at the optim library, which contains several optimization algorithms, including SGD, which is included in pytorch. The latter is a gradient-based algorithm.

scipy.optimize.minimize
This is an optimization algorithm in a library called scipy. Let's take a look at how to use it.
https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

Some optimization algorithms require first-order second-order derivatives, while others do not. In this case, we will simply use Powell/Nelder-Mead/COBYLA, etc. as those that do not require them. The functions are the same as in the previous GA. Here, we will throw it with the initial x value.

It doesn't make much difference which one you use, but it will give you a similar solution. Next, let's look at PyTorch's optim.

PyTorch Optimizer
Optimization algorithms for machine learning are mainly gradient-based. It calculates the derivative from the initial position and descends to a lower one, and implements an algorithm based on the stochastic gradient method, called SGD.

First load the tool.

Prepare the initial values and the optimization algorithm.
The initial values must be in the form torch.sensor.

There are various optimization algorithms based on SGD. lr is the learning rate, which in this case is set to 0.1.

In execution, the loop is passed around. The actual value of x is calculated by substituting the value of x as a function.

The calculation was completed in this way. The implementation procedure was a little different from other optimization algorithms.

Bayesian optimization
When optimizing something, Bayesian optimization is a prioritized search. Bayesian optimization is often used in machine learning to search for a set of parameters that require various settings, such as choices, discrete values, and continuous values. In this article, we will look at a library called optuna.

This time, we will optimize the parameters of the previous problem of guessing the rent, with the NN intermediate layer, the optimization algorithm, and the learning rate as variables, respectively. The parameter to be minimized is the one that is closest to the correct value of 11.5 for rent.

Thus, parameters were explored.