生物启发式优化方法及其在管理中的应用

1、1 报告内容报告内容 v启发式优化方法研究背景启发式优化方法研究背景 v生物启发式优化方法生物启发式优化方法 v群体智能优化方法（群体智能优化方法（SI） vSI算法在管理中的应用算法在管理中的应用 v实例研究实例研究 2 报告内容报告内容 启发式计算方法研究背景启发式计算方法研究背景 生物启发式计算方法生物启发式计算方法 群体智能优化方法（群体智能优化方法（SI） SI算法在管理中的应用算法在管理中的应用 实例研究实例研究 3 v最优化问题模型最优化问题模型 启发式计算方法背景启发式计算方法背景 min( )f x .( ) 0 ( ) 00 i i stg x h x 或 v全局最优与局部

2、最优全局最优与局部最优 D xSR v实际生活中的优化问题实际生活中的优化问题 4 经典的计算方法经典的计算方法 v17世纪世纪Newtown 微积分微积分 v1847年年 Cauchy 最速下降法最速下降法 v1947年年 Dantzig 单纯形方法单纯形方法 v1939年年 Kantorovich下料问题和运输问题下料问题和运输问题 问题求解问题求解 5 启发式计算方法启发式计算方法 【定义定义1-11-1】 启发式算法是一种基于直观或经验构造的算启发式算法是一种基于直观或经验构造的算 法，在可接受的耗费（指计算时间、占用空间等）下给出待法，在可接受的耗费（指计算时间、占用空间等）下给出待

3、 解决优化问题每一实例的一个可行解，该可行解与最优解的解决优化问题每一实例的一个可行解，该可行解与最优解的 偏离程度未必可事先估计。偏离程度未必可事先估计。 【定义定义1-21-2】 启发式算法是一种技术，该技术使得能在可启发式算法是一种技术，该技术使得能在可 接受的计算费用内去寻找尽可能好的解，但不一定能保证所接受的计算费用内去寻找尽可能好的解，但不一定能保证所 得解的可行性和最优性，甚至在多数情况下，无法描述所得得解的可行性和最优性，甚至在多数情况下，无法描述所得 解与最优解的近似程度。解与最优解的近似程度。 经典的启发式方法基本原理经典的启发式方法基本原理: :根据问题的部分已知信息来启

4、发式根据问题的部分已知信息来启发式 地探索该问题的解决方案，在探索解决方案的过程中将发现的地探索该问题的解决方案，在探索解决方案的过程中将发现的 有关信息记录下来，不断积累和分析，并根据越来越丰富的已有关信息记录下来，不断积累和分析，并根据越来越丰富的已 知信息来指导下一步的动作并修正以前的步骤，从而获得在整知信息来指导下一步的动作并修正以前的步骤，从而获得在整 体上较好的解决方案。体上较好的解决方案。 6 启发式计算方法分类启发式计算方法分类 v物理启发式物理启发式 模拟退火算法模拟退火算法 （模拟固体熔化状态下由逐渐冷模拟固体熔化状态下由逐渐冷 却至最终达到结晶状却至最终达到结晶状 态的物

5、理过程态的物理过程） 量子计算量子计算 （模拟量子态的叠加性和相模拟量子态的叠加性和相 干性干性 以以 及及 量子量子 比特之间的纠缠性）比特之间的纠缠性） v社会与文化启发社会与文化启发 文化算法文化算法 （模拟人类社会的演化过程模拟人类社会的演化过程） 人口迁移算法（人口迁移算法（模拟人口流动与人口迁移模拟人口流动与人口迁移） 7 报告内容报告内容 启发式计算方法研究背景启发式计算方法研究背景 生物启发式计算方法生物启发式计算方法 群体智能优化方法（群体智能优化方法（SI） SI算法在管理中的应用算法在管理中的应用 实例研究实例研究 生物启发式优化方法生物启发式优化方法 v遗传算法遗传算法

6、 v神经网络神经网络 v模糊逻辑模糊逻辑 v。 生物启发式计算是指以生物界的各种自然现象或过程生物启发式计算是指以生物界的各种自然现象或过程 为灵感，而提出的一系列启发式智能计算方法。为灵感，而提出的一系列启发式智能计算方法。 9 遗传算法遗传算法 进化过程进化过程优化过程优化过程 生物进化过程是一个自然， 并行，稳健的优化过程，这 一优化过程的目的在于使生 命体达到适应环境的最佳结 构与效果，而生物种群通过” “优胜劣汰”及遗传变异来 达到进化（优化）目的的。 10 遗传算法遗传算法 + + + = = 生物的进化机制生物的进化机制 u自然选择自然选择 适应环境的个体具有更 高的生存能力，同

