java遗传算法排课如何性能优化？
问题描述
如图所示，在X轴上有5个点，分别为x1, x2, x3, x4, x5。这5个点的实际间距已知为L，但实际中由于测量误差的存在，每个点x1, x2, x3, x4, x5会有一系列如图中黑色圈内
问题描述
如图所示，在X轴上有5个点，分别为x1, x2, x3, x4, x5。这5个点的实际间距已知为L，但实际中由于测量误差的存在，每个点x1, x2, x3, x4, x5会有一系列如图中黑色圈内所示的测量点。那么如何在实际测量点中取值可以使得相邻位置的间距最接近L，问题可以描述为如下数学公式：
F=min∑|xi+1−xi−L|,1≤i≤4
F=min∑|xi+1−xi−L|,1≤i≤4
解决思路
通过查询资料发现，我要解决的问题和TSP问题（旅行商问题）很像。TSP问题中是预先给定数量已知位置固定的点，然后求得是旅行商人从任意一个点出发遍历所有的点（中间每个点只能经过一次）最后回到这个点时路径最短，具体可以参考维基百科旅行商问题。
我要解决问题的特点是点之间的间距固定，但每个点的位置上有n个测量点，我的最终目的是选择最优的测量点使得路径距离和4L之间的偏差最小，换言之也是使得路径的最短（只不过是与4L做差值之后最短），这就与TSP问题不谋而合了。虽然每个位置上有个n个测量点，但每次只从每个位置上取出一个测量点，这样就形成一条线路，然后计算路径间距，最后通过比较即可选择出最优的路径，这就和TSP问题求解的思路是一样的了。
但是如果遍历每个位置上的点来求所有的路线，这样当测量点数n比较大时计算量就相对很大了，所以就想到了用启发式搜索算法的方式来搜索最优解，最后使用遗传算法来解决这个问题。
遗传算法
遗传算法，顾名思义，可以联想到自然界种群繁衍、基因遗传的过程，实际上它也是借鉴进化生物学中的一些现象发展起来的（交叉，变异，选择以及遗传等等）维基百科遗传算法，是一种通过模拟生物进化过程搜索最优解的启发式搜索算法。
遗传算法的本质就是模仿自然界优胜劣汰、适者生存的过程。它往往从实际问题的解集出发通过一定的编码方式形成问题域中“基因”、“染色体”和“个体”的概念，进而确定初始种群（由一定数量的个体组成），然后根据问题域中的适应度函数（Fitness Function），通过一代代的选择（Selection）、交叉（Crossover）和变异（Mutation）等方式模拟这个种群的进化过程，最后逐渐进化出较好的个体（也就是解集中近似的最优解）。将遗传算法应用到实际问题的流程大致如下：
1. 对实际问题的解集进行编码，使其可以对应生物遗传过程中“基因”、“染色体”和“个体”的概念。比如本题中，解集就是每个位置上的随机选一个测量点连起来的路径，这样我可以对测量点进行编号，使得每个测量点就代表了一个“基因”，然后一条路劲就代表了一条“染色体”，进而形成一个个体（每个个体只有一条“染色体”）。具体如下图所示：
2. 确定问题域中的适应度函数（Fitness Function）。这个一般实际问题都会已经给出，比如本题中的适应度函数就是前面所述的数学公式：
F=min∑|xi+1−xi−L|,1≤i≤4
F=min∑|xi+1−xi−L|,1≤i≤4
3. 确定初始种群（population）。这个可以用random的方式随机生成，如果为了比较快的收敛到较优解，也可以一开始就生成一些表现优良的“个体”。
4. 然后根据适应度函数进行选择（Selection）、交叉（Crossover）和变异（Mutation），通过一定代数的遗传即可选出近似的最优解。
以上就是我查阅资料后对遗传算法的一个基本的理解，下面我将具体介绍每个步骤中使用的方法（包括编码的方式，个体的选择，交叉的方式等）并展示相应的代码。（如果还想对遗传算法有更深入的了解，可以看这里知乎如何通俗易懂的理解遗传算法）
解题过程
1. 编码方式
对问题域的解集进行编码，获得相应的“基因”、“染色体”等，常用的编码方式有两种：
1) 实数编码：使用实数进行编码（比如0，1，2等等）。
2) 二进制编码：这个编码方式就是使用二进制0、1来表示问题域中解集。
对于本题中，每个位置上有n个测量点，显然用二进制编码方式不太合适，而如果用实数编码的方式则可以很好的表示每个位置上的测量点。因此，我使用实数（0 ~ n-1）对每个位置上的测量点进行编号，这样我只要新建一个二维数组即可表示每个位置上的所有测量点。同时，使用random的方式随机生成测量点，即可将测量点的坐标值保存在数组中对应的位置。其代码如下：
//pointNum是位置数（本题中是5），realPointNum是每个位置上实际的测量点数
class GARandom {
private int pointNum,realPointNum;
public GARandom(int pointNum,int realPointNum) {
this.pointNum = pointNum;
this.realPointNum = realPointNum;
}
public double[][] randomInitPopulation(){
double[][] x = new double[pointNum][realPointNum];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
if(i == j){
x[i][j] = i * 10;//将一组收敛值放入其中，用以后面测试算法的性能
}else{
x[i][j] = i * 10 + (i + 1)*Math.random();
}
}
}
return x;
}
}
2. 确定适应度函数
本题的适应度函数就是要使得相邻位置的间距最接近L，即前面所描述的数学公式：
F=min∑|xi+1−xi−L|,1≤i≤4
F=min∑|xi+1−xi−L|,1≤i≤4
题目中有5个位置，也就是要选出使每两个相邻的位置最接近固定间距L的测量点。所以可以像TSP问题一样事先计算出相邻位置测量点之间的距离并将其保存在数组中，然后在种群进化的过程中，根据种群的“染色体”（也就是路径）计算出总的偏差，以此来判断其适应度的好坏（这里是距离越小适应度越好）。计算相邻位置测量点距离的代码如下：
//求得每两个位置，所有点之间的距离
distance = new double[pointNum - 1][realPointNum][realPointNum];
for (int i = 0; i < pointNum - 1; i++) {
for (int j = 0; j < realPointNum; j++) {
for (int k = 0; k < realPointNum; k++) {
distance[i][j][k] = Math.abs(x[i + 1][k] - x[i][j] - L);
}
}
}
评价个体适应度的代码如下：
//根据先验条件求得个体适应度，并根据适应度求得单个个体的概率以及个体的累积概率
//以便选择阶段使用
private void evaluate(int[][] chromosome) {
int k = 0;
double len = 0;
double sumFitness = 0;
double[] tempFitness = new double[scale];
//根据距离数组求得每条路径的适应度，也就是和固定距离L的偏差的和
while (k < chromosome.length) {
for (int i = 0; i < chromosome[k].length - 1; i++) {
len += distance[i][chromosome[k][i]][chromosome[k][i + 1]];
}
fitness[k] = len;
len = 0;
k++;
}
//求总的适应度
for (int i = 0; i < scale; i++) {
tempFitness[i] = 10.0 / (fitness[i] + 1);//计算适应度，这里距离越小适应度越大，因此采用倒数的方式表示
sumFitness += tempFitness[i];
}
//根据适应度，转化成相应的单个个体概率和个体的累积概率，用于后面的轮盘赌选择策略
double tempP = 0;
for (int i = 0; i < scale; i++) {
ps[i] = tempFitness[i] / sumFitness;//单个个体概率
tempP += ps[i];
pc[i] = tempP;//个体累积概率
}
}
3. 确定初始种群
这里我采用了随机生成的方式，但是为了使初始种群中能覆盖所有经过实数编号的测量点（0 ~ n-1），所以我让前n个体的“染色体”如下所示：
这种方式使得初始种群的前n个个体的“染色体”排列是全0，全1直到全n-1，这样尽可能将所有的测量点都覆盖进去，避免随机生成的时候漏掉一些测量点。其代码如下：
//生成父代种群的“染色体”，也就是随机选取每个位置上的点组成一个网络
//scale是种群规模，pointNum是位置数（x1-x5）
oldPopulation = new int[scale][pointNum];
for (int i = 0; i < scale; i++) {
for (int j = 0; j < pointNum; j++) {
if (i < realPointNum){
oldPopulation[i][j] = i;
}else{
oldPopulation[i][j] = rand.nextInt(realPointNum);
}
}
}
4. 选择（Selection）
确定初始种群后，就根据适应度函数计算出初代最优的个体，并将其直接遗传给子代。这里这么做的原因是，保存表现最优良的个体，让其余个体进行交叉或变异（当然还有其他的方式，这个由你自己决定），这种方式也叫做精英选择。然后通过轮盘赌选择方式，随机选择个体放到子代中去。这个轮盘赌选择方式是根据每个个体适应度占总适应度的概率进行选择的，想详细了解的可以看这篇博文轮盘赌策略。选择阶段的代码如下：
//精英选择（选择上一代中fitness最好的个体，然后直接保存到下一代中）
private void selectMaxFitness() {
int maxId = 0;
double tempFitness = fitness[0];
//
for (int i = 1; i < scale; i++) {
if (tempFitness > fitness[i]) {
tempFitness = fitness[i];
maxId = i;
}
}
if (bestLength > tempFitness) {
bestLength = tempFitness;
bestGen = t;
System.arraycopy(oldPopulation[maxId], 0, bestChoice, 0, pointNum);
}
copyPopulation(0, maxId);
}
//轮盘赌选择策略
private void select() {
int j, selectId;
double r;
selectMaxFitness();//精英选择，保留上一代fitness最好的个体
for (int i = 1; i < scale; i++) {
r = rand.nextDouble();
for (j = 0; j < scale; j++) {
if (r <= pc[j]) {
break;
}
}
if (j < scale) {
selectId = j;
copyPopulation(i, selectId);
}
}
}
5. 交叉（Crossover）
选择完之后，就要对这些个体进行“染色体”交叉，用以产生子代。交叉的方式有很多，我这里选择了最简单的单点交叉，即通过random.nextDouble()随机生成一个数，当它小于交叉概率时，即表明可以进行“染色体”的交叉，然后随机生成一个索引值，然后将相邻的“染色体”位于索引值后的部分进行交叉。其代码如下：
//单点交叉
private void crossover() {
for (int k = 1; k < scale/2; k += 2) {
double pCrossoverTemp = rand.nextDouble();
//小于交叉概率时进行“染色体”交叉,将交叉索引(包括交叉索引处的元素)后的元素进行互换
if (pCrossoverTemp <= pCrossover) {
int tempCrossover;
int indexCrossover = 1 + rand.nextInt(pointNum - 1);//排除索引值为0的情况，整体交换没有意义
for (int i = indexCrossover; i < pointNum; i++) {
tempCrossover = newPopulation[k][i];
newPopulation[k][i] = newPopulation[k + 1][i];
newPopulation[k + 1][i] = tempCrossover;
}
}
}
}
当然这是最最简单的交叉算子，如果想使用表现更好的算子，可以看这篇博文遗传算法中几种交叉算子。
6. 变异（Mutation）
变异这个部分，我没有查阅很多资料，直接用了最简单的单点变异。其代码如下：
private void mutation() {
for (int i = 1; i < scale; i++) {
double pMutationTemp = rand.nextDouble();
if (pMutationTemp < pMutation) {
//随机选择变异位置
int mutationIndex = rand.nextInt(pointNum);
//将变异位置的值保存下来
int temp = newPopulation[i][mutationIndex];
//获得变异值
int mutationTemp = rand.nextInt(realPointNum);
//确保变异值和之前的值不一样
while (mutationTemp == temp) {
mutationTemp = rand.nextInt(realPointNum);
}
newPopulation[i][mutationIndex] = mutationTemp;
}
}
}
7. 重复操作
从确定初代种群开始到经过第一次的选择、交叉和变异这就产生了第一个子代。然后重复4、5、6这三个步骤，整个遗传算法就有如自然界进化一般，在适应度函数的制约下，自动朝着最优解的方向“进化”而去，当然遗传算法一般得到只是最优解的近似解。
代码测试
测试输入
初始种群的大小设定为30，即初始种群包含30个个体;每个位置实际测量点的数量设定为10个;“进化”的代数设定为2000，即算法要历经2000代的“遗传进化”;相邻位置的固定间距设定为10;交叉概率定为0.8;变异概率定为0.1。
测试结果
由上图可以看出经过2000次的选择、交叉和变异，在固定间距是10的情况下，算法在第355代找到了最佳的路径01234，也就是我事先输入到数组的0，10，20，30，40这组数据。
