基于云模型的全局最优化算法

收稿日期 : 2006204221 基金项目 : 国家 973计划资助项目 (2004CB719401) ; 国家自然科学基金资助项目 (60496323, 60375016) 作者简介 : 张光卫 (1970 - ) ,男 ,山东济南人 , 博士生 , ezhang@263. net.
第 4期 张光卫等 :基于云模型的全局最优化算法
Zhang Guangwei Kang J ianchu L i Hesong
( School of Computer Science and Technology, Beijing University of Aeronautics and A stronautics, Beijing 100083, China)
本. En代表定性概念的可度量粒度 , 熵越大通常
概念越宏观. 一方面 En 是定性概念随机性的度
量 ,反映了能够代表这个定性概念的云滴的离散
程度 ;另一方面又是定性概念亦此亦彼性的度量 ,
反映了在论域空间可被概念接受的云滴的取值范
围. He是熵的不确定性度量 ,即熵的熵 ,由熵的随
机性和模糊性共同决定. 用 3 个数字特征表示的
1 云模型简介
云模型是定性概念与其数值表示之间的不确 定性转化模型.
定义 1 云和云滴. 设 U 是一个用数值表示 的定量论域 , C是 U 上的定性概念 ,若定量值 x∈ U 是定性概念 C 的一次随机实现 , x 对 C 的确定 度 μ( x) ∈[ 0, 1 ]是有稳定倾向的随机数. μ: U → [ 0, 1 ], Π x∈U, x→μ( x)则 x 在论域 U 上的分布 称为云 ,记为 C ( x,μ) . 每一个 x称为一个云滴 [ 6 ]. 如果概念对应的论域是 n 维空间 ,则可以拓广至 n维云.
定性概念的整体特征记做 C ( Ex, En, He) .
定义 2 一维正态云算子. AForward ( C ( Ex, En,
He) )是一个把定性概念的整体特征变换为定量
表示的 映射 π: C →Π , 满 足条件 : ①Θ = { ti |
N rnd ( En, He)的一次实现 , i = 1, …, N }; ②X = { xi |
定 义 3 进 化 模 式 ( evolving pattern ). EP ( Ex, En, He)是用云模型表达的进化模型. 其中 Ex称为种子个体 ,表达祖先遗传的优良特性 ; En 称为进化熵 ,代表了进化的大概范围 ; He称为进 化超熵表示进化的稳定性 , He越大则不确定性越 强. 进化模式包括一维模式和多维模式 ,多维模式 可用 EP ( Ex1 , En1 , He1 ; …; Exn , Enn , Hen )表示 ,其 中维数 n 为大于等于 1 的整数. 给定父代个体 ( Ex)作为母体 , 指定 En和 He,利用正态云算子 便可以产生任意数量的云滴 ,所有云滴均是该母 体的后代个体 ,所有个体形成一个种群 ,因而进化 模式可以看成是种群的产生模式.
487
进行自适应概率性搜索 、前者消除了解中的不适 应因素 ,后者利用了原有解中的已有知识 ,从而加 速了对优化解的搜索过程.
GA 善长全局搜索 ,然而其局部搜索能力却 明显不足 ,存在易陷入局部最优解和选择压力过 大造成的早熟收敛等问题 [ 3 - 4 ].
云模型是李德毅院士提出的一种定性定量转 换模型 [ 5 - 8 ] ,已经在智能控制 、模糊评测等多个领 域得到应用. 云模型在知识表达时具有不确定中 带有确定性 、稳定之中又有变化的特点 ,体现了自 然界物种进化的基本原理 : 对于云模型 C ( Ex, En, He) , Ex可以代表父代个体遗传的优良特征 , 是子代对父代的继承 , En和 He表示了继承过程 的不确定性和模糊性 ,表现了物种进化过程中的 变异特征. 正态云算子可以完成概念空间到数值 空间的转换 ,一方面这种转换是确定和精确的 ,因 为数值空间的每一个云滴都是定性概念的一次量 化实现 ,都在一定程度上是该定性概念的代表 ;另 一方面 ,这种转换又是随机和模糊的 ,每一次变换 得到不同的云滴集合 ,同一定性概念可用云滴集 合中的任何一个代表 ,而且不同的云滴代表该概 念的确定程度不同.
最重要的研究方向之一. 遗传算法 GA[ 2 - 3 ] ( Genetic A lgorithm )是模仿
自然界生物进化过程提出的计算模型 ,近年来已 经广泛地应用于工程技术领域进行复杂非线性系 统的优化设计 ,以其鲁棒性 、可并行处理性及高效 率在函数优化中得到广泛的应用. GA 结合了达 尔文 (C. R. Darw in)的适者生存生物进化理论和 孟德尔 ( G. M endel)的遗传学机理 ,通过迭代操作
(中国电子工程系统研究所 北京 100840)
摘 要 : 基于云模型在定性概念与其定量数值表示之间转换过程中的优良特性 ,结 合遗传算法的基本思想 ,提出一种自适应高精度快速随机搜索算法 ,并将之运用到函数寻优 中. 在定性知识的指导下该算法能够自适应控制搜索空间的范围 ,较好地避免了传统遗传算法 易陷入局部最优解和选择压力过大造成的早熟收敛等问题. 算法易于实现 ,不存在遗传算法中 的编码问题. 试验结果表明该算法具有精度高 、收敛速度快等优点. 在众多优化问题上有广泛 的应用前景.
关 键 词 : 遗传算法 ; 云模型 ; 最优化 中图分类号 : TP 183 文献标识码 : A 文 章 编 号 : 100125965 (2007) 0420486205
C lo ud m o de l ba se d a lgo rithm fo r g lo ba l op tim iza tio n o f func tio n s
N rnd ( Ex, ti )的一次实现 , ti ∈Θ, i = 1, …, N }; ③Π
= { ( xi , yi )
| xi ∈ X, yi
∈Θ = e , t - ( x i- Ex) 2 / ( 2 t2i ) i
}.
其中 , N rnd (μ,δ)为生成期望为 μ,方差为 δ的正态
随机变量 ; N 为云滴的个数.
定义 4 种群 (population). 在一个进化代 ,由 同一种子个体 ( seed)产生的个体 ( population indi2 vidual)的集合. 种群中所有个体均继承了种子的 优良特征 ,并且相对于种子个体有一定程度的变 化 ;种群中个体的数目称为种群大小 ( population
488
北 京 航 空 航 天 大 学 学 报 2007年
size) ,也称种群规模. 定义 5 群落 ( community). 在一个进化代中
所有种群的集合. 群落中种群的数目称为丰富度 ( abundance degree) ;群落中个体的数目称为群落 大小 ( community size) ,也称群落规模 ; 按照群落 中种群的规模对种群的地位进行划分 ,分为建群 种 、优势种和劣势种 ,其中优势种比劣势种拥有的 个体多 ,建群种为优势种中的最优者.
云模型所表达的概念的整体特性可以用期望 Ex ( Expected value ) , 熵 En ( Entropy) , 超 熵 He (Hyper entropy)这 3 个数字特征来整体表征 ,多 维云模型的整体特征可由多组数字特征表示. Ex 是云滴在论域空间分布的期望 ,是最能够代表定 性概念的点 ,或者说是这个概念量化的最典型样
第200373卷年
第
4月 4期
Baidu Nhomakorabea
北京航空航天大学学报 Journal of Beijing University of Aeronautics and A stronautics
Ap ril 2007 Vol. 33 No14
基于云模型的全局最优化算法
张光卫 康建初 李鹤松
李德毅
(北京航空航天大学 计算机学院 , 北京 100083)
基于云模型的优良特性 ,结合遗传算法的基 本原理本文提出一种自适应高精度快速随机搜索 算法 CBOA (C loud B ased Op tim ization A lgorithm ) , 该算法不但比传统遗传算法精度高 ,而且能够很 好地避免遗传算法易陷入局部最优解和选择压力 过大造成的早熟收敛等问题.
L i Deyi
( China Electronic System Engineering Company, Beijing 100840, China)
Ab s tra c t: Num erical op tim ization of given objective functions is a crucial task in many scientific p rob2 lem s. B ased on the outstanding characteristics of cloud model on the p rocess of transform ing a qualitative con2 cep t to a set of quantitative numerical values, and integrate w ith the basic p rincip le of genetic algorithm , a no2 vel adap tive evolutionary algorithm for continuous global op tim ization p roblem s was p roposed. W ith the instruc2 tions of qualitative know ledge, the extent of searching space is self2adjusted and the possibility of p rem ature and the p robability of trapp ing in local best op tim ization are greatly reduced, so the algorithm can find high ac2 curate numerical solution w ithin a short time. The algorithm avoids the p rocess of coding and crossover so it is easy to be carried out. B y the experiments on typ ical test functions, the p recision, stability and convergence rate were well p roved.
利用正态云算子 ,就可以把定性概念 C ( Ex,
En, He)变换为数值表示的云滴集合 ,实现了概念
空间到数值空间的转换. 一维正态云算子可以拓
广至 n维正态云算子.
2 CBOA
基于云模型的优化算法 ,利用云模型在知识 表示中的特点 ,结合遗传算法的思想 ,用 Ex 代表 父代个体的优良特征 ,用 En和 He表示继承过程 的不确定性和模糊性 ,控制遗传和变异的程度 ,用 正态云算子完成概念空间到数值空间的转换 ,产 生种群 ,实现遗传操作. 首先介绍以下概念.
Ke y wo rd s: genetic algorithm; cloud model; op tim ization
全局最优化问题的研究始于 20世纪 60年代 中期. 数学和计算机科学领域已经提出众多的解 决方法 ,如非线性规划方法 、界限函数法 、网格法 、 B ranin 的轨迹法 、模拟退火算法 、Levy 的隧道法 、 Shubert的序列法 、Ge Renpu 的填充函数法等全 局最优化方法 [ 1 ] ,它们基本可分为确定型方法与 随机型方法两大类 ,但都存在着一定的局限性 ,使 这个问题的研究一直倍受关注 ,成为最优化领域