[科普中国]-文化算法

原理简介

文化算法正是基于此目的来模拟人类社会的演进过程而提出的。通过—个独立于种群空间的信仰空间，来获取和保存并加以整合解决问题的知识，使种群的进化速度超越单纯依靠生物基因遗传的进化速度，具有良好的全局优化性能。

详细内容文化算法由种群空间和信仰空间构成双层进化机制，总体上包括三大元素：种群空间、信仰空间和通信协议。

种群空间从微观的角度模拟生物个体根据一定的行为准则进化的过程，信仰空间从宏观的角度模拟文化的形成、传递和比较等进化过程。

种群空间和信仰空间是两个相对独立的进化过程，但是又相互影响相互促进，两个空间根据通信协议相互联系，对进化信息进行有效提取和管理，并将其用于指导种群空间的进化。文化算法基本框架结构如右图所示。

这个过程使得种群像人类社会推演一样，不仅有生物特征的进化，而且有文化信念作为指导，超越单纯的生物进化，具有目的性和方向性。算法结束后，末代种群中的最优个体经过解码，可以作为问题近似最优解。

文化算法的重要特征是引进了信仰空间，将群体空间中的个体在进化过程中形成的个体经验，通过接受函数传递到信仰空间，信仰空间将收到的个体经验看作一个单独的个体，根据一定的行为规则进行比较优化，形成知识储备，它根据现有的经验和新个体经验的情况更新知识，修改群体空间中个体的进化行为规则, 以使个体空间得到更高的进化效率。

具体作用机理1）初始化一个种群空间p，然后通过目标函数（适应度函数）对种群空间中的个体进行评价；

2）根据目标函数给定的取值范围和初始种群中的候选解，按照信仰空间结构，生成初始信仰空间；

3）根据影响函数influence()，对种群中的每个父个体进行变异，生成相因个数的子个体；

4）对于生成的父、子共2p新中群的每个个体，从中随机选取c个个体与其进行比较，如果该个体适应值优于与其比较的个体则称其获胜一次，记录每个个体获胜次数。选取p个具有最多胜利次数的个体作为下一代的父个体；

5）设定接收函数，更新信仰空间；

6）不满足结束条件，则重复（3）至结束1。

文化算法的特点文化算法具有以下特点：

(1)双重进化继承：在种群空间和信念空间分别继承父代的信息；

(2)种群空间的进化是由信念空间中保存的知识进行引导；

(3)支持种群空间和信念空间的层次结构；

(4)支持两个空间的自适应进化；

(5)不同空间的进化可以按不同的速度进行；

(6)支持不同算法的混合问题求解；

(7)“文化”改变的不同模型可表达于一个模型之内。

文化算法的以上特征决定了其可适用于：种群空间和信念空间按不同速率进化的复杂系统；需采用不同方式的知识表示的问题；结合搜索和知识引导的混合系统；需要多种群及其交互的问题求解；支持多层次种群空间和信念空间并存的多层次结构问题等。

理论发展Reynolds于1994年最先引入文化算法的概念，他指出任何符合文化算法要求的计算构架都能够被用来表示种群空间，如进化规划、进化模式、遗传算法等；不同的符号表示方法都能被用来描述信念空间，如语义网络、逻辑、集合论等。他最初采用遗传算法来模拟微观进化过程，用Mitchell所描述的译本空间(VersionSpaces)来模拟宏观进化过程。随后他和他的学生相继在文化算法领域展开研究，并取得一定成果。

目前国外大部分相关文献均来自于Reynolds和他的学生。Reynolds和Chung于1995年起利用文化算法求解全局优化问题，并取得较好结果。

Chung关注于解决静态无约束实值函数优化，他提出了两种知识类型：环境知识和标准知识，后来它们被认为是划分信念空间的两种最基本的知识类型。

Chung和Reynolds比较了两种知识类型在引导搜索过程中所起到的不同效果：环境知识不适用于高维问题；用标准知识同时决定搜索步长和方向能起到不错的效果，并指出算法的改进取决于知识类型和问题结构。Zannoni和Reya~olds于1996年将遗传规划嵌入文化系统框架(即C )，用于控制规划进化过程(Pm—gram Evolution Process)E引。Shinin Zhu提出模糊文化算法(Rm Fuzzy Cultural Algorithm)，其中包括模糊接受函数、模糊信念空间、模糊知识更新以及模糊影响函数。

1999年Jin和Reynolds提出了一种 维地域模式(regional schema)，称为“知识元”(Bellef—cel1)，将其作为文化算法中的显性机制来对非线性约束知识进行获取、保存和整合，并在Chung的基础上除去环境知识，加入约束知识(constraint knowledge)。

2002年David提出基于GP的双文化算法框架。此外他们还将文化算法用于图像分割、动态优化问题、数据挖掘等。当然除了Reynolds 和他的学生外，还有其他的一些学者也致力于文化算法的研究。CoeUo和Becerra在Jin和Reynolds基础上对一些约束准则作了进一步改进，如信念空间的约束部分每代更新一次，而标准知识每k代更新一次等。

2003年他们首次提出将文化算法用于解决多目标优化问题。Digalakis J G和Margaritis K G提出一种多种群文化算法(a multipopulation cultural algOdthm)——并行协作文化算法(paralld c0一operating cultural algo—rithm)，并将之用于复杂组合优化问题，证实了种群间采用不同的进化行为，以及彼此间的信息交流、共同协作往往能起到不错的效果1 引。N．B．HO和J．C．Tay提出了一种有效的文化算法CENACE，用于灵活作业调度问题(Flexible Job—Shop Scheduling Problem)。

他们用合成调度规则(Composite Dispatching Rules)产生初始种群，采用文化进化体系来维护各代的知识模式和资源分配，信念空间影响可行染色体表示的变异和选择。Cruz，Pacheco等将文化算法算子引入量子进化算法，能够更加可靠地更新算法状态，避免过早收敛于局部最优。同时也改进了结果，保持了算法所需要的特征，如，鲁棒性、快速收敛等l2引。Trung和Xin Yao将文化算法与迭代局部搜索(Iterated Local Search，ILS)结合，提出了一种新的基于种群的构架CA—ILS，用于解决单目标无约束数值优化问题。该算法能够有效地检测问题的结构模式，自适应地改变全局搜索补偿和方向，从而能很快地找到下一个更优解2。

应用1.在不同的种群内可按不同的速度进行进化求解的复杂系统问题；

2.结合搜索和知识引导的混合系统求解问题；

3.需多种群及其交互的求解问题；

4.将不同算法结合利用其各自特性进行混合求解的问题等3。