摘要
加权MAX-SAT问题(WMSAT)是一个NP-难问题,针对WMSAT的特点,提出一个改进的蚁群算法。该算法的研究对象由"边"转化为"顶点",简化算法模型;提出取值概率的概念,并以之替换信息素,实现对蚁群进化的直接控制,提高蚁群的可进化性。实验结果表明新算法是有效的。
The weighted MAX-SAT problem（WMSAT） is one of the NP-hard problems. This paper proposed an improved ant colony algorithm according to the features of WMSAT. It changed the studied object of the algorithm from edge to vertex to make the algorithm model simpler. Then proposed the concept of value assignment probability and replaced pheromone with it to improve the evolution ability of ant colony for a more direct controlling. The experimental results show that the new algorithm is effective.
出处
《广西大学学报（自然科学版）》
CAS
CSCD
北大核心
2010年第2期315-319,共5页
Journal of Guangxi University（Natural Science Edition）
基金
国家自然科学基金资助项目(50605010)
广西教育厅科研资助项目(200911LX15)
广西研究生教育创新计划资助项目(105930903042)
关键词
加权MAX-SAT问题
蚁群算法
取值概率
weighted MAX-SAT problem
ant colony algorithm
value assignment probability
