text:
# 1 Introduction

## 1 Introduction

### Evolutionary algorithms (EA):

Evolutionary algorithms are capable of solving complicated optimization tasks in which an objective function $`f:IIR`$ shall be maximized. $`iI`$ is an individual from the set $`I`$ of feasible solutions. Infeasible solutions due to constraints my also be considered by reducing $`f`$ for each violated constraint. A population $`PI`$ of individuals is maintained and updated as follows: one or more individuals are selected according to some selection strategy. In generation based EAs, the selected individuals are recombined (e.g. crossover) and mutated, and constitute the new population. We prefer the more incremental, steady-state population update, which selects (and possibly delets) only one or two individuals from the current population and adds the newly recombined and mutated individuals to it. We are interested in finding a single individual of maximal objective value $`f`$ for difficult multimodal and deceptive problems.

### Standard selection schemes (STD):

The standard selection schemes (abbreviated by STD in the following), proportionate, truncation, ranking and tournament selection all favor individuals of higher fitness \[Gol89, GD91, BT95, BT97\]. This is also true for less common schemes, like Boltzmann selection \[MT93\]. The fitness function is identified with the objective function (possibly after a monotone transformation). In linear proportionate selection the probability of selecting an individual depends linearly on its fitness \[Hol75\]. In truncation selection the $`\alpha \%`$ fittest individuals are selected, usually with multiplicity $`\frac{1}{\alpha \%}`$ in order to keep the population size fixed \[MSV94\]. (Linear) ranking selection orders the individuals according to their fitness. The selection probability is, then, a (linear) function of the rank \[Whi89\]. Tournament selection \[Bak85\], which selects the best $`l`$ out of $`k`$ individuals has primarily developed for steady-state EAs, but can be adapted to generation based EAs. All these selection schemes have the property (and goal!) to increase the average fitness of a population, i.e. to evolve the population towards higher fitness. For a population with a Gaussian fitness distribution, the probability of selecting an individual and the effect of selection is shown in Figure 1.

### The problem of the right selection pressure:

The standard selection schemes STD, together with mutation and recombination, evolve the population towards higher fitness. If the selection pressure is too high, the EA gets stuck in a local optimum, since the genetic diversity rapidly decreases. The suboptimal genetic material which might help in finding the global optimum is deleted too rapidly (premature convergence). On the other hand, the selection pressure cannot be chosen arbitrarily low if we want EA to be effective. In difficult optimization problems, suitable population sizes, mutation and recombination rates, and selection parameters, which influence the selection intensity, are usually not known beforehand. Often, constant values are not sufficient at all. There are various suggestions to dynamically determine and adapt the parameters \[Esh91, BHS91, Her92, SVM94\]. Other approaches to preserve genetic diversity are fitness sharing \[GR87\], crowding \[Jon75\] and local mating \[CJ91\]. They depend on the proper design of a neighborhood function based on the specific problem structure and/or coding.

### The main idea:

Here, we propose a new selection scheme, based on the insight that we are not primarily interested in a population converging to maximal fitness, but only in a single individual of maximal fitness. The scheme automatically creates a suitable selection pressure and preserves genetic diversity better than STD. The proposed fitness uniform selection scheme FUSS (see also Figure 1) is defined as follows: if the lowest/highest fitness values in the current population $`P`$ are $`f_{min/max}`$, we select a fitness value $`f`$ uniformly in the interval $`[f_{min},f_{max}]`$. Then, the individual $`iP`$ with fitness nearest to $`f`$ is selected and a copy is added to $`P`$, possibly after mutation and recombination. We will see that FUSS maintains genetic diversity much better than STD, since a distribution over the fitness values is used, unlike STD, which all use a distribution over individuals. Premature convergence is avoided in FUSS by abandoning convergence at all. Nevertheless there is a selection pressure in FUSS towards higher fitness. The probability of selecting a specific individual is proportional to the distance to its nearest fitness neighbor. In a population with a high density of unfit and low density of fit individuals, the fitter ones are effectively favored.

### Contents:

In Section 2 we discuss the problems of local optima and exponential takeover \[GD91\] in STD. Motivated by the need to preserve genetic diversity, we define the fitness uniform selection scheme FUSS. We discuss under which circumstances FUSS leads to an (approximate) fitness uniform population.

Further properties of FUSS are discussed in Section 3, especially, how FUSS creates selection pressure towards higher fitness and how it preserves diversity better than STD. Further topics are the equilibrium distribution and the transformation properties of FUSS under linear and non-linear transformations.

In Section 4 we demonstrate by way of a simple optimization example that an EA with FUSS can optimize much faster than with STD. We show that crossover can be effective in FUSS, even when ineffective in STD. Furthermore, FUSS and STD are compared to random search with and without crossover.

There is a possible slowdown when including recombination, as discussed in Section 5, which can be avoided by using a scale independent pair selection. It is a “best” compromise between unrestricted recombination and recombination of individuals with similar fitness only.

To simplify the discussion we have concentrated on the case of discrete, equi-spaced fitness values. In many practical problems, the fitness function is continuously valued. FUSS and some of the discussion of the previous sections is generalized to the continuous case in Section 6.

A summary, conclusions and further discussions can be found in Section 7.

The focus of this work is on a theoretical analysis of FUSS. Implementation details and numerical results for various test-functions and for real-world problems will be presented elsewhere.

## 2 Fitness Uniform Selection Strategy (FUSS)

### The problem of local optima:

Proportionate, truncation, ranking and tournament are the standard (STD) selection algorithms used in evolutionary optimization. They have the following property: if a local optimum $`i^{lopt}`$ has been found, the number of individuals with fitness $`f^{lopt}=f(i^{lopt})`$ increases exponentially. Assume a low mutation and recombination rate, or, for instance, truncation selection after mutation and recombination. Further, assume that it is very difficult to find an individual more fit than $`i^{lopt}`$. The population will then degenerate and will consist mostly of $`i^{lopt}`$ after a few rounds. This decreased diversity makes it even more unlikely that $`f^{lopt}`$ gets improved. The suboptimal genetic material which might help in finding the global optimum has been deleted too rapidly. On the other hand, too high mutation and recombination rates convert the EA into an inefficient random search. In the following we suggest a new a new selection scheme, which automatically generates a suitably adapting selection pressure.

### The fitness uniform selection scheme (FUSS):

For simplicity we start with a fitness function $`f:IF`$ with discrete equi-spaced values $`F=\{f_{min},f_{min}+\epsilon ,f_{min}+2\epsilon ,\mathrm{},f_{max}\epsilon ,f_{max}\}`$. The continuous valued case $`F=[f_{min},f_{max}]`$ is considered later. The fitness uniform selection scheme (FUSS) is defined as follows: randomly select a fitness value $`f`$ uniformly from the fitness values $`F`$. Randomly (uniformly) select an individual $`i`$ from population $`P`$ with fitness $`f`$. Add another copy of $`i`$ to $`P`$.

Note the two stage uniform selection process which is very different from a one step uniform selection of an individual of $`P`$ (see Figure 1).

In STD, inertia increases with population size. A large mass of unfit individuals reduces the probability of selecting fit individuals. This is not the case for FUSS. Hence, without loss of performance, we can define a pure model, in which no individual is ever deleted; the population size increases with time. No genetic material is ever discarded and no fine-tuning in population size is necessary. What may prevent the pure model from being applied to practical problems are not computation time issues, but memory problems. If space gets a problem we delete individuals from the most occupied fitness levels. Most of the following statements remain valid with this modification.

### Asymptotically fitness uniform population:

The expected number of individuals per fitness level $`f`$ after $`t`$ selections is $`n_t(f)=n_0(f)+t/|F|`$, where $`n_0(f)`$ is the initial distribution. Hence, asymptotically the fitness levels get uniformly occupied by a population fraction

$$\frac{n_t(f)}{|P_t(f)|}=\frac{n_0(f)+t/|F|}{|P_0(f)|+t}\frac{1}{|F|}\text{for}t\mathrm{},$$

where $`P_t(f)`$ is the set of individuals at time $`t`$ with fitness $`f`$.

### Fitness gaps and continuous fitness:

