【摘要】：MPMC-RPRM问题是一个大规模的NP难组合优化问题，而遗传算法通常被用来求解这一类的问题。所以我们也提出一个求解MPMCRPRM的遗传算法。显然，我们提出的遗传算法试图在结果中搜索到最好的车次集合。遗传算法开始于生成一个初始的种群。在做交叉的过程中，运用启发式算法尽量避开两列相近的列车同时被选中的情形。在我们的计算中，遗传算法的终止时间为2个小时。表5-5基本模型、两阶段启发式算法和遗传算法的比较分析
MPMC-RPRM问题是一个大规模的NP难组合优化问题，而遗传算法通常被用来求解这一类的问题。所以我们也提出一个求解MPMCRPRM的遗传算法。遗传算法的基本思路是在种群（population）中的每一个个体（individual）代表一个发车的车次集合，最初，个体的一些子集的值被设定为1（ut=1）。然后再求解受限的BM来求得可能的最大目标值，把这个目标值作为个体的适应度（fitness）。显然，我们提出的遗传算法试图在结果中搜索到最好的车次集合（ut）。这里，用一系列0-1变量的值ut，∀t∈T作为个体的染色体，染色体的大小是|T|。
遗传算法开始于生成一个初始的种群。在我们的算例求解中，初始种群的大小设定为200。因为选中的列车次数∑t∈Tut越多，计算时间越长。所以，计算了一个运行列车次数的上限，这个上限的值为
在计算每一代种群时，一直选最好的80个个体作为下一代的父亲，这80个个体同样也会进入下一代种群中。
在做交叉的过程中，运用启发式算法尽量避开两列相近的列车同时被选中的情形。因为如果两个相邻的列车同时开出的话，后面的一列车通常不能获取足够多的需求。(www.xing528.com)
运用交叉算子产生的后代种群代替了原来的父种群，为了更快搜索到更优的解，考虑将变异算子用到后代种群的生成中。具体来讲，对每一个染色体中的ut，t会被以0.05的概率随机选中，被选中的ut的值变为1-ut。在我们的计算中，遗传算法的终止时间为2个小时。计算结果见表5-5。
表5-5 基本模型、两阶段启发式算法和遗传算法的比较分析
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
