1. TSP算法在实际中有什么意义
不要问解决数学问题有什么用，总会有用的，数学是自然科学的基础。
TSP问题的概述
旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中着名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题。
TSP问题的由来
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。
TSP在中国的研究
同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。
2. 优化算法笔记（二十七）蜉蝣算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
蜉蝣算法（mayfly optimization algorithm）是根据蜉蝣的飞行和繁衍行为提出的优化算法。该算法提出与2020年（论文接收在2019年），算是一个新算法。算法的流程和结构其实与蜉蝣的关系不大，可以看作是对粒子群的一个修改。
蜉蝣算法中群体分为雄性和雌性，雄性的行为与粒子群相似，通过全局最优和自身历史最优移动，而雌性则是向优于自己的配偶移动，若配偶弱于自己则自行局部搜索。然后这对雌性和雄磨搭孝性会产生两个后代，并保留群体中的较优个体。
算法的流程结构都有些许复杂，不过有粒子群基础的小伙伴应该能很好的理解。
这次我们的主角就是蜉蝣了（虽然关系不太大）。
蜉蝣算法中有两种角色，雄性蜉蝣和雌性蜉蝣，其数量均为N/2,N为群体总数, 其位置为 ,速度 为了方便描述，下面使用XM表示雄性蜉蝣的位置，XF表示雌性蜉蝣的位置。
整个算法的每次迭代流程大致可以分为四步：
1. 将蜉蝣群体均分为雄性组和雌性组，每组内按优劣顺序排列。
2. 雄性个瞎稿体移动
3. 雌性个体移动
4. 雄性雌性交配产生两个后代
5. 在这2N个个体中选出N个作为下一代
可以看出每次迭代算法产生了2N个新个体，所以说蜉蝣算法的计算速度会比其他算法更慢，因为蜉蝣算法多计算了N个个体的适应度值。（其他大多数算法每次迭代只计算N个值）。
由于1.分组和5.选择比较简单，不需要再详细描述，下面只介绍2,3,4这三个步骤。
雄性蜉蝣的移动方式与粒子群中的粒子相似枝携，新位置当前位置和速度决定：
其中 表示第n代群体中的第i个个体的第j维的位置。
其速度则有以下公式决定：
其中如果该个体使群体中的最优个体则使用公式（3）进行移动，其他个体则使用公式（2）进行移动。 表示第n代群体中的第i个个体的第j维的速度，pbest为该个体所到过的最好位置，gbest为全局最好位置，a1,a2,beta为常数，一般取值为2，rp为当前位置与pbest的欧式距离，rg为当前位置与gbest的欧式距离，e为自然常数，d为常数，一般取值为0.1，r为[-1,1]内的随机数。
公式2是不是和粒子群的速度更新公式很像？下面是粒子群的速度更新公式
与粒子群相比雄性蜉蝣的速度更新公式将两个随机数r1与r2替换成了与距离相关的值，个人认为这不是一个好的修改，不过后面可以看出，该改动为算法提供了强大的局部搜索能力。
下面做一个试验：现在将蜉蝣算法中所有个体全部划分为雄性，即没有雌性的搜索行为和交配产生后代的行为。也可以认为是在粒子群算法中将公式（3）替换为公式（2），我们看看效果。（唯一不同的是蜉蝣算法中雄性中的全局最优个体使用公式（3）进行移动）。
可以看出，只有最优个体在缓慢的移动，并且在略过最优解附近后仍在移动。问题出在哪呢？
有两个原因：
1 .如下公式的值
我们上述的实验中取值范围（-100,100），初始化时两个个体之间的欧式距离r的取值范围在10以下的都比较少，此时自身的历史最优就是自己本身，也不会产生速度。
当r=10时，其分母为e^200,其值约等于0，此时公式（2）如下
即速度不会发生任何变化。
下面，我们把解空间缩小100倍看看效果。
可以看出仅仅是修改了取值范围，雄性蜉蝣们的行为就发生了巨大的改变。因为距离参数会受到解空间范围的影响，当距离足够小时，公式（2）中的距离参数所算出的速度不在是0，所以雄性蜉蝣们便活跃了起来。
当然这是一个不好的现象，算子不应该受解空间范围改变有如此大的影响。
2 .初始速度
每个蜉蝣都有初始速度呀，就像粒子群一样，所以一开始应该也会移动。
蜉蝣确实有初始速度，不过速度的每一维都是0。为什么呢？不能是一个不是0的值吗？可以但又不完全可以，因为蜉蝣算法没有给出速度的上下限范围，没有范围就无法初始化到该范围内的值。作者将速度的上下限作为了一个改进点放到了文章的后部！
结合上述1,2两点，雄性个体中除最优个体外，其他个体的速度几乎都是0，可以说是以肉眼不可见的方式在缓慢移动。或者也可以理解为该步骤的主要作用是局部搜索，当个体之间距离较远时则不会移动，将雄性单独拿出来实验是没有意义的。如果必须单独拿出来用则需要设置速度上下限，并在初始化中为个体设置随机速度。
其实论文中的速度上下限，以及惯性系数递减等粒子群中已有的步骤，完全可以直接沿用到原始的蜉蝣算法中，而不应作为改进单独拎出来说明。此处也可以直接沿用粒子群算的速度更新公式。
每只雌性个体会有自己对应的雄性个体作为配偶，雌雄两组顺序配对，即最优的雌性配对最优的雄性，次优的雌性配对次优的雄性。
雌性的移动方式为向由于自己的配偶移动，若配偶弱于自己则自行搜索。
其位置的计算公式与雄性相同均为公式（1），速度的更新公式如下：
其中xm为该雌性个体配对的雄性个体的位置，xf为该雌性个体的位置，rmf为这两只蜉蝣之间的位置，fl为常量一般取值为0.1，r为[-1,1]内的随机数。
当该雌性个体差于雄性个体时，使用公式(7)中的上式，当雌性个体优于该雄性个体时，使用公式(7)中的下式。
与雄性的速度更新公式相似的问题，因为距离参数rmf的值可能非常大，会导致公式(7)中的上式做小范围的局部搜索，速度更新幅度较小。可以试着用随机数去代替距离参数：
其中r2为[0,1]内的随机数。
交配行为中一对雌性和雄性会产生两个后代，其产生公式如下：
其中L为随机数，取值范围应该是(0,1),xm为雄性蜉蝣，xf为雌性蜉蝣，可以看出产生的两个个体关于这对雌性的中心对称。该步骤为蜉蝣算法提供了全局搜索能力，并结合选择操作加快了算法的收敛速度。
整个蜉蝣算法的流程如下：
其流程看上去还是挺简单的，不过由于分了雌性和雄性两种，导致所需操作的步骤细节很多，同时由于父辈母辈更新自身位置后还产生了后代，其实每次迭代计算了2N个个体的适应度值，导致其速度慢。
适应度函数 。
实验一 ： 原算法
从图像可以看出，蜉蝣算法的收敛速度非常的快，在解附近聚集后群体仍然能够移动并向着正解运动，并最终收敛在正解附近。和之前的全是雄性蜉蝣的实验大相径庭，应该是因为交配产生的后代优于了父辈母辈，父辈母辈被替代了，所以看上去移动了。当距离变小后，雌性雄性蜉蝣的速度更新公式则开始生效了。
不过，结果并不太好，但是在预期内，可以看出，其精度是非常高的，但是算法不太稳定，会出现非常差的结果。
因为距离较远时全靠着交配产生的后代更新位置，此时会快速收敛到当前的最优个体附近。当距离变小后，雌性和雄性的速度更新公式开始生效，此时的群体较为集中，其运动轨迹就像贪吃蛇一样。
综上，可以看出算法的前期收敛很快，算法的局部搜索精度很高，同时全局搜索能力较弱，依靠局部搜索花上跟多时间也能找到最优解。由于全局搜索能力不强，且收敛过快，算法应该比较容易陷入局部最优。
实验二 ： 去除距离操作，还原成类似粒子群的速度更新方式，使用公式（4）（8）
实验二的图像中蜉蝣的收敛速度比实验一中慢了一点，而且也没有那么集中，最终也聚集在了正解附近，这个图像其实和粒子群也有了几分相似。不过由于选择操作的作用，蜉蝣算法的总是会收敛的更快，即使设置了速度上限依然如此，因为即使该个体迭代数次可以飞到最优解，但后代可是可以直接降生与最优解附近的，如此一来该个体会被取代，剩下的个体则集中在了最优解附近。
从结果上看，实验二损失了不上精度有点不能接受，但是也稳定了不少，局部搜索能力也有所削弱。蜉蝣算法的收敛行为主要由交配繁衍后代和选择下一代来提供，如果要调整其搜索速度需要修改交配操作。原论文中也写出了相关的改进，如，父代母代产生一雌一雄两个子代，子代雄性优于父代则保留，子代雌性优于母代则保留。此处不再赘述，可以阅读原文。
蜉蝣算法受雌雄蜉蝣的运动和交配产生后代的行为启发而提出的优化算法，个人感觉该算法与蜉蝣关系不大，而是更像是对粒子群的一种改进。算法的流程较为复杂，不过有粒子群作为基础也很好理解。算法的性能比我想象的要好，其中雌性和雄性的移动为算法提供了局部搜索能力，而交配繁衍后代进行选择提供了全局搜索能力。算法的局部搜索能力很强但是稳定性较差，容易陷入局部最优。由于每次迭代产生了更多的新个体数，为了保证公平，它的迭代次数应为其他算法的1/2。
其实原文中还有许多的优化和改进步骤，这里也不一一实验了，还是推荐去看看原论文。
看到蜉蝣算法，想起了之前一个写着玩的算法，也是将种群分为了雌雄两类。不过没有蜉蝣算法这么复杂的操作，只是通过雌雄交配产生后代进行更新迭代，通过母辈生育有几率死亡以及近亲繁殖的后代有几率死亡来控制跳出局部最优，效果中规中矩，不提了。
参考文献
Zervoudakis, K., Tsafarakis, S., A mayfly optimization algorithm, Computers &
Instrial Engineering (2020) 提取码：ogl4
以下指标纯属个人yy,仅供参考
目录
上一篇 优化算法笔记（二十六）和声搜索算法
下一篇 优化算法笔记（二十八）蝗虫算法