基于群体智能的数据挖掘-方法及应用课件.ppt
生物启发式优化方法生物启发式优化方法及其在管理中的应用及其在管理中的应用牛 奔Email:报告内容报告内容v启发式优化方法研究背景启发式优化方法研究背景v生物启发式优化方法生物启发式优化方法v群体智能优化方法（群体智能优化方法（SI）vSI算法在管理中的应用算法在管理中的应用v实例研究实例研究2报告内容报告内容1 1启发式计算方法研究背景启发式计算方法研究背景2 2生物启发式计算方法生物启发式计算方法3 3群体智能优化方法（群体智能优化方法（SI）4 4SI算法在管理中的应用算法在管理中的应用5 5实例研究实例研究3v最优化问题模型最优化问题模型启发式计算方法背景启发式计算方法背景v全局最优与局部最优全局最优与局部最优 v实际生活中的优化问题实际生活中的优化问题4经典的计算方法经典的计算方法v17世纪世纪Newtown 微积分微积分v1847年年 Cauchy 最速下降法最速下降法v1947年年 Dantzig 单纯形方法单纯形方法v1939年年 Kantorovich下料问题和运输问题下料问题和运输问题 问题求解问题求解5启发式计算方法启发式计算方法【定义定义1-11-1】启发式算法是一种基于直观或经验构造的算启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例的一个可行解，该可行解与最优解的解决优化问题每一实例的一个可行解，该可行解与最优解的偏离程度未必可事先估计。偏离程度未必可事先估计。【定义定义1-21-2】启发式算法是一种技术，该技术使得能在可启发式算法是一种技术，该技术使得能在可接受的计算费用内去寻找尽可能好的解，但不一定能保证所接受的计算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。解与最优解的近似程度。经典的启发式方法基本原理经典的启发式方法基本原理:根据问题的部分已知信息来启发式根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。好的解决方案。6启发式计算方法分类启发式计算方法分类v物理启发式物理启发式 模拟退火算法模拟退火算法（模拟固体熔化状态下由逐渐冷模拟固体熔化状态下由逐渐冷 却至最终达到结晶状却至最终达到结晶状 态的物理过程态的物理过程）量子计算量子计算（模拟量子态的叠加性和相模拟量子态的叠加性和相 干性干性 以及以及 量子量子 比特之间的纠缠性）比特之间的纠缠性）v社会与文化启发社会与文化启发 文化算法文化算法 （模拟人类社会的演化过程模拟人类社会的演化过程）人口迁移算法（人口迁移算法（模拟人口流动与人口迁移模拟人口流动与人口迁移）7报告内容报告内容1 1启发式计算方法研究背景启发式计算方法研究背景2 2生物启发式计算方法生物启发式计算方法3 3群体智能优化方法（群体智能优化方法（SI）4 4SI算法在管理中的应用算法在管理中的应用5 5实例研究实例研究8生物启发式优化方法生物启发式优化方法v遗传算法遗传算法v神经网络神经网络v模糊逻辑模糊逻辑v。生物启发式计算是指以生物界的各种自然现象或过程生物启发式计算是指以生物界的各种自然现象或过程为灵感，而提出的一系列启发式智能计算方法。为灵感，而提出的一系列启发式智能计算方法。遗传算法遗传算法进化过程进化过程优化过程优化过程生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过”“优胜劣汰”及遗传变异来达到进化（优化）目的的。10遗传算法遗传算法生物的进化机制生物的进化机制u自然选择自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来u杂交杂交 随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体u突变突变 随机改变父代的染色体基因结构，产生新染色体11神经计算神经计算树突树突 突触突触 轴突轴突 细胞体细胞体人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。12神经计算神经计算人工神经网络（人工神经网络（Artificial Neural Networks,ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力。INxT？I1I2I3S13模糊逻辑模糊逻辑是A1集结器去模糊化y规则规则1 1 y 是B1 y 是B2 y 是Br是A2是Ar规则规则2规则规则r模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数（MembershipFunctions,MF）；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论。14其它生物启发式计算技术其它生物启发式计算技术v进化规划算法进化规划算法v进化编程进化编程v人工免疫系统人工免疫系统vDNA计算计算v膜计算等膜计算等15报告内容报告内容1 1启发式计算方法研究背景启发式计算方法研究背景2 2生物启发式计算方法生物启发式计算方法3 3群体智能优化方法（群体智能优化方法（SI）4 4SI算法在管理中的应用算法在管理中的应用5 5实例研究实例研究16群体智能（群体智能（Swarm Intelligence）生物学家研究表明：在这些群居生物中虽然每个个体生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。用下，却表现出异常复杂而有序的群体行为。AC18AC19AC20轨迹更新:Visibility:ij=1/dij蚂蚁算法蚂蚁算法表示轨迹的相对重要性表示能见度的相对重要性轨迹的持久性表示第K只蚂蚁在本次循环中留在路径ij上的信息量21生物社会学家生物社会学家E.O.Wilson指出：指出：“至少从理论上，在搜索食至少从理论上，在搜索食物过程中群体中个体成员可以得益于所有其他成员的发现和物过程中群体中个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。来的优势是决定性的，远大于对食物的竞争带来的劣势。”鱼鱼群群觅食模型觅食模型22v避免碰撞避免碰撞v速度速度匹配匹配 v中心中心聚集聚集鸟群的飞行行为鸟群的飞行行为23鸟鸟群群觅食模型觅食模型FoodGlobal Best SolutionPast Best Solution24Randomly searching foods社会型行为的模拟社会型行为的模拟25认知行为认知行为（Cognition Behavior）o先前经验先前经验26Max26社会行为社会行为（Social Behavior）oWe tend to adjust our beliefs and attitudes to conform with those of our social peers.Max人类社会系统27粒子群算法介绍 v每每个寻优的问题个寻优的问题解都被想像成一解都被想像成一支鸟支鸟，也，也称称为为“Particle”。v所有的所有的Particle 都有一都有一个个fitness function 以以判断判断目前的位置之好目前的位置之好坏坏，v每一每一个个Particle具有记忆具有记忆性，能性，能记记得所搜得所搜寻寻到最佳位置。到最佳位置。v每一每一个个Particle 还还有一有一个个速度以速度以决定飞决定飞行的行的距离与距离与方向。方向。28局部局部最最优优解解全全局局最最优优解解运动向量惯性向量Study FactorStudy FactorHereIam!ThebestpositionofteamMybestpositionx(t)pgpivPBestgBestx(t+1)速度与位置更新速度与位置更新29算法流程vInitialization：将群族做初始化，以随机的方式求出每一Particle之初始位置与速度。vEvaluation：依据fitnessfunction计算出其fitnessvalue以作为判断每一个Particle之好坏。vFind Pbest：找出每一个Particle到目前为止的搜寻过程中最佳解，这个最佳解称之为Pbest。vFind the Gbest：找出所有群体中的最佳解，此最佳解称之为Gbest。vUpdate the Velocity and position：根据速度与位置公式更新每一Particle的速度与位置。vTermination.返回步骤2继续执行，直到获得一个令人满意的结果或符合终止条件为止。30参数选择v粒子数粒子数:一般取一般取 20 40.其实对于大部分的问题其实对于大部分的问题10个粒子个粒子已经足够可以取得好的结果已经足够可以取得好的结果,不过对于比较难的问题或不过对于比较难的问题或者特定类别的问题者特定类别的问题,粒子数可以取到粒子数可以取到100 或或 200v粒子的维数粒子的维数:这是由优化问题决定这是由优化问题决定,就是问题解的长度就是问题解的长度v粒子的范围粒子的范围:由优化问题决定由优化问题决定,每一维可是设定不同的范每一维可是设定不同的范围围vVmax:最大速度最大速度,决定粒子在一个循环中最大的移动距决定粒子在一个循环中最大的移动距离离,通常设定为粒子的范围宽度通常设定为粒子的范围宽度v学习因子学习因子:c1 和和 c2 通常等于通常等于 2.不过在文献中也有其他的不过在文献中也有其他的取值取值.但是一般但是一般 c1 等于等于 c2 并且范围在并且范围在0和和4之间之间v中止条件中止条件:最大循环数以及最小错误要求最大循环数以及最小错误要求.31PSO与与遗传算法遗传算法的的比较比较o相同点相同点n都都是是基基于于种种群群的的n都都需要需要适应适应度度函函数数.n都都是是随随机机计算技术计算技术 n不不能能保保证证100%收敛收敛o不不同同点点nPSO没有交叉变异等进化操作没有交叉变异等进化操作.nPSO中中通过粒子的竞争与协作实现种群进化通过粒子的竞争与协作实现种群进化n粒粒子子具具有有记记忆忆能力能力 o优点优点nPSO 容容易易实现实现具具有有较较小的小的调整调整参参数数n收收敛敛速度速度快快、解质量高、鲁棒性好、解质量高、鲁棒性好 32Schwefels function 33初始状态345代后3510代后3615代后37100代后38500代后39最终结果迭代次数搜寻结果0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771最优解837.965840414243报告内容报告内容1 1启发式计算方法研究背景启发式计算方法研究背景2 2生物启发式计算方法生物启发式计算方法3 3群体智能优化方法（群体智能优化方法（SI）4 4SI算法在管理中的应用算法在管理中的应用5 5实例研究实例研究44 SI算法提供了一种求解复杂系统优化间题的通用框架，它不算法提供了一种求解复杂系统优化间题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科泛应用于很多学科。下面是下面是SI的一些主要应用领域：的一些主要应用领域：(1)(1)管理领域的组合优化问题管理领域的组合优化问题管理领域的组合优化问题管理领域的组合优化问题 随着问题规模的增大，组合优化问题的搜索空间也急剧扩随着问题规模的增大，组合优化问题的搜索空间也急剧扩 大，大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上满意解上，而而SI算法是寻求这种满意解的最佳工具之一。实践证算法是寻求这种满意解的最佳工具之一。实践证明，明，SI算法对于组合优化中的算法对于组合优化中的NP完全问题非常有效。完全问题非常有效。例如，例如，SI已经在求解旅行商问题、背包问题、装箱问题、指派已经在求解旅行商问题、背包问题、装箱问题、指派问题等方面得到成功的应用。问题等方面得到成功的应用。SI算法在管理中应用算法在管理中应用45（2 2 2 2）物流与供应链管理中应用）物流与供应链管理中应用）物流与供应链管理中应用）物流与供应链管理中应用 物流与供应链管理中，在很多情况下所建立起来的数学物流与供应链管理中，在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实管理中也主要是靠一些经验来进行管理。而目前在现实管理中也主要是靠一些经验来进行管理。现在群体智能算法已成为复杂问题的有效工具，在生产计现在群体智能算法已成为复杂问题的有效工具，在生产计划调度、运输问题、车辆路径调度问题、物流配送管理问划调度、运输问题、车辆路径调度问题、物流配送管理问题，多级库存优化控制策略，题，多级库存优化控制策略，供应链需求预测优化模型研供应链需求预测优化模型研究，究，都得到了有效的应用都得到了有效的应用.SI算法在管理中应用算法在管理中应用46 (3)(3)(3)(3)知识管理中的应用知识管理中的应用 知识管理是企业为实现其管理目标，运用现代的管理理论知识管理是企业为实现其管理目标，运用现代的管理理论和技术，对企业内部和外部知识资源进行发现，挖掘，整理，和技术，对企业内部和外部知识资源进行发现，挖掘，整理，整合，并实施科学的管理和维护，将最合理的知识在最恰当的整合，并实施科学的管理和维护，将最合理的知识在最恰当的时候提供给最需要的人，以便做出最科学的决策。时候提供给最需要的人，以便做出最科学的决策。目前基于群体思想的方法应用于知识管理的主要方向有：客目前基于群体思想的方法应用于知识管理的主要方向有：客户关系管理中的客户行为聚类分析，关联分析，户关系管理中的客户行为聚类分析，关联分析，文档分类，文档分类，属性约简属性约简.SI算法在管理中应用算法在管理中应用47 (5)(5)(5)(5)项目管理项目管理 项目管理网络计划中的工期限定项目管理网络计划中的工期限定-资源均衡问题资源均衡问题 项目合作伙伴的选择问题项目合作伙伴的选择问题 (4)(4)(4)(4)风险管理风险管理 传统的风险管理大都是凭借主观经验，采用定性的判断方传统的风险管理大都是凭借主观经验，采用定性的判断方 法，大多数情况下只考虑信用风险最低而忽略投资投资组法，大多数情况下只考虑信用风险最低而忽略投资投资组 合理论在此过程中的重要。研究如何在各种复杂的、不确合理论在此过程中的重要。研究如何在各种复杂的、不确 定的环境中对资产进行有效的配置，实现资产的回报最大定的环境中对资产进行有效的配置，实现资产的回报最大 化与所承担风险的最小化的均衡，将是化与所承担风险的最小化的均衡，将是SISI应用研究的一个应用研究的一个 重要方向。重要方向。SI算法在管理中应用算法在管理中应用48报告内容报告内容1 1启发式计算方法研究背景启发式计算方法研究背景2 2生物启发式计算方法生物启发式计算方法3 3群体智能优化方法（群体智能优化方法（SI）4 4SI算法在管理中的应用算法在管理中的应用5 5实例研究实例研究49配送中心选址问题配送中心选址问题 配送中心是将取货，集货，包装，仓库，装卸，分货，配货，配送中心是将取货，集货，包装，仓库，装卸，分货，配货，加工，信息服务，送货等多种服务功能融为一体的物流据点。加工，信息服务，送货等多种服务功能融为一体的物流据点。配送中心是进行物流配活动的最主要的硬件设施，所有的物配送中心是进行物流配活动的最主要的硬件设施，所有的物流活动都是基于配送中心这个平台来进行的，它是供应链中非流活动都是基于配送中心这个平台来进行的，它是供应链中非常重要的节点。配送中心的定位几乎决定常重要的节点。配送中心的定位几乎决定 配送业务所需要的配送业务所需要的成本和费用水平。成本和费用水平。本例研究的是多配送中心选址本例研究的是多配送中心选址50配送中心选址问题配送中心选址问题物流配送总费用从配送中心到需求点的单位费用从配送中心到需求点运输量在点设置配送中心的固定费用及管理费用等需求点的需求量可兴建配送中心的最多个数配送中心的容量51配送中心选址模型配送中心选址模型52配送中心选址模型配送中心选址模型53粒子的编码粒子的编码物流配送选址问题主要是在一系列需求点中确定配送中心的最佳位置，目标是使各项费用总和最小。因此对于每个需求点而言，就有两个问题是不是配送中心隶属于哪个配送中心。需求点号：1 2 3 4 5 6 7 0 1 0 2 3 0 0 3 1 2 2 3 2 1 2：2 74：3 4 65：1 5需求点隶属情况：54约束处理约束处理55算法流程算法流程1.初始化一群鸟，每个鸟位置向量X的每一维随机取（1-m）（配送中心数）之间的实数，每个速度向量V的每一维随机取-(m-1),(m-1)之间的整数2.对每个鸟进行整数规范化，计算其适应度值，将初始评价值作为个体历史最优解，并寻找全局最优值3.位置与速度的更新4.对X进行整数规范化，再更新个体与全局最好值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需求点费用表需求点费用表1234567891011121016743466989210565457710910365036910121215141547630310111313161512545630781010131296349107064910667451011860295498671213104201062796712131099100481310910151613105640491189141512642840512910151296971395058最优解的进化最优解的进化59最终求解结果最终求解结果配送中心需求点供应量1 23 4 5 6 7 8 9 10 11 12152 4213242 341383 53213需求量5 42 3 2 4 3 5 4 322合计396061
