Computer Engineering and Applications 计算机工程与应用 2011，47（12） 229 一种求解车间调度问题的混沌遗传规划方法 周 强 1，崔逊学 2 ZHOU Qiang1，CUI Xunxue2 1.滁州学院 计算机科学与技术系，安徽 滁州 239012 2.解放军炮兵学院，合肥 230031 1.Department of Computer Science and Technology，Chuzhou University，Chuzhou，Anhui 239012，China 2.Artillery Academy of PLA，Hefei 230031，China ZHOU Qiang，CUI Xunxue.Chaos genetic programming method for job-shop scheduling problem.Computer Engineering and Applications，2011，47（12）：229-233. Abstract： The job-shop scheduling problem is an NP-hard combinational optimization problem in the manufacturing field. The paper proposes a job-shop scheduling algorithm based on chaos genetic programming.Genetic programming is adopted to design a chromosome structure，the chaos sequence method is used to improve the quality of initial population，chaos distur- bances are taken to maintain the diversity of evolutionary population，and the self-adaptive adjusting method of individual weight is applied.Accordingly the proposed algorithm has a comprehensive solving capacity for a scheduling problem.Simula- tion experiments show that it has better ability to find the global optimum for several typical scheduling testing benchmarks. The results of Gantt charts point out the optimum solutions obtained by this novel algorithm are better than the historic ones.The comparison of the results reveals the feasibility and efficiency of the method. Key words：job-shop scheduling；chaos；genetic programming；combinational optimization that 摘 要：作业车间调度问题是制造业的一个经典 NP-hard 组合优化难题。提出一种基于混沌遗传规划的调度算法，利用遗传规划 进行染色体的结构设计，采用混沌序列改善初始种群质量，利用混沌扰动来维持进化群体的多样性，并自适应调整个体权重，使 算法具有优良的综合求解性能。实验表明，算法对典型的标准调度测试问题具有较强的全局搜索能力，甘特图表明其获得的最 优解优于当前已知的最优解历史记录，对比结果表明了该方法的有效性。 关键词：作业车间调度；混沌；遗传规划；组合优化 DOI：10.3778/j.issn.1002-8331.2011.12.064 文章编号：1002-8331（2011）12-0229-05 文献标识码：A 中图分类号：TP301.6 1 引言 作业车间调度问题（Job Shop Scheduling Problem，JSSP） 是制造业的重点研究难题之一，属于典型的 NP-hard 问题。它 是许多实际生产调度问题的简化模型，常采用人工智能的优 化方法来搜索求解。JSSP 的求解方法即调度优化算法，可分 为精确求解和近似求解两种[1]。精确方法在合理的时间内只 能求解小规模问题。近似求解法能够在可接受的时间内，求 得问题近似最优解或准最优解。近年来近似求解法发展迅 速，已成为人们研究的热点，受到学术界的广泛重视，它主要 包括遗传算法、模拟退火算法和禁忌搜索等[2]。 针对作业车间调度问题，人们提出各种思想和解决思路， 希望提高调度优化的性能。文献[3]将粒子群算法、遗传操作 和模拟退火三者有机地结合在一起，设计了一种约束混合进 化算法。文献[4]基于粒子群的群体智能优势，实现大范围的 全局搜索，设计了基于关键工序的领域选择方法，嵌入禁忌搜 索模块来强化局部搜索能力，基于交换序的混合粒子群优化 来增强粒子算法的搜索能力。文献[5]将作业车间调度的所有 约束条件建模为计算能量函数的表达式，采用混沌动力学和 离散 Hopfield 神经网络来优化调度，设计了一种暂态混沌离散 神经网络的作业车间调度方法。但上述方法在一定程度上存 在早熟收敛、收敛速度慢等效率问题。 相对而言，遗传规划（Genetic Programming，GP）作为一种 在遗传算法的基础上发展起来的优化方法，以树型层次结构 来描述问题模型，其本身就具有结构自动寻优能力和擅于表 示复杂问题的特点，因此非常适宜求解复杂的车间作业调度 问题[6]。 混沌作为当前人工智能领域的一种优化理论，具有随机 性和遍历性的优点，容易跳出局部搜索极值的羁绊。它根据 迭代的不重复性和遍历性，按照自身规律不重复地遍历所有 状态。利用混沌变量进行优化搜索，可避免陷入局部最优点， 基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.60773129）；安徽高校省级自然科学研究项目 （No.KJ2011B115，No.KJ2009B140）。 作者简介：周强（1978—），男，讲师，主要研究领域为智能计算、调度算法、网络优化；崔逊学（1969—），男，博士，副教授。E-mail：aq_ay@126.com 收稿日期：2010-11-22；修回日期：2011-01-26 

