遗传算法C++实现

admin1

遗传算法是美国的J.Holland教授和他的学生于1975年受生物进化论的启发而提出并建立发展起来的。现在在诸多研究领域都有其应用。

主要涉及TSP求解问题；后来研究者的改进遗传算法也有很多。

遗传算法借鉴的是生物进化过程，遵循“适者生存”的规律。流程大概如下：



Step1
输入：种群大小、染色体长度、交叉概率、变异概率、停止规则

Step2
初始化种群

Step3
计算个体适应度

Step4
选择操作

Step5
交叉操作

Step6
变异操作



关于Step5和Step6，也有很多改进规则。
[code]#define POP_SIZE 600 // 群体大小
#define MAX_GEN 1000 // 最大迭代次数
#define PC 0.99                 // 交叉概率
#define PM 0.2                 // 变异概率
#define VariableNum 7 //
#define alpha 0.6         // 隐含的算法选择压力
[/code]

变异实现代码：

[code]void CAlgorithm::mutation(double x[POP_SIZE][VariableNum + 1])
{
        for (int i = 0; i < POP_SIZE; i++)
        {
                for (int j = 0; j < VariableNum; j++)
                {
                        if (rand() / 32767.0 < PM)
                        {
                                switch (rand()%3)
                                {
                                case 0:
                                {
                                        x[i][j] = Boundary[j][0] + (Boundary[j][1] - Boundary[j][0]) * rand() / 32767.0;
                                        break;
                                }
                                case 1:
                                {
                                        x[i][j] = x[i][j] + (Boundary[j][1] - x[i][j]) * rand() / 32767.0;
                                        break;
                                }
                                case 2:
                                {
                                        x[i][j] = Boundary[j][0] + (x[i][j] - Boundary[j][0]) * rand() / 32767.0;
                                        break;
                                }
                                default:
                                        break;
                                }
                        }
                }
        }
}[/code]