算法是什么?

算法是处理解决问题的思路及办法,程序语言是按照一定语法把算法表达来。

打个比方,你头脑里有了一套新思想,一个新发现,你可以用中文写出来,也可以用英文写出来,让大家明白。思想和发现可以比作是算法,用中文或英文可以比作是程序语言。

因此核心是算法,但程序语言是实现算法的载体。在计算机等系统中,算法是处理某一问题的思路方法,而程序语言能具体表达算法从而使之运行起来通过算法需要完成的任务。

前提假设:

要实现的这个算法网上能搜到大量的资料,比如算法的思想是什么,使用这个算法的例子(翻书太慢,不够丰富,不推荐)。

1. 给你一个算法,在动手编程之前,你应该把注意力放在哪里?

算法的核心是解决问题的思路和方法,所弄明白一个算法的思路是非常有必要的(当然对于某些教材上的算法给出的步骤详细的不能再详细,不知道思路比着步骤也能编,这里不考虑)。

在用遗传算法解决问题时:

百度搜索遗传算法,比较多见的是百度百科,CSND博客,博客园,知乎,脚本之家的内容,也是我重点关注的搜索结果。前三者的内容相对比较系统,可以从中掌握这个算法的由来,思想,一般步骤。知乎大神的回答一般比较深入浅出,或者站在一个比较高的高度耳目一新,脚本之家给出的代码比较实用,百度知道一些论坛智库里面也会有一些有价值的回答,但是没有前面几个的思想有深度。

这里从百度百科的结果看思想:

理解好这个介绍就完成了一大步(因为具体问题的具体实现不能照搬,只有思想是通用的):从这里理解了遗传算法就是仿真生物种群优胜劣汰的过程,适者生存,不适者淘汰。并且知道了这个算法的解决问题一般步骤是编码,产生初代种群,迭代演化(演化要计算个体适应度,交叉,变异,产生新的个体)

此外还需要理解每个过程都需要实现什么功能:

这里看得出整个算法的关键是构造一个迭代(不懂迭代就理解维循环),迭代的每一步需要计算种群中每个个体的适应度,优胜劣汰种群中的个体,种群中交叉运算,变异运算(是为了生成新的可行解,为寻找到初始种群里之外更好可行解提供了可能)得到新的种群

看懂了思想,知道了每步是干啥的,就可以联系我们要解决的问题思考(思考的方式大致就是要解决的问题有什么?可以对应到算法的那一部分上?这样对应后其他部分要怎么实现?):

要求解的问题是最优化问题,那么个体(染色体)是不是就对应着每个可行解?

适应度是不是对应着目标函数值?

求得了适应度要怎么按照适应度的大小繁殖后代?(用rand函数怎么实现?)

如何实现交叉运算?(不同可行解之间哪些部分可以交换,并且有益于构造出不同的可行解?)

如何实现变异运算?(随机改变某些个体的某些属性的值可以吗?)

对于这些细节有了大致的思路或者模糊的思路就可以开始尝试编写代码了

如果觉得自己的思路太模糊,可以看看别人的例子代码(如果没有理解这些算法的思想,直接看已有的代码,要看懂很困难,当然也可以从里面的循环和分支结构作为突破口,画画流程图,写一写注释,来帮助理解代码),也可以直接上手去编,遇到问题再去网上找解决方案(matlab那么杂,函数那么多,记不住的东西就要善于网上去搜)

2. matlab编程应该熟练哪些知识?

参考另一篇博客哪些知识点是学习matlab应该熟练掌握的?,基本功熟练,才能看到问题有想法思路(能力决定思维)

比如针对这次数学建模第三轮训练——下料问题,假设建立了这样的模型:

可行解(切割方案)是由两个矩阵和两个向量表示的,矩阵A的每一行表示用一根5000mm长的材料切割出50种钢管的数量,由于钢管种类多达50种,如果穷举所有可能切法是困难的,所以矩阵A的行数暂定为200行,矩阵B的每一行表示用一根6000mm长的材料切割出50跟钢管的数量,同样暂定其行数为200行,列向量a的行数同A的行数一样,表示按照每种切割方法切割原材料的根数,列向量b表示按照B的每行的切割方法切割原材料的根数。

目标函数是这种切割方案产生的废料的量。

约束条件是每根原材料够长,切割出每种钢管数目达到需求。

(精力有限,省去数学语言描述)

怎么应用约束条件,是直接根绝约束条件生成可行解,还是随机生成后判断是否满足约束?前者设计困难,后者效率可能非常低下。

编写代码(本例中要遗传的个体比较复杂,就不进行编码解码,直接把80个可行解作为初始种群,相应的代价是交叉和变异不容易):

close all;clear;clc;

AL=5000;BL=6000;

NL=[] % 50种钢管的长度

NN=[] % 50种钢管的数量

%% 初始化,上面的步骤a)

T = 1000; % 迭代1000步

M = 80; % 种群规模

P = []; % 种群

for m=1:M % 初始化种群

P(m)=temp; % 上面需要构造一个合适的方法生成初始可行解,实现较麻烦,

% 我的大致思路是

%% 迭代(迭代包括个体评价,选择,交叉,变异)

for t=1:T % 至多进化T次

%%%%%%%%%% 个体评价,假设已有一个函数score,输入A、B、x、y,返回浪费材料的长度

sc = zeros(1,M);

temp = P(m);

sc(m) = score(temp.A,temp.B,temp.x,temp.y); % 计算得分

% 做一个合适的变换,让浪费材料长度变为得分(适应度),这里简化了

sc = sc-min(sc)/(max(sc) - min(sc));

%%%%%%%%%% 选择,轮盘赌算法,就是让得分对应于轮盘上扇形的宽度

%选择50次,落到哪个扇区,对应的个体就有一个后代

sumsc = sum(sc);

[~,index]=find(sumsc*rand>csum);

if(isempty(index)) index=0;

P(m) = oldP(index+1);

%%%%%%%%%% 交叉运算,这里随机选择30对进行交叉运算,这里假设实现了交叉算子

%across ,输入两个个体,函数交换两个个体里矩阵A,B,x,y里的部分行,列,数据

toex = ceil(M*rand(30,2));

P(toex(i,:)) = across(P(toex(i,:)));% 两两做交叉运算

%%%%%%%%% 变异运算,随机选取几个对象,改变A,B,x,y里的部分数据,

%这里假设已经实现了变异算子variation

toch = ceil(M*rand(10,1));% 假设10个发生变异

P(toch(i)) = variation(toch(i));

% 目前已经按照遗传算法的思想写出了整体骨架,细节有空再完善

请关注我

戳二维码关注