元启发式算法手记四 Mimetic
元启发式（Metaheuristics）算法是当前大数据领域最前沿的解决实际最困难问题的一系列算法框架，针对NP-Hard组合优化问题，用元启发式搜索往往可以得到相当不错的结果。本系列内容将持续更新所有具有代表性的元启发式算法，一方面是个人学习笔记，另一方面是为了填补中文圈准确资料稀少的问题。因为学习源头为英文，部分名词的翻译并不精准，仅以个人喜好进行名词翻译，如果有别的地方不同的翻译方法，请以英文为准。
本文为系列四，主要介绍Mimetic，我也不知道中文叫啥搜索程序。本文将使用Mimetic进行一次模拟计算，场景是一家大型全球公司在疫情恢复后，要根据人口情况进行工厂选址，这类问题叫做Facility Location Problems (FLP) ，是经典的NP-Hard问题。
本文是经典的销售问题 – 门店选址的解法示范。并附代码。
大概意思
Mimetic其实算是一系列算法的集合，做为一种智能算法解决框架。
本文所描述的步骤是，首先根据开放数据拿到全球人口数量最多的100个城市及其行政规划地理信息。然后再配合aws的开放卫星数据，以卫星数据确定相应城市近年的灯光变化情况来确定他们的发展情况。发展得好的城市，当然就是要建厂的地方了。而另一方面，建厂是有成本的，建得太多呢，成本就高，建得少呢，覆盖的人口数量就小了。所以要在其中找到一个多因素下的最优解。
大概就是这么个意思。
Mimetic要点
Mimetic是一个大框架，所以里面的参数非常多。他主要的提升在于，本地搜索一回进行一次解法的寻找，而Mimetic是一回进行一批解法的寻找（population-based），类似遗传算法的搞法。
里面有两个重要的操作：重组（Recombination）和杂交（Hybridization）。重组是靠多组解法整新的解集。而杂交是试图往里面放进去领域知识。
population是一群解空间的集合，姑且起个名字叫解群吧。解群都很相近，我们就说这算法停滞了。所以要有所谓的解群多样性。
Mimetic的模板
其实很简单，只需要follow下面的步骤。
step1.初始化一个解群
step2.重复以下步骤
step3.通过这个解群，用上面提到的办法重组出来更多的解群。
step4.检查有没有提升
step5.重启新的解群
是不是很简单？
Mimetic到门店选址问题上
在选址的问题上，有两个目标，1.覆盖人数越多越好，2.成本越低越好。
这就出来一个概念叫做 pareto front（瞎翻为帕雷多前线），也就是在前线上的解都是无可挑剔的（人数相等时成本最低的，和 成本相等时人数最多的）。
所以在选择最优解的时候就变成了组成pareto front了。算法最终就可以得到一组解。
算法步骤：
1.靠随机+局部搜索生成初始的答案，这时候不一定行。
2.进入迭代
3.依靠固定步骤 选择->重组->变异->本地搜索（相似于遗传算法） 生成新的解群
4.两个解群进行对比选择进入pareto front
5.检查有没有停滞，有停滞要加入随机生成解
6.直到迭代结束
看代码