=-赵新超-=分享 http://blog.sciencenet.cn/u/zhaoxc 平静的生活,零散的记忆

博文

群智能优化算法与人生

已有 15288 次阅读 2014-3-3 03:15 |个人分类:科学研究|系统分类:科研笔记| 进化计算, 群智能, 搜索算法, 算法人生

注:

1】本人所熟悉的智能计算的算法分支很有限,本文所做的划分肯定存在很大的主观意识,因此如何划分肯定是仁者见仁、智者见智的问题;

2】由于问题的复杂性,在可忍受时间范围内,群智能优化算法不保证找到问题的最优解,只能保证找到问题的较优解或可接受解,其实关于搜索的NP难问题,我国诗人贾岛早就给过我们提示,“云深不知处,只在此山中”,只是搜索算法的设计人士没注意到而已。

Why to write】近些年智能计算相关领域发展迅速,引起数学、计算机、控制工程、管理和金融工程、工业工程等广大领域学者和工程技术人员的广泛关注,近几天有博士问到这个问题,即智能计算领域称谓和名词的内涵和外延的关联,因此就大致对这些智能计算的分支做个粗略梳理,但由于知识面所限,这些梳理肯定会有不妥、甚至错误之处,因此仅供参考。

【写作思路】从宏观到微观。

【搜索算法】分为4个层次:蒙特卡洛方法(Monte Carlo method);启发式方法(Heuristics);元启发式方法(meta-Heuristics);超启发式算法(hype-Heuristics)

1】粗略的说,蒙特卡洛方法指使用随机数(更常见的伪随机数)解决很多计算问题的方法,最典型、最常用的是产生01之间服从均匀分布的随机;解决的典型问题:在单位矩形内均匀随机的撒很多点,落在单位圆内的点占所有点的百分比大致估计pi。这种无任何指导信息的随机方法对人来说有点像看天吃饭、等天掉馅饼的意思。

2】启发式方法指利用了问题本身的信息来指导算法的搜索过程,这里的信息通常是局部的、有限的、不完整的信息。启发式方法则是在有限的搜索空间内,利用某种/些简单的启发式规则,大大减少尝试的数量,能迅速地达到问题的解决,但也很有失败的可能,该方法的关键之处是如何设计简单有效的启发式规则

个人认为,该方法的典型代表是贪心算法,简单说就是有便宜就占的方法,但既然无论便宜大小都要占,因此在算法前期搜索阶段解可能会有一些改进,但显然小局部的“便宜”都让你占完,同社会角色的人类似,该解就找不到别的解再给他便宜占,因此该算法就会陷入死胡同而再无出来的可能;其他的比如梯度、海塞矩阵都可以称为不同层次的启发式信息。

这里面有另外一个问题,问题利用启发式信息所需花费的代价越大,则解决特定问题时一般效率越高、效果越好,但适用的问题类型越窄,该算法典型是牛顿算法,需要利用海塞矩阵的启发式信息,在局部范围内求解问题达到二次的收敛速度;反之,一个算法利用启发式信息的代价越小,其解决明确问题时一般效率会越低、效果会次之,但适用的问题类型越广泛,此时的代表亦可举贪心算法。这种“启发式信息代价与算法效率和效果”犹如社会角色的专家和杂家,各有优势和用武之地。

3】元启发式方法粗略的说可以看成随机版本的基于群体的启发式算法,是既想拥有启发式方法H的“专和快”,又想拥有蒙特卡洛M方法的“省事”,这显然是矛盾的要求,但由于解决具体问题的潜在需求和挑战,以及人类“懒”的本性,于是就需要寻求多快好省的求解方法,如果知Evolution Strategy (ES)的产生背景,会大致理解这一“说法”。但这是要冒风险的,像一个笑话说的,一位聪明丑男娶一位漂亮但不甚聪明的女子,想生一个既聪明又漂亮的孩子,其结果却生了一个又丑又笨的孩子。因此,这里如何利用合理的折中,如何合理利用不同搜索机制的优势、并尽量避免其劣势就显得极其重要。