7、时染 色体特征被保留下来 u杂交杂交 随机组合来自父代的染 色体上的遗传物质，产 生不同于它们父代的染 色体 u突变突变 随机改变父代的染色体 基因结构，产生新染色 体 11 神经计算神经计算 树突树突 突触突触 轴突轴突 细胞体细胞体 人工神经网络是由 具有 适应性的简单单元组成的 广泛并行互连的网络，它 的组织能够模拟生物神经 系统对真实世界物体所作 出的交互反应。 细胞体 突 触 轴突 树 突 图12.2 生物神经元功能模型 输 入 输 出 信息处理 电脉冲 形成 传输 12 神经计算神经计算 人工神经网络（人工神经网络（Artificial Neural Networks, ANN），

8、一种模范动 物神经网络行为特征，进行分布式并行信息处理的算法数学模型。 这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连 接的关系，从而达到处理信息的目的。人工神经网络具有自学习和 自适应的能力。 IN 1 N jj j xwI xT？ 1 w 2 w 3 w 4 w I1 I2 I3 S 13 模糊逻辑模糊逻辑 是 A1 x 集 结 器 去 模 糊 化 y 规则规则1 1 x y 是 B1 y 是 B2 y 是 Br 是 A2 x 是 Ar x 规则规则2 规则规则r 模糊推理系统是建立在模糊集合理论、模糊if-then规则和模 糊推理等概念基础上的先进的计算框架。 模糊推理系统的

9、基本结构由三个重要部件组成：一个规则库， 包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶 属度函数（Membership Functions, MF）；以及一个推理机制， 按照规则和所给事实执行推理过程求得合理的输出或结论 。 14 其它生物启发式计算技术其它生物启发式计算技术 v进化规划算法进化规划算法 v进化编程进化编程 v人工免疫系统人工免疫系统 vDNA计算计算 v膜计算等膜计算等 15 报告内容报告内容 启发式计算方法研究背景启发式计算方法研究背景 生物启发式计算方法生物启发式计算方法 群体智能优化方法（群体智能优化方法（SI） SI算法在管理中的应用算法在管理中的应用 实例