230 2011，47（12） Computer Engineering and Applications 计算机工程与应用 达到全局最优。由于混沌算法编程简单，计算精度较高，对优 化目标函数的特性要求较少，因而应用范围很广[7]。从混沌学 的角度来看，生物进化的模式是“随机+反馈”，随机是系统本 身的特性，混沌则是系统进化和获得信息的来源，在算法中引 入混沌理论会使计算更接近真实的生物进化模式。 提出了一种基于混沌遗传规划的作业车间调度算法，采 用 GP 表达作业调度的复杂结构问题，将混沌原理引入作业车 间调度优化过程，设计了搜索过程中调整进化压力的方案，通 过典型的 JSSP 问题实验表明了该算法的有效性。 2 基于混沌遗传算法的调度算法 2.1 基本思想 本文调度算法的设计思想是将混沌理论与 GP 结合，既弥 补 GP 的缺陷，又发挥其特长。采用混沌序列染色体来避免未 达到最优的某些个体被不公平淘汰，实现模型结构的自动寻 优，这种混沌遗传规划特别适合求解作业车间调度问题。 通常进化算法的变异和交叉操作是随机的，认为采用混 沌序列的交叉和变异操作更接近物种繁衍的机理。因为计算 机科学领域的人工模拟交叉和变异过分简化了生物的遗传操 作过程，实际上物种繁衍具有其内在规律，不单纯是简单的数 学运算。本文算法的思路如下： （1）采用混沌序列来确定变异和交叉的位置。由于混沌 具有内在随机性，虽然貌似噪声，但不同于噪声。针对传统交 叉和变异操作算子的敏感性问题，采用混沌树型染色体序列 可避免进化群体陷入局部最优解，增强个体解的多样性。 （2）利用混沌序列产生初始群体，生成与优化变量相同数 目的混沌变量，将混沌操作的遍历范围映射到优化变量的取 值范围，并择优选出初始种群。 （3）在判断出种群发生早熟时，对染色体的局部基因进行 混沌扰动，即在近优解区域搜索，协助个体跳出局部优化，以 便快速发现全局最优解。 这里采用著名的 Logistic 混沌映射产生混沌变量。如果 ，由下式得到第 s+1 代值： 变量ω在第 s 代的值为 ω(s) i (s)) 0 < ω (s)(1 - ω i i i i ω (s + 1) = μω < 1  i = 1 2  n （1） 其中，i 是混沌变量序号，s 为迭代次数，μ是吸引子。当μ取作 0Ï{00.250.50.751} 时，上式表现出典型的混沌动 4，且 ω 态特性，使混沌变量初始值的微小变化会导致其长期行为的 显著变化，混沌变量的轨迹可遍历整个遗传规划的搜索空间。 2.2 适应度函数 i 指示变量，其意义分别为： a ihk = = x ijk ì 1，若机器h先于机器k加工工件i í 0，非上述情况 î ì 1，若工件i先于工件j在机器k上加工 í 0，非上述情况 î （4） 2.3 实现方案 （1）编码方式 根据车间调度问题的特点，采用整数染色体编码方法，对 于 n 个工件和 m 台机器的调度问题，染色体的每个基因编码即 为工件在机器上的工序编号，染色体长度与工序个数相同即 n ´ m 个，则每条染色体的组成是一个 [0n ´ m - 1] 的全排列。 例如对于一个 4×3 型调度问题，节点值采用[0，11]之间的整数 表示，如表 1 所示。 表 1 4×3 型调度问题的编码表 n 0 1 2 3 0 0 1 2 3 m 1 4 5 6 7 2 8 9 10 11 任意整数 Num 所代表工序的机器号和工件号由式（5）、式 （6）得出： MacNum = Num div n JobNum = Num mod n （5） （6） （2）混沌初始化 在基本遗传规划中，随机生成的初始群体存在大部分个 体远离最优解的现象，且易产生个体聚集现象，因而限制了算 法的搜索效率。混沌运动具有遍历性和对初始条件的敏感 性，能在一定范围内不重复地遍历所有状态。采用混沌搜索 代替随机搜索，提高初始种群个体的质量，优化了搜索效率。 混沌初始化的基本过程如下：输出一组 n 维随机数作为初 值，利用式（1）产生其余 N - 1 个 n 维的混沌变量，并按式（7）将 N 个混沌变量映射到优化变量的取值范围，筛选出可行解。 j - a + (b = round(a X ij i = 12N；j = 12n 如果 V )R ) ij j j i =[x x i1 x i2 ] 表示问题的一个可行解，对每个 in 可行解使用折半法转换成 XML 二叉树形结构，再分别以前、 中、后序三种方式进行存储，形成三个不同的可行解，这为局 部优化提供更大的搜索范围，通过计算和比较它们的适应值， 选取较优的可行解组成初始群体。 （7） 适应度函数是评价个体优劣的关键指标。本文研究 n 个 工件在 m 台机器上的加工优化问题，已知各工件操作的加工 时间及其在各机器上的加工次序约束、最小化工艺约束条件 相容的各机器上所有工件的完成时间，设计的适应度函数模 型如下： i ik ik F s.t. c c c x }，i = 12n；k = 12m = min max{max C ik + M (1 - a + M (1 - x - p - c ³ 0 i = 12n；k = 12m = 0或1 ij = 12n；k = 12m  i = 12n；hk = 12m ih  ij = 12n；k = 12m jk )³ c ihk )³ p ijk jk ik ik ijk （2） （3） 其中，符号 c 工时间；M 是一个足够大的正数；a 分别为 i 工件在机器 k 上的完成时间和加 分别为指示系数和 和 p 和 x ik ik ihk ijk （3）自适应权重设计 权重设计实质上是一种进化压力调整。个体权重决定了繁 殖数量，个体越好，权重越大，则被繁衍的机会越大。标准的遗 传算法经过多次迭代之后，个体适应度易趋向一致，出现近亲繁 殖现象，对群体进化不利。如果进化群体自适应改变进化压力， 适当增加较弱个体的繁殖比率，能增强全局寻优的能力。 在本文设计的自适应权重方案中，权重值根据式（8）随代数 而调整。为便于计算权重值，按式（9）对原始适应度值进行调整。 = W i 2 a 2 a ) , a > 0 （8） ) i ( 1 F å ( 1 F N i = 1 i 

周 强，崔逊学：一种求解车间调度问题的混沌遗传规划方法 2011，47（12） 231 = b + OldF F i - BestF, b > 0 （9） 表示原始适应度值，BestF 表示当前最优适应 i 式（9）中 OldF 度值，a 和 b 用于调整权重。 i （4）混沌遗传算子 遗传规划以树型层次结构来表示染色体，基因是不能重 复的工序编号。由于调度问题的工序数相同，因而每棵树中 节点数量也相同。 树型染色体执行如下三种操作算子： ①节点变异。在一棵树中根据混沌序列选择两个节点的 值进行交换。 ②子树变异。如果子树的根节点没有祖先和后代的关 系，则利用混沌序列从一棵树中选取两个子树进行互换。 ③嫁接交叉。选取两棵树作为父代，采用混沌序列从一 棵捐赠树中确定一个子树，将其嫁接到接收树中，嫁接后树节 点个数不改变，且树中每个节点的值不重复，否则为非法个 体。为了保证个体的合法性，在嫁接操作之前，先在接收树中 删除与捐赠子树中值相同的节点。 这里执行嫁接交叉操作时，接收树中被删除的节点分为 三类，分别是叶子节点、叶子双亲节点、最多有 1 个后代的节点 的父节点。如果父节点被删除，则按层序遍历选择第 1 个最多 有 1 个后代的子节点取代父节点（如图 1 所示）。若无法嫁接， 则在捐赠树中根据混沌序列选择新的分枝。 0 0 少任一非最优个体的繁殖数；如果 å N i = 1 非最差个体的繁殖数。 NKid i < N ，则增加任一 ⑤将每代最优个体直接复制到后代种群，确保每代的最 优个体性能不再下降，同时在判断出种群发生早熟时，对染色 体的局部基因进行混沌扰动。 ⑥在节点变异、子树变异和嫁接交叉三种操作算子中，根 据各自概率选择执行一种遗传操作即可保持整体进化效果。 例如，利用混沌序列根据节点变异概率 Pn选择两个节点进行 交换；根据子树变异概率 Ps和混沌序列，选择两棵子树进行交 换；根据嫁接交叉概率 Pg和混沌序列选择一棵有效的捐赠树 嫁接到接收树。 （4）计算个体适应值（Fi）。 （5）gen=gen+1，如果 gen N， i 测试 1 执行标准测试集 FT06。测试样本数为 50，a、b 初 始值为 1。测试实验中使节点变异概率从 0 递增至 0.4，增量为 0.05；子树变异概率从 0 递增至 1，增量为 0.1；嫁接概率从 0 递 增至 1，增量为 0.05。三种概率之和被约束为 1，每种概率组合 的程序运行 200 代。 该测试的结果表明，节点变异、子树变异和嫁接交叉的概 率分别为 0.4、0.4、0.2 时，可很快达到全局最优解 54。这表明 高概率的节点变异和子树变异比高概率的嫁接操作能产生更 好的解。由于树中叶子节点和小分支的数量相对较多，因而 被交换的概率较大。节点变异和子树变异对表现型影响较 小，增强了局部搜索的性能；嫁接交叉是将捐赠树的分支嫁接 到接收树，使树结构变化较大，对表现型影响较大，增强全局 搜索的性能。 测试 2 执行标准测试集 ABZ6。随着测试集规模的增加， 将节点变异概率的变化范围扩展为 0  0.8，每种概率组合运行 500 代。 该测试的结果显示，节点变异、子树变异和嫁接交叉的概 率分别为 0.6、0.2、0.2 时，可很快达到最优解 932，比原有最优 解 943 有了显著提高。 以上两组测试结果都反映出不同规模的测试集要采用不 同的算子概率组合，当局部搜索和全局搜索的比率为 4∶1 时， 它们均可很快获得全局最优解。 3.2 结果与分析 （1）FT06 和 LA01 调度问题 FT06 调度问题是 6 个工件和 6 台机器，LA01 调度问题是 10 个工件和 5 台机器。采用测试中使用的节点变异、子树变异 和嫁接概率取值 0.4、0.4 和 0.2。这两个调度问题分别独立运 

232 2011，47（12） Computer Engineering and Applications 计算机工程与应用 80 70 60 50 40 30 20 10 0 值 价 评 最优值 平均值 1 11 21 31 41 51 61 71 81 91 101 代数 （a）FT06 问题 值 价 评 1 000 900 800 700 600 500 400 300 200 100 0 1 最优值 平均值 11 21 31 41 51 61 71 81 91 101 代数 （b）LA01 问题 图 2 FT06 和 LA01 调度问题的计算结果 2 000 1 800 1 600 1 400 1 200 1 000 800 600 400 200 0 值 价 评 1 600 1 400 1 200 1 000 800 600 400 200 0 值 价 评 最优值 平均值 1 600 1 400 1 200 1 000 800 600 400 200 0 值 价 评 最优值 平均值 最优值 平均值 1 1 5 1 0 1 1 5 1 1 0 2 1 5 2 1 0 3 1 5 3 1 0 4 1 5 4 1 0 5 1 5 5 1 0 6 1 5 6 1 0 7 1 5 7 1 0 8 代数 1 1 5 1 0 1 1 5 1 1 0 2 1 5 2 1 0 3 1 5 3 1 0 4 1 5 4 1 0 5 1 5 5 1 0 6 1 5 6 1 0 7 1 5 7 1 0 8 代数 1 1 5 1 0 1 1 5 1 1 0 2 1 5 2 1 0 3 1 5 3 1 0 5 1 5 5 1 0 6 1 5 6 1 0 7 1 5 7 1 0 8 1 0 4 1 5 4 代数 （a）ABZ5 问题 （b）ABZ6 问题 （c）LA16 问题 图 4 ABZ5、ABZ6 和 LA16 调度问题的计算结果 行 10 次，最大进化代数为 100。 测试 FT06 问题时，经过 59 代即可达到最优解 54，用时 40.5 s；测试 LA01 问题时，经过 50 代即可达到最优解 663，用时 40.2 s，实验结果如图 2 所示。该图所示为 FT06、LA01 在一次 测试中最优值与平均值随代数变化的情况。图 3 所示为 FT06 和 LA01 调度问题求解结果对应的机器操作甘特图，表明本文 算法在求解该类问题时的强搜索能力。本文调度问题的历史 记录最优解值均来源于文献[1]。 3 6 9 23 25 5 12 28 1 0 2 4 11 10 7 8 15 20 17 18 21 29 26 35 33 （a）FT06 问题的最优解（本文算法为 54，历史记录为 55） 32 30 31 13 16 14 19 22 24 27 34 4 17 22 1 13 5 10 26 2 0 18 15 27 24 3 7 12 29 11 14 6 8 19 9 16 25 21 20 23 28 35 34 38 32 39 31 30 33 36 37 42 49 46 47 （b）LA01 问题的最优解（本文算法为 663，历史记录为 666） 41 40 45 48 43 44 图 3 FT06 和 LA01 问题最优调度对应的甘特图 （2）ABZ5、ABZ6 和 LA16 调度问题 针对 ABZ5、ABZ6 和 LA16 调度问题，采用测试过的节点 变异、子树变异和嫁接概率取值 0.6、0.2 和 0.2。每次实验分为 两组：第一组中 a 和 b 的取值为 1，运行 800 代；第二组中每 200 代调整一次权重，a 从 1 增加到 4，步长为 1，b 由 1 增加到 13，步 长为 4，共运行 800 代。两组实验分别独立运行 10 次。第二组 实验的目的是为了验证本文权重变化方案的效果。 图 4 所示为 ABZ5、ABZ6 和 LA16 在一次测试中最优值与 平均值随代数变化的情况。图 5 所示为 ABZ5 和 LA16 在最优 解为 1 209、899 个时间单位对应的机器操作甘特图。结果表 示本文调度算法能在有限代数和时间内完成优化求解任务。 8 19 5 16 29 22 4646 48 9 23 32 13 28 37 41 54 47 55 4 11 27 36 40 7 15 26 31 43 50 1 18 33 52 0 14 21 38 42 57 25 49 6 17 3 12 20 39 30 2 35 34 53 56 51 5959 10 24 45 71 77 68 69 61 73 80 95 （a）ABZ5 问题的最优值（本文算法为 1 209，历史记录为 1 234） 72 89 62 74 79 82 87 96 81 98 85 92 84 93 65 67 64 63 78 76 70 83 88 86 99 94 90 91 60 75 97 44 58 66 0 7 14 3 12 2 16 4 18 23 11 29 1 13 27 32 36 49 42 37 48 17 26 41 59 60 73 82 98 50 65 54 61 68 70 89 85 80 87 91 64 77 84 90 92 72 86 93 6 5 8 15 10 9 19 24 38 21 39 47 34 45 57 67 66 78 76 25 22 20 28 30 40 44 33 31 35 43 46 555 56 52 53 51 62 63 69 79 71 81 83 97 99 96 94 75 74 88 95 （b）LA16 问题的最优值（本文算法为 899，历史记录为 945） 图 5 ABZ5 和 LA16 问题最优调度对应的甘特图 表 2 列出了实验结果统计，与标准的遗传算法（GA）进行 量化比较，发现： （1）本文算法在求解上述五个标准问题时，求解结果优于 其他算法，除了明显优于标准遗传算法外，还优于文献[8]提出 的 MGA 算法、文献[9]提出的 SA 算法和文献[10]提出的 TS 算 法。尽管本文算法在混沌序列和混沌遗传算子的处理上需要 花费一定时间，但从实验结果来看，总体计算时间并不长，可 适用于实际的车间作业调度问题。 （2）实验 2 中方法 2 的最优值略优于方法 1，反映出在进化 200 代后，如果降低个体的权重差距，即减少优良个体的繁殖 数量同时提高较差个体的繁殖数量，可在有限时间内产生出 更好的解。 （3）实验 2 中两种方法产生的结果平均值互有高低，表明 虽然改变权重有可能产生优解，但不排除产生劣解。例如 LA16 问题的实验结果表明，方法 2 的最优值 899 优于方法 1 的 

周 强，崔逊学：一种求解车间调度问题的混沌遗传规划方法 2011，47（12） 233 907，但平均值 930 却高于方法 1 的 929，说明方法 2 另外 9 次实 验的结果平均比方法 1 多两个时间单位。总体来看当改变权 重时，平均值会短暂增加，因为权重变化使适应值差的个体得 到较多的繁殖机会。尽管它允许部分评价值差的个体能得到 繁殖，但增加了个体跳出局部最优解的概率，提高了算法的全 局优化性能。 表 2 调度算法性能的实验结果统计 国际当前已 知最优解[1] 本文方法 1 本文方法 2 最优解 平均解 最优解 平均解 经典遗传算法 最优解 平均解 55 666 1 234 943 945 54 663 1 211 941 907 57 663 1 243 970 929 1 209 932 899 1 230 955 930 55 666 1 239 947 946 55 666 1 259 965 977 问题 规模 FT06 LA01 ABZ5 ABZ6 LA16 6，6 10，5 10，10 10，10 10，10 实验1 实验2 4 结论 针对作业车间调度这一经典的 NP-hard 组合优化难题，提 出了一种基于混沌遗传规划的调度算法。主要思想是利用遗 传规划进行染色体的结构设计，采用混沌序列改善初始种群 质量，利用混沌扰动来维持进化群体的多样性，并自适应调整 个体权重，使得算法具有优良的综合求解性能。通过一些标 准作业调度问题的测试集进行仿真实验，表明此算法对典型 的标准调度测试问题具有较强的全局搜索能力，甘特图表明 其获得的最优解优于当前已知的最优解历史记录，对比结果 表明了该方法的有效性。 参考文献： [1] 王凌.车间调度及其遗传算法[M].北京：清华大学出版社，2003. [2] Yamada T，Nakano R.A genetic algorithm applicable to large-scale job-shop problems[C]//Proc of the 2nd International Workshop on Parallel Problem Solving from Nature，Amsterdam，North Hol- land，1992：281-290. [3] 张长胜，孙吉贵，杨轻云，等.一种求解车间调度的混合算法[J].自 动化学报，2009，35（3）：332-336. [4] 宋晓宇，曹阳，孟秋宏.求解Job Shop调度问题的粒子群算法研究[J]. 系统工程与电子技术，2008，30（12）：2398-2401. [5] 徐新黎，王万良，吴启迪.改进计算能量函数下作业车间调度的混 沌神经网络方法[J].控制理论与应用，2004，21（2）：311-314. [6] Tomassini M，Luthi L，Giacobini M，et al.The structure of the genetic programming collaboration network[J].Genetic Program- ming and Evolvable Machines，2007，8（1）：97-103. [7] 李德毅，杜鹢.不确定性人工智能[M].北京：国防工业出版社，2005. [8] Martyn M T，Zatloukal P D，Source M.Visualization and analy- sis of interfacial instability in coextrusion of LDPE melt[J].Plas- tics，Rubber and Composites，2004，33（1）：27-35. [9] Vaddiraju S R，Kostic M，Reifscheider I，et al.Extrusion simula- tion and experimental validation to optimize precision die de- sign[C]//ANTEC，2004，1：76-80. [10] Rincon A J，Hrymak A N，Vlachopoulos J.Transient finite ele- ment analysis of generalized Newtonian coextrusion flows in complex geometries[J].International Journal for Numerical Meth- ods in Fluids，1998，28（8）：1159-1181. （上接 224 页） 计数据质量问题对挖掘结果的影响，从而为挖掘的可行性分 析提供指导。本文首次针对电信业欠费挖掘主题，提出一个 数据质量评估体系 TIM-DQAS，针对电信欠费挖掘主题下的 分类，从缺失和离群两方面对数据质量进行评估。TIM-DQAS 着重分析了不同属性的缺失和非平衡数据中的离群现象对分 类结果的影响，并提出基于类分布的属性加权算法 CAWA、基 于属性加权的缺失评估算法 AMEA 和非平衡离群评估算法 IOEA 对这种影响进行量化，进而给出评估得分的计算方法， 形成一个较为完整的评估体系，并结合行业经验给出了欠费 挖掘评估得分的参照值。实验证明，评估得分向量及其参照 值能够合理量化缺失和离群对分类结果的综合影响程度，对 电信欠费挖掘的可行性提供支撑。 参考文献： [1] Vassiliadis P，Simitsis A，Skiadopoulos S.Conceptual modeling for ETL processes[C]//Proceedings of the 5th ACM International Workshop on Data Warehousing and OLAP，McLean，Virginia， USA，2002：14-21. [3] Pipino L L，Lee Y W，Wang R Y.Data quality assessment[J].Com- munications of the ACM，2002，45（4）：211-218. [4] 韩京宇，徐立臻，董逸生.数据质量研究综述[J].计算机科学，2008， 35（2）：1-5. [5] Chawla N V，Japkowicz N，Kotcz A.Editorial：Special issue on learning from imbalanced data sets[J].ACM SIGKDD Explora- tions Newsletter，2004，6（1）：1-6. [6] 高嘉伟，梁吉业.非平衡数据集分类问题研究进展[J].计算机科学， 2008，35（4）：10-13. [7] Johnson T，Dasu T.Data quality and data cleaning：An overview[C]// Proceedings of the 2003 ACM SIGMOD International Confer- ence on Management of Data，San Diego，California，USA，2002. [8] Even A，Shankaranarayanan G.Utility-driven assessment of data quality[J].The DATA BASE for Advances in Information Sys- tems，2007，38（2）：75-93. [9] 魏藜，宫学庆，钱卫宁，等.高维空间中的离群点发现[J].软件学报， 2002，13（2）：280-291. [10] Karypis G，Aggarwal R，Kumar V，et al.Multilevel hypergraph partitioning：Application in VLSI design[C]//Proceedings of the 34th annual Design Automation Conference，Anaheim，Califor- nia，United States，1997：526-529. [2] Wang R Y，Storey V C，Firth C P.A framework for analysis of data quality research[J].IEEE Transactions on Knowledge and Da- ta Engineering，1995，7（4）：623-640. [11] Kerber R.ChiMerge：Discretization of numeric attributes[C]//Pro- ceedings of 9th Conference in Artificial Intelligence，San Jose， California，United States，1992：123-128.