We made two unrealistic assumptions. First, we assumed that each fitness level is initially occupied. If the smallest/largest fitness values in $`P_t`$ are $`f_{min/max}^t`$ we extend the definition of FUSS by selecting a fitness value $`f`$ uniformly in the interval $`[f_{min}^t\frac{1}{2}\epsilon ,f_{max}^t+\frac{1}{2}\epsilon ]`$ and an individual $`iP_t`$ with fitness nearest to $`f`$. This also covers the case when there are missing intermediate fitness values, and also works for continuous valued fitness functions ($`\epsilon 0`$).

### Mutation and recombination:

The second assumption was that there is no mutation and recombination. In the presence of small mutation and/or recombination rates eventually each fitness level will become occupied and the occupation fraction is still asymptotically approximately uniform. For larger rates the distribution will be no longer uniform, but the important point is that the occupation fraction of no fitness level decreases to zero for $`t\mathrm{}`$, unlike for STD. Furthermore, FUSS selects by construction uniformly in the fitness levels, even if the levels are not uniformly occupied. We will see that this is the more important property.

## 3 Properties of Fuss

### FUSS effectively favors fit individuals:

FUSS preserves diversity better than STD, but the latter have a (higher) selection pressure towards higher fitness, which is necessary for optimization. At first glance it seems that there is no such pressure at all in FUSS, but this is deceiving. As FUSS selects uniformly in the fitness levels, individuals of low populated fitness levels are effectively favored. The probability of selecting a specific individual with fitness $`f`$ is inverse proportional to $`n_t(f)`$ (see Figure 1). In a typical (FUSS) population there are many unfit and only a few fit individuals. Hence, fit individuals are effectively favored until the population becomes fitness uniform. Occasionally, a new higher fitness level is discovered and occupied by a new individual, which then, again, is favored.

### No takeover in FUSS:

With FUSS, takeover of the highest fitness level never happens. The concept of takeover time \[GD91\] is meaningless for FUSS. The fraction of fittest individuals in a population is always small. This implies that the average population fitness is always much lower than the best fitness. Actually, a large number of fit individuals is usually not the true optimization goal. A single fittest individual usually suffices to having solved the optimization task.

### FUSS may also favor unfit individuals:

Note, if it is also difficult to find individuals of low fitness, i.e. if there are only few individuals of low fitness, FUSS will also favor these individuals. Half of the time is “wasted” in searching on the wrong end of the fitness scale. This possible slowdown by a factor of 2 is usually acceptable. In Section 4 we will see that in certain circumstances this behaviour can actually speedup the search. In general, fitness levels which are difficult to reach, are favored.

### Distribution within a fitness level:

Within a fitness level there is no selection pressure which could further exponentially decrease the population in certain regions of the individual space. This (exponential) reduction is the major enemy of diversity, which is suppressed by FUSS. Within a fitness level, the individuals freely drift around (by mutation). Furthermore, there is a steady stream of individuals into and out of a level by (d)evolution from (higher)lower levels. Consequently, FUSS develops an equilibrium distribution which is nowhere zero. We expect FUSS to somewhat lower (but not to solve) the problems associated with genetic drift. The above does also not mean that the distribution within a level is uniform. For instance, if there are two (local) maxima of same height, a very broad one and a very narrow one, the broad one may be populated much more than the narrow one, since it is much easier to “find”.

### Steady creation of individuals from every fitness level:

In STD, a wrong step (mutation) at some point in evolution might cause further evolution in the wrong direction. Once a local optimum has been found and all unfit individuals were eliminated it is very difficult to undo the wrong step. In FUSS, all fitness levels remain occupied from which new mutants are steadily created, occasionally one leading to further evolution in a more promising direction.

### Transformation properties of FUSS:

FUSS (with continuous fitness) is independent of a scaling and a shift of the fitness function, i.e. FUSS($`\stackrel{~}{f}`$) with $`\stackrel{~}{f}(i):=af(i)+b`$ is identical to FUSS($`f`$). This is true even for $`a<0`$, since FUSS searches for maxima and minima, as we have seen. It is not independent of a non-linear (monotone) transformation unlike tournament, ranking and truncation selection. The non-linear transformation properties are more like the ones of proportionate selection.

## 4 A Simple Example

In the following we compare the performance of fitness uniform selection (FUSS), random search (RAND) and standard selection (STD) with and without recombination on a simple test example. We regard it as a prototype for deceptive multimodal functions. The example should demonstrate why FUSS can be superior to RAND and STD. Numerical results are briefly discussed at the end of the section.

### Simple 2D example:

Consider individuals $`(x,y)I:=[0,1]\times [0,1]`$, which are tupels of real numbers, each coordinate in the interval $`[0,1]`$. The example models individuals possessing up to 2 “features”. Individual $`i`$ possesses feature $`I_1`$ if $`iI_1:=[a,a+\mathrm{\Delta }]\times [0,1]`$, and feature $`I_2`$ if $`iI_2:=[0,1]\times [b,b+\mathrm{\Delta }]`$. The fitness function $`f:I\{1,2,3\}`$ is defined as

