Teja Project

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Abstract

1

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Abstract This thesis deals with generalized traveling salesman problem (GTSP) which is a variation of the well-known traveling salesman problem (TSP). In generalized traveling salesman problem (GTSP), given a weighted undirected graph D and a partition of vertices of D into V1,V2,...,Vk clusters. We have to find minimum weight cycle containing exactly one vertex from each cluster set Vi, i=1,2,...,k. For solving this NP-hard problem, we are using hybrid approach, which is a combination of steady-state genetic algorithm (SSGA) and local tour improvement heuristics. Generalized traveling salesman problem (GTSP) has many practical applications such as postal routing, computer file sequencing and order picking in warehouses. To deal with GTSP we are using one variation of the genetic algorithm (GA) called steady state genetic algorithm (SSGA). This project is divided into two parts 1. We have studied the approach proposed by Snyder and Daskin (2006) to solve GTSP in which individual has been encoded using random-key encoding in a SSGA framework instead of original generational framework. 2. We have developed our own approach to solve GTSP in which we have used permutation encoding technique to encode an individual. At each generation, order crossover and swap mutation operators have been applied on a SSGA framework.

2

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Contents Acknowledgements Abstract 1.

Introduction

2. Background 2.1

Introduction Evolutionary Computation

2.2

Soft Computing Methods in Optimization

2.2.1 Soft Computing vs. Hard Computing 2.2.2 Soft Computing-Based Optimization: Nature as a Role Model 2.2.3 Capabilities of Evolutionary Computation 2.3 Evolutionary Computation Techniques in Optimization 2.3.1 Generic Evolutionary Computation Algorithm 2.3.2 Solution Presentation 2.3.3 Initial Population 2.3.4 Operators of Evolutionary Computation Algorithms 2.3.4.1

Evaluating the Objective Function Value

2.3.4.2

Introducing Variation into the Solution Population

2.3.4.3

Selection

2.3.5 Genetic Algorithms 2.3.6 Evolution Strategies 2.3.7 Evolutionary Programming 2.3.8.

Artificial Immune Systems 3

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 3.

Generalized Traveling Salesman Problem (GTSP) 3.1.

Introduction

3.2.

Problem Definition Version of GTSP

3.2.1

4.

3.3.

GTSP is NP-Hard

3.4.

Previous Work Related to GTSP

Steady State Genetic Algorithm (SSGA) 4.1.

Introduction

4.2.

Genetic Algorithm Cycle

4.3.

General Structure of GAs

4.4.

Encoding 4.5.1

Random key encoding

4.5.2

Permutation key encoding

4.5.

Evaluation

4.6.

GA operators 4.5.1

Selection

4.5.2

Crossover

4.5.2.1

Uniform crossover

4.5.2.2

Order crossover

4.5.3 4.5.3.1

Replacement Replace worst

4.7.

Diversity and Selection Pressure in SSGA

4.8.

Local Optimization Heuristics

4.9.

4.5.1

2-opt

4.5.2

Swap

Techniques Involved 4.9.1 Algorithm for Selection Process 4.9.2 Algorithm for Iterative Local Search 4.9.3 Psuedo Code of Genetic Algorithm Technique

4

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 5.

Random Key Encoding 4.1.

Introduction

4.2.

Feasibility Solutions

4.3.

GTSP and Random Key

4.4.

Solving GTSP by SSGA 4.5.1

Uniqueness

4.5.2

Crossover

Complexity associated with Random Key

4.5. 6.

Permutation Encoding 6..1

Introduction

6..2

Permutation Encoding and GTSP

6..3

Solving GTSP by SSGA 6.1..1

Order Crossovers

6.1..2

Swap Mutation

Complexity associated with Permutation Encoding

6..4

7 Design and Implementation 7..1 Requirements 7..1.1

Problem Statement

7..2 Requirements Analysis 7..1.2 System Analysis 7..3 Software requirements Specifications 7..1.3 Functional Requirements 7..2.3 Non functional Requirements 7..4 About the software 7..5 DFD Design 7.5.1

Architectural Design

7.5.1.1 Uml Use case Design 7.5.1

Detailed Design

7.5.2.1 DFD Design 7.5.2.2 Sequence Diagrams 5

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 7.5..2.3.

Activity

Diagrams 7.5.2.3 Class Diagrams 8. Testing 8..1

9.

Unit Testing

8.1.1

Black box Testing

8.1.2

White Box Testing

8..2

Integration Testing

8..3

System Testing

Computational Results 9.1. Results of GTSP using SSGA with Random Key Encoding 9.2. Results of GTSP using SSGA with Permutation Encoding 9.3. Comparison of different Approaches

10.

Conclusions

References

6

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

1. Introduction

7

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

1. Introduction Generalized traveling salesman problem (GTSP) is a generalization of the well known traveling salesman problem (TSP). The GTSP was introduced by Henry Labordere in 1960s. TSP is the most commonly used combinatorial optimization problem to solve by researchers. In the traditional definition of TSP we are provided with number of cities and aim is to find a tour, visiting each city exactly once and returning to the starting city such that the length of the tour is minimized. In several TSP variations salesman is allowed to visit only a subset of cities according to some specified criterion, for example, in the prize collecting TSP where each node has an associated prize and a salesman calls for a minimum cost cycle covering a node subset whose total prize is not less than a given value. In such applications one variant of TSP called GTSP is used. In GTSP not all the nodes need to be visited by the tour. GTSP is defined on a weighted graph in which nodes have been pregrouped into m mutually exclusive and exhaustive node sets or clusters. The GTSP is the problem of finding a minimum cost cycle which includes exactly one node from each cluster. GTSP can be reduced to TSP if single node present in each of the cluster. Being a generalization of TSP, GTSP is also NP-Hard problem. GTSP is a useful model for problems involving two simultaneous decisions of selection and sequence. Here we are dealing with the symmetric GTSP. Genetic algorithm (GA) is one of the most commonly used optimization techniques to solve combinatorial optimization problems like the TSP. GA is an evolutionary technique that use crossover and mutation operator to solve optimization problem using a survival of the fittest idea. This technique does not ensure an optimal solution, however it gives good approximation in a reasonable amount of time. Therefore GA is a well studied for NP-Hard problems like GTSP. Here we are going to use one variant of the genetic algorithm called Steady-state genetic algorithm (SSGA). In this paradigm only a single individual is created at each generation. We used a binary-tournament selection strategy with a replace-worst replacement strategy. In Steady-State Genetic Algorithm best solution are always kept in the population and newly generated solution is immediately available for selection so it converges faster. It maintains the diversity of population at each generation, therefore the problem of premature convergence is avoided. As it maintain a single population at any given time and because of faster convergence it requires less computer memory to operate on individuals, therefore it seems to give possible performance improvements by reducing the computational cost. In our project we have first studied the approach given by Snyder and Daskin (2006) in a SSGA framework, that is, we have used SSGA instead of generational GA. Snyder and Daskin (2006) have used the random key encoding technique to encode the solution and a parameterized uniform crossover including local improvement based on the 2-opt discussed by Lin and Kernighan (1972) and swap to boost the solution quality. Random key encoding makes the problem more complex to solve. In our approach we are trying to reduce the complexity using permutation encoding techniques with order crossover. Nearest neighbor criteria to take selection decisions on nodes in clusters and also using swap mutation operator.

8

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

2. Background

9

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

2. Background 2.1 Introduction Evolutionary Computation Evolutionary computation algorithms, a class of nature-inspired optimization methods, have been studied extensively during the last five decades. But using these algorithms for optimization is a multifaceted process, and a lot of research still remains to be done. First, the optimization problem at hand has to be mapped to the EC algorithm so that the optimization algorithm can tackle it effectively. Second, the optimization algorithm usually has to be tailored specifically to match the requirements of the present task to produce the required performance. Third, in many cases multiple techniques have to be compared before a decision is made as to which method is eventually used. The need for ever more powerful, i.e. more application specific, optimization algorithms is clear when we consider the increasingly complicated optimization tasks the modern world offers us.

Fig.1. The three branches of EC research Fig. 1shows the modeling of an optimization problem in a computationally efficient form, the development of application-specific evolutionary algorithms, and the use of a comprehensive statistical scheme 10

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm for evaluating the differences between two separate algorithms. The methods proposed in this dissertation, among others, can be studied either theoretically, empirically, or both. Theoretical proof out powers empirical results and it is naturally desirable, but such comprehensive theoretical results may occasionally be hard, if not impossible, to derive. Evolutionary algorithms are complex stochastic procedures, and often simplifications are required to make theoretical inspection of evolutionary algorithms feasible. Then again, the problem follows of how much the theoretical results achieved using simplifications correspond to reality. Through carefully designed experiments and objectively analyzing the results using proper statistical methods it is possible to draw valuable conclusions regarding the outcome of the research under certain conditions. However, one must be careful when generalizing such results, since empirical results only tell us about the exact process under study.

2.2 Soft Computing Methods in Optimization Optimization is a part of our everyday life. For most everyday problems, and many Engineering ones, convenient deterministic solutions have been created. The current problem parameters are manipulated by a well-defined method, and we obtain an optimal or competitive solution. For example, when designing a digital filter we need to define the passband and stopband characteristics, and there exist various methods for solving the filter parameters in such a way that the design criteria are met. However, in many complex cases there are no methods to determine whether a certain solution is a global extremum unless all the possible solutions are evaluated. In fact, it may even be difficult to know whether a problem is difficult or not in the first place. The global extrema solutions of problems, although theoretically interesting, are usually not required for a practical system to produce satisfactory or even competitive results.

2.2.1 Soft Computing vs. Hard Computing Optimization methods can generally be divided into conventional computing methods, hard computing (HC), and nature-inspired soft computing (SC) methods. HC methods are based on theoretically welldefined practices. Examples of popular hard computing methods in optimization are the steepest gradient approach, linear programming, and Newton’s method. Then again, SC methods, such as evolutionary computation, are considered as a group of methods designed on the basis of the principles of natural phenomena, and HC methods are the opposite of this, namely, methods not directly mimicking natural models.

11

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm Traditional HC methods of optimization usually rely on derivative information, if Such information exists, obtained from the fitness landscape. This term describes the value of different solutions in the solution space. Figures 2a and 2b illustrate two very different fitness landscapes. In Fig. 2a, a simple derivative method, such as Newton’s method, is guaranteed to find the global maximum every time, regardless of the starting point. However, when considering the fitness landscape in Fig. 2b, it is by no means clear where the algorithm will end. The optimum that is found clearly depends on the starting point.

