DESIGN AND APPLICATIONS OF NEW HARMONY SEARCH ALGORITHMS

Abstract

Optimization is the process of finding the best alternate solution among a given set of solution under some given constraints. The process of finding maximum or the minimum possible value, which a function can attain in its domain, is known as optimization. One of the most striking trend that emerged in the optimization field is the simulation of natural processes as efficient global search methods. The natural processes or phenomena are firstly analyzed mathematically and then coded as computer programs for solving complex nonlinear real world problems. The resulting methods are called “Nature Inspired Algorithms” that can often outperform classic methods. The advantages of these methods are their ability to solve various standard or application based problems successfully without any prior knowledge of the problem space. Moreover, these algorithms are more likely to obtain the global optima of a given problem. They do not require any continuity and differentiability of the objective functions. Also, they work on a randomly generated population of solutions instead of one solution. They are easy to programme and can be easily implemented on a computer. Some of the examples of Nature Inspired Optimization Techniques are Genetic Algorithm, Particle Swarm Optimization, Artificial Bee Colony Optimization and Ant Colony Optimization. Harmony Search (HS) is a musicians behavior inspired metaheuristic algorithm developed in 2001, though it is a relatively new meta heuristic algorithm, its effectiveness and advantages have been demonstrated in various applications like traffic routing, multi objective optimization, design of municipal water distribution networks, load dispatch problem in electrical engineering, rostering problems, clustering, structural design, classification and feature selection to name a few. The aim of this PhD Thesis is to improve the efficiency and reliability of Harmony Search algorithm in the context of solving real life problems. The organization of this thesis is as follows. Chapter 1 is introductory in nature it states the definitions and underlines the objectives and motivation behind this Thesis. It also reviews the available literature. The chapter closes with a brief summary of the work presented in this Thesis. Chapter 2 introduces a novel algorithm based on hybridization of Harmony search and Simulated Annealing called HS-SA to inherit their advantages in a complementary way and overcome their limitations. Taking the inspiration from Simulated Annealing the proposed HS-SA algorithm accepts even the inferior harmonies, compared to the harmonies already stored in Harmony Memory, with probability determined by parameter called Temperature. The Temperature parameter is initially kept high to i favour exploration of search space and is linearly decreased to gradually shift focus to exploitation of promising search areas. The performance of HS-SA is analyzed and compared with Harmony Search algorithm and Simulated Annealing on IEEE CEC 2014 benchmark functions. The numerical results demonstrate the superiority of the proposed algorithm on multimodal benchmark functions. The performance of HS-SA is particularly outstanding on composition problems. Composition functions are combined, rotated, shifted, and biased version of other unimodal and multi-modal test functions and mimic the difficulties of real search spaces by providing a massive number of local optima and different shapes for different regions of the search space. Chapter 3 introduces Two Phase Harmony Search (TPHS) algorithm that attempts to strikes a balance between exploration and exploitation by concentrating on diversification in the first phase using catastrophic mutation and then switches to intensification using local search in the second phase. Catastrophic mutation allows the evolutionary algorithm to increase diversity in the population on the cost of decreasing convergence speed so as to escape the local optimal. The key differences between standard HS and TPHS are: 1. In TPHS both PAR and BW are linearly decreased whereas both PAR and BW remain constant in standard HS (where PAR is the Pitch adjustment rate and BW is the Bandwidth). 2. The Harmony Memory is re initialized except the elite (catastrophic mutation) if the best harmony is not updated in L generations, where L is predefined number of generations. 3. Towards the end of the execution the algorithm shifts focus to exploitation by performing local search around the best solutions. The performance of TPHS is analyzed and compared with 15 state-of-the-art metaheuristic algorithms namely Standard HS, Improved Harmony Search Algorithm, Global Best Harmony Search Algorithm, Self-adaptive Global Best Harmony Search Algorithm, Evolution Strategy with Covariance Matrix Adaptation, Comprehensive Learning PSO, Adaptive Particle Swarm Optimization, Dynamic Neighbourhood Learning PSO, Heterogeneous Comprehensive Learning PSO, Social Learning PSO, Self Regulating PSO, Social Spider Optimization Algorithm, Differential Evolution, Differential Evolution With Successful Parent Selecting Framework, Dynamic Multi-swarm Particle Swarm Optimizer with Harmony Search on IEEE CEC 2014 benchmark functions. The numerical results demonstrate the superiority of the proposed TPHS algorithm in terms of accuracy particularly on multimodal functions. Chapter 4 introduces Shrinking Memory Harmony Search (SMHS) algorithm, the SMHS attempts to ii strike a balance between exploration and exploitation by concentrating on diversification in the beginning using extended memory and broad Bandwidth and then gradually switching to intensification by shrinking harmony memory and utilizing local search operator. The performance of SMHS is compared with nineteen state-of-the-art metaheuristic algorithms (four HS variants, five PSO variants, eight DE variants, and one variant each of GA and ES). The numerical results demonstrate the superiority of the proposed SMHS algorithm on multimodal function and its performance is outstanding on composition functions. In Chapter 5 the performance of the three proposed algorithms namely HS-SA, TPHS & SMHS is compared on IEEE CEC 2014 benchmark suite and a real life problem called Camera Calibration. The problem of camera calibration has been studied extensively in photogrammetry and computer vision community because of its important applications such as vehicle guidance, robotic navigation and 3D-reconstruction. Camera calibration problem deals with finding the geometrical relationship between the 3D scene and its 2D images taken by two cameras. It defines exactly how the scene has been projected by the camera to result in the given image(s). Camera calibration involves: 1. Determination of the orientation and position of the camera with respect to the scene which is specified by extrinsic parameters. 2. Determination of the internal geometric and optimal characteristics of the camera, which is specified by intrinsic parameters. It is established SMHS is the better performing algorithm on all categories of benchmark functions & Camera Calibration problem. 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 Chapter 6 is to explore the hybridization between Harmony Search (HS) and Hill Climbing (HC) 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). RHSHC perform significantly better than standard Harmony Search algorithm and standard Hill Climber algoiii rithm. On comparing RHSHC with the Genetic Algorithm it has been concluded that former outperforms latter both in terms of effectiveness and efficiency particularly on 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. The maximum clique problem (MCP) is to determine a complete sub graph (clique) of maximum cardinality in a given graph. MCP is conspicuous for having real world applications and for its potentiality of modelling other combinatorial problems and is one of the most studied NP-hard problems. Chapter 7 investigates the capabilities of Harmony Search algorithm for solving maximum clique problem. We propose and compare two different instantiations of a generic HS algorithm namely Harmony Search for MCP (HS MCP) and Harmony Search with idiosyncratic harmonies for MCP (HSI MCP) for this problem. HS MCP has better exploitation and inferior exploration capabilities than HSI MCP whereas HSI MCP has better exploration and inferior exploitation capabilities than HSI MCP, it has been concluded that former performs better than latter by testing them on all the instances of DIMACS benchmark graphs. HS MCP has been compared with a recently proposed Harmony search based algorithm for MCP called Binary Harmony search (BHS) and the simulation results show that HS MCP significantly outperforms BHS in terms of solution quality. Skin, rich in lycopene, is an important component of waste originating from tomato (lycopersicon esculentum) paste manufacturing plants. Lycopene belongs to the carotenoid family, is a bright red pigment that has received great interest due to its various biological activities. Lycopene is a potent antioxidant and has been found effective in reducing the risk of chronic diseases by protecting cells against oxidative damage. Various studies have shown that lycopene is associated with decreasing the risk of breast and prostate cancer. According to the World Processing Tomato Council 1,200,000 tons of tomato processing waste is produced worldwide. One of the main components of tomato processing waste is skin. At present, the tomato processing waste is either discarded or used as animal fodder, but its abundance in lycopene makes it a promising prospect as a sustainable, alternative and low-cost source of this nutraceutical compound. Chapter 8 deals with Optimization of Lycopene extraction from tomato processing waste skin using Harmony Search Algorithm. The Thesis concludes with the Chapter 9. It derives the overall conclusions of this Thesis. It outlines the limitations and scope of the proposed algorithms. Later it suggests future scope and new directions of research in this area.