优化圆形填充算法，实现更紧密的填充和更小的边界圆

Question

我正在研究一个圆包装问题，我需要将一组不同半径的圆包装成尽可能小的边界圆，圆之间没有任何重叠。我正在使用遗传算法方法来生成可能的圆排列，并根据包含所有圆的边界圆的半径来评估它们的适合度。

我已在图像[输出]中附加了代码的当前输出：

当前实施细节：

 I use Processing with a genetic algorithm that initialises circle positions randomly.

   Each individual in the population represents a sequence of circle placements.

   Fitness is calculated as the radius of the bounding circle that encapsulates all the circles.

  I attempt to minimise this radius through generations of the genetic algorithm.

问题： 尽管进行了多次迭代，这些圆仍然没有紧密堆积，并且边界圆的半径比期望的要大。这些圆圈经常聚集在一起，而没有有效地优化可用空间。

问题：

1. 是否有既定的策略或对遗传算法的修改可以帮助实现更紧密的包装？
2. 如何修改圆放置或重叠解析策略以有效减小边界圆的大小？
3. 将不同的方法与遗传算法集成（例如力定向放置或模拟退火）是否可以提高封装效率？

任何关于优化循环打包算法的见解或建议或对我的代码的帮助将不胜感激！！！

 import java.util.ArrayList;
import java.util.Collections;

ArrayList<Circle> circles;
Population population;

void setup() {
  size(800, 800);
  circles = new ArrayList<Circle>();
  int[] radii = {10,12,15,20,21,30,30,30,50,40};
  for (int radius : radii) {
    float x = random(300, 500);
    float y = random(300, 500);
    circles.add(new Circle(radius, x, y));
  }
  population = new Population(100, circles);
  noLoop();
}

void draw() {
  background(255);
  population.runGenerations(1000);
  population.displayBest();
}

class Circle {
  float x, y, radius;

  Circle(float radius, float x, float y) {
    this.radius = radius;
    this.x = x;
    this.y = y;
  }

  void display() {
    ellipse(x, y, radius * 2, radius * 2);
  }

  boolean overlaps(Circle other) {
    float distance = dist(x, y, other.x, other.y);
    return distance < radius + other.radius;
  }

  void adjustPosition(Circle other) {
    float overlap = radius + other.radius - dist(x, y, other.x, other.y);
    float angle = atan2(y - other.y, x - other.x);
    x += cos(angle) * overlap / 2;
    y += sin(angle) * overlap / 2;
    other.x -= cos(angle) * overlap / 2;
    other.y -= sin(angle) * overlap / 2;
  }
}

class Individual {
  ArrayList<Integer> genes;
  float fitness;

  Individual(ArrayList<Integer> genes) {
    if (genes == null) {
      this.genes = new ArrayList<Integer>();
      for (int i = 0; i < circles.size(); i++) {
        this.genes.add(i);
      }
      Collections.shuffle(this.genes);
    } else {
      this.genes = new ArrayList<Integer>(genes);
    }
    adjustCirclePositions();
    fitness = calculateFitness();
  }

  void adjustCirclePositions() {
    for (int i = 0; i < genes.size(); i++) {
      Circle c1 = circles.get(genes.get(i));
      for (int j = i + 1; j < genes.size(); j++) {
        Circle c2 = circles.get(genes.get(j));
        if (c1.overlaps(c2)) {
          c1.adjustPosition(c2);
        }
      }
    }
  }

  Individual mate(Individual partner) {
    ArrayList<Integer> childGenes = new ArrayList<Integer>(genes.size());
    for (int i = 0; i < genes.size(); i++) {
      childGenes.add(genes.get(i));
    }
    for (int i = 0; i < partner.genes.size(); i++) {
      int idx = partner.genes.get(i);
      if (!childGenes.contains(idx)) {
        childGenes.set(i, idx);
      }
    }
    return new Individual(childGenes);
  }

  void mutate() {
    int index1 = (int) random(genes.size());
    int index2 = (int) random(genes.size());
    Collections.swap(genes, index1, index2);
    adjustCirclePositions();  // Adjust after mutation to avoid overlap
  }

  float calculateFitness() {
    float maxD = 0;
    float centerX = width / 2;
    float centerY = height / 2;
    for (int index : genes) {
      Circle circle = circles.get(index);
      float dist = dist(centerX, centerY, circle.x, circle.y) + circle.radius;
      if (dist > maxD) maxD = dist;
    }
    return maxD; // Lower is better
  }

  void display() {
    for (int index : genes) {
      circles.get(index).display();
    }
    displayBoundingCircle();
  }

  void displayBoundingCircle() {
    float maxD = calculateFitness();
    stroke(255, 0, 0);
    noFill();
    ellipse(width / 2, height / 2, 2 * maxD, 2 * maxD);
    fill(0);
    textSize(16); // Larger text size for better readability
    text("Bounding circle radius: " + nf(maxD, 0, 2), 20, 30); // Top left corner
  }
}

class Population {
  ArrayList<Individual> individuals;

  Population(int size, ArrayList<Circle> circles) {
    individuals = new ArrayList<Individual>();
    for (int i = 0; i < size; i++) {
      individuals.add(new Individual(null));
    }
  }

  void runGenerations(int count) {
    for (int i = 0; i < count; i++) {
      ArrayList<Individual> newGeneration = new ArrayList<Individual>();
      for (Individual ind : individuals) {
        Individual partner = individuals.get((int) random(individuals.size()));
        Individual child = ind.mate(partner);
        child.mutate();
        newGeneration.add(child);
      }
      individuals = newGeneration;
    }
  }

  void displayBest() {
    Individual best = individuals.get(0);
    for (Individual ind : individuals) {
      if (ind.fitness < best.fitness) {
        best = ind;
      }
    }
    best.display(); // Display the best individual with the bounding circle
  }
}

Answer 1

你还差得很远。使用全局非线性规划求解器，我得到一个半径为 99.8851 的外圆的解。