$$f(x,y)=\{\begin{array}{c}1\text{if}(x,y)I_1\backslash I_2,\hfill \\ 2\text{if}(x,y)I_2\backslash I_1,\hfill \\ 3\text{if}(x,y)I_1I_2,\hfill \\ 4\text{if}(x,y)I_1I_2.\hfill \end{array}\text{}$$

We assume $`\mathrm{\Delta }1`$. Individuals with none of the two features ($`iI\backslash (I_1I_2)`$) have fitness $`f=3`$. These “local $`f=3`$ optima” occupy most of the individual space $`I`$, namely a fraction $`(1\mathrm{\Delta })^2`$. It is disadvantageous for an individual to possess only one of the two features ($`i(I_1\backslash I_2)(I_2\backslash I_1)`$), since $`f=1/f=2`$ in this case. In combination ($`iI_1I_2)`$), the two features lead to the highest fitness, but the global maximum $`f=4`$ occupies the smallest fraction $`\mathrm{\Delta }^2`$ of the individual space $`I`$. With a fraction $`\mathrm{\Delta }(1\mathrm{\Delta })`$, the $`f=1/f=2`$ minima are in between.

### Random search:

Individuals are created uniformly in the unit square. The “local optimum” $`f=3`$ is easy to “find”, since it occupies nearly the whole space. The global optimum $`f=4`$ is difficult to find, since it occupies only $`\mathrm{\Delta }^21`$ of the space. The expected time, i.e. the expected number of individuals created and tested until one with $`f=4`$ is found, is $`T_{RAND}=\frac{1}{\mathrm{\Delta }^2}`$. Here and in the following, the “time” $`T`$ is defined as the number of created individuals until the first optimal individual (with $`f=4`$) is found. $`T`$ is neither a takeover time nor the number of generations (we consider steady-state EAs).

### Random search with crossover:

Let us occasionally perform a recombination of individuals in the current population. We combine the $`x`$-coordinate of one uniformly selected individual $`i_1`$ with the $`y`$ coordinate of another individual $`i_2`$. This crossover operation maintains a uniform distribution of individuals in $`[0,1]^2`$. It leads to the global optimum if $`i_1I_1`$ and $`i_2I_2`$. The probability of selecting an individual in $`I_i`$ is $`\mathrm{\Delta }(1\mathrm{\Delta })\mathrm{\Delta }`$ (we assumed that the global optimum has not yet been found). Hence, the probability that $`I_1`$ crosses with $`I_2`$ is $`\mathrm{\Delta }^2`$. The time to find the global optimum by random search including crossover is still $`\frac{1}{\mathrm{\Delta }^2}`$.

### Mutation:

The result remains valid (to leading order in $`\frac{1}{\mathrm{\Delta }}`$) if, instead of a random search, we uniformly select an individual and mutate it according to some probabilistic, sufficiently mixing rule, which preserves uniformity in $`[0,1]`$. One popular such mutation operator is to use a sufficiently long binary representation of each coordinate, like in genetic algorithms, and flip a single bit. In the following, we assume a mutation operator which mutates with probability $`\frac{1}{2}/\frac{1}{2}`$ the first/second coordinate, preserves uniformity, is sufficiently mixing, and leaves the other coordinate unchanged, like the single-bit-flip operator.

### Standard selection with crossover:

The $`f=1`$ and $`f=2`$ individuals contain useful building blocks, which could speedup the search by a suitable selection and crossover scheme. Unfortunately, the standard selection schemes favor individuals of higher fitness and will diminish the $`f=1/f=2`$ population fraction. The probability of selecting $`f=1/f=2`$ individuals is even smaller than in random search. Hence $`T_{STD}\frac{1}{\mathrm{\Delta }^2}`$. Standard selection does not improve performance, even not in combination with crossover, although crossover is well suited to produce the needed recombination.

### FUSS:

At the beginning, only the $`f=3`$ level is occupied and individuals are uniformly selected and mutated. The expected time till an $`f=1/f=2`$ individual in $`I_1I_2`$ is created is $`T_1\frac{1}{\mathrm{\Delta }}`$ (not $`\frac{1}{2\mathrm{\Delta }}`$, since only one coordinate is mutated). From this time on FUSS will select one half(!) of the time the $`f=1/f=2`$ individual(s) and only the remaining half the abundant $`f=3`$ individuals. When level $`f=1`$ and level $`f=2`$ are occupied, the selection probability is $`\frac{1}{3}+\frac{1}{3}`$ for these levels. With probability $`\frac{1}{2}`$ the mutation operator will mutate the $`y`$ coordinate of an individual in $`I_1`$ or the $`x`$ coordinate of an individual in $`I_2`$ and produces a new $`f=1/2/4`$ individual. The relative probability of creating an $`f=4`$ individual is $`\mathrm{\Delta }`$. The expected time to find this global optimum from the $`f=1/f=2`$ individuals, hence, is $`T_2=[(\frac{1}{2}\mathrm{}\frac{2}{3})\times \frac{1}{2}\times \mathrm{\Delta }]^1`$. The total expected time is $`T_{FUSS}T_1+T_2=\frac{4}{\mathrm{\Delta }}\mathrm{}\frac{5}{\mathrm{\Delta }}\frac{1}{\mathrm{\Delta }^2}T_{STD}`$. FUSS is much faster by exploiting unfit $`f=1/f=2`$ individuals. This is an example where (local) minima can help the search. Examples where a low local maxima can help in finding the global maximum, but where standard selection sweeps over too quickly to higher but useless local maxima, can also be constructed.

### FUSS with crossover:

The expected time till an $`f=1`$ individual in $`I_1`$ and an $`f=2`$ individual in $`I_2`$ is found is $`T_1\frac{1}{\mathrm{\Delta }}`$, even with crossover. The probability of selecting an $`f=1/f=2`$ individual is $`\frac{1}{3}/\frac{1}{3}`$. Thus, the probability that a crossing operation crosses $`I_1`$ with $`I_2`$ is $`(\frac{1}{3})^2`$. The expected time to find the global optimum from the $`f=1/f=2`$ individuals, hence, is $`T_2=9O(1)`$, where the $`O(1)`$ factor depends on the frequency of crossover operations. This is far faster than by STD, even if the $`f=1/f=2`$ levels were local maxima, since to get a high standard selection probability, the level has first to be taken over, which itself needs some time depending on the population size. In FUSS a single $`f=1`$ and a single $`f=2`$ individual suffice to guarantee a high selection probability and an effective crossover. Crossover does not significantly decrease the total time $`T_{FUSSX}T_1+T_2=\frac{1}{\mathrm{\Delta }}+O(9)`$, but for a suitable 3D generalization we get a large speedup by a factor of $`\frac{1}{\mathrm{\Delta }}`$.

### Simple 3D example:

We generalize the 2D example to D-dimensional individuals $`𝐱[0,1]^D`$ and a fitness function

$$f(𝐱):=(D+1)\underset{d=1}{\overset{D}{}}\chi _d(𝐱)\underset{1dD}{\mathrm{max}}d\chi _d(𝐱)+d+1,$$

where $`\chi _d(𝐱)`$ is the characteristic function of feature $`I_d`$

$$\chi _d(𝐱):=\{\begin{array}{c}1\text{if}a_ix_ia_i+\mathrm{\Delta },\hfill \\ 0\text{else.}\hfill \end{array}$$

For $`D=2`$, $`f`$ coincides with the 2D example. For $`D=3`$, the fractions of $`[0,1]^3`$ where $`f=1/2/3/4/5`$ are approximately $`\mathrm{\Delta }^2/\mathrm{\Delta }^2/\mathrm{\Delta }^2/1/\mathrm{\Delta }^3`$. With the same line of reasoning we get the following expected search times for the global optimum:

$$T_{RAND}T_{STD}\frac{1}{\mathrm{\Delta }^3},$$

$$T_{FUSS}\frac{1}{\mathrm{\Delta }^2},T_{FUSSX}\frac{1}{\mathrm{\Delta }}.$$

This demonstrates the existence of problems, where FUSS is much faster than RAND and STD, and that crossover can give a further boost in FUSS, even when ineffective in combination with STD.

### Numerical results:

An EA with FUSS and STD has been implemented. First experiments confirm the superiority of FUSS also for other complicated multimodal and deceptive fitness functions. The asymptotic behavior of the convergence times $`T`$ for $`\mathrm{\Delta }0`$ for the previous example has been verified. We got similar results for the function $`f(x+a,y+b)=2\frac{x^2}{x^2+\mathrm{\Delta }^2}+\frac{y^2}{y^2+\mathrm{\Delta }^2}+4e^{(x^2+y^2)/\mathrm{\Delta }^2}`$, which is a continuous version of the 2D example. We further applied FUSS to the Traveling Salesman Problem. We considered $`10^{\mathrm{1..3}}`$ cities with random matrix distances, random initial paths, random 1-Opt and 2.5-Opt mutation operators, inverse length as fitness, but no crossover yet. The solutions found by FUSS are consistently and significantly better than those found by STD. The current implementation can in no way compete with up-to-date TSP-solvers \[JM97, ACR00\], but this was not the intention of the comparison. The results are very preliminary yet. Implementation details and detailed simulation results will be presented in a forthcoming publication.

## 5 Recombination

### Worst case analysis without recombination:

We now want to estimate the maximal possible slowdown of FUSS compared to STD. Let us assume that all individuals in STD have fitness $`f`$, and once one individual with fitness $`f+\epsilon `$ has been found, takeover of level $`f+\epsilon `$ is quick. Let us assume that this quick takeover is actually good (e.g. if there are no local maxima). The selection probability of individuals of same fitness is equal. For FUSS we assume individuals in the range of $`f_{min}`$ and $`f`$. Uniformity is not necessary. In the worst case, a selection of an individual of fitness $`<f`$ never leads to an individual of fitness $`f`$, i.e. is always useless. The probability of selecting an individual with fitness $`f`$ is $`\frac{1}{|F|}`$. At least every $`|F|th`$ FUSS selection corresponds to a STD selection. Hence, we expect a maximal slowdown by a factor of $`|F|`$, since FUSS “simulates” STD statistically every $`|F|th`$ selection. It is possible to artificially construct problems where this slowdown occurs (unimodal function, local mutation $`xx\pm \epsilon `$, no crossover). We have never observed this large slowdown in our experiments. For the more complicated multimodal and deceptive objective functions we were interested in, FUSS often outperformed STD in solution quality and time.

### Quadratic slowdown due to recombination:

We have seen that $`T_{FUSS}|F|T_{STD}`$. In the presence of recombination, a pair of individuals has to be selected. The probability that FUSS selects two individuals with fitness $`f`$ is $`\frac{1}{|F|^2}`$. Hence, in the worst case, there could be a slowdown by a factor of $`|F|^2`$ — for independent selection we expect $`T_{FUSS}|F|^2T_{STD}`$. This potential quadratic slowdown can be avoided by selecting one fitness value at random, and then two individuals of this single fitness value. For this dependent selection, we expect $`T_{FUSS}|F|T_{STD}`$. One the other hand, crossing two individuals of different fitness can also be advantageous, like the crossing of $`f=1`$ with $`f=2`$ individuals in the 2D example of Section 4.

### Scale independent pair selection:

It is possible to (nearly) have the best of independent and dependent selection: a high selection probability $`p(f,f^{})\frac{1}{|F|}`$ if $`ff^{}`$ and $`p(f,f^{})\frac{1}{|F|^2}`$ otherwise, with uniform marginal $`p(f)=\frac{1}{|F|}`$. The idea is to use a strongly correlated joint distribution for selecting a fitness pair. A “scale independent” probability distribution $`p(f,f^{})\frac{1}{|ff^{}|}`$ is appropriate. We define the joint probability $`\stackrel{~}{p}(f,f^{})`$ of selecting two individuals of fitness $`f`$ and $`f^{}`$ and the marginal $`\stackrel{~}{p}(f)`$ as

$$\stackrel{~}{p}(f,f^{}):=\frac{1}{2|F|\mathrm{ln}|F|}\frac{1}{\frac{1}{\epsilon }|ff^{}|+1},$$
(1)
$$\stackrel{~}{p}(f):=\underset{f^{}F}{}\stackrel{~}{p}(f,f^{})=\underset{f^{}F}{}\stackrel{~}{p}(f^{},f).$$

We assume $`|F|3`$ in the following. The $`+1`$ in the denominator has been added to regularize the expression for $`f=f^{}`$. The factor $`(2|F|\mathrm{ln}|F|)^1`$ ensures correct normalization for $`|F|\mathrm{}`$. More precisely, using $`\mathrm{ln}\frac{b+1}{a}_{i=a}^b\frac{1}{i}\mathrm{ln}\frac{b}{a1}`$, one can show that

$$1\frac{1}{\mathrm{ln}|F|}\underset{f,f^{}F}{}\stackrel{~}{p}(f,f^{})\mathrm{\hspace{0.33em}1},\frac{1}{2}|F|\stackrel{~}{p}(f)\mathrm{\hspace{0.33em}1}$$

i.e. $`\stackrel{~}{p}`$ is not strictly normalized to $`1`$ and the marginal $`\stackrel{~}{p}(f)`$ is only approximately (within a factor of 2) uniform. The first defect can be corrected by appropriately increasing the diagonal probabilities $`\stackrel{~}{p}(f,f)`$. This also solves the second problem.

$$p(f,f^{}):=\{\begin{array}{cc}\stackrel{~}{p}(f,f^{})\hfill & \text{for}ff^{}\hfill \\ \stackrel{~}{p}(f,f^{})+[\frac{1}{|F|}\stackrel{~}{p}(f)]\hfill & \text{for}f=f^{}\hfill \end{array}$$
(2)
### Properties of $`p(f,f^{})`$:

$`p`$ is normalized to $`1`$ with uniform marginal

$$p(f):=\underset{f^{}F}{}p(f,f^{})=\frac{1}{|F|},p(f,f^{})\stackrel{~}{p}(f,f^{}),$$

$$\underset{f,f^{}F}{}p(f,f^{})=\underset{fF}{}p(f)=1,$$

Apart from a minor additional logarithmic suppression of order $`\mathrm{ln}|F|`$ we have the desired behaviour $`p(f,f^{})\frac{1}{|F|}`$ for $`ff^{}`$ and $`p(f,f^{})\frac{1}{|F|^2}`$ otherwise:

$$p(f,f\pm m\epsilon )\frac{1}{2\mathrm{ln}|F|}\frac{1}{m+1}\frac{1}{|F|},$$

$$p(f,f^{})\frac{1}{2\mathrm{ln}|F|}\frac{1}{|F|^2}.$$

During optimization, the minimal/maximal fitness of an individual in population $`P_t`$ is $`f_{min/max}^t`$. In the definition of $`p`$ one has to use $`F_t:=\{f_{min}^t,f_{min}^t+\epsilon ,\mathrm{},f_{max}^t\}`$ instead of $`F`$, i.e. $`|F||F_t|=\frac{1}{\epsilon }(f_{max}^tf_{min}^t)+1|F|`$.

## 6 Continuous Fitness Functions

### Effective discretization scale:

Up to now we have considered a discrete valued fitness function with values in $`F=\{f_{min},f_{min}+\epsilon ,\mathrm{},f_{max}\}`$. In many practical problems, the fitness function is continuous valued with $`F=[f_{min},f_{max}]`$. We generalize FUSS, and some of the discussion of the previous sections to the continuous case by replacing the discretization scale $`\epsilon `$ by an effective (time-dependent) discretization scale $`\widehat{\epsilon }`$. By construction, FUSS shifts the population towards a more uniform one. Although the fitness values are no longer equi-spaced, they still form a discrete set for finite population $`P`$. For a fitness uniform distribution, the average distance between (fitness) neighboring individuals is $`\frac{1}{|P_t|1}(f_{max}^tf_{min}^t)=:\widehat{\epsilon }`$. We define $`\widehat{F}_t:=\{f_{min}^t,f_{min}^t+\widehat{\epsilon },\mathrm{},f_{max}^t\}`$. $`|\widehat{F}_t|=\frac{1}{\widehat{\epsilon }}(f_{max}^tf_{min}^t)+1=|P_t|`$.

### FUSS:

Fitness uniform selection for a continuous valued function has already been mentioned in Section 2. We just take a uniform random fitness $`f`$ in the interval $`[f_{min}^t\frac{1}{2}\widehat{\epsilon },f_{max}^t+\frac{1}{2}\widehat{\epsilon }]`$. One may even take the limit $`\widehat{\epsilon }0`$ in this case probably without harming FUSS. Independent and dependent fitness pair selection as described in the last section works analogously. An $`\widehat{\epsilon }=0`$ version of correlated selection does not exist; a non-zero $`\widehat{\epsilon }`$ is important. A discrete pair $`(f,f^{})`$ is drawn with probability $`p(f,f^{})`$ as defined in (1) and (2) with $`\epsilon `$ and $`F`$ replaced by $`\widehat{\epsilon }`$ and $`\widehat{F}_t`$. The additional suppression $`\mathrm{ln}|\widehat{F}_t|=\mathrm{ln}|P_t|`$ is small for all practical population sizes.

In all cases an individual with fitness nearest to $`f`$ ($`f^{}`$) is selected from the population $`P`$ (randomly if there is more than one nearest individual).

### Discussion:

If we assume a fitness uniform distribution, a worst case bound $`T_{FUSS}\stackrel{<}{}_{t=1}^{T_{STD}}|P_t|`$ seems plausible, since the probability of selecting the best individual is approximately $`|P_t|`$. For constant population size we get a bound $`T_{FUSS}\stackrel{<}{}|P|T_{STD}`$. For the preferred non-deletion case with population size $`|P_t|=t`$ the bound gets much worse $`T_{FUSS}\stackrel{<}{}\frac{1}{2}T_{STD}^2`$. This possible (but not necessary!) slowdown has similarities to the slowdown problems of proportionate selection in later optimization stages. Larger choices of $`\widehat{\epsilon }`$ may be favorable if the standard choice causes problems.

## 7 Summary & Conclusions

We have addressed the problem of balancing the selection intensity in EAs, which determines speed versus quality of a solution. We invented a new fitness uniform selection scheme FUSS. It generates a selection pressure towards sparsely populated fitness levels. This property is unique to FUSS as compared to other selection schemes (STD). It results in the desired high selection pressure towards higher fitness if there are only a few fit individuals. The selection pressure is automatically reduced when the number of fit individuals increases. A joint pair selection scheme for recombination has been defined, but not yet implemented. A heuristic worst case analysis of FUSS compared to STD has been given. FUSS solves the problem of exponential takeover and the resulting loss of genetic diversity of STD, while still generating enough selection pressure. It does not help in getting a more uniform distribution within a fitness level. We showed analytically by way of a simple example that FUSS can be much more effective than STD. FUSS should be compared to STD on other problems to further explore its efficacy and limitations. First results look encouraging. Of special interest is whether FUSS could improve up-to-date EAs that solve difficult combinatoric optimization problems, like TSPs. We expect FUSS to be superior to STD in cases where an EA with STD effectively gets trapped into local optima.


format: text

text:
# A Classic Type 2 QSO

## 1 Introduction

The unified model for AGNs is widely accepted. Briefly, the physics of black hole, accretion disk, jet, and obscuring torus is convolved with the geometry of the viewing angle and can explain most of the apparent disparate properties of active galaxies (Antonucci, 1993). The use of the word torus here is generic for the obscuring region since there are many variants of the geometry of the obscuring region including a strict toroidal geometry and flaring disk models (Efstathiou & Rowan-Robinson, 1995; Granato et al., 1997). Type 1 objects exhibit the straight physics of AGNs with no absorption and Type 2 objects arise when the view is obscured by the torus. A crucial component that has long been sought are heavily obscured powerful quasars called QSO 2s. They have been predicted to have narrow permitted lines, powerful hard X-ray emission and a high equivalent width Fe K$`\alpha `$ line (Ghisellini et al., 1994).

In the absence of a good standard case doubt has been expressed, at times, about the whole QSO 2 phenomenon (Halpern et al., 1999). The successful finding of an optically obscured central AGN in the starburst NGC 6240 (Vignati et al., 1999) made X-rays the obvious wavelength to uncover the Type 2 QSO phenomenon. There have been few previous studies of candidate Type 2 objects in the X-ray band. One has been observed by ROSAT and ASCA (Almaini et al. 1995; Georgantopoulos et al. 1999). Two are underluminous objects from ASCA (Ohta et al., 1996) and Chandra (Fabian et al., 2000). Also, the hyper-luminous infrared galaxy IRAS 09104 +4109, observed with BeppoSAX (Franceschini et al., 2000) and recently with Chandra iwasawa2001 (Iwasawa et al. 2001), appears to be an example of a Type 2 QSO at moderate redshift, $`z=0.442`$. It is a cD galaxy in a rich cluster and is radio loud with a radio jet. A recent candidate at high redshift ($`z=3.288`$) has been found in the deep Chandra exposure of the Lynx field (Stern et al. 2001).

In parallel with the X-ray work, imaging and spectropolarimetric studies on warm ultraluminous, infrared galaxies (ULIRGs) indicate that all of them might contain buried QSOs (Tran et al., 2000). In addition, high redshift radio galaxies (HZRGs) harbour obscured QSOs, and intensive studies are underway to understand the physics of the central regions of these objects (Vernet et al., 2001).

From our multiwaveband studies of the 1Msec exposure of the Chandra Deep Field South (CDF-S) (Giacconi et al. 2001a; Tozzi et al. 2001; Rosati et al. 2001; Giacconi et al. 2001b) we now discuss a classic X-ray selected Type 2 QSO: CXOCDFS J033229.9 -275106 (hereafter CDF-S 202). We note in passing that, in contrast to the above mentioned radio studies, CDF–S 202 is radio quiet.

The Paper is organized as follows. In Section II we describe the multiwavelength observations we use. In Section III we present and analyze the optical spectrum. In Section IV we discuss the X-ray spectrum. In Section V we study the object further and present some of the wider implications of this work. We conclude and consider future work in the final section.

We assume a cosmology in this paper with the parameters $`H_0=60`$ km s-1Mpc-1, $`\mathrm{\Omega }_m=0.3`$ and $`\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$.

## 2 Imaging Observations

We have combined 11 individual Chandra pointings into a mosaic with a maximum of 942 ksec of exposure time (hereafter the 1 Msec exposure). The limiting fluxes achieved are $`5.5\times 10^{17}`$ erg cm-2 s-1 in the 0.5-2 keV band and $`4.5\times 10^{16}`$ erg cm-2 s-1 in the 2-10 keV band (Rosati et al. 2001). The details of the X-ray observations are given in Giacconi et al. (2001b, submitted). Among the sources with $`z>3`$, CDF–S 202 is the one with the hardest X-ray spectrum. In the X-ray image from $`0.57`$ keV the source is $`3\mathrm{}`$ from the center, where the point response function has a full–width–half–maximum (FWHM) of 1$`\mathrm{}`$. The X–ray intensity profile is completely consistent with that of a point–source at this resolution. There are no other X-ray sources detected within 30$`\mathrm{}`$.

The primary optical ID was made in deep $`R`$ and $`I`$ band images ($`R`$(Vega)$`26`$) obtained using the Focal Reducer Spectrograph (FORS1) on the European Southern Observatory Very Large Telescope 8.2m facility (ESO/VLT–ANTU). All magnitudes quoted in this paper are Vega magnitudes. CDF-S 202 has an $`R`$ magnitude of 23.53 and an $`I`$ magnitude of 22.65. We have additional photometric coverage of this object in the $`U`$, $`V`$, $`B`$, $`J`$ and $`Ks`$ bands. The B band used here is from ESO Wide–Field Imager data taken on the 2.2m ESO telescope, which reaches a limiting magnitude of 26. The near–infrared data comes from the ESO Imaging Survey (EIS) and reaches 23.6 in $`J`$ and 21.8 in $`Ks`$. Of these five bands our candidate QSO 2 is detected significantly in $`V`$ and $`Ks`$, at 25.27 and 20.99 respectively. The $`B`$–band source is very faint, essentially at the limiting magnitude. The images in the $`B`$, $`R`$, $`I`$, $`J`$ and $`Ks`$ bands are given in Fig. 1.

## 3 Optical Spectroscopy

### 3.1 Observations and Data Reduction

The optical spectrum was obtained with the multislit mode on the Focal Reducer Spectrograph (FORS1) on the European Southern Observatory Very Large Telescope 8.2m unit facility (ESO/VLT–ANTU) on 11–25–2000. The FORS instrument is described in detail in Mitsch et al. (1994). The spectroscopy was obtained using the 150I+17 grism and no order separation filter, which allows maximum wavelength coverage but introduces second order contamination. This grism gives a spectral resolution of 5.5Å$`/`$pixel. The detector slit width was 1.2 arcseconds, (around 30Å dispersed), chosen to maximize the signal-to-noise ratio of the resulting spectra (i.e. including most of the light from the object, but minimizing the sky background). The final spectrum is composed of 7 exposures with a total integration time of $``$3 hours.

Data reduction was carried out using the IRAF package. This involved bias subtraction, flat fielding, background subtraction, wavelength and flux calibration. The background was subtracted by fitting a second order polynomial to each column. The spectrum was extracted using an aperture width of 14 pixels, which was sufficent to include the total emission from the object.

Wavelength calibration was derived using the spectra from four arc lamps (He, HgCd and two separate Ar lamps) taken on the same night. Line centers and shapes can only be determined to a few Å accuracy due to the finite slit width. In addition, the exact location of the object on the slit can introduce an additional few Å systematic shift in the spectrum. These limit the redshift to an accuracy of $`\pm 0.005`$. It is also important to note that the finite slit size and seeing introduces an artificial broadening of the lines. As the seeing is potentially wavelength dependent, this effect can be also wavelength dependent. We estimate this effect to be a few times 10Å. Therefore, the line widths measured (see Table 1) should be considered upper limits.

The spectra were flux calibrated using very wide (5 arcsec) slits using both a red and a blue photometric standard star for comparison. As the seeing is potentially wavelength dependent, applying this flux calibration can introduce a wavelength dependent slit-loss (in addition to the varying slit loss introduced by the atmospheric refraction). Considering the relatively good seeing (0.5” FWHM at the beginning of the observation) and low airmass, this color effect is not very strong. Second order contamination was removed from the specphot standard observations using two standards with very different spectral shape. This made it possible to calibrate the true throughput of the system. Due to the very faint continuum of CDF-S 202, the second order contamination was not removed from its spectra. This implies that the continuum shape would be incorrect (if we could detect it), but the emission line features are correctly calibrated. Comparing the spectra obtained using each photometric standard, we estimate that our flux calibration is accurate to 5%. At present, we use known CTIO extinction curves until ESO extinction curves for Paranal become available to us.

### 3.2 Emission-Line Analysis

QSOs can be classified into Type 2 and Type 1 objects in a similar fashion to Seyfert galaxies, which are generally classified based on their relative emission–line widths using the scheme proposed by Weedman (1970, 1973) and Khachikian & Weedman (1971, 1974). In this scheme, Seyferts which show broad H I, He I and He II emission lines FWHM $`35\times 10^3`$ km s-1) are known as Seyfert 1 galaxies. These galaxies also display strong blue continua, and frequently complexes of broad Fe II emission are also seen. Superimposed on this spectrum are ‘narrow’ forbidden lines, which are thought to be formed in a much larger extended narrow line region (NLR) around the nucleus.

The forbidden lines in Seyfert 1 galaxies such as \[O III\], \[N II\], and \[S II\] typically have FWHM of $`5\times 10^2`$ km s-1. Galaxies with permitted and forbidden lines with approximately the same FWHM (typically $`5\times 10^2`$ km s-1) are called Seyfert 2 galaxies. The broad lines are absent in such objects and they display a flat, featureless continuum (eg., Kinney et al., 1993; Heckman et al., 1995). Similarly, broad QSO emission lines typically have widths of 3000-5000 km s-1, while narrow QSO emission lines are a few hundreds of km s-1 (eg., Peterson, 1997; Forster et al., 2001).

To determine the emission line fluxes and FWHM for CDF–S 202, the optical spectral line profiles were modeled by one Gaussian per line using the ngaussfits task in IRAF. This routine uses least squares fitting implemented by a downhill simplex minimization algorithm. The resulting emission line fluxes and FWHM found for the emission lines in CDF–S 202 are given in Table 1. The final spectrum is shown in Figure 2. The permitted emission lines, O IV, Ly$`\alpha `$, N V, C IV, and He II have S/N ratios $`>3\sigma `$ and are well identified, giving a redshift of $`z=3.700\pm 0.005`$. The continuum is not detected to a 3$`\sigma `$ limit of $`3\times 10^{19}`$ ergs/s/cm2/Å. This is consistent with the flat, featureless continua seen in many Type 2 objects such as NGC 3393 (eg. Kinney et al., 1993; Heckman et al., 1995).

The emission line widths of CDF–S 202 are given in Table 1. They have a rest–frame FWHM of between $`7002300`$ km s-1. Note that these FWHM are actually upper limits as discussed in the previous section, and that the “true” FWHM may be even less than those quoted here. The FWHM of Ly$`\alpha `$ has an upper limit of 1100 km s-1. Assuming that our FWHM upper limits are close to the true FWHM of the emission lines (within 100-300 km s-1), then our Ly$`\alpha `$ FWHM is similar to the FWHM of $`900`$ km s-1 observed in the Type 2 QSO IRAS 09104+4109 (Kleinmann et al., 1988). Such FWHM are broader than those seen in typical Seyfert 2s ($`5\times 10^2`$ km s-1), but narrower than those observed in Seyfert 1s and broad-line QSOs ($`30005000`$km s-1). Our FWHM are, however, similar to those found in the so-called “narrow-line Seyfert 1” galaxies which have FWHM of 1000-2000 km s-1 (Goodrich, 1989). However, narrow–line Seyfert 1 galaxies are generally defined as having Balmer lines slightly broader than the forbidden lines, an \[O III\] $`\lambda `$5007/H$`\beta `$ ratio less than 3, and in most cases, the presence of high ionization iron species. Without spectra at optical wavelengths in the rest-frame, and better estimates of the FWHM, we are unable to determine whether CDF-S 202 fits these criteria.

We note that the absorption seen in CDF-S 202 of $`N_H10^{24}`$ cm-2 is common for Type 2 objects (Maiolino et al., 1998; Risaliti, Maiolino & Salvati, 1999) but not for Type 1s (Reeves & Turner, 2000). In addition, the flat, featureless continuum to a 3$`\sigma `$ flux limit of $`3\times 10^{19}`$ ergs/s/cm2 supports a Type 2 classification of CDF–S 202.

Figure 3 shows the N V/He II vs. N V/C IV diagram with models by Vernet et al. (2001) and Hamann & Ferland (1993). Hamann & Ferland (1993) showed that high redshift quasars ($`z>2`$) define a tight correlation, indicated by the dashed line in this figure. This correlation is predominantly a result of metallicity variations in which the higher redshift quasars have higher metallicities. This redshift–metallicity effect may be due to higher QSO or host galaxy masses at higher redshifts. From Figure 3, we can see that the N V/C IV and N V/He II ratios for CDF–S 202 are strong, similar to those previously seen in Type 1 QSOs and powerful radio galaxies at similar redshifts (Hamann & Ferland, 1993; Vernet et al., 2001). The position of CDF–S 202 in this figure indicates emission line ratios intermediate between HzRGs and BLR QSOs.

The solid line shown in Figure 3 gives the best–fit power-law photoionization model for high redshift radio galaxies (HzRG) run by Vernet et al. for metallicities from $`0.44Z_{}`$. Similarly, the Hamann & Ferland (1993) model for the broad emission-line region of QSOs (QSO BLR) is shown in dashes. From these models, CDF-S 202 appears to be a high metallicity (Z$`2.53\times Z_{}`$) object, at the high end of the metallicity range found in HzRGs by Vernet et al. although an independent metallicity diagnostic is required to verify this.

The He II/C IV ratio is $`0.3`$. Heckman et al. (1995) note that this ratio is typically 0.1 in Seyfert 1 galaxies compared with 0.9 for Seyfert 2 galaxies. Narrow–line radio galaxies (the radio–loud analogs to Seyfert 2 galaxies) also show strong He II/C IV ratios ($`0.9`$) (McCarthy, 1993), while spectra of high-z quasars resemble the Seyfert 1 galaxies with He II/C IV$`0.15`$ (Francis et al., 1991). The He II/C IV ratio for CDF-S 202 is intermediate between the Type 1 and Type 2 values. However, CDF-S 202 is more likely a Type 2 QSO rather than an intermediate QSO, since its emission line velocity widths are relatively narrow and heavy obscuration is confirmed from the X–rays.

## 4 X-ray Spectroscopy

The X–ray spectrum of CDF–S 202 and the relative background spectrum were extracted from the X–ray image using the standard CIAO v2 software. The source spectrum was extracted in a circle with radius $`R=5\mathrm{}`$, the background spectrum was extracted in an annulus between $`R+2\mathrm{}`$ and $`R+12\mathrm{}`$ around the source position. We verified that changing the source extraction radius does not affect significantly our results. With the same software we produced response matrix functions at the CDF–S 202 position. The X–ray spectrum of CDF-S 202 was then analyzed using XSPEC v11.0. The data were rebinned to have at least 10 counts per bin (source + background), in order to validate the use of the $`\chi ^2`$ statistics. Hereafter errors are quoted at the 90% confidence level for one interesting parameter ($`\mathrm{\Delta }\chi ^2=2.71`$). The fit with a simple power law absorbed by the Galactic hydrogen gives a very flat slope ($`\mathrm{\Gamma }=0.51\pm 0.27`$) suggesting heavy absorption. We then considered two possible scenarios. First, we assumed the X–ray emission is transmitted through an absorber which cuts off the spectrum at low energies. Usually the absorber is identified with the putative obscuring torus expected from unified schemes, although its geometry could be different. Second, we assumed the X-rays are reflected. The obscuring material is then optically thick to Compton scattering with no transmitted X-rays observed in the Chandra band up to $`7\times (1+z)33`$ keV, implying $`N_\mathrm{H}10^{25}`$ cm-2. In this case the X-rays are reflected by the inner edge of the torus (or any cold cloud off the line of sight). Generally, for large equivalent width of the Fe K$`\alpha `$ line, the reflection model is favoured (Ghisellini et al., 1994).

We first considered the transmission model and fitted the spectrum with an absorbed powerlaw. The best fit photon index ($`\mathrm{\Gamma }=1.847`$) is poorly constrained, therefore we fixed it to be $`\mathrm{\Gamma }=1.8`$, a standard value for AGN, deriving a column density of $`N_\mathrm{H}=6.7_{2.1}^{+2.4}\times 10^{23}`$ cm-2. A residual excess around 1.4 keV suggested the presence of an iron K$`\alpha `$ line at 6.4 keV rest frame ($`6.4/(1+3.700)1.4`$ keV), therefore we added a narrow Gaussian line to the model fixing the line energy to 6.4 keV and the line width to 0 keV. The addition of the iron line changes the $`\chi ^2/dof`$ value from 11.6/16 to 9.5/15; the fitted column density slightly increases to $`N_\mathrm{H}=7.9_{2.3}^{+3.5}\times 10^{23}`$ cm-2. Although the iron line detection is not significant ($`<2\sigma `$ level according to an $`F`$-test for one additional free parameter), we will leave the line in the transmission model for comparison with the reflection model. The line equivalent width in the observed frame is $`EW_{K\alpha }=175_{175}^{+360}`$ eV, corresponding to $`EW_{K\alpha }=823_{823}^{+1694}`$ eV in the rest frame. The 2-10 keV rest frame luminosity is calculated to be $`4.4\times 10^{43}`$ erg s-1. When correcting for absorption, the intrinsic 2–10 keV rest frame luminosity is $`3.3\times 10^{44}`$ erg s-1. In Figure 4 we show the fit to the X–ray spectrum together with the best fit transmission model.

We then considered a pure reflection model using the pexrav model in XSPEC with $`\mathrm{\Gamma }`$ fixed to 1.8 and adding at $`6.4`$ keV rest frame a narrow Gaussian line with $`\sigma _{K\alpha }=0`$ keV. The description of the data is as good as in the transmission model ($`\chi ^2/dof=10/15`$; see Figure 5). With this model the line is detected at $`>2\sigma `$ level according to an $`F`$-test for one additional free parameter ($`\mathrm{\Delta }\chi ^2`$=4.6 with respect to the same reflection model without the line). The rest frame line energy and equivalent width are $`E_{\mathrm{K}\alpha }=6.43\pm 0.34`$ keV and $`EW_{\mathrm{K}\alpha }=1186_{922}^{+1195}`$ eV, respectively. The line equivalent width is then in full agreement with the expectations from Compton thick sources (Ghisellini et al., 1994). Assuming a reflection efficiency of 3% (see e.g. Krolik, Madau & Zicky 1994; Maiolino et al. 1998; and Sect 3.1 in Gilli, Risaliti & Salvati 1999), the 2–10 keV rest frame intrinsic luminosity of the source is $`\mathrm{1.4\hspace{0.25em}10}^{45}`$ erg s-1111We note that assuming $`H_0`$=50 km/s/Mpc and $`q_0=0`$ gives luminosities higher by a factor of $`3`$..

In principle one could look at the source variability to estimate which scenario is favored. Indeed, short term variability, on timescales of a few 10 ksec, indicates that the observed radiation is transmitted rather than reprocessed by a pc–scale reflecting material. Unfortunately, analysis of short term variability is not possible given our photon statistics. Also, long term variability (the data were collected in a 14 months period) is poorly constrained.

We also note in passing the blip in the X- ray spectrum at 3.2 keV, corresponding to a restframe energy $`15`$ keV. This is not a statistically significant line in the spectrum but we point out that such features have found twice previously in ASCA observations of other AGN and may be associated with Doppler-bosted $`FeK\alpha `$ (Yaqoob et al., 1999).

## 5 Discussion and Implications

How common are QSO 2s and how can more be detected? This object stood out in a Hardness Ratio-Redshift plot of the currently cataloged sources in the Chandra Deep Field South as the highest redshift source with the hardest spectrum. One would expect to observe the red ($`RKs4`$) colors of the host galaxy (see e.g. Fig. 7 in Lehmann et al. 2001). In this case, at $`z=3.700`$, the $`RKs`$ color of $`2.5`$ does not reflect the galactic continuum, but rather the chance super-position of emission lines into the broad–band filters. For CDF–S 202, the $`R`$ band contains both Ly$`\alpha `$ and CIV, while the $`Ks`$ band contains the weaker H$`\beta `$, H$`\delta `$ and HeII. Since the CDF-S 202 optical continuum is not detected, we used the NGC 1068 template redshifted to z=3.7 to verify the effect of line subtraction to the optical-infrared colors, assuming that the NGC 1068 spectrum is identical to that of CDF-S 202. We found that $`RKs=3.92`$ when lines are subtracted, which is comparable with the Lehmann et al. findings.

Both observed and corrected (i.e. line subtracted) magnitudes are shown in Fig. 6, along with the X-ray spectrum and the radio upper limit ($`F_\nu <100\mu Jy`$, where $`F_\nu `$ is the flux density at 20 cm) derived from VLA observations (K.Kellerman, private communication). To put our data into perspective, they have been shifted to the rest frame and compared with the SED the nearby galaxy NGC 6240 (Hasinger 2001), which has no AGN signatures in its optical spectrum but shows clearly a buried AGN emerging at higher X–ray energies Vignati et al. (1999).

The inferred metallicity for this object is $`Z_{}`$ typical of high redshift AGN but on the high side. In fact, looking at our diagnostic diagram, CDF–S 202 has a higher metallicity than any of the high–z radio galaxies of Vernet et al. (2001); Hamann & Ferland (1993). Indeed, it has been found that there is a metallicity evolution such that for redshift $`z>3`$ radio galaxies, the metallicity is $`<2\times Z_{}`$ (de Breuck et al., 2000). This relatively high metallicity is consistent with a high star formation rate during these early epochs as the bulge and central black hole are formed.

Assume now that the $`FeK\alpha `$ line arises in the obscuring cloud. We will now estimate various quantities of the obscuring region using either standard parameters or, where possible, parameters inferred from our data. To simplify the calculation we assume that the obscuring cloud is spherical. From other studies (Gilli et al., 2001) we find that the Type 2 to Type 1 ratio is $`10`$ at high redshift and therefore it is a reasonable assumption that the obscuring torus is an almost totally enclosing cloud.

We define the ionization parameter, U, in the usual manner as

$$U=\frac{L_X}{nr^2}$$
(1)
in an obscuring material of density, $`n`$, at distance, $`r`$ from the source. For standard values U $`=10^2`$ erg cm s-1 (Matt et al., 1996).

For the inferred absorbing column, N, of the spherical uniform cloud, we find

$$N=nr.$$
(2)
For a typical inferred absorbing column we use of $`N=10^{24.5}`$ cm-2 that is consistent with canonical estimates expected for Type 2 QSOs and also with our inferred column densities in Section 4.

It follows directly that the radius of the cloud is

$$r=\frac{L_X}{NU}1\mathrm{p}\mathrm{c}(L_X/10^{45}\mathrm{erg}\mathrm{s}^1)(10^2\mathrm{erg}\mathrm{cm}\mathrm{s}^1/U)(10^{24.5}\mathrm{cm}^2/N),$$
(3)
and the density of the cloud is

$$n=\frac{N^2U}{L_X}.$$
(4)
The mass estimate of the obscuring cloud, $`M_{cloud}`$, is

$$M_{cloud}=(\frac{4\pi }{3})\mu m_Hnr^3=(\frac{4\pi }{3})\mu m_H(\frac{L_x^2}{NU^2})$$
(5)
where $`\mu `$ is the mean molecular weight of the obscuring material. We then estimate the mass in the obscuring region $`M_{cloud}`$, to be

$$M_{cloud}1\times 10^5M_{}(L_X/10^{45}\mathrm{erg}\mathrm{s}^1)(10^2\mathrm{erg}\mathrm{cm}\mathrm{s}^1/U)(10^{24.5}\mathrm{cm}^2/N_H).$$
(6)
We now assume that the velocity dispersion outside the obscuring cloud can still be dominated by influence of the black hole. This will not always be the case but here the numbers are sufficiently interesting and consistent to analyze the problem further. Then, the velocity dispersion, $`\sigma _{cloud}`$, just outside the obscuring region is given by

$$\sigma _{cloud}^2=(\frac{GM_{BH}}{r})$$
(7)
where $`M_{BH}`$ is the mass of the black hole. It follows directly that

$$\sigma _{cloud}^2=(\frac{GM_{BH}}{L_X})(NU)$$
(8)
We further rewrite the black hole mass in terms of the Eddington luminosity given by

$$M_{BH}=(\frac{\sigma _T}{4\pi Gcm_H})L_{EDD}$$
(9)
and then

$$\sigma _{cloud}^2=(\frac{\sigma _T}{4\pi cm_H})(\frac{L_{EDD}}{L_X})(NU)$$
(10)
Now we can estimate the velocity dispersion, just outside the obscuring region is

$$\sigma _{cloud}2500kms^1[L/L_{EDD}]/10^2)^{1/2}(U/10^2\mathrm{ergcms}^1)^{1/2}(N/10^{24.5}\mathrm{cm}^2)^{1/2}.$$
(11)
We have assumed here that the black hole is generating X–rays with an efficiency of $`1\%`$ relative to the Eddington luminosity which we justify as follows. As discussed by Elvis et al. (1994) the ratio of X–ray luminosity to bolometric luminosity, $`L_{bol}`$, is 10%. Here we assume $`L_{bol}/L_{EDD}`$ is also 10%. The inferred mass of the black hole is then

$$M_{BH}8\times 10^8M_{}(10^2/[L_X/L_{EDD}])(L_X/10^{45}\mathrm{ergs}^1)$$
(12)
This explains the rather large width of the narrow lines that originate outside the obscuring region. That such a dense cloud closely covers the nucleus in high redshift Type 2 objects is to be expected since in the galaxy formation process large amounts of gas are present in the bulge-forming black-hole-growing epoch. The encapsulation of the nucleus probably increases with redshift.

We now discuss our analysis and analyze the energetics of the line emission. Following the standard scenario,we assume that:(1) the ratio of UV to X-ray luminosity is 10 (Elvis et al., 1994);(2) $`10\%`$ of the UV continuum escapes, consistent with the ratio of Type 2/Type 1 $`10`$ at high redshift; (3) $`10\%`$ of the continuum flux is re-radiated isotropically into lines and (4) the covering factor of the narrow line region is $`10\%`$. We find that the line flux should be $`10^2L_X`$. The actual line flux is $`L_{line}2\times 10^{43}`$erg s-1 roughly consistent with the above model. In a similar calculation we use the observationally derived relation $`L_{Ly\alpha }10^3L_{bol}`$ (Vanden Berk et al., 2001, T. Heckman, private communication) where $`L_{bol}`$ is the bolometric luminosity of the QSO and $`L_{Ly\alpha }`$ is the narrow line luminosity in $`Ly\alpha `$. We then find that CDF-S 202 has an inferred luminosity from the Ly$`\alpha `$ line of $`L_{bol}=2\times 10^{46}`$ erg s-1. In addition, the X-ray luminosity inferred from the line strength and the observationally determined value ($`L_x/L_{bol}=0.1`$ (Elvis et al., 1994) is $`L_x=2\times 10^{45}`$ erg s-1. This constructs a consistent picture of CDF-S as an enshrouded Type2 QSO.

In general for observations to support such an analysis of Type 2 QSOs physics as given above we would like to study in the future a significantly lower redshift sample of X-ray selected QSO 2 to attempt to infer the depth of the potential well via the rotation curve and the central stellar velocity dispersion using, say, STIS observations. Imaging observations of such objects in CDF-S with HST can give important morphological constraints (see Schreier et al., 2001) and possibly an estimate of the bulge mass which can also be used to estimate the black hole mass (Magorrian et al., 1998; Gebhardt et al., 2000). In addition, deep Chandra and XMM observations of high-redshift Narrow Line Radio Galaxies (NLRG) can give insight into the physics of Type 2 QSOs. In unified models NLRG are the radio loud equivalent of Type 2 QSOs. It has been proposed by Ridgeway et al. (2001) that a few percent of the Lyman-break galaxy population (Steidel et al., 1999) may be Type 2 QSOs. X-ray studies of a well-selected subsample of these Lyman-break systems are also indicated.

It is expected from models that the radiation absorbed in the cold obscuring torus to be re-radiated in the far infra-red. IRAS 09014+4109 is such an object. Interestingly, it is the only hyperluminous infrared galaxy to be detected as an obscured AGN (iwasawa2001, Iwasawa et al. 2001). Deep IR imaging and spectroscopy are essential to constrain the contribution of QSO 2s to the IR background. Current thinking is that the AGN contribution may approach that due to star formation if sufficient Type 2 QSOs contribute. For these powerful buried QSOs at high redshift the Type2/Type1 ratio is unknown but may continue to increase with redshift giving a major contribution to the IR background. In a related issue these Type2 QSOs may be powerful submillimeter sources. We already know that a fraction of optically identified SCUBA sources are AGN (Barger et al., 1999; Smail et al., 1999) although the bulk of the sub-mm population is not likely to be powered by AGN, as suggested by the non-detections of SCUBA sources with Chandra (Hornschemeier et al., 2000). However, we must await the Atacama Large Millimeter Array (ALMA) to study them in detail in the CDF-S.

Depending on the assumed cosmology and X-ray transmission or reflection scenario, the intrinsic 2-10 keV rest frame luminosity of CDF-S 202 varies from $`3\times 10^{44}`$ to $`3\times 10^{45}`$ erg s-1. Even assuming the lowest luminosity value, CDF-S 202 is a powerful obscured AGN, beyond the knee, or break in the slope, of the AGN X-ray luminosity function at $`L_{,X}=10^{43.7}ergs^1`$ (Miyaji et al., 2000).Above this break luminosity, $`L_{,X}`$ the X-ray selected AGNs are QSOs. Let us now discuss the implications of CDF-S 202 for the origin of the X–ray background (Comastri et al., 1995). Based on the population synthesis models described by Gilli et al. (2001)222Gilli et al. (2001) adopted $`H_0`$=50 km/s/Mpc, $`\mathrm{\Omega }_m=1`$ and $`\mathrm{\Omega }_\lambda =0`$. Here we quote their predictions correcting for the different cosmology adopted in this paper., obscured AGN with $`L_{210}>3\times 10^{44}`$ erg s-1 and $`N_\mathrm{H}>10^{22}`$ cm-2 should make up a significant part ($`30\%`$) of the hard X-ray background. About 70% of them should be observed at $`z=13`$, while 15% is expected at higher redshifts, assuming the AGN space density to decrease above $`z3`$ as found in optical and radio surveys (Schmidt, Schneider & Gunn 1995; Fan et al. 2001; Shaver et al. 1999). On the same assumption we expect 8 obscured QSO with intrinsic luminosity $`L_{210}>3\times 10^{44}`$ erg s-1, $`N_\mathrm{H}>10^{22}`$ cm-2 and $`z>3`$ to be observed in the 1 Msec CDF-S. We will have to await further analysis of these objects in CDF-S to understand the contribution of the QSO 2 population relative to the other sources that make up the X-ray background.

## 6 Conclusions and Future Work

We conclude that in the Chandra Deep Field South 1Msec exposure we have found a QSO 2 at redshift 3.700 (CDF-S 202). There is no generally accepted definition of a Type 2 QSO. We suggest that CDF-S 202 defines the class well by optical spectrum, X-ray spectrum and X-ray luminosity. Its luminosity ($`10^{45\pm 0.5}`$erg s-1 in the 2–10 keV band), X–ray spectrum, narrow permitted lines ($`1500`$ km s-1), and undetected continuum (to a limit of $`3\times 10^{19}`$ erg cm-2 s-1 Å-1) make it a classic case. There are several other candidates in the field that have hard spectra and high redshift. Clearly, in Type 2 QSOs the $`FeK\alpha `$ feature can be used in conjunction with deep optical and IR faint object spectroscopy to determine redshifts. CDF-S 202 has the highest redshift $`FeK\alpha `$ line spectrum yet observed (Reeves et al., 2001).

We have discussed in the paper the implications for the X-ray background, the infrared background, the origin of the UV continuum in Type 2 objects and the relation of the growth of black holes to bulge and galaxy formation. Currently we aim to both increase the sample and to observe CDF-S 202 further with: IR spectroscopy and imaging, HST, millimeter facilities and XMM.

C.N. thanks Tim Heckman, Julian Krolik, David Neufeld, David Strickland and Tahir Yaqoob for stimulating discussions. G. Hasinger acknowledges support under DLR grant 50 OR 9908 O. R. Giacconi and C. Norman gratefully acknowledge support under NASA grant NAG-8-1527 and NAG-8-1133.