In inequality
d (f (P_{u}), f (P_{v})) ≤ qd (P_{v}, P_{u})
the coefficient q is called the Lipschitz constant. It determines the convergence speed of the contraction mapping
If t = 0
Let q = 0.99 we have
That means that the length of evolution is less or equal to 100 times the length of the first step of the algorithm. So Lipschitz constant lets us visualize the number of evolutionary generations of the population.
Lipschitz constant setting
We need to set the Lipschitz constant to satisfy the inequality of the contraction mapping. We will prove that inequality is equivalent tod (P_{t+1}, P_{t+2}) ≤ qd (P_{t}, P_{t+1})
(*)
∀ t ∈ ℕ
Inequality (*) states that at all times, the distance between two successive generations is always less or equal to q the distance between two previous successive generations.
Without losing generality, suppose u <v, we have
d (f (P_{u}), f (P_{v})) = d (P_{u+1}, P_{v+1}) = E_{u+1} - E_{v+1} = E_{u+1} - E_{u+2} + E_{u+2} - E_{u+3} + ... + E_{v} - E_{v+1}
= (E_{u+1} - E_{u+2}) + (E_{u+2} - E_{u+3}) + ... + (E_{v} - E_{v+1}) = d (P_{u+1}, P_{u+2}) + d (P_{u+2}, P_{u+3}) + ... + d (P_{v}, P_{v+1})
According to inequality (*) we have
d (P_{u+1}, P_{u+2}) ≤ qd (P_{u}, P_{u+1})
d (P_{u+2}, P_{u+3}) ≤ qd (P_{u+1}, P_{u+2})
...
d (P_{v}, P_{v+1}) ≤ qd (P_{v-1}, P_{v})
Therefore
d (P_{u+1}, P_{v+1}) ≤ qd (P_{u}, P_{u+1}) + qd (P_{u+1}, P_{u+2}) + ... + qd (P_{v-1}, P_{v}) = qd (P_{u}, P_{v})
Thus we only need to satisfy the inequality (*) instead of the inequality of the contraction mapping.
This is simply that we hold the two average error values E_{t-2}, E_{t-1} of the previous two generations, along with the current average error value E_{t} to evaluate the condition of the contraction mapping
for (;;) { // ... if (Et == Et_1) break; if ( Et_1 - Et > q * (Et_2 - Et_1) ) { undo(); continue; } backup(); Et_2 = Et_1; Et_1 = Et; // ... }
The above theory clearly shows the effectivity in experiment, the algorithm converges very fast, like the contraction nature of the mapping.
Note: The population needs to move freely before actually entering the contraction mapping.
Can't see mail in Inbox? Check your Spam folder.
Comments
There are currently no comments
New Comment