3-SAT Using Island-based Genetic Algorithm

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2016/12/01

タイトル(英語): 3-SAT Using Island-based Genetic Algorithm

著者名: Salmah Mousbah Zeed Mohammed (School of Computer Sciences, Universiti Sains Malaysia), Ahamad Tajudin Khader (School of Computer Sciences, Universiti Sains Malaysia), Mohammed Azmi Al-Betar (School of Computer Sciences, Universiti Sains Malaysia)

著者名(英語): Salmah Mousbah Zeed Mohammed (School of Computer Sciences, Universiti Sains Malaysia), Ahamad Tajudin Khader (School of Computer Sciences, Universiti Sains Malaysia), Mohammed Azmi Al-Betar (School of Computer Sciences, Universiti Sains Malaysia)

キーワード: Island model concept，Genetic algorithm，3-SAT problem

要約(英語): SAT problem, also known as a three conjunctive normal form (3-CNF), is an expression where every clause consists of exactly three literals but with the unrestricted number of literals and clauses. The 3-SAT problem is known to be an NP-hard and very difficult to solve. Where to solve the 3-SAT is to find an assignment of true or false to each of the literals in the clauses such that 3-SAT expression is evaluated to true. This study implemented the island model genetic algorithm (Island-based GA) to solve the 3-SAT problem. Hence, the solution involves the novel use of Island-based GA to improve the performance of solving 3-SAT problem. The benchmark SAT problems of four suits (URSAT1, URSAT2, URSAT3, and URSAT4) in SATLIB were used to test the performance of the Island-based GA and were compared with MAEA-SAT and Standard GA (SGA). The Island-based GA obtained good results and performance in solving large-scale SAT problems.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.136 No.12 （2016） 特集Ⅰ：電気・電子・情報関係学会東海支部連合大会　特集Ⅱ：国際会議ACIS 2014/2015

本誌掲載ページ: 1694-1698 p

原稿種別: 論文／英語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/136/12/136_1694/_article/-char/ja/