KaaPexei 发表于 2021-9-19 16:05

有一些超级难的算法比如遗传算法,蚁群算法,看了数学建模国赛感觉好难写,那些人怎么写出来的?

畅所欲言随便吐槽,反正辣鸡一个,不怕吐槽
是有现成的算法给我套用吗,还是必须一点点写

闲鱼技术01 发表于 2021-9-19 16:08

想起了大一下学期,和老师一起做遗传算法的日子,经过一年多的努力,最后在老师帮助下还发了一篇会议论文
L. Wang, W. Gong: Ensemble of different parameter adaptation techniques in differential evolution. BIC-TA (2) 2016: 73-79还和老师当时去西安参加了会议,周围都是研究生、博士生,自己一个本科生还是有些自豪的。


当然现在自己已经研二了,就回忆下当时的过程吧。
认识老师是在一门「计算机导论」的课上,当时老师讲到「大学生,大家要多做东西,可以找院里的老师帮助,老师会和热心的,不要怕自己什么都不会,要敢于尝试,balabala」
然后过了一段时间,自己一直记着这个事。有一天终于鼓起勇气去找了老师,哈哈,就是去找了上课的老师。
因为自己是上大学才接触到编程的,当时选择计算机专业也只是一种感觉,就是感觉自己喜欢计算机,当时也还没上一学期课,真的是还什么都不会。然后和老师说,自己现在只会一些基础的 C++,别的也不会什么,但是很喜欢编程,想和老师做点东西。
老师说,喜欢就好,我会给你定期布置任务,每周也要向我汇报做了什么。
于是,科研的生活就开始了。
大一的寒假,老师就给我发来一篇论文。
Storn R , Price K . Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 1997, 11(4):341-359.当我打开这篇 pdf 的时候,懵逼了。


天呐,纯英文的,我的四级还没考呢,,,
但也没办法,只能硬着头皮看呗,有道的划词翻译用起来,把不会的单词用 pdf 的注释起来,然后就这样一点点的自己慢慢读,慢慢理解。
大二开始,老师又问自己会不会 Matlab ,那时候当然不会了,然后就又去学,不过网上资料也很多,学的也很快。
再接下来,就是看了一本讲遗传算法的书,还有 matlab 工具箱。


然后在书里对遗传算法有了大概的认识,以及可以用别人写好的一些遗传算法的工具箱做一些简单的最优值问题。
接着就又回到了之前的论文
Storn R , Price K . Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 1997, 11(4):341-359.我主要做的是差分演化计算,而这篇可以看做是最基础的算法,简称 DE 算法。然后老师让我自己用 C++ 去实现论文中提供的算法。其实就是初始化种群、变异、交叉这几个步骤。然后自己就尝试写了一下,并且算了一些简单的函数的最优值,发现还可以,现在都记得当时写出来的开心。
再接下来,就是一篇又一篇的论文。


jADE,jDE 等等,看完以后老师还是让自己尝试着实现。之后老师给了我老师自己封装好的一个差分演化计算的框架,让我自己研究一下怎么用,去跑一些数据。
问自己有没有什么想法优化一下,自己当时也提不出来什么好的 idea。然后老师就会讲一下他的想法,让我去实现一下,跑一下公开数据集的数据,然后再用别人的数据跑一下,作对比。又学了一下统计软件 Origin 。
当时记忆深刻呀,因为演化计算会设置一个种群迭代的次数,所以得出一次结果其实还是很慢的。当时为了更快得到结果,用舍友的电脑跑,用云服务器 24 小时的跑,不停的跑啊跑。
反正不停的尝试,然后和老师交流,最后找到了一种可以优化的方案,最后把最终的结果以及分析给老师,老师帮忙完成了论文。
一年多最大的收获就是,基本了解了科研的全过程,其实就是看论文,然后实现论文里的思想,然后跑数据,然后优化,然后跑数据,然后优化,当优化成功的时候,就可以做一篇论文了。
以至于对后来自己毕业设计也有很大帮助,当时是写深度学习相关的,上手会很快,当老师给一些英文论文的时候也不再害怕了。
其实编程的话不管什么,做之前都会觉得好难呀,当接触一个新的东西的时候又会觉得好难呀。但每当完成以后,再回过头来看,其实也并不难。然后就这样一次一次的战胜自己,再后来看到新的的东西也就不会害怕了,因为已经深信自己一定可以完成的,就像以前一次又一次的成功。

mypro334 发表于 2021-9-19 16:15

