并行蚁群算法求解加权MAX-SAT

摘要

For making the algorithm more direct control, the algorithm more efficient, this paper weighted the characterises of the MAX-SAT, simplified discrete approach to re-model of ant colony algorithm and proposed the concept of probability values , replaced the traditional elements of pheromone ant colony algorithm, finally made parallel improvements of the algorithm. Experimental results show that the new algorithm is more parallel efficiency, reduces the search time significantly, and achieves good speedup and efficiency.%为了使得算法对蚁群进化的控制更加直接、算法更加高效,针对加权MAX-SAT的特点,以重离散化方式简化蚁群算法模型,提出取值概率的概念,并以之替换传统蚁群算法中信息素,最后对该算法作并行化改进.实验结果表明,得到的基于改进后并行化的蚁群算法更具有效性,搜索时间明显降低,取得了较好的加速比和效率.