记忆原理的元胞自动机优化算法及其收敛性证明  

Cellular Automata Algorithm for Solving Optimization Problems Based on Memory Principles and its Global Convergence Proof

作　　者：陆秋琴[1] 牛倩倩[1] 黄光球[1] 

机构地区：[1]西安建筑科技大学管理学院,西安710055

出　　处：《计算机科学》2013年第4期249-255,共7页Computer Science

基　　金：陕西省科学技术研究发展计划项目(2011K06-08);陕西省教育厅科技计划项目(12JK0789)资助

摘　　要：为了求解大规模优化问题,根据记忆原理与元胞自动机的特点构造了求解优化问题的全局收敛算法。在该算法中,将优化问题的理论搜索空间划分为离散搜索空间,该空间定义为元胞空间,其中的每个元胞对应着一个候选解。将记忆原理的记忆、遗忘规律用于控制每个元胞的状态转移;元胞的状态由其空间位置、位置修正量以及记忆残留值构成,该值分为瞬时记忆、短时记忆和长时记忆3种状态类型,并依据元胞接受刺激的强度被加强或衰减;记忆残留值低于某个阈值的元胞时被遗忘,不再被处理。在元胞演化过程中,元胞从一个状态转移到另一个状态实现了元胞空间对理论搜索空间的搜索。应用可归约随机矩阵的稳定性条件证明了本算法具有全局收敛性。测试结果表明本算法是高效的。To solve large-scale optimization problems（OP）,the algorithm with global convergence was constructed for solving OP based on the characteristics of memory principles（MP） and cellular automata（CA）.In the algorithm,the theoretical search space of OP is divided into the discrete space,and the discrete space is defined as celullar space where each cell is an alternative solution of OP;the memorizing and forgeting rules of MP are used to control transition of states of each cell;a cellular state consists of position,increment of position and residual memory which is divided into three kinds of memory state such as instantaneous,short and long-term memory,each of which is strengthed or wea-kened by accepted stimulus strength.A cell is forgotted and then discarded when its residual memory is lower than a threshould.During evoluation process,a cell＇s transferring from one state to another realizes the search of cellular space on the theoretical search space.The stability condition of a reducible stochastic matrix was applied to prove the global convergence of the algorithm.The case study shows that the algorithm is efficient.

关 键 词：优化 元胞自动机 记忆原理 全局收敛性 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]