动态环境下文化算法研究

Memetic algorithm (MA) has a double evolutionary structure which combines gene evolution with cultural evolution. The double evolutionary structure makes MA present better performance over traditional evolutionary algorithms, there are a lot of successful optimization instances of using MA to solve complicated optimization problems. Nevertheless, it is well established that depending on the property and complexity of a problem, a strategy of MA that may have proven to give performance advantage on a particular class of problems can only be achieved by accepting a tradeoff in performance degradation on other classes of problems, so a key drawback of MA is that in order for it to be useful on a certain problem instance, one often needs to carry out extensive tuning of the control parameters and to try different memes. Another drawback of MA is that MA's cultural model is only a simple mimic of human social evolution, and it may not solve some complicated optimization problems under dynamic environment.. In order to find the methods of adaptively selecting control parameters and strategies for MA, this project plans to estimate the difficulty of optimization problem by construing the analysis formula of objective function and analyzing the information obtained from evolutionary procedure based on optimum attractor theory. The mathematical model of dynamic environment will be established, including changing frequency, intensity, predictability and detecting method of dynamic environment. Also the mechanism of interaction between MA and dynamic environment will be discussed. How to maintain the diversity of genetic population and memes under dynamic environment will be researched based on the above mechanism. Formation, diffuseness, differentiation, integration, conflict and extinction of memes will be studied. Further, the characters of time domain and zone domain will be attached to memes of MA, the culture evolutionary model will be built up by further imitating the aggregation action of human society and the development procedure of human cities. Those novel proposals, which are inspired by models of adaptation in natural systems that combine the evolutionary adaptation of a population with individual learning within the lifetimes of its members, may obviously improve the universality of MA, may expand the application areas for MA and improve the ability for MA to fit to the change of dynamic environment. The theoretical framework for memetic algorithms under dynamic environment will be set up in this project and it has very important significance for both the theoretical research and the application of memetic algorithms.

文化算法采用种群空间与信度空间双层进化结构，具有比传统进化计算更好的性能，但现有的文化算法缺乏较好的通用性，其模型仅是对人类社会进化的简单模拟，还不能有效解决动态环境下的复杂优化问题。本项目拟研究建立根据目标函数解析式估计求解问题难度方法，并采用最优吸引子理论分析进化过程估计求解问题优化特征因子，在此基础上建立自适应选择文化算法控制参数和控制策略的方法。研究建立动态环境模型，建立文化算法与动态环境的相互作用机制，研究建立在动态环境下的进化过程中保持遗传群体的基因多样性和文化的多样性的方法。建立具有进化群体时域和地域特征的文化形成、扩散、整合、冲突、消亡机制，并通过模拟人类社会部落聚居和城市发展过程，进一步完善文化进化模型。以此提高文化算法通用性，拓展其应用范围，并提高文化算法适应动态环境变化的能力，建立动态环境下文化算法的理论框架。

本项目以动态环境下的文化算法为主要研究对象，通过对动态优化问题求解困难度进行分析，建立能够根据问题难度自适应选择文化算法控制参数和控制策略的方法，解决已有的文化算法缺乏较好通用性的问题。项目的主要研究内容包括：1）研究进化算法困难度模型，对已有的典型方法进行综述与分析；研究最优吸引子理论，并提出优化问题的探索、利用有效比指标，用于度量优化问题困难度。2）研究动态环境下优化难度对探索与利用平衡的影响，提出有效高频分量占比、梯度依赖性、问题频率特性等困难性指标，通过正交实验的方法研究动态环境下的探索与利用平衡理论，并以困难性为知识信息提出基于问题优化难度的文化算法。3）对文化算法的种群空间与信念空间进行研究。研究种群空间的空间拓扑结构与演化规则，提出基于密度制约的文化算法用于解决不同复杂度的动态优化问题；研究多层信念空间策略，文化集的构成与融合，研究文化算法与动态环境的相互作用机制。4）通过多种策略实现动态环境下文化算法的多样性保持，建立基于映射矩阵的多物种进化机制，并研究不同物种之间的捕食、共生等协同机制；在探索与利用平衡研究的基础上，研究灾变的强度和范围与动态优化问题困难度的相互关系。5）建立元胞空间中文化扩散与信息传递机制，研究文化区的划分机制、文化整合机制。提出一种新的由当前种群最优个体及其所在区域、当前个体共同确定的对偶知识，通过对偶知识实现不同文化区域内进化信息的交互与传递。6）通过将文化算法应用于图像处理、模式识别等复杂优化问题求解，验证和进一步完善动态环境下文化算法，建立动态环境下文化算法的应用示例，包括：无人机动态实时航迹规划问题、动态图像序列基于光流场的三维场景重建问题、复杂断口图像的阈值分割问题等。