改进蚁群算法在求解加权MAX-SAT问题中的应用

摘要

蚁群算法是一种智能仿生优化算法,具有正反馈性、天然的并行性和较强的鲁棒性、自组织性等优点。蚁群算法是一种根据大自然中的蚂蚁觅食规律形成的人工蚁群算法,根据蚂蚁通过最短路径寻找到食物的原理来求解组合优化问题,利用信息素通信的特点,快速收敛到求解问题的最优值。经过大量的实验研究表明在实际应用中蚁群算法具有很强的适应性和发展前景。
　　 可满足性问题SAT属于命题逻辑中合取范式(CNF),是一个NP-难问题。如今SAT问题是计算复杂性理论研究和人工智能领域研究中的一个核心问题。现在很多领域的研究都离不开SKT问题,比如地质勘探、天气预报、卫星定位系统、机器学习、VLSI集成电路的设计和检测、逻辑推理机等都获得了应用,因此研究可满足性问题就显得具有极其重要的理论意义和现实价值。最大可满足性问题MAX-SAT是SAT问题的一个扩展,有两种形式:一种为满足子句数为研究对象,一种则是子句加权情况为研究对象。本文研究的重点是在加权最大化可满足问题wMSAT中的应用。
　　 本文结合蚁群算法在求解组合优化问题时的优越性,首先提出了运用改进的蚁群算法(IACA)在加权MAX-SAT问题中求解问题,将问题进行重离散化,用取值概率代替信息素机制,提高算法求解的效率和质量,并与经典的搜索算法WALKSKT算法的求解结果进行比较。实验结果表明,改进后的蚁群算法在加权MAX-SAT问题中的应用是行之有效的。
　　 其次,把蚁群算法进行并行化改进,让算法在多核环境下并行化的寻找问题的最优值,再让算法求解加权MAX-SAT问题,并分析并行算法的加速比和效率。和之前的实验结果进行比较,得出并行化的蚁群算法求解问题的时间明显减少,取得了较好的的加速比和效率。