巢湖学院计算机系2009届毕业设计（论文） 8 7 9 3 7-9-3 9-3 3 null 3 2 2 1 (2) 解码过程，从最后一个码字开始，每当遇到在该码字之前的不大于该码字的码，则将当前码字加一，则可实现解码，如表5.2，
表5.2 Grefenstette解码过程
排序（Grefenstette码逆序） 1 2 2 3 2 2 2 1 1
当前码字之前的码字 1-1-2-2-2-3-2-2 1-1-2-2-2-3-2 1-1-2-2-2-3 1-1-2-2-2 1-1-2-2 1-1-2 1-1 1 null 当前城市 3 9 7 8 6 5 4 2 1 由于采用这种顺序表示技术，可以采用基本遗传算法的交叉操作，例如， 单点交叉的情形，交叉前，父个体1和父个体2分别为: p1: (1 1 2 2 | 2 3 2 2 1) p2: (2 1 2 2 | 5 2 2 1 1) 它们代表旅程分别为: 1-2-4-5-6-8-7-9-3 2-1-4-3-9-6-7-5-8
两个个体在交叉点处进行基因重组，生成子个体1和子个体2，分别为 p1: (1 1 2 2 5 2 2 1 1) p2: (2 1 2 2 2 3 2 2 1) 它们代表旅程分别为: 1-2-4-5-9-6-7-3-8 2-1-4-5-6-8-7-9-3
从上述的单点交叉来看，Grefenstette编码可以有效地解决传统交叉导致的无意义的解带来的问题。 5.1.4、变异操作，
本系统设计使用互换变异，随机选择染色体中的两个位置，并将这两个城市的位置互换对于基于路径表示的TSP问题的遗传算法，在同一染色体的上随机选择两个位置进行翻转和交换其值似乎是最有效的方法。1986年Grefenstette测试到，随机的选择
23
巢湖学院计算机系2009届毕业设计（论文）
两个点并将这两个点中的子路径翻转的变异操作是很有效的。1987年Grefenstette采用了2-opt局部提高操作作为一种变异操作，这种变异操作在作业调度问题中得到了很好的解【19】. 5.2、程序设计具体细节：
5.2.1、编码方式：采用路径表示，结合Grefenstette编码。 5.2.2、种群进化方式：采用代进化。
5.2.3、选择算子：赌轮式选择以及经营策略。
5.2.4、交叉算子：对路径表示进行Grefenstette编码，然后进行传统的单点交叉，然后解码。
5.2.5、变异算子：随机选择两个城市互换位置
5.2.6、适应度函数设计：对每个体，采用染色体长度*MAX-个体路径总和，其中MAX表示城市之间距离允许的最大值。
5.2.7、参数设置：种群大小，交叉概率，变异概率，进化代数都有用户通过界面提供，如图5.1所示。
5.2.8、一点改进：为了防止遗传算法出现局部最优(早熟)，我们独立的调用遗传算法m次，选取其中最优的个体。M由用户通过界面提供。 5.3、界面设计：
利用java很容易进行程序设计，本系统利用Visual editor进行界面程序设计，通过该界面用户可以提交遗传算法的参数，提供输入文件，当遗传算法运行结束时，界面反馈给用户。界面如图5.1
图5.1 用户界面
5.4、程序的总体架构设计
遗传算法程序，界面程序相对独立的设计，界面程序负责与用于交互，并调用遗传算法。遗传算法根据界面程序提供的参数设置，给出TSP问题的最优解，返回界面，然后在反馈到用户[10]。如图5.2所示。
24
巢湖学院计算机系2009届毕业设计（论文）
5.5、程序的进一步处理
程序利用java程序设计，需要运行在java虚拟机上，有很大的不便，我利用java提供的jar命令，将程序打包成jar文件，由于程序运用了SWT技术，这时得到的jar文件并不能直接运行。经过一系列的调研，发现可以利用工具exe4j，该工具是利用jar文件生成.exe文件的一个工具，该工具很容易使用，具体过程如图5.3——5.7所示。程序需要动态链接库文件swt-win32-3236.dll，放在相同目录下，最终生成一个可执行文件，不需要java虚拟机环境。
25
巢湖学院计算机系2009届毕业设计（论文） 系统设计的抽象架构参数SWT界面程序参数遗传算法用户运行结果最优解参数种群大小，进化代数交叉概率，变异概率输入文件路径遗传算法调用次数图5.2 系统的总体架构
26
巢湖学院计算机系2009届毕业设计（论文）
图5.3
图5.4
27