引言

遗传算法是由美国的 Holland 教授于 1975 年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子( 选择、交叉和变异) 对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其工作流程可以概括成下图：

需要指出的是，适应度函数、选择、交叉和变异操作均要根据实际问题进行灵活变更，并非固定模式。本文下面针对TSP这个特定问题，给出实际采用的方案。

实现思路

本文采用面向对象思想实现，分别创建了如下的若干类：

• GeneticAlgorithm：遗传算法类，工作流程环节对应的若干操作均由该类实现
• SpeciesNode：物种结点类，含有基因序列、路径长度、适应度等参数
• List<SpeciesNode>：种群链表类，链接物种构成种群的类
• Constant：常量类，存储地图数据、种群上限数、进化代数、交叉概率、变异概率等参数

初始化种群

不管这个遗传算法有多少道工序，每道工序多么复杂，总得有个开始点吧。那么第一道工序，就是要初始化一波各式各样、不同类型物种（表现在程序上就是基因序列即城市序列不同）构成的种群。所以我们先创建一个种群类：

class SpeciesNode 
{	
    int[] genes;//基因序列
    float distance;//路程
    float fitness;//适应度
    float rate;//轮赌概率

    //构造函数
    ......
    
    //生成初始基因
    void createGenes()
    {
        //初始化基因为1-CITY_NUM序列
        for(int i = 0;i < genes.length;i++)
            genes[i]=i+1;
        
        //获取随机种子
        Random rand=new Random();

        for(int j=0;j<genes.length;j++)
        {
            int num= j + rand.nextInt(genes.length-j);
            
            //交换
            int tmp;
            tmp=genes[num];
            genes[num]=genes[j];
            genes[j]=tmp;
        }
    }
    
    //计算适应度
    void calFitness()
    {
        ......
    }
}

前面提过，基因序列genes对应着城市序列，即相当于有了一条巡回路线。上面的createGenes()函数采用随机策略初始化出了一段基因序列，但事实上不止这一种初始化策略，还有一种使用较多的是“贪婪策略”，它可以在初始化的时候就快速地锁定在一波路线都较短的种群，其算法流程如下：

Step1  随机初始化一个起始城市\({n_i}\)，追加至genes

Step2  若genes已满，转Step4；反之，选出从\({n_i}\)出发到其它所有城市中路线最短的城市\({n_j}\)

Step3  将\({n_j}\)追加至genes，作为新的\({n_i}\)，转Step2

Step4  生成genes，结束

具体落实到代码实现上，我们可以使用一个类型为HashMap<Integer>的禁忌表记录已经加入genes的城市，以便在筛选最短城市的时候，可以用它的contains方法先快速判断下该城市是否已加入genes，从而不再参与下一步路线长度的谁小的比较运算，一定程度上缓解了遍历genes的低效。具体代码这里就不贴出来啦。

这种策略看似提升了效率，但却也往往容易陷入局部最优解，因为有时一个当前看起来较次的解，很有可能在经过几轮选择、交叉、变异后超越之前保留的那些局部最优解，究其原因我目前也是很困惑，或许这就是随机算法的魅力吧，或者可以说是大自然进化的神奇。

既然有了genes，那就立马可以算出这条路线的长度distance了，进而我们又可以通过distance算出该物种的适应度fitness。下面我们就来看看这个适应度函数是怎么把distance映射成fitness的。

计算适应度

适应由适应度函数产生，是描述个体性能好坏的主要指标，根据适应度的大小对个体进行优胜劣汰。适应度函数的选择对算法收敛性、收敛速度的影响很大，针对不同的问题需要根据经验来确定相应的参数。下面我们就讨论下TSP问题中常采用的适应度函数：

假设现在有物种：\[s = {n_1},{n_2}, \cdots ,{n_n},{n_1}\]我们很容易求出它的基因序列所表达的巡回路线长度：\[d(s) = \sum\limits_{j = 1}^n {d({n_j},{n_{j + 1}})} \]因为我们更希望路线长度较短的物种生存下来（当然目前路线长度较长的也并不意味着他的后代物种长度也长），而如果直接拿\(d(s)\)作为适应度岂不是南辕北辙了吗？所以我们采用“取倒数”的方法来处理，得到适应度函数：\[f(s) = \frac{1}{{d(s)}}\]下面是SpeciesNode类中计算适应度的函数calFitness的代码实现：

//计算物种适应度
void calFitness()
{
    float totalDis=0.0f;
    for(int i = 0;i < Constant.CITY_NUM;i++)
    {
        int curCity=this.genes[i]-1;
        int nextCity=this.genes[(i+1) % Constant.CITY_NUM]-1;

        totalDis += Constant.disMap[curCity][nextCity];
    }
    
    this.distance=totalDis;
    this.fitness=1.0f/totalDis;
}

结语

为物种评出了它的适应度后，接下来等待着我们的就是GeneticAlgorithm类中选择算子、交叉算子和变异算子的实现啦，会在下一章一一给出详尽阐述，敬请期待。