用遗传算法求解 N 皇后问题

START
Generate the initial population
Compute fitness
REPEAT
    Selection
    Crossover
    Mutation
    Compute fitness
UNTIL population has converged
STOP

import java.util.*;
import java.util.stream.Collectors;

public class Queen {
    private static int N = 10;
    private static double RATE = 0.3;

    public static void main(String[] args) {
        Queen queen = new Queen();
        HashSet<String> result = new HashSet<>();
        int[] father = queen.init();
        int[] mother = queen.init();
        int times = 3000000;
        for (int i = 0; i < times; i++) {
            List<Integer[]> son = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                son.add(Arrays.stream(queen.crossover(father, mother)).boxed().toArray(Integer[]::new));
            }
            son = queen.mutation(son);
            Map<Integer[], Integer> res = queen.selection(son);
            for (Map.Entry<Integer[], Integer> c : res.entrySet()) {
                if (c.getValue() == 0) result.add(Arrays.toString(c.getKey()));
            }
            father = Arrays.stream(res.entrySet().iterator().next().getKey()).mapToInt(k -> k).toArray();
            mother = Arrays.stream(res.entrySet().iterator().next().getKey()).mapToInt(k -> k).toArray();
        }
        System.out.println("Solutions: " + result.size());
    }

    private int[] init() {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= N; i++) list.add(i);
        Collections.shuffle(list);
        return list.stream().mapToInt(i -> i).toArray();
    }

    private int[] crossover(int[] originFather, int[] originMother) {
        int[] father = Arrays.copyOf(originFather, N);
        int[] mother = Arrays.copyOf(originMother, N);
        int[] rend = new int[N];
        for (int i = 0; i < N; i++) {
            rend[i] = Math.random() >= 0.5 ? 0 : 1;
        }
        int[] son = new int[N];
        int f = 0, m = 0;
        for (int i = 0; i < N; i++) {
            if (rend[i] == 0) {
                for (f = 0; f < N; f++) if (father[f] != 0) break;
            } else {
                for (m = 0; m < N; m++) if (mother[m] != 0) break;
            }
            son[i] = rend[i] == 0 ? father[f] : mother[m];
            for (int j = 0; j < N; j++) {
                if (father[j] == son[i]) father[j] = 0;
                if (mother[j] == son[i]) mother[j] = 0;
            }
        }
        return son;
    }

    private List<Integer[]> mutation(List<Integer[]> chromosomes) {
        for (Integer[] chromosome : chromosomes) {
            if (Math.random() < RATE) continue;
            int i = (int) (Math.random() * N);
            int j = (int) (Math.random() * N);
            if (i == j) continue;
            chromosome[i] ^= chromosome[j];
            chromosome[j] ^= chromosome[i];
            chromosome[i] ^= chromosome[j];
        }
        return chromosomes;
    }

    private Integer fitness(Integer[] result) {
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (Math.abs(result[i] - result[j]) == j - i) res++;
            }
        }
        return res;
    }

    private Map<Integer[], Integer> selection(List<Integer[]> son) {
        Map<Integer[], Integer> result = son.stream().collect(Collectors.toMap(x -> x, this::fitness));
        result = result.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (oldValue, newValue) -> oldValue, LinkedHashMap::new));
        return result;
    }
}