算法引入
在面对复杂的组合优化问题时，传统精确算法往往在多项式时间内难以求解。遗传算法（Genetic Algorithm, GA）由John Holland于1975年提出，模拟自然界中的生物进化过程——选择、交叉、变异——在庞大的解空间中进行高效搜索。与梯度下降等局部搜索方法不同，遗传算法通过维护一个种群（population）同时探索多个区域，借助”适者生存”的选择压力逐步收敛到全局最优或近似最优解。它已成功应用于旅行商问题（TSP）、排课系统、神经网络权重优化、机器人路径规划等众多NP难问题。
核心思想
遗传算法将问题的候选解编码为”染色体”（通常是一串基因序列），通过迭代执行以下操作进化种群：
编码与解码
将问题解映射为固定长度的染色体。例如TSP问题中，城市序列 [3, 1, 4, 2, 0] 表示从城市3出发，依次经过1、4、2、0后返回。
适应度函数
评估每个个体的优劣。TSP中适应度通常为路径总长度的倒数，路径越短适应度越高。
选择操作
根据适应度选择父代个体，适应度越高被选中的概率越大。常用轮盘赌选择或锦标赛选择。
交叉操作
将两个父代染色体的基因片段交换，产生新的子代。TSP中常用部分映射交叉（PMX）保持解的合法性。
变异操作
以较小概率随机改变某些基因，维持种群多样性，防止过早收敛到局部最优。
Java完整实现
import java.util.*;
/**
* 遗传算法实现
* 求解旅行商问题（TSP）：寻找访问所有城市并返回起点的最短路径
*/
public class GeneticAlgorithmTSP {
private final int cityCount; // 城市数量
private final double[][] distance; // 城市间距离矩阵
private final int populationSize; // 种群大小
private final double crossoverRate; // 交叉概率
private final double mutationRate; // 变异概率
private final int eliteCount; // 精英保留数量
private final Random random;
private List<Individual> population; // 当前种群
private Individual bestIndividual; // 历史最优个体
private int generation; // 当前代数
/**
* 个体类：表示一条TSP路径
*/
class Individual implements Comparable<Individual> {
int[] chromosome; // 染色体：城市访问顺序
double fitness; // 适应度（路径越短适应度越高）
double distance; // 路径总长度
Individual(int[] chromosome) {
this.chromosome = chromosome.clone();
evaluate();
}
/**
* 计算路径总长度和适应度
*/
void evaluate() {
this.distance = 0;
for (int i = 0; i < cityCount - 1; i++) {
this.distance += GeneticAlgorithmTSP.this.distance[chromosome[i]][chromosome[i + 1]];
}
// 返回起点
this.distance += GeneticAlgorithmTSP.this.distance[chromosome[cityCount - 1]][chromosome[0]];
// 适应度为路径长度的倒数（加小量防止除零）
this.fitness = 1.0 / (this.distance + 1e-6);
}
@Override
public int compareTo(Individual other) {
return Double.compare(other.fitness, this.fitness); // 降序
}
@Override
public String toString() {
return "路径=" + Arrays.toString(chromosome) + ", 距离=" + String.format("%.2f", distance);
}
}
public GeneticAlgorithmTSP(int cityCount, double[][] distance,
int populationSize, double crossoverRate,
double mutationRate, int eliteCount) {
this.cityCount = cityCount;
this.distance = distance;
this.populationSize = populationSize;
this.crossoverRate = crossoverRate;
this.mutationRate = mutationRate;
this.eliteCount = eliteCount;
this.random = new Random(42);
this.generation = 0;
}
/**
* 初始化种群：随机生成城市排列
*/
public void initialize() {
population = new ArrayList<>();
for (int i = 0; i < populationSize; i++) {
int[] chromosome = new int[cityCount];
for (int j = 0; j < cityCount; j++) chromosome[j] = j;
// Fisher-Yates洗牌
for (int j = cityCount - 1; j > 0; j--) {
int k = random.nextInt(j + 1);
int tmp = chromosome[j];
chromosome[j] = chromosome[k];
chromosome[k] = tmp;
}
population.add(new Individual(chromosome));
}
bestIndividual = population.get(0);
updateBest();
}
/**
* 更新历史最优个体
*/
private void updateBest() {
for (Individual ind : population) {
if (ind.distance < bestIndividual.distance) {
bestIndividual = new Individual(ind.chromosome);
}
}
}
/**
* 轮盘赌选择：适应度越高被选概率越大
*/
private Individual rouletteWheelSelection() {
double totalFitness = population.stream().mapToDouble(i -> i.fitness).sum();
double pick = random.nextDouble() * totalFitness;
double current = 0;
for (Individual ind : population) {
current += ind.fitness;
if (current >= pick) {
return ind;
}
}
return population.get(population.size() - 1);
}
/**
* 锦标赛选择：从k个随机个体中选最优
*/
private Individual tournamentSelection(int tournamentSize) {
Individual best = null;
for (int i = 0; i < tournamentSize; i++) {
Individual candidate = population.get(random.nextInt(populationSize));
if (best == null || candidate.fitness > best.fitness) {
best = candidate;
}
}
return best;
}
/**
* 部分映射交叉（PMX）：保持TSP解的合法性
*/
private Individual[] pmxCrossover(Individual parent1, Individual parent2) {
int[] p1 = parent1.chromosome;
int[] p2 = parent2.chromosome;
int[] c1 = new int[cityCount];
int[] c2 = new int[cityCount];
Arrays.fill(c1, -1);
Arrays.fill(c2, -1);
// 随机选择交叉区间
int point1 = random.nextInt(cityCount);
int point2 = random.nextInt(cityCount);
if (point1 > point2) {
int tmp = point1; point1 = point2; point2 = tmp;
}
// 复制交叉段
for (int i = point1; i <= point2; i++) {
c1[i] = p1[i];
c2[i] = p2[i];
}
// 建立映射关系并填充剩余位置
fillPMX(c1, p2, point1, point2);
fillPMX(c2, p1, point1, point2);
return new Individual[]{new Individual(c1), new Individual(c2)};
}
private void fillPMX(int[] child, int[] parent, int start, int end) {
Set<Integer> used = new HashSet<>();
for (int i = start; i <= end; i++) used.add(child[i]);
// 填充交叉区间左侧
for (int i = 0; i < start; i++) {
int val = parent[i];
while (used.contains(val)) {
// 查找映射
for (int j = start; j <= end; j++) {
if (child[j] == val) {
val = parent[j];
break;
}
}
}
child[i] = val;
used.add(val);
}
// 填充交叉区间右侧
for (int i = end + 1; i < cityCount; i++) {
int val = parent[i];
while (used.contains(val)) {
for (int j = start; j <= end; j++) {
if (child[j] == val) {
val = parent[j];
break;
}
}
}
child[i] = val;
used.add(val);
}
}
/**
* 交换变异：随机交换两个城市的位置
*/
private void mutate(Individual ind) {
if (random.nextDouble() < mutationRate) {
int i = random.nextInt(cityCount);
int j = random.nextInt(cityCount);
int tmp = ind.chromosome[i];
ind.chromosome[i] = ind.chromosome[j];
ind.chromosome[j] = tmp;
ind.evaluate();
}
}
/**
* 逆序变异：随机翻转一段路径（2-opt思想）
*/
private void mutateReverse(Individual ind) {
if (random.nextDouble() < mutationRate) {
int i = random.nextInt(cityCount);
int j = random.nextInt(cityCount);
if (i > j) { int tmp = i; i = j; j = tmp; }
while (i < j) {
int tmp = ind.chromosome[i];
ind.chromosome[i] = ind.chromosome[j];
ind.chromosome[j] = tmp;
i++; j--;
}
ind.evaluate();
}
}
/**
* 执行一代进化
*/
public void evolve() {
// 按适应度排序
population.sort(Comparator.naturalOrder());
List<Individual> newPopulation = new ArrayList<>();
// 精英保留：直接复制最优个体
for (int i = 0; i < eliteCount && i < populationSize; i++) {
newPopulation.add(new Individual(population.get(i).chromosome));
}
// 生成新一代
while (newPopulation.size() < populationSize) {
Individual parent1 = tournamentSelection(3);
Individual parent2 = tournamentSelection(3);
Individual[] children;
if (random.nextDouble() < crossoverRate) {
children = pmxCrossover(parent1, parent2);
} else {
children = new Individual[]{new Individual(parent1.chromosome),
new Individual(parent2.chromosome)};
}
mutateReverse(children[0]);
mutateReverse(children[1]);
newPopulation.add(children[0]);
if (newPopulation.size() < populationSize) {
newPopulation.add(children[1]);
}
}
population = newPopulation;
generation++;
updateBest();
}
/**
* 运行遗传算法指定代数
*/
public void run(int maxGenerations) {
for (int i = 0; i < maxGenerations; i++) {
evolve();
if ((i + 1) % 100 == 0) {
System.out.println("第 " + (i + 1) + " 代，最优距离: " +
String.format("%.2f", bestIndividual.distance));
}
}
}
/**
* 获取当前最优解
*/
public Individual getBest() {
return bestIndividual;
}
/**
* 获取当前代数
*/
public int getGeneration() {
return generation;
}
public static void main(String[] args) {
// 构造10个城市的TSP问题
int n = 10;
double[][] cities = new double[n][2];
Random rand = new Random(123);
for (int i = 0; i < n; i++) {
cities[i][0] = rand.nextDouble() * 100;
cities[i][1] = rand.nextDouble() * 100;
}
// 计算欧氏距离矩阵
double[][] dist = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double dx = cities[i][0] - cities[j][0];
double dy = cities[i][1] - cities[j][1];
dist[i][j] = Math.sqrt(dx * dx + dy * dy);
}
}
System.out.println("=== 遗传算法求解TSP ===");
System.out.println("城市数量: " + n);
GeneticAlgorithmTSP ga = new GeneticAlgorithmTSP(
n, dist, 200, 0.8, 0.15, 5
);
ga.initialize();
System.out.println("初始最优距离: " + String.format("%.2f", ga.getBest().distance));
ga.run(1000);
System.out.println("\n最终最优解:");
System.out.println(" " + ga.getBest());
System.out.println(" 总代数: " + ga.getGeneration());
// 对比：贪心最近邻算法
System.out.println("\n贪心最近邻算法对比:");
double greedyDist = greedyTSP(dist, n);
System.out.println(" 贪心距离: " + String.format("%.2f", greedyDist));
System.out.println(" 优化率: " + String.format("%.1f%%",
(greedyDist - ga.getBest().distance) / greedyDist * 100));
}
/**
* 贪心最近邻算法作为基准对比
*/
private static double greedyTSP(double[][] dist, int n) {
boolean[] visited = new boolean[n];
int current = 0;
visited[current] = true;
double total = 0;
int count = 1;
while (count < n) {
double minDist = Double.MAX_VALUE;
int next = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[current][i] < minDist) {
minDist = dist[current][i];
next = i;
}
}
total += minDist;
visited[next] = true;
current = next;
count++;
}
total += dist[current][0]; // 返回起点
return total;
}
}
算法优化策略
自适应参数
- 自适应变异率：种群多样性下降时提高变异率，收敛稳定时降低
- 精英保留比例：随着进化代数增加，适当提高精英保留数量
混合局部搜索
在遗传算法中嵌入2-opt、3-opt等局部搜索操作，大幅提升解的质量：
private void localSearch2Opt(Individual ind) {
boolean improved = true;
while (improved) {
improved = false;
for (int i = 0; i < cityCount - 1; i++) {
for (int j = i + 2; j < cityCount; j++) {
double d1 = distance[ind.chromosome[i]][ind.chromosome[i+1]]
+ distance[ind.chromosome[j]][ind.chromosome[(j+1)%cityCount]];
double d2 = distance[ind.chromosome[i]][ind.chromosome[j]]
+ distance[ind.chromosome[i+1]][ind.chromosome[(j+1)%cityCount]];
if (d2 < d1) {
// 翻转i+1到j之间的路径
reverse(ind.chromosome, i + 1, j);
ind.evaluate();
improved = true;
}
}
}
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 初始化 | O(P·N) | P为种群大小，N为城市数 |
| 每代进化 | O(P·N²) | 主要开销在PMX交叉操作 |
| 空间复杂度 | O(P·N) | 存储种群 |
| 收敛特性 | 无保证 | 启发式算法，依赖参数调优 |
应用场景
遗传算法在以下场景有广泛应用：
- 旅行商问题：物流配送路径规划、电路板钻孔路径优化
- 排课/排班系统：满足多重约束的最优时间表生成
- 神经网络结构搜索：自动发现高效的神经网络架构
- 特征选择：从高维数据中选择最优特征子集
- 投资组合优化：在风险约束下最大化收益
- 游戏AI：策略参数的自适应优化
遗传算法以其简单优雅的进化机制和强大的全局搜索能力，成为求解复杂优化问题的首选启发式方法之一。
