二：上图是无向图，其赋权邻接矩阵A如下所示（矩阵的1-53行列分别对应着0-52个标号点）
?0?6??9.2??????????????A????????????19.8?????10.1?????12.960????9.2?0?????0???????0?????8.3??09.7??????9.707.3??????7.3010.1?12.9???????????????????????????????????????????11.4???????11.89.5????????14.5??????????0?????????0??????????0?????????014.2????????14.20??????????0?????????0??????????0?? ???19.8?4.8??4.8?8.3????????????????????????????????????????9.5???????????11.814.5?11.4三：运用floyd算法（计算程序见附录二）求得各编号点之间的最短距离矩阵如
下所示：
???6??9.2??14?34.9??17.5?27.2??34.5?...B???...??54.3?43.7??39?19.8??31.1?10.1??28??12.96015.219.14023.533.2......9.204.88.318......144.8013.134.917.527.234.5......4025.70248.32409.717......184543.7394519.831.110.128344262.915.219.123.533.240.5......60.349.725.837.116.124.14512.9?18.9??22.1??26.9?47.8??30.4?40.1??47.4?...??...??67.2?56.6??51.9?32.7??44?23? ?15.1??0?25.3......45.143.629.819.733.919.337.220.913.122.823.3......49.948.434.624.538.733.727.8......55.859.342.335.449.69.707.3......177.30......32......27.129.311.8......29.8..................032......0......9.5......25.720.9......36.835.321.511.425.627.645.523.737.355.231......44.662.5............14.516.822.833.7............40.525.323.327.860.345.149.955.836.827.129.8......49.743.648.459.335.329.34525.819.724.535.411.4459.517.415.335.932.753.767.217.523.920.741.755.2021.320.841.855.3014.20214429.947.82102334.520.4015.1......17.429.834.642.321.511.814.5......15.317.53116.8......35.923.921.337.133.938.749.625.623.716.119.324.73418.937.242......32.720.720.814.227.637.344.6......53.741.741.829.962.945.555.262.5......67.255.255.347.834.520.422.126.947.830.440.147.4......67.256.651.932.7
5.问题一的求解
5.1 模型一的建立 5.1.1 目标函数的确立
首先以0点表示巡视组的出发点（县城），点1到52表示巡视组需要经过的村镇。对于目标函数应综合考虑两个方面----在巡视距离最短时尽可能使任务均衡。
(一)：三个巡视组所走过的路程最短，
目标函数为：S1?min?lm （5.1.1.1）
m?1N各巡视组所走的巡视路线应尽可能的相同即均衡度：
在保证了总路程最短的情况下很有可能会出现其中的某一条路线过长，使某一巡视组的负载过重，而某一条路线又过短；为了避免这一情况使三个巡视组的巡视路线尽可能的均衡，巡视任务尽可能同样多，规定每个巡视组经过的村镇数必须大于16个，得约束方程如下所示：
?yi(m)?16 （5.1.1.2）
i?152
定义变量；
?1,巡视组m通过弧段（i,j） xij(m)?? （5.1.1.3）
?0,巡视组m未通过弧段（i,j） yi(m)?1,第m个巡视组访问村镇i （5.1.1.4） ???0,第m个巡视组未访问村镇i5252 则第m个巡视组走过的路程为
lm???cijx?m?ij m?1,2,3 （5.1.1.5）
i?0j?0每个巡视组从县城出发，然后回到县城，且所有的村镇严格只有一个巡视组访问一次
?N,i?0 ?yi(m)?? （5.1.1.6） m?1?1,i?1,2,...,52N 任意一条弧的终点城市只有一个起点城市与之对应 ?xij(m)?yj(m) （5.1.1.7）
i?052任意一条弧的起点城市只能有一个终点城市与之相连
?xij(m)?yi(m) （5.1.1.8）
j?0525.1.2综上所述，得到问题一的单目标最优化模型：
S1?min?lm
m?1N
5252?(m)?lm???cijxiji?0j?0???N?y(m)??N,i?0?i???1,i?1,2,...,52?m?1??52? s.t??xij(m)?yj(m)?i?0??52?x(m)?y(m)iji??j?0???52??yi(m)?16??i?1
5.2 模型一的求解（遗传算法的设计） 5.2．1 遗传个体的编码设计
遗传算法将问题空间表示为包括出发点县城共53个地点的位串空间，设A为各个村庄城镇之间的最短距离矩阵，用A矩阵对应的行列数1,2，…,53分别表示各村庄城镇，其中点1表示巡视组出发的县城。因为一共有三个巡视组，故插入两个虚拟点54，55,来表示巡视组的出发地点，设置节点1,53,54之间的距离无穷大，到其它各点的距离与1点一至，故可得到新的最短距离矩阵，对应的行列数分别表示55个节点，这样就保证了不会出现出发点1直接走到虚拟出发点的情况。
5.2.2 初始种群的产生与群体规模的选择
由于本题中没有先验知识故初始群体是采用完全随机的方法产生的。 合适的群体规模对遗传算法的收敛具有重要意义。群体太小则难以求得理想结果，群体太大则计算太过复杂。根据经验，群体规模一般取10-160，本题取群体规模为80。
5.2.3适应度函数的设计
遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。适应度值反映了解的优劣程度，在某种环境条件下，某已知基因型的个体将其基因传递到其后代基因库中的相对能力是衡量个体存活和生殖机会的尺度，适应度越大，存活和生殖机会越高。本题中若某一个个体所对应的解求得的目标函数值越小，其适应度越高应该越容易保留，
对应得目标函数值越大越容易被淘汰故取适应度函数为：
f?aj??1，即目标函数的倒数。 s1aj5.2.4 选择
选择即从当前群体中选择适应值高的个体以生成交配池的过程。第一步计算适应值，运用适应值比例选择进行计算：首先计算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该个体在选择过程中被选中的概率。对于给定的规模为n的群体p={a1,a2,...,an},个体aj?p的适应值
为f(aj)，其选择概率为ps(aj)?f(aj)?f(a)ji?1n(j?1,2,...,n)
第二步运用轮盘赌选择方法来进行选择，将个体适应度按比例转化为选中概率。为了选择交配个体需要进行多轮选择，每一轮产生一个[0,1]均匀随机数，将该随机数做为选择指针来选择备选个体。
选择过程体现了生物进化过程中适者生存，优胜劣汰的思想，并且保证优良基因遗产给下一代个体。
5.2.5部分匹配与交叉变异
在遗传过程中适应度好的基因就更容易遗传到下一代中去，优良的基因会迅速充满种群。对于采用遗传算法来搜索结果，优良的基因若迅速充满种群，则求解结果将迅速收敛为局部最优解，从而不能达到全局搜索的目标；交叉与变异算子的加入是为了保持基因的多样性，有效的防止了优良的基因迅速充满种群，使搜索结果尽可能为全局最优解。 （1）交叉算子
交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作，目的是为了在下一代产生新的个体。本题中使用的是部分匹配交叉算子。交叉的原理如下（选取本题中的9个点进行说明）
如下随机选择两个父个体及其交叉点：
父个体1：（12|3456|789） 父个体2：（53|2749|861）
由此可得到两交叉点之间的基因对应关系如下
3???2,4???7,5???4,6???9
交换两父个体交叉点之间的基因后得到的子个体如下： 子个体一：（xx|2749|xxx） 子个体二: (xx|3456|xxx)
其中x为未确定的基因，由于基因2、8为交叉，子个体中这两个基因就保留,得到子个体的基因如下：
子个体一：（1x|2749|x8x）
子个体二: (xx|3456|8x1)
对于子个体中的第二个基因，2由交叉段的映射关系3???2，故可得该基因
变为3；其它位置的基因由映射关系同理可得
子个体一：（13|2749|486） 子个体二: (43|3456|891)
(二)变异算子
变异操作模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。变异操作主要是保证群体一定程度的多样性，传算法中，变异算子通过按变异概率pm随机反转某位等位基因的二进制字符值来实现。变异原理如下(随机选取9个点做说明) 1,2,3,4,5,6,7,8,9
将第3,8基因之间反转得到如下新个体： 1,2,8,7,6,5,4,3,9
运用遗传算法，经Matlab编程计算（程序见附录二）得各巡视组的安排路线，和所要走的路程如下表所示： 巡视组编号 巡视组的巡视路线 路线长度 路线总长度一 50-25-24-22-47- 23-18-17-16-45-19-46 194.9 -20-48-21-26-49 二 3-6-7-8-41-12-43-14-15-44-13-42-11 215.9 570.1 -10-9-5-40-4-39 三 2-38-35-36-33-32-34-37-53-30-52-31 159.3 -29-28-27-51 巡视路线在图上的表示如下，三种颜色分别代表三个组的巡视路线。
6.问题二的求解
在遗