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

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