膜进化算法是一种抽象于生物细胞结构和活动的进化算法,作为膜计算的应用方向,具有天然的并行框架等特点。在近年来的发展中,被广泛应用于求解各类NP难（Non-deterministic Polynomial Hard）问题并获得了较好的成果。SAT问题（The Satisfiability Problem）是计算机科学的核心问题之一,同时也是首个被证明的NP完全问题,它一直吸引了众多研究人员的关注。3-SAT问题作为SAT问题的一类代表,和计算机科学中的很多领域都有广泛的联系,对计算机理论和人工智能的发展都起着至关重要的作用。目前用于求解3-SAT问题的方法主要分为精确算法和近似算法两类。作为近似算法中最优秀的一类算法,结合配置检测策略的局部搜索算法能很有效地解决随机3-SAT实例,但是效率受制于初始真值指派的优劣。本文研究了求解3-SAT问题的随机局部搜索算法,在给出的3个改进策略的基础上提出了一个基于改进策略的3-SAT问题局部搜索算法ISSATA,提升了3-SAT问题的求解效率。根据膜进化算法的框架,结合3-SAT问题的特点,通过设计膜进化算法的各种算子,本文提出了一个基于膜进化求解3-SAT问题的MEASAT算法,该算法在大型实例中能有更好的效率。同时相关的实验结果也分别说明了ISSATA算法以及MEASAT算法的有效性。本文的主要研究工作包括:1.给出了3个求解3-SAT问题的新策略,形成了新的求解算法ISSATA,包括:利用变量和语句的信息为变量赋初值,使得初始化指派能尽可能的满足更多的语句,从而替代一般局部搜索算法中的随机初始化策略;不完全贪心地选择score值最大的变量,为变量的选择增加随机性,从而避免算法陷入局部最优;当候选变量score值相同时,使用变量所处的语句信息,替代常见的时间戳改进算法效率。得到的ISSATA算法不仅在随机3-SAT测试集上有了较大提升,而且在精心设计的3-SAT数据集上,也表现出了一定的效果。2.针对ISSATA算法在求解大型数据集上的不足,本文结合膜进化算法提出了MEASAT算法。通过组合不同算子,改变算子的执行顺序等,设计出了膜内进化策略和膜间的进化策略,加速算法的收敛从而提升了算法在大型数据集上的效率。