2
$\begingroup$

Why do these two methods, the particle swarm optimization (PSO) and the genetic algorithm find global minima (or are at least able to).

And my second question is that these both algorithms are based on the fact we know where we want to land in the first place? How do you know this on beforehand?

$\endgroup$
2
$\begingroup$

I find stochastic gradient descent to be conceptually easier, so I will use that example for optimization instead. Stochastic gradient descent looks very much like the "normal" or "batch" gradient descent that we are all familiar with, with the exception that on each iteration the update step is computed with a new, randomly selected, subset of the measurement data. It can be shown that the average stochastic gradient descent update is equal to the batch gradient descent update, which is known to converge to local optima. The hope, is that the injected randomness is sufficient to escape local minima, and that through exploring a series of local minima we can find a global minimum. This is never guaranteed. In particular, we could construct functions with infinite series of progressively better local minima but no global minimum. But even without presenting the algorithm with artificially difficult problems, there is no guarantee that the algorithm will find a global optimum in a finite amount of time.

For your second question, knowing the answer before solving the problem is often difficult. But in many cases there is some theoretical background to the problem at hand that allows you to set constraints on viable parameters. For example for a chemical reaction the rate constants must be greater than zero and less than the diffusion limit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.