There is a vast reservoir of traditional optimization methods around and these can be summarized into three classes: calculus-based methods, enumeration methods, and random methods. Goldberg describes these classes as follows. Calculus-based methods have been studied extensively and they have been proven to work in a variety of practical problems. Calculus-based methods can be divided into indirect and direct methods. Indirect methods usually solve a set of nonlinear equations that result from the gradient of the objective function being set to zero. An extremum found using this method is usually local. Direct search methods, on the other hand, move towards the local gradient at a certain point. However, both of these methods lack robustness. Robustness in this case means the ability to find competitive solutions despite the difficulty, i.e., multimodality, of the fitness function. Unless some sort of random restart mechanism is added, the calculus-based methods get stuck at the first extremum they find, whether it is global or local. Another severe limitation of calculus-based methods is the fact that they require the objective function to be continuous and that there exists a first, or sometimes also a second, derivative at each point. In many challenging modern-day problems this is usually not the case. For example, when the setup of an electronic circuit is being optimized, there is only a discrete set of components available. Thus, no continuous domain exists and 12

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm therefore neither does derivative information. Enumerative search is a so-called brute force method. This means that the algorithm calculates the objective function values at every point within the search space. Needless to say, this method is very convenient for very small search spaces, but for many problems it rapidly becomes extremely inefficient and basically useless as the dimensions of the problem increase. This is clear when a traveling salesman problem (TSP) is considered, for example. In short, a TSP is solved when the shortest path connecting a given number of cities is found. The problem is easy when the number of cities is small, e.g. of the order of 10. All the solutions can easily be evaluated and the shortest path can be selected. However, even with a moderately large number of cities, say 100, the evaluation process of all the paths becomes very time-consuming. The number of possible solutions is in this case 99!/2. Random search methods take random walks through the search space and they can save the best objective function value encountered. Additionally, HC-based optimization is an active research area, and new research results are frequently introduced at conferences and in journals. The number of difficult optimization problems is increasing all the time in our Everyday life, especially in the engineering sciences. During the last five decades the field of evolutionary computation has pursued the goal of offering nature-inspired solutions to ever more complex optimization tasks that are not reasonably solvable using conventional methods. Evolutionary computation methods are among the fundamental soft computing techniques, and SC, also well justified theoretically, differs from HC in that, unlike HC, it is tolerant of imprecision, uncertainty, partial truth, and approximation. In addition, the capability of SC methods to produce impressive results in difficult optimization tasks is due to the flexibility of these methods in conforming to the current problem. Popular soft computing methods include, in addition to EC, fuzzy logic and neural networks. These methods, although all emerging from nature, have different purposes: NN is used for learning and approximation, FL for approximate reasoning, and EC as a systematic random search.

2.2.2 Soft Computing-Based Optimization: Nature as a Role Model It is common for biological entities to consciously or unconsciously make the things they do better in order to cope with the requirements of the surrounding environment. In other words, they optimize their performance with respect to some measurable or immeasurable characteristics in order to survive or to succeed in some other way. After an optimization process, these optimized biological entities, or any systems in general, are improved in terms of speed, stamina, pleasure, or some other measure that is appropriate for those specific circumstances. In 1859 Charles Darwin described the evolution of species as an optimization process, the primary 13

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm tools of which are variation and selection. Many of Darwin’s findings have been elaborated by the achievements of modern-day science, such as genetics. The basic principles of evolution are easily explained using an example. An animal Population evolves over time and reproduces, creating individuals ever better suited to meeting the demands of the environment. In this case the demands of the surrounding environment constitute the objective function, i.e. the value of the objective function tells us how well each animal survives in the current conditions. Good characteristics of an individual could be, for example, the ability to find food and shelter easily. Good individuals may live longer and get a greater chance of creating offspring and thus passing their characteristics on to new generations. This phenomenon of the survival of the fittest can be described as a process of selection. Reproduction, or passing one’s genes on to the next generation, can be carried out by means of mating, in which both the parents contribute to the genetic or trait characteristics of the offspring, or by means of asexual reproduction. In asexual reproduction descendants are created from a single parent and this kind of reproduction scheme is common, e.g., among plants and fungi. Variation is introduced to the animal population by mixing individuals’ genetic codes in reproduction and, in addition, by a mutation that can randomly alter the genetic code of an individual. Variation is essential for evolution, for if no new genetic material or combinations are introduced into the population, the evolution of the population stops. This mechanism of variation and selection has shaped, e.g., animals from scratch to what they are today. Natural evolution can be translated into a computational optimization technique, as Follows. First, a population of random solutions is created. The population here refers to an animal species in the previous example, where a single solution corresponds to an individual animal. There also needs to be a way to calculate a value of the objective function, i.e. the function that is being optimized, for each and every individual. In nature, individuals struggle or survive, or both, and in EC methods we get an output produced by the objective function that can be arranged into an ordered list describing how good a solution this specific individual is. Reproduction is carried out in EC methods in such a way that a single solution is modified or multiple solutions are combined to create offspring solutions, the characteristics of which are a combination of the characteristics of a single parent or more parents. Additionally, some or all characteristics of the solution can be mutated so as to induce further variation in the solution population. Finally, those solutions that produce the best objective function values have the best chances in probabilistic terms of making it to the next generation to reproduce. This is how variation and selection are implemented in EC methods. 14

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Computational methods based on natural evolution can, for now, only be a pale Shadow of what nature is implementing every day. Still, taking the basic elements of evolution, namely variation and selection, it has been shown that robust and powerful optimization methods can be created. In the context of using natural phenomena as models for optimization, novel paradigms are proposed and accepted, not necessarily for being faithful to their sources of inspiration, but for being useful and feasible. At this point it is necessary to bear in mind that evolutionary computation methods only model evolution and natural behavior from the genetic or trait point of view. The phenotype, the final outcome of an individual in nature, is an extremely complex combination of genetics and environment that is very difficult, if not impossible, to understand and model on the basis of current knowledge. Therefore, evolutionary computation in most cases neglects the effect of environmental factors. The field of evolutionary computation is not fragmenting: rather, it is uniting from Fragments based on different aspects and implementations of variation and selection. The main paths that should finally lead to a unified evolutionary computation field are genetic algorithms (GA), evolution strategies (ES), and evolutionary programming (EP). Evolutionary computation has established its place in the fields of science and engineering, and an impressive but by no means complete list of recent application areas where evolutionary computation has been successfully applied is given below: • Acoustics • Aerospace engineering • Astronomy and astrophysics • Arts • Chemistry • Digital signal processing • Electrical engineering • Financial markets • Gaming • Geophysics • Healthcare • Materials engineering • Mathematics and algorithms • Medical engineering • Military and law enforcement • Molecular biology • Music • Pattern recognition and data mining • Routing and scheduling • Sports • Systems engineering 15

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Domain Control Design Scheduling Robotics Machine Learning Signal Processing Game Playing Combinatorial Optimization

Application Types gas pipeline, pole balancing, missile evasion, pursuit semiconductor layout, aircraft design, keyboard configuration, communication networks manufacturing, facility scheduling, resource allocation trajectory planning designing neural networks, improving classification algorithms, classifier systems filter design poker, checkers, prisoner’s dilemma set covering, travelling salesman, routing, bin packing, graph colouring and partitioning

Although evolutionary computation algorithms have proven to be powerful optimization tools, there is still a great deal to be done in terms of the reliability and robustness of the algorithms and accelerating-problem solving. It has been shown, that if the operators of the evolutionary algorithm fulfill certain requirements, the evolutionary algorithm is guaranteed to achieve the global optimum. The requirements are an elitist selection operator and the capability of a variation operator to transform a solution from any state to any other state. Unfortunately, there are no guarantees regarding the time it takes the algorithm to arrive at such an optimum. Nowadays there is often no time to run an optimization algorithm dozens of times to get a satisfactory result: instead, competitive results should be achieved using as few runs as possible.

2.2.3 Capabilities of Evolutionary Computation Evolutionary computation methods have proven their power in many demanding real world optimization tasks. In many fields there exists a deterministic hard computing based procedure to obtain optimal or nearoptimal methods quite conveniently. If such a solution scheme exists for a particular problem, then such a method should definitely be used, for computationally they usually perform very efficiently. Sometimes, for the reasons described earlier, traditional methods are insufficient, and maybe then EC methods alone or EC methods implemented together with traditional hard computing methods can offer a competitive solution.

2.3 Evolutionary Computation Techniques in Optimization Section 2 described briefly the primary elements of evolutionary computation, i.e. Variation and selection. In this section, these and other 16

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm important evolutionary Computation-related concepts are discussed in more detail. Additionally, some prevailing evolutionary computation techniques, i.e., genetic algorithms, evolution Strategies and evolutionary programming are discussed. Although all evolutionary computation algorithms rely roughly on the same principles of natural evolution, they are occasionally divided into two sub-categories: genotypic algorithms and phenotypic algorithms. Genetic algorithms are considered to be genotypic algorithms, i.e. in simulated evolution the genes, or the parameters of a solution candidate, are transferred through reproduction from generation to generation. Evolution strategies and evolutionary programming, on the other hand, are considered to be phenotypic algorithms. Evolutionary programming mimics the behavior of species and evolution strategies deal with individuals. This means that instead of the actual genes, or parameter values, the traits of the previous generation are passed to the offspring generation without mating. The field of evolutionary computation is constantly developing. The latest information can be found published at the two main conferences in the field: the Genetic and Evolutionary Computation Conference (GECCO) [Gec06] and the IEEE Congress on Evolutionary Computation (CEC). These conferences are among the best places to find out how natural systems are currently mimicked to construct innovative computational optimization schemes.

2.3.1 Generic Evolutionary Computation Algorithm Biologically inspired algorithms vary remarkably in the way data are presented or Which operators are used and how they work. However, eventually they all conform to the theory of Darwin, i.e. the algorithms search for the optimum, using variation and selection as the main operators. Thus, a generic biologically inspired optimization algorithm could be described as follows: 1. Generate an initial population of nI individual solutions to the optimization Problem. 2. Evaluate the objective function value to find out how good each solution is. 3. Introduce variation into the population. 4. Select solutions for the next generation on the basis of their objective function Value so that better solutions have a higher probability of being selected. 5. Go to 2 if solution or run time requirements have not been met. Otherwise exit. A single stage including everything from evaluating the solutions to 17

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm selection is usually called a generation. There exist countless ways to introduce variation and Carry out selection and new approaches can be tailored to conform to the requirements of a specific problem. In the following sections some key issues are discussed in relation to operators used in biologically inspired computation.

2.3.2 Solution Presentation In most EC implementations every individual is a solution, better or worse, to the Problem at hand and EC algorithm operators directly manipulate the structure of these candidate solutions. A co evolutionary scheme is presented in which a population of solutions and a population of test cases are evolved in parallel. The study concluded that using this kind of method, better generalization of the results was achieved in a robot navigation problem. There are no restrictions on the format of the solutions, so the algorithm can easily be adapted to conform to a particular problem. Probably the most common form of solution presentation is the array presentation. Figure 3 shows example solutions to a generic problem. The objective function might have, e.g., 10 variables. Then, each solution is an array of 10 variables, as in Fig. 3. Now the symbols in the solution array can be numbers, discrete or continuous, characters, and symbols or almost anything, as long as we can somehow express how well it solves the problem to be optimized on the basis of the information contained in the solution. This type of solution presentation is most commonly used with genetic algorithms, evolution strategies, evolutionary programming, and the clonal selection principle.

