Let's consider that for a given problem, a configuration is a vector of several hundred dimensions in the problem space. A score can be assigned to each configuration. An optimal solution to the problem is a configuration with a score of 1. The search space is manifestly too large to explore exhaustively in search of an optimal solution.
In this particular instance, I am not trying to find a solution, I have at my disposal various heuristics (simulated-annealing, ant colonies, etc) that serve me well on that end. However, I want to understand and characterize the search space better. So far, what I have attempted, is to generate some configurations randomly. How could I quantify how representative the sampling is? Do you think I am using the right approach? And finally, how would you suggest that I proceed further?
Could you define what a dimension is: real or discrete values? Have you tried genetic algorithms? There is much theory regarding how to select the initial population.
I don't want here to find a solution, I try to characterise my search space. Dimensions are discrete but I think the problem would be the same with real values. To summerize I have random configurations and their score and I want to know how representative of the whole space they are.
Here is my intuition without any proof that it works. Assume your search space is divided into set of regions. Then, a sampling approach is representative if it favours no region over the other. Depending on the problem on hand, dividing the space into regions can be done on the fly without preprocessing.
I typically work backward from Nyquist-Shannon sampling theorem to determine the amount of under-sampling (or under-representation for that matter). The first problem here then becomes how do I represent my data space as a set of signals because what you might have in hand may not be time variant. The time dimension in this case needs to be substituted by the appropriate dimension.
- Badges
- Science topic