跳转至

遗传算法

概述

遗传算法（Genetic Algorithm, GA）是一种模拟生物进化过程的随机搜索算法，通过选择、交叉、变异等遗传操作，在解空间中搜索最优解。

生物进化类比

生物概念 算法对应
染色体 解的编码
基因 编码的每一位
个体 一个解
种群 解的集合
适应度 解的质量
选择 保留优秀解
交叉 解的组合
变异 解的扰动

遗传算法特点

  • 种群搜索：同时搜索多个解
  • 随机性：引入随机因素避免局部最优
  • 适应性：根据适应度调整搜索方向
  • 通用性：适用于各种优化问题

算法框架

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdlib.h>
#include <string.h>

#define POP_SIZE 100
#define MAX_GEN 1000
#define CROSS_RATE 0.8
#define MUTATE_RATE 0.1
#define CHROMO_LEN 50

typedef struct {
    int genes[CHROMO_LEN];
    double fitness;
} Individual;

typedef struct {
    Individual pop[POP_SIZE];
    int chromoLen;
    int popSize;
    int maxGen;
    double crossRate;
    double mutateRate;
} GeneticAlgorithm;

void initGA(GeneticAlgorithm *ga) {
    ga->chromoLen = CHROMO_LEN;
    ga->popSize = POP_SIZE;
    ga->maxGen = MAX_GEN;
    ga->crossRate = CROSS_RATE;
    ga->mutateRate = MUTATE_RATE;
}

void initPopulation(GeneticAlgorithm *ga, 
                   void (*initFunc)(Individual*)) {
    for (int i = 0; i < ga->popSize; i++) {
        initFunc(&ga->pop[i]);
    }
}

void evaluateFitness(GeneticAlgorithm *ga,
                    double (*fitnessFunc)(Individual*)) {
    for (int i = 0; i < ga->popSize; i++) {
        ga->pop[i].fitness = fitnessFunc(&ga->pop[i]);
    }
}

选择操作

轮盘赌选择

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
Individual* rouletteSelection(GeneticAlgorithm *ga) {
    double totalFitness = 0;
    for (int i = 0; i < ga->popSize; i++) {
        totalFitness += ga->pop[i].fitness;
    }
    
    double r = (double)rand() / RAND_MAX * totalFitness;
    double cumFitness = 0;
    
    for (int i = 0; i < ga->popSize; i++) {
        cumFitness += ga->pop[i].fitness;
        if (cumFitness >= r) {
            return &ga->pop[i];
        }
    }
    
    return &ga->pop[ga->popSize - 1];
}

锦标赛选择

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Individual* tournamentSelection(GeneticAlgorithm *ga, int k) {
    Individual *best = &ga->pop[rand() % ga->popSize];
    
    for (int i = 1; i < k; i++) {
        Individual *candidate = &ga->pop[rand() % ga->popSize];
        if (candidate->fitness > best->fitness) {
            best = candidate;
        }
    }
    
    return best;
}

排序选择

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void rankSelection(GeneticAlgorithm *ga, Individual *selected[], int count) {
    int indices[POP_SIZE];
    for (int i = 0; i < ga->popSize; i++) {
        indices[i] = i;
    }
    
    for (int i = 0; i < ga->popSize - 1; i++) {
        for (int j = 0; j < ga->popSize - i - 1; j++) {
            if (ga->pop[indices[j]].fitness < ga->pop[indices[j + 1]].fitness) {
                int temp = indices[j];
                indices[j] = indices[j + 1];
                indices[j + 1] = temp;
            }
        }
    }
    
    for (int i = 0; i < count; i++) {
        selected[i] = &ga->pop[indices[i]];
    }
}

交叉操作

单点交叉

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void singlePointCrossover(Individual *parent1, Individual *parent2,
                         Individual *child1, Individual *child2,
                         int chromoLen, double crossRate) {
    *child1 = *parent1;
    *child2 = *parent2;
    
    if ((double)rand() / RAND_MAX < crossRate) {
        int point = rand() % chromoLen;
        
        for (int i = point; i < chromoLen; i++) {
            child1->genes[i] = parent2->genes[i];
            child2->genes[i] = parent1->genes[i];
        }
    }
}

