88 APPENDIX 1 WORKING PRINCIPLE OF GENETIC ALGORITHM A1.1 OVERVIEW OF GENETIC ALGORITHM In the genetic algorithm a solution, i.e., a point in the search space is represented by a finite sequence of zeros and ones, called a chromosome. Figure A.1.1 presents the pseudo-code of the working of a simple GA. First, a population of strings representing the decision variables is randomly generated. The size of the population depends on the string length and the problem being optimized. Each string is then evaluated using the objective function value. In GA terminology, the objective function value of a string is known as the “fitness” of the string. This evaluation function acts as a pseudo-objective function, since it is a raw measure of the solution value. For constrained optimization problems, the evaluation function typically comprises a weighted sum of the objective and penalty functions to consider the constraints. This approach allows constraints to be violated, but a penalty depending on the magnitude of the violation is incurred. A highly infeasible individual has a high penalty value and will rarely be selected for the next generation, allowing the GA to concentrate on feasible or near-feasible solutions. Once the strings are evaluated, the three genetic operators; reproduction, crossover and mutation are applied to create a new population. 89 Initialize a population of strings at random Evaluate each string in the population Repeat Reproduction Crossover Mutation Evaluation of the population Until (termination criterion) Figure A1.1 Pseudo-code of working of Genetic Algorithm A1.2 REPRODUCTION The selection of individuals to produce successive generations plays an important role in GA. Reproduction comprises forming a new population, usually with the same total number of chromosomes, by selection from members of the current population, following a particular scheme. The higher the fitness, the more likely it is that the chromosome will be selected for the next generation. There are several strategies for selecting the individuals (e.g roulette wheel selection, ranking methods and tournament selection). Here we use tournament selection (Goldberg 1989). In tournament selection, n individuals are selected in random from the population, and the best of the n is inserted into the new population for further genetic processing. This procedure is repeated until the mating pool is 90 filled. Tournaments are often held between pairs of individuals (n=2), although larger tournaments can be used. Though this scheme selects good individuals for the next generation, it can not guarantee that the best solution obtained survives throughout the optimization process. In other words, the best solution obtained from the GA may not be included in the final solutions, which are clustered towards a solution. To avoid this, the GA is modified such that once an individual with highest fitness among the current generation is found; it will be kept unchanged into the next generation. This process is called “elitism” (Eshelman et al. 1993). A1.3 CROSSOVER OPERATION The crossover operator is mainly responsible for the global search property of the GA. Crossover basically combines substructures of two parent chromosomes to produce new structures, with the selected probability typically in the range of 0.6-1.0. The blend cross operator (BLX- ) is employed in this study. It has an interesting property: the location of the offspring depends on the difference in parent solutions. If the difference between the parent solutions is small, the difference between the offspring and parent solutions is also small. This property of a search operator allows us to constitute an adaptive search. If the diversity in the parent population is large, an offspring population with a large diversity is expected, and vice versa. Thus, such an operator will allow the searching of the entire search space early on (when a random population over the entire search space is initialized) and also allow us to maintain a focused search when the population tends to converge in some region in the search space. The details of BLX- crossover are explained in Chapter 3.3. 91 A1.4 MUTATION Mutation acts as a background operator and it is used to search the unexplored search space by randomly changing the values at one or more positions of the selected chromosome. This is often carried out with a constant probability between 0.001 and 0.01 for each element in the population. In this thesis, the non-uniform mutation operator is applied to the mixed variables with some modifications. After mutation, the new generation is complete and the procedure begins again with the fitness evaluation of the population. A1.5 STOPPING CRITERIA Stopping criteria are the conditions under which the search process will terminate. In this study, the search will terminate if the number of iterations reach the maximum allowable number. 92 APPENDIX 2 Table A2.1 Line Data for IEEE 30-bus system Line Number From Bus To Bus Number Number R X Line flow Limit Line Impedance 1 1 2 0.0192 0.0575 130 2 1 3 0.0452 0.1852 130 3 2 4 0.0570 0.1737 65 4 2 5 0.0472 0.1983 130 5 2 6 0.0581 0.1763 65 6 3 4 0.0132 0.0379 130 7 4 6 0.0119 0.0414 90 8 4 12 0.0000 0.2360 65 9 5 7 0.0460 0.1160 70 10 6 7 0.0267 0.0820 130 11 6 8 0.0120 0.0420 32 12 6 9 0.2080 0.2080 65 13 6 10 0.5560 0.5560 32 14 6 28 0.0599 0.0599 32 15 8 28 0.2000 0.2000 32 16 9 11 0.0000 0.2080 65 17 9 10 0.0000 0.1100 65 18 10 20 0.0936 0.2090 32 19 10 17 0.0324 0.0845 32 20 10 21 0.0348 0.0749 32 21 10 22 0.0727 0.1499 32 22 12 13 0.0000 0.1400 65 23 12 14 0.1231 0.2559 32 93 Table A2.1 (Continued) Line Number 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 Line Impedance From Bus To Bus Number Number 12 12 14 15 15 16 18 19 21 22 23 24 25 25 27 27 28 29 15 16 15 18 23 17 19 20 22 24 24 25 26 27 29 30 27 30 R X 0.0662 0.0945 0.2210 0.1070 0.1000 0.0824 0.0639 0.0340 0.0116 0.1150 0.1320 0.1885 0.2544 0.1093 0.2198 0.3202 0.0000 0.2399 0.1304 0.1987 0.1997 0.2185 0.2020 0.1932 0.1292 0.0680 0.0236 0.1790 0.2700 0.3292 0.3800 0.2087 0.4153 0.6027 0.3960 0.4333 Table A2.2 Generator data for IEEE 30-bus system Bus data Pg min Pg max Qg min Sg max 1 50 200 -20 250 2 20 80 -20 100 5 15 50 -15 80 8 10 35 -15 60 11 10 30 -10 50 13 12 40 -15 60 Line flow Limit 32 32 16 16 16 16 16 32 32 16 16 16 16 16 16 16 65 16 94 Table A2.3 Transmission Line Data for IEEE 118-bus system Rating Transmission lines (MVA) 4-5,8-9,8-5,9-10,15-17,23-25,26-25,25-27,30-17,26-30,3437,38-37,60-61,63-59,63-64,64-61,38-65,64-65,49-66,49- 500 66,65-66,65-68,68-69,69-70,69-75,77-80,77-80,68-81,8180,85-86,86-87,88-89,89-90,89-92,89-92,100-103,32-113,68116 8-30,80-99 200 1-2,1-3,3-5,5-6,6-7,4-11,5-11,11-12,2-12,3-12,7-12,11-13,1214,13-15,14-15,12-16, 16-17,17-18,18-19,19-20,15-19,2021,21-22,22-23,23-24,27-28,28-29,17-31,29-31, 23-32,3132,27-32,15-33,19-34,35-36,35-37,35-37,34-36,37-39,3740,30-38,39-40, ,40-41,40-42,41-42,43-44,34-43,44-45,4546,46-47,46-48,47-49,42-49,42-49,45-49, 48-49,49-50,4951,51-52,52-53,53-54,49-54,49-54,54-55,54-56,55-56,5657,50-57, 56-58,51-58,54-59,56-59,56-59,55-59,59-60,5961,60-62,61-62,62-66,62-67,65-66, 66-67,47-69,49-69,2470,70-71,24-72,71-72,71-73,70-74,70-75,74-75,76-77,69-77, 75-77,77-78,78-79,79-80,83-84,83-85,84-85,85-88,85-89,9091,91-92,92-93,92-94, 93-94,94-95,80-96,82-96,94-96,8097,80-98,92-100,94-100,95-96,96-97,98-100,99-100,100101,92-102,101-102,100-104,103-104,103-105,100-106,104105,105-106 105-107,105-108,106-107,108-109,103-110,109110,110-111,110-112,17-113,32-114,27-115,114-115,12117,75-118,76-118. 175 95 Table A2.4 Generator Data for IEEE 118-bus system Bus no Pg (MW) Bus no Pg(MW) Bus no Pg(MW) 10 450 54 48 87 4.0 12 85 59 155 89 607.0 25 220 61 160 100 252.0 26 314 65 391 103 40.0 31 7.0 66 392 111 36.0 46 19 69 516 49 104 80 477 96 APPENDIX 3 MULTI-OBJECTIVE OPTIMIZATION PROBLEM A general multi-objective design problem is expressed by equation (A3.1) Min F ( x) [ f1 ( x ), f 2 ( x),..... f k ( x)] Subject to (A3.1) x S x=(x1,x2,…xn)T where f1(x), f2(x)….. fk(x) are the k objective functions , (x1,x2,….xn) are the n optimization parameters, and S Rn is the solution or parameter space. Obtainable objective vectors, {F(x)| x S}, are denoted by Y, so S is mapped by F onto Y. Y Rk is usually referred to as the attribute or criteria space, where Y is the boundary of Y. For a general design problem, F is non-linear and multi-modal, and S might be defined by non-linear constraints and may contain both continuous and discrete member variables. f1* , f 2* ,......., f k* will be used to denote the individual minima of each objective function respectively. The utopian solution is defined as F * f1* , f 2* ,......., f k* . As F* minimizes all objectives simultaneously, it is an ideal solution, however it is rarely feasible. In this formulation, minimize F(x), lacks clear meaning as the set {F(x)} for all feasible x lacks a natural ordering, whenever F(x) is vector-valued. In order to 97 determine whether F(x1) is better then F(x2), and thereby order the set {F(x)}, the subjective judgment from a decision-maker is needed. One property commonly considered as necessary for any candidate solution to the multiobjective problem is that the solution is not dominated. Considering a minimization problem and two solution vectors x, y S. x is said to dominate y, denoted x > y, if: i 1,2,...k : f1 ( x) f1 ( y) and j 1,2,.....k : f j ( x) f j ( y) The Pareto subset of Y contains all non-dominated solutions. The space in Rk formed by the objective vectors of Pareto optimal solutions is known as the Pareto optimal front, P. If the final solution is selected from the set of Pareto optimal solutions, there would not exist any solutions that are better in all attributes. It is clear that any final design solution should preferably be a member of the Pareto optimal set. If the solution is not in the Pareto optimal set, it could be improved without degeneration in any of the objectives, and thus it is not a rational choice. This is true as long as the selection is done based on the objectives only. Pareto optimal solutions are also known as non-dominated or efficient solutions. Figure A3.1 provides a visualization of the presented nomenclature. 98 f2 X2 F(x) f 1* Y Y S * F X1 f 2* p f1 Figure A3.1 Solution and attribute space nomenclature for a problem with two design variables (x1 and x2) and two objectives (f1 and f2) Solution and attribute space nomenclature for a problem with two design variables (x1 and x2) and two objectives (f1 and f2), which should both be minimized. The attribute space, Y, looks the same regardless of how the objectives are aggregated to an overall objective function. Depending on how the overall objective function is formulated, the optimization will result in different points on the Pareto front.