C 语言遗传算法求解多项式

（一）题目简述

基于遗传算法的优化问题求解。通过对给定多项式函数进行优化，实现迭代优化计算找到使其取得最小值的变量x的解。

设计目标：

1. 寻找多项式函数的最小值：通过遗传算法，对给定的多项式函数进行优化，找到使其取得最小值的解。

2. 提高搜索效率：通过选择、交叉和变异操作，增加种群的多样性，提高搜索的广度和深度，以更快地找到最优解。

3. 使用随机数生成函数：通过srand()和rand()这两个常用的随机数生成函数，实现选择、交叉和变异操作中的随机性。

4. 应用链表、排序、文件操作和位运算：利用链表数据结构存储和操作种群，使用排序算法对种群进行排序，通过文件操作实现数据的读取和保存，利用位运算进行交叉和变异操作。

5. 实现多项式求解：设计算法能够求解给定的多项式函数，并根据误差要求找到使函数取得最小值的变量x的解。

6. 可扩展性和可维护性：代码的设计考虑到算法的可扩展性，采用函数调用，和宏常量设置参数，可以应用于不同的优化问题，并能够灵活调整遗传算法的参数。

代码实现过程分析：

2. 计算适应度：根据多项式函数计算每个个体的适应度。

3. 选择操作：根据适应度值选择父本个体，使用锦标赛选择算法进行选择。

4. 交叉操作：通过随机选择交叉点，将父本个体的基因序列进行交叉，生成新的个体。

5. 变异操作：根据设定的变异概率，对个体的基因序列进行变异，引入新的基因。

6. 更新种群：将生成的新个体加入种群，并通过新个体优化种群基因产生新个体。

7. 判断终止条件：设定的终止条件，判断是否达到最优解或迭代次数超过限制。

8. 输出结果：输出找到的最优解及对应的适应度值。

1.针对给定的多项式函数，通过遗传算法优化问题求解程序找到使其取得最小值的变量x的解。

2.实现灵活对遗传算法参数（例如种群个数，最优解个数，交叉变异概率）参数修改的，以适应不同问题的求解，增强程序的精准度

3.对代码内各部分功能进行封装，尽可能满足工程需求。

初始化种群，在定义域范围创建个体基因型，通过排序找出适应度最高的个体基因型并进行保存，然后使用这一代的最优基因型，对种群基因型进行优化产生下一代，然后不断迭代进化，直至产生符合精度的最优解，然后终止迭代输出最优值。

注；遗传算法中采用染色体结构体作为基本单位；包含染色体基因型（x的值）和适应度（符合函数要求的值）作为一个单位，但在此项目由于所求函数并不复杂，所以为了简化代码，在定义时用数组代替了种群，而数组中的每一个元素代表元素的基因型。每一个基因型（x）通过函数求出一个y，作为适应度。

- double类型的数组x，用于存放种群的基因型。

- double类型的数组sorted_x，用于存放排序后的种群。

种群基因库:double x[POPULATION_SIZE];

选出的最优解的基因：sorted_x[ELITISM_COUNT];

#define POPULATION_SIZE 100//定义种群大小

#define MAX_GENERATIONS 1000//定义最大迭代次数

#define CROSSOVER_RATE 0.8//定义基因交叉概率

#define MUTATION_RATE 0.5//定义变异概率

#define ELITISM_COUNT 2//保留最优解个数 ；即每个进化周期保留最优解个数

#define precision 0.001//设置精度

double lower_bound = -8;//区域最小值

double upper_bound = 8;//区域最大值

注：这里参数基本采用宏常量定义，方便后期对参数进行修改调整，增强了代码的可扩展性，和灵活性

本算法利用遗传算法，模仿生物遗传进化交叉变异操作进行优化不断迭代不断提高算法搜索的广度.深度和精度，最终输出符合精度的x的值。

   3.2算法主要步骤（伪码描述）

//直接用数组存放种群 :即函数的基因型

double x[POPULATION_SIZE];

//初始化种群，利用时间戳随机数在定义域内随机取基因

void initializePopulation(double x[POPULATION_SIZE]);

//进行排序这里利用冒泡排序，选出最优解

void sum(double x[POPULATION_SIZE], double sorted_x[ELITISM_COUNT]);

//进行迭代产生下一代种群包含交叉变异操作

void evolution(double sorted_x[ELITISM_COUNT ], double x[POPULATION_SIZE]);

//判断终止条件计算当前最优值时y函数值的平均差值

double end(double sorted_x[ELITISM_COUNT ]);

//计算当最优解的值；用于输出

double sum2(double sorted_x[ELITISM_COUNT ]);

//使用while循环判断是否终止迭代

while (generation < MAX_GENERATIONS)

4.1时间复杂度分析：

计算每个x对应的y值的时间复杂度是O(N)，其中N为种群数量。

快速排序的时间复杂度为O(NlogN)，其中N为种群数量。

将排序后前n大的元素存储到sorted_x数组中的时间复杂度为O(n)，其中n为前n大的元素个数，即ELITISM_COUNT。

所以整个函数的时间复杂度为O(NlogN + n)。

补充：在给基因编码的过程中采用十进制编码

4.2空间复杂度分析：

x和y数组的空间复杂度均为O(N)，其中N为种群数量。

temp_val、pivot和i、j都是常量的空间复杂度。

sorted_x数组的空间复杂度为O(n)，其中n为前n大的元素个数，即ELITISM_COUNT。

因此整个函数的空间复杂度为O(N + n)

五.编码实现

#include //基本的输入前输出函数

#include

#include

#include

#define POPULATION_SIZE 100//定义种群大小

#define MAX_GENERATIONS 1000//定义最大迭代次数

