metaheuristic 元
启发式方法。一些随机
搜索算法诸如进化算法、蚁群算法、粒子群算法这类具有启发式框架的智能算法称为
元启发式算法。
这种算法称为现代
启发式算法(metaheuristic)。Metaheuristic一词由Glover首次使用,其来源于两个希腊词语:Heuristic来源于动词“heuriskein”,其意思为去发现(“to find; find out; gain, procure”),而前缀meta意思为“higher, beyond”,即在更高的层次上超越。在metaheuristic被广泛使用之前,人们经常用 modernheuristic一词。
Osman和LaPorte给出的定义为:“现代
启发式算法可以正式定义为一个
迭代产生过程,该过程智能地组合不同的概念引导下属启发式算法(subordinateheuristic)探索(exploration)和开发(exploitation)搜索空间,为了有效地发现近似最优解,算法利用学习策略来组织搜索信息。”
Stutzle指出:“现代
启发式算法典型的是一种高级策略,该策略引导基本的问题特定的启发式算法来增强其性能。…许多现代
启发式算法的搜索过程是一种概率决策过程,但是这种搜索与纯随机搜索(purerandomsearch)的主要区别在于它不是盲目的随机搜索,而是以一种智能的形式进行随机搜索。”
Metaheuristic Network网站对于现代
启发式算法给出的定义为:“Metaheuristic是一个用来定义启发式算法的概念集,这些启发式算法可以用来求解不同的优化问题。换句话说Metaheuristic可以被看成是一种算法框架,这种算法框架通过微小的改动可以运用到不同的优化问题。”
由上述各种不同的定义,可以看出Metaheuristic是一组利用不同
启发式算法探索搜索空间的高级策略。其一个重要的思想就是多样化搜索(diversification)和集中搜索(intensification)之间的动态平衡机制。多样化搜索是指探索搜索空间,而集中搜索则是指利用搜索过程累积的经验知识在特定的区域进行深度发掘。这种搜索策略一方面快速地探索搜索空间中包含高质量解的区域,另一方面又不浪费太多的时间在一些以前探索过的或者不能发现高质量解的区域探索。