6
$\begingroup$

Formula is here: $$ p(i)=\frac{e^\frac{f(i)}{T}}{\displaystyle \sum_j e^\frac{f(j)}{T}} $$

Prove:

1) Each $p(i)$ is a number between $0$ and $1$, no matter what the fitness is (positive or negative). This scheme does not require that fitness has to be positive.

2) The sum of all the $p(i)$'s is $1$, i.e. this is a probability distribution.

3) No matter what $T$ is:

  • If two items have same fitness, they have same probability of being picked.
  • If all fitnesses are the same, we pick random item.

4) No matter what the fitnesses are:

  • As $T\to\infty$ we tend to pick random item.
  • As $T\to0$ we tend to pick only the best item. That is, its probability is $1$, the probability of all others is $0$. If there are $m$ joint best items, we pick them with probability $1/m$, and all others with probability $0$.
  • 0
    For (2), ... if the denominator is summing up $n$ or so terms, and then you add $n$ of the $p(i)$, well...2011-08-14
  • 0
    For (1): Why would the denominator be always greater than or equal to the numerator?2011-08-14
  • 0
    ...you really could have started with defining the $p$, $f$, and $T$ in the formula you gave, though...2011-08-14

1 Answers 1