实现二进制遗传算法时频繁出现段错误，求排查原因

我正在做CodeWars上的《Training on Binary Genetic Algorithms》题目，题目预加载了fitness函数，测试时会生成随机35位字符串，我的run函数需要用遗传算法找到并返回这个字符串。但运行代码时，几乎总会在打印种群和适应度的环节触发段错误，代码如下：

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

typedef double fitness_t (const char *, ...);
extern fitness_t fitness;

void generate (size_t length, char * s)
{
  for (size_t i = 0; i < length; i++)
    s[i] = rand() % 2 + 48;
}

double sum(size_t n, double ar[n])
{
  double sum = 0;
  for (int i = 0; i < n; i++)
    sum += ar[i];
  return sum;
}
  
void select (int size, char* population[size], double fitnesses[size])
{
  double probabilities[size]; // normalized to 1
  double r;                   // random number
  int s1, s2;
  int i;
  
  for (i = 0; i < size; i++)
    probabilities[i] = fitnesses[i] / sum(size, fitnesses);
  
  // select first chromosome
  r = (double)(rand() % 1000000) / 1000000; // generates a random float between 0 and 1
  for (i = 0; i < size && r > 0; i++)
    r -= probabilities[i];
  s1 = i;
  
  // select second chromosome
  s2 = s1;
  while (s2 == s1) // ensures the two chromosomes aren't the same
  {
    r = (double)(rand() % 1000000) / 1000000; // generates a random float between 0 and 1
    for (i = 0; i < size && r > 0; i++)
      r -= probabilities[i];
    s2 = i;
  }

  // places these two chromosomes on top
  char * temp = population[0];
  population[0] = population[s1];
  population[s1] = temp;
  
  temp = population[1];
  population[1] = population[s2];
  population[s2] = temp;
}

void crossover (size_t n, char* s1, char* s2)
{
  int r = rand() % n; // select a random bit to cross over at
  char temp;

  for (size_t i = r; i < n; i++) // swap every bit from bit r to bit n
  {
    temp = s1[i];
    s1[i] = s2[i];
    s2[i] = temp;
  }
}
 
void mutate (size_t n, char* s, double p)
{
  double r;

  for (size_t i = 0; i < n; i++) // for each bit
  {
    r = (double)(rand() % 1000000) / 1000000;  // random float between 0 and 1
    if (r <= p)       // if random number is less than probability
    {
      if (s[i] == '1') s[i] = '0';    // swap 0s and 1s
      else s[i] = '1';
    }
  }
}

void bubbleSortPop(int size, char * population[size], double fitnesses[size])
{
    int i, j;
    char * temp_chrome;
    double temp_fitness;
    for (i = 0; i < size - 1; i++)
        // Last i elements are already in place
        for (j = 0; j < size - i - 1; j++)
            if (fitnesses[j] < fitnesses[j + 1])
            {
              temp_chrome = population[j];
              population[j] = population[j+1];
              population[j+1] = temp_chrome;
              
              temp_fitness = fitnesses[j];
              fitnesses[j] = fitnesses[j+1];
              fitnesses[j+1] = temp_fitness;
            }
}

// this function changes the population.
// select, crossover, mutate
void evolve(fitness_t f, size_t size, int length, char * population[size], 
            double fitnesses[size], double p_c, double p_m)
{
  char * s1, * s2;
  double f1, f2;
  char * temp_pop[size+2];
  double temp_fit[size+2];
  int i;
  double r;
  
  // moves two selected parents to the top
  select(size, population, fitnesses); 
  
  // begin reproduction process; duplicate the chromosomes
  s1 = population[0];
  s2 = population[1];
 
  // crossover
  r = (double)(rand() % 1000000) / 1000000;  // random float between 0 and 1
  if (r < p_c)                              // probability of crossing over
    crossover(length, s1, s2);              // commences with crossover
  
  // mutate
  mutate(length, s1, p_m);
  mutate(length, s2, p_m);
  
  // calculate fitnesses
  f1 = f(s1);
  f2 = f(s2);
  
  // merge fitneses
  // copy original fitnesses into temp_fit
  for (i = 0; i < size; i++)
    temp_fit[i] = fitnesses[i];
  // add new fitnesses
  temp_fit[size] = f1;
  temp_fit[size+1] = f2;  
  
  // merge children into population
  // copy original population into temp_pop
  for (i = 0; i < size; i++)
    temp_pop[i] = population[i];
  // add two children to temp_pop
  temp_pop[size] = s1;
  temp_pop[size+1] = s2;
 
  // sort fitnesses and population
  bubbleSortPop(size+2, temp_pop, temp_fit);
  
  // add first 100 elements of temp_pop and fit to population and fitnesses
  for (i = 0; i < size; i++)
  {
    population[i] = temp_pop[i];
    fitnesses[i] = temp_fit[i];
  }

}

