前言

Kino的课题常需要用到元启发式算法，就在此稍稍总结。
元启发式(metaheuristic)，很多时候也被称为智能优化(intelligent optimization)、现代启发式(Modern Heuristic)、智能计算(Intelligent Computation)、自然计算(Natural Computation)等，细分到具体算法有遗传算法、粒子群算法、差分进化算法、蚁群算法等。
**元启发式(metaheuristic)*这个词本身可以拆成两部分来看，元(meta)和启发式(heuristic)*，本文主要从这两方面来阐述元启发式的概念，后续文章再介绍各算法的原理、步骤、代码等。

1. Meta

首先来解释元(meta)，程序员对这个词并不陌生，学习编程语言到某个阶段总会出来一个元编程(metaprogramming)技术，还会经常见到元数据(metadata)等。与顾名思义的一些概念相比，元的概念就有点晦涩了，初次遇见总是一脸诧异，难以理解。
感性上来看，metaXXX就是相比XXX来说更高级的一种概念/理论，是研究超越XXX的存在，玄之又玄，不能理解不是你的错，就像形而上学(metaphysics)一样难以理解。
而不去探讨meta哲学性质的意义，只考虑其作为前缀(prefix)的情况，根据meta在Wikipedia的相应词条Meta[1]，meta大多数时候可以理解为X about X，大致翻译为关于X的X，这里的关于在中文语境里通常用实现、描述、编写等动词代替。例如metadata就是data about data，即描述数据的数据，metaprogramming就是programming about programming，即编写程序的程序，诸如此类。如果有需要，这种概念还可以递归，即添加任意多的meta前缀，变身成为metametameta…。
在此基础上再去看meta的中文翻译元，就会发现这个翻译其实很巧妙。“元”汉语里有 起源/开始(如元旦/元始天尊)、基本/根本(如元素/元气/元件) 的意思，完美地涵盖了meta想要表达的意思。然而元这个字很少单用，已经融合在最常见的一些词语中，所以当看到用元的前缀生造出的词语时，大多数人还是会难以理解。

这样说完感觉可能还是一片迷茫，就拿上面所说的metadata和metaprogramming作为示例来具体说明。

1.1 Metadata

关于Metadata，循序渐进地来举几个栗子。

  • 填写各类登记表时，通常需要填写姓名、性别、爱好等信息，那么我们填写的信息Kino、女、睡觉就是具体需要的data，而姓名、性别、爱好这种描述属性的文字，就属于metadata
  • 对上面的内容稍加扩展，可以认为在进行关系型数据库设计时，我们建立的表结构就可以看作是metadata，而最终记录到表中的内容就是data，而对于K-V数据库来说，也不妨理解为Key是metadata，Value是data，JSON数据自然也可如此理解。
  • XML数据格式，XML(Extensible Markup Language)作为一种标记语言(Markup Language)，本就是Metadata一种表现形式。可以把XML的tag和property的key作为metadata，而把content和property的value作为data。HTML作为XML的亲戚，也可以如此理解，而至于HTML中的meta标签，又是将整个HTML文件看作data，这个meta标签里的内容就是用来描述这整个HTML的data也就是metadata了，比如<meta name="google-site-verification" content="......" />

1.2 Metaprogramming

按照上面的逻辑继续下去，变量声明就是描述变量的类型，难道就是metaprogramming了吗? 显然不会是这么简单的事情。
metaprogramming本身还是一个比较宏观的定义，对应到不同编程语言的具体实现上，又各有不同。下面简单叙述几种语言的metaprogramming机制，只要实际使用过其中一种，就不难理解了。

  • C++：在C++中，可以利用模板实现元编程，在Effective C++中就有关于模板元编程的讨论
  • Java：在Java中，最为人熟知的反射，就可以用来实现元编程
  • Python：在Python中，如果一个类继承的不是object而是type，那么它就被成为**元类(metaclass)**，可以用元类来验证、注册子类，这也可以称为元编程

从上面的例子中总结一下，元编程的实现手段各异，但大多是想解决这几个问题：

  • 设计中出现的相似内容太多，而这些重复内容存在于类层面，已经不能通过类的抽象来解决了，或者解决起来更为复杂(比如引入过于复杂的设计模式等)，这个时候需要更高一层的抽象来处理问题，解决这个问题的过程就可以称为元编程，Python中的metaclass就是典型的应用
  • 面向对象程序的设计中，类的定义是在编译期就确定的，运行时动态生成的是实例，如果想要更高一层，在运行时动态生成类，那么这个实现过程就可以称为元编程，Java中的反射是典型的应用
  • …

这也提醒了我们，在使用元编程前需要思考这个问题是否必须使用元编程、使用元编程能否简化实现过程，如果可以再尝试使用，否则就需要谨慎对待。
元编程更大程度上是一个概念和思想，而不是一个具体方法和手段

1.3 Off topic

思维一发散，意识就止不住到处游走，虽然离题万里，但且记录在此吧。