10、研究实例研究 群体智能（群体智能（Swarm Intelligence） 生物学家研究表明：在这些群居生物中虽然每个个体生物学家研究表明：在这些群居生物中虽然每个个体 的智能不高，行为简单，也不存在集中的指挥，但由的智能不高，行为简单，也不存在集中的指挥，但由 这些单个个体组成的群体，似乎在某种内在规律的作这些单个个体组成的群体，似乎在某种内在规律的作 用下，却表现出异常复杂而有序的群体行为。用下，却表现出异常复杂而有序的群体行为。 17 A C 18 A C 19 A C 20 otherwise 0 allowed if )( allowed )( )( j tp j ijij ijij

11、t t k ij ),()()( ij ntttnt ijij 轨迹更新: Visibility: ij = 1/dij 蚂蚁算法蚂蚁算法 表示轨迹的相对重要性 表示能见度的相对重要性 轨迹的持久性 ij 表示第K只蚂蚁在本次循环中留在路径ij上的信息量 21 生物社会学家生物社会学家E.O.Wilson指出：指出：“至少从理论上，在搜索食至少从理论上，在搜索食 物过程中群体中个体成员可以得益于所有其他成员的发现物过程中群体中个体成员可以得益于所有其他成员的发现 和先前的经历。当食物源不可预测地零星分布时，这种协和先前的经历。当食物源不可预测地零星分布时，这种协 作带来的优势是决定性的，远大于

12、对食物的竞争带来的劣作带来的优势是决定性的，远大于对食物的竞争带来的劣 势。势。” 鱼鱼群群觅食模型觅食模型 22 v 避免碰撞避免碰撞 v 速度速度匹配匹配 v 中心中心聚集聚集 鸟群的飞行行为鸟群的飞行行为 23 鸟鸟群群觅食模型觅食模型 Food Global Best Solution Past Best Solution 24 Randomly searching foods 社会型行为的模拟社会型行为的模拟 25 认知行为认知行为 o 先前经验先前经验 2 6 Max 26 社会行为社会行为 o We tend to adjust our beliefs and attitudes

13、 to conform with those of our social peers. Max 人类社会系统 27 粒子群算法介绍 v 每每个寻优的问题个寻优的问题解都被想像成一解都被想像成一支鸟支鸟，也，也称称 为为“Particle”。 v 所有的所有的Particle 都有一都有一个个fitness function 以以 判断判断目前的位置之好目前的位置之好坏坏， v 每一每一个个Particle具有记忆具有记忆性，能性，能记记得所搜得所搜寻寻 到最佳位置。到最佳位置。 v 每一每一个个Particle 还还有一有一个个速度以速度以决定飞决定飞行的行的 距离与距离与方向。方向。 28

14、局部局部 最最优优解解 全全局局 最最优优解解 运动向量 惯性向量 12 X = X ,X ,.,X iiiid 12 V = V ,V ,.,V iiiid 12 (1)( )( )( )() ()() () ididididgdid ttttvvc randpxcrandpx (1)( )( ) iii tttxxv Here I am! The best position of team My best position x(t) pg pi v PBest gBest x(t+1) 速度与位置更新速度与位置更新 29 算法流程 v Initialization ：将群族做初始化，以随机

15、的方式求出每 一Particle 之初始位置与速度。 v Evaluation：依据fitness function 计算出其fitness value 以作为判断每一个Particle之好坏。 v Find Pbest ：找出每一个Particle 到目前为止的搜寻过 程中最佳解，这个最佳解称之为Pbest。 v Find the Gbest：找出所有群体中的最佳解，此最佳解 称之为Gbest。 v Update the Velocity and position：根据速度与位置公 式 更新每一Particle的速度与位置。 v Termination. 返回步骤2继续执行，直到获得一个令人

16、 满意的结果或符合终止条件为止。 30 参数选择 v 粒子数粒子数: 一般取一般取 20 40. 其实对于大部分的问题其实对于大部分的问题10个粒子个粒子 已经足够可以取得好的结果已经足够可以取得好的结果, 不过对于比较难的问题或不过对于比较难的问题或 者特定类别的问题者特定类别的问题, 粒子数可以取到粒子数可以取到100 或或 200 v 粒子的维数粒子的维数: 这是由优化问题决定这是由优化问题决定, 就是问题解的长度就是问题解的长度 v 粒子的范围粒子的范围: 由优化问题决定由优化问题决定,每一维可是设定不同的范每一维可是设定不同的范 围围 v Vmax: 最大速度最大速度,决定粒子在一个

17、循环中最大的移动距离决定粒子在一个循环中最大的移动距离, 通常设定为粒子的范围宽度通常设定为粒子的范围宽度 v 学习因子学习因子: c1 和和 c2 通常等于通常等于 2. 不过在文献中也有其他不过在文献中也有其他 的取值的取值. 但是一般但是一般 c1 等于等于 c2 并且范围在并且范围在0和和4之间之间 v 中止条件中止条件: 最大循环数以及最小错误要求最大循环数以及最小错误要求. 31 PSO与与遗传算法遗传算法的的比较比较 o 相同点相同点 n 都都是是基基于于种种群群的的 n 都都需要需要适应适应度度函函数数. n 都都是是随随机机计算技术计算技术 n 不不能能保保证证100%收敛收

18、敛 o 不不同同点点 n PSO没有交叉变异等进化操作没有交叉变异等进化操作 . n PSO中中通过粒子的竞争与协作实现种群进化通过粒子的竞争与协作实现种群进化 n 粒粒子子具具有有记记忆忆能力能力 o 优点优点 n PSO 容容易易实现实现具具有有较较小的小的调整调整参参数数 n 收收敛敛速度速度快快、解质量高、鲁棒性好、解质量高、鲁棒性好 32 Schwefels function n :1=i 420.9687,= 418.9829;=)( maximum global 500500 where )sin()()( 1 i i n i ii x nxf x xxxf 33 初始状态 34

19、 5代后 35 10代后 36 15代后 37 100代后 38 500代后 39 最终结果 迭代次数搜寻结果 0416.245599 5515.748796 10759.404006 15793.732019 20834.813763 100837.911535 5000837.965771 最优解837.9658 400 450 500 550 600 650 700 750 800 850 14166425610244096 sample.dat 40 ) 1(exp() 3/ 1 ( )exp()5/(10) 1(exp()1 ( 3Maximize 2 2 2 1 2 2 2 1 5

20、 2 3 11 2 2 2 1 2 1 xx xxxxxxxxz 41 42 43 报告内容报告内容 启发式计算方法研究背景启发式计算方法研究背景 生物启发式计算方法生物启发式计算方法 群体智能优化方法（群体智能优化方法（SI） SI算法在管理中的应用算法在管理中的应用 实例研究实例研究 44 SI算法提供了一种求解复杂系统优化间题的通用框架，它不算法提供了一种求解复杂系统优化间题的通用框架，它不 依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广 泛应用于很多学科。下面是泛应用于很多学科。下面是SI的一些主要应用领域：的一些主要应

21、用领域： 随着问题规模的增大，组合优化问题的搜索空间也急剧扩随着问题规模的增大，组合优化问题的搜索空间也急剧扩 大，大， 有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最 优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其 满意解上，而满意解上，而SI算法是寻求这种满意解的最佳工具之一。实践证算法是寻求这种满意解的最佳工具之一。实践证 明，明，SI算法对于组合优化中的算法对于组合优化中的NP完全问题非常有效。完全问题非常有效。 例如，例如，SI已经在求解旅行商问题、背包

22、问题、装箱问题、指派已经在求解旅行商问题、背包问题、装箱问题、指派 问题等方面得到成功的应用。问题等方面得到成功的应用。 SI算法在管理中应用算法在管理中应用 45 物流与供应链管理中，在很多情况下所建立起来的数物流与供应链管理中，在很多情况下所建立起来的数 学模型难以精确求解，即使经过一些简化之后可以进行求学模型难以精确求解，即使经过一些简化之后可以进行求 解，也会因简化得太多而使得求解结果与实际相差甚远。解，也会因简化得太多而使得求解结果与实际相差甚远。 而目前在现实管理中也主要是靠一些经验来进行管理。而目前在现实管理中也主要是靠一些经验来进行管理。 现在群体智能算法已成为复杂问题的有效工

23、具，在生产计现在群体智能算法已成为复杂问题的有效工具，在生产计 划调度、运输问题、车辆路径调度问题、物流配送管理问划调度、运输问题、车辆路径调度问题、物流配送管理问 题，多级库存优化控制策略，供应链需求预测优化模型研题，多级库存优化控制策略，供应链需求预测优化模型研 究，都得到了有效的应用究，都得到了有效的应用. . SI算法在管理中应用算法在管理中应用 46 知识管理中的应用知识管理中的应用 知识管理是企业为实现其管理目标，运用现代的管理理论知识管理是企业为实现其管理目标，运用现代的管理理论 和技术，对企业内部和外部知识资源进行发现，挖掘，整理，和技术，对企业内部和外部知识资源进行发现，挖掘

24、，整理， 整合，并实施科学的管理和维护，将最合理的知识在最恰当的整合，并实施科学的管理和维护，将最合理的知识在最恰当的 时候提供给最需要的人，以便做出最科学的决策。时候提供给最需要的人，以便做出最科学的决策。 目前基于群体思想的方法应用于知识管理的主要方向有：目前基于群体思想的方法应用于知识管理的主要方向有： 客户关系管理中的客户行为聚类分析，关联分析，客户关系管理中的客户行为聚类分析，关联分析， 文档分类，文档分类， 属性约简属性约简. . SI算法在管理中应用算法在管理中应用 47 项目管理项目管理 项目管理网络计划中的工期限定项目管理网络计划中的工期限定- -资源均衡问题资源均衡问题 项

25、目合作伙伴的选择问题项目合作伙伴的选择问题 风险管理风险管理 传统的风险管理大都是凭借主观经验，采用定性的判断方传统的风险管理大都是凭借主观经验，采用定性的判断方 法，大多数情况下只考虑信用风险最低而忽略投资投资组法，大多数情况下只考虑信用风险最低而忽略投资投资组 合理论在此过程中的重要。研究如何在各种复杂的、不确合理论在此过程中的重要。研究如何在各种复杂的、不确 定的环境中对资产进行有效的配置，实现资产的回报最大定的环境中对资产进行有效的配置，实现资产的回报最大 化与所承担风险的最小化的均衡，将是化与所承担风险的最小化的均衡，将是SISI应用研究的一个应用研究的一个 重要方向。重要方向。 S

26、I算法在管理中应用算法在管理中应用 48 报告内容报告内容 启发式计算方法研究背景启发式计算方法研究背景 生物启发式计算方法生物启发式计算方法 群体智能优化方法（群体智能优化方法（SI） SI算法在管理中的应用算法在管理中的应用 实例研究实例研究 49 配送中心选址问题配送中心选址问题 配送中心是将取货，集货，包装，仓库，装卸，分货，配货，配送中心是将取货，集货，包装，仓库，装卸，分货，配货， 加工，信息服务，送货等多种服务功能融为一体的物流据点。加工，信息服务，送货等多种服务功能融为一体的物流据点。 配送中心是进行物流配活动的最主要的硬件设施，所有的配送中心是进行物流配活动的最主要的硬件设施

27、，所有的 物流活动都是基于配送中心这个平台来进行的，它是供应链中物流活动都是基于配送中心这个平台来进行的，它是供应链中 非常重要的节点。配送中心的定位几乎决定非常重要的节点。配送中心的定位几乎决定 配送业务所需要配送业务所需要 的成本和费用水平。的成本和费用水平。 本例研究的是多配送中心选址本例研究的是多配送中心选址 50 配送中心选址问题配送中心选址问题 111 m in mnn ijijjj ijj Uh XF Z U 物流配送总费用 ij h 从配送中心 到需求点 的单位费用ij 从配送中心 到需求点 运输量ij ij X j F 在点 设置配送中心的固定费用及管理费用等j j d 需求

28、点 的需求量j i M 可兴建配送中心的最多个数 i P 配送中心 的容量 51 配送中心选址模型配送中心选址模型 1 1,2, n ijj i Xdjn 1 1, 2, n iji j XMim 0 1,2,;1,2, ij Xim jn 52 配送中心选址模型配送中心选址模型 1, 0, j j Z j 被选为配送中心 被不选为配送中心 1 ;1,2, n j j ZP jn 53 粒子的编码粒子的编码 物流配送选址问题主要是在一系列需求点中确 定配送中心的最佳位置，目标是使各项费用总 和最小。因此对于每个需求点而言，就有两个 问题 是不是配送中心 隶属于哪个配送中心。 需求点号：1 2

29、3 4 5 6 7 0 1 0 2 3 0 0 3 1 2 2 3 2 1 2： 2 7 4： 3 4 6 5： 1 5 需求点隶属情况： 54 约束处理约束处理 111 11 min max(,0) mnn ijijjj ijj mn iji ij Uh XF Z RXM 55 算法流程算法流程 1. 初始化 一群鸟，每个鸟位置向量X的每一维随机 取（1-m）（配送中心数）之间的实数，每个速 度向量V的每一维随机取-(m-1),(m-1)之间的整数 2. 对每个鸟进行整数规范化，计算其适应度值， 将初始评价值作为个体历史最优解，并寻找全 局最优值 3. 位置与速度的更新 4. 对X进行整数规

30、范化，再更新个体与全局最好值 5. 得到终终止条件，则返回 56 实例研究实例研究 现有一个12需求点的物流网络，要求从中选择 出3个作为配送中心，使各项费用总和最小。已 知在和建设配送中心的固定费用分别为 11，16，14，14，15，13，18，12，11，14，16， 11个单位，合配送中心的容量均为13个单位，各 点的需求量分别为5，4，2，3，2，4，3，5，4， 3，2，2个单位。需求点的间距见下表 57 需求点费用表需求点费用表 123456789101112 1016743466989 210565457710910 3650369101212151415 4763031011

31、1313161512 54563078101013129 634910706491066 745101186029549 86712131042010627 967121310991004813 1091015161310564049 11891415126428405 129101512969713950 58 最优解的进化最优解的进化 59 最终求解结果最终求解结果 配送 中心 需求点供应量 1 23 4 5 6 7 8 9 10 11 12 152 4213 242 3413 83 53213 需求 量 5 42 3 2 4 3 5 4 322合计39 60 61 经典的计算方法经典的计

32、算方法 v17世纪世纪Newtown 微积分微积分 v1847年年 Cauchy 最速下降法最速下降法 v1947年年 Dantzig 单纯形方法单纯形方法 v1939年年 Kantorovich下料问题和运输问题下料问题和运输问题 问题求解问题求解 生物启发式优化方法生物启发式优化方法 v遗传算法遗传算法 v神经网络神经网络 v模糊逻辑模糊逻辑 v。 生物启发式计算是指以生物界的各种自然现象或过程生物启发式计算是指以生物界的各种自然现象或过程 为灵感，而提出的一系列启发式智能计算方法。为灵感，而提出的一系列启发式智能计算方法。 63 A C 64 参数选择 v 粒子数粒子数: 一般取一般取 20 40