NEW PSO BASED MEMBRANE ALGORITHMS FOR CHESS, SUDOKU AND OTHER APPLICATIONS

Abstract

Several real world problems can be formulated as optimization models. These optimization models, however, are often complex and intricate posing several mathematical challenges like large dimensions, non-linearity, multimodality, non-convexity, etc. Further, the problems may be subject to restrictions like constrained, discrete, or continuous variables. In fact situations may arise where the mathematical nature of the problem is not properly defined. Consequently, researchers have focused their attention on general purpose algorithms that can deal with a wide range of problems irrespective of the mathematical nature/complexities of the problem. In the past few decades, focus is laid on nature inspired algorithms (NIA), which is due to their simple structure have become quite popular with researchers dealing with complex and intricate problems. NIA are based on the self-organizing collective processes in nature and human artefacts like natural evolution or socio-cooperative behavior of natural species like birds, ants or bees. These techniques are found to be promising due to their ability to adapt themselves in the continuously changing environment. The scope of this Thesis include the study and development of an efficient natural computing paradigm namely, Membrane Algorithms. In general, these algorithms are designed by defining the evolution and communication rules and set of objects to be evolved within the parallel and distributed framework of P-systems. This Thesis, however, focuses on the specific type of Membrane Algorithms, i.e. Particle Swarm Optimization (PSO) based Membrane Algorithms, which uses the update equation of PSO as their evolution rules. Due to its parallel nature, these algorithms are best suited for computationally complex problems. Also, as membrane algorithms have no fixed set of evolution rules, the problem specific set of rules can be defined within their framework. The study of relevant literature indicates existence of only six PSO based Membrane Algorithms all of which are used for continuous function optimization. The main contribution of this thesis includes the proposal of one Membrane Algorithm with deterministic rules specifically designed for problem of Sudoku Solving while one PSO based Membrane Algorithm each for discrete and continuous optimization problems. ii The proposed Deterministic Membrane Algorithm (DMA), for solving Sudoku uses the five deterministic evolution rules, divided into two phases, within the membrane structure of Cell-like P-system having membranes equal to the size of the Sudoku problem to be solved. The PSO based Membrane Algorithm, MA_PSO_M, proposed for discrete problems, although has the evolution rules that can be used for any optimization problems. However, to demonstrate the efficiency of modified PSO rules used in algorithm, it is applied to problem of Sudoku by defining the problem specific search space which itself is a contribution as has been defined in this manner for first time in literature. To further improve the performance of MA_PSO_M for solving Sudoku problem, a deterministic phase comprising of the four rules of previously proposed deterministic membrane algorithm is added to it. Another PSO based Membrane Algorithm, namely M_PSO_MA, proposed for continuous function optimization is designed so as to apply seven different variants of PSO, found to best in various aspect in literature, simultaneously to same problem without directly hybridizing the component. The reason to do so is to avoid the deterioration of property of any variant due to the influence of other in case they are hybridized directly. M_PSO_MA is designed using one-layered cell-like P-system with six elementary and a skin membrane. To demonstrate the effectiveness of M_PSO_MA it is compared with all the existing state-of-art PSO based Membrane Algorithms for both unconstrained and constrained continuous optimization functions. All the algorithms are tested on 30 unconstrained problems of IEEE CEC-2014 and 18 constrained problems of IEEE CEC- 2010 and the obtained results are visualized analytically and statistically to determine the best algorithm. To further analyze the efficiency of these membrane algorithms, all are applied to tune the weights of evaluation function of the designed chess engine. The chess engine is designed with 8 x 8 array board representation searched using minimax algorithm with alpha-beta pruning. The used evaluation function is very basic one based on just material balance and mobility. The evaluation function is trained for 50 generations by each algorithm where each generation includes 20 games played by every individual player against a fixed player. Each player is defined by the values of the weights of its material balance and mobility. The best player obtained after tuning or training by each algorithm is tested by playing 400 games against player with standard weights of the chess theory. These membrane algorithms are also used to solve three constrained engineering design problems and a differential equation namely Blasius Equation. iii To further explore best membrane algorithms for continuous function optimization, figured out on the basis of above experiments, are finally used to train the neural network for classification problem which is used to specify the species of the given Iris Flower. The feed forward neural network having one hidden layer with varied number of nodes is used for the purpose. The hidden transfer function used is hyperbolic tangent while activation function used is softmax with the training conducted using batch method. Based on the present study, the advantages and deformities of each of the existing and proposed PSO based Membrane Algorithms are highlighted. Furthermore, new research directions are also outlined.