直接调包,python有一个叫scikit-opt的包,把题主说的那几个超级难的算法(如遗传算法,蚁群算法)都高效实现了已经(其作者和著名的scikit-learn没有关系):
https://github.com/guofei9987/scikit-opt感觉还是蛮不错的。我还做过一个scikit-opt结合线程池实现并行样本评价的程序,有时间会分享一下。
另外,传统优化也是需要学习的,可以用scipy.optimize模块。深度学习技术也会在比赛中越来越多。最后基础算法知识(刷力扣用的那些技能)也是基础中的基础。专业领域知识(如语音图像的常见预处理)再熟悉一下就可以上战场了,数学建模没啥好神秘的。
说实话比赛时候大部分时间可能都会用来建模型,也就是写问题的约束条件。真正到解的时候,多试几个求解器就完事儿了。不然这比赛也不能叫建模大赛了,改叫求解器大赛就好。本人研究生数学建模三等奖,放到最后说吧怕丢人,哈哈哈哈哈哈。
最后打个广告,带数学建模学习(部分题型),现在还没开始做,有兴趣可私聊我讨论。
<hr/>点赞人好多,我趁机贴点我的相关文章吧:(都是比较有趣的简短文章,欢迎品鉴)(以前我做创意编程做的多点,以后会更多地做数学建模和数据分析的相关事情)
忘荃:大富翁模拟器-使用Processing忘荃:Python中的模型敏感度分析(使用Salib)忘荃:数学建模:利用Simpy模拟简单排队模型忘荃:在 Gym 上构建会动的人工智障2:寻迹小车(python)忘荃:CodeingGames上的PID自动控制实战-通关Coders Strike Back 青铜白银段忘荃:连连看:processing原创编程实例忘荃:50行代码实现抽象画【蒙特卡洛抽样】忘荃:Processing做益智游戏-二维魔方相关专栏:
趣味学编程processing.PyPython 数学建模与超级可视化最后发一个我做相关领域创作一年,总结出来的“编程学习最小闭环理论”吧,真的非常推荐看一下~吾行吾道,虽远必至。
计算机学院的学生该怎样提高自己的编程能力?

fwalker 发表于 2021-9-19 16:22

实现算法这种事,难与不难是相对的,看你的经验和知识储备。
十几年前,大四做毕业设计的时候,看到同屋的研究生用遗传算法做项目,感觉很高大上,潜意识里觉得很难。
刚读研老板甩手给了一个十万行代码的软件学习。虽然很多部分没有吃透,但是也学了一些东西。以后再阅读其他代码没有那么慌了。
博二突然有天想了解下这些智能优化方法,就找了一本书,下面这本:
《智能优化方法》【摘要 书评 试读】- 京东图书边看边自己撸,大概花了一个月的时间,把书里的算法都实现了一遍。从头到尾感觉是很轻松的事情。跟UCT和alpha-beta剪枝相比,这些算法实现起来简单多了。
随着你的经验越来越多,很多事情都会突然顿悟,就像突然学会骑自行车一样。有些东西,如果觉得特别难,不是那么要紧的话,可以放一放,后面经验和能力积累得足够多,回头再来做自然而然就不那么难了。有些硬骨头非啃不可,多找人交流一下,比闷着头自己干强百倍。
自己撸,是在用身体感受算法的各个细节,会积累更多的经验,非常有助于你实现其他算法,还会发现一些教科书里没有提到的问题。比如,实现k-means聚类的时候,如果有的簇不包含成员,那么需要在编程时考虑这种情况。有些教科书就没有提到遇到这种情况该怎么办,甚至没有提到会遇到这种情况,如果你自己撸,就可以发现这个问题,然后去CSDN去看别人是怎么解决的。如果只是调包,那么很可能你根本不会发现这个问题,也失去了一次经验积累的机会。而且,你总有一天会自己设计实现新的算法,没有包可调,那就只能靠自己了。
对于你很熟悉的自己撸过的,或者自己的重点不在于实现这个算法,那就调包吧。

acecase 发表于 2021-9-19 16:29

这个分两种境界:
第一种,就想马上使用,定性的理解算法的基本原理和流程,然后直接看Matlab遗传算法的文档,看明白主要参数都是什么意思,再把配的例子调试一遍,这样就够了,遇到常规问题可以解决。
第二种,深入理解算法每一步的公式推理过程,把现成的实现代码拿过来,调试理解一遍,或者再强一些手写调试成功一遍代码。这样,遇到非常规问题,需要重新编写某些步骤(才能适用于你的具体问题),只要肯花时间就能解决。
建模使用的话,第一种境界就可以了。

Baste 发表于 2021-9-19 16:33