Another commonly used solution presentation format is the tree-like structure shown in Fig. 4. However, this format can also be transformed into an array. This type of individual presentation is most common in conjunction with genetic programming (GP), a subset of genetic algorithms. In genetic programming, the individual solutions are computer programs that are evolved using the principles of simulated evolution. Additionally, in evolutionary programming the solutions can be state machines that can be presented as trees.

18

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Naturally, the form of the solution is not restricted, so one can combine different data types and presentations to solve the problem at hand in the best possible way. The question easily arises as to how the solution should be formatted. Should binary or integer presentation be used? Binary presentation might have an advantage over integer presentation in some problems using certain evolutionary operators, such as single or multi-point crossover, and vice versa. A good guideline is to use such a presentation as the task at hand naturally exhibits. In other words, if it is natural to use binary solutions in a certain application, then there is no need to convert the solutions to some other format in the hope of a superior EC algorithm performance. Solutions of evolutionary computation algorithms are sometimes called individuals, or chromosomes, referring to their biological counterparts. The term chromosome is especially used with genetic algorithms. Figure 5 explains a few of the terms regularly used in conjunction with evolutionary computation algorithms. Different variables in the genetic algorithm solutions are called genes. Other EC algorithms have adopted terms such as variable value or trait value. The genes can have different values, alleles. For example, the values 5 and 10 could be different alleles for a gene. A collection of individuals on which the EC algorithm operates is usually called a population, solution pool, or selection pool.

19

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

2.3.3 Initial Population Generating the initial population is a process of creating nI solutions for the EC Algorithm to start working with. Solutions are usually created by assigning a random variable value to each parameter in each candidate solution. It is important that the mechanism creating random values is capable of covering the whole search space, and that it is not biased if no a priori information concerning a good solution is available. If there is some kind of information concerning particularly appropriate solutions, this information can be taken into account when creating the initial population. These kinds of mechanisms are called seeding. The size of the initial population is directly reflected in the run time of the algorithm, assuming that the population size stays constant throughout the run time of the algorithm. This is simply because the objective function usually has to be evaluated using each solution during each generation, so that the larger the population is, the more objective function evaluations there are, and thus the more time is required.

2.3.4 Operators of Evolutionary Computation Algorithms This section discusses the operators used in evolutionary algorithms. The task of the operator is primarily to introduce variation into the solution population and to conduct selection. The section starts with discussion related to evaluating the objective function value. 20

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

2.3.4.1 Evaluating the Objective Function Value Evolutionary computation algorithms, like many other optimization algorithms, do not need to know anything about the problem they are optimizing. The only requirement is that for each solution there has to be a way to determine how good it is. This evaluation is performed by calculating the objective function value using the variable values of the current solution. This objective function is the function that is being optimized. Depending on whether the objective function is minimized or maximized, it is called a cost function or fitness function, respectively. The terms cost function and fitness functions are commonly used in context with GA, ES, and EP. For AIS optimization the value of the object function is called affinity value. Regardless of whether the task is to maximize or minimize, good solutions have high affinity and less fit solutions have low affinity. Despite the different names, all the values of the objective functions should be presented in numbers, or another directly comparable format. Objective functions can basically be constrained or unconstrained, and continuous or discrete. If the objective function is constrained, then the parameter values lie at some specific interval, e.g. –5 < x < 5. In unconstrained problems such restrictions do not exist. A continuous objective function can basically produce any values, e.g. –3 < y < 3, whereas a discrete objective function can only produce certain values, e.g. y ∈ {-2,-1, 0, 1, 2}. Additionally, the objective function can be dynamic, i.e. it changes as a function of Time. In dynamic environments are divided into three types. In the First type the location of the optimum changes over time. In the second type, the Optimum remains the same, but the value of the optimum changes. Finally, in the third type both the location and the value of the optimum are subject to change. The dynamic objective function can, for example, simulate a real-world situation in which the cheapest route by plane must be found in an environment where flight ticket prices change as a function of time. Traditionally, objective functions have been functions evaluated by computers, but Another very different and interesting approach has been proposed, in which the Fitness of an individual is determined by a human. In other words, a human assigns a solution an objective function value depending on how it matches the characteristics of the solution that specific user is looking for. This kind of EC Involving human-based fitness or cost function evaluation is called Interactive EC (IEC).

2.3.4.2 Introducing Variation into the Solution Population Introducing

variation

into the

solution population

is of crucial 21

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm importance: without Variation the evolution would stop, since no improvement in the candidate material would take place. There are multiple ways to introduce variation, and usually these Methods are classified under the headings mutation and reproduction. These methods can be used separately or together. Furthermore, the variation operators can use one or two individuals or the whole population to produce individuals for the next generation. These kinds of methods are called asexual, sexual, or panmictic operators, respectively. Next, some variation schemes commonly used in evolutionary computation are discussed.

Reproduction The basic principle of reproduction is that from one or more parent solutions the Variation operator creates one or more new individuals. The characteristics of these new individuals are a combination of the parents’ characteristics or an additional Random variation on the parents’ characteristics. A popular form of reproduction is crossover, and this Operator is used especially frequently in genetic algorithms. In Fig. 6, the principle of a simple single-point crossover between two parent solutions is shown. In this case two parents produce two offspring. First, a crossover point is randomly chosen. From this point, the chromosomes are separated and recombined using a part from the other parent. Although a single-point crossover is presented, the method can be implemented simultaneously at multiple points. This type of crossover efficiently passes on the characteristics of the parent solutions to the offspring. On the other hand, this type of reproduction operator is not able to produce new genetic or trait material unless the candidate solution is coded so that the crossover point can split a gene or trait variable. This can happen, for example, when the mantissa and the exponent of a variable are coded in consecutive genes and the crossover point is located between them. Various different types of crossover operators have been studied in the literature, depending on the problem that the specific algorithm is trying to solve. The proposed operator avoids creating offspring that contain closed subpaths in the tour connecting the given cities. This is important, since the solutions to a TSP cannot contain closed subpaths, since such solutions violate the constraint stating that each city must be visited only once. However, Fogel points out that a crossover operator performs poorly in TSP problems in general, whereas gives detailed instructions for designing efficient crossover operators for TSPs. Therefore, it is important to experiment with different operators when tuning an optimization algorithm for a specific problem.

22

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Blending crossover, is a convenient operator with integer and continuous parameter solutions in genetic algorithms. A random number, β, is first selected, and on the basis of this an offspring can be created, as shown in Fig. 7. β is a weighting factor that determines how much emphasis is given to each parent. If β is 0.5, then the offspring produced is the average of the parents.

A single parent can also produce new individuals. In this case, a random variable with known mean and standard deviation can be added to the parent solution to create a new solution, as shown in Fig 8. This type of reproduction is usually used with evolution strategies and evolutionary programming. This type of creation of offspring constantly evolves new material, but, at the same time, is unable to maintain the existing individual characteristics intact. This phenomenon can be fought to some extent using elitism.

23

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm The creation of new individuals does not need to happen every time. pr is the probability of reproduction happening. For example, if reproduction happens, offspring are created according to the rules explained above. If reproduction does not happen, the offspring can be exact copies of the parents without any mixing of the characteristic values. The value of pr is very problem-dependent and can usually be found only through trial and error by experimenting with different values and choosing the most suitable. In some applications it is enough to have the reproduction probability roughly in some region instead of a specific value. This is because the performance of the algorithm is not necessarily so strongly influenced by pr, i.e. the algorithm behaves quite similarly, regardless of whether pr is, and e.g., either 0.80 or 0.85 Genetic programming uses primarily a tree-like representation to describe the structure of a computer program and the dependencies of its different variables. To create offspring, a crossover between two or more trees can take place. In such a crossover the trees exchange sub-trees at random locations. This section discussed some of the most commonly used operators for creating new individuals from existing ones. Some other operators also exist, both general-purpose and application-specific operators. There are few restrictions on the characteristics of the reproduction operator: the offspring can be created from the parents using many sorts of means. To select the parents, selection mechanisms similar to those used in selecting individuals for the next generation can be used.

Mutation Mutation is another way of producing variation in the solution pool, in addition to that offered by reproduction operators. Mutation operators essentially add a random change or changes to variables of a solution. The mutation operator should be able to produce any parameter value within the search space. Usually, the same kind of mechanism can be used to mutate solutions as is used to create parameter values in the initial population. When dealing with binary solutions, the easiest and most commonly used mutation operator is the so-called bit flip operator. As shown in Fig 9, a single bit can be reversed to create variable diversity in the solution pool.

A mutation operator can also be created by substituting a random 24

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm parameter value for a single one, just as when creating an initial population. This procedure is shown in Fig. 10. Similarly, for example, a random variable can be subtracted or added to a parameter value in order to mutate it

Mutation can drastically change the fitness of an individual, regardless of whether the individual was fit or less fit before the mutation. This means that the best current solution can in some cases be so badly degenerated that the selection operator excludes it from the next generation. This kind of phenomenon can hinder or slow down the convergence of the evolutionary algorithm. To compensate this problem, elitism can be applied. Elitism can mean that what is currently the best solution is never mutated so that its fitness value would decrease. Genetic programming primarily uses a mutation method similar to that shown in Fig 11. In mutation the tree-like structure encounters a variation at some node. At this node a random sub-tree is created. Other types of variations may include the addition of a node or sub-tree, removal of a node or sub-tree, or modification of a single variable-value character.

25

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Just like reproduction, mutation does not necessarily happen every time. pm, the Mutation probability, describes the probability that a single solution or a single Variable of a solution is mutated. If mutation should take place, the algorithm proceeds as stated above; if not, the solution is left as it is. The mutation probability can also be determined experimentally. In artificial immune systems mutation is used widely as a variation operator. However, the parent solution is not mutated directly; rather, a number of identical Clones are created from the parent, and each clone undergoes a mutation, thus creating a collection of modified individuals related to the parent.

Discussion Concerning Variation The significance of mutation operators has been discussed extensively. Goldberg States that mutation is only a secondary operator in the path of evolution, meaning that the role of mutation is considerably less important than that of reproduction. On the other hand, Fogel explains the nature of mutation as acting as the driving force of evolutionary algorithms, meaning that mutation is at least as important as reproduction. In most cases, crossover does not introduce new parameter values to the selection pool, unless the coding structure allows the crossover point to be located within a single variable. Then again, mutation is able to produce new material within the existing parameter values and, if it is applied appropriately, it is able to produce any possible solution combination within the search space. In this sense, crossover is just a special case of mutation and in most cases the mutation operator is capable of producing more diversity in the solution pool 26

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm than crossover. Evolutionary algorithms have been proven to converge to a global optimum if the variation operator is capable of transforming a solution from any state to any other and an elitist selection method is applied. In most cases crossover does not fulfill this condition, but mutation does, and thus mutation should not be considered as a secondary operator, but rather a crucial one. Nevertheless, the no free lunch theorem still applies to all algorithms and operators, and so, eventually, the usability of any operator depends on the problem. Mutation and reproduction can occasionally use similar methods, such as adding a Random variable to a trait value. However, the fundamental difference between these two operators is that a reproduction operator produces one or more new individuals from an existing solution, whereas mutation only alters an already-existing solution. It is clear that crossover alone is usually not capable of evolving indefinitely, but that it sooner or later faces stagnation. Then again, using a mere mutation operator promotes evolution, although the pace may be slow. The combination of these two Operators may produce better results than using either one alone, since by using the Operator’s side-by-side, the capability of the crossover to connect good combinations of parameter values and the capability of mutation to introduce new variations to the solution pool creates a potentially efficient algorithm. Still, according to the NFL theorem the individual and combined performance of the operators is the same over all possible problems. The AIS optimization method, the clonal selection principle, is a straightforward way of adding variation to the solution pool. A small number of the worst individuals are replaced by randomly created new individuals. Such a simple method is powerful in exploring new areas of the search space.

