# Centroid of nearest-neighbours on a hypersphere as a method for applying crossover in genetic algorithms

I am currently building a genetic algorithm to tune n parameters where n will probably be in the range of 3 ≤ n ≤ 8 but could be up to 15.

I would like my initial population N (let's say N=1000) to be evenly dispersed across the input space. This is equivalent to evenly distributing N points on the surface of an n-dimensional hypersphere (a quite difficult problem but here's a pretty good solution for anyone who's interested: http://www.academia.edu/17166201/Uniform_distribution_of_points_on_a_hyper-sphere_with_applications_to_vector_bit-plane_encoding).

When calculating the next generation I surmised that the most effective way to combine parents would be to calculate the centroid, on the surface of the hypersphere, between some m nearest-neighbour parents. The larger m is, the fewer new points we would add. The rest being calculated in a similar fashion but from random parents. Another option would be to interpolate between the m nearest-neighbour parents, weighting the centroid nearer to fitter parents, but this may reduce the randomness too much.

My problems are:

a) I am not sure how to do this in n-dimensions and also make sure that the point remains on the surface.

b) I am not sure how to correctly subdivide the surface.

I can't see anything wrong with my logic but I haven't been able to find any papers, code, etc. that use a similar cross-over/mutation. I am quite new to this field so perhaps I am not aware of the correct terminology.

• This is an interesting, general problem. The question seems to be more about geometry than genetic algorithms per se, so you might consider editing the title/tags to include something about centroids/interpolation on a sphere. This might attract more answers, and could also help people who have related (but not GA-specific) problems to find your post later. Jun 25, 2016 at 4:18
• Thanks for the feedback. I'm new so its always good to learn how to improve my stackexchange 'question-asking technique'. Jul 4, 2016 at 15:08

In Euclidean space, the weighted average of a set of input points is easy to calculate and has a nice, closed form solution. As you mention, it's not possible to perform the same procedure on the sphere, because the resulting point would no longer lie on the surface of the sphere.

A quick and dirty approach is to simply take the standard weighted average, then renormalize the resulting vector so that it lies on the surface of the sphere. This is an approximate solution that might work in certain cases. There is precedent in the literature.

A more principled solution is to generalize the weighted average to spherical geometries by recasting it as an optimization problem. In Euclidean space, the weighted average can be written as the point that minimizes the weighted sum of squared distances to each of the input points. The solution to this optimization problem is the familiar expression for the weighted average. Say we want to take the weighted average of points $\{x_1, ..., x_n\} \in \mathbb{R}^d$. The corresponding weights for each point are given by $\{w_1, ..., w_n\}$. The weights are nonnegative and sum to $1$. The weighted average $a^*$ is given by:

$$a^* = \underset{a}{\text{argmin}} \sum_{i=1}^{n} w_i \| x_i - a\|^2$$

This problem can be generalized to spherical geometries by replacing the Euclidean distance with the geodesic distance on the surface of the sphere (i.e. how far you'd have to travel along the surface of the sphere to get from one point to another).

$$a^* = \underset{a}{\text{argmin}} \sum_{i=1}^{n} w_i D_S(x_i, a)^2$$

Here, $D_s(x_i, a)$ denotes the geodesic distance between points $x_i$ and $a$ on the surface of sphere $S$. BTW, this formulation of the problem is for (hyper)spheres of any dimension, not just 3.

I'm not aware of a closed form solution for this problem, but the following paper gives two iterative algorithms. They report runtimes of a few hundred microseconds for taking the weighted average of 12 points on a 3-sphere. They also discuss how to perform interpolation on the surface of a sphere, which seems relevant to some of the use cases you're considering.

Buss and Fillmore (2001). Spherical Averages and Applications to Spherical Splines and Interpolation.

• Firstly I have to apologise, it was rude to ask a question right before I went on holidays for a week. Sorry for the late reply. Your answer is great, and that paper is extremely informative. I'll try out their method. You mentioned that there was a literary precedent for taking the weighted average as a crossover method but I have only seen papers where the weighted average of two parents is taken, never m nearest-neighbours. Perhaps I have just not found them. Surely this method would cover more of the input space and lead to a faster convergence. Jul 4, 2016 at 15:02
• I should clarify...the precedent I mentioned wasn't for genetic algorithms in particular, but for that particular way of calculating the average of points on a sphere. Buss&Filmore have some citations for this in the introduction. Your approach sounds interesting, hope it works Jul 4, 2016 at 16:04
• OK, good to know. I'm going to try it out 'quick and dirty' first; using the weighted average and re-normalizing the vectors. Jul 6, 2016 at 12:05