其实并不难,这两种算法都是先写好算子,然后迭代就完事儿了。
不想写代码可以看这个
guofei9987/scikit-opt六种启发式都写好了,代码简洁易懂。遗传算法、粒子群算法、模拟退火算法、蚁群算法、免疫优化算法、鱼群算法。
抄就完事了

ChuanXin 发表于 2021-9-19 16:40

参加过几次国赛,研究生期间水了一次国二,一次国一,作为我们组编程担当看到这个问题还是想说两句的。
国赛期间这么短的时间(记得本科是三天,研究生四天),从0纯手撸这些算法是不太现实的,时间分配上还要考虑分析题目,收集文献,确定模型,收集数据,实现模型,输出论文。
重要的是前期的知识储备,常用的基础算法模型无论是自己先实现一遍,还是收集大牛已实现的,有自己的算法库,才能做到手中有粮,心中不慌。比赛里能用到的,魔改之,应付比赛是足够的了。
如果仅就遗传算法而言,看到有答主提到 Matlab遗传算法工具箱,这个还是十分强大的,调它!源码拿来,魔改它!但我个人认为这个太重了,没必要拿来水比赛。拿出来一些基本的源码出来魔改就行,比赛最重要的是参与感对不(狗头保命)
仅就比赛而言,前期的准备和积累是十分重要的,无论是学校组织的培训或校内赛,几个小伙伴一起组会学习这类基础知识,对自己的成长都是帮助很大的。
脱离比赛,更重要的是个人的成长吧,把一些现实问题抽象成数学问题,拿书本里面的知识去实践,拯救了无数数学系的厌学少年(大误,此处来自一个数学学渣的吐槽)。
写着写着就跑偏了,很难忘那段和小伙伴们因为热爱,一起全身心投入一件事的激情时光。

Mecanim 发表于 2021-9-19 16:47

查文献也是需要技巧的,比如高级检索。

jquave 发表于 2021-9-19 16:51

很多算法在通用机器学习库里面没有,比如sklearn虽然是个通用机器学习库,但是并没有包含所有算法,像关联规则这样的算法sklearn就没得。
不过Python具有庞大的社区,如果通用的机器学习库不能调包的话可以直接上pypi找,在pypi上直接搜索算法名称,保管一大堆该算法的第三方实现,有的文档写的还贼详细。
你要做的就是pip install xxx,然后对着文档说明调个包。

yukamu 发表于 2021-9-19 16:53

以下是点赞多了之后更新的部分。
我最近弄自己的论文遇到了个链接:
做仿生算法论文遇到的保存历代的粒子群算法(PSO)的代码库(有对应参考文献的):http://clerc.maurice.free.fr/pso) 里面的代码都对应着经典的论文。

