1、v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level1分布式群体智能计算与应用陈伟能陈伟能 博士博士 副教授副教授20152015年年 9 9月月 8 8日日 20152015夏季学期夏季学期高性能计算导论高性能计算导论讲座讲座v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level2p 联系方式联系方式陈伟能陈伟能 博士、副教授博士、副教授Email：Addr
2、ess: 中山大学东校区信息学院中山大学东校区信息学院510欢迎各位同学与我联系！欢迎各位同学与我联系！v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level3主主 要要 内内 容容分布式群体智能计算分布式群体智能计算群体智能计算应用群体智能计算应用研究方向研究方向群体智能计算简介群体智能计算简介一一二二三三四四v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth lev
3、el4什么是群体智能？什么是群体智能？p 群体智能计算是模拟自然界群体智能行为的优化方法 蚁群优化蚁群优化（Ant Colony Optimization，ACO；Dorigo et al., 1992） 粒子群优化粒子群优化（Particle Swarm Optimization，PSO；Kennedy & Eberhart , 1995） 人工蜂群人工蜂群（Artificial Bee Colony，ABC；Karaboga, 2005） 蚂蚁群体的寻路行为蚂蚁群体的寻路行为飞鸟群体的觅食行为飞鸟群体的觅食行为个体行为模式简单，但群体行为模式具有智能性个体行为模式简单，但群体行为模式具有智
4、能性v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level5蚁群优化蚁群优化（Ant Colony OptimizationAnt Colony Optimization）p “双桥实验双桥实验”v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level6蚁群优化蚁群优化（Ant Colony OptimizationAnt Colony Optimization）
5、p “双桥实验双桥实验”v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level7蚁群优化蚁群优化（Ant Colony OptimizationAnt Colony Optimization）p “双桥实验双桥实验”v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level8粒子群优化粒子群优化（Particle Swarm OptimizationParticle
6、 Swarm Optimization）飞去哪儿？njXGBestrcXPBestrcVVjijjjijijjiji,.,2 , 1 ),()(2211个体认知：（self cognition）个体曾经抵达的最优位置社会互动：（social interaction）种群整体抵达的最优位置v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level9算法流程图算法流程图蚁群优化流程图粒子群优化流程图v Click to edit Master text stylesv Second l
7、evelv Third levelvFourth levelvFifth levell大数据、大规模大数据、大规模l维度诅咒（维度诅咒（curse of dimensionality）l数据驱动数据驱动l缺乏精确的数学解析缺乏精确的数学解析模型模型10为什么要研究群体智能？为什么要研究群体智能？实际应用需求实际应用需求优化方法优化方法面临的挑战面临的挑战交通物流交通物流模型模型经济金融经济金融经济金融经济金融规模规模科学计算科学计算实际应用中存在着大量的复杂优化问题传统方法无法使用群体智能群体智能的优势的优势 不依赖问题的精确解析模型和数学特性，启发式搜索不依赖问题的精确解析模型和数学特性，启
8、发式搜索 在可接受时间内发现问题的满意解在可接受时间内发现问题的满意解群体智能计算已成为求解复杂优化问题的重要途径p 求解复杂优化问题的重要方法求解复杂优化问题的重要方法v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level11为什么要研究群体智能？为什么要研究群体智能？p 国际前沿研究课题国际前沿研究课题IEEE Trans.每年刊印关于PSO的论文数目一般研究发展规律计算智能研究所处阶段计算智能研究所处阶段4. 4. 归纳总结，归纳总结，提出理论框架提出理论框架6. 6.
9、得出完备得出完备的数学基础的数学基础3. 3. 算法提出算法提出5. 5. 系统性能分析系统性能分析7. 7. 实际验实际验证和应用证和应用1. 1. 实际需求实际需求2. 2. 多种实践探多种实践探索索l IEEE Trans. Evolutionary ComputationIEEE Trans. Evolutionary Computation影响因子影响因子5.5455.545，计算机理论领域，计算机理论领域102102本期刊排名第本期刊排名第1 1（1 1区）区）l IEEE Trans. CyberneticsIEEE Trans. Cybernetics影响因子影响因子3.781
10、(13.781(1区区) )主要主要刊物刊物v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level12为什么要研究群体智能？为什么要研究群体智能？p 群体智能与大数据研究群体智能与大数据研究 大数据的特点（大数据的特点（4V：Volume、Velocity、Variety、Value） 大数据驱动的大数据驱动的科学研究第四范式科学研究第四范式数据驱动下缺乏精确数学模型的优化问题需要群体智能计算方法求解格雷v Click to edit Master text stylesv S
11、econd levelv Third levelvFourth levelvFifth level13Big Data: The Fourth ParadigmBig Data: The Fourth Paradigmphenomenonphenomenonconclusionconclusion1st: experiment2nd: theory3rd: simulationphenomenonphenomenonconclusionconclusionTraditional scientific thinking paradigm Know whyThe thinking paradigm
12、 under big data Know what4th: big datav Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level14为什么要研究群体智能？为什么要研究群体智能？p 群体智能与高性能计算群体智能与高性能计算群体智能计算与高性能计算相辅相成大规模大规模群体智能计算群体智能计算高性能计算环境高性能计算环境优势：强大的全局优化能力基于高性能计算的大规模群体智能计算方法基于群体智能计算的资源调度管理优化存在问题：大规模优化需要大量计算资源优势：提供强大的计算能力存在问题
13、：大量计算资源的管理与调度v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level15已有工作简介已有工作简介高代价的约束处理高代价的约束处理低代价的约束处理低代价的约束处理早熟收敛问题早熟收敛问题提高多样性、避免早熟提高多样性、避免早熟连续空间特解算法连续空间特解算法连续、离散通解算法连续、离散通解算法科学问题科学问题 解决途径解决途径 代表性成果代表性成果 算法应用算法应用 群体智能计算的适用性问题群体智能计算的适用性问题集合空间拓展集合空间拓展引入寿命机制引入寿命机制新型编
14、码策略新型编码策略成果成果1 1：集合型群：集合型群体智能计算体智能计算成果成果2 2：基于寿命：基于寿命的群体智能计算的群体智能计算成果成果3 3：约束优化：约束优化的群体智能计算的群体智能计算工作流工作流软件工程软件工程金融管理金融管理不同解空间中的不同解空间中的算法适用性问题算法适用性问题多峰优化中的算多峰优化中的算法适用性问题法适用性问题约束优化中的算约束优化中的算法适用性问题法适用性问题v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level161 1 解空间拓展解空间
15、拓展集合型群体智能集合型群体智能p 问题的提出问题的提出n 经典经典PSO、DE等算法定义于连续实数向量空间，一般用于求等算法定义于连续实数向量空间，一般用于求解连续空间的优化问题解连续空间的优化问题n 如何将算法拓展成连续、离散空间的通用算法？如何将算法拓展成连续、离散空间的通用算法？njxgbestrcxpbestrcwvvjijjjijijjiji,.,2 , 1 ),()(2211njxvxjijiji,.,2 , 1 ,例如：原始的粒子群优化算法例如：原始的粒子群优化算法速度更新速度更新位置更新位置更新速度、位置及其相关操作都定义在连续实数向量空间速度、位置及其相关操作都定义在连续实
16、数向量空间v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level17p 主要创新点：主要创新点：在集合空间重定义群体智能计算方法在集合空间重定义群体智能计算方法城市1城市2城市3城市4城市5城市6城市7城市8城市9城市10连续搜索空间连续搜索空间X离散搜索空间离散搜索空间),(21niiixxxix解的表示：实数向量解的表示：实数向量Representation: real vectors 解的表示：集合解的表示：集合Sets (1,2), (2,3), (3,4), , (1
17、,5)集合理论集合理论 1 1 解空间拓展解空间拓展集合型群体智能集合型群体智能v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level18参数参数集合集合 （coefficientset）1352461352460.5 0.50.50.50.5位置位置位置位置 （position-position） and |BeAeeBA135246135246135246njXGBestrcXPBestrcVVjijjjijijjiji,.,2 , 1 ),()(2211带概率的集合带概率
18、的集带概率的集合带概率的集 （union of two sets with possibilitis） V11=(1, 2)/0.6, (1, 4)/0.9V12 =(1, 2)/0.9, (1, 3)/0.3V11 V12 = (1, 2)/0.9, (1, 3)/0.3, (1, 4)/0.91 1 解空间拓展解空间拓展集合型群体智能集合型群体智能v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level19p 科学价值科学价值 将部分连续空间的群体智能计算特解算法拓展成通解算
19、法将部分连续空间的群体智能计算特解算法拓展成通解算法 各种版本的各种版本的PSO、DE等算法均可基于此框架拓展等算法均可基于此框架拓展 拓展后算法的搜索特性与参数设置，和经典算法保持一致拓展后算法的搜索特性与参数设置，和经典算法保持一致经典经典PSOPSO、DEDE算法算法解的表示：连续实数向量解的表示：连续实数向量算法操作：实数向量运算算法操作：实数向量运算适用空间：连续空间适用空间：连续空间特解算法特解算法提出的提出的集合型群体智能计算集合型群体智能计算解的表示：元素可为各种数据解的表示：元素可为各种数据 类型的集合类型的集合算法操作：集合运算算法操作：集合运算适用空间：连续、离散空间适用
20、空间：连续、离散空间通解算法通解算法集合型拓展集合型拓展1 1 解空间拓展解空间拓展集合型群体智能集合型群体智能v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level20p 代表论文代表论文 Wei-neng Chen (陈伟能陈伟能), et al, “A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems,” IEEE Transactions on Ev
21、olutionary Computation, vol.14, no.2, pp.278-300, April, 2010. 巴西巴西Parana联邦大学的联邦大学的Pozo教授教授在进化计算顶级会议在进化计算顶级会议IEEE CEC上上发表的文章中专门用发表的文章中专门用“Chen and ACO”的段落来介绍我们的成果。的段落来介绍我们的成果。同行引用同行引用及评价及评价IEEE 计算智能分会计算智能分会(CIS)会刊会刊Computational Intelligence Magazine在在Publication Highlight中介绍中介绍了我们的成果。是该季度了我们的成果。是该季
22、度IEEE CIS出版的全部出版的全部103篇篇IEEE Trans. 论文中被介绍的论文中被介绍的 8 篇之一。篇之一。1 1 解空间拓展解空间拓展集合型群体智能集合型群体智能v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level212 2 多峰优化拓展多峰优化拓展基于寿命的群体智能基于寿命的群体智能p 问题的提出问题的提出n 算法在多峰优化环境下容易落入局部最优，出现早熟现象算法在多峰优化环境下容易落入局部最优，出现早熟现象n 如何提高算法的搜索多样性，避免早熟现象，同时又
23、保持算如何提高算法的搜索多样性，避免早熟现象，同时又保持算法的快速收敛特性？法的快速收敛特性？njxgbestrcxpbestrcwvvjijjjijijjiji,.,2 , 1 ),()(2211njxvxjijiji,.,2 , 1 ,例如：经典的粒子群优化算法例如：经典的粒子群优化算法速度更新速度更新位置更新位置更新种群中个体都向全局最优个体种群中个体都向全局最优个体gbest学习，当学习，当gbest落入局部最优，将导致算法早熟停滞落入局部最优，将导致算法早熟停滞v Click to edit Master text stylesv Second levelv Third levelv
24、Fourth levelvFifth level22p 主要创新点：主要创新点：将寿命机制引入群体智能计算将寿命机制引入群体智能计算100年年80年年20年年8年年为什么生物具有衰老为什么生物具有衰老和寿命现象？和寿命现象？Weismann，1882衰老有利于进化，为下一代发展腾出了空间Goldsmith，2006进化衰老理论：寿命是一种遗传现象，对生物的多样性有重要作用启发基于寿命的基于寿命的群体智能计算方法群体智能计算方法2 2 多峰优化拓展多峰优化拓展基于寿命的群体智能基于寿命的群体智能v Click to edit Master text stylesv Second levelv T
25、hird levelvFourth levelvFifth level23)()(2211XgBestXpBestVVrcrc经典经典PSO算法：算法：始终向始终向gBest学习，容易落入局部最优学习，容易落入局部最优基于寿命的基于寿命的PSO算法：算法：)()(2211jijjjijijjijixLeaderrcxpBestrcvv进化衰老理论进化衰老理论 衰老和寿命与生物的遗传和衰老和寿命与生物的遗传和进化多样性息息相关进化多样性息息相关向有寿命限制的向有寿命限制的Leader学习，学习，当当Leader落入局部最优时会由于落入局部最优时会由于衰老而被取代，从而引入充分的搜索多样性衰老而被
26、取代，从而引入充分的搜索多样性p 科学价值科学价值n 将生物学的进化衰老理论引入智能计算方法将生物学的进化衰老理论引入智能计算方法n 提高算法搜索多样性，避免早熟收敛提高算法搜索多样性，避免早熟收敛2 2 多峰优化拓展多峰优化拓展基于寿命的群体智能基于寿命的群体智能v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level24p 代表论文代表论文 Wei-neng Chen (陈伟能陈伟能), et al., “Particle Swarm Optimization with an
27、 Aging Leader and Challengers,” IEEE Transactions on Evolutionary Computation, vol. 17, no. 2, pp. 241-258, April 2013. 入选入选ESI高被引论文高被引论文IEEE Trans. on Evolutionary Computation的评审人评价我们的成果为的评审人评价我们的成果为PSO提供了一提供了一个新的研究方向个新的研究方向(provides a new direction of research for the algorithm)。IEEE Fellow，新加坡南洋理
28、工大学的，新加坡南洋理工大学的Changyun Wen 教授，在教授，在IEEETrans. on Cybernetics上发表待印的论文中上发表待印的论文中指出申请人提出的算法在测试的问题上表指出申请人提出的算法在测试的问题上表现良好。现良好。2 2 多峰优化拓展多峰优化拓展基于寿命的群体智能基于寿命的群体智能v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level253 3 约束优化拓展约束优化拓展新型编码策略新型编码策略p 问题的提出问题的提出n 算法在搜素过程中生成大量非
29、法解，造成计算代价耗费算法在搜素过程中生成大量非法解，造成计算代价耗费n 如何提高算法在约束优化中的效率？如何提高算法在约束优化中的效率？p 主要创新点：主要创新点：提出新型编码策略使算法只生成合法解提出新型编码策略使算法只生成合法解约束平面约束平面等式约束问题：基于等式约束问题：基于约束平面的变换编码约束平面的变换编码项目资源约束问题：项目资源约束问题：基于有向无环图的编码基于有向无环图的编码TSMC-CTSMC-C20102010(IF=2.548)TEvCTEvC20122012(IF=4.810)v Click to edit Master text stylesv Second le
30、velv Third levelvFourth levelvFifth level26主主 要要 内内 容容分布式群体智能计算分布式群体智能计算群体智能计算应用群体智能计算应用研究方向研究方向群体智能计算简介群体智能计算简介一一二二三三四四v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level27研究背景与意义研究背景与意义粒子群优化流程图粒子群优化流程图计算量较大（CPU-intensive）需要反复迭代地生成并评估解算法求解大规模优化问题时存在效率瓶颈内在分布性算法中“个体
31、”的操作相对独立，具有分布特性算法的特征有利于在并行、分布环境中实现v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level28研究背景与意义研究背景与意义大规模分布式群体智能计算群体智能计算群体智能计算高性能计算环境高性能计算环境优势：强大的全局优化能力优势：提供强大的计算能力群体智能计算内在的并行分布特性v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level2
32、9研究背景与意义研究背景与意义p 目的目的n 提高群体智能方法解决大规模、高时耗优化问题的能力提高群体智能方法解决大规模、高时耗优化问题的能力n 提高分布式群体智能计算方法的效率提高分布式群体智能计算方法的效率p 并行分布式算法的评价标准并行分布式算法的评价标准n 加速比和效率加速比和效率n理想状态：理想状态：T并行并行 = T串行串行/Pn实际加速比：实际加速比：S = T串行串行/T并行并行n效率效率E=T串行串行/（p*T并行）并行）n 可扩展性可扩展性n若增加进程数，而输入规模也以相应的增长率增长的情况下，程序的效若增加进程数，而输入规模也以相应的增长率增长的情况下，程序的效率保持为率
33、保持为E，则称程序是可扩展的，则称程序是可扩展的v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level30分布式进化计算的关键问题分布式进化计算的关键问题计算层：计算和通讯过程如何组织？并行模型问题层：如何对大规模问题降维处理？问题解耦平台层：选择哪种分布式计算环境？并行环境v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level311 1 并行环境并行环境超级计
34、算超级计算云计算云计算计算机集群计算机集群GPUGPUP2PP2P网络网络v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level322 2 问题解耦：如何实现问题降维问题解耦：如何实现问题降维p 解耦目的解耦目的n 减少优化问题维度、降低大规模问题的优化难度减少优化问题维度、降低大规模问题的优化难度p 解耦的基本思想解耦的基本思想n 尽可能介绍解耦后各个子问题之间的关联性尽可能介绍解耦后各个子问题之间的关联性p 两个关键问题两个关键问题如何解耦？如何将大规模问题分解为多个低维子
35、问题如何协同？各部分子问题如何协同进化、优化v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level332 2 问题解耦问题解耦处理器处理器集合集合1目标目标1目标目标2目标目标N多目标问题多目标问题处理器处理器集合集合2处理器处理器集合集合N解解 组组 装装计计算算分分拆拆目目标标分分拆拆处理器处理器集合集合1子问题子问题1子问题子问题2 子问题子问题N高维问题高维问题处理器处理器集合集合2处理器处理器集合集合N解解 组组 装装计计算算分分拆拆维维度度分分拆拆v Click t
36、o edit Master text stylesv Second levelv Third levelvFourth levelvFifth level342 2 问题解耦问题解耦p 基于具体问题的特点进行解耦（基于具体问题的特点进行解耦（Problem-specific）功率电路优化问题PCA为一个子问题FN为另一个子问题主要不足：仅适用于具体特定问题主要不足：仅适用于具体特定问题v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level352 2 问题解耦问题解耦p 随机分组
37、（随机分组（IEEE Trans. on EC, 2011）在不清楚给维度关系的在不清楚给维度关系的情况下，通过随机性提情况下，通过随机性提高准确分组的机会高准确分组的机会变量随机分组变量随机分组分组数随机选定分组数随机选定主要不足：随机分组准确性较低主要不足：随机分组准确性较低v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level362 2 问题解耦问题解耦p 差分分组（差分分组（IEEE Trans. on EC, in press）将相关的变量尽可能分在同一组将相关的变量
38、尽可能分在同一组若若则认为这两个变量之间是不相关的则认为这两个变量之间是不相关的不相关的情况相关的情况主要不足：差分判断需要较大计算量主要不足：差分判断需要较大计算量但单次判断只能基于一个初始点但单次判断只能基于一个初始点v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level372 2 问题解耦问题解耦p 多目标拆分多目标拆分v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFi
39、fth level382 2 问题解耦问题解耦p 协同进化框架（协同进化框架（Cooperatively Coevolution）任务协同资源协同v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level392 2 问题解耦问题解耦p 协同进化框架（协同进化框架（Cooperatively Coevolution）特点：进化一个子问题，其他部分固定，定期交流通讯特点：进化一个子问题，其他部分固定，定期交流通讯存在问题：计算量问题、通讯问题、同步存在问题：计算量问题、通讯问题、同步/
40、 /异步问题异步问题v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level403 3 并行模型：主从模型并行模型：主从模型p 特点特点n 当适应值评价时间当适应值评价时间通讯时间时，算法效率越高通讯时间时，算法效率越高n 主从之间频繁通讯，主节成为瓶颈主从之间频繁通讯，主节成为瓶颈p主节点（主节点（Master）n存储整个种群存储整个种群n执行整个算法的各个算子操作执行整个算法的各个算子操作(如选择、交叉、变异等如选择、交叉、变异等)p从节点（从节点（Slaves）n适应值评估
41、适应值评估n局部搜索局部搜索p通讯规则通讯规则n只发生在主从节点之间只发生在主从节点之间（slaves之间不进行通讯）之间不进行通讯）v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level413 3 并行模型：岛屿模型（粗粒度）并行模型：岛屿模型（粗粒度）p 特点特点n 能更好地体现算法的并行分布特性，并提高算法全局搜索能力能更好地体现算法的并行分布特性，并提高算法全局搜索能力n 对岛屿的数目和通讯方式敏感，可拓展性受限对岛屿的数目和通讯方式敏感，可拓展性受限p岛节点（岛节点（
42、Island）n存储一个子种群存储一个子种群n在子种群上在子种群上执行整个执行整个子子算法的算法的各个各个算子操作算子操作n与其他岛进行消息传递与其他岛进行消息传递p通讯规则通讯规则n发生在岛与岛间的个体迁移发生在岛与岛间的个体迁移n每隔一定代数在规定的拓扑结每隔一定代数在规定的拓扑结构下执行构下执行v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level423 3 并行模型：细胞模型（细粒度）并行模型：细胞模型（细粒度）p 特点特点n 个体间相互独立，并行分布性强，容错性强个体
43、间相互独立，并行分布性强，容错性强n 通讯量较大，需在提高全局搜索能力和控制通讯开销之间取得平衡通讯量较大，需在提高全局搜索能力和控制通讯开销之间取得平衡p单元节点（单元节点（Cell）n存储一个个体存储一个个体n个体的更新通过与邻居个体的个体的更新通过与邻居个体的交互实现交互实现p通讯规则通讯规则n发生在单元与单元之间的消息发生在单元与单元之间的消息迁移迁移n每个个体只允许与其邻域内的每个个体只允许与其邻域内的个体进行通讯。个体进行通讯。v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFif
44、th level433 3 并行模型并行模型p 层次模型层次模型p 特点特点n 能综合不同模型的优点，提高并行算法效率能综合不同模型的优点，提高并行算法效率层次模型层次模型基本思想 将多种并行模型，将多种并行模型，通过不同层次结通过不同层次结合起来合起来v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level44主主 要要 内内 容容分布式群体智能计算分布式群体智能计算群体智能计算应用群体智能计算应用研究方向研究方向群体智能计算简介群体智能计算简介一一二二三三四四v Click
45、to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level45应用应用1 1 云计算资源与工作流管理云计算资源与工作流管理云计算p 核心核心计算资源的调计算资源的调度和管理度和管理 复杂调度问题复杂调度问题p 目标目标提高服务质量、提高服务质量、降低成本、提降低成本、提高资源利用率高资源利用率v Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level46应用应用1 1 云计算资源与工作
46、流管理云计算资源与工作流管理Workflow ApplicationtasktasktasktasktasktasktaskGrid/Cloud EnvironmentComputational resourcep 复杂的计算任务在云环境中往复杂的计算任务在云环境中往往被建模为工作流往被建模为工作流p 云工作流调度问题是一个云工作流调度问题是一个NP-难难优化问题优化问题p 工作流调度的性能对云工作流调度的性能对云/网格计网格计算的性能起到至关重要的作用算的性能起到至关重要的作用v Click to edit Master text stylesv Second levelv Third le
47、velvFourth levelvFifth level47应用应用1 1 云计算资源与工作流管理云计算资源与工作流管理collect servicesinformationGrid MarketDirectory(GMD)schedulingmoduleQoSestimationmoduleservice reservationservice executionUserworkflowspecificationQoS requirementQoSparameterrecorderregister as GSPGive me list of servicesand QoS informatio
48、nserviceinformation listGrid ServiceProvider (GSP)GSPGSPGridserviceregister asserviceService available?Available time slotreservationexecutionQoSfeedbackviolation managementv Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level48应用应用1 1 云计算资源与工作流管理云计算资源与工作流管理稳定性稳定性Rel
49、iability期限期限Deadline预算预算Budget用户自定义用户自定义QoS约束约束User-defined QoS Constraints最大化可靠性最大化可靠性ReliabilityMaximization最小化工期最小化工期MakespanMinimization最小化费用最小化费用CostMinimization用户自定义优化目标用户自定义优化目标User-specified QoS Preferencep优化目标优化目标Optimization Objective 最优化用户定义的最优化用户定义的QoS参数，同时满足参数，同时满足用户定义的所有用户定义的所有QoS约束。约束
50、。Optimize the user-specified QoS optimization preference, subject to all the QoS constraints defined by the usersv Click to edit Master text stylesv Second levelv Third levelvFourth levelvFifth level49应用应用1 1 云计算资源与工作流管理云计算资源与工作流管理难点1：如何满足多种QoS约束条件How to satisfy multiple QoS constraints? 难点2：如何根据需要优
