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

Presentation on theme: "牛 奔 生物启发式优化方法 及其在管理中的应用"— Presentation transcript:

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

2 报告内容 启发式优化方法研究背景 生物启发式优化方法 群体智能优化方法（SI） SI算法在管理中的应用 实例研究

3 报告内容 1 启发式计算方法研究背景 2 生物启发式计算方法 3 群体智能优化方法（SI） 4 SI算法在管理中的应用 5 实例研究

4 启发式计算方法背景 实际生活中的优化问题 最优化问题模型 全局最优与局部最优

5 经典的计算方法 17世纪Newtown 微积分 1847年 Cauchy 最速下降法 1939年 Kantorovich下料问题和运输问题
问题求解 1947年 Dantzig 单纯形方法

6 启发式计算方法 【定义1-1】 启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例的一个可行解，该可行解与最优解的偏离程度未必可事先估计。 【定义1-2】 启发式算法是一种技术，该技术使得能在可接受的计算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。 经典的启发式方法基本原理:根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。

7 启发式计算方法分类 物理启发式 模拟退火算法 （模拟固体熔化状态下由逐渐冷 却至最终达到结晶状 态的物理过程）
量子计算 （模拟量子态的叠加性和相 干性 以及 量子 比特之间的纠缠性） 社会与文化启发 文化算法 （模拟人类社会的演化过程） 人口迁移算法（模拟人口流动与人口迁移）

8 报告内容 1 启发式计算方法研究背景 2 生物启发式计算方法 3 群体智能优化方法（SI） 4 SI算法在管理中的应用 5 实例研究

9 生物启发式优化方法 遗传算法 神经网络 模糊逻辑 。。。。。 生物启发式计算是指以生物界的各种自然现象或过程
为灵感，而提出的一系列启发式智能计算方法。 遗传算法 神经网络 模糊逻辑 。。。。。

10 遗传算法 生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过” “优胜劣汰”及遗传变异来达到进化（优化）目的的。 遗传算法的思想来源于达尔文的自然进化论和孟德尔、摩根的群体遗传学说，由美国Michigan大学的John Holland教授于1975年提出。 遗传算法的核心思想：求解问题时，将问题的求解过程视为染色体适者生存的过程，通过染色体一代一代的不断进化（包括选择、交叉、变异等操作），保留优良个体，淘汰劣质个体，最终收敛到“最适应环境”的个体，从而找到问题的最优解或满意解。 进化过程 优化过程

11 遗传算法 生物的进化机制 自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来 杂交
随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体 突变 随机改变父代的染色体基因结构，产生新染色体 遗传算法的思想来源于达尔文的自然进化论和孟德尔、摩根的群体遗传学说，由美国Michigan大学的John Holland教授于1975年提出。 遗传算法的核心思想：求解问题时，将问题的求解过程视为染色体适者生存的过程，通过染色体一代一代的不断进化（包括选择、交叉、变异等操作），保留优良个体，淘汰劣质个体，最终收敛到“最适应环境”的个体，从而找到问题的最优解或满意解。

12 神经计算 人工神经网络是由 具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。
树突 突触 轴突 细胞体 人工神经网络是由 具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。 受生物神经系统的启发，人们提出了一种新型的非算法信息处理方法—人工神经网络。 轴突是一根长神经纤维，其主要功能是将神经冲动由胞体传至其它神经元。每个神经元只有一根轴突。 突触：神经元与神经元之间的连接点。它是神经元之间的传递信息关键性结构。可以分为两类：化学性突触和电突触。 神经元之间的信息是通过突触完成的。当神经冲动传至突触前膜时，突触中的神经递质与突触后膜上的相应受体结合，于是 后膜两侧的离子分布发生改变，呈兴奋性或抑制变化。 因为一个神经元通常有许多突触，其中有些是兴奋性的，有些是抑制性的，如果兴奋性突触活动强度总和超过抑制性突触活动强度总和，并达到一定的阈值，就能使使该神经元的轴突起始发生动作电位，产生神经冲动。出现神经冲动时则该神经元呈现兴奋，反之则表现为抑制。 神经元的每个突触的活动强度用一个固定的实数即权值模拟。 1943 年，心理学家 McCulloch 和数学家 Pitts提出的神经元二元阈值单元(Binary threshold unit)，即著名的 M-P 模型[15]。该模型的基本思想是：神经细胞的工作方式是兴奋或者是抑制。基于这个思想，McCulloch 和 Pitts在神经元模型中引入了硬极限函数。MP模型是一种静态的模型，结构固定，权值无法调节，缺乏学习能力。

