第四篇 如何用随机算法求解组合优化问题（十一）
清华大学计算机系 马少平
第十一节：用遗传算法求解旅行商问题
小明：关于遗传算法介绍了这么多的内容，请艾博士举一个具体求解的例子吧。
艾博士：好的，下面我们还是以旅行商问题为例，看看如何用遗传算法求解该问题。我之前编写过一个遗传算法求解旅行商问题的程序，下面将我在程序中用到的参数和方法做个介绍。
（1）编码方案采用整数编码。
（2）群体规模N为400，程序中要求群体规模为偶数，因为在做交叉操作时，需要群体中的个体两两配对。
小明：群体规模为偶数是遗传算法的要求吗？
艾博士：遗传算法并没有要求群体规模一定为偶数，但考虑到交叉操作是成对进行的，群体规模为偶数更方便一些。
（3）进化代数为500代，也就是完成了500代进化后算法就结束。
（4）选择操作采用轮盘赌的方法进行。
（5）适应函数采用非线性加速方法。由于旅行商问题求解的是最短路径，在程序中将非线性加速方法做了如下修改，以适应求解最小值问题，其中的M取20。
艾博士：小明你看这个适应函数与我们在前面介绍过的非线性加速方法有什么区别？
小明对比了一下两个公式后说：将原来公式分母中的fmax-f(x) 修改为了f(x)-fmin ，我明白了，这样修改后就将一个最小值问题转化为了最大值问题，挺巧妙的一个方法。
（6）交叉概率 Pc 选取为0.6，采用常规交叉法进行交叉操作，具体请看前面常规交叉法的讲解。
（7）变异概率Pm 选取为0.2，采用逆序交换的方法进行变异操作。
讲解到这里艾博士对小明说：上述内容我们前面都讲解过了，作为练习，回家后写一个用遗传算法求解旅行商问题的程序吧？前面也给过10城市和20城市的例子，你可以做一个测试，看看结果如何。
小明：好的，我这就回去写程序，艾博士，再见。
第二天小明带着自己写的程序来找艾博士：艾博士，程序我写好了，也进行了测试。开始时我并没有用你提供的参数，想自己试试看看什么样的参数是合适的。但是刚开始效果很不好，运行多次也很难找到最优解。经过几次参数调整后，虽然提高了找到最优解的概率，但是觉得效果还是不太理想，找到最优解的概率比较低。最后我采用了您提供的参数和交叉、变异的操作方法，发现效果非常好，运行了几千次，几乎每次都能得到最优解。我想知道您是如何做到这一点的？
艾博士笑了笑说：刚开始时我跟你是一样的，效果也很不理想，经过反复调整测试，才有了现在这个结果。
小明：看来还是需要多调整多测试啊。
艾博士：我们讲解的只是算法的基本原理，在具体使用这些算法解决实际问题时，还会遇到很多的问题。当运行结果不理想时，不要轻易否定算法的实用性，可能需要反复调整参数和具体方法，才可能会有比较好的结果。
小明：我记住了，谢谢艾博士的反复教诲。
小明读书笔记
结合旅行商问题实例，给出利用遗传算法求解该问题的具体方法，包括编码方法、群体规模、选择方法、交叉方法、变异方法和适应函数等。
未完待续