Search Space for Population Metaheuristic Optimization Problem
-
29-09-2020 - |
質問
Given that x objects (repetition allowed) can be arranged into y configurations, and that the population size is N, I am uncertain as to whether the size of the search space is |S| = |(y^x) * N| or |S| = |(y^x)^N|.
|y^x| comes from basic combinatorics: it is the number of ways to arrange |x| objects into |y| configurations.
As an example, suppose x = (1, 2, 3, 4) and y = (1, 2, ... 5) and N = 100. Clearly, |x| = 4 and |y| = 5. The xs are drawn from some probability distribution (e.g., uniform). A configuration might look like
1 1 3 2 4
Another might be
4 3 1 1 3
for some previously-specified probability distribution. The underlying metaheuristic algorithm generates N = 100 such configurations randomly.
I am just unsure on how to incorporate N.
解決
There are $|x|^{|y|}$ configurations. Then you want to generate $N$ configurations. By the same reasoning, there are $(|x|^{|y|})^N$ ways to do that.