GA optimization of 3D point cloud

Question

slaiyer 2014-10-9

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/157991-ga-optimization-of-3d-point-cloud

编辑： Matt J 2014-10-12

I have a 3D point cloud I need to optimize with respect to maximizing the volume of its convex hull. For n points, the input to the fitness function currently looks like:

arr(3 * n) = [ X1, Y1, Z1, X2, Y2, Z2, ... Xn, Yn, Zn ]

This works just fine till I add upper and lower bounds to the Z coordinates via vectors which look like:

LB(3 * n) = [ -Inf, -Inf, 3000, ... -Inf, -Inf, 3000 ]
UB(3 * n) = [  Inf,  Inf, 9000, ...  Inf,  Inf, 9000 ]

Here, the optimization performance and solution quality both drop greatly. The convex hull of the point cloud now tends to approach a cube, instead of freely expanding in X and Y. I think this because the GA only sees them as a vector of doubles, being unable to distinguish between X, Y, and Z coordinates, having no clue of their spatial significance.

I tried to implement custom data type optimization using cells, but run into other problems, the most major of which is of how to specify upper and lower bounds (which GA insists must be double vectors). The documentation for custom data type optimization offers no insight into this either.

Another wild guess would be to create 3 subpopulations of X, Y, and Z coordinates, and optimize them within themselves with no crossover, but I'm not sure if this would be feasible.

I would be grateful if someone could point me towards a viable approach for modelling this scenario, and would be glad to provide relevant snippets of code for reference as required.

EDIT (fitness function):

   function volume = fitfun(N, credit, NUM)
     INDIVS = size(N, 1);
     volume = zeros(INDIVS, 1);
     overlapFraction = 0.2;
     parfor i = 1 : INDIVS
       inferior = false;
       N2 = reshape(N(i,:), 3, NUM).';
       [ facets, volume(i) ] = convexHull(delaunayTriangulation(N2));
       numFacets = size(facets, 1);
       numVerts = size(facets, 2);
       for f = 1 : numFacets
         for v1 = 1 : numVerts
           v2 = rem(v1, numVerts) + 1;
           p = [ facets(f,v1); facets(f,v2) ];
           n = [ N2(p(1),:); N2(p(2),:) ];
           range = [ credit(p(1)); credit(p(2)) ];
           edge = norm(n(1,:) - n(2,:));
           % Edge length constraint:
           range = range_calc(n, range, edge);
           coverage = range(1) + range(2);
           overlap = coverage - edge;
           minOverlap = edge * overlapFraction;
           if overlap < minOverlap
             volume(i) = 0;
             inferior = true;
             break
           end
         end
         if inferior == true
           break
         end
       end
       if inferior == true
         continue
       end
     end
   end

12 个评论
显示 10更早的评论隐藏 10更早的评论

slaiyer 2014-10-10

编辑：slaiyer 2014-10-10

Sorry, I must not have been clear in my description of the situation.

