Title: Stochastic Global Optimization Algorithms: A Systematic Formal Approach,
Abstract: As we know, some global optimization problems cannot be solved using analytic
methods, so numeric/algorithmic approaches are used to find near to the optimal
solutions for them. A stochastic global optimization algorithm (SGoal) is an
iterative algorithm that generates a new population (a set of candidate
solutions) from a previous population using stochastic operations. Although
some research works have formalized SGoals using Markov kernels, such
formalization is not general and sometimes is blurred. In this paper, we
propose a comprehensive and systematic formal approach for studying SGoals.
First, we present the required theory of probability (\sigma-algebras,
measurable functions, kernel, markov chain, products, convergence and so on)
and prove that some algorithmic functions like swapping and projection can be
represented by kernels. Then, we introduce the notion of join-kernel as a way
of characterizing the combination of stochastic methods. Next, we define the
optimization space, a formal structure (a set with a \sigma-algebra that
contains strict \epsilon-optimal states) for studying SGoals, and we develop
kernels, like sort and permutation, on such structure. Finally, we present some
popular SGoals in terms of the developed theory, we introduce sufficient
conditions for convergence of a SGoal, and we prove convergence of some popular
SGoals.