13 神经计算 IN x>T？ I1 I2 I3 S 受生物神经系统的启发，人们提出了一种新型的非算法信息处理方法—人工神经网络。 轴突是一根长神经纤维，其主要功能是将神经冲动由胞体传至其它神经元。每个神经元只有一根轴突。 突触：神经元与神经元之间的连接点。它是神经元之间的传递信息关键性结构。可以分为两类：化学性突触和电突触。 神经元之间的信息是通过突触完成的。当神经冲动传至突触前膜时，突触中的神经递质与突触后膜上的相应受体结合，于是 后膜两侧的离子分布发生改变，呈兴奋性或抑制变化。 因为一个神经元通常有许多突触，其中有些是兴奋性的，有些是抑制性的，如果兴奋性突触活动强度总和超过抑制性突触活动强度总和，并达到一定的阈值，就能使使该神经元的轴突起始发生动作电位，产生神经冲动。出现神经冲动时则该神经元呈现兴奋，反之则表现为抑制。 神经元的每个突触的活动强度用一个固定的实数即权值模拟。 1943 年，心理学家 McCulloch 和数学家 Pitts提出的神经元二元阈值单元(Binary threshold unit)，即著名的 M-P 模型[15]。该模型的基本思想是：神经细胞的工作方式是兴奋或者是抑制。基于这个思想，McCulloch 和 Pitts在神经元模型中引入了硬极限函数。MP模型是一种静态的模型，结构固定，权值无法调节，缺乏学习能力。   人工神经网络（Artificial Neural Networks, ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力。

14 模糊逻辑 y 模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。
规则1 是 A1 y 是 B1 去模 糊化 集结器 规则2 y 是 A2 y 是 B2 规则r 是 Ar y 是 Br 模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。 模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数（Membership Functions, MF）；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论 。 模糊性是人类思维和客观事物普遍存在的属性之一。 美国加州大学Zadch博士于1965年发表了关于模糊集的论文，首次提出了表达 事物模糊性的重要概念一隶属函数，开创了模糊计算这一新的研究领域。 模糊推理系统是建立在模糊集合理论、模糊IF-THEN规则和模糊推理等概念基础上的先进的计算框架。 模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数(Membership Functions, MF)；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论。模糊推理系统在很多场合需要得到精确的输出，特别是用作控制器的情况，这时模糊推理系统实现从输入到输出之间的非线性映射。这个映射是由一组模糊规则基来完成的，其中，每个规则描述映射的局部行为。特别地，规则的前件定义了输入空间中的模糊区域，而后件规定了模糊区域中的输出。

15 其它生物启发式计算技术 进化规划算法 进化编程 人工免疫系统 DNA计算 膜计算等

16 报告内容 1 启发式计算方法研究背景 2 生物启发式计算方法 3 群体智能优化方法（SI） 4 SI算法在管理中的应用 5 实例研究

17 群体智能（Swarm Intelligence）
生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。

18 A C

19 A C

20 A C

21 蚂蚁算法 ij = 1/dij 轨迹更新: Visibility: 表示轨迹的相对重要性 表示能见度的相对重要性 轨迹的持久性
表示第K只蚂蚁在本次循环中留在路径ij上的信息量

22 鱼群觅食模型 生物社会学家E.O.Wilson指出：“至少从理论上，在搜索食物过程中群体中个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。”

23 鸟群的飞行行为 避免碰撞 速度匹配 中心聚集 生物学家Heppner等人开展了对鸟群趋同性行为的深入研究。
鸟群的同步飞行这个整体的行为只是建立在每只鸟对周围的局部感知上面，而且并不存在一个集中的控制者。 也就是说整个群体组织起来但却没有一个组织者，群体之间相互协调却没有一个协调者。 避免碰撞 速度匹配 中心聚集

24 鸟群觅食模型 Food Global Best Solution Past Best Solution
为了说明PSO算法的基本原理，设想如下的场景：一群鸟在随机搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是他们可以判断自己当前的位置离食物的距离。 研究表明：最简单有效的就是搜寻目前离食物最近的鸟的周围区域，利用搜索过程中离食物最近鸟的经验及自身的经验，整个鸟群便很容易找到食物的位置所在。 Past Best Solution

25 Randomly searching foods
社会型行为的模拟 Randomly searching foods

26 认知行为 （Cognition Behavior）
先前经验 Max 6 2

27 社会行为 （Social Behavior）
We tend to adjust our beliefs and attitudes to conform with those of our social peers. ２ １ Max ５ 人类社会系统

28 粒子群算法介绍 每个寻优的问题解都被想像成一支鸟，也称为“Particle”。
所有的Particle 都有一个fitness function 以判断目前的位置之好坏， 每一个Particle具有记忆性，能记得所搜寻到最佳位置。 每一个Particle 还有一个速度以决定飞行的距离与方向。

29 速度与位置更新 PBest gBest My best position pi x(t) The best position of team
Study Factor 局部 最优解 My best position PBest 全局 最优解 pi 运动向量 x(t) The best position of team pg Here I am! x(t+1) 惯性向量 gBest v

