## Representation of Search Spaces

Assume we seek the cheapest set of emission abatement options (which represent individual 'measures' or combinations of these) for different countries, to meet certain air quality targets. One of the simplest representations of the search space would be a set of Boolean values, telling whether a certain measure shall be implemented or not. However, measures that belong to the same technology group may exclude each other. For instance, we might choose to implement either medium efficient electrostatic precipitators for all hard coal power plants in a certain region, or high efficient (but more expensive) ones, but not both at the same time. Hence, the Boolean representation leads to infeasible solutions in the search space, which is obviously disadvantageous.

To avoid gaps in the search space, every solution could for instance be represented by integer values, one for each technology. For example, zero might stand for 'implement no measure', one for 'medium efficient EP', and two for 'high-efficient EP'. Of course, this way two measures that can be applied to the same technology at the same time have to be treated like three: again zero for no measure, one for the first measure, two for the second, three for both.

Actually there is a representation of the search space that is for most cases even better suited. The basic idea is to rank potential measures in order to ensure that first the 'most efficient' ones are taken. The most important part then is to find out by some optimization technique, how the efficiency of measures to progress toward the target can be quantified in a manner most suitable to the problem.. More precisely, the optimization's objectives are the parameters used to quantify the difference of efficiency of two alternative measures. If this value divided by the difference of costs of the measures is big enough, the first measure is superior to the second one.

More precisely, we denote the technologies in a country c by

and those measures, that can be applied to technology t3c by M' = {m''0,..., m',K ^'^j where m'f means not to implement any measures. For the emission reduction of pollutant p that is caused by a measure m that can be applied to a technology in region c we write Ae«. Now we can define the efficiency of a measure by

We can interpret the weighting factors Ac,p by a para-metrization of a part of the search space, that is by a alternative representation of it, because the following algorithm describes how to map any set of weights to a solution. The first big advantage is that this part is much smaller than the original search space and still covers all interesting regions, as it is demonstrated below. Additionally, the solutions are now ordered in a sensible p p manner, because a higher weight also leads to a solution with better (i.e., more efficient) performance in controlling emissions. However, it is beyond the scope of this paper to illustrate the actual application in more detail.

To map the set of weights to the search space, we define the following algorithm:

1. Start with a solution that has least costs. (Note: some measure may have negative costs.)

2. Loop through all technologies in all countries, t'c.

3. Give the measure for technology t'c that is chosen by the solution, the name ml. Collect the subset M C M'c containing all measures m2 with v(m2) - v(ml) > 0.

4. Drop all measures m2 in M with c(ml) = c(m2) and (v(m2) — v(m1))/(c(m2) — c(ml)) < 1, where c maps a measure to its costs.

5. If M is empty, implement the measure ml for technology tcc and return to step 2.

6. Implement the measure with least costs in M instead of ml and return to step 3.

Obviously, the algorithm terminates, because the set of technologies is finite and in step 3 M is smaller than M'c because at least ml is dropped. Furthermore, the solution is pareto-optimal in terms of the objectives costs and emission per pollutant and country, where pareto-optimality is defined as not being inferior to another solution in respect ofat least one objective, if the score for all other objectives is the same. The proof's idea that all solutions of the new representation are pareto-optimal is rather simple, although we will only sketch it here: first we note that if s is a solution found by the algorithm, then any change in a technology's measure that increases v by some amount costs even more money. A change in another technology's measure that saves money will lead to an even bigger loss in respect of v:if ml,..., mn are the measures that are successively taken in step 6 and m is cheaper than mn and m was eliminated in step 4 because of mj we get v(mc + l) — v(mc)>c(mi + l)-c(m) for all 0< c < n and v(m) - v(mj) < c(m) - c(mj), because m is more expensive because of step 3. The first inequation gives a telescoping sum, that gives us v(mn) — v(mj) > c(mn) — c(mj) and the second one means v(m) < v(m) + c(m) — c(m). Together, this tells us v(mn) — v(m) > c(mn) — c(m) — c(m) + c(m) = c(mn) — c(m), which proves the previous statement.

For the sake of completeness, it should be mentioned that this parametrization does not cover all pareto-optimal solutions. Assume, for example, that we want to reduce emissions ofp in c by l0t and we have measures with tuples of reduction and costs of (l0t, 50 €) and (201, 70 €), then the algorithm will always choose the second measure. Nevertheless, this kind of'fine-tuning leads to the so-called 'knapsack problem' which is NP-complete. This means, in short, that based on current knowledge no algorithm exists, which is able to solve this problem in appropriate time -however, this theory has yet to be proved. Of course, even solutions with best relation of emission reduction and costs might be preferred, instead of only looking at reduction thresholds and costs, because at least for small changes in emissions, the reduction of external costs is more or less proportional to the reduction of emissions. 