2.3.4.3 Selection A selection operator selects the individuals from the current generation to proceed to the next generation. A selection operator is also crucial to the operation of any Evolution algorithm, since without selection the solution population would not be guided in any direction and would perform like a purely random search. Selection Operators usually favor good individuals, thus directing the evolution of the population towards a better average value of the objective function. Depending on the implementation, the selection can be carried out among offspring or parents and offspring, or whatever combination of solutions exists in the previous generations. The main idea in selection is that the better the objective function value of an individual, the better its 27

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm chance of proceeding to the next generation. Usually, the size of the solution population is kept constant in order to keep the execution time for each generation the same. However, it is possible to increase or reduce the population sizes as the evolution proceeds, a procedure that directly affects the execution time of the algorithm. This kind of approach aims mainly at performing global searches with fewer individuals and using a larger population to refine the local search. The effect of variable population size is studied, where the population size is reduced by the selection operator and periodically increased by the addition of random individuals. Numerous selection mechanisms exist, and some of the most widely used methods Include rank-based, roulette wheel, and tournament selection. A rank-based selection mechanism simply selects the nrank first solutions ordered according to their fitness values in descending order. nrank equals nI, the initial population size, if the population size is kept constant throughout the execution of the algorithm. Rank-based selection is somewhat deterministic selection methods in the sense that the fit solutions are always selected and the less fit are not. This drives the EC Algorithm relatively quickly towards an optimum, regardless of whether it is global or local. Less fit solutions can contain good ingredients when considering the global optimum, but especially in early generations of an EC algorithm local optima can distract the search and lead to a premature convergence of the algorithm. Premature convergence is a state in which the population of the EC is homogeneous. This condition can occur in local optima or at any other point within the search space. When using rank-based selection one should pay special attention to variation methods, i.e. reproduction and mutation, to ensure diversity within the solution population. Roulette wheel selection, illustrated in Fig. 12, selects the individuals that will survive to the next generation on the basis of their proportional fitness. The selection simulates a roulette wheel, where each individual in the population has a selection sector proportional to its fitness. The better the individual is, the greater its chances of continuing to the next round. Roulette wheel selection makes it possible for each and every individual to make it to the next generation, regardless of its fitness. This may slow down or hinder the convergence of the EC algorithm, since the selection operator may disqualify good solutions. On the other hand, though, good ingredients within less fit individuals have a chance of being selected.

28

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Figure 13 shows the general principle of a generic tournament selection operator. ntournament solutions are selected either randomly or using some kind of a selection Operator for a tournament and each tournament produces a winner, just as in a sports competition. Solutions compete against each other and the best one, i.e. the one with the highest fitness value, moves on to the next round. This method can be implemented by assigning each individual an equal probability of getting selected for a tournament or the probabilities can be biased, as in roulette wheel selection. This method does not guarantee the survival of the fittest, which may lead to problems similar to those discussed with roulette wheel selection. This is the case when the fittest individual is not selected to compete in any of the tournaments. On the other hand, tournament selection allows each individual a chance to proceed to the next generation, thus preserving a possibly greater diversity of variable values in the selection pool than the rank-based selection method.

2.3.5 Genetic Algorithms 29

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm Genetic algorithms are probably the best known of all the evolutionary algorithms. GAs was invented independently at least three times by Fraser, Bremermann, and Holland. Fraser was a biologist who wanted to simulate evolution in order to get greater insight into the biological process and using the algorithms he developed for optimization was not his primary purpose. Then again, Bremermann and Holland clearly developed their algorithms for optimization purposes. The basics of simulated evolution based on genetics are compactly summarized in. Fogel describes the stages of plain GA as follows: 1. The problem at hand is defined as an objective function. 2. A population of candidate solutions is initialized as vectors. 3. Each solution in the population is decoded into an appropriate form for Objective function evaluation. 4. Each solution is assigned a probability of reproduction 5. Reproduction is carried out according to the assigned probabilities. In addition, mutation can be applied to selected individuals on the basis of the assigned probabilities. 6. The process is stopped if a suitable solution is found or when run time requirements have been met. GAs are suitable for many types of optimization tasks and they are widely used. For this reason, they have been widely studied and a variety of performance-tuning Methods exist. Genetic algorithms could be described as the standard evolutionary Algorithms. Genetic programming is a subset of GA. In genetic programming, the Individuals are computer programs that are evolved to solve a specific problem. One type of problem in which GP is often used is where there are specific inputs and a desired target, and the problem is to find a program to use the input to achieve the target. The target can be, for example, to control a system based on input sensory values. In genetic programming the structure of the program can change drastically during evolution.

2.3.6 Evolution Strategies The concept of evolution strategies was created by Rechenberg and Schefel in 1964. In those papers, very simple evolution strategies (including only a few individuals) are outlined and implemented, mainly because of the insufficient computing power, computers becoming available for these scientists only a couple of years after the introduction of the original concept of the algorithm. Evolution strategies differ from genetic algorithms in that each individual, in addition to the parameter values, contains a set of strategy parameters, which were later introduced to the concept. These strategy parameters help to optimize the optimization process itself, as the strategy parameters are subject to crossover and mutation in a similar 30

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm manner to the actual solution variables. Since ES individuals suffer mutation according to Gaussian distribution, a strategy parameter could contain the standard deviation of the distribution. So, this mutation-determining parameter evolves as the algorithm proceeds. The stages of ES as they are typically used at present are described as follows: 1. The problem is defined as finding a real valued n-dimensional vector x that is Associated with the extremum of the objective function. 2. An initial population of parent vectors, xi, i=1, …, nI, is selected randomly From the feasible search space. 3. An offspring vector is created from two or more parents by crossover. The Crossover also includes the crossing over of the strategy parameters. 4. Mutation is introduced by adding a random variable with a zero mean and the Standard deviation pointed in the individual’s strategy parameter to each component of x. 5. Selection determines which of these vectors (parent and offspring) are maintained by ranking the objective function values. The ni best vectors act as Parents for the next generation. 6. The process is continued until a satisfactory solution is reached or run time Requirements have been met.

2.3.7 Evolutionary Programming The foundations for the EP research to come were laid in the early 1960s by L. J. Fogel. Evolutionary programming is similar to evolution strategies in the sense that the mutation is controlled by a strategy parameter, i.e. a standard deviation value is conjugated to each individual. Mutation is usually the only operator used with EP; however, the possibility of multiparent recombination of the best solutions over various generations has also been considered. D. B. Fogel describes the main phases of EP as follows: 1. A population of individuals is created. These individuals can be presented, for Example, as arrays. 2. The objective function value for each individual is evaluated. 3. Offspring individuals are created by mutating the parent individuals on the Basis of the standard deviation parameter given in the strategy parameters. 4. The best individuals are selected to act as parents for the next generation. 5. The process continues until satisfactory results have been achieved or run time Requirements have been met.

31

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm GP and EP share many similarities, the most significant difference being the use of Crossover as an important variation operator in GP. EP relies more on a mutation Operator. Genetic programming is able to modify the number of states through a Crossover operator, whereas the number of states in evolutionary programming can be altered by the mutation operator. In evolutionary programming, the individuals can be finite state machines, as described in the early experiments. Nowadays, however, the solution structure arises naturally from the problem specifications.

2.3.8. Artificial Immune Systems Artificial immune systems stand out as more recent contenders in the field of evolutionary computation when compared to GA, EP, and ES. AIS and its optimization scheme, the clonal selection principle (CSP) or the clonal selection Theorem, are widely credited to, among others, de Castro and Timmis, dating back to the mid-’90s. Instead of mimicking natural evolution, CSP simplifies the mammalian immune system for optimization purposes. The major difference between the traditional EC methods, GA, ES, and EP, and CSP is that, instead of a single optimum, the basic configuration CSP is capable of finding multiple, and separate, good solutions. For GAs, ESs, and EPs, finding multiple good solutions is possible, but this requires the algorithms to be specifically designed that way. In brief, the mammalian immune system operates as follows. When an Animal is exposed to an antigen, something that is normally not part of the animals System, the bone marrow-derived B lymphocyte cells respond by producing antibodies. Antibodies are attached to the surface of the lymphocytes and they recognize and bind to antigens that match their structure. By binding to the antigens, and with the help of additional signals from the so-called T cells, the antigen stimulates the B cell to proliferate and mature into plasma cells or memory cells that can circulate for a long time within the animal. The whole scheme is naturally considerably more complicated, but the main aspects used in the optimization are quite straightforward. The objective function is the antigen. Antibodies are candidate solutions trying to maximize their affinity with respect to the objective function, i.e. the antigen. The candidate solutions are cloned proportionately to how good their affinities are. Thus the best matching candidate solutions are cloned in greater numbers. The optimization procedure using CSP, an algorithm called CLONALG, is explained as follows: 1. Create an initial population of nI antibodies. 2. Determine the affinities of each individual in the solution pool. 3. Select m highest affinity antibodies for cloning. 4. The m selected antibodies are cloned independently and proportionately to 32

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm Their affinities: the higher the affinity, the higher number of clones created for Each of the m selected antibodies. 5. The clones are mutated proportionately to their affinity: the better the affinity, the smaller the mutation rate. This stage is called affinity maturation. 6. The affinity of the clones is calculated. 7. If one of the clones has a higher affinity than its parent, then replace the parent with this higher-affinity mutated clone. 8. Replace the w worst individuals with random new antibodies. 9. The process is continued until a satisfactory solution is reached or run time requirements have been met. CSP contains many of the operators of the traditional EC methods, such as variation and selection.

33

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

3. Generalized Traveling Salesman Problem (GTSP)

