Capacitated Facility Location Problem

初始解
这里模拟退火法目的就是为了跳出局部最优解的，所以初始解重要，但又没有那么重要，初始解设计得好的话，模拟退火法可以很快得到收敛，使用的时间相对较短一点；但初始解很差，模拟退火法求得的解也没什么差距，只不过需要的时间需要的长一些。这里我尝试过几种不同的初始化的方法，包括一下几种，但测试后发现，加入贪婪因素后求解的效率表现得很差，反而最后两种初始化的效果不错，而最后一种表现得最好，个人猜测是这个解的形式与理论上最优解类似。

• 用全贪婪获得初始解
• 用部分贪婪获得初始解（百分比）
• 简单的填满前面几个工厂
• 完全随机化选择部分工厂开放，但不让所有的工厂开放

新解的产生
新解的产生设计到我们搜索范围的大小，这里有两个关键因素，一个是重复产生新解的次数，一个是新解产生的方法；有足够多的次数来产生邻居，那么我们找到邻居的最优解的概率就越高，这里设置为200次就可以了；而产生邻居的方式要根据具体问题而定，这个问题我采取随机产生一个顾客和工厂的下标，将该顾客分配给该工厂，有一下情况发生：

• 工厂没有开放的情况并且工厂的容量满足顾客需求，将该顾客分配给该工厂。
• 如果工厂已经开放，并且其剩下的容量足够提供顾客的需求，那么将顾客分配给该工厂。
• 如果工厂容量不足以提供顾客需求，重复生成随机数操作，直到找到一个新解为止。

初温
初温的设置与模拟退火跳出局部有关系，在温度较高的时候，解跳出局部最优的可能性就越大，所以初温应该有一定的高度，让解跳出局部，这里设置的初温是120度。

降温速率
降温速率与邻居的效率有关，降温幅度底，那么找到邻居最优解的邻居解的产生可能性就越大，参考降温速率为0.95-0.99。

终止温度
终止温度与最终找到的最优解有关，温度足够低，那么当前解接受差解的概率就会很低，终止温度底，那么保证最终获得的解是一个不错的解。

初始解
这里的初始解的产生很模拟退火采用的是同一种初始化的方法，效果表现得还不错，具体描述见上。

重复次数
这里重复的次数是保证在足够多的解空间中对结果进行搜索，实验证明，这里我们需要对解空间的大小以及搜索需要的时间进行权衡；解空间大的时候，搜索需要的时间也必然会变得长一些，找出的解也可能会好一些；而解空间小，搜索的花费没有那么大，找出的最优解可能没有那么好，权衡之下，重复20000次是比较好的选择。

新解的产生
新解产生根模拟退火新解产生一致，具体见上。

禁忌表的设计
原理的示意图如下

禁忌表的引入可以有效避免环的产生，避免那些冗余得搜索，根据这样的原理，那么很自然要设计的一个参数就是在几步以内不可以搜索同样得解呢？也就是在几步以内这个解要保存在禁忌表中，当有同样的解在禁忌表发现的时候，我们直接跳过这个解，不去搜索它。当搜索了足够长的步数以后再将这个解从禁忌表中移除，那么这个禁忌表的长度如何设计呢？有下面两种策略：

• 固定长度20
• 根据解空间而变化
  可能是由于数据集的适应度比较好，所以固定长度20的时候，算法的表现已经足够好了。
  当如果根据上述方式来设计的话，会存在一个明显的问题，那就是时间的花费，禁忌搜索本来需要的时间就比较长了，如果中间还要加上搜索禁忌表的花费的话，那么所用的时间复杂度将会变得异常高，对于这样的情况，我们可以采用这样的方法进行优化，
  
  这样只需要O(1)的时间就可以查询到该解是否在禁忌表中，当当前维护的count>表中对应元素的值的时候，表示我们可以重新搜索这个解，否则这个解在禁忌的状态。