《北京信息科技大学-优化设计2》由会员分享，可在线阅读，更多相关《北京信息科技大学-优化设计2（93页珍藏版）》请在金锄头文库上搜索。
1、机械工程系 第 4章 机械工程系 主要内容 1.智能优化算法 1.1遗传算法 1.2蚁群算法 1.3粒子群算法 2.多学科优化概述 形成动因、研究概况、目前存在的主要问题 3.多学科综合优化设计体系 4.多学科优化求解 机械工程系 1.智能优化算法 遗传算法（ 1.1） 1.1.1 遗传算法的原理 1.1.2 遗传算法的基本运算 : 选择 ; 交换 ; 变异 1.1.3 遗传算法（ GA）的基本参数 机械工程系 遗传算法简称 GA（ Genetic Algorithm） ， 最早由美国 Michigan大学的 J. Holland教授提出 （ 于上世纪 60-70年代 ， 以 1975年出版的
2、一本著作为代表 ） ,模拟自然界 遗传机制 和 生物进化论 而成的一种并行随机搜索最优化方法 。 遗传算法是以达尔文的自然选择学说为基础发展起来的 。 自然选择学说包括以下三个方面： 机械工程系 （ 1） 遗传：这是生物的普遍特征 ， 亲代把生物信息交给子代 ， 子代总是和亲代具有相同或相似的性状 。 生物有了这个特征 ， 物种才能稳定存在 。 （ 2） 变异：亲代和子代之间以及子代的不同个体之间的差异 ， 称为变异 。 变异是随机发生的 ， 变异的选择和积累是生命多样性的根源 。 （ 3） 生存斗争和适者生存：具有适应性变异的个体被保留下来 ， 不具有适应性变异的个体被淘汰 ， 通过一代代的
3、生存环境的选择作用 ，性状逐渐与祖先有所不同 ， 演变为新的物种 。 机械工程系 1) 遗传算法 GA把问题的解表示成 “ 染色体 ” ； 2) 每次执行和操作一群 “ 染色体 ” ， 也即是假设解 。 3） 把这些假设解置于问题的 “ 环境 ” 中 ， 并按适者生存的 原则 ， 从中选择出较适应环境的 “ 染色体 ” 进行复制 ， 再通过交叉 ， 变异过程产生更适应环境的新一代 “ 染色体 ” 群 。 4） 一代一代地进化 ， 最后收敛到最适应环境的一个 “ 染色 体 ” 上 ， 它就是问题的最优解 。 1.1.1 遗传算法的原理 机械工程系 选择运算 从旧的种群中选择适应度高的染色体，放入
4、 匹配集 （缓冲区），为以后染色体交换、变异，产生新的染色体作准备。 选择方法 适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率： )()( iic xfxfPxi 为种群中第 i个染色体， 1.1.2 遗传算法的基本运算 : 选择 ; 交换 ; 变异 机械工程系 染色体的 适应度和所占的比例 用转轮方法进行选择 举例： 具有 6个染色体的二进制编码、适应度值、 Pc累计 值。 机械工程系 选择具体步骤 1）计算各染色体适应度值 2）累计所有染色体适应度值，记录中间累加值 S 和最后累加值 sum = f(xi) 3）产生一个随机数 N， 0 N
5、sum 4）选择对应中间累加值 S 的染色体进入交换集 5） 重复（ 3）和（ 4），直到获得足够的染色体。 机械工程系 交换操作 方法 :随机选择二个染色体 (双亲染色体 ),随机指定一点或多点 , 进行交换 ,可得二个新的染色体 (子辈染色体 ). 新的子辈染色体 : A 11010001 B 01011110 复制不能创新 ,交换解决染色体的创新 机械工程系 模拟生物在自然界环境变化 ,引起基因的突变。在染色体二进制编码中， 1变成 0；或 0变成 1。 突变产生染色体的多样性，避免进化中早期成熟，陷入局部极值点，突变的概率很低。 变异操作 机械工程系 GA的流程 机械工程系 1.1.3
6、 遗传算法（ GA）的基本参数 种群规模 P: 参与进化的染色体总数 . 代沟 G: 二代之间不相同的染色体数目 ,无重叠 G = 1; 有重叠 0 G 1 选择方法 : 转轮法 ,精英选择法 ,竞争法 . 交换率 : Pc 一般为 60100%. 变异率 : Pm 一般为 0.110% 机械工程系 举例 : 变异概率取 0.001 初始种群和它的适应度值 染色体的交换操纵 机械工程系 有效载荷姿控热控TT&C电源推进结构轨道高度成本运载火箭星蚀期任务分析任务分析0 .10 .1 10 .1 210 .5 550 .10 .210 .460 .1 230 .1 70 .10 .10 .4 37
7、0 .120 .2 180 .18运载火箭0 .10 .1 10 .60 .45电源分析6推进系统0 .0 10 .0 10 .0 30 .2 27结构分析20 .2 69成本分析10 .1 24TT & C13热控估算32姿控系统0 .311有效载荷94321运载火箭电源分析推进系统结构分析成本分析热控估算姿控系统有效载荷任务前后顺序？ 举例 机械工程系 优化中考虑任务单元独立执行时间和反馈概率大小。 交换算子改进：选择一个父代染色体，在染色体中选择一个基因的位置 k，其选择概率为 交换算子和变异算子的改进 1 7 8 2 5 4 3 6 8 4 2 6 3 7 5 1 8 4 2 父染色体
8、 1 父染色体 2 6 3 7 5 1 8 2 4 1 7 5 3 6 1 7 5 3 6 8 4 2 6 3 7 5 1 8 2 4 niikkttp1机械工程系 变异算子改进： 在染色体中选择一个任务单元的位置，将其设置为移动任务。 移动 “ 移动任务 ” 到染色体序列的一个位置，得到新的染色体。 “ 移动任务 ” 的新位置相对于原位置，分为向前和向后，移动的目标位置按照如下规则： 目标插入点在点的概率为： 向后移动到点之后，目标插入点在点的概率为： 确定要进行移动的目标位置的概率后，采用轮盘赌概率选择算法选择目标位置，移动 “ 移动任务 ” ，得到两个新的染色体 mjmkdmjdPmkj
9、 11),(),(mjmkddmjddPnmkj 1m a xm a x),(),(机械工程系 1.2蚁群算法 1.3粒子群算法 智能优化计算 群智能 群智能的概念 群智能算法 3.2 蚁群优化算法原理 3.2.1 蚁群算法的起源 3.2.2 蚁群算法的原理分析 3.2.3 蚂蚁系统的模型与实现 3.2.4 蚂蚁系统的参数设置和基本属性 3.3 粒子群算法的基本原理 3.3.1 粒子群算法的提出 3.3.2 粒子群算法的原理描述 3.3.3 基本粒子群算法描述 3.3.4 参数分析 3.3.5 与遗传算法的比较 智能优化计算 1.分类 按照单元之间的交互形式，将复杂产品 /系统分为： 集体式（
10、蜂群式）、合作式、协作式。 复杂工程产品 /系统分类 协作式合作式 集体式目标类型是否意识到其他实体有意识 无意识共享个人 协作式合作式 集体式目标类型是否意识到其他实体有意识 无意识共享个人蜂群式交互：实体具有局部环境下感知相关信息的能力，所有实体使用简单动作协议或命令规则，实体之间的通讯需求大大减少，并且能导致所要的系统涌现行为。 合作式交互：实体能感知其它实体存在，有共享目标。例如多个机器人一起完成扫地工作。 协作式交互：实体能感知其它实体存在，每个实体有自己的目标，它们之间还有共享目标，实体间互相帮助以获得各自的、协调的目标。例如卫星设计，有通讯、结构、姿控等多个单元（异构单元），每个
11、成员专攻一项以获得自己的目标，同时帮助团队获得更广阔目标。 蜂群式系统协作式系统同构单元异构单元复杂系统 单元实体是独立的、自治的； 单元实体具有简单的行为； 单元实体没有集中控制，是分布式； 单元实体的行为是随意的； 单元实体共享信息，局部交互 ； 计划和执行同时进行，系统是实时的 ； 个别单元实体的退出，不会影响系统性能 ； 单元之间可互相感知 ， 它们的动作能对队友的目标有帮助； 实体互相帮助以获得各自的、协调的目标 ； 强调实体单元的智能和自治，可以有集中控制蜂群式系统协作式系统同构单元异构单元复杂系统单元实体是独立的、自治的；单元实体具有简单的行为；单元实体没有集中控制，是分布式；单
12、元实体的行为是随意的；单元实体共享信息，局部交互 ；计划和执行同时进行，系统是实时的 ；个别单元实体的退出，不会影响系统性能 ；单元实体是独立的、自治的；单元实体具有简单的行为；单元实体没有集中控制，是分布式；单元实体的行为是随意的；单元实体共享信息，局部交互 ；计划和执行同时进行，系统是实时的 ；个别单元实体的退出，不会影响系统性能 ；单元之间可互相感知 ， 它们的动作能对队友的目标有帮助；实体互相帮助以获得各自的、协调的目标 ；强调实体单元的智能和自治，可以有集中控制智能优化计算 群集智能（ Swarm Intelligence, SI ） 人们把群居昆虫的集体行为称作 “ 群智能 ” （
13、 “ 群体智能 ” 、“ 群集智能 ” 、 “ 集群智能 ” 等） 特点 个体的行为很简单，但当它们一起协同工作时，却能够 突现 出非常复杂（智能）的行为特征。 智能优化计算 描述 群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。 特性 指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。 优点 灵活性：群体可以适应随时变化的环境； 稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。 典型算法 蚁群算法（蚂蚁觅食） 粒子
14、群算法（鸟群捕食） 群 智 能 算 法 智能优化计算 智能优化计算 蚁群的自组织行为 “ 双桥实验 ” ：通过遗留在来往路径上的信息素（ Pheromone）的挥发性化学物质来进行通信和协调。 1.2.1 蚁群算法的起源 1.2蚁群优化算法原理 食物 食物 蚂蚁群 另一个实验 食物 食物 蚂蚁群 智能优化计算 提出蚁群系统 1992年，意大利学者 M. Dorigo在其博士论文中提出蚂蚁系统（ Ant System）。 近年来， M. Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术 蚁群优化（ ant colony optimization, ACO）。 1.2.1 蚁群算法的起源 1.2蚁群优化算法原理 蚂蚁从 A点出发，随机选择路线 ABD或 ACD。经过 9个时间单位时：走 ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到 C点。 1.2.2 蚁群算法的原理分析 1.2蚁群优化算法原理 智能优化计算 蚁巢 食物 经过 18个时间单位时：走 ABD的蚂蚁到达终点后得到食物又返回了起点 A