Generalized Traveling Salesman Problem (GTSP) 3.1 Introduction Generalized traveling salesman problem (GTSP) is the generalization of the well Known traveling salesman problem (TSP). GTSP is first introduced by Henry-Labordere , Srivastava in 1960’s (1969) in relation with record balancing problems arising in computer design. In GTSP set of nodes is grouped into set of nodes called node sets or clusters and salesman has to find the least cost cycle which must pass through each cluster. In the traditional definition of TSP we are provided with n number of cities and a cost 34

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm matrix C , where cij is the cost of traveling from city i to city j. The goal is to minimize the total cost of traveling to every city exactly once and returning to the starting city. In several of the applications salesman is allowed to visit only a subset of the nodes of graph chosen according to a specified criterion such as in postal routing which has been discussed in Laporte, Mecure and Nobert (1987) and Rousseau (1988). In this application, a postal van must be routed to make pickups from a number of urban mail boxes. The problem is complicated by the fact that the postal van driver is prohibited from crossing a street on a foot in order to make a pickup. This means that for a mail box situated at a street corner, the pickup can only be made from the van stopped in one of the two lanes immediately adjacent to the corner. Although these two potential stop locations are physically close, they result in the van being pointed in two very different directions, thereby yielding different distances to the next mailbox pickup. The problem is modeled as a GTSP by creating a node set for each mailbox to be picked up within each node set; a node is created for each of the two potential pickup locations. Other applications of the GTSP include computer file sequencing, order picking in warehouses, process planning for rotational parts, routing of clients through welfare agencies, airplane and vehicle routing, rural mail delivery, etc. In GTSP not all the nodes need to be visited by the tour as it is shown in the following figure of GTSP. We are dealing with a symmetric GTSP.

Fig: GTSP (different colors represent different clusters) 3.2 Problem definition Generalized traveling salesman problem (GTSP) extends the classical traveling salesman problem (TSP) and is defined as follows. We consider an undirected weighted complete graph G = ( V, E, c ) with node set V, edge set E, and edge cost function c : E R . Node set V is partitioned into r pairwise disjoint clusters V1,V2, . . . , Vr, r

U

i =1

Vi = V , Vi ∩ Vj = Ф, i, j = 1, . . . , r, i ≠ j. A solution

to the GTSP

defined on

G is

a

subgraph S = (P, T)

with

P 35

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm = {p1, p2, . . . , pr} ⊆ V connecting exactly one node from each cluster, i.e. pi ∈ Vi for all 1 ≤ i ≤ r, and T ⊆ E being a round trip. The costs of such around trip are its total edge costs, i.e. C (T) and the objective is to identify a solution with minimum costs. When edge cost satisfy the triangle inequality, even if we allow more than one node per cluster to be connected, an optimal solution of the GTSP always contains only one node from each cluster.

3.2.1 Versions of GTSP •

One node from each cluster in a route. By this approach the problem is to find a minimum cost cycle which includes exactly one node from each cluster.

•

More than one node from each cluster in a route. By this approach the problem is to find a minimum cost cycle which includes one or more than one node from each cluster.

The GTSP simultaneously selects the nodes to include in the cycle and sequences the nodes along the cycle. Thus, two related decisions associated with GTSP given as follows:

1. Selection Selecting a node from each cluster.

2. Sequence Sequencing the selected nodes to be visited to get minimum cost cycle.

36

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

3.3 GTSP is NP-Hard NP-hard is the complexity class of problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When the decision version of a combinatorial optimization problem is proved to belong to the class of NP-complete problems, then the optimization version is NP-hard. TSP is a NP-hard problem as it includes choose the best solution sequence of cities by checking from finitely many feasible solutions. For example for n city problem there are (n-1)! Different tours. It may take years to solve this problem if the city numbers in problem increases. GTSP involves two related decisions simultaneously that is selection of nodes and sequencing of nodes. If we have a preselection of nodes then the remaining problem is a TSP which is NP-hard. Therefore GTSP is also NP-hard problem.

3.4 Previous work related to GTSP GTSP was introduced independently by Henry-Labordere (1969) and Srivastava (1969) and Saksena (1970), Henry-Labordere (1970) developed a dynamic algorithm to deal with symmetric GTSP. The related reported work are very limited compared with those on TSP and the existing algorithm for GTSP are mainly based on dynamic programming techniques. However, because of its NP-hard nature of GTSP only the modest size instances can be solved through dynamic programming. On range instances these techniques take the too huge memory requirements and prohibited large computational cost the main methodology of the dynamic programming algorithm is to transform the GTSP into TSP and then to solve the TSP using existing algorithm. The transformation of a GTSP into traveling salesman problem(TSP) was first introduced by Lien and Ma (1993) in which the number of nodes of the transformed TSP was relatively very large in fact more than three times the number of nodes and edges in the associated GTSP and are therefore of limited practical value. Later Dimitrijevic and Saric (1997) developed another transformation to decrease the size of corresponding TSP. In their method, the number of nodes of the TSP was twice the number of nodes in the original GTSP. This technique was further improved by Behzad and Modarres (2002) where the transformed graph has some number of nodes on the original graph but they transform an instance of GTSP on a partially undirected graph where the distance function satisfies the triangle inequality into an instance of standard TSP on a much larger directed graph without a triangle inequality. However, the transformation increases edge cost significantly, that may lead to problems in some cases. Thus, the resulting problem is in fact more difficult than TSP. Laporte and Nobert (1983) developed branch and bound approach for symmetric GTSP and then Laporte (1987) enhanced his branch and bound algorithm to deal with the asymmetric GTSP. Fischetti (1997) has developed a branch-and-cut algorithm which could solve instances with up to 442 nodes to optimality. To approach larger GTSP instances various metaheuristic have been suggested. Renaud 37

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm and Boctor (1998) developed a composite heuristic GI3 which on performs average at 1% above the optimal solution. Snyder and Daskin (2006) describe a genetic algorithm (GA) that achieves relatively good results in short running times. It uses random keys to encode a solutions and a parameterized uniform crossover operator in addition it has local improvement based on the 2opt and swap heuristic to improve solution quality.

38

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

4. Steady State Genetic Algorithm

Steady State Genetic Algorithm 4.1 Introduction A genetic algorithm is an optimization technique based on natural evolution. It 39

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm incorporates the survival of the fittest idea into a search algorithm which provides a method of searching that does not need to explore every possible solution in the feasible region to obtain a good result. Genetic algorithms are based on the natural process of evolution. In nature, the fittest individuals are most likely to survive and mate, therefore the next generation should be fitter and healthier because they were bred from healthy parents. This same idea is applied to a problem by first guessing solutions and then combining the fittest solutions to create a new generation of solutions which should be better than the previous generation. To solve GTSP, we are using steady-state genetic algorithm (SSGA) which is a variation of the genetic algorithm. SSGA is a different from the generational model in that there is typically one single new member inserted into the new population at any time. A replacement/deletion strategy defines which member in the current population is forced to remove from old population to make a room for the new offspring. SSGA are overlapping systems since parents and offspring compete for survival. A suitable encoding is found for the solution to our problem so that each possible solution has a unique encoding and the encoding is some form of a string. The initial population is then selected; usually at random through alternative techniques using heuristics have been proposed. The fitness of each individual in the population is then computed that is whether it is near the optimum compared to the other individuals in the population. Two individuals are then selected from the population to be considered as parents which go through crossover operator where two new individuals are recombined to create new individuals. A new generated individual is then replaced by one of the existing individuals present in the old population according to some replacement criteria. Whenever new individuals created either by applying GA operators or while creating initial population we are applying local improvement heuristics. With GTSP, we are using the following GA operators to generate new population. • • •

Selection Crossover Replacement/Deletion

4.2 Genetic Algorithm Cycle

40

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Fig. 1 depicts an overview of a simple GA. The selection operator chooses two members of the present generation in order to participate in the next operations: Crossover and mutation. The crossover operator intermixes the alleles of the two parents to obtain an offspring. The mutation operator occurs a short period of time after crossover and as in nature it exchanges alleles randomly. The three most important aspects of using genetic algorithms are: (1) definition of the objective function, (2) definition and implementation of the genetic representation, and (3) definition and implementation of the genetic operators. Once these three have been defined, the generic genetic algorithm should work fairly well

4.3 General Structure of GAs

4.4 Encoding 41

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm The encoding process is often the most difficult aspect of solving a problem using genetic algorithms. Encoding of chromosomes is one of the problems, when you are starting to solve problem with GA. Encoding very depends on the problem. Our problem is Generalized Traveling Salesman Problem (GTSP), which includes sequencing of cities to visit from each cluster. To suit this sequencing problem we have Random Key encoding techniques as well as permutation encoding can also be useful.

4.4.1 Random Key Encoding Random-key encoding is first proposed by Bean. A chromosome is expressed as a string of random numbers which are used as a sort keep for decoding. Consider in a single machine sequencing problem. First generating a uniform (0, 1) random variate for each job, then such a sequence of realization is passed to the fitness evaluation routine which sorts them and sequences the jobs in ascending order of the sort taking the chromosome [0.34, 0.12, 0.17, 0.78, 0.48] for a 5 job and 1 machine problem as an example, the smallest random key is 0.12 corresponding to gene2, so job 2 is the first job in the sequence. The second smallest random key 0.17 corresponding to gene 3, so job 3 is the second job in the sequence continuing the same way for other random keys in the chromosome the final sequence will be 2 -> 3 -> 1 -> 5 -> 4. Bean has demonstrated that all crossovers produce feasible sequences.

4.4.2 Permutation Encoding In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence. Permutation encoding is only useful for ordering problems. Chromosome A 3 2 5 1 4 6 9 8 7 Even for this problems for some types of crossover corrections must be made to leave the chromosome consistent (i.e. have real sequence in it). In permutation encoding crossover is a bit different and more complicated. We have a number of crossover techniques to deal with permutation encoding. 1. Partially-Mapped crossover (PMX) 2. Cycle crossover (CX) 3. Modified crossover 4. Order crossover (OX)

4.5 Evaluation Evaluation is used to find out the fitness of an individual in a population. Fitness decides how good the solution is found by genetic algorithm. Fitness is used to guide the search by deciding which individuals will be used as future points to look for better solutions. Fitness 42

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm decides which individuals will go further for reproduction in next generation. Fitness in Biology means the extent to which an organism is adapted to or able to produce offspring in a particular environment. The fitness function plays a major role in the selection process. In GTSP the fitness of an individual depends on the distance covered to do one Hamiltonian cycle which pass through each city in each cluster. Less the distance covered to do one cycle highest would be the fitness of an individual. In our GTSP we deal with Euclidean distance and Pseudo-Euclidean distance.

4.6 GA Operators 4.6.1 Selection The selection operator involves randomly choosing members of the population to enter in a mating pool. The operator is carefully formulated to ensure that better members of the population with higher fitness have a greater probability of being selected for mating. By choosing appropriate selection strategy it is possible to prevent search process not simply converges to the nearest local optimum. Without selection pressure, the search process becomes random and promising regions of the search space would not be favored over non-promising regions. We have chosen the binary tournament selection with SSGA to solve GTSP, against the ranking selection, for two reasons: •

The complexity of the tournament selection is lower than the complexity of the ranking selection.

•

The selective pressure is higher. This feature allows us to measure whether each crossover is able to keep the population diversity.

Tournament selection runs a tournament between two individuals and selects the winner.

