【遗传算法c语言代码】遗传算法（Genetic Algorithm, GA）是一种基于自然选择和遗传机制的优化算法，广泛应用于复杂问题的求解中。它通过模拟生物进化过程，如选择、交叉、变异等操作，逐步逼近最优解。本文将对遗传算法的基本原理进行总结，并提供一个简单的C语言实现示例。
一、遗传算法基本原理总结
| 步骤 | 描述 | 目的 |
| 1. 初始化种群 | 随机生成一定数量的个体（染色体） | 构建初始解空间 |
| 2. 适应度评估 | 计算每个个体的适应度值 | 衡量个体优劣 |
| 3. 选择 | 根据适应度值选择优良个体 | 保留优质解 |
| 4. 交叉 | 随机选择两个个体进行基因交换 | 增加多样性 |
| 5. 变异 | 随机改变某些基因 | 避免陷入局部最优 |
| 6. 迭代终止 | 判断是否达到最大迭代次数或满足终止条件 | 结束算法运行 |
二、遗传算法C语言代码示例
以下是一个简单的遗传算法实现，用于求解函数最小值问题：
目标函数： $ f(x) = x^2 $
搜索范围： $ x \in [-10, 10] $
```c
include
include
include
include
define POP_SIZE 100
define CHROM_SIZE 10
define MAX_GEN 100
define MUT_RATE 0.01
typedef struct {
int gene[CHROM_SIZE]; // 染色体
double fitness; // 适应度
} Individual;
// 将二进制编码转换为十进制
double bin_to_dec(int gene) {
int i;
double val = 0;
for (i = 0; i < CHROM_SIZE; i++) {
val += gene[i] pow(2, CHROM_SIZE - 1 - i);
}
return val - 512; // 转换到 [-10, 10
}
// 适应度函数
double calculate_fitness(int gene) {
double x = bin_to_dec(gene);
return x x;
}
// 初始化种群
void init_population(Individual pop) {
int i, j;
srand(time(NULL));
for (i = 0; i < POP_SIZE; i++) {
for (j = 0; j < CHROM_SIZE; j++) {
pop[i].gene[j] = rand() % 2;
}
pop[i].fitness = calculate_fitness(pop[i].gene);
}
}
// 选择操作（轮盘赌）
int select_parent(Individual pop) {
double total_fit = 0;
for (int i = 0; i < POP_SIZE; i++) {
total_fit += pop[i].fitness;
}
double r = (double)rand() / RAND_MAX total_fit;
double sum = 0;
for (int i = 0; i < POP_SIZE; i++) {
sum += pop[i].fitness;
if (sum >= r) return i;
}
return 0;
}
// 交叉操作
void crossover(Individual parent1, Individual parent2, Individual child1, Individual child2) {
int point = rand() % CHROM_SIZE;
for (int i = 0; i < point; i++) {
child1->gene[i] = parent1->gene[i];
child2->gene[i] = parent2->gene[i];
}
for (int i = point; i < CHROM_SIZE; i++) {
child1->gene[i] = parent2->gene[i];
child2->gene[i] = parent1->gene[i];
}
}
// 变异操作
void mutate(Individual ind) {
for (int i = 0; i < CHROM_SIZE; i++) {
if ((double)rand() / RAND_MAX < MUT_RATE) {
ind->gene[i] ^= 1;
}
}
}
// 主函数
int main() {
Individual pop[POP_SIZE];
Individual new_pop[POP_SIZE];
init_population(pop);
for (int gen = 0; gen < MAX_GEN; gen++) {
for (int i = 0; i < POP_SIZE; i += 2) {
int p1 = select_parent(pop);
int p2 = select_parent(pop);
crossover(&pop[p1], &pop[p2], &new_pop[i], &new_pop[i + 1]);
mutate(&new_pop[i]);
mutate(&new_pop[i + 1]);
new_pop[i].fitness = calculate_fitness(new_pop[i].gene);
new_pop[i + 1].fitness = calculate_fitness(new_pop[i + 1].gene);
}
for (int i = 0; i < POP_SIZE; i++) {
pop[i] = new_pop[i];
}
// 找出当前最优解
double best_fit = 1e9;
for (int i = 0; i < POP_SIZE; i++) {
if (pop[i].fitness < best_fit) {
best_fit = pop[i].fitness;
}
}
printf("Generation %d: Best Fitness = %.6f\n", gen, best_fit);
}
return 0;
}
```
三、总结
遗传算法是一种强大的全局优化方法，适用于难以用传统数学方法解决的问题。在C语言中实现遗传算法时，需要注意以下几个关键点：
- 编码方式：通常采用二进制编码，便于交叉和变异操作。
- 适应度函数：是决定个体优劣的核心指标。
- 选择策略：轮盘赌选择是一种常用方法，但也可尝试其他策略如锦标赛选择。
- 交叉与变异：控制好交叉率和变异率，避免过早收敛或无法找到最优解。
通过以上代码示例，可以快速上手遗传算法的C语言实现，并根据具体问题进行调整和优化。