文化基因算法(Memetic Algorithm, MA)是Pablo Moscato提出的建立在模拟文化进化基础上的优化算法,Pablo Moscato 认为,在遗传算法（GA） 中,变异操作可以看作是含有一定噪声的爬山搜索,实际上模拟遗传编码和自然选择的过程不应包含变异操作,因为在文化进化的过程中,在众多的随机变化步骤中得到一个正确的可提高整体性能的一步进展是非常困难的,只有此领域的拥有足够的专业知识的精通者们,才有可能创造新的进展,但是这样的事情发生的频率是很低的。

因此,文化基因的传播过程应是严格复制的,若要发生变异,那么每一步的变异都需要有大量的专业知识支撑,而所有的变异都应带来进展而不是混乱,这就是为什么我们观察到的文化进化速度要比生物进化速度快得多的原因。对应于模拟生物进化过程的遗传算法,Moscato提出了模拟文化进化过程的文化基因算法,文化基因算法用局部启发式搜索来模拟由大量专业知识支撑的变异过程,因此说,文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。

文化基因算法的模型如下：

其中包含的9各要素解释如下：

文化基因算法的一般流程可以描述如下 :

（1）初始解的生成 ,并对初始种群进行局部优化。

（2）随机选择群体中的个体进行交叉 ,并对所生成的子个体进行局部优化 。

（3）随机对群体中的个体进行变异 ,并对生成子个体进行局部优化 。

（4）对群体进行更新 。

（5）判断是否满足终止条件 ,如果满足终止条件就结束 ,否则返回第二步。

详细流程图如下：

文化基因算法的这种全局搜索和局部搜索的结合机制使其搜索效率在某些问题领域比传统遗传算法快几个数量级,可应用于广泛的问题领域并得到满意的结果。很多人将文化基因算法看作混合遗传算法、 遗传局部搜索或是拉马克式进化算法,实际上,文化基因算法提出的是一种框架、 是一个概念,在这个框架下,采用不同的搜索策略可以构成不同的文化基因算法,如全局搜索策略可以采用遗传算法、 进化策略、 进化规划等,局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。

下面给出一个文化基因算法对Rosenbroek函数的测试程序：

函数的matlab表示如下：

function f=Test_Function(X)

D=length(X);

f=0;

for i=1:D-1

f=f+100*(X(i+1)-X(i)^2)^2+(X(i)-1)^2;

end

%------------------------------------------------------------------------

%% memetic算法求解Rosenbroek函数源程序

%------------------------------------------------------------------------

clc;

clear;

tic;

M=20; %染色体个数

P_mutate=0.1;%变异概率

P_cross=0.95;%交叉概率

D=20;%函数的维数

NCmax=20;%迭代次数

Xmax=10;

Xmin=-10;

for i=1:M

for j=1:D

X(i,j)=rand*(Xmax-Xmin)+Xmin;%种群初始化

end

end

for i=1:M

fitness(i)=Test_Function(X(i,:));%计算适应度

end

for NC=1:NCmax

%%杂交

randrow=randperm(M);

s=1;

for i=1:M/2

if rand<=P_cross

w1=rand;w2=rand;

X(M+s,:)=w1*X(randrow(i),:)+(1-w1)*X(randrow(M-i),:);

X(M+s+1,:)=w2*X(randrow(M-i),:)+(1-w2)*X(randrow(i),:);

s=s+2;

end

end

%%变异

s=1;

new_M=size(X,1);

for i=1:new_M

if rand<=P_mutate

if rand<0.5

X(new_M+s,:)=X(i,:)+(Xmax-X(i,:))*(rand*(1-NC/NCmax))^2;

else

X(new_M+s,:)=X(i,1)+(Xmax-X(i,1))*(rand*(1-NC/NCmax))^2;

end

s=s+1;

end

end

%%选择

new_fitness(1:M)=fitness;

for i=M+1:length(X)

new_fitness(i)=Test_Function(X(i,:));

end

[iteration_fitness(NC),flag]=min(new_fitness);

nextX(1,:)=X(flag,:);

nextfitness(1)=new_fitness(flag);

P_select=(1./new_fitness)/sum((1./new_fitness));%计算选择概率

cum_P_select=cumsum(P_select);

for i=2:M

pos=find(cum_P_select>=rand);

nextX(i,:)=X(pos(1),:)

nextfitness(i)=new_fitness(i);

end

X=[];fitness=[];

X=nextX;

fitness=nextfitness;

nextX=[];P_select=[];sum_P_select=[];nextfitness=[];

new_fitness=[];

for i=1:M

[X(i,:),fitness(i)]=fminsearch('Test_Function',X(i,:));

%利用matlab自身的函数进行局部搜索

end

end

toc;

plot(iteration_fitness);

[Best_fitness,flag]=min(fitness);

Best_solution=X(flag,:);

算法的种类有很多，本系列主要针对几种最新的和流行的算法进行简单介绍，后续可能会有更好的系列出现。

感谢关注，有兴趣可以参加讨论。