MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Uniformly distribute a population in a given search space

I am trying to uniformly distribute a finite number of particles into a 2D search space to get me started with an optimization problem, but I am having a hard time doing it. I am thinking that it might have something to do with convex sets, but I might as well be totally off, so I am asking you guys of a proper way to do it .

Edit: Ok, so I have to implement the Particle Swarm Optimization algorithm in order to get the polynomial input for Baker's algorithm and to get started with PSO, I have to uniformly distribute the particles in the search space (the initial example I got was of the distribution of particles inside of a cube, but that's kind of vague for me). What does it mean to uniformly distribute in the search space?

-
What's wrong with choosing one coordinate uniformly and then another? – Qiaochu Yuan Jan 13 2010 at 18:15
If your space is irregularly shaped, use rejection sampling (en.wikipedia.org/wiki/Rejection_sampling). See also mathoverflow.net/questions/9854/… – Steve Huntsman Jan 13 2010 at 18:19
Well, what if the search space is a rectangle, say with a 2^16 size ? I guess your solution will still work. – hyperboreean Jan 13 2010 at 20:30
@Leonid: yes you are right ... I am not talking about the probability density function, but rather how to uniformly distribute those points in the space. – hyperboreean Jan 14 2010 at 17:57
@Hyperboreean -- you should try to indicate what you mean by "uniformly distribute", perhaps with an example of the sort of thing you're looking for. I suspect you're not getting any answers because no one is sure what you want. You should also explicitly ask a question --- our experience is generally that the effort of putting a problem into the explicit form of a question really pays off! – Scott Morrison Jan 15 2010 at 21:14
show 1 more comment

Despite the lack of formalization in your question I'm going to take a guess that you don't really want points that are distributed uniformly at random, as that tends to result in clusters and voids that you probably want to avoid. Rather you may want to be using something like Lloyd's algorithm: start with randomly generated points but then repeatedly move each point to the centroid of its Voronoi cell, resulting in a set of points that are nearly equally spaced across the domain and that, within the domain, are spaced in a pattern approximating a hexagonal close-packing.

-

Since you are working in 2D, how about choosing the center of the 2D space as the center of an imaginary circle and the distance between the center and one of the sides as the radius. For each quadrant of the circle generate some random number of individuals, at a random distance from the center. That way, you have a fairly good representation of the search space, I think.

-

It sounds to me like this problem is a a candidate for quasi-random sequences: use, for example Sobol, to distribute the points very evenly over the search space (avoiding the clustering that would occur from using randomly chosen points).

-