Harmony search based memetic algorithms for solving sudoku

摘要

The development of hybrid procedures for optimization focuses on enhancing the strength and compensating for the weakness of two or more complementary approaches. The goal is to intelligently combine the key elements of the competing methodologies to create a superior solution procedure. The objective of this paper is to explore the hybridization between Harmony Search and Hill Climbing algorithm by utilizing the exploration power of the former and exploitation power of the latter in the context of solving Sudoku which is a well-known hard combinatorial optimization problem. We call this hybrid algorithm Harmony Search Hill Climber (HSHC). In order to extend the exploration capabilities of HSHC it is further modified to create three different algorithms namely Retrievable Harmony Search Hill Climber (RHSHC), Global Best Retrievable Harmony Search Hill Climber (GB-RHSHC) and Random Best Retrievable Harmony Search Hill Climber (RB-RHSHC). Comparing the four algorithms proposed in this paper RHSHC outperforms its three variations in terms of effectiveness. Experimental results demonstrate that RHSHC perform significantly better than standard Harmony Search algorithm and standard Hill climber algorithm. On comparing RHSHC with the genetic algorithm it has been concluded that former outperforms latter both in terms of effectiveness and efficiency particularly for Hard and Expert level puzzles. Comparing RHSHC and hybrid AC3-tabu search algorithm it has been concluded that RHSHC is very competent to hybrid AC3-tabu search algorithm.