基于协同进化的异构种群挖掘混沌迭代函数.doc

基于协同进化的异构种群挖掘混沌迭代函数 郑皎凌, 唐常杰1, 徐开阔1, 1 , 杨宁1, 段磊1 1(四川大学 计算机学院 数据库与知识工程研究所,成都 610065)(成都信息工程学院软件工程系　成都　610225) 摘要:混沌迭代序列是复杂系统动力学研究的一个分支,其序列值在不同参数条件下时会出现分叉及混沌现象.已有的方法不能同时挖掘拟合迭代序列的迭代函数的结构及其相应条件参量.本文则旨在同时挖掘出二者,主要工作包括:(1)提出了基于协同进化的异构种群挖掘模型,能融合不同种群的优势;(2)提出了新的适合挖掘迭代序列的适应度计算方式;(3)从理论上证明了多种群协同挖掘的进化难度远大于单种群进化难度,通过实验证实了在有效协同策略下,多种群进化得到的结果远优于单种群的进化结果;(4)提出3种协同进化策略,在对迭代序列的函数拟合以及参数拟合两方面,多路并行式结合策略能达到相对较优效果;(5)在合成数据和真实数据上进行了实验,证实了算法的正确性和有效性. 关键词: 混沌迭代序列, 协同进化模型,挖掘模型,异质种群,种群结合策略 1. 研究背景和目标 1.1混沌现象 混沌是一种确定性的非周期现象,天气,地震,传染病扩散,城市道路交通流量观测数据中都可能呈现出非周期的混沌现象[1~3].挖掘其中规律富有吸引力和挑战性. 观察表明, (1) 混沌虽然是非周期现象,但却是由确定性的系统产生的,其本质是确定性的,有望通过数据挖掘手段将产生混沌的确定性系统挖掘出来.(2) 很多复杂系统的研究认为迭代系统是描述混沌现象的有力工具.例如,今年的天气会影响明年的天气(见实验部分8.2),当前已经被传染的人口数量会影响下一时间被传染的人口数,某城市道路当前的交通流会影响下一时刻的交通流.Sarkovskii定理和Li Yorke定理[4]都指出,对一维迭代映射动力系统,只要有周期3就有混沌.迭代系统在不同的参数条件影响下,会逐渐从稳定的周期状态演变成非周期的混沌状态.例如某些传染病的扩散在不同条件下会出现爆发,缓慢扩散或逐渐消亡的不同状态.又如著名的用于预测生物种群数量的logistic函数x(t)=r*x(t-1)*(1-x(t-1)),在r取不同值时,x(t)会出现从分岔到混沌的过程,如图1. (a) r = 2.6, x(0)=0.1 (b) r = 3.3, x(0)=0.1 (c) r = 3.6, x(0)=0.1 (d) r = 3.9, x(0)=0.1 图1 logistic 序列的分叉混沌现象 Fig1 logistic sequence’s bifurcate and chaotic phenomenon 1.2 挖掘目标 上述分析表明,混沌迭代系统包括为两部分,(1) 确定的迭代规律,(2) 可使系统从稳定走向混沌的调节参数.本文将分规律挖掘和参数挖掘两部分建立模型.下面给出形式化的挖掘目标. (1)一阶n元的耦合迭代序列:设有一组时间序列数据{S1, S2,…, Sn}, Si={xi(0), xi(1),…, xi(T)}(i∈[1,n]),如果任意xi(t) (t∈[0,T])由{ x1(t-1), x2(t-1),…, xn(t-1)}决定,则称{S1, S2,…, Sn}为一阶n元耦合迭代序列. 如气象中温度时间序列,前一年的温度影响下一年的温度,这是以年为迭代时间单位的一阶1元耦合迭代序列(见实验8.2). (2)一阶n元m参量的耦合迭代函数Fn,m:Fn,m是形如(1)式具有n个耦合变元{ x1(t), x2(t),…, xn(t) }和m个参量{r1, r2,…rm}的迭代函数.其中,Fn,m迭代运算n次可以产生一阶n元耦合迭代序列. x1(t+1) = f1(x1(t), x2(t),…, xn(t),r1, r2,…rm); x2(t+1) = f2(x1(t), x2(t),…, xn(t),r1, r2,…rm); ... ... xn(t+1) = f1(x1(t), x2(t),…, xn(t),r1, r2,…rm); (1) (3)挖掘目标:设一组待挖掘的数据是一阶n元耦合迭代序列{S1, S2,…, Sn},Si={xi(0), xi(1),…, xi(T)}(i∈[1,n]),该序列的初值为{ x1(0), x2(0),…, xn(0)}.挖掘目标要找出一个一阶n元m参量的耦合迭代函数Fn,m,使得Fn,m以初值{ x1(0), x2(0),…, xn(0)}进行T次迭代后得到的一阶n元耦合迭代序列{P1, P2,…, Pn}, Pi={yi(0), yi(1),…, yi(T)}(i∈[1,n]),与目标序列拟合程度最高,即使得Fn,