聚类与2-OPT

1. kmeansK-means 是一种聚类方法它把一批数据分成K组让同一组里的点尽量靠近彼此。在你的项目里一个城市就是地图上的一个点例如坐标(x, y)。设定K32意思是想把这些城市分成 32 个片区。这里的K是簇的数量不是算法运行次数。每个簇都有一个中心点代表这片区的大致位置。中心通常是簇内所有城市坐标的平均值因此它不一定对应一座真实城市。K-means 全程只在乎一个数叫SSE簇内平方误差。用人话说每个点量一下它到本组中心的距离平方然后全部加起来。K-means 怎么分组可以把它想成在地图上放置 32 个临时服务点**先放中心。**程序先挑出K个初始中心。项目用的是 K-means第一个中心随机选后面的中心更倾向于选离已有中心较远的城市让初始中心分布得开一些。**城市找最近中心。**每座城市比较自己到各中心的距离归到最近的中心所属片区。**片区中心移动。**每个中心移动到自己片区内所有城市坐标的平均位置。**重复分配和移动。**城市可能因为中心移动而改换片区程序继续重复直到中心基本不再移动或达到迭代上限。最后K-means 给每座城市一个簇标签也给出每个簇的中心坐标。Kmeans本身不直接负责优化路线长度仅负责聚类因为 1,577 个城市放在一起直接排访问顺序问题规模很大初始路线也不容易构造。先按地理位置分成片区可以让程序先处理彼此靠近的城市再把各片区路线连接起来更容易得到一条合理的起始路线。2-opt2-opt 会在环上遍历每条边用一个双层循环尝试比较每两条边之间拆了重新组合之后会不会使总长度更短。假设原来有a ─ b c ─ d它会尝试换成a ─ c b ─ d这个变换其实是用反转操作实现的比如原本的边是a-b-e-f-g-c-d这里尝试拆的是a-c和b-d并看重新组合后总长度是否减少其实就是直接将b-e-f-g-c直接反转为了c-g-f-e-b来实现的因为g-f-e和e-f-g长度是一样的而我们只关心总长度有没有减少不关心它的访问顺序是怎样的所以就直接这样操作了。只有新连接更短才接受换法。整个过程1. 先读地图计算城市间距离程序读取fl1577.tsp中每座城市的坐标并计算城市间的整数距离算出一个1577*1577的距离矩阵之后在用到某两点之间的距离时直接查表即可无需再去计算。矩阵是对称的从城市 A 到 B 的距离等于从 B 到 A 的距离。2. K-means 把城市划成片区由于实验结果在不同的随机种子下取得的效果有所差别为了获得更好的实验结果与避免实验偶然性本项目会取5个随机种子2026到2030共做5次优化尝试实验结果取最好的那次。在某一随机种子的条件下接下来开始进行分簇但由于不同的簇数也会对实验结果产生影响这里同样采取多次取最好的做法分别取K16、32、64三种簇数分簇过程会先选K个初始中心然后将每个城市归属到距离其最近的初始中心全部城市归属完毕后对每个中心所有的城市坐标取平均值得到这一簇的中心。由于不同的初始中心也会影响最终实验效果所以同理在选初始中心时也会选择8次并且这8次都会完整运行 K-means但程序会根据最终的簇内平方误差SSE只保留最好的分簇结果。随后程序根据该分簇结果构造并优化路线。所以总的来说项目最终会进行5*3*8120次分簇但只保留15次最好的分簇结果。3. 确定簇的访问顺序与形成小环接下来程序先选择0号簇然后选择距离0号簇最近的那个簇用簇中心坐标算然后依次选距离上一个被选簇最近的簇依次类推就能最终得到簇的访问顺序然后程序按照这个访问顺序依次对每个簇进行处理。先从0号簇的0号城市开始0号簇是访问顺序里的第一个簇然后选距离0号城市最近的城市作为下一个被选择的城市接着再选离这个城市最近的城市依次类推得到这个簇的城市访问顺序如a-c-b-d-e这个方法也叫做最近邻法程序将这个城市视作一个首尾相连的环在使用2-opt算法进行处理时除了ac、cb、bd、de这些边之外还会处理ea边。0号簇的小环形成之后程序会立即对这个小环进行2-opt处理优化这个小环的总路线长度得到一个优化后的小环。这个簇处理完成之后按照簇的访问顺序开始处理下一个簇过程是一样的先按最近邻法排好城市访问顺序形成小环然后进行2-opt处理得到优化后的小环。接下来程序会将两个环进行合并。每次合并时程序会遍历当前大环多个簇小环合并后的环和新簇小环上的所有边组合从当前大环选一条边从新簇小环选一条边对这两条边分别尝试两种接法计算每种接法对总长度的影响选出增加长度最少的一种。单次选边过程例子环 A城市 P ─ 城市 Q环 B城市 R ─ 城市 SP、Q、R、S是四座不同的城市。程序拆掉这两条旧边再比较两种连接方式接法一P ─ RQ ─ S接法二P ─ SQ ─ R它会选增加距离较少的接法。这样原本两个分开的环就变成一个大环。这就像把两个独立的环形街区道路剪开再选最省路的一组接口接成一个更大的环。它只保证当前这两个环的这一步合并选了最省的接法不代表所有片区的整体合并方案都达到了全局最优。5. 对整个大环做完整 2-opt所有片区合成一个完整回路最终大环后程序再做一次完整 2-opt结束后得到一条完整的KMeans2opt路线6. ILS 扰动路线尝试跳出局部最优只做 2-opt 有个问题如果需要先把路线弄长一点才能最后变得更短2-opt 通常不会主动走这一步因为它每次只接受缩短路线的换边。这里补充两种新的opt方式以及双桥扰动候选表 2-opt普通 2-opt 会尝试很多种两边换接法。候选表 2-opt 会优先检查每座城市附近较近的 40 个城市找到能缩短路线的换法就调整。这样通常更快但可能漏掉需要连接较远城市的改进。Or-opt从路线中取出连续的 13 座城市整段搬到路线的另一个位置段内顺序不变如果新路线更短就保留这次搬动。双桥扰动是一种故意改变路线结构的操作目的是让搜索跳出当前卡住的位置。假设把一条闭合路线切成四段A → B → C → D → 回到 A双桥扰动会拆开这些段之间的连接再按另一种顺序接起来。你这个项目里会把段的顺序改成A → D → C → B → 回到 A每一段内部的城市顺序保持不变变化的是各段之间的连接。所有城市仍然都在路线里、没有重复或遗漏但新路线可能暂时更长。因此作为改进本项目加入了迭代局部搜索ILSILS是Iterated Local Search的缩写中文通常叫迭代局部搜索。先用候选表 2-opt 和 Or-opt 把当前路线改善到一个局部最优。把路线切成四段用“双桥扰动”改变四段的连接顺序。扰动可能让路线暂时变长然后程序再运行局部搜索把它拉回一个新的局部最优。如果新路线比历史最好路线短就更新最好结果如果长度相同也允许换成不同路线增加后续搜索的变化。如果连续很多轮没找到更短的路线程序会增加扰动次数让路线结构改变得更明显。它和普通 2-opt 的主要区别是2-opt 是小范围换两条边双桥扰动会重新连接四段路线跳得更远。完成 1,500 次扰动后再用完整 2-opt 收尾。打个比方2-opt 是不断修补眼前明显绕远的路双桥扰动则是把行程中几段调换位置先走出原来的路线结构虽然这可能暂时会使总路线变长再让 2-opt 和 Or-opt 继续打磨。Or-opt 和 2-opt 的区别是2-opt 反转一整段路线Or-opt 则把连续1、2 或 3 座城市作为一个小段整体搬到另一条边后面顺序是不变的。它能调整某几个城市在路线中的位置补充 2-opt 不容易做到的变化。7. 比较不同参数和随机种子的结果主程序不只跑一个设置而是比较簇数k 16、32、64。随机种子2026到2030共 5 个。NN2opt基准5 次。KMeans2opt3 种簇数 × 5 个种子共 15 次。KMeansILS同样是 15 次。所以完整实验一共记录35 条运行结果。对每一条路线程序都会检查城市是否恰好访问一次并把路线长度、时间、参数和搜索历史保存下来去最好的一次为实验结果。