| 【中文题名】 | 遗传算法求解反SVM问题在集群系统上的实现 |
| 【英文题名】 | A Genetic Algorithm for Solving SVM Inverse Problem and Its Implementation on Computer-cluster |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-11-14 |
| 【中关键词】 | 支持向量机,遗传算法,集群系统,并行算法,, |
| 【英关键词】 | support vector machines,genetic algorithms,cluster,parallel algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 决策树的学习算法，比如ID3算法，选用最小信息熵作为启发式信息。用该方法生成的决策树规模小且计算复杂度低，但是泛化能力不佳。考虑到支持向量机(SVM)的分类间隔与泛化能力的关系，可以设想使用SVM的最大间隔作为生成决策树的启发式信息，使得决策树有较强的泛化能力。求解支持向量机反问题，可得SVM的最大间隔。但是，其解法的时间复杂度较高。我们尝试使用遗传算法求解SVM反问题，但当求解问题的规模较大时，其效率也较低，本课题针对如何提高该算法的求解效率做了有意义的探索。
本文在深入分析使用基本遗传算法求解支持向量机反问题的基础上，针对集群系统并行计算环境，提出一种求解SVM反问题的并行算法。首先对求解支持向量机反问题的串行处理过程进行了探讨，并分析了基本遗传算法的时间复杂度及各个算子的耗时情况；然后，通过分析串行处理过程中的可并行性，提出主从式并行处理策略：将耗时占90％以上的评估操作交给各个从结点并行处理，而将耗时很少的选择、交叉和变异等操作交给主结点做全局处理。最后，给出了本文算法在集群系统上的实现过程及其测试结果，测试数据表明算法是可行的和有效的。 |
| 【论文题纲】 |
|
第1章 绪论 |
8-12 |
|
1.1 课题背景及意义 |
8-9 |
|
1.2 研究状况 |
9-10 |
|
1.2.1 支持向量机 |
9 |
|
1.2.2 遗传算法 |
9-10 |
|
1.3 本文研究的主要内容 |
10-12 |
|
第2章 支持向量机及其反问题 |
12-19 |
|
2.1 支持向量机(SVM) |
12-17 |
|
2.1.1 线性SVM |
12-15 |
|
2.1.2 非线性SVM |
15-17 |
|
2.2 支持向量机反问题 |
17-19 |
|
第3章 遗传算法 |
19-31 |
|
3.1 基本遗传算法 |
19-22 |
|
3.1.1 基本概念 |
19-20 |
|
3.1.2 基本遗传算法描述 |
20-22 |
|
3.2 利用基本遗传算法求解SVM反问题 |
22-27 |
|
3.2.1 算法流程及其说明 |
22-24 |
|
3.2.2 实验结果及耗时分析 |
24-27 |
|
3.3 并行遗传算法 |
27-31 |
|
3.3.1 主从式并行遗传算法 |
28-29 |
|
3.3.2 粗粒度并行遗传算法 |
29-30 |
|
3.3.3 细粒度并行遗传算法 |
30-31 |
|
第4章 集群系统中求解SVM反问题的并行算法研究 |
31-38 |
|
4.1 求解SVM反问题的主从式并行遗传算法 |
31-32 |
|
4.1.1 背景 |
31 |
|
4.1.2 算法设计 |
31-32 |
|
4.2 实现与性能分析 |
32-38 |
|
4.2.1 实验环境 |
32-34 |
|
4.2.2 并行实现 |
34-35 |
|
4.2.3 实验结果 |
35-38 |
|
第5章 结束语 |
38-39 |
|
5.1 总结 |
38 |
|
5.2 展望 |
38-39 |
|
参考文献 |
39-41 |
|
攻读硕士学位期间撰写的论文 |
41-42 |
|
致谢 |
42 |
|
| 【DOI】 | LunWen.ID:2.2008.388026 |
