Theoretical Limits and Benchmarks

The interesting question is, what the real capabilities of such GA structures are. What are the theoretical limits of the availability of information in this example along with some benchmarks? How efficient is such a mechanism to approach possible goals?

Asking for the availability of the information is facing the problem whether and how it is possible to find exactly those informations which are representing the 'optimal' states for the evolving system.

Asking for the efficiency of the search process is asking how to measure the amount of resources used (consumed energy, number of actions, time needed, ...).

The optimal states of a system $a$ as part of a population $p_{i} \in$ $\cal{P}$ accompanied by other populations $p_{j}$ which all are living in one environment $e \in$$\cal{E}$ are in the case of real physical biological systems usually not known in advance from the point of view of the participating systems. From the theoretical point of view of this chapter it is assumed, that such 'optimal states' - if they would exist -had to be encoded into a set of binary strings $\cal{G}$$^{*}$ being a subset of the set of all possible binary strings $\cal{G}$ which induce a process which generates a phenotype $o(\cal{G}$$^{*})=$$\cal{P}$$^{*}$ which is able to behave 'optimally'. Thus the set of optimal states $\cal{G}$$^{*}$ is a set of binary strings forming a subset of $\cal{G}$ and the actual states $\cal{G}$$^{0}$ can be different. Thus one has to assume as worst case scenario

$$\cal{G}^{*} \subseteq \cal{G}$$ (3.33)

$$\cal{G}^{\emptyset} \subseteq \cal{G}$$ (3.34)

$$\cal{G}^{*} \neq \cal{G}^{\emptyset}$$ (3.35)

$$\gamma : \Sigma^{*} \times \cal{G}^{\emptyset} \times \cal{G}^{\emptyset} \longmapsto \cal{G}^{*}$$ (3.36)

where $\gamma$ is the genetic function leading from an actual non-optimal set of binary strings $\cal{G}$ $^{\emptyset}$ to a set of optimal strings. The input string $\Sigma$ can include relevant information for this mapping or not. In the worst case it holds:

$$\Sigma^{*} = \emptyset$$ (3.37)

In the worst case there is no additional information available. The search for the 'optimal' set $\cal{G}$$^{*}$ would have to be realized in this case by pure chance.

In a 'better-than-worst' case the input set $\Sigma^{*}$ is not empty and provides at least 'partial' information about 'fitness' which can be used to 'improve' the genetic process above chance.

In the following reflections we will start with the worst case scenario with only pure chance as search principle.