我是数模国一负责编程的同学,刚开始也是Matlab小白。说点自己的小小经验。
我的Matlab不是成体系学的,而是通过多次训练赛,然后写多了就会了。我用了两本工具书,学习Matlab的本体时,用的是《MATLAB数学建模与仿真》,因为我是通信的嘛。其实写到最后,要活用Matlab的内部搜索功能,当你会用这个去使用不同的函数了,就OK了。然后学习仿生算法时,是我的老师给我推了下面的这个书。其实总结一下就是,多打比赛,把司守奎的数学建模算法里面用到的各种算法都能用Matlab写出来,就OK了。
先推荐一本书吧,我的指导老师推给我的(个人感觉非常好用,并不是打广告,所以截图截成这个样子,希望知乎别折叠掉。(也有人叫我好物推荐这个书,感兴趣的可以划到末尾看看书的链接hh)大家可以先到图书馆看看有没有的借。


就是这个书,非常有用,能让你迅速入门各种智能算法。
但是,如何真正入门一个智能算法,最后还是要真正的在训练中,用它去解题。算法只是一个工具,不是算法越复杂,奖项越高。记得有一个训练题,有一个给分点是搜索结果,满分标准的搜索方法就是简单的利用单调性进行二分的搜索;用遗传算法的反而被扣了三分。在这里还想说一点就是,司守奎老师的算法书才是国赛最基本的最根本的东西,编程队员内容必须熟悉会操作。对于陌生的函数也要具备快速掌握使用方法的能力。智能算法只是数模的很小一部分,非常小的一部分,希望大家不要过于纠结于看起来高大上的算法,还请打好基础,再玩花活。想打好国赛,多训练建模是一部分,做完真题之后,对照评分标准,看看到底是怎么评分的,了解评分的过程,对于之后做题是会有很大帮助的。
以下是回答的本体:
如何学一个算法,比如遗传算法。
1、先了解方法的基本理论。
仿生学算法,是将实际的问题,要进行抽象转化的,对应关系一定要清楚。比如,遗传算法中,个体对应什么,种群对应什么。算法的操作以及算法的核心流程必须清楚。初始化要干嘛?什么是变异操作,什么是选择操作,什么是交叉操作。这些操作,是对谁进行的,什么条件下进行。算法的一些参数要清楚。种群数量,迭代数,交叉概率,变异概率等等。
2、按照前人代码实际在简单问题操作
可以按书自己写一个,也可以抄别人代码,自己真实操作一下。一定要找那些写的有体系的代码。比如遗传算法,有初始化、选择、交叉、变异操作,这些操作是要写在子函数中,而主代码是调用这些子函数去运算。这样子的代码,才能为你所用,才能更好的改进。
3、进阶
遗传算法的编码有哪些?二进制,实数编码,这些编码什么时候用,怎么编码译码,他们的交叉,变异操作应该怎么根据编码方式改?遗传算法的选择方法有哪些?轮盘赌,等等,怎么写?遗传算法的参数怎么弄可以跑的快一些,比如交叉概率,变异概率的自适应等等

随便写的答案居然有98个赞,感觉还是良心点,补充一下好了。
首先,遗传算法不需要经常用的,他是目标规划的最后手段,先看看你的目标方程和约束条件是否满足司守奎的书中的几种常用规划,满足就直接按照书本调用matlab的函数。
血的教训告诉我,一般目标规划用遗传真心浪费时间。如果看起来不太行,那么就用遗传搜吧。关于遗传算法的基础知识,CSDN上面其实有很多的,我随便谈一下使用遗传的一些坑吧。
1.关于编码:越界了怎么办?
比如我有变量 x y , 我的x可以取 y可以取, 那么可以用4个bit表示x和y。比如:0010->x=0,y=2。那么问题来了,在交叉和变异的时候,一不小心出现了11**,就是x=3了怎么办? 这是不可取的,那这时,我们是允许这个个体继续参与运算,在计算适应度的时候将其设定为特定值以示非法,还是就地处理,在每次交叉、变异操作后都检测头一个bit以确保他是0而不会为1呢? 这其实是需要自己思考的。
2.多目标规划怎么计算适应度?
其实就是一个多目标规划怎么求解的问题了。你可以转化为单目标,可以看看别的论文怎么做,也可以把多个目标设置不同的权重。还有一个叫非支配排序遗传算法:李莉. 基于遗传算法的多目标寻优策略的应用研究 . 江南大学,2008.有兴趣的伙伴可以看看。个人建议多目标的时候不要死板的只计算一个适应度, 比如你模型输出有温度+湿度,那你编程的时候就先别给它合成一个适应度,先输出温度+湿度再说,等以后团队讨论怎么决策哪个解是比较优的, 这样写程序不会太麻烦自己,不然团队讨论了之后就得推翻重写。
3.解太多了咋办,要搜好久?
1)先大范围区间搜一下,比如答案要求小数点后一位,那你先整数搜一下,看看有没有规律。
有规律,缩小区间范围搜索没有规律,那就利用先前大范围区间搜索的较优解,作为下一次搜索的初始化解。
2)把搜索区间拆开,1-30拆开成1-10 11-20 21-30, 代码拷贝三份开三台电脑搜索呗。
注意matlab的版本适配问题,遗传用到矩阵运算好多, 2017a和以下版本交换代码时似乎矩阵加减法都会有玄学问题。


<hr/>评论也有人叫我可以好物推荐这个书,我是很认可这个书的,大家可以先从图书馆借回来再看看是否符合自己的实际需求。不需要的可以直接跳到底部hhh
还有司守奎的算法书,才是数学建模的核心,编程队员需要熟悉每一个问题的特征以及其MATLAB的解法:
我学Matlab的那个书,这个可能比较适合通信的同学,因为有一部分是仿真的,大家看看就好hh
对不起,好物分享上瘾, 最后安利一个我一直用的眼贴吧,确实能缓解一些疲劳,但效果也因人而异(撸代码撸久了可以贴一下,感觉度数增长确实有所缓解)
<hr/>我的另一些关于数模的回答。
<a href="http://www.zhihu.com/question/345203110/answer/821933193" data-draft-node="block" data-draft-type="link-card" data-image="http://pic4.zhimg.com/v2-192d670084479ab32e83920147ec7a33_720w.jpg" data-image-width="1627" data-image-height="1220" class="internal">如何评价2019年全国大学生数学建模竞赛?
数学建模省奖很多么?
美赛S奖保研有用吗?
页: [1] 2 3
查看完整版本: 有一些超级难的算法比如遗传算法,蚁群算法,看了数学建模国赛感觉好难写,那些人怎么写出来的?