遗传算法与离散粒子群算法在SAT问题上的应用

作     者：王逸君 

作者单位：吉林大学 

学位级别：硕士

导师姓名：欧阳丹彤;董旭初

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：随机优化 模拟进化计算 群智能 

摘      要：对目标函数进行优化(优化问题)的算法,如遗传算法、粒子群算法、蚁群算法等,是在满足一定约束的条件下,确定一系列参数的取值同时应用算法的迭代计算,找到满足优化标准的解。求解优化问题的算法可以分为局部优化算法和全局优化算法。比较著名的局部优化算法有最速下降法,模拟退火算法等,全局优化算法中最重要的一类就是进化算法,本文对遗传算法、粒子群算法和离散粒子群算法的基本思想,发展以及改进作了一个比较详尽的描述。遗传算法(Genetic Algorithm,GA)是一类求解复杂全局优化问题的仿生型算法,广泛的应用于组合优化、机器学习等领域。粒子群算法是一种基于种群的优化算法,它是一种全新的进化算法,它具有进化算法的一些特征,通过粒子之间的信息共享来控制每个粒子在搜索空间的飞行轨迹。相对于一般的进化算法,它的效率更高,运算量更小,目前已经得到了广泛的应用。 本文在第三章提出一种全新的对遗传算法的改进方法,即在基于小生境的遗传算法中增强局部搜索能力,这是对遗传算法提高局部搜索能力的一种全新的尝试。这种方法在迭代次数比价较高的情况下可以得到比标准遗传算法更好的结果。第五章提出在二元离散离子群算法中提高局部搜索能力的一种新的尝试,并使用这两种改进的算法来处理编码在[0,1]空间上的SAT问题。