README.md

2E-VRP大作业优化记录

##2015.12.26 ###已实现

1. 尽量减少路径数量，不仅仅是卫星内的路径，也考虑一下卫星间的路径，如果卫星 1有一条路径只有1个点，而卫星2也有同样情况，那么把这两点合并可能会有更优结果。目前在卫星间操作添加一个检测sat1单点路径的方法。
2. 考虑容忍n次不更新的算法。容忍后仍不更新的惩罚为1.5，更新的奖励1。
3. Onlooker选择食物源的方法：考虑到Fit和不更新次数，提出公式：score=(max(fit)-fit(i)+alpha)*(1-notIm(i)/notImLimit);然后将其归一化。
4. 在卫星内搜索操作的插入法中，添加尝试插入但超载时的搜索跟卫星重合点进行剔除以腾出足够空间容纳要插入的客户。
5. 卫星内搜索操作增加寻找单点路径归并操作，但这操作在后期才使用。

###待实现 ####更多想法/优化

1. 多次不优化将被淘汰的食物源可使用与当前全局最优解交叉的方法。思路：增加卫星间搜索的方法，继承了当前食物源和全局最优解的部分结构，成为新的食物源。
2. 对于多节点，例如set2中的最后两个数据集，节点较多，观察别人的较优结果，发现他们的卫星客户重合点都是独立起来的，所以可以确定一个指导，尽量把重合点独立。
3. 分解一个小路径给若干个大路径。

####实验1 设置ABC的参数RunTime为多次，每一次运行的初始化解为上一次的最优解。思想为：在前最优解的附近再搜索，增加搜索局部最优能力。缺点：陷入局部，完全放弃了上轮的多样性。 ####实验2 设置ABC的参数RunTime为多次，每一次运行的初始化解为上一次的若干个较优解。思想为：在前多个较优解的附近再搜索，比实验1具有更广的搜索能力。缺点：仍具有局部性。 ####实验3 设置ABC的参数RunTime为3次：第一次，常规运行；第二次，常规运行；第三次，去前两次相等的若干个较优解作为初始解。

##2015.12.27 ###问题 对于昨天使用1000只Bee、100次迭代跑的set2、set3的情况，发现以下问题：

1. set后面的数据集都跑不好，这些数据集的特点是卫星偏离客户（在客户群的边上），客户相对较多，可能的原因是：卫星内的搜索量不够就达到了Limit上限，今天测试一下那几个数据集使用较大的Limit，后面会加上结果（在总体迭代次数相同的情况下，较大Limit不好的地方在于减少了卫星间搜索的次数）
2. Bee数量增加的效果比没有想象中明显，只是对某些次优结果更稳定，并不保证能跑到最优，说明瓶颈并不在于计算量。分析原因：多样性不足（20%）、卫星内搜索能力不足（80%）。
3. 下午发现当一个路径谁也插不进谁的时候，要考虑交换方法。但是后来又好了，可能有容忍机制，但是只能走k步。

###解决方案

1. 增加二层优化的幅度，同时增大Limit。例如，插入法选择的客户可多个（目前是一个）、2-opt方法长度范围增加。控制变量实验。
2. 增加较优源的衍生源。使用交叉的方法，把将要丢弃的食物源跟较优源进行交叉操作，这样得到的食物源具有部分较优源的特征，对它进行搜索，相当于增加较优源的领域的搜索计算资源，但这样并不是改善二层搜索能力，而是增加较优源附近的源数量。

今天先看看这些问题，做做实验。其他先不写。

##2015.12.28 ###总结昨天 对于昨天写的其实没啥进展，今天更多的是对比好的结果和我自己跑的结果的差距。但是还是先说一下昨天问题的进展：（对应问题标号）

1. 今天对11_19数据集进行对比观察，这个数据集的特点也挺普通，就是客户还是围绕着中心，没有出现问题所说的卫星偏置，但还是跑不出好结果。于是我就拿了睿博跑的较好的结果进行对比观察，方法是首先看他有没有这种卫星-客户分配，然后再观察这些分配在迭代过程中的表现。经过几乎一天的观察发现，目标结果的分配用我的算法很难达到，1000只蜜蜂初始化大概可能有1只达到，甚至没有，2000只就有两个左右。对比了我的根据距离最近原则进行分配的方法与目标分配的差异，发现有三个点，分别是12，33，37。其中33，37到两个卫星的距离都很相似，相差在4以内，而12则相差12，离卫星2较近。这种我认为还是较容易搜素到的，但实际上较困难。
2. 像上面所说，尽然曾经出现了好结果的分配情况，但是还是跑不到好结果，所以基本上可以把问题定位在卫星内的搜索。
3. 这个问题方法在evernote中写了，晚点更新。

