自然计算的数理模型及其算法研究

The mathematical-physical models and designation of their algorithms for Nature Inspired Computation are researched, by using theory and methods of mathematics and physics. Orienting typical problems and applications, their practical models and swarm intelligence evolutionary algorithms are researched and proposed. a) Researches on dynamical models and theory: Making analogy between behavior of evolutionary algorithm and dynamical system, population and particle system, the dynamical models of algorithms and their model-building methods are researched. A general framework of the dynamical models will be researched and proposed. b) Researches on dynamical behavior: Equations of the algorithm dynamical system are built, and then the dynamical behavior of population on run-time algorithms will be analyzed, such as the bifurcation and phase transition. The theory of stability and convergence will be established. c) Researches on population evolution and control strategies: Based on above model and theory, stability and robustness in the evolutionary progress are analyzed and control strategies on population diversity and algorithm convergence are presented to guide the design of practical algorithms. d) Researches on optimal trajectory theory: combined with typical applications, several performance optimization indicators are presented to build optimal performance function. Optimal control model of the algorithm will be set up and the optimal trajectory theory will be analyzed, and then optimal control strategy with practical value will be proposed. e) Application researches: On the one hand, we use the theory and method to analyze and solve the typical problems, and on the other hand, we also, Orienting typical problems and applications, study the new model and algorithm based on the characteristics of the problem and domain knowledge.

运用数学物理方法研究自然计算的数学物理模型及其算法的设计与分析，面向典型问题和应用，提出有针对性的模型和群智能演化算法。（1）动力学模型及理论研究，将演化算法的运行比拟为动力系统，种群比拟为粒子系统，研究其动力系统模型的建模方法和理论，建立算法统一的动力学模型；（2）动力学行为研究，建立算法动力系统的动力学方程，分析算法运行时群体的吸引子和相变等动力学行为，提出算法的稳定性和收敛性理论；（3）群体进化与控制策略研究，基于上述模型和理论，分析群体进化过程中的稳定性与鲁棒性，提出群体多样性和算法收敛性的控制策略，以指导实用算法的设计；（4）最优轨道理论研究，结合典型应用提出若干性能优化指标构建最优性能泛函，建立算法的最优控制模型，分析其最优轨道理论，提出有实用价值的最优控制策略；（5）应用研究，一方面运用上述理论和方法进行典型问题的分析和求解，同时也结合问题特征和领域知识研究新的模型和算法。

本项目研究基于动力系统理论，建立自然智能计算的数理模型。别于已有理论分析方法的随机过程及其马尔科夫链模型，运用确定性的数学物理方法，分析随机性算法求解与进化过程中的确定性行为，以理论分析结果指导算法的设计和改进。以典型的算法和典型问题的求解，对理论模型和理论结果进行实验验证与实验分析。本项目的研究完成了上述目标，建立了四个有价值的自然智能计算的数理模型。首先，从经典的模拟退火算法入手，建立了模拟退火算法的弹性力学模型，证明了算法运行的中前期和中后期两阶段不同的收敛性态；将此模型推广应用于粒子群算法，提出了粒子群算法的PID自适应优化控制模型，改进了粒子群算法的收敛性态和寻优轨迹；进一步建立了模拟退火算法的弛豫时间模型，定量分析了模拟退火算法的时间复杂性，以此模型为基础提出了马尔科夫链长度和退火温度的动态设置方法，以及自适应回火策略；对一类以群体进化为特征的演化算法建立了它们的气体动力学模型（波动模型），模型求解得到了粒子密度分布的波动解，分析粒子密度波的传播行为，以确定性的方法证明了演化算法的收敛性，并以密度波的传播速度定义算法的收敛速度，同时也分析了差分进化算法的相变特征。运用国际上公认的、广泛应用测试集问题，实验验证了上述模型的适用性，理论结果的正确性，特别是对波动模型选取了最典型的遗传算法、粒子群算法和差分进化算法进行了一般性的验证，表明了动力系统模型及其理论分析结果的普适性。自然计算类算法的基本特征是随机性和群体性，自诞生以来对它们的理论分析通常运用随机过程理论，特别是马尔科夫模型，但获得的理论结果是概率性的，不具确定性，限制了理论结果的适用范围，难以应用于指导算法的设计和改进。本项研究变换理论分析视角，以动力系统理论和方法分析随机性算法的确定性行为，理论结果具有较好的普适性，能够用于指导算法的设计和改进，甚至有望基于模型和理论结果设计和发展新的自然智能计算算法。