I am reading a paper titled "A Robust Real-Coded Genetic Algorithm using Unimodal Normal
Distribution Crossover Augmented by Uniform Crossover : Effects
of Self-Adaptation of Crossover Probabilities" by Ono, Kita, and Kobayashi. You can download the paper from CiteSeerX.
In the discussion about the UNDX operator on page 2, Ono et. al use the phrase "vectors $\vec{e}_2$, …, $\vec{e}_{n_{param}}$ are the orthogonal basis vectors spanning the subspace perpendicular to vector $\vec{e}_1$".
I do not have the mathematical background to interpret this phrase. I need to understand it so I can code UNDX and similar genetic crossover operators. What does it mean, and how do I do it?
My best interpretation after consulting Wikipedia pages for concepts like basis and spanning set is that I'm supposed to build a rotation and translation of an identity matrix so that one of my points is the origin and the vector to one of the other points is one of my axes. I do not know whether this interpretation is correct. Trying to follow this idea lead to a bunch of 3D specific answers for building rotation matrices from two vectors, but I need a general approach that can handle any number of dimensions.
Am I even on the right track?
EDIT
I have read the Wikipedia pages on the Gram-Schmidt process. It seems easy enough to apply Gram-Schmidt to the UNDX process in the paper, but there is also a UNDX-m process proposed in this paper by Kita, Ono, and Kobayashi. Another paper by Deb, Joshi, and Anand also describes UNDX-m and proposes a modification to it called PCX. Both of these processes allow for an arbitrary number of points to be used in the recombination. Both of them use the same sort of language to describe this a set of vectors $\left\{\vec{e}^{\left(i\right)} \forall 1 \le i \le n_{param} \right\}$, and I am confused as to how I can apply the Gram-Schmidt process to a set of arbitrary points.
I will use the example of PCX since access to that paper is free. Suppose that my number of points $\mu=10$, and I choose the ten blue parent points marked as blue diamonds in the figure below. The red square represents the mean vector $\vec{g}$ of the ten parents. The green arrow represents the direction vector $\vec{d}^{\left(p\right)}$. PCX requires knowing the $\vec{e}^{\left(i\right)}$ vectors that are the "orthonormal bases that span the subspace perpendicular to $\vec{d}^{\left(p\right)}$."
How do I determine the $\vec{e}^{\left(i\right)}$ vectors described above from the vector $\vec{d}^{\left(p\right)}$ and the remaining nine parent points? Applying Gram-Schmidt using all possible $\vec{d}^{\left(i\right)} \equiv \vec{p}^{\left(i\right)} – \vec{g}$ as the set of vectors does not seem to work…
EDIT
I think I figured out the answer to my edit. I'm not sure why it took so long to click >_<
I had been assuming that there had to be something special about the basis calculated so that points outside of those described could not be generated. But that is not the case; the only necessity is that this basis be able to generate vectors in the same directions as the points used. This means that if all the points chosen happen to lie on a hyperplane, there should only be enough orthogonal vectors needed to describe the plane.
If this is true, then it does not matter which $n_{param} – 1$ of the remaining $\mu – 1$ points are chosen for the Gram-Schmidt process. So long as the vectors do not lie along a line, they will generate a new basis vector, and in conjunction they will describe a spanning set possible of describing any and all of the points generated.
I can see why people might have found my bewilderment confusing now : )
Best Answer
Take your vector and extend it to a basis. Then, apply Gram-Schmidt to the remaining vectors and you will get an orthonormal basis to the vector's orthogonal complement.