The unbounded GA is constrained only by the edge length constraints specified. It is free to expand in all directions roughly around whatever origin is implied in 'PopInitRange' (or in 'InitialPopulation' when I'm testing with an explicit population), the score of an individual being the volume of the convex hull of the point cloud it forms. It may end up occupying space in say Z = [ -4000, 6000 ] if I center the initial population around [ 0, 0, 0 ].

(What I meant was that [ 3000, 9000 ] is almost always a subset of the Z interval of the unbounded GA's solution, especially when I center the initial population around a point anywhere in Z = 6000. I mentioned this to lay to rest your concerns that there may be no satisfactory solutions in this interval.)

Since the current scenario to be dealt with has Z bounded to [ 3000, 9000 ], I center the initial population around [ 6000, 6000, 6000 ] (any X and Y values will do). The unbounded solution may now end up in Z = [ 0, 12000 ] (of which my target bounds of [ 3000, 9000 ] are clearly a subset).

To derive a bounded solution in [ 3000, 9000 ], I obviously center the initial population around some point in Z = 6000 ((LB + UB) / 2) for both the bounded (my target) and unbounded (currently reliable) GAs.

I need to find a way to restrict the otherwise unbounded solution to the interval [ 3000, 9000 ] along the Z axis, while letting it freely expand in X and Y, essentially creating a very thick pancake of sorts, if I may. I hope I have clarified my predicament.

Matt J 2014-10-10

编辑：Matt J 2014-10-10

The unbounded solution may now end up in Z = [ 0, 12000 ] (of which my target bounds of [ 3000, 9000 ] are clearly a subset).

Well...there's little that we can conclude from that. We also know trivially that the unbounded solution will end up in Z=[-inf, inf] of which [3000,9000] is clearly a subset.

What exactly is defective in the solution that bounded GA gives you? Does it not satisfy all the constraints?

slaiyer 2014-10-10

编辑：slaiyer 2014-10-10

My intention in providing the example intervals of Z = [ -4000, 6000 ] (initial population centered around [ X_any, Y_any, 0 ]) and Z = [ 0, 12000 ] (initial population centered around [ X_any, Y_any, 6000 ]) was to convey an idea of the general length of the unbounded solution interval along the Z axis (restricted to such sizes as a consequence of the edge length constraints).

The defect in the solutions currently provided by the bounded GA is that instead of the generally disc-like expected shape of the convex hull (from squashing the generally spheroid/ovoid shape of the unbounded solutions), an almost cubic convex hull is being formed. This cubic hull is not nearly optimal, as even from a cursory inspection of visualizations of the unbounded and bounded solutions, it can expand a lot more along X and Y.

I surmise this is due to the GA seeing the input as a vector of doubles, and being unable to distinguish between X, Y, and Z coordinates, having no clue of their spatial significance. In creating successive generations, it apparently mixes and matches genes without discrimination. As a result of which, the bounded values from every third gene seem to spread everywhere else.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2014-10-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/157991-ga-optimization-of-3d-point-cloud#answer_154765

编辑：Matt J 2014-10-10

This cubic hull is not nearly optimal, as even from a cursory inspection of visualizations of the unbounded and bounded solutions, it can expand a lot more along X and Y.

Well, a test must be made to see whether the fault for that is GA, or whether it is some problem in the constraints or fitness function that you have provided.

It sounds like you could manually alter the solution given by unbounded GA to obtain a solution with a better fitness value. I.e., you could expand it further along X,Y by hand. I would do so, then re-run bounded GA with that hand-crafted solution in the initial population. Then, you can see if GA improves upon that solution or if instead it progresses back toward the solution you don't like. If the latter, you know there is something wrong in the fitness/constraint functions provided by you.

4 个评论
显示 2更早的评论隐藏 2更早的评论

slaiyer 2014-10-12

编辑：slaiyer 2014-10-12

在 MATLAB Online 中打开

penalty = volume(i) / NUM;
for j = 1 : NUM
  if N2(j,3) < bounds(1) || N2(j,3) > bounds(2)
    volume(i) = volume(i) - penalty;
  end
end

I'm currently having to resort to setting a primitive penalty (see above) inside the iteration code for vertices breaching bounds. The solutions are now optimal in all aspects, proving the validity of the code itself (which has already been done for superset intervals in the unbounded version).

However, this approach is hardly "organic", considering that the LB and UB parameters exist exclusively for this purpose. I also tried setting (2 * NUM) linear constraints targeted at the NUM number of Z coordinates, leading to EXACTLY the same behaviour as setting LB and UB. (I even tried setting both the linear constraints and LB/UB together, with all possible valid permutations in the options structure for the sake of completeness.)

Hand-crafting solutions is not an option as this is only part of the big picture that will be completely automated. Although I cannot "accept" your answer as the button so offers, I would like to thank you for your interest in my issue and your efforts towards helping me resolve it.

slaiyer 2014-10-12

It doesn't resolve everything, as vertices may still breach bounds, although it's a rare occurrence in the optimized spatial arrangement, and by a minor amount at its worst. This is clearly because the penalty approach is only a discouragement and not a hard limit in any way.

Matt J 2014-10-12

编辑：Matt J 2014-10-12

Well now, you can take that solution and put it in the initial population of bounded GA, like I was suggesting before, and see if it solves the problem rigorously (or at least within TolCon).

Remember, even though it's a "global optimization" algorithm, it can still probably benefit from your help in finding the right region to search.

请先登录，再进行评论。

GA optimization of 3D point cloud

12 个评论
显示 10更早的评论隐藏 10更早的评论

回答（1 个）

4 个评论
显示 2更早的评论隐藏 2更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

GA optimization of 3D point cloud

12 个评论 显示 10更早的评论隐藏 10更早的评论

回答（1 个）

4 个评论 显示 2更早的评论隐藏 2更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

12 个评论
显示 10更早的评论隐藏 10更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论