43

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Fig: Binary Tournament Selection 4.6.2 Crossover Crossover operator aims to interchange the information and genes between chromosomes. Therefore, crossover operation combines two or more parents to reproduce new children. Children may hopefully collect all good features that exist in his parents. Crossover plays a major role in GA, so defining a proper crossover is highly needed in order to achieve a better performance of GA. Different types of crossover operators have been studied. To solve GTSP, we are using two different crossover techniques which based on the encoding technique of individuals.

4.6.2.1 Uniform crossover With random key encoding technique, we are using uniform crossover technique. Single and multi-point crossover defines crossover points as places where an individual can be split. Uniform crossover generalizes the scheme to make every gene in chromosome a potential crossover point. A crossover mask the same length as the chromosome is created at random and the content in the mask indicate which parent will supply the offspring with which gene.

44

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

4.6.2.2 Order crossover With random key encoding technique, we are using order crossover technique. Order crossover was proposed by Davis. The offspring inherits the elements between the two crossover points, inclusive, from the selected parent in the same order and position as they appear in that parent. The remaining elements are inherited from the alternate parent in the order in which they appear in that parent, beginning with the first position following the second crossover point and skipping over all elements already present in the offspring.

4.6.3 Replacement We have to choose the replacement strategy that considers two features of the individual to be included into the population: A measure of the contribution of diversity to the population and the fitness function. There are different replacement strategies that try to enforce population diversity. In particular, we present a replacement strategy based on the contribution of diversity of the new offspring to the population where it will be included.

4.6.3.1 Replace-worst The idea is to replace an element of the population with worse fitness function value than the one of the offspring and with lower contribution of diversity than the one provided by the offspring. In this way, we deal with two underlying objectives simultaneously •

To optimize the fitness function

•

To enhance population diversity, that is to promote useful diversity

This strategy is very simple and it needs the little computational cost comparing with other replacement strategy.

4.7 Diversity and Selection Pressure in SSGA There are two primary factors in the search carried out by GA. •

Selection Pressure :

In order to have an effective search there must be a search criterion (the fitness function) and a selection pressure that gives individuals with higher fitness a higher chance of being selected for reproduction, mutation, and survival. Without selection pressure, the search process becomes random and promising regions of the search space would not be favored over nonpromising regions.

45

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm •

Population diversity :

In order to have an optimized fitness value without being converge prematurely, we need to maintain diversity in population such that each individual in the population has much different fitness value with others in a population. Selection pressure and population diversity are inversely related. Increasing selection pressure results in a faster loss of population diversity, while maintaining population diversity offsets the effect of increasing selection pressure. These two factors should be controlled in order to obtain their beneficial advantages simultaneously, allowing the most promising search space regions to be reached and refined. The population diversity versus selection pressure problem has been tackled considering both the parent selection and the replacement phases of a SSGA. There are parent selection mechanisms and replacement strategies that: •

Promote diversity only, or

•

Select pressure only, or

•

Both diversity and selection pressure are included.

4.8 Local Optimization Heuristics Local optimization heuristics add great power to our SSGA. Whenever new individual is created by applying GA operators or during the construction of the initial population, we attempt to improve the solution using 2-opt and swap operation.

4.8.1 2-opt 2-opt is well known local optimization technique. It starts with an arbitrary initial tour and incrementally improves on this tour by making successive improvement that exchange two of the edges in the tour provided that this change decrease the length of the tour.

Fig: 2-Opt operation 46

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

4.8.2 Swap Swap involves removing the node from one of the cluster in the tour and tries all the nodes from that cluster by inserting them in each edge of the tour and the insertion is done provided that the tour cost should be decreased. Three possibilities exist with the swap operation in the tour •

The new node may be inserted on the tour in a spot same from the original tour.

•

The new node may be inserted on the tour in a spot different from the original tour.

•

The same node inserted on the tour in a spot different from the original tour.

Fig: Swap Operation 4.9 Techniques Involved 4.9.1 Algorithm for The Selection Process begin for each organism compute: Euclidean distance; determine maximum Euclidean distance; fitness function; fitness summation; roulette selection probability; deterministic sampling probability endfor sort population on fitness value in a descending order; duplicate each organism exactly as deterministic sampling probability in mating pool; counter=number of organisms in a mating pool; parent1_index = random(counter – 1) parent2_index = random(counter – 1) / on condition that not selected before / start crossover process; end

47

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 4.9.2 Algorithm for Iterated Local Search Procedure ILS(Xi) s = Xi h := 1; while (h <= number of cluster ) do s1 := remove the pair (nR,K,πR,K) from s randomly, and replace the nodes πR,K with another node π*R,K from the same cluster nR,K to establish the pair (nR,K,π*R,K). s2 := best solution obtained by inserting the pair (nR,K,π*R,K) into m+1 possible positions of s1 if f(s1)
Solving Generalized Traveling Salesman Problem Using Genetic Algorithm For i := 1 to P do Calculate the fitness value for chromosome (i) by applying fitness function; i := i + 1; End for {Selection operation} While (new population < P) do Choose the chromosome to survive by applying the roulette wheel selection; End while End begin End while

49

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

5.Random key Encoding

50

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

5. Random key Encoding

5.1 Introduction Random key is one of the encoding techniques used in genetic algorithm. A chromosome is expressed as a string of random numbers which are used as a sort keep for decoding. The random keys representation Bean (1992) encodes a solution with random numbers. These values are used as sort keys to decode the solution. Random keys eliminate the offspring feasibility problem by avoiding the issue. Chromosomal encodings are constructed that represent solutions in a soft manner. These encodings are interpreted in the objective evaluation routine in a way that avoids the feasibility problem. There are other encodings that use random variates (e.g. Back, Hoffmeister, and Schwefel (1991)) but not in the manner of random keys. Bagchi et al (1991) explore different scheduling problem encodings but none that are similar to random keys. The strength of random keys is its robustness. The approach works for many other problems. Bean (1992) describes the use for the traveling salesman problem, scheduling, vehicle routing, resource allocation, and quadratic assignment problems. Bean showed excellent computational results for identical machine scheduling and resource allocation and reasonable computational results for the quadratic assignment problem. An example of random keys is now provided for the context of job shop scheduling. For the single machine sequencing problem, generate a uniform (0, 1) random deviate for each job. When such a sequence of realizations is passed to the objective evaluation routine, sort them and sequence the jobs in ascending order of the sort. For a five job problem, the chromosome is as follows. Here we assign each gene a random value between 0 to 1. To decode the chromosome, we select the job in ascending order of their genes. 0.46 0.91 0.33 0.75 0.51 Would be sorted to the sequence or decoded as a sequence. 3

1

5

4

2

5.2 Feasibility Solutions In genetic algorithm, to generate new population new individuals has to be generating by applying GA operators. GA operators act directly on the random key encoding. Parent 1: Encoded tour in random key and decoded tour. 51

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 0.42 2

0.06

0.38

3

1

0.48 4

0.81 5

Parent 2: Encoded tour in random key and decoded tour. 0.46 3

0.91 1

0.33 5

0.75 4

0.51 2

Here we use one point crossover with four as a crossover point string after that point will get exchange and two new individuals will generate. 0.42

0.06

0.38

0.48

0.81

0.46

0.91

0.33

0.75

0.51

Two newly generated Children are as follows Children 1: 0.42

0.06

0.38

0.75

0.51

2

3

1

5

4

0.46

0.91

0.33

0.48

0.81

3

1

4

5

2

Children 2:

Since any ordered set of numbers can be interpreted as a sequence, all offspring are feasible

5.3 GTSP and Random key The generalized traveling salesman problem combines location and sequencing, cities to be served are partitioned. We must choose one city from each partition to visit and then sequence stops to visit and then sequence stops at the cities chosen. There is clear interdependence between the portions of the decision. To represent this problem with random keys, designate one gene for each partitioning set. For set i, randomly choose an integer in {1,2, . . . ,ni}, where ni is the number of cities in that set. Add a uniform (0, 1) deviate. To construct a solution from a chromosome assume that, in each set, you visit the city indexed by the integer part of the gene. Then sequence the cities in ascending order of the fractional parts of the alleles. The dynamic of the genetic algorithm will simultaneously choose cities in each set and route them. 52

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

For example, consider the GTSP instance with V = { 1, . . . , 20 } and V1= { 1, . . . , 5 } , . . . , V4 = { 16, . . . , 20}.

The random key encoding 4.23

3.07

1.80

3.76

4

18

11

Decodes as the tour 8

The integer parts of the genes decode as, respectively, node 4 (fourth node in V1), node 8 (third node in V2), node 11 (first node in V3) and node 18 (third node in V4) and the fractional parts, when sorted, indicate that the clusters should be visited in the order 2

1

4

3.

5.4 Solving GTSP by SSGA SSGA maintains a large number of random key encoded individuals in a population. All individuals should be unique in population. At each generation of SSGA we are applying several operators that construct a new generation by creating a new individual from old one. First binary tournament selection operator has been applied to select two individuals which go further in crossover operation. Replace the newly generated individual by worst individual in an old population using replace worst replacement strategy.

5.4.1 Uniqueness SSGA maintains a number of solutions also called population. All the solutions should maintain in an encoded form and each individual in population should be unique. After applying local improvement heuristic on each individual in an initial population we have applied the GA operators like selection, crossover which will generate new individual in a population. Each time 53

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm a new individual is created, it is compared to the individuals already in the population; if it matches one of them, it is discarded and a new individual is created. Duplicate-checking is performed after improvement, and individuals are considered identical if the decoded solutions are identical, not the encoded individuals. For example, chromosomes 2.14

4.25

3.50

2.68 and

2.07

4.73

3.81

2.99

Are considered to be same since they represent the same tour 2

9

13

16.

In population there may exist multiple “reflections” and “rotations”. This is undesirable to allow. That is, if 1 6 11 16 is already in the population, we would not want 6 11 16 1 or 16 11 6 1 in the population. The reason behind this is diversity and convergence. This decrease the diversity in the population it converges prematurely if applies crossover operation between those individuals.

5.4.2 Crossover We have used uniform crossover operator of GA with random key encoding technique without using mutation to maintain diversity and convergence. It is used instead of the traditional single point and multiple point crossovers. Two parents are selected from the current population by binary tournament selection. With SSGA best solutions always are passed from one generation to next generation. For example, Consider two parents have been selected for crossover operation. Parent 1: 2.67

3.96

2.16

4.38

5.63

3.14

Parent 2: 2.11

5.39

2.05

1.13

4.97

5.70

With uniform crossover, only one offspring get generated from two parents. New individual generated by inheriting each gene from one of the two parents which depends on the probability which parent to select for inheriting his gene in offspring. 54

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

The offspring that has been generated by selecting proper genes from one of the two parents is given as follows where first, second, sixth genes in offspring chromosome have been selected from parent 2 and rest of the genes has been selected from parent 1. 3.96

5.39

2.16

4.38

5.63

5.70