30 算法流程 Initialization ：将群族做初始化，以随机的方式求出每一Particle 之初始位置与速度。
Evaluation：依据fitness function 计算出其fitness value 以作为判断每一个Particle之好坏。 Find Pbest ：找出每一个Particle 到目前为止的搜寻过程中最佳解，这个最佳解称之为Pbest。 Find the Gbest：找出所有群体中的最佳解，此最佳解称之为Gbest。 Update the Velocity and position： 根据速度与位置公式 更新每一Particle的速度与位置。 Termination. 返回步骤2继续执行，直到获得一个令人满意的结果或符合终止条件为止。

31 参数选择 粒子数: 一般取 20 – 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200 粒子的维数: 这是由优化问题决定, 就是问题解的长度 粒子的范围: 由优化问题决定,每一维可是设定不同的范围 Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度 学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间 中止条件: 最大循环数以及最小错误要求.

32 PSO与遗传算法的比较 相同点 都是基于种群的 都需要适应度函数. 都是随机计算技术 不能保证100%收敛 不同点
粒子具有记忆能力 优点 PSO 容易实现具有较小的调整参数 收敛速度快、解质量高、鲁棒性好

33 Schwefel's function

34 初始状态

35 5代后

36 10代后

37 15代后

38 100代后

39 500代后

40 最终结果 迭代次数 搜寻结果 5 10 15 20 100 5000 最优解

41

42

43

44 报告内容 1 启发式计算方法研究背景 2 生物启发式计算方法 3 群体智能优化方法（SI） 4 SI算法在管理中的应用 5 实例研究

45 SI算法在管理中应用 SI算法提供了一种求解复杂系统优化间题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是SI的一些主要应用领域： (1) 管理领域的组合优化问题 随着问题规模的增大，组合优化问题的搜索空间也急剧扩 大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上，而SI算法是寻求这种满意解的最佳工具之一。实践证明，SI算法对于组合优化中的NP完全问题非常有效。 例如，SI已经在求解旅行商问题、背包问题、装箱问题、指派问题等方面得到成功的应用。

46 SI算法在管理中应用 （2）物流与供应链管理中应用
物流与供应链管理中，在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。 而目前在现实管理中也主要是靠一些经验来进行管理。现在群体智能算法已成为复杂问题的有效工具，在生产计划调度、运输问题、车辆路径调度问题、物流配送管理问题，多级库存优化控制策略，供应链需求预测优化模型研究，都得到了有效的应用.

47 SI算法在管理中应用 (3) 知识管理中的应用
(3) 知识管理中的应用 知识管理是企业为实现其管理目标，运用现代的管理理论和技术，对企业内部和外部知识资源进行发现，挖掘，整理，整合，并实施科学的管理和维护，将最合理的知识在最恰当的时候提供给最需要的人，以便做出最科学的决策。 目前基于群体思想的方法应用于知识管理的主要方向有：客户关系管理中的客户行为聚类分析，关联分析， 文档分类，属性约简.

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

49 报告内容 1 启发式计算方法研究背景 2 生物启发式计算方法 3 群体智能优化方法（SI） 4 SI算法在管理中的应用 5 实例研究

50 配送中心选址问题 配送中心是将取货，集货，包装，仓库，装卸，分货，配货，加工，信息服务，送货等多种服务功能融为一体的物流据点。
配送中心是进行物流配活动的最主要的硬件设施，所有的物流活动都是基于配送中心这个平台来进行的，它是供应链中非常重要的节点。配送中心的定位几乎决定 配送业务所需要的成本和费用水平。 本例研究的是多配送中心选址

51 配送中心选址问题 物流配送总费用 从配送中心 到需求点 的单位费用 从配送中心 到需求点 运输量 在点 设置配送中心的固定费用及管理费用等
从配送中心 到需求点 的单位费用 从配送中心 到需求点 运输量 在点 设置配送中心的固定费用及管理费用等 需求点 的需求量 配送中心 的容量 可兴建配送中心的最多个数

52 配送中心选址模型

53 配送中心选址模型

54 粒子的编码 物流配送选址问题主要是在一系列需求点中确定配送中心的最佳位置，目标是使各项费用总和最小。因此对于每个需求点而言，就有两个问题 是不是配送中心 隶属于哪个配送中心。 需求点号： 需求点隶属情况： 2： 4： 5：

55 约束处理

56 算法流程 初始化 一群鸟，每个鸟位置向量X的每一维随机取（1-m）（配送中心数）之间的实数，每个速度向量V的每一维随机取-(m-1),(m-1)之间的整数 对每个鸟进行整数规范化，计算其适应度值，将初始评价值作为个体历史最优解，并寻找全局最优值 位置与速度的更新 对X进行整数规范化，再更新个体与全局最好值 得到终终止条件，则返回

57 实例研究 现有一个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个单位。需求点的间距见下表

58 需求点费用表 1 2 3 4 5 6 7 8 9 10 11 12 15 14 13 16

59 最优解的进化

60 最终求解结果 配送中心 需求点 供应量 1 2 3 4 5 6 7 8 9 10 11 12 13 需求量 合计39

61 Thank you for your listening!