元启发式方法(meta-Heuristics)总体可以分为三类(Evolutionary, Physics-based, and SI algorithms):基于进化机制的、基于物理原理的、基于群体智能的。

meta-Heuristics并行的称谓:群体优化算法(Population-based Optimization Algorithm, SA可看作群体规模为1,要区别于群体智能Swarm Intelligence, SI)、自然计算(Natural Computation)、计算智能(Computational Intelligence)、智能计算(Intelligent Computation/Computing)(NCCIIC放到Evolution-based范畴也未尝不可)

3.1Evolution-based群体计算机制:

这种算法的基本产生规则是达尔文的自然选择、适者生存(Natural selection, survival of fittest)准则,Evolution-based群体计算机制的主要操作是杂交/交叉(Recombination/Crossover)和变异(Mutation)、选择等运算操作,从而实现Agents的群体驱动和进化,这种算法通常称为

演化算法(Evolutionary Algorithm)

演化计算(Evolutionary Computation)

进化算法、进化进算、仿生计算(Bio-inspired Computing)等。

Evolution-based群体计算机制从狭义上来说,包含

遗传算法(Genetic Algorithm, GA)

进化/演化策略(Evolution Strategy , ES)

进化/演化规划(Evolutionary Programming , EP)

遗传规划(Genetic Programming , GP)等四种进化算法分支。

Evolution-based群体计算机制从广义上来说,除了包含上述四种算法,还包扩

免疫优化算法(Immune Optimization Algorithm)

差分进化(Differential Evolution, DE)

地理优化算法Biogeography-Based Optimizer (BBO)

Memetic算法等;

其中免疫优化算法IOA还包括四种计算分支:

克隆选择算法(Clonal Selection Algorithm, CSA)

人工免疫网络(Artificial Immune  Network, AIN)

负选择算法(Negative Selection Algorithm, NSA)

危险理论(Danger Theory)等;

3.2Physics-based计算机制:

该算法的产生机理不同于遗传机制算法,而是将某些物理规律建模为群体优化算法,搜索的群体解通过启发于某种物理原理的规则实现群体Agents在搜索空间的相互信息交流和位置移动,最典型莫过于模拟退火算法(Simulated Annealing, SA)了,还包括,

Gravitational Search Algorithm (GSA)

Chemical Reaction Optimization Algorithm (CRO)

Gravitational Local Search (GLSA)

Big-Bang Big-Crunch (BBBC)

Central Force Optimization (CFO)

Charged System Search (CSS)

Black Hole (BH) algorithm,

Ray Optimization (RO) algorithm

  Small-World Optimization Algorithm (SWOA)

Galaxy-based Search Algorithm (GbSA)

Curved Space Optimization (CSO)

禁忌搜索算法(Tabu Search, TS)(我也不太确定TS应该划到哪个范畴)等;

3.3Swarm Intelligence (SI)-based计算机制:

SI模拟大自然的生物群体的群体搜索、协作行为和涌现现象,实现单个个体无法实现的基于群体的智能搜索行为,通过生物的群体协作、信息交流和社会智能等现象实现搜索最优解的目的,主要包括

粒子群优化算法(Particle Swarm Optimization, PSO)

蚁群优化算法 (Ant Colony Optimization, ACO)

人工蜂群算法(Artificial Bee Colony Optimization, ABC)

除此之外,还有

Bat-inspired Algorithm (BA)

Artificial Fish-Swarm Algorithm (AFSA)

Grey Wolf Optimizer (GWO)

Weed Optimization Algorithm (WOA)

Krill Herd (KH)

Firefly Algorithm (FA)

Cuckoo Search(CS)

Fruit Fly Optimization Algorithm (FOA)

Lion's Algorithm

Monkey Search

Dolphin Partner Optimization (DPO)

主要参考文献

Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis, Grey Wolf Optimizer, Advances in Engineering Software 69 (2014) 46–61.

4】超启发式算法(hype-Heuristics)

超启发式算法大致可以理解为“寻找启发式算法的启发式算法”,