双点交叉

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void twoPointCrossover(Individual *parent1, Individual *parent2,
                      Individual *child1, Individual *child2,
                      int chromoLen, double crossRate) {
    *child1 = *parent1;
    *child2 = *parent2;
    
    if ((double)rand() / RAND_MAX < crossRate) {
        int point1 = rand() % chromoLen;
        int point2 = rand() % chromoLen;
        
        if (point1 > point2) {
            int temp = point1;
            point1 = point2;
            point2 = temp;
        }
        
        for (int i = point1; i <= point2; i++) {
            child1->genes[i] = parent2->genes[i];
            child2->genes[i] = parent1->genes[i];
        }
    }
}

均匀交叉

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void uniformCrossover(Individual *parent1, Individual *parent2,
                     Individual *child1, Individual *child2,
                     int chromoLen, double crossRate) {
    for (int i = 0; i < chromoLen; i++) {
        if ((double)rand() / RAND_MAX < 0.5) {
            child1->genes[i] = parent1->genes[i];
            child2->genes[i] = parent2->genes[i];
        } else {
            child1->genes[i] = parent2->genes[i];
            child2->genes[i] = parent1->genes[i];
        }
    }
}

变异操作

位翻转变异

C
1
2
3
4
5
6
7
8
void bitFlipMutation(Individual *individual, 
                    int chromoLen, double mutateRate) {
    for (int i = 0; i < chromoLen; i++) {
        if ((double)rand() / RAND_MAX < mutateRate) {
            individual->genes[i] = 1 - individual->genes[i];
        }
    }
}

交换变异

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void swapMutation(Individual *individual, 
                 int chromoLen, double mutateRate) {
    if ((double)rand() / RAND_MAX < mutateRate) {
        int i = rand() % chromoLen;
        int j = rand() % chromoLen;
        
        int temp = individual->genes[i];
        individual->genes[i] = individual->genes[j];
        individual->genes[j] = temp;
    }
}

逆转变异

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void inversionMutation(Individual *individual,
                      int chromoLen, double mutateRate) {
    if ((double)rand() / RAND_MAX < mutateRate) {
        int i = rand() % chromoLen;
        int j = rand() % chromoLen;
        
        if (i > j) {
            int temp = i;
            i = j;
            j = temp;
        }
        
        while (i < j) {
            int temp = individual->genes[i];
            individual->genes[i] = individual->genes[j];
            individual->genes[j] = temp;
            i++;
            j--;
        }
    }
}

完整遗传算法

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void geneticAlgorithm(GeneticAlgorithm *ga,
                     void (*initFunc)(Individual*),
                     double (*fitnessFunc)(Individual*)) {
    initPopulation(ga, initFunc);
    evaluateFitness(ga, fitnessFunc);
    
    Individual newPop[POP_SIZE];
    
    for (int gen = 0; gen < ga->maxGen; gen++) {
        int newPopSize = 0;
        
        while (newPopSize < ga->popSize) {
            Individual *parent1 = tournamentSelection(ga, 3);
            Individual *parent2 = tournamentSelection(ga, 3);
            
            Individual child1, child2;
            singlePointCrossover(parent1, parent2, 
                               &child1, &child2,
                               ga->chromoLen, ga->crossRate);
            
            bitFlipMutation(&child1, ga->chromoLen, ga->mutateRate);
            bitFlipMutation(&child2, ga->chromoLen, ga->mutateRate);
            
            newPop[newPopSize++] = child1;
            if (newPopSize < ga->popSize) {
                newPop[newPopSize++] = child2;
            }
        }
        
        for (int i = 0; i < ga->popSize; i++) {
            ga->pop[i] = newPop[i];
        }
        
        evaluateFitness(ga, fitnessFunc);
    }
}

Individual* getBest(GeneticAlgorithm *ga) {
    Individual *best = &ga->pop[0];
    for (int i = 1; i < ga->popSize; i++) {
        if (ga->pop[i].fitness > best->fitness) {
            best = &ga->pop[i];
        }
    }
    return best;
}

0-1背包问题实例

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef struct {
    int weight[CHROMO_LEN];
    int value[CHROMO_LEN];
    int capacity;
    int n;
} KnapsackProblem;

KnapsackProblem kp;

void knapsackInit(Individual *ind) {
    for (int i = 0; i < kp.n; i++) {
        ind->genes[i] = rand() % 2;
    }
}

