Stochastic ranking

The general non-linear programming problem ($A$) can be formulated as solving the objective function

$$\index{Mathematics!Objective function} minimize\qquad f(x),\qquad x = (x_{1},\ldots,x_{n}) \in \mathcal{R}^n$$ (1)

where $x \in \mathcal{S} \cap \mathcal{F}, \mathcal{S} \subseteq \mathcal{R}^n$ defines the search space which is an $n$-dimensional space bounded by the parameteric constraints

$$\index{Mathematics!Constraints} \underline x _{i} \leq x_{i} \leq \overline x _{i},\qquad i \in \{1,\ldots,n\}$$ (2)

and the feasible region $\mathcal{F}$ is defined by

$$\index{Mathematics!Feasible region} \mathcal{F} = \{x\in\mat... ...R}^{n}\vert g_{j}(x) \leq 0\qquad \forall j\in\{1,\ldots,m\}\}$$ (3)

where $g_{j}(x),j\in\{1,\ldots,m\}$ are constraints. Generally, a penalty term is introduced to transform a constrained optimization problem ($A$) into an unconstrained on ($A'$), such as

$$\index{Mathematics!Fitness function} \psi(x) = f(x) + r_{g}\phi(g_{j}(x);\qquad j = 1,\ldots,m)$$ (4)

where $\phi\geq 0$ is a real-valued function which imposes a "penalty" controlled by a sequnce of penalty coefficients $\{r_{g}\}^{G}_{0}$, where $g$ is the generation counter. Thus the function $\psi$ will be referred to as the fitness function. In particular, the following quadratic loss function has often been used as the penalty function.

$$\index{Mathematics!Penalty function} \phi(g_{j}(x);\qquad j = 1,\ldots,m)=\sum_{j=1}^{m} max\{0,g_{j}(x)\}^{2}$$ (5)

Therefore, the problem is to balance the two functions and achieve a minimum fitness.

In Runarsson and Yao's work, a new approach, stochastic ranking method, has been developed to strike the right balance between objective and penalty functions. Here is the bubble-sort-like procedure of stochastic ranking method.

Figure 1: Stochastic ranking schema

where $\mathbf{U}(0,1)$ is a uniform random number generator and $N$ is the number of sweeps going through the whole population. When , the ranking is overpenalization, and for , the ranking is an underpenalization. The initial ranking is always generated at random. So the probability of an adjacent individual winning a comparison in the ranking procedure is

$$\index{Mathematics!Ranking probability} P_{w} = P_{fw}P_{f} + P_{\phi w}(1-P_{f})$$ (6)

where $P_{fw}$ is the probability of the individual winning according to the objective function (Eqn.1), and $P_{\phi w}$ is according to the penalty function (Eqn.5).