突然想到导师最喜欢提的问题：“你这个效能评估的参数选取标准是什么呢？你怎么证明你这个效能评估的结果是可信的呢？毁伤评估的结果是怎么得来的呢？”似也有点元的意味，而且还可以无限递归，最终变成“评估评估…评估的结果”。如果该项工作有客观的评估标准，评估起来就相对简单可信，如果没有客观标准，靠专家标准或者自己选取的参数标准评估，可信性就大打折扣了，这个时候就可以再追问一句：“你怎么评价你选取的参数是可靠的呢？”。
今天刚好看到新闻，国际单位制的七个基本单位重新进行了定义，都改以宇宙的基本常数为基础定义[2]，于是突然想到，所谓度量系统Metric System里的单词metric，在词源上是不是和meta同源的，毕竟metric是用来衡量一切的标准，有种meta的意味在里面，不过事实到底如何，毫无词源学基础的Kino是无法确定了。
似乎更能理解那句不是爱因斯坦的名言“越简单越好，但不要过于简单”，过犹不及，繁简之间如何取舍是个永恒的问题，奥卡姆剃刀并不是万能的，更何况繁简也是相互转化的，就像有时想为了简洁不停地添加meta，最终却导致设计模式的臃肿，反而更复杂了。所谓大道至简，是对还是错，还未可知。但是爱因斯坦真的说过这句：“不应否认任何理论的终极目标都是尽可能让不可削减的基本元素变得更加简单且更少，但也不能放弃对任何一个单一经验数据的充分阐释。”这似乎是个比较恰当的说法。

2. Heuristic

维基百科也有启发式(Heuristic)的词条[3]，但实际的定义很简单。
启发式算法(Heuristic)算法和精确(Exact)算法相对应，它们的求解对象都是运筹优化类问题。区别在于，对于组合优化等非凸优化问题，用精确算法虽可求出其全局最优解，但计算效率低，有时还是NP问题，规模变大则无法在有限时间内求解，而利用启发式算法，可以提高计算效率，但求得的解可能只是较好的次优解，而不能达到全局最优解。
针对一个具体的优化问题，提出一个在计算效率和求解质量间取得均衡的具体算法，这个算法就叫做启发式算法。
例如需要求解\(y=f(x)\)的最小值，用精确求解可以得到准确值为\(\min{y}=22\)，耗时\(t=10s\)，而使用启发式算法求得的结果是\(\min{y}=22.22\)，但耗时只有\(t=3s\)。
对于精确求解法，具体包括穷举法、分支定界法、割平面法、动态规划法等，而对于传统的启发式算法，包括构造型方法、局部搜索算法、松弛方法、解空间缩减法等。

3. Metaheuristic

综合以上概念，将meta和heuristic结合得到的所谓元启发(metaheuristic)，理论定义上应该是heuristic about heuristic，但是这种实现启发式的启发式，还是很难直观理解。
先回到刚刚说的启发式算法，严格意义上的启发式，是针对某个特定优化问题的，只要是能够取得较好值的算法都可以叫做启发式算法，而元启发，就是给定一套流程/方法论，对不同的问题，只要按照该流程设计，就能实现一个针对具体问题的启发式算法，因此把这个抽象的流程称之为元启发。换句话说，启发式是面向问题的(Problem Oriented)，而元启发是面向方法的(Method Oriented)。最常见的比如遗传算法，它只给定了一个标准流程：编码->初始化->选择->交叉->变异->…，而针对一个具体的优化问题，需要设计特定的编码方式、选择特定的适应度函数…，如此设计完成的具体算法才是启发式算法。
但是、然而、不过，现在的论文中，大多数时候把元启发和启发式也混着用，在整篇文章中，通常只使用元启发式或启发式其中一个词，所以界限并没有那么分明了，元启发经常被称为启发式、启发式也经常被叫做元启发。
元启发也有维基百科页面，戳这里

后记

传统的任务分配、组合优化类等运筹学问题，大多都可以抽象成非凸优化的模型，也是NP问题，无法用传统方法求解，同时这些问题大多缺少或不能统计历史数据，因此也无法使用有监督机器学习等算法，这种情况下使用智能优化算法就非常合适。
针对这些运筹学问题，只要能够利用元启发算法的思想设计出合理的启发式算法，从而解决问题，其实就是一个很好的工作，但是现在的研究导向是发论文至上，研究智能优化算法的实验室也不例外，一切以发论文为导向，设计全新的元启发式算法实在困难，于是现在的论文大多还是Problem Oriented，通过说动听的故事阐述问题意义，再找出和之前的问题区别，比如多了一个小小的约束条件，这时就可以命名这个问题为XXXXX，以此说明自己定义了一个新问题，再抽象出该问题的数学模型(大多数时候只是在目标函数或约束条件上做些许修改，太简单没有做的意义，太复杂元启发也难以求解)，然后根据元启发算法的流程设计出完整的算法(在流程中的任一处加一点修改即可称之为改进)，编程实现算法做比较，得出结论;当然Method Oriented也还是有的，刚刚提到的一些小的改动、针对经典的TSP等做算法改进、超多目标优化问题的求解方法等。
总之一切为了论文，至于这些论文里的问题是否真的有意义、方法是否真的有创新，谁在乎呢。

Footnote

  1. 1.Wikipedians. (2018, November 12). Meta. Retrieved from https://en.wikipedia.org/wiki/Meta↩
  2. 2.Wikipedians. (2018, November 19). 2019 redefinition of SI base units. Retrieved from https://en.wikipedia.org/wiki/2019_redefinition_of_SI_base_units↩
  3. 3.Wikipedians. (2014, May 25). Heuristic (computer science). Retrieved from https://en.wikipedia.org/wiki/Heuristic_(computer_science)↩
  4. 4.Wikipedians. (2018, November 16). Metaheuristic. Retrieved from https://en.wikipedia.org/wiki/Metaheuristic↩