Java элемент массива объекта установлен в ноль

Question

У меня проблема с пересечением порядка в алгоритме geneti c. Он должен скопировать часть первого родителя между указателями на потомство, удалить из номеров второго родителя (номер города в моей проблеме tsp), который существует в потомке, добавить одно за другим числа, оставленные от второго родителя. Например:

parent1. , , , , , , , , , , , , 3 4 1 5 2

parent2. , , , , , , , , , , , , 4 2 1 5 3

firstPointer = 1, secondPointer = 3

потомство после первого шага: ноль 4 1 5 ноль

конечное потомство. , , , , , , , 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;
    }

Answer 1

Когда вы создаете массив типа объекта (например, 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;
  }
}