#define CROSSOVER_RATE 0.8//定义基因交叉概率

#define MUTATION_RATE 0.5//定义变异概率

#define ELITISM_COUNT 2//保留最优解个数 ；即每个进化周期保留最优解个数

#define precision 0.001//设置精度

double lower_bound = -8;//区域最小值

double upper_bound = 8;//区域最大值

double sorted_x[ELITISM_COUNT ];

//直接用数组存放种群 :即函数的基因型

double x[POPULATION_SIZE];

//初始化种群

void initializePopulation(double x[POPULATION_SIZE]);

//进行排序

void sum(double x[POPULATION_SIZE], double sorted_x[ELITISM_COUNT]);

//进行迭代产生下一代种群包含交叉变异操作

void evolution(double sorted_x[ELITISM_COUNT ],double x[POPULATION_SIZE]);

//判断终止条件

double end(double sorted_x[ELITISM_COUNT ]);

//计算当最优解的值

double sum2(double sorted_x[ELITISM_COUNT ]);

int main() {

    double x[POPULATION_SIZE];

    srand(time(NULL));     // 使用当前时间作为随机数种子

    initializePopulation(x);  // 调用函数进行初始化

    int generation =0;

    while (generation < MAX_GENERATIONS) {

    sum( x,sorted_x);//进行排序

    evolution(sorted_x,x);//进行迭代

 double avg_delta =end(sorted_x);//判断当前精度

 double y = sum2(sorted_x);

    if (avg_delta

        // 使用当前时间作为随机数种子

   x[i] = (double)rand() / RAND_MAX * (upper_bound - lower_bound) + lower_bound;//TODO

}

}

void sum(double x[POPULATION_SIZE], double sorted_x[ELITISM_COUNT]) {

    double y[POPULATION_SIZE];

    double temp;

    // 计算每个x对应的y值

    for (int i=0; i

        for (int j=0; j

                // 交换y值

                temp = y[j];

                y[j] = y[j+1];

                y[j+1] = temp;

                // 紧随其后交换x值

                temp = x[j];

                x[j] = x[j+1];

                x[j+1] = temp;

            }

        }

    }

for (int i = 0; i

for(int i=0;i

if ((double)rand() / RAND_MAX < CROSSOVER_RATE) {

int n = ELITISM_COUNT;   // 生成 0 到 n-1 的随机整数

    int random_num = rand() % ELITISM_COUNT;

        double alpha = (double)rand() / RAND_MAX;

        double* ptr =&x[i];

        *ptr = (alpha * x[i] + (1 - alpha) * sorted_x[n])/2;

    } if ((double)rand() / RAND_MAX < MUTATION_RATE) {

        x[i] = (double)rand() / RAND_MAX * (upper_bound - lower_bound) + lower_bound;

    }

}

}

double end(double sorted_x[ELITISM_COUNT]) {

  double y[POPULATION_SIZE];

  for (int i=0; i

    deltas[i-1] = y[i-1] - y[i];

  }

  double total_delta = 0.0;

  for (int i = 0; i < ELITISM_COUNT - 1; i++) {

    total_delta += deltas[i];

  }

  double avg_delta = fabs(total_delta / (ELITISM_COUNT - 1));

  return avg_delta;

}

double sum2(double sorted_x[ELITISM_COUNT ]){

double y = sorted_x[0] * sorted_x[0] - 4 * sorted_x[0];

return y;

}

第一次测试：

参数设置；种群数量为10 最大迭代为1000次 交叉概率为0.8 变异概率为0.2

运行结果；由于种群数量太小在，最大迭代次数内未达到要求精度

分析；

种群数量影响取值种群基因的类型，影响搜索广度，因此种群数量不能过小

第二次测试；

参数设置；种群数量为50 最大迭代为10000次 交叉概率为0.8 变异概率为0.2

运行结果；在7376次迭代后出现了目标值

分析；增加了种群数量，提高选值速率

第三次测试；

参数设置；种群数量为100 最大迭代为10000次 交叉概率为0.8 变异概率为0.2

运行结果

分析；增加了种群数量，提高选值速率

......省略

（注:这里仅仅展示了对种群复杂度对算法速率的影响，在后面的测试中依次对交叉和变异概率等参数的选择进行了分析，后面结论在总结中体现.）

此部分从基本功能、拓展创新两个方面的完成情况进行总结。

结合任务书的要求总结本课题实现的功能，调试过程中遇到的问题、分析原因给出解决的方法。有没有功能上的拓展创新，以后算法可以改进的方向等。

（一）基本功能：

1.程序基本功能达到预期，使用了遗传算法，能够在一定的迭代次数后完成在定义域内对于目标函数最小值的符合精度的解。

2.使用了宏常量定义参数，可以随时进行更改参数进行优化调整。

3.封装函数合理，而且使用工程设计流程，在调用前先对函数进行了声明，

增加了代码的可读性和拓展性。

（二）拓展创新；

1.在编译第一代程序使使用了遗传算法标准模式，采用结构体数组记录种群基因，复杂了问题。在第二代设计中，打破了标准遗传算法模型，采用遗传算法思想，而不使用结构体，直接使用数组记录种群基因。大大降低了代码的复杂度，和空间效率。在实现代码使仅仅使用了两个数组，就完成了代码的实现。针对问题善于思考打破常规很重要。

（三）算法分析总结

当前程序优点；

需要改进的地方:

因此这几个参数要根据问题适当调整测试，不能太大也不能太小。

据我测试数据

当前函数正常参数区间

  群数量30-200

最大迭代次数10000+

交叉概率0.7-0.9

变异概率0.1-0.3

最优值个数 1-5

是否可以通过算法直接求出参数最佳值，然后用于计算