# What does "unknown search spaces" mean in the context of Evolutionary Algorithms?

In the article Multi-Verse Optimizer: a nature-inspired algorithm for global optimization (DOI 10.1007/s00521-015-1870-7), it's written

The results of the real case studies also demonstrate the potential of MVO in solving real problems with unknown search spaces

where MVO stands for Multi-Verse Optimizer.

What does "unknown search spaces" mean in the context of Evolutionary Algorithms and, especially, in the context of the Multi-Verse Optimizer?

(Disclaimer: although I have never seen a formal definition of unknown search space, here is my attempt to define it based on my knowledge of search and search algorithms in machine learning and evolutionary algorithms; I am aware of a definition of unknown environment (see chapter 2, p. 44, of Norvig and Russell's AI book), but that definition is different from the one below.)

An unknown search space is a search space (i.e. a set of objects of interest with some relationship between them) where you do not know anything about

1. where the best/worst solutions/objects are (i.e. where the local/global minima/maxima are) and/or
2. how these objects are related.

A typical example where the search space is known is the search space associated with a path-finding problem where you know the start and goal locations, the intermediate locations that you can go through from the start to the goal locations, and the distance between locations. If you have this information, you can find the optimal path from the start to the goal location by just exploiting your knowledge of it (you can use e.g. depth-first search). Think about finding the shortest path from one city to another.

In other (most) cases, you may not know anything about the relationship between 2 or more solutions/objects, unless you explore the search space (i.e. take random actions or some other more informed actions).

For example, let's suppose that you want to search for a function of the form $$f : [0, 1]^{28 \times 28} \rightarrow \{0, 1\}$$ from a set of functions $$\mathbb{F}$$, i.e. $$f \in \mathbb{F}$$. In this case, you can think of a function $$y = f(\mathbf{x}) \in \mathbb{F}$$ as a classifier of greyscale images, where $$\mathbf{x} \in [0, 1]^{28 \times 28}$$ is a $$28 \times 28$$ greyscale image and $$y \in \{0, 1\}$$ is the class (name) of the object in the image $$\mathbf{x}$$ (in this case, we assume there's only one main object in the image $$\mathbf{x}$$). In machine learning, $$\mathbb{F}$$ could be represented by a set of neural networks (with a specific architecture, e.g. number of layers), and $$f \in \mathbb{F}$$ would be one of these specific configurations. In this context, usually, we do not know anything about the relationship between these neural networks, so the search space is unknown. So, you need to explore the search space in some way, for example, by changing some of the parameters of one neural network $$f \in \mathbb{F}$$ to get another neural network $$f' \in \mathbb{F}$$ and see how that affects, for example, your accuracy at classifying images.

This definition also applies to evolutionary algorithms (and, although I have not read that paper, I assume it also applies to that context). In fact, evolutionary algorithms are usually used to solve problems with unknown search spaces. For example, test case selection or finding a policy for an agent.

• See also Bayesian Optimization with Unknown Search Space by Huong Ha et al. It seems that their definition is consistent with the one above that I gave. However, this paper, which cites the previous one, seems to suggest that an unknown search space is a search space where you really don't know what it contains (i.e. which objects) and that you may need to define a search space arbitrarily and this search space that you chose may not contain the solution at all.
– nbro
Oct 12 at 15:21
• They write "When the search space is unknown, one heuristic solution is to specify it arbitrarily. However, there are two problems: (1) an arbitrary search space that is finite, no matter how large, may not contain the global optimum (2) optimisation efficiency decreases with increasing size of the search space.". This still seems consistent with my definition above, but here they put an emphasis on knowing which objects it contains. This is still a bit vague. It's possible that the authors of the paper mentioned by the OP had in mind a different definition of unknown search space.
– nbro
Oct 12 at 15:28