《不确定性人工智能》课程教学云进化与函数最优解

1、1云 进 化 计 算Evolutionary Computing Based on the Cloud Model不确定性人工智能课件之十五2人工智能沿着演绎的思路，在符号数学的道路上走了50年，研究的是人造的智能还是自然界生命的智能？为什么不可以从生物学受到启示，模拟自然智能，创造进化算法，研究人工生命？质 疑：3从复杂系统的角度看进化 自然选择是生命进化的重要途径:在生存斗争中,优胜劣汰,适者生存。生物进化过程中存在偏好依附现象,而不是纯随机的选择，这才导致了强者越强,弱者越弱。*3序 言4云进化算法一、进化计算二、重温正态云的数学性质三、云进化算法的设计与实现四、云进化算法的性能评测5一

2、、 进 化 计 算6进化计算的思想生物进化的本质是优化给定环境约束和初始条件，通过选择可以得到与最优解尽可能接近的表现型。环境持续不断地变化，物种跟随环境变化，不断地向一个新的更优解进化。模拟自然进化，计算科学者提出了各种进化计算的方法。67遗传算法早期的遗传算法, 通过在个体之间随机交配，达到优化目的。忽略了种群的整体遗传特征 8现代综合进化论思想进化的基本单位是种群，而不是个体进化是群体中基因频率变化的结果精确研究种群基因频率由一代到下一代的变化，阐述自然选择的作用 89基础概念基因频率特定基因的统计结果占总体样本的比例进化可以反映成基因频率的变换进化知识种群中个体基因的分布情况选择压力外

3、界环境施加于生物体的进化压力，可改变生物的进化取向10进化是基因频率的变动过程在理想群体中，基因频率或基因型频率逐代将保持不变 哈迪-温伯格（Hardy-Weinberg）法则(1908年) 11进化知识进化知识的表示的两个关键:遗传。 基因分布的凝聚特征 ，也可称作偏好依附特征，决定了种群演化的方向变异。基因分布的离散特征 ，决定了种群个体的多样性云进化算法中把“种群中个体基因的分布情况”定义为一种进化知识。 1112选择压力(Selection pressure)外界环境施加于生物体的进化压力，可改变生物的进化方向选择压力过小：进化缓慢, 算法中表现为搜索缓慢，难以收敛选择压力过大：种群早

4、熟, 算法中会导致搜索的过早终止 13进化算法的两种不收敛情况：以进化规划算法为例：如果算法使用了过小的变异算子标准差，造成选择压力过大，导致种群陷入局部极值不能自拔，因此求解精度无法满足需要，称为早熟收敛。如果算法使用了过大的变异算子标准差，种群中的某些个体虽然已达到了全局最优解所在的邻域，但是这些个体的变异强度是如此地大，以至于个体与全局最优解间的距离始终不能足够地小，因此求解精度不能满足需要，导致不能收敛。14反馈调整自适应进化系统作用于形成进化过程阶段性进化成果进化知识选择压力 选择压力影响进化过程,产生阶段性进化成果以阶段进化成果为反馈动态调整进化知识种群基因分布的凝聚和离散程度发生

5、变化影响选择压力15二、重温正态云的数学性质16正态密度分布函数随方差的变化曲线17 如果一个概念缺少共识，反映其数字特征的超熵会变得很大，这个概念的定量云滴群离散成为雾，云的整体轮廓不再清晰可见。尽管雾化过程中，云滴整体上趋于离散，但始终可保持云滴在靠近中心部分占优势。18正态分布正态分布广泛存在于自然现象、社会现象、以及生产活动之中中心极限定理阐述了满足正态分布的条件，是正态分布普适性的理论基础。 1819泛正态分布许多随机现象不能用正态分布描述如果决定随机现象的因素单独作用不是均匀地小，某些因素之间存在相互依赖，那么就不符合正态分布的产生条件，不构成严格的正态分布，或者只能用正态分布来近

6、似处理。 1920云的正态形态 当云的超熵He=0时，所有云滴都落在高斯曲线上，云退化为正态分布，称He=0为云的正态。从这个意义上说，正态分布是云的特例. 2021超熵变大的过程当He逐渐增大的时候，云滴开始离散，云滴的凝聚性变差了22云滴分布规律根据云发生器的实现算法, 因为：PEn-3HeEnEn/3时云图的变化随着He的继续增大，内外轮廓曲线趋向重合 2425云进化算法思路：使用云模型表示进化知识，期望表示种子，熵表示遗传过程中的变化通过超熵的变化改变选择压力，或者促进遗传，或者诱导变异通过种群基因频率的变化产生新个体26通过实验方式验证云模型适合表示进化知识既凝聚又离散的特点进化知识

7、就是“种群中个体基因的分布情况”进化知识具有凝聚特征-体现遗传，决定了种群演化的方向进化知识具有离散特征-体现变异，决定了种群个体基因的多样性27实 验 思 路以期望为中心,选择不同的范围，如： 0.618En,1En, 2En, 3En,考察落在该范围内外的云滴分布情况考察定量论域U的宽度,以及云滴在整个论域上的分布情况28实验设计：*28初始化Ex=Ex0=0,En=En0=1,He=He0=0，Count = 0正向正态云发生器生成1000个云滴C(Ex,En,He)统计指标变化He: He=He + 0.01En0He20En0Count1000求出四个指标的平均值，Count+结束云

