《(1.5)--第5章 智能计算人工智能导论.ppt》由会员分享，可在线阅读，更多相关《(1.5)--第5章 智能计算人工智能导论.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 智能计算Computational IntelligencePPT模板下载： 目录目录CONTENTS二三粒子群算法遗传算法一智能计算概述一、智能计算概述人工计算智能早已超越人类以科学运算、逻辑处理和等形式化或规则化的运算为核心人工感知智能已取得重大进展以图像识别、语音识别和语言翻译等为代表，趋于实用水平人工认知智能研究难度更大以理解、推理和决策为代表，强调会思考和能决策，综合性更强模拟人“学”人辅助人可以“不以人为师”、从根本超越人的智能。人工智能的三个基本阶段一、智能计算概述受自然界、生物界规律的启迪，人们模仿设计了求解问题的一些算法，统称为智能计算（Computational I
2、ntelligence,CI），是计算智能的重要研究方向。由于广泛应用于优化问题求解中，也称为智能优化。应用领域：组合优化、智能控制、机器学习、规划设计等。进化计算群体智能遗传算法遗传规划进化策略粒子群算法蚁群算法蜂群算法PPT模板下载： 目录目录CONTENTS二三粒子群算法遗传算法一智能计算概述二、遗传算法生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能。遗传算法（Genetic Algorithm，GA）：1975年约翰霍兰德提出，是一类借鉴生物进化规律(适者生存、优胜劣汰）演化而来的随机化搜索方法。约翰霍兰德（1929）霍普金斯大学心理学教
3、授遗传算法之父2.1 算法提出遗传以基因形式包含在染色体内。每个基因有特殊的位置控制某种特殊性质。基因突变、杂交可产生更适合环境的后代。经过自然选择，适应性高的基因结构得以保存。达尔文（18091882）孟德尔（18221884）2.2 生物学基础二、遗传算法（1）达尔文的进化论（适者生存原理）每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。（2）孟德尔的遗传学说（基因遗传原理）二、遗传算法2.2 生物学基础为什么过去的杀虫药现在不好使了呢？适者生存+优胜劣汰基因重组/交叉：在有性繁殖
4、过程中，控制不同性状染色体的基因重新组合；基因突变：染色体的某些基因位的组成或数目发生改变。2.2 生物学基础基因突变基因重组二、遗传算法染色体算法将问题的解表示成染色体（个体），即以一定方式编码的串。执行算法前，给出种群（一群“染色体”），即一组假设解的集合。按照适者生存的原则，选择出较适应环境的染色体进行复制，再通过交叉、变异过程产生更适应环境的新一代种群。重复此过程，逐代进化，搜索到最适应环境的一个染色体，它就是问题的最优解。2.3 算法基本思想二、遗传算法遗传算法模型二、遗传算法2.4 算法基本理论编码/解码种群初始化适应度函数遗传算子对待解决问题的参数（决策变量）进行编码，一般用字符
5、串表示，常用编码机制：二进制编码、实数编码、排列编码等。二、遗传算法1、编码/解码（1）种群中的一条染色体代表一个个体（2）一条染色体代表求解问题的某个假设解，包含多个决策变量的编码，每个决策变量包含多个基因。2.4 算法基本理论（1）变量的编码串长：二、遗传算法1、编码/解码（2）变量的解码：表现型到基因型的解空间变换基因型到表现型的解空间变换2.4 算法基本理论10110110110012二、遗传算法因此，染色体（3个决策变量）共有3*4=12个基因。（2）假设某个染色体初始化为：3决策变量的解码：个体的个体的编号号个体的个体的编码10001100000201011110013000000
6、010141001110100N00010100112、种群初始化将种群中每条染色体（个体）的基因位，按照编码方式初始化成基因型，常用方法：随机初始化。二、遗传算法2.4 算法基本理论编号个体的编码解码适应度值10001100000X1f(X1)20101111001X2f(X2)30000000101X3f(X3)41001110100X4f(X4)N0001010011XNf(XN)二、遗传算法3、适应度函数评估个体优、劣的标准，适应度值越大的个体越优，可以根据求解问题的抽象函数来设计。其中2.4 算法基本理论从父代种群中选择进入下一代种群后续繁殖环节的个体过程，也称为环境选择。常用方法：
7、（1）轮盘赌选择；（2）锦标赛选择；（3）部分替换选择。二、遗传算法4、遗传算子选择操作2.4 算法基本理论（1）轮盘赌选择每次从父代种群中取出一定数量个体，然后选择其中最好的一个进入子代种群。重复直到子代种群规模达到父代种群规模。二、遗传算法依据个体适应度值计算每个个体在下一代中出现的概率，并按此概率随机选择个体构成子代种群。（2）锦标赛选择2.4 算法基本理论二、遗传算法4、遗传算子交叉操作2.4 算法基本理论二、遗传算法4、遗传算子变异操作2.4 算法基本理论种群环境染色体基因适应能力交叉突变进化结束进化过程的新群体适应度函数可行解的编码串一个编码单元解的适应度值交换部分编码某些编码的数
8、值改变算法结束生物进化遗传算法二、遗传算法对应关系2.4 算法基本理论二、遗传算法2.5 算法流程与特点开始（2）初始化种群（3）计算适应度值（4）选择操作（5）交叉操作（6）变异操作输出种群中适应度最优的染色体终止条件YN常用的终止条件：（1）达到最大进化代数；（2）达到最优解的精度；（3）种群的最优个体适应度值或平均适应度连续几代未变。（1）确定编码解码方式结束算法操作简单，易于实现，可以很方便与其他方法混合；对决策变量的编码进行操作，这样提供的参数信息量大，优化效果好；寻优规则由概率决定，是一种高效启发式搜索，而非盲目地穷举或完全随机搜索；通过目标函数来计算适应度值，不需要其他推导和附加
9、信息，应用范围较广；从多点开始并行操作，防止搜索过程收敛于局部最优解，可使用并行计算提高速度。二、遗传算法2.5 算法流程与特点函数：其中二、遗传算法2.6 求解连续优化问题实例二、遗传算法因此，染色体（2个决策变量）共有34个基因。决策变量的编码串长：（1）编码/解码2.6 求解连续优化问题实例二二进制数制数十十进制数制数实数数x10101010100111010143637-1.6707x2000011000100100016289-4.5202二、遗传算法（1）编码/解码2.6 求解连续优化问题实例V1=0101010100111010100001100010010001=x1 x2=-
10、1.6707-4.5202V2=1110101000110111110100010100000111 =x1 x2=4.1492 1.3482V3=0000010000001100110010111101011011 =x1 x2=-4.8418 0.9250V4=1011111000000000110001110111000100 =x1 x2=2.4220 0.5814V5=0011001110100110010010010110110111 =x1 x2=-2.9825 0.7367V6=1000100000010110110011011111001110 =x1 x2=0.3160 1
11、.0900二、遗传算法（2）种群随机初始化2.6 求解连续优化问题实例二、遗传算法（3）适应度评价2.6 求解连续优化问题实例x1=-1.6707 x2=-4.5202eval(V1)=f(-1.6707-4.5202)=0.0413eval(V2)=f(4.1492 1.3482)=0.0499eval(V3)=f(-4.8418 0.9250)=0.0395 最差个体最差个体eval(V4)=f(2.4220 0.5814)=0.1388eval(V5)=f(-2.9825 0.7367)=0.0958eval(V6)=f(0.3160 1.0900)=0.4371 最优个体最优个体根据适
12、应度计算个体在子代中出现的概率，并按照此概率随机选择个体构成子代种群。Step1：计算种群所有个体适应度值的和二、遗传算法（4）轮盘赌选择2.6 求解连续优化问题实例染色体编号适应度值被选择的概率累积概率随机数被选中次数V10.04130.05140.05140.04511V20.04990.06220.11360.05931V30.03950.04930.16290.15331V40.13880.17300.33590.71510V50.09580.11940.45530.82960V60.43710.54471.00000.90803二、遗传算法（4）轮盘赌选择2.6 求解连续优化问题实例
13、轮盘赌选择后的新个体对应的父代个体 V1=0101010100111010100001100010010001V1 V2=1110101000110111110100010100000111V2 V3=0000010000001100110010111101011011V3 V4=1000100000010110110011011111001110V6 V5=1000100000010110110011011111001110V6 V6=1000100000010110110011011111001110V6二、遗传算法（4）轮盘赌选择2.6 求解连续优化问题实例V1=010101010011
14、1010100001100010010001C1=0101010100110111110100010100000111V2=1110101000110111110100010100000111C2=1110101000111010100001100010010001V3=0000010000001100110010111101011011C3=0000010000001100110010111111001110V4=1000100000010110110011011111001110C4=1000100000010110110011011101011011V5=1000100000010110
15、110011011111001110C5=1000100000010110110011011111001110V6=1000100000010110110011011111001110C6=1000100000010110110011011111001110第1次，产生随机数r1=0.0563，V1与V2发生交叉，交叉位是10。第2次，产生随机数r2=0.7630，V3与V4发生交叉，交叉位是24。第3次，产生随机数r3=0.1023，V5与V6发生交叉，交叉位是20。2.6 求解连续优化问题实例二、遗传算法（5)单点交叉：二、遗传算法2.6 求解连续优化问题实例C10.4795,0.2112
16、,0.6046,0.2000,0.7864,0.4355,0.4930,0.6764,0.9703,0.7832,0.6155,0.2972,0.8561,0.7444,0.3343,0.8551,0.3899,0.2378,0.2483,0.7392,0.2981,0.7675,0.1919,0.5573,0.3600,0.4848,0.6593,0.9651,0.7256,0.9852,0.2654,0.9628,0.2115,0.1787C20.1705,0.3740,0.9871,0.9722,0.8194,0.9267,0.9974,0.3591,0.6925,0.2026.0111
17、9,0.2370,0.2998,0.2638,0.7364,0.5979,0.8660,0.7739,0.2837,0.8057,0.4051,0.7009,0.7966,0.5037,0.8998,0.2398,0.4652,0.7505,0.7142,0.2617,0.3158,0.3669,0.8008,0.6568C30.9767,0.1703,0.6626,0.2847,0.7807,0.4558,03321,0.7374,0.4426,0.7403,0.8640,0.9463,0.2724,0.5633,0.5232,0.6391,0.4819,0.8163,0.1805,0.78
18、01,0.4816,0.7578,0.4938,0.4287,0.9972,0.6092,0.1391,0.0319,0.7058,0.9848,0.8015,0.9084,0.6110,0.8132C40.4390,0.5806,0.1810,0.8441,0.8055,0.9856,0.1559,0.5595,0.6848,0.8672,0.8240,0.6724,0.4908,0.2595,0.6514,0.9246,0.4889,0.4986,0.1203,0.9470,0.2721,0.2384,0.1097,0.7979,0.5447,0.4999,0.2775,0.6115,0.
19、2512,0.4159,0.9362,0.2692,0.7177,0.2842C50.7423,0.8637,0.5606,0.9159,0.8616,0.9823,0.6873,0.5757,0.7754,0.9443,0.9703,0.7974,0.8935,0.4618,0.1704,0.3890,0.8807,0.4607,0.1984,0.6290,0.8368,0.4956,0.9418,0.4480,0.5668,0.8297,0.5412,0.6493,0.4509,0.9956,0.5529,0.5675,0.8496,0.1765C60.2755,0.8544,0.1073
20、,0.3425,0.6520,0.7312,0.8116,0.6142,0.0202,0.1891,0.4380,0.8968,0.2547,0.1674,0.2334,0.5292,0.2003,0.3767,0.7010.0.1117,0.7663,0.8332,0.5333,0.7279,0.5884,0.3165,0.4737,0.6106,0.9388,0.9978,0.8399,0.7749,0.6920,0.8387 第9个基因变异第28个基因变异产生的6*34随机数矩阵变异之前的个体变异之后的个体C1=0101010100110111110100010100000111C1=0
21、101010100110111110100010100000111C2=1110101000111010100001100010010001C2=1110101000111010100001100010010001C3=0000010000001100110010111111001110C3=0000010000001100110010111110001110C4=1000100000010110110011011101011011C4=1000100000010110110011011101011011C5=1000100000010110110011011111001110C5=10001
22、00000010110110011011111001110C6=1000100000010110110011011111001110C6=1000100010010110110011011111001110二、遗传算法2.6 求解连续优化问题实例（6)单点变异：第一次迭代运行结束的种群中，最好的个体是V4，最差的个体是V2。V1=C1=0101010100110111110100010100000111,f(-1.6712,1.3482)=0.1782V2=C2=1110101000111010100001100010010001,f(4.1496,-4.5201)=0.0259V3=C3=0
23、000100000011001 10010111110001110,f(-4.8418,0.9288)=0.0395V4=C4=1000100000010110110011011101011011,f(0.3160,1.0812)=0.4408V5=C5=1000100000010110110011011111001110,f(0.3160,1.0900)=0.4371V6=C6=1000100010010110110011011111001110,f(0.3355,1.0900)=0.4347二、遗传算法2.6 求解连续优化问题实例（7)适应度评价：对变异后的种群个体的适应度值重新评价。二、
24、遗传算法实验结果2.6 求解连续优化问题实例（7)终止条件判断：若满足终止条件，则输出最优染色体及适应度值，否则返回（4）继续执行。种群规模N影响算法搜索能力和运行效率，一般设置为20100。N设置较大，搜索空间大，保证群体的多样性，提高算法的搜索能力；但也增加算法计算量，降低运行效率。N设置较小，降低计算量，但也降低了每次进化种群中包含更多较好染色体的能力。编码长度L影响计算量和交叉变异操作的效果。与优化问题密切相关，一般由选择的编码方法决定。二进制编码方法，L根据解的取值范围和规定精度要求选择大小。二、遗传算法2.7 控制参数设置种群规模N编码长度L二、遗传算法2.7 控制参数设置PPT模
25、板下载： 目录目录CONTENTS二三粒子群算法遗传算法一智能计算概述设想场景：一群鸟在随机搜索食物。问题：找到食物的最优策略是什么？小鸟们相互共享位置。每只鸟搜索目前距离食物最近的鸟的周围区域，根据自身飞行的经验并向距离食物最近的鸟靠拢。信息的社会共享三、粒子群算法已知：在这块区域里只有一处食物最多。所有鸟虽然不知道食物在哪，但能感受到当前位置离食物有多远。粒子群算法3.1 算法提出3.1 算法提出三、粒子群算法1995年年，受到鸟群觅食过程中的迁徙和群聚行为的启发，Eberhart等人建立了一个数学简化模型，提出粒子群算法(Particle Swarm Optimization,PSO)。
26、PSO收敛速度快、简单易实现，是一种代表性的群体智能算法，成功应用于很多的领域，比如函数优化、图像处理、电力系统优化、医疗诊断等。Eberhart，电子工程学博士向大自然学习“自然界的蚁群、鸟群、鱼群、羊群、牛群、蜂群等，其实时时刻刻都在给予我们以某种启示，只不过我们常常忽略了大自然对我们的最大恩赐！”一群鸟觅食，初始位置各不相同，沿着各自方向飞行。三、粒子群算法3.2 算法基本思想（1）鸟类觅食举例它们定期分享各自的搜索成果。经过交流，红鸟思考并调整下一步的飞行方向。三、粒子群算法鸟儿们不断交流、调整飞行，最终到达食物最多的地方。3.2 算法基本思想（1）鸟类觅食举例三、粒子群算法首先，每个
27、粒子在搜索空间中搜索个体最优解，将其记为当前个体极值；然后，将个体极值与粒子群里的其他粒子共享，找到群体的最优个体极值，将其作为群体的当前全局最优解；最后，所有粒子根据自己找到的当前个体极值和粒子群共享的当前全局最优解来调整自己的速度和位置。3.2 算法基本思想（2）数学模型抽象信息的社会共享森林食物的量每只鸟所处位置食物量最多位置求解空间目标函数值一个解（粒子位置）全局最优解鸟类觅食粒子群算法对应关系3.2 算法基本思想（2）数学模型抽象粒子群算法基于生物群体之间的“信息共享”机制，来实现在搜索空间对潜在解的寻找，即每个“粒子”在搜索空间内多次搜索，搜索行为在不同程度上受其他粒子的影响，也受
28、其自身经验的影响。假设在D维搜索空间中，有m个粒子。（1）第i个粒子的位置向量表示为：（2）第i个粒子的飞行速度向量表示为：（3）第i个粒子搜索到的个体最优位置为：（4）整个粒子群搜索到的全局最优位置为：三、粒子群算法3.3 算法基本理论（2）粒子速度的更新其中，w为惯性权重，c1和c2为加速因子（两个正常数），rand1和rand2为均匀分布于0,1的随机数。三、粒子群算法（1）粒子位置的更新i=1,2,m，d=1,2,D3.3 算法基本理论三、粒子群算法（2）粒子速度的更新惯性部分：对自身运动状态的信任。认知部分：粒子本身的思考，来源于自身经验。社会部分：粒子间的信息共享，来源于群体中的其
29、他优秀粒子的经验。3.3 算法基本理论参数1：惯性权重w粒子保持运动惯性的速度（依据自身速度进行惯性运动），表示粒子对当前自身运动状态的信任程度。三、粒子群算法（2）粒子速度的更新惯性方向粒子个体最优方向群体最优方向惯性方向粒子个体最优方向群体最优方向粒子新方向粒子新方向惯性速度小的粒子更趋向于跟随种群最优方向，保证算法收敛能力。惯性速度大的粒子更趋向于探索未知空间，有利于跳出局部极值，保证算法探索能力。三、粒子群算法参数1：惯性权重w解决实际优化问题时，可以使用自适应调整策略，即：先使用较大的w全局搜索，搜索空间快速收敛于某一区域，然后使用较小的w局部搜索，以获得高精度的解。（2）粒子速度的
30、更新3.3 算法基本理论三、粒子群算法（2）粒子速度的更新参数2：加速因子c1和c2将粒子推向个体最优位置和群体最优位置的加速权重，表示粒子的动作来源于自己经验的部分和其他粒子经验的部分。3.3 算法基本理论参数3：粒子数，通常一般取2040，对较难或特定类别的问题可以取100200。参数4：最大速度Vmax，决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。三、粒子群算法（2）粒子速度的更新3.3 算法基本理论三、粒子群算法3.4 算法流程与特点算法优点简单易实现、收敛速度快；粒子有记忆功能算法缺点标准粒子群缺乏速度的自适应调节，易陷入局部最优，导致收敛精度低或不收敛；标准粒子群算法不能有效求解离散及组合优化问题参数难以确定，对不同的问题，需选择合适的参数来达到最优效果。三、粒子群算法3.4 算法流程与特点小结：算法提出基本原理算法参数思考：粒子在进行速度更新时，受到哪些因素的影响？三、粒子群算法算法优缺点惯性权重的取值对算法的性能有什么影响？