International Journal of Computational Intelligence Systems

<Previous Article In Issue
Next Article In Issue>
Volume 11, Issue 1, 2018, Pages 402 - 413

An Improved Adaptive Genetic Algorithm for Solving 3-SAT Problems Based on Effective Restart and Greedy Strategy

Authors
Huimin Fu1, *, fuhm6688@qq.com, Yang Xu1, xuyang@swjtu.edu.cn, Guanfeng Wu1, wuguanfengfeng@126.com, Hairui Jia2, *, hairuilover@163.com, Wuyang Zhang1, 1404158954@qq.com, Rong Hu1, 806080468@qq.com
1National-Local Joint Engineering Laboratory of System Credibility Automatic Verification, Southwest Jiaotong University, Chengdu, Sichuan 610031, P.R. China.
2China Academy of Finance Research, Zhejiang University of Finance and Economics, Hangzhou, 310018, China
*Corresponding author.
Corresponding Authors
Received 22 October 2017, Accepted 16 December 2017, Available Online 1 January 2018.
DOI
10.2991/ijcis.11.1.30How to use a DOI?
Keywords
genetic algorithm(GA); adaptive genetic algorithm(AGA); restart; greedy strategy; 3-SAT problems
Abstract

An improved adaptive genetic algorithm is proposed for solving 3-SAT problems based on effective restart and greedy strategy in this paper. Several new characteristics of the algorithm are developed. According to the shortcomings of the adaptive genetic algorithm, it is easy to fall into the premature convergence and destroy optimal individual and make genetic performance decline. An improved adaptive genetic algorithm is proposed to adjust the crossover operator and mutation operator in different stages of evolution dynamically, and make use of the restart strategy to overcome the prematureness. At the same time, the algorithm adopts greedy strategy to make the maximum fitness value of each generation unabated, so as to accelerate the search for the optimal speed. In the experiment, several benchmark SAT problems in SATLIB are used to test the performance of the improved algorithm and the results are compared with those of other similar algorithms. The results show that the improved adaptive algorithm has a higher success ratio and faster solution speed.

Copyright
© 2018, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

<Previous Article In Issue
Next Article In Issue>
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
11 - 1
Pages
402 - 413
Publication Date
2018/01/01
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.11.1.30How to use a DOI?
Copyright
© 2018, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

risenwbib
TY  - JOUR
AU  - Huimin Fu
AU  - Yang Xu
AU  - Guanfeng Wu
AU  - Hairui Jia
AU  - Wuyang Zhang
AU  - Rong Hu
PY  - 2018
DA  - 2018/01/01
TI  - An Improved Adaptive Genetic Algorithm for Solving 3-SAT Problems Based on Effective Restart and Greedy Strategy
JO  - International Journal of Computational Intelligence Systems
SP  - 402
EP  - 413
VL  - 11
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.11.1.30
DO  - 10.2991/ijcis.11.1.30
ID  - Fu2018
ER  -