迁移式并行遗传算法求解支持向量机反问题

论文摘要

支持向量机(SVM)反问题的研究内容是：给定一个未知类属性的事例集,可将其随机分为二部分,如何划分才能使得这两部分之间的间隔最大。求解支持向量机反问题的意义重大。比如,在决策树的学习算法中,使用SVM的最大间隔替代最小信息熵,作为启发式信息,这将大大改善决策树的泛化能力。求解支持向量机反问题,可得SVM的最大间隔。但是,其解法的时间复杂度较高。为在实际应用中得到有效的应用,必须提高算法的求解效率。本文借助高性能计算集群,提出了一种用于求解SVM反问题的迁移式并行遗传算法。本文首先探讨求解支持向量机反问题的基本遗传算法的串行处理过程,并分析了该算法的时间复杂度及各算子的耗时情况；然后,通过分析串行处理过程中的可并行性,结合集群系统,设计一种求解SVM反问题的并行算法：迁移式并行遗传算法。最后,给出了本文算法在集群系统上的实现过程及其测试结果,测试数据表明算法是可行的和有效的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题来源及意义
• 1.2 国内外研究状况
• 1.2.1 支持向量机
• 1.2.2 遗传算法
• 1.3 主要研究内容
• 第2章 支持向量机
• 2.1 最优分类超平面
• 2.2 线性支持向量机解决线性可分问题
• 2.3 线性支持向量机解决线性不可分问题
• 2.4 非线性支持向量机
• 第3章 遗传算法
• 3.1 基本概念及算法描述
• 3.1.1 基本概念
• 3.1.2 基本遗传算法描述
• 3.2 并行化途径
• 3.2.1 主从式并行化方法
• 3.2.2 迁移式模型
• 3.2.3 细粒度模型
• 第4章 支持向量机反问题及其串行解法
• 4.1 支持向量机反问题
• 4.2 支持向量机反问题的串行求解算法
• 4.2.1 算法流程及说明
• 4.2.2 实验结果及耗时分析
• 第5章 求解支持向量机反问题的迁移式并行遗传算法
• 5.1 迁移式并行遗传算法
• 5.1.1 算法背景
• 5.1.2 算法设计
• 5.2 实现与性能分析
• 5.2.1 实验环境
• 5.2.2 并行实现
• 5.2.3 实验结果
• 第6章 总结与展望
• 参考文献
• 攻读硕士学位期间撰写的论文
• 致谢