2

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

父母 1 。. . . . . . . . . . . . 3 4 1 5 2

父母2。. . . . . . . . . . . . 4 2 1 5 3

第一个指针 = 1，第二个指针 = 3

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

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

抱歉这一点，它们只是为了对齐

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

我认为，问题可能出在这一行： 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;
    }
4

1 回答 1

0

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

您还应该创建 Object 然后将它们分配给cities1和cities2。此外，最好通过覆盖equals方法City或比较城市名称来检查城市的平等性！

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

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];
          }
        } else {
          break;
        }
      }
    }

    for (int i = 0; i < citiesCount; i++) {
      for (int j = 0; j < citiesCount; j++) {
        if (offspring2[i] == null) {
          boolean parent1IsInOffspring2 = isCityInTheOffspring(parent1[j], offspring2);
          if (!parent1IsInOffspring2) {
            offspring2[i] = parent1[j];
          }
        } else {
          break;
        }
      }
    }

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

    return offspring;
  }

  private static boolean isCityInTheOffspring(City city, City[] offspring) {
    for (int i = 0; i < offspring.length; i++) {
      if (offspring[i] != null && offspring[i].getName().equals(city.getName())) {
        return true;
      }
    }
    return false;
  }
}
于 2020-04-04T14:44:43.580 回答