ainatipen
发表于 2021-10-7 18:46
如果你单纯指的是 Evolutionary algorithm / Meta-heuristic 我的观点是,有,但不是非常有价值。
在 @Chao Xu 下面评论写得蛮长的,单独拿出来好了。
----
Me: 我记得 Simulated Annealing / Genetic Algorithm 之类的 meta-heuristic 是有一定理论基础证明 convergence 的。文章有点长没时间仔细看完,但里面有提到这些的理论基础,敢问作者是怎么评论它们的?
@Chao Xu第六页和第七页. 文章里作者肯定这些存在的非常restricted的theoretical result. 但是作者认为1990年以后就没有什么有意义的东西了, 就连那些theoretical result也并不是很有用.
----
不记得 theory 能给出的 result 有多强,但印象中应该不是 PRAS (polynomial-time randomized approximation scheme),所以老实说的确是没有很强的保证,不好好调参数效果也许还不如一个 log(n) 的 approximation algorithm。
其实用来用去人们似乎用得最多的还是最老的 Simulated annealing,其他新发明的只是 yet another (meta) heuristic,框架是差不多的: random search in a large (probably infinite solution space) and iteratively improve, hopefully find a good enough solution。他们跟普通搜索方法的最重要区别在于,都有一定的机制跳出 local optima。
Key insight:
适用于一些复杂、困难得甚至没有有效 heuristic 的问题真正有效的应用,需要精心设计的 solution space:如何采取更有效、简洁、快速 evaluate cost function 以及搜索 neighbor 的 representation / encoding,以及针对不同 instance 的参数调优。
> 创新到什么程度能算是创立了一种被人认可的新算法,而不是对原有算法的改进?
比起原来的结果有 significant improvement。理论层面,比如从 log n -> 4/3 n 的 provable 的近似。实验上,比如从原来能做到的 80% -> 90% 的准确率,更严谨的可使用一些统计技术来评价。
JoshWindsor
发表于 2021-10-7 18:52
当然有存在的必要,不然你让我们搞计算机研究的拿什么申请基金啊。。。
(看点赞的人多再具体回答这个问题)
------------------------------
有三十二个人关注此问题,压力好大。。。三脚猫的功夫不知道说出来的话能不能服众呢。。。
先说明一下,我的研究方向是模式识别与计算机视觉那块得;问题里的那些算法,其实我并不是特别了解。。。
。。。
。。。
。。。
各位先别掀桌,毕竟问的是这些算法有没有必要性嘛~如果你要我写一篇介绍这些算法的科普文,那么上Google搜索关键词加"survey"或者"introduction"就能出来一堆东西了,而且人家说的肯定比我好:什么某某算法用在某地方有奇效,某某算法其实很垃圾,某某理论是人类的未来,宇宙的良心,某某领域下的所有知识都来源于韩国的私密达。。。
如果你逼我回答这些东西,把我折叠掉吧,现在整paper写这种survey都要吐血了,我才不会在工作划水的时候还干这类苦逼事儿呢。。。
不过问题说的这两点,的确是好问题,也基本上和“腾讯出新产品算不算创新”差不多类型的疑问。在这一点上,我还是能够说几句得。
-----------------------------------------------------------------------------
楼主的问题主要是搞这么多尽整没用东西的必要性,首先我说一个大家都能够接受的理由(前面回答一个问题被人踩了那么多次想想就心痛。。。):一个算法,或者一个概念,在提出来的时候,其实经常是不成熟的。概念虽然新颖,但就像刚出生的小鸟一样,十分脆弱,有时候还不见得会比现有算法要好;所以需要慢慢培养,挖掘里面的潜能,确定这个新的理论能够适用在什么地方,不能用在什么地方,优劣点,能不能和其他算法合并起来弄成一个新的更牛逼的货,等等等等。
等这些活都干完了,一个完整的理论才能算最终完成。我们看大学教科书里那些看起来很牛逼的理论体系,也都是这样一点点堆出来得。
不要觉得这些微创新让人不齿,俗话说一口吃不成胖子,罗马不是一天建成得,Linux不是一个人写出来得。你说的这些新算法,其实都成为了一个更大理论体系的基石。后人在我们前人研究的基础上,不断的往上构筑新的东西,总有一天,那个最终问题会有被攻破的可能。如果你要求一个科学家,在最开始的时候就开发出一套完整的framework,那不但不切实际,也没有必要,效果也不见得好。
那么一般科学是怎么发展得呢?像问题里说到的这些算法,一般会经历同行比较,容易实现且效果比较好的算法,就会被更多的论文引用到,也会被更多的人所熟知。更多的人研究某个特定算法后,整个算法体系也会变得更加完整。在经过一段时间后,量变引起质变,你就可以称之为全新的新理论了,研究者在这个理论里发现了新的问题,想到了几个相应的解决办法,以此类推下去。而其他的那些竞争者,在渐渐的无人问津后,也就慢慢得埋没于论文之海里了。
-------------------------------------------------------------------
第二个理由,也就是最开始提到得,我们这些搞研究的人就是靠这些微创新吃饭得啊~~我之前在另外一个问题里说过,博士读的这几年,就是挖坑的过程;挖了三四年,挖的方向不对,博士毕业就会出问题;我把搞研究比喻成挖矿的另外一个原因就是,搞课题和挖钻石黄金一样,一个课题其实不是挖不完得;当一个问题得出了最优解之后,也就是这个课题死亡的时候了。
这点上我想引用一下Bleach漫画里的内容,你们感受一下:
“完美”就是没有再进一步,也没有“创造”的空间。这代表着智慧与才能都将无用武之地了。
这是第306话的内容,那会儿我还在读本科,你们能够想到我读到这一段后有多么“culture shock"嘛。。。
搞科研最怕的一件事情,就是自己当前搞的领域,已经得到最优解了。别人已经发现了真理,大家用那个就能得到最好的结果,那还要我们其他人干什么。。。
所以挺矛盾得吧,搞科研一方面要不断搞新花样出来,同时又要担心某个蛇精兵真的弄出完美结果来,搞得大家都不开心。。。
这时候,微创新就派上用场了。
今天你改进算法里的一个缺陷,明天我帮你relax一个constraint,后天我把这个算法用在新的领域上,大家都能够发表paper,所有人都能够皆大欢喜。
这样的话虽然科研进度有点慢,但好歹大家都有活路了,申请科研基金有底气了,我们也可以继续参加会议吃喝玩乐去了,吼吼!
然后有一群有良知的人就看不下去了,发明了一个让人深恶痛绝的单词:“Novelty”。意思就是你丫得要是想水论文我就拿这个把你拒掉!这群有良知的人一般都在顶级会议里,所以这也是那些会议投起来都那么难的原因,诶。。。
--------------------------作补充的分割线--------------------------------
2014年4月30日更新:因为一直有答题后点取消关注的习惯,所以后面大家的回答我都没见到,直到 有人 @ 我后才发现,貌似里面的内容造成了一些误会(以及这个回答被人踩了那么多,看着就让人心痛,大家都太认真了我去。。。),在此说明:
我最后写的那块所谓”微创新“的话,其实我是一种调侃的意味,说的一些三观不正的话。现在看来,绝对造成误会了,以为计算机领域就是这么水旺旺的状态。。。
现在我就认真回答了,如果就是改参数这类contribution级别,绝对不会登入大雅之堂得。事实情况下,越是高级会议,越追求novelty,也就是论文contribution的创新程度。如果只是水workshop之类,当然你想随便怎么水都成,毕竟有好多workshop都没多少人投,要是再挑三捡四的话这会议也不用开了。。。
但像我这里的CVPR之流,中稿率只有20%左右。要是那些改参数的论文也能中的话,那只有一种可能:
一定是chair的小三投的稿子!
除了这种情况,我想不出像CVPR这种三个feedback为accept最后都能被拒的会议,novelty被定为trivial的文章会中的可能性。。。
恩,所以 @Chao Xu说的事情,计算机领域这里,高级会议是不可能中得:改参数就不用说了,有时候改算法如果改得不够多都不行,什么”XX算法在新领域的运用“之类的文章肯定会被reviewer骂得连他妈妈都不认识。。。就我所知道的情况,改算法最后能够中,唯一的可能性就是原算法太烂,而某家伙化腐朽为神奇得把那个算法给救活了,而且还比同类的其他算法结果还要好,才有中稿的可能。。。
而且还要考虑算法是否解释清楚,motivation是否足够迫切,实验做得是否充足,你的导师和我是否是仇人,你组里的人有没有在过去十年内拒过我们组的论文,等等等等。。。。反正就20%的中稿率,据了这篇还有一大堆candidate可以选呢。。。
顺便一说,上面的这些坑爹理由我都不幸碰过,算是达成”被拒理由“收集成就了,奖杯就放在google scholar的个人主页上呢,你们慢慢体会一下。。。
所以简而言之,漫画插图后面的内容,描述是需要做补充得:并不是所有的论文都只是修参数之流,也有开创新算法之流。前者在低等级会议和workshop中常见,后者主要在高级会议中。当然咯,对于整个大领域来说,对于解决领域终极问题来说,这还是一小步中的一小步,也就是我所谓的”微创新“啦~特此说明,修改正文我就不做了,因为懒。。。
以上
最后再吐漕一下double blind机制,妈蛋说是double blind但稍微有点经验的reviewer一看paper的reference部分就知道是哪个组写的文章了,这double blind还有啥意义。。。
DomDomm
发表于 2021-10-7 18:54
真正优化算法领域,群体智能算法毫无疑问处于鄙视链的最末端。
按照以前老板的说法,不就是撒豆成兵嘛。
经典算法,永远是充满美感。你可以看到研究者是怎样深入挖掘问题的结构特点,设计出漂亮的算法,然后对着薄薄几页纸的论文惊叹。
近似算法,伪多项式时间算法,启发式算法,元启发式算法…也有自己的精妙之处,起码你同样能够看到作者的深入思考。
当然还有拉格朗日方法,某院士大牛的真爱…
然后你看到了遗传,蚁群,粒子群…恩,也蛮有意思的,虽然调参是个罩门。当年身边搞智能算法的,最怕答辩时遇到大牛屡试不爽的两个问题:1. 你的近优解有上下界吗?2. 调参花了多久?
最后看到…鱼群算法,鸟群算法,头脑风暴算法,菌群算法…这算误入生物系?我曾经见过一个女生,答辩时介绍自己的鱼群算法,模仿了鱼的休息,鱼觅食,鱼抱团防御天敌…就差鱼嘿咻了,估计是女生脸皮薄不好意思吧!
stonstad
发表于 2021-10-7 18:57
领域相关人士简单说一下吧。
首先,各种x群算法我本人也是相当反感,但这种改个参数就自称新算法的往往是三区以下的文章,而且要么是没公开源代码,作者自说自话,要么就是做了几个特例测试函数,毫无说服力,这种paper给领域招黑,应该打压。
实际上像moead,nsga系列这种开创性的进化算法,并且在工程以及理论领域应用较多的实在不多。近些年tlbo算一个。
而且很多算法都存在算法拟合问题的情况,即算法缺乏通用性,现在千奇百怪的测试函数集很多,大家都只挑自己算法表现好的来测试。比如cec2009的uf和cf系列,这个测试集很有挑战性,但是在这个测试集表现好的函数在其他测试集表现如何呢?我个人在传统zdt和dtlz测试集测试了moead等cec2009参赛算法,在同样在同样参数下,结果相当难看。也就是说,参数对这类算法影响很大。但是同样对应一种类型的问题有一个合适的参数就够了,而不是每个问题想得到好的结果都要去调参,这样的算法才称得上是合格的进化算法。
遗憾的是,近些年许多进化类算法对着某组问题测来测去,一直去拟合参数得到更好的竞赛结果,而忽略了进化算法的通用性,这是进化算法领域发展最值得诟病的一点。
不过,在进化算法领域的顶刊ieee trans上,不得不说高品质的文章还是很多的,那里的文章基本对问题测试的就比较全,对算法讨论也较深,同时创新点也非一般得调参拟合,但即使这样,里面依然也有题主说的水文。
另,进化算法是缺乏理论上的收敛性证明的,尽管很多问题它看上去的确收敛。
===
稍微更新两句吧。
我最近在写一篇进化算法的SCI,用了三组测试集来对比,同时审稿人要求多种评判指标,pareto compliant与non pareto compliant,以及不同的排序方式。因为算是提了一个简单的机制,所以我选择了将近30个二维三维测试问题来测试,暂不考虑三维以上。
现在进化算法想发文章单单用igd或者gd来评价结果已经不行了,也是十分不充分的。一组测试集也直接会reject,各大期刊逐渐要求公开源代码或者有完整可复现的伪代码。
最新的文章好多都在wfg和DTLZ上测到了15维甚至更高,我感觉有些跑偏了,如果优化问题到了这个复杂程度,不如去想想怎么先缩减维度,毕竟15维优化出来的结果根本没啥指导工程意义。
我觉得,进化算法目前应该注重如何在最大限度降低算法复杂度的情况下,提升算法的性能,以及三维以上的优化问题的可视化和解读上。
并且,通过实验验证来证明优化的可靠性是急需的,而不是陷入钻纯理论和对比数据堆砌的牛角尖。毕竟进化算法在工程应用领域应该是大有可为的。
应该是的。
量子计算9
发表于 2021-10-7 19:03
所谓群体智能算法,即模仿生物群落的特点来进行优化搜索。但是这些只是生物学伪装,本质上依然是随机搜索。
个人认为,所有的这类算法都包含两个部分。第一部分是局部搜索,即在局部空间寻找最优值;第二部分是全局搜索,即在局部搜索陷入最优后跳出。
如果一个群体智能算法可以在这两个部分有所突破,提出全新的泛型,那么我觉得这个算法就是有价值的。如果只是换了一个生物学的伪装,本质依然是前人的搜索泛型,那么这个算法就只是灌水而已。
xiangtingsl
发表于 2021-10-7 19:09
智能算法方向通常被设置在计算机系(与人工智能师出同门)
但因为其被广泛应用在解决运筹学问题
这里仅从智能算法在运筹学和供应链管理应用的角度浅谈
工业界
这次回国跑了国内运筹学相关的几个大厂以及明星企业
在问及他们几十人的算法团队主要采取哪些运筹学算法的时候
启发式以及智能算法占了多数
中规中矩用整数规划建模调用如Cplex求解器的很少
一方面是因为国内研究运筹学精确算法的团队很少(据我所知)
另一方面很多工业界应用对时效的要求非常严格
因此单从工业界应用角度 -- 必须存在
它是有实际应用价值的
回到学术界
数学规划领域的精确算法虽然有优美的数学模型/几何意义但经常被称为“绣花枕头”
智能算法虽然几乎没有数学理论支撑但却是“万金油”
至于调参(炼金术)以及论文灌水的问题
我想于每个专业都是存在的
既然这个community仍然存在(国内做这个方向的不少)
那么必然有他存在的道理
这个道理可以是:在工业界有足够多的应用
P.S.:大厂们其实纷纷表示想招精确算法人才,因为稀缺阿
最后关于智能算法本身,作为一种随机/迭代算法,或许你想进一步了解它以及与其他俩个community的异同:
遗传算法,模拟退火算法,粒子群算法,神经网络等智能算法的作用?
【学界】整数规划精确算法/近似算法/(元)启发算法/神经网络反向传播等算法的区别与关联
<hr/>更多运筹学、人工智能(算法)干货,敬请关注公众号『运筹OR帷幄』,以及:
『运筹OR帷幄』大数据人工智能时代的运筹学
RedZero9
发表于 2021-10-7 19:11
“In general, all metaheuristic design should return to a situation in which methods are developed based on insight into the structure of the problem.”出自Metaheuristics - the Metaphor Exposed。
能肯定的是:脱离问题而设计的算法都是没有存在意义的。不管是群智能、进化算法甚至是数学规划领域的方法。
只是群智能算法“偏离问题”的程度有点过了。
一个逼格满满的比喻就可以标榜为创新,加上这类算法实现框架大同小异,coding难度低,发文章又全靠最后的实验数据,而且代码还可以不用贴出来,可想而知灌水是有多容易了。找些benchmark问题跑跑,对比一下自己写出的“别人的算法”,这里面的猫腻可想而知。
当然如果有类问题确实可以用蟑螂算法解出来比其它算法都好的,那么这样的发现还是有一定价值的,只是这种文章真的很少,有这样的发现也很难。
话虽这么说,但是Metaheuristics在OR圈还是非常重要且很有存在价值的领域。这个领域的创始者Fred Glover拿过冯诺依曼理论奖。他Informs上的简介:Fred W. Glover
Arzie100
发表于 2021-10-7 19:17
群体算法就是换张皮一个算法
研究起来比较快是一方面
所以这方面的水paper很多很多
但是其中的精华部分还是很有用的
是解决NPHARD问题的手段之一啊
RhinoFreak
发表于 2021-10-7 19:17
自神经网络和遗传算法的兴盛发展之后,各种与生物思想相关的算法层出不穷,如蚁群算法、鱼群算法、蜂群算法、蛙跳算法、蜘蛛算法,等等。
从小在县城长大的二狗子虽然只有小学三年级的教育背景,但从小就对计算机科学有着浓厚的兴趣,尤其是算法方面,并一直坚持自学和钻研最前沿的理论。在一个月黑风高的夜晚,二狗子在建筑工地的厨房观察到蟑螂觅食行踪的规律,由此受到启发,提出了一套全新的具有自适应、自学习、自组织能力的人工智能优化算法,即蟑螂算法,并在相关专业的核心期刊上发表了论文,他也由此成为了一位受人尊敬的学者。
当然,二狗子绝不会满足于现有的成就,他坚信,对科学的钻研是永无止尽的。后续系列之蝇蛆算法、蛤蟆算法、跳蚤算法、王八算法、大闸蟹算法,敬请期待。
fwalker
发表于 2021-10-7 19:25
遵循简单规则的简单生物以群体形式出现时,可以表现出惊人的复杂性、效率,甚至是创造力。这种特性被称为“群体智能”,在自然界中随处可见,但研究人员最近开始利用这种特性来升级改造一些领域,如机器人、数据挖掘、医学和区块链。
例如,蚂蚁只能完成有限的功能,但是蚁群可以建造桥梁,创造传递食物和信息的“高速公路”,发动战争,奴役其他物种的蚂蚁——所有这些都超出了任何一只蚂蚁的理解范围。同样的,鱼群、鸟群、蜂群和其他物种群体所表现出的有计划性的行为,也应当出现在拥有更高的智商等级的物种之中。
这发生在一个叫做“共识主动性”的过程中。简单来说,一个小组成员行为的一个小小改变会导致其他成员的行为也发生改变,从而导致一种新的行为模式出现。
当一只蚂蚁找到食物来源时,它会用信息素标记出路径。这吸引了其他蚂蚁过来,引导它们前往食物来源所在地,并提示它们用更多的信息素标记这条路。随着时间的推移,最有效的路线将成为超级高速公路,因为获取食物的路线耗时更短且对于蚂蚁来说更容易的话,到达食物所在地的蚂蚁就越多,它们留下的信息素也就越多。因此,这看起来就像是一个更聪明的个体选择了最佳路线,但这条路线来自于许多个体所做的微小的、简单的改变。
那么,这对人类意味着什么呢?不胜枚举。在过去的几十年里,研究人员开发出了大量的算法和启发式算法,比如蚁群算法和粒子群优化算法,并且这些算法正很快被采用。
机器人群
一群机器人将遵循和蚁群一样同样的原则来工作:每个成员都有一套简单的规则可以遵循,以进行自我组织和自我支持。
例如,乔治亚机器人与智能系统实验室(GRITS)的研究人员创造了一群简单的机器人,它们可以拼写单词和弹奏钢琴。这些机器人不能交流,但仅仅基于周围机器人的位置,它们就能够使用自己的特殊创建的算法来确定完成任务的最佳路径。
这对无人机群也非常有用。
去年2月,中国的航空公司亿航制造了一千架无人机组成的无人机群,它们不仅完成了精彩的高空飞行表演,还展示了能完全自主地随机应变和排除故障的能力。
此外,就在最近,剑桥大学和科克大学公布了他们称之为“无人机智能能源共享网络”(Energy Neutral Internet of Drones)的构想。令人惊讶的是,这群无人机能主动与其他没有得到通讯信息,或者能量不足的无人机分享信息或能量。
世界各国的军队也都在利用这一点。
去年,美国国防部宣布其一大批微型无人机测试成功,它们可以更低能耗、更有效地执行复杂任务。他们声称,“微型无人机显示出了先进的群体行为,如集体决策、适应性编队飞行和自我修复。”
一些专家估计,至少有30个国家正在积极地发展建设无人机群,甚至是水下无人机,用于完成军事任务,包括情报收集、导弹防御、精确导弹打击和加强通信。
美国国家航空航天局还计划在太空探索中部署大量的微型宇宙飞船,医疗界也在考虑使用大量的纳米机器人来精确运送药物、进行显微手术、靶向攻击毒素和制造生物传感器。
如果人类是蚂蚁呢?
任何区块链的优势都来自于支持它的社区的规模和多样性。比特币、以太坊和莱特币等加密货币是由使用、投资、以及最重要的,开采这些货币的人们所影响,从而让区块链发挥作用。没有一个活跃的社区,或者群体,他们的区块链就会失败。
若你从上往下看,区块链竟像蚁群一样运转,自然而然便会找到最有效的方式来移动大量信息。
矿工们相互竞争来进行复杂的计算,以增加另一块区块,而赢家则会得到区块链的原生货币和商定的费用。当然,拥有功能更强大的电脑的矿工更有可能赢得奖赏,从而也进一步增强了赢家的能力,让他们获得更多的奖励。随着时间的推移,能留下来的矿工越来越少,因为胜利者能够更有效地承担更多的工作量,就像蚂蚁建造高速公路一样。
此外,一家名为“Unanimous AI”的公司开发了一种算法,让人类可以集体做出预测。到目前为止,人工智能算法及其人类参与者做出了一些预测,准确的令人惊讶不已,比如肯塔基赛马会的前四名、奥斯卡奖得主、斯坦利杯冠军等等。有越多的人参与到该群体之中,他们的预测能力就越大。
需要说明的是,这不是基于群体共识的预测。更确切地说,这群人利用软件实时地输入他们的意见,从而对群体内的其他成员进行细微的改变,由此其他成员的输入的意见也会产生细微的变化。
研究表明,在没有算法的情况下,群体智能的表现总是优于没有算法加持的个体和人群的表现。虽然这只是冰山一角,但也有一些人认为,群体智能可以彻底改变医生对患者的诊断方式,以及向消费者推销产品的方式。群体智能甚至可能是真正创造人工智能的关键一步。
虽然群体智能是许多物种成功的关键组成部分,但加以时日,人类便能利用它的有效性。