8、滴分布随超熵变化云模型对进化知识表示的适用性29实验设计：*29初始化Ex=Ex0=0,En=En0=1,He=He0=0，Count = 0正向正态云发生器生成1000个云滴C(Ex,En,He)统计指标变化En: En=En + 0.01En0En20En0Count0增大个体凝聚程度减小He减小EnEn=En/K(K1)查表确定求精操作如果原He的值小于查表所得值，则以原He为准，否则以查表所得值为准。61进化策略局部求变连续平凡进化代数 local增加遗传粒度减小子代个体产生的凝聚程度 放大He放大EnEn=En*L(L global种群进行重新初始化不通过优选的方法产生种子个体熵可取

9、为精英个体的方差取历史跨代精英个体的平均值突变操作取历史当代精英个体的平均值超熵取为He=nEn突变的发生概率较低，通过种群淘汰的策略就可以避免连续平凡代数过大的情况63精英个体（种子）选择策略种群统一选择策略：从所有种群中选择精英个体，然后把精英个体分配到各个种群做种子收敛速度快无形中进行了种群淘汰，容易早熟种群独立选择策略：从每个种群中选择精英个体并作为该种群下一个进化代的种子 能够很好地保证个体的多样性收敛速度慢64种群淘汰算法在进化到一定程度之后，每隔一定的进化代就要按比例进行一次种群淘汰被淘汰的种群将从其它的种群中选择优秀个体，作为该种群的种子意义防止种群陷入局部最优充分保证“发达”

10、地区的领先地位65种群的初始化对一个种群来说，如果待优化问题的变化范围为min,max，那么期望取其中间值，熵取(max-min)/2，超熵取4倍的熵。超熵的初始值较大是为了保证搜索区间的合理性,因为第一代总能找到最优值。66云进化算法流程框图*6667算法性能评测68算法评价方法为了较好反映算法本身的特征和实际应用能力，同时便于不同领域的研究人员互相理解和交流，研究人员专门设计了具有复杂数学特征的纯数学函数这些函数在设计时已经考虑了实际问题数学模型中可能呈现的数学特征和可能遇到的各种情况和影响因素69Ackley函数f = Ackley 函数可以是任意维数首先考虑最直观的二维Ackley函数

11、-32.768 xi 32.768,i = 1,2,3n70二维Ackley函数图形*70整体形态局部放大71云进化算法流程框图*7172算法初始化整个群落：1000（每一维1000个云滴）1000云滴分为10组（10个种群）subgroups1000 = 300,200,150,50,50,50,50,50,50,50;群落向量初始值：X1i = rand(1) * (32.768 + 32.768 )- 32.768 X2i = rand(1) * (32.768 + 32.768 ) - 32.768X1和X2均为1000维的向量73第一次计算将X1和X2中对应的x1和x2组成一个自变量

12、对，代入Ackley函数，计算函数值取计算结果中极小值的Top10（精英）以Top10为种子，利用正向云算法生成1000个云滴。Enx1 = (maxx1-minx1)/6; Hex1 = 0.05*Enx174第二次计算x1和x2代入函数后，计算新的结果。if 较上代优秀 /非平凡进化代En与He减半继续以新的Top10生成云滴else /平凡进化代不调整En与He继续以新的Top10生成云滴75第N次计算连续的出现非平凡进化代减小En与He，坚决求精连续的出现平凡进化代增大He，局部求变出现跨代精英，求变成功无果，放弃当前结果，定性突变，X1与X2重新初始化N达到规定的最大值输出最优结果7

13、61,5,10次计算结果云滴的散落范围（坐标系）分别为(-40,40),(-30,30),(-1,1)7720,40,80次计算结果云滴的散落范围（坐标系）分别为(-0.12,0.12),(-10-5, 10-5),(-10-9, 10-9)78低维函数(10)全局搜索能力79实验设置群落规模500，群落丰富度10，群落中种群的规模为150，100，75，25 ，25， 25， 25，25 25，25适应度函数取为目标函数fitness= f1进化代数20局部求变阈值local=2定性突变阈值global=10 ，进化系数K=10,种子选择策略均采用种群统一策略变异概率和交叉概率均为0不使用种

14、群淘汰策略。80收敛曲线81CBEA与PSO对比82高维函数全局搜索能力测试83高维实验参数设置84高维函数全局搜索能力比较OGA/Q (IEEE Trans. on Evolutionary Computing, 2001)An Orthogonal Genetic Algorithm with Quantization for Global Numerical Optimization ,IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 5, NO. 1, FEBRUARY 2001OEA (组织进化数值优化算法)西交大博士论文,200

15、4StGA (改进遗传算法)A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization ,IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 8, NO. 5, OCTOBER 2004CLPSO(全面学习粒子群算法)Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION,2006FEP（快速进化规划）Evolutionary Programming Made Faster, IEEE TRANSACTIO