double knapsackFitness(Individual *ind) {
    int totalWeight = 0;
    int totalValue = 0;
    
    for (int i = 0; i < kp.n; i++) {
        if (ind->genes[i]) {
            totalWeight += kp.weight[i];
            totalValue += kp.value[i];
        }
    }
    
    if (totalWeight > kp.capacity) {
        return 0;
    }
    
    return totalValue;
}

C++ 实现

C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
template<typename Gene>
class GeneticAlgorithm {
private:
    struct Individual {
        vector<Gene> chromosome;
        double fitness;
        
        bool operator<(const Individual& other) const {
            return fitness > other.fitness;
        }
    };
    
    function<void(vector<Gene>&)> initFunc;
    function<double(const vector<Gene>&)> fitnessFunc;
    function<void(const vector<Gene>&, const vector<Gene>&, 
                  vector<Gene>&, vector<Gene>&)> crossoverFunc;
    function<void(vector<Gene>&)> mutateFunc;
    
    vector<Individual> population;
    int popSize;
    int maxGen;
    double crossRate;
    double mutateRate;
    
    Individual select() {
        int k = 3;
        Individual best = population[rand() % popSize];
        for (int i = 1; i < k; i++) {
            Individual candidate = population[rand() % popSize];
            if (candidate.fitness > best.fitness) {
                best = candidate;
            }
        }
        return best;
    }
    
public:
    GeneticAlgorithm(int ps, int mg, double cr, double mr)
        : popSize(ps), maxGen(mg), crossRate(cr), mutateRate(mr) {}
    
    void setFunctions(
        function<void(vector<Gene>&)> init,
        function<double(const vector<Gene>&)> fitness,
        function<void(const vector<Gene>&, const vector<Gene>&, 
                      vector<Gene>&, vector<Gene>&)> cross,
        function<void(vector<Gene>&)> mutate
    ) {
        initFunc = init;
        fitnessFunc = fitness;
        crossoverFunc = cross;
        mutateFunc = mutate;
    }
    
    vector<Gene> solve() {
        population.resize(popSize);
        for (auto& ind : population) {
            initFunc(ind.chromosome);
            ind.fitness = fitnessFunc(ind.chromosome);
        }
        
        for (int gen = 0; gen < maxGen; gen++) {
            vector<Individual> newPop;
            newPop.reserve(popSize);
            
            while (newPop.size() < popSize) {
                Individual parent1 = select();
                Individual parent2 = select();
                
                vector<Gene> child1, child2;
                if ((double)rand() / RAND_MAX < crossRate) {
                    crossoverFunc(parent1.chromosome, parent2.chromosome,
                                 child1, child2);
                } else {
                    child1 = parent1.chromosome;
                    child2 = parent2.chromosome;
                }
                
                if ((double)rand() / RAND_MAX < mutateRate) {
                    mutateFunc(child1);
                }
                if ((double)rand() / RAND_MAX < mutateRate) {
                    mutateFunc(child2);
                }
                
                Individual ind1 = {child1, fitnessFunc(child1)};
                Individual ind2 = {child2, fitnessFunc(child2)};
                
                newPop.push_back(ind1);
                if (newPop.size() < popSize) {
                    newPop.push_back(ind2);
                }
            }
            
            population = newPop;
        }
        
        return max_element(population.begin(), population.end())
               ->chromosome;
    }
};

参数选择

参数 常用范围 影响
种群大小 50-200 太小多样性不足，太大计算量大
交叉概率 0.6-0.9 控制基因重组频率
变异概率 0.001-0.1 维持多样性，防止早熟
最大代数 100-1000 控制搜索时间

时间复杂度

  • 每代复杂度：O(popSize × fitnessCost)
  • 总复杂度：O(maxGen × popSize × fitnessCost)

应用场景

  1. 组合优化：TSP、调度、装箱
  2. 机器学习：特征选择、参数优化
  3. 电路设计：电路优化、布局
  4. 神经网络：权重优化、结构设计
  5. 游戏AI：策略优化

优缺点

优点

  1. 全局搜索：可跳出局部最优
  2. 并行性好：种群可并行评估
  3. 无需梯度：适用于不可导函数
  4. 灵活性强：编码方式多样

缺点

  1. 参数敏感：需要调参
  2. 早熟收敛：可能陷入局部最优
  3. 效率较低：需要大量评估
  4. 无最优保证：不保证找到全局最优

参考资料