大数据挖掘就是海量数据挖掘
13
我们的理解
14
大数据的认识
从计算机的发展历程说起
计
CPU + 存储
早期 近代
算
机 I/O 设备
15
大数据的认识
从计算机的发展历程说起
CPU1 CPU2
CPU + 存储
CPU3
CPU4
计
超级计算机 云计算平台 神经突触计算机芯片
算 机
I/O 设备
今天
物联网的广泛应用
上述思想可兼容各类进化算法：多种群协同优化多目标问题的通用算法框架
30
研究1：多种群协同进化的多目标PSO
单个种群的进化策略
每个种群优化一个目标，进化过程与单目标PSO算法类似。 每个种群中粒子的位置更新方法： 新位置 原位置 新速度
原速度的惯性影响 个体历史最佳位置的引导
每个粒子从全局Archive中随机 选择一个学习对象： 计算量小 保持多样性
模型
方法
海量数据：经过长年探索已经形成一套可行的处理方法
大数据：尚且缺少行之有效的处理方法，亟待发展新方法 海量数据：有明确的挖掘目标，关注解释事物之间的因果关系
目标
大数据：没有具体的挖掘目标，关注点从因果关系转向关联关系； 其价值在于能够发现超出预想的知识，填补空白。
20
如何解决大数据问题？
大数据的特点
智能化需求中的优化问题
• 缺乏精确数学模型 • 具有高维、非线性等特点 • 传统方法难以求解 需求
进化计算
• 模拟自然进化的智能方法 智能计算成为解决大规模、 • 不依赖问题的数学特性 复杂优化问题的重要途径。 • 成为解决复杂优化问题的重要途径
• 传统进化计算方法求解大规模复杂 优化问题时存在性能瓶颈 • 传统进化计算方法以串行执行为主， 无法发挥分布式计算平台优势
种群历史最佳位置的引导
全局Archive中非劣解的引导
31
研究1：多种群协同进化的多目标PSO
全局Archive的更新策略 (1)
全局Archive 中的原有解
精英学 习策略 非劣解 选择 策略
种群1中每个粒子的历史最优位置
全局 Archive
种群2中每个粒子的历史最优位置
种群M中每个粒子的历史最优位置
Cross-reproduction
从全局（以分布密度为标准）和 局部Archives（以适应值为标准） 中分别选择一个个体进行交叉
CMPSO 在 UF1 和 UF2 上 对 Pareto 前 沿 的 覆盖 比 MOEA/DDE更均匀
研究成果已发表于国际期刊IEEE Transactions on Cybernetics
Z.-H. Zhan, J. Li, J. Cao, J. Zhang, H. Chung, and Y. H. Shi, “Multiple populations for multiple objectives: A coevolutionary technique for solving multiobjective optimization problems,” IEEE Transactions on Cybernetics, vol. 43, no. 2, pp. 445 – 463, Apr. 2013.
中山大学超算学院
主要 内容
对大数据的理解
分布式进化计算
大数据是什么？
社交媒体 社交网站产生 “大数据” 的文字、图片、
视频等数据
电信 “大数据”
从各种移动终 端和通信网络 获取的数据
大数据就是存储量级超TB的数据？ 大数据就是多种数据的综合体？ 具有4V特征的数据就是大数据？ 大数据的主要价值在于体量大？
由医疗机构 保存的记录 和标本构成 的数据集
医疗 “大数据”
金融 “大数据”
由银行等金 融机构收集 的市场活动 数据
由大量标本的 基因序列构成 的数据库
基因 “大数据”
气象 “大数据”
由地面和高空 观测站不间断 传回的数据 12
大数据 ＝ 海量数据？
大数据是海量数据的另一种说法
大数据只是体量比海量数据更大
36
研究2：带双层Archive的多目标进化算法
研究背景与意义
问题提出
多目标优化问题期望得 到尽量接近Pareto前沿 且均匀分布的一组解
难点所在
Pareto前沿的精确逼近 与全面覆盖常难以兼顾
主要研究内容
运用双层Archive结构 同时实现Pareto前沿的 精确逼近与全面覆盖
现有多目标进化算法
No
进化结束？
Yes
结 束
39
研究2：带双层Archive的多目标进化算法
进化过程中个体的流向
第gen代 第gen+1代
全局Archive
Self-reproduction
按分布密度从全局Archive中 选择个体进行交叉和变异
全局Archive
局部Archive 1
局部Archive 1
局部Archive 2 ... 局部Archive N
算法思想
分配 具 有 M 个 冲 突 目 标 的 通信
多
目标1
种群1
目
标 问
目标2
分配
通信
全局 Archive
保存原 问题的 非劣解
种群2
…
…
题
分配
通信
目标M
种群M
主要创新点：
每个种群优化一个目标：解决了赋值困难，充分探索了目标空间
种群通过全局Archive共享信息：促使解均匀覆盖整个Pareto前沿
大数据的理解与 分布式进化计算方法
张军
中山大学 超级计算机学院
2014年10月
1
中山大学超算学院
主要 内容
对大数据的理解
分布式进化计算
中山大学简介
3
中山大学由孙中山先生在 1924 年创立，至今已有近百年 历史。2012年，在校学生总数达83633人，教职工总数达13683 人。 继承孙中山先生“一文一武”的教育思想 教育部直属综合性大学 入选“985”和“211”工程的全国重点高校
第1类：如NSGA II
MOEA-DLA
通过双层 Archive结构 结合两类 算法的优点
基于非支配排序和拥挤距离对问题进行整体求解
优点：全面性较好 缺点：对复杂Pareto前沿逼近精度较低
第2类：如MOEA/D
通过权重将原问题拆分为多个单目标问题分别进行优化
优点：精度较高 缺点：解的分布存在缺陷
37
32
…
研究1：多种群协同进化的多目标PSO
全局Archive的更新策略 (2)
精英学习策略： 新解 原解 随机扰动向量 随机扰动全局Archive中的解，帮助算法跳出局部最优。 非劣解选择策略：
① 运用非支配排序（non-dominated sorting）选出非劣解； ② 如果非劣解的数目超过Archive的容量，根据拥挤距离（crowdingdistance）删去分布密度最大的若干解。
将高维问题拆分为若干低维问题，以便高效计算和处理
在分布式计算平台上对拆分后的低维问题进行协同处理
运用聚合原理将各个低维问题上的结论组合的大数据分析方法
问题拆分方法 值得研究的拆分方法
随 机 拆 分
目标1 (f1)
复杂多目标问题
min g ( x, i ) i(1) f1 ( x ) i(2) f 2 ( x ) where i(1) i(2) 1
3
中山大学简介
湖南省
江西省
4
福建省 北校区 广西省 东校区（大学城） 广州
深圳
珠海 澳门 南校区 香港
中山大学校区分布情况
广东省
珠海校区
4
中山大学简介
南校区风光
5
5
中山大学简介
东校区风光
6
中山大学简介
7
北校区风光
7
中山大学简介
8
珠海校区风光
8
超算学院选址
超算学院位于中山大学大学城校区内的广州超算中心第5层
min g (x, λ1) min g (x, λ2) min g(x, λ3)
按 任 务 拆 分
min g(x, λN) 目标2 (f2)
按 目 标 拆 分
分拆
多个单目标问题
...
min g(x, λ1) min g(x, λN)
子系统1
…
子系统N
24
可行的大数据分析方法
分布的、自组织的智能计算方法
研究2：带双层Archive的多目标进化算法
算法思想
N个单目标问题 多目标问题
min {f1(x), f2(x), …, fM(x)}
通过权重 拆分
min å i w f ( x )
(1) i i
子问题1
min å i w f (x )
(2) i i
子问题2
…
min å i wi( N ) fi (x )
38
研究2：带双层Archive的多目标进化算法
算法流程
开 始 随机产生一组解以初始化全局和局部Archives
• 全局Archive内部的self-reproduction • 两层Archive之间的Cross-reproduction
执行进化算子产生新的解
根据新解更新全局和局部Archives
大数据与智慧城市
智慧体的感官
建 设 智 慧 城 市 的 关 键 技 术
物联网技术
智慧体的血脉
大数据技术
高性能 计算
智慧体的大脑
高性能计算技术