5.5 Complexity associated with random key encoding We have applied local improvement heuristic to aid the GA to converge faster, whenever new individual is created either during crossover or during initial population. We attempt to improve the solution using 2-opt and swap local optimization heuristics. For example, we have the chromosome as follows for the sets given in section above 2.67

1.16

4.96

1.49

This represents a tour 6

16

2

11

Now suppose we performed a swap operation by replacing node 11 by node 13 and repositioning it after node 6 so that the new tour is 6

13

16

2

The new random key encoded individual is 2.96

1.16

3.49

1.67.

Modifying the individual require lot off computation. First we need to check all the nodes in a cluster in each possible edge of a tour then find at which edge it gives smallest distance and at which node in the respective cluster. After finding node and where to insert that node you have to rearrange the position of the fractional values and integer values to show proper node in encoded solution so that when it decode it should be same as modified solution. It becomes very difficult task to modify the encoded individual in population which always changes while improving the solution which is generated by applying GA operators or while generating the initial population.

55

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

6.Permutation Encoding

56

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

6. Permutation Encoding 6.1 Introduction Permutation encoding is useful when individual fitness depends on positions of genes in chromosome. In that case chromosomes A and B shown below are different and also have different fitness. Main difference between random key encoding and permutation encoding is that there are no genes with the same value in permutation encoding chromosomes. A permutation encoding can be represented by a list of distinct integer values. Each integer value in the list directly encodes the relative ordering of some problem specific object. Chromosome A

3 2 5 1 4 6 9 8 7

Chromosome B

1 2 3 4 5 6 7 8 9

This representation prohibits missing or duplicate allele values and facilitates a simple decoding mechanism. To encode individual in GTSP, random key encoding is very complex encoding technique to decode the individuals. Permutation encoding technique is simple to decode and computation. With random key encoding, cluster and node in that cluster is present in the encoding of individual for GTSP problem. With permutation encoding, encoded individuals only gives the ordering of clusters to be visited. Which node to be visited in respective cluster tour is decided by using nearest neighbor criteria for permutation encoding technique. Each individual in a population then goes through local optimization technique like 2opt and swap. One point, two point crossover or multipoint crossover requires some kind of repairing algorithm to get the feasible tour when used with permutation encoded individuals. Specialized crossover techniques are available to deal crossover with such individuals like partially mapped crossover (PMX), cycle crossover (CX), modified crossover and order crossover (OX). We are using order crossover and swap mutation operators in GA.

6.2 Permutation encoding and GTSP GTSP is a problem of sequence and selection decisions. Sequence decision is about to sequence the cluster in a tour. Selection decision is about to select a node from each cluster. If we have an instance of GTSP in which we have seven clusters and in each cluster five nodes are present cluster route is given as follows. 4

3

7

1

6

5

2

To select a node from each cluster nearest neighbor criteria is used. First select one of the cities randomly from the first cluster in the cluster route. From that city select the nearest city from the next cluster in the cluster route. For example if three is randomly selected city from the 57

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm fourth cluster. The city from the third cluster which is nearest to the third city in fourth cluster is selected. If the first city gives the smaller distance then first city from third cluster is selected. In same way, the city from the seventh cluster which is nearer to the first cluster in third cluster is selected. Select all the cities from each cluster of the cluster route. After applying the nearest neighbor criterion to select the cities from each cluster the selection sequence of cities is given by 3

1

5

1

2

3

4

We have used variation of the nearest neighboring technique to select the cities from each cluster. In the variation, instead of considering randomly generated city from first cluster in the cluster tour we consider randomly generated city from each cluster of the route and generate the number of selection sequence of cities in clusters. The number of selection sequence of cities is equal to the number of the clusters in the cluster route. Consider only one selection sequence which has lesser distance among those. Thus one individual of the GTSP has one cluster route which gives the sequence of cluster, one node tour which gives selection of cities to visit from the clusters in clusters route and cost of individual if we use permutation encoding.

6.3 Solving GTSP by SSGA Steady state genetic algorithm maintains large number permutation encoded solution in population. To check uniqueness of individuals in population is easy if they are permutation encoded as compared to these encoded using random key encoding technique. In random key encoding it needs to first decode the individuals in a population and then check its uniqueness. At each iteration of GA we are applying several operators that construct a new generation by creating a new individual from old one. The operators which we are using are Selection which selects the best quality solutions from the population to through crossover operator and produces a new individual which contain some combination of genes from parents. Mutation operator changes a few genes randomly. Whenever offspring created it goes through the local improvement heuristics. Replacement operator to replace the newly created offspring in population by an old individual in population. Following operators we are using with

6.3.1 Order crossover Order crossover allows two cut points to be randomly chosen on the parent chromosomes. In order to create an offspring, the string between the two cut points in the first parent is first copied to the offspring. Then, the remaining positions are filled by considering the sequence of cities in the second parent, starting after the second cut point when the end of the chromosome is reached, the sequence continues at position 1. In the following figure, the substring 5 6 4 in parent 1 is first copied to the offspring (step1). Then, the remaining positions are filled one by one after the second cut point, by considering the corresponding sequence of cities in parent 2, namely 5 7 8 1 4 2 3 6 ( step2). 58

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm Hence, city 5 is first considered to occupy position 6, but it is discarded because it is already included in the offspring. City 7 is the next city to be considered, and it is inserted at position 6. Then, city 8 is inserted at position 7, city 1 is inserted at position 8, city 4 is discarded, city 2 is inserted at position 1, city 3 is inserted at position 2, and city 6 is discarded. Parents Parent 1

:

1

2

5

6

4

3

8

7

Parent 2

:

1

4

2

3

6

5

7

8

(Step 1)

:

-

-

5

6

4

-

-

-

(Step 2)

:

2

3

5

6

4

7

8

1

Offspring

6.3.2 Swap mutation The swap mutation operator is used here, which simply selects two positions (activities) at random and swaps their contents.

Parent chromosome 2

1

3

4

5

6

7

8

9

10

11

4

5

9

7

8

6

10

11

Child chromosome 2

1

3

Fig: The Swap Mutation operator In the above figure, positions 6 and 9 are selected randomly and the contents present at those positions are interchanged to create a child chromosome.

6.4 Complexity associated with permutation encoding We have applied local improvement heuristic to aid the GA to converge faster. Whenever new individual is created either during crossover or during initial population, we attempt to improve the solution using 2-opt and swap local optimization heuristics. When new individual is created during initial population and after applying crossover or mutation operator it has to go through local optimization techniques like 2-opt and swap operation. It makes modification to 59

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm chromosome which has to do less computation to modify a individual as compared to individuals when it is used with a random key encoding. For example, if we you have a following chromosome first sequence are sequence of cluster second is the selection of node from respective cluster and applying a swap operation on it. 4

3

7

1

6

5

2

3

1

5

1

2

3

4

If we apply swap operation for cluster 6 then we have to try all the five nodes of sixth cluster in each cluster edge. If the third node of the sixth cluster gives less distance when it is inserted in between third and seventh cluster then the improved chromosome would be as follows: 4

3

6

7

1

5

2

3

1

3

5

1

3

4

Computation which has to after local improvement is less complex with individuals encoded with permutation encoding only need to insert the cluster and node at appropriate places without having a need to sorting values a in random key encoded individuals, Thus the complexity associated with permutation encoding

60

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

7.Design and Implementation

61

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 7.

Design and Implementation

7.1 Requirements The purpose of this document is to specify the requirements for the implementation of Steady-state genetic algorithm (SSGA) to solve Generalized traveling salesman problem (GTSP). 7.1.1 Problem Statement: Generalized traveling salesman problem (GTSP) is a generalization of the well known traveling salesman problem (TSP). In the traditional definition of TSP we are provided with number of cities and aim is to find a tour, visiting each city exactly once and returning to the starting city such that the length of the tour is minimized. GTSP is defined on a weighted graph in which nodes have been pregrouped into m mutually exclusive and exhaustive node sets or clusters. The GTSP is the problem of finding a minimum cost cycle which includes exactly one node from each cluster. Genetic algorithm (GA) is one of the most commonly used optimization techniques to solve combinatorial optimization problems like the TSP. GA is an evolutionary technique that use crossover and mutation operator to solve optimization problem using a survival of the fittest idea.

7.2 Requirements Analysis: 7.2.1 System analysis: Existing System: The GTSP was introduced by Henry Labordere in 1960s. Being a generalization of TSP, GTSP is also NP-Hard problem. GTSP is a useful model for problems involving two simultaneous decisions of selection and sequence. Snyder and Daskin (2006) have used the random key encoding technique to encode the solution and a parameterized uniform crossover including local improvement based on the 2-opt discussed by Lin and Kernighan (1972) and swap to boost the solution quality. Random key encoding makes the problem more complex to solve. 62

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Proposed System: Here we are going to use one variant of the genetic algorithm called Steady-state genetic algorithm (SSGA). In this paradigm only a single individual is created at each generation. We used a binary-tournament selection strategy with a replace-worst replacement strategy. In Steady-State Genetic Algorithm best solution are always kept in the population and newly generated solution is immediately available for selection so it converges faster. It maintains the diversity of population at each generation, therefore the problem of premature convergence is avoided. As it maintain a single population at any given time and because of faster convergence it requires less computer memory to operate on individuals, therefore it seems to give possible performance improvements by reducing the computational cost. In our approach we are trying to reduce the complexity using permutation encoding techniques with order crossover. Nearest neighbor criteria to take selection decisions on nodes in clusters and also using swap mutation operator.

7.3 Software Requirements Specification (SRS) A software requirements specification (SRS) is a complete description of the behavior of the system to be developed. It includes a set of use cases that describe all of the interactions that the users will have with the software.

The Software Requirements Specification document forces the system to be responsible for the functional and non-functional requirements that constitutes the process of the requirements analysis. Performance

requirements, Design constraints and external interface

constraints come under non-functional requirements. Use cases are also known as functional requirements. In addition to use cases, the SRS also contains nonfunctional (or supplementary) requirements. Non-functional requirements are requirements which impose constraints on the design or implementation (such as performance requirements, quality standards, or design constraints).

63

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 7.3.1 Functional requirements: The basic functions involved are described below: Modules Taking input and calculating distances Generating the initial population Applying the genetic algorithm operators

Module Description Taking input and calculating distances First of all we need an input file which contains the data about the total number of cities, x coordinate of the city, y coordinate of the city, and the cluster number of the particular city. We store all these descriptions about the particular problem in an input XML file. We need to store each city coordinate and its corresponding cluster number in an array and we should calculate the distance from each city to every other city and the number of cities in each cluster. As the coordinates are Euclidean coordinates we can calculate the city distances by the formula [(X1X2)2 + (Y1-Y2)2]1/2. Now the distance from each city to every other city is stored in an array. With this information we have the next task to calculate the closest cities from a particular city, but the condition is that the next closest city to a particular city should not belong to the same cluster. The argument numberOfCloseCites is given from the gui, if it is greater than the maximum number of cities then we have to assign maximum number of cities to the numberOfCloseCities. Generating the initial population Till now we have the total number of cities, x and y coordinate of each city and its corresponding cluster number, distance from each city to every other city, and closest cities from each city. The next task is to generate the initial population which can have the number of tours. This consist of selection and connecting the cities. Each tour in the population is an individual. To make a tour we take a random city from the city list and with the data obtained already by closest city to the each city, we connect this city to the closest one