定义:超启发式算法提供了一种高层次启发式方法,通过管理或操纵一系列低层次启发式算法(Low-Level HeuristicsLLH),以产生新的启发式算法。

超启发式算法运行在一个由启发式算法构成的搜索空间上,该搜索空间上的每一个顶点代表一系列LLH的组合,其结果是为了获得针对所求问题的最优或较优的一个或多个LLH组合,粗略的说超启发式算法是在()启发式算法的搜索空间上找到一个最优的启发式算法。详细信息请参考大连理工大学江贺老师发表于《中国计算机学会通讯》2011年第3期的《超启发式算法:跨领域的问题求解模式》。

[参考文献] http://oscar-lab.org/paper/cccf_11.pdf

【搜索算法三句半】

背景:搜索算法的发展很好的反映了人们认识世界的过程,

蒙特卡洛:不知咋搜索,问题出现,咋办?撞运气,随机找,看天吃饭;

贪心搜索:有比较的意识了,有历史信息,有好的就扔掉旧的,即有便宜就上、无便宜就走,只盯着眼前最好的,有点类似于狗熊掰棒子的意思;

模拟退火:其思想简单说还是“有便宜就上”,但该算法的眼光要深远一些、度量要大一些,即除了“有便宜就上”的贪心准则,还有“没便宜我也可能上”的牺牲精神,这度量一大,SA就不得了了,与Greedy有了质的区别,即算法的概率1收敛性,但在实用起来收敛速度还是比较慢的;换个角度看,模拟退火也可以看作醉酒版本的经典算法,即只记住一点模糊的、局部的搜索信息,而且走起路来方向还没准(搜索轨迹可能没有任何规律可言);

牛顿等经典算法:可看作极限版本的模拟退火算法,即把问题的信息挖掘的很充分,在局部范围内类似于精确制导,就像牛顿算法求解二次无约束优化似的,一步到位!但换个角度看,牛顿这把刀用对地方和问题很锋利,但要把剃头刀被建筑师傅用作瓦刀用于敲砖块,那就另当别论了;

群智能优化算法:一个有度量、有眼光的人就很厉害了,一群有度量、有眼光的人肯定更厉害,而且这些人不是独立的,相互之间的搜索信息毫不保留的互通有无,那这一群有度量、有眼光、毫无私心、一心为公的人在一块肯定更了不得,于是激发了这个领域持续的蓬勃发展。群体优化算法也可以看作一群喝醉酒的、又没私心、一心只想着团体、走路东倒西歪的醉汉(我喝醉过一次,知道醉酒时大脑是清楚的)

【算法与人生】

纳什《美丽心灵》大家估计都看过(没看过强烈推荐),纳什在Bar里思考如何成功约会美女的过程启发了纳什均衡。

群体优化算法,以蚁群为例,一个蚂蚁和蚂蚁群体的区别不可同日而语,本质的原因在于Agent蚂蚁不“聪明”,没有私心,各司其职,但就是这样一群“不聪明”的蚂蚁表现出惊人的行为和能量。个人认为,群体智能(Swarm Intelligence)已经不足以描述这些涌现现象,而应该称之为“群体智慧”(Swarm Wisdom)。

有些人说德国人木讷,但如果遵守规则的行为是木讷的话,这确实是木讷;

英国在住房上有一项福利政策,即单亲妈妈可以申请到很好的house(在中国就是有独立前后院落的23层别墅),如果我国有这项政策???想想为了多收拆迁款和拆迁房,有多少人“离婚”(这里假定政府给的补偿是合理的)?我们会不会认为这是可以接受的行为?英国女人真的很傻!!?

  if 个体in{聪明,“愚笨”},then =>> 群体in{聪明,愚笨,智慧}?



https://wap.sciencenet.cn/blog-86581-772563.html

上一篇:我为河南考生说句话---之信阳师范学院
下一篇:真实的世界、你我的世界和社会
收藏 IP: 158.125.125.*| 热度|

9 霍艾伦 王小平 程适 樊建勋 王满喜 彭真明 贾利颖 王鹏 秦健勇

该博文允许注册用户评论 请点击登录 评论 (13 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 07:15

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部