遗传算法适应度和交叉选择

Question

我正在尝试使用遗传算法为教室中的给定部分随机安排座位列表，以便该教室中的所有组坐在一起。

这是我目前的尝试，我不清楚改进此算法的最佳方法，因为这是我学习 GA 的非常早的阶段。

我正在使用 Java 库 Jenetics，它非常适合我入门，这是引擎。

        final Engine<EnumGene<Seat>, Double> ENGINE = Engine
                .builder(SeatingFitness::fitness, encoding)
                .populationSize(200)
                .selector(new RouletteWheelSelector<>())
                .alterers(
                        new PartiallyMatchedCrossover<>(0.2),
                        new Mutator<>(0.01)
                )
                .optimize(Optimize.MINIMUM)
                .build();

编码看起来像这样

    static final ISeq<Seat> seats = ISeq.of(createSeats());
    static final Codec<ISeq<Seat>, EnumGene<Seat>> encoding = Codecs.ofPermutation(seats);

    public static List<Seat> createSeats() {
        return new ArrayList<>(Arrays.asList(
                new Seat("Group C", 1),
                new Seat("Group A", 2),
                new Seat("Group B", 3)
                .....more seats here....)
    }

我的健身功能肯定可以改进，我没有使用任何库，所以这里的任何建议都很好，但它看起来像这样。

基本上我所做的只是找到组中每个座位的 x 和 y 坐标，计算每个座位与组中其他座位的距离，然后将这些值相加。值越低越好，因此 Engine

中的 Optimize.MINIMUM

private static int numberOfSeatsInRow = 8;

    public static double fitness(final ISeq<Seat> seats) {

        AtomicDouble score = new AtomicDouble();
        // Group together all the seats that belong to a particular group.
        Map<String, List<Seat>> grouping = seats.stream().collect(groupingBy(Seat::getGroup));

        grouping.forEach((group, groupsSeats) -> {
            // Find the location in the overall list of the seats for the group.
            if (!group.equals(Seat.EMPTY_SEAT)) {
                List<Integer> indexOfSeatInOverallList = groupsSeats.stream().map(seats::indexOf).collect(Collectors.toList());
                if (indexOfSeatInOverallList.size() > 2) {
                    // Get the first element positioned correctly on the x and y axis

                    double totalCalculated = indexOfSeatInOverallList.stream().reduce(0, (subTotal, currentElement) -> {

                        int xReferenceCoordinate = calculateXCoordinate(currentElement);
                        int yReferenceCoordinate = calculateYCoordinate(currentElement);

                        double totalDistance = 0;
                        int multiplier = groupsSeats.size() <= numberOfSeatsInRow ? 10 : 500;
                        for (Integer integer : indexOfSeatInOverallList) {
                            int xSecondary = calculateXCoordinate(integer);
                            int ySecondary = calculateYCoordinate(integer);
                            if (ySecondary != yReferenceCoordinate) {
                                totalDistance += multiplier * Math.abs(yReferenceCoordinate - ySecondary);
                            }
                            totalDistance += calculateDistanceBetweenTwoPoints(xReferenceCoordinate, yReferenceCoordinate, xSecondary, ySecondary);
                        }

                        return (int) totalDistance;
                    });

                    score.getAndAdd(totalCalculated);
                }
            }

        });
        return score.get();
    }

    private static int calculateXCoordinate(int positionInList) {
        int xPosition = positionInList % numberOfSeatsInRow;
        if (xPosition == 0) {
            xPosition = numberOfSeatsInRow;
        }
        return xPosition;
    }

    private static int calculateYCoordinate(int positionInList) {
        int xPosition = positionInList % numberOfSeatsInRow;
        int yPosition = positionInList / numberOfSeatsInRow;
        if (xPosition == 0) {
            yPosition = yPosition - 1;
        }

        return yPosition + 1;
    }

    private static double calculateDistanceBetweenTwoPoints(int x1, int y1, int x2, int y2) {
       // https://dqydj.com/2d-distance-calculator/
        double xValue = Math.pow((x2 - x1), 2);
        double yValue = Math.pow((y2 - y1), 2);
        return Math.sqrt(xValue + yValue);
    }

查看下面的结果图片，您可以看到它非常好（尽管运行需要大约 3 分钟才能产生正确的结果）。

Answer 1

关于您的 Engine 定义，我可以看到一点是您正在使用 Mutator 修改器来解决组合问题。这会导致您的表现不佳（很可能）。 Mutator 不服从染色体中的 独特元素 属性。突变染色体意味着使其失效，这会导致新染色体的不断重建。对于组合问题，只有 SwapMutator 和 PartiallyMatchedCrossover 是有效改变者。

final Engine<EnumGene<Seat>, Double> ENGINE = Engine
    .builder(SeatingFitness::fitness, encoding)
    .populationSize(200)
    .selector(new RouletteWheelSelector<>())
    .alterers(
        new PartiallyMatchedCrossover<>(0.2),
        new SwapMutator<>(0.01))
    .optimize(Optimize.MINIMUM)
    .build();

您的适应度函数可能也有改进，但为了对此发表评论，整个适应度函数代码会很好。

Answer 2

我看了一下适应度函数。您为每次适应度函数调用计算的某些内容可以计算一次。

private static final ISeq<Seat> SEATS = ISeq.of(
    new Seat("Group C", 1),
    new Seat("Group A", 2),
    new Seat("Group B", 3)
);

private static final Map<String, List<Seat>> SEAT_GROUPS = SEATS.stream()
    .collect(groupingBy(Seat::getGroup));

SEAT_GROUPS地图由座位表定义，不会改变。如果我是对的，你的适应度函数中的 reduce 函数忽略了之前计算的距离。

double totalCalculated = indexOfSeatInOverallList.stream()
    .reduce(0, (subTotal, currentElement) -> {
            // subTotal is ignored in your code, but should be added to the result.
            return (int) totalDistance + subTotal;
        })

你的calculateDistanceBetweenTwoPoints可以实现为

double distance(final int x1, final int y1, final int x2, final int y2) {
    // sqrt(x^2 + y^2)
    return Math.hypot(x2 - x1, y2 - y1);
}

我的“清理”版本将如下所示。

private static final int SEATS_PER_ROW = 8;

private static final ISeq<Seat> SEATS = ISeq.of(
    new Seat("Group C", 1),
    new Seat("Group A", 2),
    new Seat("Group B", 3)
);

private static final Map<String, List<Seat>> SEAT_GROUPS = SEATS.stream()
    .collect(groupingBy(Seat::getGroup));

public static double fitness(final ISeq<Seat> seats) {
    double score = 0;

    for (var entry : SEAT_GROUPS.entrySet()) {
        final var group = entry.getKey();
        final var groupsSeats = entry.getValue();
        final int multiplier = groupsSeats.size() <= SEATS_PER_ROW ? 10 : 500;

        if (!group.equals(Seat.EMPTY_SEAT)) {
            final int[] indexes = groupsSeats.stream()
                .mapToInt(seats::indexOf)
                .toArray();

            if (indexes.length > 2) {
                final double dist = IntStream.of(indexes)
                    .reduce(0, (a, b) -> toDistance(multiplier, indexes, a, b));

                score += dist;
            }
        }
    }

    return score;
}

private static int toDistance(
    final int multiplier,
    final int[] indexes,
    final int sum,
    final int index
) {
    final int x1 = toX(index);
    final int y = toY(index);

    int total = 0;
    for (int i : indexes) {
        final int x2 = toX(i);
        final int y2 = toY(i);
        if (y2 != y) {
            total += multiplier*Math.abs(y - y2);
        }
        total += distance(x1, y, x2, y2);
    }

    return sum + total;
}

private static double distance(final int x1, final int y1, final int x2, final int y2) {
    // sqrt(x^2 + y^2)
    return Math.hypot(x2 - x1, y2 - y1);
}

private static int toX(final int index) {
    int x = index%SEATS_PER_ROW;
    if (x == 0) {
        x = SEATS_PER_ROW;
    }
    return x;
}

private static int toY(final int index) {
    final int x = index%SEATS_PER_ROW;
    int y = index/SEATS_PER_ROW;
    if (x == 0) {
        y = y - 1;
    }
    return y + 1;
}

遗传算法适应度和交叉选择

Genetic Algorithm Fitness and Cross Over selection

genetic-algorithm

jenetics