7.3.2 Non Functional requirements Hardware requirements:

•

Processor Type

: Pentium -IV

•

Speed

: 2.4 GHZ 64

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm •

Ram

: 256 MB RAM

•

Hard disk

: 20 GB HD

Software requirements: •

Operating System

: Win2000

•

Programming Package

: C#

•

SDK

: DOT NET

7.4 About the Software:

C# C# (pronounced "C Sharp") is a multi-paradigm programming language encompassing imperative, functional, generic, object-oriented (class-based), and component-oriented programming disciplines. It was developed by Microsoft within the .NET initiative and later approved as a standard by Ecma (ECMA-334) and ISO (ISO/IEC 23270). C# is one of the programming languages designed for the Common Language Infrastructure. The goals used in the design of C# are as follows: • C# is intended to be a simple, modern, general-purpose, object-oriented programming language. • The language, and implementations thereof, should provide support for software engineering principles such as strong type checking, array bounds checking, detection of attempts to use uninitialized variables, and automatic garbage collection. Software robustness, durability, and programmer productivity are important. • The language is intended for use in developing software components suitable for deployment in distributed environments. • Source code portability is very important, as is programmer portability, especially for those programmers already familiar with C and C++. • Support for internationalization is very important. • C# is intended to be suitable for writing applications for both hosted and embedded systems, ranging from the very large that use sophisticated operating systems, down to the very small having dedicated functions. 65

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm • Although C# applications are intended to be economical with regard to memory and processing power requirements, the language was not intended to compete directly on performance and size with C or assembly language. Features of C#: By design, C# is the programming language that most directly reflects the underlying Common Language Infrastructure (CLI). Most of its intrinsic types correspond to value-types implemented by the CLI framework. However, the language specification does not state the code generation requirements of the compiler: that is, it does not state that a C# compiler must target a Common Language Runtime, or generate Common Intermediate Language (CIL), or generate any other specific format. Theoretically, a C# compiler could generate machine code like traditional compilers of C++ or FORTRAN. In practice, all existing compiler implementations target CIL. Some notable C# distinguishing features are: •

There are no global variables or functions. All methods and members must be declared within classes. Static members of public classes can substitute for global variables and functions.

•

Local variables cannot shadow variables of the enclosing block, unlike C and C++. Variable shadowing is often considered confusing by C++ texts.

•

C# supports a strict Boolean datatype, bool. Statements that take conditions, such as while and if, require an expression of a boolean type. While C++ also has a boolean type, it can be freely converted to and from integers, and expressions such as if(a) require only that a is convertible to bool, allowing a to be an int, or a pointer. C# disallows this "integer meaning true or false" approach on the grounds that forcing programmers to use expressions that return exactly bool can prevent certain types of programming mistakes such as if (a = b) (use of = instead of ==).

•

In C#, memory address pointers can only be used within blocks specifically marked as unsafe, and programs with unsafe code need appropriate permissions to run. Most object access is done through safe object references, which always either point to a "live" object or have the well-defined null value; it is impossible to obtain a reference 66

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm to a "dead" object (one which has been garbage collected), or to random block of memory. An unsafe pointer can point to an instance of a value-type, array, string, or a block of memory allocated on a stack. Code that is not marked as unsafe can still store and manipulate pointers through the System.IntPtr type, but it cannot dereference them. •

Managed

memory

automatically

cannot

garbage

be

collected.

explicitly Garbage

freed;

instead,

collection

it

is

addresses

memory leaks by freeing the programmer of responsibility for releasing memory which is no longer needed. C# also provides direct support for deterministic finalization with the using statement (supporting the Resource Acquisition Is Initialization idiom). •

Multiple inheritance is not supported, although a class can implement any number of interfaces. This was a design decision by the language's lead architect to avoid complication, avoid dependency hell and simplify architectural requirements throughout CLI.

•

C# is more typesafe than C++. The only implicit conversions by default are those which are considered safe, such as widening of integers and conversion from a derived type to a base type. This is enforced at compile-time, during JIT, and, in some cases, at runtime. There are no implicit conversions between booleans and integers, nor between enumeration members and integers (except for literal 0, which can be implicitly converted to any enumerated type). Any userdefined conversion must be explicitly marked as explicit or implicit, unlike C++ copy constructors and conversion operators, which are both implicit by default.

•

Enumeration members are placed in their own scope.

•

C# provides properties as syntactic sugar for a common pattern in which a pair of methods, accessor (getter) and mutator (setter) encapsulate operations on a single attribute of a class. 67

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm •

Full type reflection and discovery is available.

•

C# currently (as of 3 June 2008) has 77 reserved words.

7.5 Architectural Design 7.5.1. UML USE CASE DIAGRAM A use case is a high–level piece of functionality that the system will provide .Use case diagram represents the functions of a system from the user’s point of view. A use case diagram mainly contains actors and use cases .The use cases and actors define the scope of the system being developing. An actor is any one or any thing that interact with the system being built .Use case diagrams focus on what the system will do with out actual implementations.

Figure - Use Case Diagram

68

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

7.5.2 Detailed Design In detailed design phase the internal design of the modules ,or how the specifications of the module can be satisfied ,is decided. This design level is often called detailed design or logic design Detailed

design essentially expands the system design to contain a more detailed

description of the processing logic .So that the design is sufficiently complete for coding . The basic goal of this phase is to specify the logic for the different modules that have been specified during the system design

7.5.2.1 DFD Design GA SELECTION FLOW

69

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

70

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

GA flow

The GA system whose flow diagram is given in Fig starts with randomly selected initial population. The successive generations are derived by applying the selection, crossover and mutation operators to the previous tour population. A current generation is acted upon by the three operators to produce the successive generation, i.e. selection, crossover and mutation 71

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm operation. Before performing these operations, a fitness function evaluation is being implemented

7.5.2.2 Sequence diagram:

Figure - Sequence Diagram of the first user scenario

72

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

Figure - Sequence Diagram of the second user scenario

73

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 7.5.2.3 Activity diagram:

74

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 7.5.2.4 Class diagrams:

75

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

GAChromosome class

GA ChromosomeParams class

76

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

GaDefaultChromosome and GaChromosomeParamsBlock classes

77

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm GaDynamicOperationChromosome class and interfaces for genetic operations

78

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

GaPopulation class

79

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm Chromosomes in the population

80

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm GaAlgorithm class

81

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm 7.5.2.5 State Chart Diagram

82

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

8.Testing

83

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

8. TESTING In a software development project, errors can be injected at any stage during development. The development of software involves a series of production activities where opportunities for injection of human fallibility’s are enormous. Because of human inability to perform and communicate with perfection, software development is accomplished by a quality assurance activity. Software testing is a critical element of software quality assurance and represents the ultimate review of specification, design and coding. Testing presents an interesting anomaly for the software engineer. The engineer creates a series of test cases that are intended to “demolish” the software engineering process. That could be viewed as destructive rather than constructive. TESTING OBJECTIVES: 1. Testing is a process of executing a program with the intent of finding an error. 2. A good test case is one that has a high probability of finding an as – yet undiscovered error. 3. A successful test one that uncovers an as –yet undiscovered error. The above objectives imply a dramatic change in viewpoint. They move counter to the commonly held view that a successful test is one in which no errors are found. Testing cannot show the absence of defects, it can only show that software errors are present.

8.1 Unit Testing Unit testing focuses verification effort on smallest unit of software design module. All the modules in this system are tested under this strategy of unit test. This testing was carried out during coding stage itself some incorrect variable names, data in output information this type of errors were encountered. Using Black-box testing the individual interface test is also conducted, because each and every module performs external input and output. The following are some unit testing techniques,

84

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm •

Equivalence testing is a black box testing technique that minimizes the number of test cases. The possible inputs are partitioned into equivalence classes, and a test case is selected for each class.

•

Boundary testing is a special case of equivalence testing and focuses on the conditions at the boundary of the equivalence classes. Boundary testing requires that the elements be selected from the edges of the equivalence class.

•

Path testing is a white box testing technique that identifies faults in the implementation of the component. The assumption here is that by exercising all possible paths through

the code at least once, most faults will trigger

failures; this requires knowledge of source code. 8.1.1 Black Box Testing: In this strategy some test cases are generated as input conditions that fully execute all functional requirements for the program. This testing has been uses to find errors in the following categories: a)

Incorrect or missing functions

b)

Interface errors

c)

Errors in data structure or external database access

d)

Performance errors

e)

Initialization and termination errors. In this testing only the output is checked for correctness. The logical flow of the data is not checked.

8.1.2 White Box testing: In this the test cases are generated on the logic of each module by drawing flow graphs of that module and logical decisions are tested on all the cases. It has been uses to generate the test cases in the following cases: 85

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm a)

Guarantee that all independent paths have been executed.

b)

Execute all logical decisions on their true and false sides.

c)

Execute all loops at their boundaries and within their operational bounds.

d)

Execute internal data structures to ensure their validity.

8.2 Integration Testing: Integration testing ensures that software and subsystems work together as a whole. It tests the interface of all the modules to make sure that the modules behave properly when integrated together. Integration Testing Techniques  Big Bang Testing 

Top Down Testing



Bottom Up Testing



Regression Testing

8.3 System Testing A

classic System Testing problem is “Finger - Pointing”. This occurs when an

error is uncovered, and each system element developer blames the other for the problem . To solve this problem the Software Engineer should consider the following issues: Design error – handling paths that test all information coming from Other elements of the system. •

Conduct a series of tests that simulate bad data or other

potential At the Software interface. •

Record the results of tests to use as “evidence” if finger –

pointing Does occur, and System testing is actually a series of different tests whose primary purpose is to fully exercise the computer-based system. It ensures that the complete system complies with the 86

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm functional and non-functional requirements of the system. System Testing Techniques 

Functional Testing



Performance Testing



Acceptance Testing



Security Testing



Recovery Testing System testing is an expensive process but it is essential. The common view of

testing held by users is to prove that there are no errors in program. Different levels of testing that have to be conducted are 1. Code Testing 2. Program Testing 3. System Testing 8.3.1 Code Testing: The code testing has been conducted to test the logic of the program. Here we have tested the system with all the possible combinations of data to find out logical errors. The code testing is done thoroughly with all possible data available with library. 8.3.2 Program Testing: Program testing is also called as unit testing. The modules in the system are integrated to perform the specific function. The modules have been tested independently, later assembled and tested thoroughly for integration between different modules. 8.3.3 System Testing: System testing has been done to test the integration of each module in the system. It is used to find the discrepancies between the system and its original objective. It is found that there is an agreement between current specification and system documentation

87

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

9.Computational Results

88

Solving Generalized Traveling Salesman Problem Using Genetic Algorithm

10.Conclusions

89