##2015.12.29 ###计划 今天计划实现优化卫星内的交换搜索优化。 ###进展 目前已经实现卫星内的交换法，基本上可以解决谁也插不进谁的问题，也跑到了睿博那个结果，弥补了这个漏洞，但是在方法使用顺序或者说阶段性选择方面还要思考一下。例如，2-opt方法往往不需要容忍机制，这个方法基本是用来解决『打结』问题，但是插入法和交换法就需要容忍机制。目前考虑一下使用先使用插入法和交换法采用容忍机制先搜索k次，然后使用多次的不容忍2-opt进行局部优化。明天做一下实验。先提交一下代码。

##2015.12.30 ###计划 实验一下两层ABC的方法。---太慢！！！放弃 优化现有的ABC。

1. 增加初始化时的零容忍优化次数，减少迭代阶段的容忍优化的消耗。

###新想法 添加卫星内路径合并尝试。（因为我又去对比结果发现有这种情况） 具体： L=两个路径负载和-限载量。 若L<0,则返回该结果； 若L>0：如果存在客户需求大于L，组成列表，则逐个尝试取最优返回。 如果不存在客户需求大于L，则返回原结果。

针对固定路径内调优的方法：2-opt可能顾及不到相距较远的结点，所以要使用新的方法。目前想到的方法有：遍历法：选择一个结点，逐个位置插入取最优。

###进展

1. 修改了卫星内搜索方法中的释放路径法，增加了merge路径功能，超载则选择一个卫星出来。
2. 增加一个路径内优化方法。选择一个点，尝试插到所有位置取最优。

###效果 卫星内优化有改善，最优分布下跑到最优的概率增大。

##2015.12.31 ###问题发现

1. 发现某些数据集只用到一个卫星，但是我的算法很难跑到一个卫星的情况，要修改。
2. 容忍机制跟模拟退火很像，模拟退火的方法更好。我的算法只是容忍一个固定的值，而模拟退化可以根据当前的温度来接受或者拒绝搜索得到的解。在我的算法中温度可体现在不更新次数。

###进度

1. 修改了卫星内交换插不进空卫星的bug。
2. 在初始化时就引入空卫星源，这样可以增加源的多样性。
3. 修改卫星内优化的方法调用策略，5种方法等机会调用。而对于非路径内部调优方法，在执行后需执行路径调优。

###新想法

1. 增加初始化解的多样性。可尝试一个空卫星设置多个空卫星。

##2016.1.1 ###进度

1. 增加空卫星效果有所提升。
2. 4卫星特别慢

##2016.1.2 ###新想法 引入遗传的想法，把食物源的历史最优解进行交叉。 具体：首先把每个食物源分成单独一户，经过一些迭代后(后天环境变异，还是使用卫星间的插入法)，到达相对较优的解，然后记录每一户的基因排列。到达触发交叉变异的条件后，就开始选择两个源交叉。如何选择？差优搭配？先把Fitness排序，相同的合并，然后前后搭配变异形成新的源。 交叉方法：先取各个卫星对应的交集，然后把剩下的再分配。计算卫星对剩下每个卫星的吸引力(在所有源中属于该卫星的概率)，根据适应度形成概率确定分配给的卫星。（不一定实现）

##2016.1.4 ###问题

1. 如果将每一个卫星更新的情况都作用于源的不更新次数，则会产生卫星之间的拖累现象，即一个卫星已经优化到最优，但另一卫星还需要许多优化，但前一个卫星在每次操作都不更新，使源的不更新此时不断上升，从而缩减了后一个卫星优化的机会。

###方案：

1. 对每个卫星维护一个limit标志，达到限制即停止优化。

###修改

1. onlooker不再对食物源的不更新次数进行影响。出于这样的想法：优秀的解应得到更多的优化机会。之前的方法在onlooker也影响了食物源的不更新次数，这样并不能使优秀食物源得到更多优化机会，只会加快优秀食物源更换的速度，即使差的和优的食物源得到同等对待。所以需要修改。修改后相当于不更新的迭代数。