基于hga的最小旅行时间多旅行商问题研究
周辉仁1，唐万生1，魏颖辉2
（1天津大学系统工程研究所，天津300072;2辽宁科技学院管理系，辽宁本溪117022）
摘 要：为了解决最小化旅行时间的多旅行商一类问题，提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点，采用一种递阶编码方案，此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子，操作简单，并且解码方法适于求解距离矩阵对称和距离矩阵非对称的多旅行商问题。计算结果表明，递阶遗传算法是有效的，能适用于优化最小化完成时间的多旅行商问题。
关键词：递阶遗传算法；多旅行商问题；最小完成时间；解码方法
中图分类号：tp 27 文献标识码ia
1引 言
旅行商问题( tsp)是一个典型的组合优化难题，它在许多领域都有着广泛的应用，已被证明属于np问题jij。有关tsp问题的研究在现实问题中有很大的使用价值。诸如：交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等，都可抽象成tsp或mtsp问题[2-5]。为了有效地解决最小旅行时间、距离矩阵对称或者非对称的多旅行商问题，本文提出了一种递阶遗传算法和矩阵解码方法，以便确定每个城市由哪个旅行商经过以及各个旅行商的行走路线，即找到一个****旅行商分配及行走路线，在各旅行商行走完后，使耗用时间****的那个旅行商的时间最小。仿真结果证明，本文提出的算法鲁棒性好、运行效率高，具有实际应用的价值。
2 mtsp数学模型
所谓tsp问题是指：有ⅳ个城市，要求旅行商到达每个城市各一次，且仅一次，并回到起点，且要求旅行路线最短。而多路旅行商问题( mtsp)是指m个旅行商从同一个城市（或不同城市）出发，分别走一条旅行路线，使得每个城市有且仅有一个旅行商经过（出发城市除外），且总路程最短。
以点0表示旅行商的出发城市，称为源点，点l…，z表示m个旅行商需访问的城市。
定义变量：
约束条件为
式中，s为支路消去约束，即消去构成不完整路线的解，具体方法可参见文献[6]。
在该模型中，式(1)表示使m个旅行商中的旅行时间****的那个最小化；式(2)表示各个旅行商的耗用时间；式(3)表示从指定城市o出发，所有城市只有某一个旅行商严格访问一次；式(4)表示任一条弧的终点城市仅有一个起点城市与之相连；式(5)表示任一条弧的起点城市仅有一个终点城市与之相连；式(6)表示消去构成不完整线路的解。
3递阶遗传算法
在生物学领域，染色体的结构是一系列基因按层次排列而成的，一些基因控制着另一些基因。染色体可表示为包括控制基因和参数基因的递阶结构，参数基因处于****级，控制基因处于上级，下级基因串受上级基因的控制。在基因编码时，控制基因常采用整数编码，不同整数信息表示对应的基因处于不同的激活状态，而与该基因相联系的低级基因申则处于对应的状态。为计算方便和加强遗传算法在解空间的搜索能力，参数基因采用实数编码，每个基因用一个实数代表。这样定义染色体结构的遗传算法称为递阶遗传算法，它比传统遗传算法包含更多的信息，因而能处理更复杂的问题。目前，递阶遗传算法已在神经网络、模糊系统、车间调度等得到了较好的应用。
4递阶遗传算法设计
基于多旅行商问题的特点，可以设计成二级递阶染色体结构描述多旅行商问题的结构和参数，控制基因中的每一个等位基因表示城市，参数基因中的每一个等位基因表示所路过的旅行商。对于给定问题，其控制基因和参数基因个数是确定的，都为城市个数，控制基因取值为1至(z—1)中互相等的整数，参数基因取值为1至m中的整数，m为旅行商个数，因此优化多旅行商问题只需确定基因信息。
|
