粒子群优化算法求解 旅行商问题 深圳大学信息工程学院 黄彩玲 2005年6月16日 1SZUTI DSP Lab 粒子群优化算法求解旅行商问题 参照:粒子群优化算法求解旅行商问题 黄岚等 吉林大学学报(理学版) 2003年10月 2SZUTI DSP Lab 五个定义 1 设n个节点的TSP问题的解序列为s=(ai),I=1n.定义交换子 SO(i1,i2)为交换解S中的点ai1和ai2,则S=S+SO(i1,i2)为解S经算 子SO(i1,i2)操作后的新解。这里的的含义是执行交换操作。 2 一个或多个交换子的有序队列就是交换序,记作SS, SS=(SO1,SO2,SON),SO1,SO2等是交换子,之间的顺序是有意义的 。作用于一个TSP问题是意味着所有的交换子依次作用于该解上。 3 不同的交换序作用于同一解上可能产生相同的新解,所有有相同效 果的交换序的集合称为交换序的等价集。 4 若干个交换序可以合并成一个新的交换序,定义为两个交换序的 合并算子。 5 在交换序等价集中,拥有最少交换子的交换序称为该等价集的基本 交换序。 3SZUTI DSP Lab 算式 Vid=Vid+al