NATURE INSPIRED ALGORITHMS AND THEIR APPLICATIONS

Abstract

Optimization problems arise in various disciplines such as Engineering Designs, Agricultural Sciences, Manufacturing Systems, Economics, Physical Sciences, Pattern Recognition etc. In fact newly developed computational techniques are being used in every sphere of human activity where decisions are to be taken in some complex situations that can be represented by a mathematical model. In view of their practical utility there is a need for efficient and robust computational algorithms, which can numerically solve on computers mathematical models of medium as well as large size optimization problems arising in different fields. Mathematical models of real life problems often turn out to be nonlinear in nature. Such problems may have local as well as global optimal solutions. Global optimal solution is usually more difficult to obtain, as compared to local optimal solution, but in many cases it is advantageous and sometimes even necessary, to search for the global optimal solution. In order to determine the global optimal solution of a nonlinear optimization problem, usually two approaches are followed: (1) The Deterministic Approach and (2) The Probabilistic Approach. Deterministic methods extensively use analytical properties such as continuity, convexity, differentiability etc. of the objective and the constraints to locate a neighborhood of the global optimum. It is now established that deterministic methods are best suited for restricted classes of functions, namely convex functions, one dimensional rational or Lipchitz functions and Polynomials etc. whose mathematical properties can be easily determined and utilized at specified points or in specified intervals. The stochastic methods, on the other hand, utilize randomness in an efficient way to explore the set over which the objective function is to be optimized contrary to general expectation. Stochastic methods perform well in the case of the most of the realistic problems over which these have been tried. In stochastic or probabilistic methods, two phases are generally employed. In the first phase, also called global phase, the function is evaluated at a number of randomly sampled points. In the second phase, also called local phase, these points are manipulated by local searches to yield a possible candidate for a global optima. Although probabilistic methods do not give an absolute guarantee of determining the global minima, these methods are sometimes preferred over deterministic methods, because they are applicable to a wider class of functions as they depend of function evaluations alone and do not assume any mathematical properties of the functions being used. Nature Inspired Algorithms (NIA) are relatively a newer addition to class of population based stochastic search techniques. These algorithms are based on the evolutionary, self organising and collective processes in nature for example the concepts of natural evolution like selection, reproduction and mutation form the key ingredients of certain NIA whereas the socio-cooperative behaviour displayed by natural species like birds, ants, termites and bees (and also human behaviour) form basis of some other NIA. These algorithms seem promising because of their social — cooperative approach and because of their ability to adapt themselves in the continuously changing environment. Some popular NIA include Genetic Algorithms (GA), Ant Colony Optimization (ACO), Evolutionary Programming (EP), Evolutionary Strategies (ES), Particle Swarm Optimization (PSO), Differential Evolution (DE) etc. These algorithms have been successfully applied to several bench mark and real life problems arising in various fields of Science and Engineering. Although, these algorithms give a better performance than the classical optimization techniques in most of the cases, it has been observed that most of the stochastic algorithms have certain drawbacks like slow or premature convergence (resulting in inferior solution), inability to locate a global optima or getting stuck in a local optima. These problems become more persistent in case of multimodal problems i.e. problems with several local and global optima or noisy functions with shifting optima (dynamic optimization problems), i.e. to say problems in which global optima is not static but keeps on changing with time. Keeping in mind the shortcomings of the existing techniques, algorithms are developed/ modified in this Thesis which not only keep a balance between the two antagonist factors; exploration and exploitation (thereby maintaining diversity of the population and preventing premature convergence), but are also be efficient in terms of computational time. In the present study the two stochastic population based search algorithms namely, PSO and DE are considered because of their popularity and wide applicability. In the past few years, these two techniques have emerged as powerful optimization tools for solving complex optimization problems, which are otherwise difficult to solve by the usual classical methods. ii Both PSO and DE have been successfully applied to a wide range of problems including benchmark and real life problems. The objectives of this thesis are: (1) To design efficient and reliable computational techniques based on DE and PSO algorithms for obtaining the global optimal solution of constrained / unconstrained nonlinear optimization problems. (2) To test the proposed algorithms on test problems appearing in literature. (3) To apply the algorithms for solving real life problems arising in various fields of Science and Engineering. Different aspects of PSO and DE algorithms like initialization of population, effect of diversity and inclusion of evolutionary operators (for PSO), modifications in the existing operators (for DE) and hybridization of algorithms are considered in this Thesis and several modifications are suggested for the improvement of these two algorithms in terms of convergence rate without compromising with the solution quality. Finally the algorithms are validated on a set of several test and real life problems. The Thesis is divided into ten chapters. The first chapter is introductory in nature in which definitions and literature t. review are presented. In the second chapter, various analyses are done on the generation of initial population for the PSO and DE algorithms. Uniformly distributed random numbers are generally used for the initialization of population in population based search algorithms. However in the second chapter, the initial population for DE and PSO algorithms is initiated using various probability distributions and low discrepancy sequences. For this investigation, the probability distributions namely: Gaussian (G), Exponential (E), Beta (BT) and Gamma (GA) distributions and the low discrepancy sequences namely: Van der Corput (VC) sequence and Sobol (S) sequence used. Based on the above mentioned distributions and low discrepancy sequences, the following 12 modifications are proposed viz. VC-PSO, SO-PSO, GPSO, EPSO, BTPSO, GAPSO, VC-DE, SO-DE, GDE, EDE, BTDE and GADE. The proposed algorithms are tested on standard benchmark problems and the results are compared with the basic versions of PSO and DE which follows the uniform distribution for initializing the swarm. The simulation results show that a iii significant improvement can be made in the performance of PSO and DE, by simply changing the distribution of random numbers to other than uniform distribution as the proposed algorithms outperform the basic versions by a noticeable percentage. In an overall comparison, the algorithms which follow the Beta distribution and Van der Corput sequence are superior to other algorithms. Chapter 3 deals exclusively with the possible modifications in the PSO algorithm in order to improve its performance. For this purpose other evolutionary operators like mutation and crossover are added to the basic PSO algorithm and the results are recorded. A quantum behaved PSO is also designed in this chapter. In all, chapter 3 consists of several modified versions of basic PSO algorithm. Some of these versions are: ATREPSO, GMPSO, BMPSO, GAMPSO, BGMPSO, QIPSO I, QIPSO2, QIPSO3, QIPSO4, SMPSOI, SMPSO2, GWPSO+UD, MPSO, Q-QPS01, Q-QPSO2, SMQPSO1 and SMQPSO2. The proposed algorithms are tested on standard benchmark problems. The results obtained by these algorithms on all benchmark problems are either superior or at par with the basic PSO algorithm. In an overall comparison, the improved PSO algorithms assisted with Quadratic Interpolation operator (QIPSOs and Q-QPSOs) algorithms gave the best results. Chapter 4 is devoted to the modifications for the DE algorithm. Two new mutant vectors based on the Laplace probability distribution (LDE) and the using the concept of Quadratic Interpolation (DE-QI) are proposed. Five versions of LDE are suggested namely LDE1, LDE2, LDE3, LDE4 and LDE5. Also, an improved version of DE with adaptive control parameters (ACDE) is proposed. The performance of all the proposed algorithms is validated on a set of test problems and the numerical results are compared with basic DE and with two other versions of DE. The numerical results show that the proposed algorithms help in improving the convergence rate up to 50% in comparison to the basic DE and at the same time maintained a good success rate as well. In comparison among all the proposed algorithms, LDE4 and DE-QI are superior with others. Chapter 5 deals with the concept of hybridization of algorithms which is a class of modified algorithms consisting of the integration of two or more algorithms. Three hybrid global optimization algorithms namely DE-PSO, MDE and AMPSO algorithms are proposed. The performance of proposed algorithms are validated on a set of benchmark problems and the iv numerical results are compared with classical DE, PSO, EP and 5 other variants of DE, PSO and EP available in the literature. The numerical results show that the proposed algorithms are either superior or at par with all the compared algorithms in terms of convergence rate and solution quality. In chapter 6, focus is laid on the solution of constrained optimization problems. A new constraint handling mechanism for solving constrained optimization problems is proposed. It is a simple approach for handing constraints which do not require any additional parameters. Based on the new constraint handling mechanism, two algorithms are proposed namely ICPSO and ICDE. The performance of ICPSO and ICDE algorithms are validated on 20 constrained benchmark problems and compared with two other variants (constraint) of PSO and DE in the literature. The numerical results show that the proposed algorithms are quite promising algorithms for solving constraint optimization problems. Chapters 7, 8 and 9 are devoted to real life optimization problems. In chapter 7, the problem is to determine the In-Situ efficiency of Induction Motor without performing no-load test, which is not easily possible for the motors working in process industries where continuous operation is required. This problem is modeled as an unconstrained optimization problem and is framed by four different methods. The differences in the method are based on the number of input parameters used to the optimization algorithms and modifications in the equivalent circuit of the motor. Basic versions of PSO, DE and their 6 variants namely QPSO, ATREPSO, GMPSO, SMPSO1, LDE1 and DE-QI are used to solve this problem. The results obtained by the above mentioned family of PSO and DE algorithms are compared with Genetic Algorithm (GA) and a physical efficiency measurement method, called torque-gauge method. The performances in terms of objective function and convergence time prove the effectiveness of the proposed variants of PSO and DE algorithms used for comparison. In chapter 8, another problem that is quite common in the field of Electrical Engineering is considered. For this problem, the objective is to compute the values of the decision variables called relays, which control the act of isolation of faulty lines from the system without disturbing the healthy lines. This problem is modeled as a nonlinear constrained optimization problem, in which the objective function to be minimized is the sum of the operating times of all the relays, which are expected to operate in order to clear the faults of their corresponding zones. Three cases of the IEEE Bus system are considered viz. IEEE 3-bus, IEEE 4-bus and IEEE 6-bus system. It is a very complex problem and many PSO versions proposed in this thesis were not able to solve it. The problem was finally solved by using the family of DE algorithms namely LDE1, LDE2, LDE3, LDE4, LDE5 and DE-QI. The results obtained by the aforesaid algorithms are compared with the earlier published results. From the numerical and graphical results, it is shown that the proposed DE algorithms used in this study are either best or comparable with the other algorithms both in terms of solution quality and convergence rate. Chapter 9 consists of 12 small real life problems taken from different fields. The Thesis finally completes with Chapter 10, where conclusions based on the present work are drawn and suggestions for future work are made. vi