char* runN (fitness_t f, int length, double p_c, double p_m, size_t iterations) {
}

char* run (fitness_t f, int length, double p_c, double p_m)
{
  size_t size = 100;
  char * population[size];
  double fitnesses[size];
  size_t i;
  int r;
  
  srand(time(0));
  
  // initialize population array
  for (i = 0; i < size; i++)
    population[i] = malloc((length+1) * sizeof(char));

  // generate original population
  for (i = 0; i < size; i++) 
  {
    generate(length, population[i]);  
    fitnesses[i] = f(population[i]);
    printf("[%2d] %s %lf\n", i, population[i], fitnesses[i]);
  }
 
  // evolve the population
  for (i = 0; i < 10; i++)
    evolve(f, size, length, population, fitnesses, p_c, p_m);
  
//   print result
  printf("\nAFTER EVOLUTION\n");
  for (i = 0; i < size; i++) // generates original population
    printf("[%2d] %s %lf\n", i, population[i], fitnesses[i]);
  
  // store best chromosome and free memory
  char ret[length+1];
  strcpy(ret, population[0]);
  
  for (i = 0; i < size; i++)
    free(population[i]);
  
  return ret;
}

错误原因及修复方案 #

1. 返回栈内存指针导致未定义行为

run函数中定义的char ret[length+1];是栈上的局部变量，函数返回后栈内存会被系统回收，此时返回这个指针会指向无效内存，后续操作会触发段错误或其他不可预测的行为。

修复：改用malloc在堆上分配内存存储结果：

// 替换原返回部分的代码
char *ret = malloc((length + 1) * sizeof(char));
if (ret == NULL) {
    // 内存分配失败处理，释放已分配的种群内存后返回NULL
    for (i = 0; i < size; i++)
        free(population[i]);
    return NULL;
}
strcpy(ret, population[0]);

for (i = 0; i < size; i++)
    free(population[i]);

return ret;

2. 字符串未添加结束符导致越界

generate函数只生成了length位字符，但没有在末尾添加字符串结束符'\0'，导致后续printf、strcpy等函数处理字符串时会读取超出分配内存的区域，触发段错误。

修复：在generate函数的循环结束后添加结束符：

void generate (size_t length, char * s)
{
  for (size_t i = 0; i < length; i++)
    s[i] = rand() % 2 + 48;
  s[length] = '\0'; // 添加字符串结束符
}

3. select函数中存在数组越界风险

在选择染色体时，循环结束后i可能等于size，此时population[s1]（即population[size]）会访问超出数组范围的内存（数组索引应为0到size-1）。

修复：调整选择逻辑，确保s1和s2的取值在合法范围内：

// 选择第一个染色体时
r = (double)(rand() % 1000000) / 1000000;
s1 = 0;
while (r > probabilities[s1]) {
    r -= probabilities[s1];
    s1++;
}
// 选择第二个染色体时
do {
    r = (double)(rand() % 1000000) / 1000000;
    s2 = 0;
    while (r > probabilities[s2]) {
        r -= probabilities[s2];
        s2++;
    }
} while (s2 == s1);

4. sum函数循环变量类型不匹配

sum函数的参数n是size_t类型，但循环用了int i，当n超过int的取值范围时会导致循环错误。

修复：将循环变量i改为size_t类型：

double sum(size_t n, double ar[n])
{
  double sum = 0;
  for (size_t i = 0; i < n; i++)
    sum += ar[i];
  return sum;
}

额外优化建议 #

• 增加内存分配失败的检查：malloc后要检查返回值是否为NULL，避免空指针操作。
• 调整进化迭代次数：当前只迭代10次，对于35位的目标字符串，可能不足以收敛到最优解，可以增加迭代次数或者根据适应度自动终止（比如当最优适应度达到最大值时提前结束）。

内容的提问来源于stack exchange，提问作者shrivelbottom