引言
八皇后问题是计算机科学中最经典的约束满足问题之一，要求在8×8棋盘上放置8个皇后，使彼此互不攻击。传统回溯法能高效求得所有解，而遗传算法（GA）则提供了一种完全不同的思路：将棋盘布局编码为染色体，通过选择、交叉、变异等进化操作，让种群逐步收敛到可行解。本文将用Java实现基于遗传算法的八皇后求解器，重点讲解适应度函数设计与进化策略优化。
遗传算法核心原理
遗传算法模拟自然选择过程，包含五个核心组件：
- 编码（Representation）：将解空间映射为染色体。八皇后中，用数组 $[c_0, c_1, …, c_7]$ 表示第 $i$ 行皇后位于第 $c_i$ 列，天然保证行不冲突。
- 适应度函数（Fitness）：评估染色体优劣。八皇后中，统计互相攻击的皇后对数，攻击对越少适应度越高。
- 选择（Selection）：根据适应度选择父代，常用轮盘赌或锦标赛选择。
- 交叉（Crossover）：交换两个父代的染色体片段产生子代。
- 变异（Mutation）：随机改变染色体某些基因，维持种群多样性。
Java实现
染色体与种群定义
import java.util.*;
public class Chromosome implements Comparable<Chromosome> {
private int[] genes; // genes[i] = 第i行皇后所在的列
private int fitness; // 适应度：非攻击对数 = 28 - 攻击对数
private int conflicts; // 攻击对数（缓存）
private static final int N = 8;
private static final int MAX_PAIRS = N * (N - 1) / 2; // 28
public Chromosome() {
this.genes = new int[N];
// 随机初始化：每行随机一列
Random rand = new Random();
for (int i = 0; i < N; i++) {
genes[i] = rand.nextInt(N);
}
calculateFitness();
}
public Chromosome(int[] genes) {
this.genes = genes.clone();
calculateFitness();
}
/**
* 计算攻击对数：同一列或对角线上的皇后对
*/
public void calculateFitness() {
conflicts = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// 列冲突
if (genes[i] == genes[j]) conflicts++;
// 对角线冲突
else if (Math.abs(genes[i] - genes[j]) == Math.abs(i - j)) conflicts++;
}
}
fitness = MAX_PAIRS - conflicts;
}
public int getFitness() { return fitness; }
public int getConflicts() { return conflicts; }
public int[] getGenes() { return genes.clone(); }
public boolean isSolution() { return conflicts == 0; }
public void setGene(int index, int value) {
genes[index] = value;
}
@Override
public int compareTo(Chromosome other) {
return Integer.compare(other.fitness, this.fitness); // 降序
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Fitness=").append(fitness).append(", Conflicts=").append(conflicts).append("\n");
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
sb.append(genes[r] == c ? "Q " : ". ");
}
sb.append("\n");
}
return sb.toString();
}
}
遗传算法引擎
public class GeneticAlgorithm {
private static final int N = 8;
private static final int POP_SIZE = 100; // 种群大小
private static final double CROSS_RATE = 0.8; // 交叉概率
private static final double MUTATE_RATE = 0.1; // 变异概率
private static final int MAX_GENERATIONS = 10000; // 最大迭代次数
private static final int ELITE_COUNT = 10; // 精英保留数量
private List<Chromosome> population;
private Random random;
private int generation;
public GeneticAlgorithm() {
this.random = new Random();
initializePopulation();
}
private void initializePopulation() {
population = new ArrayList<>();
for (int i = 0; i < POP_SIZE; i++) {
population.add(new Chromosome());
}
Collections.sort(population);
}
/**
* 锦标赛选择：从k个随机个体中选最优
*/
private Chromosome tournamentSelection(int k) {
Chromosome best = null;
for (int i = 0; i < k; i++) {
Chromosome candidate = population.get(random.nextInt(population.size()));
if (best == null || candidate.getFitness() > best.getFitness()) {
best = candidate;
}
}
return best;
}
/**
* 轮盘赌选择：按适应度比例选择
*/
private Chromosome rouletteSelection() {
int totalFitness = population.stream().mapToInt(Chromosome::getFitness).sum();
int threshold = random.nextInt(totalFitness + 1);
int cumulative = 0;
for (Chromosome c : population) {
cumulative += c.getFitness();
if (cumulative >= threshold) {
return c;
}
}
return population.get(population.size() - 1);
}
/**
* 单点交叉：随机选择交叉点，交换后半部分
*/
private Chromosome[] crossover(Chromosome p1, Chromosome p2) {
if (random.nextDouble() > CROSS_RATE) {
return new Chromosome[]{new Chromosome(p1.getGenes()), new Chromosome(p2.getGenes())};
}
int point = random.nextInt(N - 1) + 1; // 1到N-1
int[] g1 = p1.getGenes();
int[] g2 = p2.getGenes();
int[] child1 = new int[N];
int[] child2 = new int[N];
System.arraycopy(g1, 0, child1, 0, point);
System.arraycopy(g2, point, child1, point, N - point);
System.arraycopy(g2, 0, child2, 0, point);
System.arraycopy(g1, point, child2, point, N - point);
return new Chromosome[]{new Chromosome(child1), new Chromosome(child2)};
}
/**
* 均匀交叉：每个基因独立选择来自哪个父代
*/
private Chromosome[] uniformCrossover(Chromosome p1, Chromosome p2) {
int[] g1 = p1.getGenes();
int[] g2 = p2.getGenes();
int[] child1 = new int[N];
int[] child2 = new int[N];
for (int i = 0; i < N; i++) {
if (random.nextBoolean()) {
child1[i] = g1[i];
child2[i] = g2[i];
} else {
child1[i] = g2[i];
child2[i] = g1[i];
}
}
return new Chromosome[]{new Chromosome(child1), new Chromosome(child2)};
}
/**
* 变异：随机改变某行的列位置
*/
private void mutate(Chromosome chrom) {
int[] genes = chrom.getGenes();
for (int i = 0; i < N; i++) {
if (random.nextDouble() < MUTATE_RATE) {
genes[i] = random.nextInt(N);
}
}
// 重新计算适应度
chrom = new Chromosome(genes);
}
/**
* 自适应变异：根据种群多样性调整变异率
*/
private void adaptiveMutate(Chromosome chrom, double diversity) {
double rate = MUTATE_RATE * (1 + 1.0 / (diversity + 0.01));
int[] genes = chrom.getGenes();
for (int i = 0; i < N; i++) {
if (random.nextDouble() < rate) {
genes[i] = random.nextInt(N);
}
}
}
/**
* 计算种群多样性：平均汉明距离
*/
private double calculateDiversity() {
double totalDist = 0;
int count = 0;
for (int i = 0; i < population.size(); i++) {
for (int j = i + 1; j < population.size(); j++) {
totalDist += hammingDistance(population.get(i), population.get(j));
count++;
}
}
return count == 0 ? 0 : totalDist / count;
}
private double hammingDistance(Chromosome a, Chromosome b) {
int[] g1 = a.getGenes();
int[] g2 = b.getGenes();
int dist = 0;
for (int i = 0; i < N; i++) {
if (g1[i] != g2[i]) dist++;
}
return dist;
}
/**
* 进化一代
*/
private void evolve() {
List<Chromosome> newPopulation = new ArrayList<>();
// 精英保留
for (int i = 0; i < ELITE_COUNT; i++) {
newPopulation.add(new Chromosome(population.get(i).getGenes()));
}
double diversity = calculateDiversity();
while (newPopulation.size() < POP_SIZE) {
Chromosome p1 = tournamentSelection(5);
Chromosome p2 = tournamentSelection(5);
Chromosome[] children = uniformCrossover(p1, p2);
for (Chromosome child : children) {
if (newPopulation.size() >= POP_SIZE) break;
adaptiveMutate(child, diversity);
child = new Chromosome(child.getGenes()); // 重新计算适应度
newPopulation.add(child);
}
}
population = newPopulation;
Collections.sort(population);
generation++;
}
/**
* 运行遗传算法直到找到解或达到最大代数
*/
public Chromosome solve() {
System.out.println("初始最优适应度: " + population.get(0).getFitness());
for (int gen = 1; gen <= MAX_GENERATIONS; gen++) {
evolve();
Chromosome best = population.get(0);
if (gen % 100 == 0 || best.isSolution()) {
System.out.printf("Generation %d: Best Fitness=%d, Conflicts=%d, Diversity=%.2f%n",
gen, best.getFitness(), best.getConflicts(), calculateDiversity());
}
if (best.isSolution()) {
System.out.println("找到解！代数: " + gen);
return best;
}
}
System.out.println("达到最大代数，返回当前最优解");
return population.get(0);
}
public int getGeneration() { return generation; }
}
适应度函数优化策略
public class FitnessStrategies {
/**
* 策略1：基础适应度 = 非攻击对数
*/
public static int basicFitness(int[] genes) {
int conflicts = 0;
for (int i = 0; i < genes.length; i++) {
for (int j = i + 1; j < genes.length; j++) {
if (genes[i] == genes[j]) conflicts++;
else if (Math.abs(genes[i] - genes[j]) == j - i) conflicts++;
}
}
return 28 - conflicts;
}
/**
* 策略2：加权适应度，对对角线冲突给予更高惩罚
*/
public static int weightedFitness(int[] genes) {
int colConflicts = 0, diagConflicts = 0;
for (int i = 0; i < genes.length; i++) {
for (int j = i + 1; j < genes.length; j++) {
if (genes[i] == genes[j]) colConflicts++;
else if (Math.abs(genes[i] - genes[j]) == j - i) diagConflicts++;
}
}
return 28 - colConflicts - 2 * diagConflicts;
}
/**
* 策略3：平滑适应度，考虑部分解的质量
* 对"接近不冲突"的布局给予更高分
*/
public static double smoothFitness(int[] genes) {
double score = 0;
for (int i = 0; i < genes.length; i++) {
for (int j = i + 1; j < genes.length; j++) {
if (genes[i] == genes[j]) continue; // 列冲突，0分
int diagDist = Math.abs(genes[i] - genes[j]);
int rowDist = j - i;
if (diagDist == rowDist) continue; // 对角线冲突，0分
// 距离对角线越远，贡献越高
score += 1.0 / (1 + Math.abs(diagDist - rowDist));
}
}
return score;
}
}
主程序与对比实验
public class NQueensGA {
public static void main(String[] args) {
System.out.println("=== 八皇后遗传算法求解器 ===\n");
// 运行多次取平均
int runs = 10;
int success = 0;
long totalGen = 0;
for (int i = 0; i < runs; i++) {
System.out.println("--- 运行 " + (i + 1) + " ---");
GeneticAlgorithm ga = new GeneticAlgorithm();
Chromosome solution = ga.solve();
if (solution.isSolution()) {
success++;
totalGen += ga.getGeneration();
System.out.println(solution);
} else {
System.out.println("未找到完美解，当前冲突数: " + solution.getConflicts());
}
System.out.println();
}
System.out.printf("成功率: %d/%d%n", success, runs);
if (success > 0) {
System.out.printf("平均收敛代数: %.1f%n", (double) totalGen / success);
}
// 与回溯法对比
System.out.println("\n=== 回溯法求解（基准） ===");
long start = System.currentTimeMillis();
List<int[]> backtrackSolutions = backtrackSolve();
long end = System.currentTimeMillis();
System.out.println("解的数量: " + backtrackSolutions.size());
System.out.println("耗时: " + (end - start) + "ms");
}
/**
* 回溯法基准实现
*/
static List<int[]> backtrackSolve() {
List<int[]> solutions = new ArrayList<>();
int[] cols = new int[8];
backtrack(0, cols, solutions);
return solutions;
}
static void backtrack(int row, int[] cols, List<int[]> solutions) {
if (row == 8) {
solutions.add(cols.clone());
return;
}
for (int c = 0; c < 8; c++) {
if (isValid(row, c, cols)) {
cols[row] = c;
backtrack(row + 1, cols, solutions);
}
}
}
static boolean isValid(int row, int col, int[] cols) {
for (int r = 0; r < row; r++) {
if (cols[r] == col) return false;
if (Math.abs(cols[r] - col) == row - r) return false;
}
return true;
}
}
算法优化要点
- 编码设计：采用一维数组 $[c_0, …, c_7]$ 而非二维矩阵，天然消除行冲突，将搜索空间从 $8^{64}$ 降至 $8^8 = 16,777,216$。
- 适应度函数：基础版本统计非攻击对数，加权版本对对角线冲突施加更高惩罚，引导搜索更快收敛。
- 选择压力：锦标赛选择（$k=5$）比轮盘赌收敛更快，避免早期超级个体垄断种群。
- 均匀交叉：比单点交叉更好地混合父代特征，在八皇后问题中表现更稳定。
- 自适应变异：种群多样性降低时自动提高变异率，防止早熟收敛。
- 精英保留：每代保留前10%最优个体，确保优良基因不丢失。
复杂度分析
- 时间复杂度：每代 $O(POP_SIZE \cdot N^2)$，主要消耗在适应度计算。实际通常在数百到数千代内收敛。
- 空间复杂度：$O(POP_SIZE \cdot N)$，存储种群。
- 与回溯法对比：回溯法时间 $O(N!)$ 但八皇后仅需数毫秒；GA不保证最优但能在可接受时间内找到解，且易于并行化。
总结
遗传算法为八皇后问题提供了与回溯法截然不同的解决思路。通过合理的编码设计和适应度函数，GA能在数百代内稳定收敛到可行解。本文实现的自适应变异和精英保留策略显著提升了算法的收敛速度和成功率，展示了进化计算在组合优化问题中的强大能力。
