如何用最近邻随机点划分空间？遗传算法交叉方法技术问询

Great question—since you're only optimizing 2-3 variables, working in planar or spherical space makes this problem way more tractable than high-dimensional GA scenarios. Let's break down your two core challenges with practical, actionable solutions:

1. Ensuring Equal Parental Contribution When Grouping Points #

The key here is to design grouping strategies where every parent individual is included in the same number of triangle/quadrilateral groups, so each contributes equally to the next generation's offspring. Here are two reliable approaches:

Round-Robin Rotational Grouping (For Fixed Group Sizes) #

This works best when you can adjust your population size to be compatible with your group size (3 for triangles, 4 for quadrilaterals), or when you want controlled overlap:

• First, shuffle your population randomly to avoid bias from initial ordering.
• If your population size M is divisible by group size k: Split the shuffled list into consecutive groups of k points. Each parent appears in exactly one group, so every individual contributes to exactly one offspring (the centroid of their group).
• If M isn't divisible by k: Use cyclic rotation to create overlapping groups. For example, with k=3 and M=7:
  1. Start with group [p0, p1, p2]
  2. Shift right by one to get [p1, p2, p3]
  3. Repeat until you loop back to [p6, p0, p1]
     This creates M total groups, and each parent appears in exactly k groups (3 in this case), ensuring equal contribution across all individuals.

Weighted Random Pooling (For Flexible Group Sizes) #

If you need more flexibility with arbitrary population and group sizes:

• Decide on a target number of offspring G, then calculate how many times each parent should be included in groups: t = (G * k) / M (round to the nearest integer if needed, or adjust G to make t an integer).
• Initialize a counter for each parent set to t (this tracks how many more groups they can join).
• Repeatedly select k parents with remaining counter > 0 at random, form a group, generate the centroid offspring, and decrement each selected parent's counter by 1.
• Stop when all counters reach 0. This guarantees every parent contributes exactly t times to the offspring pool.

2. Spatial Subdivision Using Nearest Neighbors #

Leveraging nearest neighbors helps you create meaningful, space-filling groups that respect the distribution of your population. Here are tailored methods for your 2D/3D use cases:

k-Nearest Neighbor (k-NN) Grouping #

This is simple, intuitive, and ensures groups are locally cohesive:

• For each parent point pi:
  1. Find its top k-1 nearest neighbors (use Euclidean distance for planes, great-circle distance for spheres).
  2. Form a group with pi and these k-1 neighbors (3 total for triangles, 4 for quadrilaterals).
  3. Generate the centroid of this group as an offspring.
• To avoid redundant groups (e.g., pi's group being identical to pj's group), you can either:
  • Keep only unique groups (check for identical sets of points), or
  • Allow duplicates—they'll produce identical centroids, which won't harm diversity unless overdone.
• Bonus: Add randomness by selecting k-1 neighbors from the top m nearest neighbors (instead of the absolute top k-1). This introduces more variability and helps avoid getting stuck in local optima.

Delaunay Triangulation (For 2D Planar Spaces) #

If you want optimal, non-overlapping spatial subdivision:

• Run a Delaunay triangulation on your planar point set. This algorithm creates triangles such that no point lies inside the circumcircle of any triangle, resulting in well-shaped, space-filling groups.
• Extract each triangle's centroid as an offspring.
• To fix unequal parental contribution:
  1. Count how many triangles each parent appears in.
  2. For parents in too many triangles, randomly discard some of their associated groups.
  3. For parents in too few, add extra groups using their nearest neighbors until all parents have the same count.

Spherical Delaunay Triangulation (For 3D Spherical Spaces) #

For 3-variable problems mapped to a sphere (e.g., unit sphere constraints):

• Use a spherical Delaunay triangulation, which extends the planar Delaunay logic to the surface of a sphere.
• Calculate the spherical centroid of each triangle (average the 3 vertex vectors, then normalize to the sphere's surface) as an offspring.
• Follow the same equal-contribution adjustment steps as the planar Delaunay method to ensure every parent contributes equally.

内容的提问来源于stack exchange，提问作者Dónal Flanagan