0
$\begingroup$

I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb.

Basically, from what I understand, given a set of points on a Pareto-front, we need to project the points onto a hyperplane with a direction vector $\eta$. Doing this will give the new crowding distance $d'$ based on the locations of the individualson the hyperplane with direction $\eta$.

To illustrate, see the figure below.

Biased crowding distance approach

My question is simple: how do we obtain the hyperplane given a user-specified direction vector $\nu$? Is it simply by getting the perpendicular of the direction vector?

And a follow up question would be: how would I project the points onto the hyperplane? If $p$ is the point and $v$ is the vector representing the hyperplane, is it correct that the new location of $p$, call it $p'$ is $\frac{v.x(p.x) + v.y(p.y)}{||v||^2} (v.x, v.y)$ based on this?

Thanks and any information would be very helpful.

$\endgroup$
1
$\begingroup$

I'm not sure if this should be considered a computer science question or not, it seems more an algebra question than anything else.

A vector is a direction vector of a hyperplane if it is parallel to that hyperplane (source).

For any vector $\vec{v} = (v_1, . . . , v_n)^T$ you can find a plane parallel to it by taking the dot product of $v$ and your variable vector $\vec{x} = (x_1, . . . , x_n)^T$ and setting the result equal to some constant $c$.

Consider $\eta$ as described in the paper, then the hyperplane he is referring to will be $$\eta_1 f_1 + . . . + \eta_n f_n = c $$ for a constant $c$. Because you are only interested in the distance between the points after projection, and not the location of the projected points, you can select $c = 0$, as shifting around the hyperplane won't affect the distances between the projected points.

Since the origin is contained in this hyperplane, the hyperplane is a subspace, call it $H$. We can then represent each $p_i$ as a vector $\vec{p_i}$ and project the vector onto the subspace.

To project a vector onto $H$ we need to find a basis for $H$. This can be done by making $n - 1$ similar vectors to $\eta$, where the difference is a single value is set to $0$ (distinct from previous selections). E.g., the plane $3x_1 + 4x_2 + 5x_3 = 0$ has a basis of $$\Bigg\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\},\Bigg\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}\Bigg\}, \text{ or } \Bigg\{\begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\}$$

Once you have a basis of $H$ you can use this guide guide to perform the projection. Note, since you have to do this multiple times, coming up with $Q$ as described in the guide and saving it will allow you to perform the process on many points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.