Java对象数组元素设置为null

Question

我对遗传算法中的顺序交叉有疑问。它应该在指向后代的指针之间复制第一对父代的一部分，从后代中存在的第二个父代号（在我的tsp问题中为城市编号）中删除，再加上第二个父代剩下的数字。例如：

parent1。 。 。 。 。 。 。 。 。 。 。 。 。 3 4 1 5 2

parent2。 。 。 。 。 。 。 。 。 。 。 。 。 4 2 1 5 3

firstPointer = 1，secondPointer = 3

第一步后的后代：null 4 1 5 null

最后的后代。 。 。 。 。 。 。 。 2 4 1 5 3

很抱歉，这只是为了对齐

这里是代码，它应该适用于两个后代，算法与第一个后代相同

我认为，问题可能在这一行：parent2Copy [j] = null;

但不是很确定，它是副本还是参考

City.java

// just main part to understand structure not all `standard` methods

public class City {

    private String name;
    private int x, y;

    public City(String name, int x, int y) {
        this.name = name;
        this.x = x;
        this.y = y;
    }
}





Main.java

public class Main {

    public static void main(String[] args) {

        City[] cities1 = {new City("3", 4, 6), new City("4", 4, 6), new City("1", 4, 6),
                new City("5", 4, 6), new City("2", 4, 6)};

        City[] cities2 = {new City("4", 4, 6), new City("2", 4, 6), new City("1", 4, 6),
                new City("5", 4, 6), new City("3", 4, 6)};

        Chromosome one = new Chromosome(cities1);
        Chromosome two = new Chromosome(cities2);


        System.out.println(one.toString());
        System.out.println(two.toString());

        Chromosome[] offspring = Crossover.orderedCrossover(one, two);

        System.out.println(offspring[0].toString());
        System.out.println(offspring[1].toString());

    }

}




Crossover.java

public static Chromosome[] orderedCrossover(Chromosome parentOne, Chromosome parentTwo) {

        Chromosome[] offspring = new Chromosome[2];

        City[] parent1 = parentOne.getArray();
        City[] parent2 = parentTwo.getArray();

        City[] parent1Copy = new City[parent1.length];
        City[] parent2Copy = new City[parent2.length];

        City[] offspring1 = new City[parent1.length];
        City[] offspring2 = new City[parent2.length];

        int firstPointer = new Random().nextInt(parent1.length);
        int secondPointer = new Random().nextInt(parent1.length - firstPointer) + firstPointer;

        while (firstPointer >= secondPointer)
            secondPointer = new Random().nextInt(parent1.length - firstPointer) + firstPointer;

        for (int i = firstPointer; i < secondPointer; i++)
            offspring1[i] = parent1[i];

        for (int i = 0; i < parent1.length; i++) {
            parent1Copy[i] = parent1[i];
            parent2Copy[i] = parent2[i];
        }

        // remove cities from parent2Copy that exists in offspring1 and parent2Copy
        for (int i = 0; i < offspring1.length; i++) {
            for (int j = 0; j < parent2.length; j++) {
                if (offspring1[i] == parent2[j])
                    parent2Copy[j] = null;
            }
        }

        // adds last cities from parent2 to offspring1 empty slots
        for (int i = 0; i < parent2.length; i++) {
            for (int j = 0; j < parent2.length; j++) {
                if (offspring1[i] == null)
                    if (parent2Copy[j] != null) {
                        offspring1[i] = parent2[j];
                        parent2Copy[j] = null;
                        break;
                    }
            }
        }

        // put back cities to copy
        for (int i = 0; i < parent1.length; i++)
            parent2Copy[i] = parent2[i];


        for (int i = firstPointer; i < secondPointer; i++)
            offspring2[i] = parent2[i];

        // remove cities from parent2 that exists in offspring and parent2
        for (int i = 0; i < offspring2.length; i++) {
            for (int j = 0; j < parent1.length; j++) {
                if (offspring2[i] == parent1[j])
                    parent1Copy[j] = null;
            }
        }

        // adds last cities from parent2 to offspring1 empty slots
        for (int i = 0; i < parent1.length; i++) {
            for (int j = 0; j < parent1.length; j++) {
                if (offspring1[i] == null)
                    if (parent1Copy[j] != null) {
                        offspring2[i] = parent1[j];
                        parent1Copy[j] = null;
                        break;
                    }
            }
        }

        offspring[0] = new Chromosome(offspring1);
        offspring[1] = new Chromosome(offspring2);

        return offspring;
    }

Answer 1

当创建对象类型的数组（如City）时，数组保存分配的对象的引用，而不是对象。因此，parent2Copy[j] = null不会影响先前从parent2Copy复制的阵列。

也许简化代码可以通过降低代码复杂度来解决问题。这是生成特征的示例代码：

import java.util.Random;

public final class Crossover {
  private Crossover (){
    throw new IllegalStateException("Crossover");
  }

  public static Chromosome[] orderedCrossover(Chromosome parentOne, Chromosome parentTwo) {
    Chromosome[] offspring = new Chromosome[2];

    City[] parent1 = parentOne.getArray();
    City[] parent2 = parentTwo.getArray();
    int citiesCount = parent1.length;

    City[] offspring1 = new City[citiesCount];
    City[] offspring2 = new City[citiesCount];

    int firstPointer = new Random().nextInt(citiesCount - 2);
    int secondPointer = new Random().nextInt(citiesCount - firstPointer) + firstPointer;

    while (firstPointer >= secondPointer) {
      secondPointer = new Random().nextInt(citiesCount - firstPointer) + firstPointer;
    }

    System.arraycopy(parent1, firstPointer, offspring1, firstPointer, secondPointer - firstPointer);
    System.arraycopy(parent2, firstPointer, offspring2, firstPointer, secondPointer - firstPointer);

    for (int i = 0; i < citiesCount; i++) {
      for (int j = 0; j < citiesCount; j++) {
        if (offspring1[i] == null) {
          boolean parent2IsInOffspring1 = isCityInTheOffspring(parent2[j], offspring1);
          if (!parent2IsInOffspring1) {
            offspring1[i] = parent2[j];
          }

          boolean parent1IsInOffspring2 = isCityInTheOffspring(parent1[j], offspring2);
          if (!parent1IsInOffspring2) {
            offspring2[i] = parent1[j];
          }
        }
      }
    }

    offspring[0] = new Chromosome(offspring1);
    offspring[1] = new Chromosome(offspring2);

    return offspring;
  }

  private static boolean isCityInTheOffspring(City city, City[] offspring) {
    if (city == null) {
      throw new IllegalArgumentException("City must not be null");
    }
    for (int i = 0; i < offspring.length; i++) {
      if (city == offspring[i]) {
        return true;
      }
    }
    return false;
  }
}