Answers.Body: <p>(Disclaimer: although I have never seen a formal definition of <em>unknown search space</em>, 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 <strong>unknown</strong> environment (see chapter 2, p. 44, of Norvig and Russell's AI book), but that definition is different from the one below.)</p>
  <p>An <strong>unknown search space</strong> is a search space (i.e. a set of objects of interest with some relationship between them) where you do not know anything about</p>
  <ol>
  <li>where the best/worst solutions/objects are (i.e. where the <a href="https://en.wikipedia.org/wiki/Maxima_and_minima" rel="nofollow noreferrer">local/global minima/maxima</a> are) and/or</li>
  <li>how these objects are related.</li>
  </ol>
  <p>A typical example where the search space is known is the search space associated with a <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1135&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">path-finding problem</a> 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 <strong>exploiting</strong> your knowledge of it (you can use e.g. depth-first search). Think about finding the shortest path from one city to another.</p>
  <p>In other (most) cases, you may not know anything about the relationship between 2 or more solutions/objects, unless you <strong>explore</strong> the search space (i.e. take random actions or some other more informed actions).</p>
  <p>For example, let's suppose that you want to <em>search</em> for a function of the form <span class="math-container">$f : [0, 1]^{28 \times 28} \rightarrow \{0, 1\}$</span> from a set of functions <span class="math-container">$\mathbb{F}$</span>, i.e. <span class="math-container">$f \in \mathbb{F}$</span>. In this case, you can think of a function <span class="math-container">$y = f(\mathbf{x}) \in \mathbb{F}$</span> as a classifier of greyscale images, where <span class="math-container">$\mathbf{x} \in  [0, 1]^{28 \times 28}$</span> is a <span class="math-container">$28 \times 28$</span> greyscale image and <span class="math-container">$y \in \{0, 1\}$</span> is the class (name) of the object in the image <span class="math-container">$\mathbf{x}$</span> (in this case, we assume there's only one main object in the image <span class="math-container">$\mathbf{x}$</span>). In machine learning, <span class="math-container">$\mathbb{F}$</span> could be represented by a set of neural networks (with a specific architecture, e.g. number of layers), and <span class="math-container">$f \in \mathbb{F}$</span> 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 <strong>explore</strong> the search space in some way, for example, by changing some of the parameters of one neural network <span class="math-container">$f \in \mathbb{F}$</span> to get another neural network <span class="math-container">$f' \in \mathbb{F}$</span> and see how that affects, for example, your accuracy at classifying images.</p>
  <p>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 <em>usually</em> used to solve problems with unknown search spaces. For example, test case selection or finding a policy for an agent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-12T15:21:56.903Z
Answers.Text: See also [Bayesian Optimization with Unknown Search Space](https://papers.nips.cc/paper/2019/file/ccf0304d099baecfbe7ff6844e1f6d91-Paper.pdf) by Huong Ha et al. It seems that their definition is consistent with the one above that I gave. However, [this paper](https://arxiv.org/pdf/2009.02539.pdf), 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-12T15:28:27.607Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-13T06:35:39.500Z
Answers.Text: I sent your answer to the author of the article and he accepted your answer.
  please edit your answer and remove the disclaimer section.
Answers.UserDisplayName: Commander
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-13T12:59:50.530Z
Answers.Text: @Commander Hello. It may still be a good idea to leave the disclaimer because, even though the author(s) of that article agrees with my definition (which is not completely precise in a mathematical sense, which I acknowledge), this definition may not be applicable to all cases, i.e. some other author may have something else in mind. People reading this answer, hopefully, will also read these comments. Anyway, thanks for confirming that this definition is what the original authors of the paper had in mind.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-12T15:03:38.793Z
Answers.LastActivityDate: 2021-10-12T15:15:37.720Z
Answers.LastEditDate: 2021-10-12T15:15:37.720Z
Answers.UserDisplayName: nbro
Body: <p>In the article <a href="https://link.springer.com/content/pdf/10.1007/s00521-015-1870-7.pdf" rel="nofollow noreferrer">Multi-Verse Optimizer: a nature-inspired algorithm for global
  optimization</a> (DOI 10.1007/s00521-015-1870-7), it's written</p>
  <blockquote>
  <p>The results of the real case studies also demonstrate the potential of MVO in solving real problems with unknown search spaces</p>
  </blockquote>
  <p>where MVO stands for Multi-Verse Optimizer.</p>
  <p>What does &quot;unknown search spaces&quot; mean in the context of Evolutionary Algorithms and, especially, in the context of the Multi-Verse Optimizer?</p>
  
Tags: <terminology><search><evolutionary-algorithms><neuroevolution>
Title: What does "unknown search spaces" mean in the context of Evolutionary Algorithms?
UserDisplayName: Commander
ThreadText: # What does "unknown search spaces" mean in the context of Evolutionary Algorithms?
  
  (Asked by: username_0 on 2021-10-12)
  
  In the article [Multi-Verse Optimizer: a nature-inspired algorithm for global
  optimization](https://link.springer.com/content/pdf/10.1007/s00521-015-1870-7.pdf) (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?
  
  **Tags:** terminology, search, evolutionary-algorithms, neuroevolution
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-10-12. Score: 2 | Accepted answer
  
  (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](https://en.wikipedia.org/wiki/Maxima_and_minima) 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](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1135&rep=rep1&type=pdf) 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.
  
  > **Comments:**
  > **username_1**: See also [Bayesian Optimization with Unknown Search Space](https://papers.nips.cc/paper/2019/file/ccf0304d099baecfbe7ff6844e1f6d91-Paper.pdf) by Huong Ha et al. It seems that their definition is consistent with the one above that I gave. However, [this paper](https://arxiv.org/pdf/2009.02539.pdf), 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.  
  > **username_1**: 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.  
  > **username_0**: I sent your answer to the author of the article and he accepted your answer. please edit your answer and remove the disclaimer section.  
  > **username_1**: @username_0 Hello. It may still be a good idea to leave the disclaimer because, even though the author(s) of that article agrees with my definition (which is not completely precise in a mathematical sense, which I acknowledge), this definition may not be applicable to all cases, i.e. some other author may have something else in mind. People reading this answer, hopefully, will also read these comments. Anyway, thanks for confirming that this definition is what the original authors of the paper had in mind.  
  
  ---
  
  