Questions 15: Genetic Algorithms

Roman Belavkin Middlesex University

Question 1 Give an example of combinatorial problem. What is the most dicult in solving these problems? Answer: One classical example is the Travelling Salesman problem (TSP), described in the lecture notes. Another example is the timetable problem. The main diculty is that the number of combinations (and, hence, the number of possible solutions) grows much faster than the number of items involved in the problem (i.e. the number of cities in TSP, the number of timeslots, etc). This problem is known as combinatorial explosion. Question 2 Name and describe the main features of Genetic Algorithms (GA). Answer: Genetic Algorithms (GA) use principles of natural evolution. There are ve important features of GA: Encoding possible solutions of a problem are considered as individuals in a population. If the solutions can be divided into a series of small steps (building blocks), then these steps are represented by genes and a series of genes (a chromosome) will encode the whole solution. This way dierent solutions of a problem are represented in GA as chromosomes of individuals. Fitness Function represents the main requirements of the desired solution of a problem (i.e. cheapest price, shortest route, most compact arrangement, etc). This function calculates and returns the tness of an individual solution. Selection operator denes the way individuals in the current population are selected for reproduction. There are many strategies for that (e.g. roulettewheel, ranked, tournament selection, etc), but usually the individuals which are more t are selected. 1

BIS3226

Crossover operator denes how chromosomes of parents are mixed in order to obtain genetic codes of their ospring (e.g. onepoint, twopoint, uniform crossover, etc). This operator implements the inheritance property (ospring inherit genes of their parents). Mutation operator creates random changes in genetic codes of the ospring. This operator is needed to bring some random diversity into the genetic code. In some cases GA cannot nd the optimal solution without mutation operator (local maximum problem). Question 3 Consider the problem of nding the shortest route through several cities, such that each city is visited only once and in the end return to the starting city (the Travelling Salesman problem). Suppose that in order to solve this problem we use a genetic algorithm, in which genes represent links between pairs of cities. For example, a link between London and Paris is represented by a single gene LP . Let also assume that the direction in which we travel is not important, so that LP = P L. a) How many genes will be used in a chromosome of each individual if the number of cities is 10? Answer: Each chromosome will consist of 10 genes. Each gene representing the path between a pair of cities in the tour. b) How many genes will be in the alphabet of the algorithm? Answer: The alphabet will consist of 45 genes. Indeed, each of the 10 cities can be connected with 9 remaining. Thus, 10 9 = 90 is the number of ways in which 10 cities can be grouped in pairs. However, because the direction is not important (i.e. LondonParis is the same as ParisLondon) the number must be divided by 2. So, we shall need 90/2 = 45 genes in order to encode all pairs. In general the formula for n cities is: n(n 1) 2 Question 4 Suppose a genetic algorithm uses chromosomes of the form x = abcdef gh with a xed length of eight genes. Each gene can be any digit between 0 and 9. Let the tness of individual x be calculated as: f (x) = (a + b) (c + d) + (e + f ) (g + h) ,

BIS3226

and let the initial population consist of four individuals with the following chromosomes: x1 = 6 5 4 1 3 5 3 2 x2 = 8 7 1 2 6 6 0 1 x3 = 2 3 9 2 1 2 8 5 x4 = 4 1 8 5 2 0 9 4

a) Evaluate the tness of each individual, showing all your workings, and arrange them in order with the ttest rst and the least t last. Answer: f (x1 ) = (6 + 5) (4 + 1) + (3 + 5) (3 + 2) = 9 f (x2 ) = (8 + 7) (1 + 2) + (6 + 6) (0 + 1) = 23 f (x3 ) = (2 + 3) (9 + 2) + (1 + 2) (8 + 5) = 16 f (x4 ) = (4 + 1) (8 + 5) + (2 + 0) (9 + 4) = 19

The order is x2 , x1 , x3 and x4 . b) Perform the following crossover operations: i) Cross the ttest two individuals using onepoint crossover at the middle point. Answer: Onepoint crossover on x2 and x1 :

O = 87123532 x2 = 8 7 1 2 6 6 0 1 1 x1 = 6 5 4 1 3 5 3 2 O2 = 6 5 4 1 6 6 0 1 ii) Cross the second and third ttest individuals using a twopoint crossover (points b and f ). Answer: Twopoint crossover on x1 and x3

x1 = 6 5 4 1 3 5 3 2 O = 65921232 3 O4 = 2 3 4 1 3 5 8 5 x3 = 2 3 9 2 1 2 8 5 iii) Cross the rst and third ttest individuals (ranked 1st and 3rd) using a uniform crossover.

BIS3226

4 Answer: In the simplest case uniform crossover means just a random exchange of genes between two parents. For example, we may swap genes at positions a, d and f of parents x2 and x3 : O = 27126201 x2 = 8 7 1 2 6 6 0 1 5 O6 = 8 3 9 2 1 6 8 5 x3 = 2 3 9 2 1 2 8 5

c) Suppose the new population consists of the six ospring individuals received by the crossover operations in the above question. Evaluate the tness of the new population, showing all your workings. Has the overall tness improved? Answer: The new population is: O1 = 8 7 1 2 3 5 3 2 O2 = 6 5 4 1 6 6 0 1 O3 = 6 5 9 2 1 2 3 2 O4 = 2 3 4 1 3 5 8 5 O5 = 2 7 1 2 6 2 0 1 O6 = 8 3 9 2 1 6 8 5 Now apply the tness function f (x) = (a+b)(c+d)+(e+f )(g+h): f (O1 ) = (8 + 7) (1 + 2) + (3 + 5) (3 + 2) = 15 f (O2 ) = (6 + 5) (4 + 1) + (6 + 6) (0 + 1) = 17 f (O3 ) = (6 + 5) (9 + 2) + (1 + 2) (3 + 2) = 2 f (O4 ) = (2 + 3) (4 + 1) + (3 + 5) (8 + 5) = 5 f (O5 ) = (2 + 7) (1 + 2) + (6 + 2) (0 + 1) = 13 f (O6 ) = (8 + 3) (9 + 2) + (1 + 6) (8 + 5) = 6 The overall tness has improved. d) By looking at the tness function and considering that genes can only be digits between 0 and 9 nd the chromosome representing the optimal solution (i.e. with the maximum tness). Find the value of the maximum tness. Answer: The optimal solution should have a chromosome that gives the maximum of the tness function max f (x) = max [(a + b) (c + d) + (e + f ) (g + h)] .

BIS3226

Because genes can only be digits from 0 to 9, the optimal solution should be: xoptimal = 9 9 0 0 9 9 0 0 , and the maximum tness is f (xoptimal ) = (9 + 9) (0 + 0) + (9 + 9) (0 + 0) = 36

e) By looking at the initial population of the algorithm can you say whether it will be able to reach the optimal solution without the mutation operator? Answer: No, the algorithm will never reach the optimal solution without mutation. The optimal solution is xoptimal = 9 9 0 0 9 9 0 0. If mutation does not occur, then the only way to change genes is by applying the crossover operator. Regardless of the way crossover is performed, its only outcome is an exchange of genes of parents at certain positions in the chromosome. This means that the rst gene in the chromosomes of children can only be either 6, 8, 2 or 4 (i.e. rst genes of x1 , x2 , x3 and x4 ), and because none of the individuals in the initial population begins with gene 9, the crossover operator alone will never be able to produce an ospring with gene 9 in the beginning. One can easily check that a similar problem is present at several other positions. Thus, without mutation, this GA will not be able to reach the optimal solution. Question 5 What two requirements should a problem satisfy in order to be suitable for solving it by a GA? Answer: GA can only be applied to problems that satisfy the following requirements: The tness function can be welldened. Solutions should be decomposable into steps (building blocks) which could be then encoded as chromosomes. Question 6 A budget ariline company operates 3 plains and employs 5 cabin crews. Only one crew can operate on any plain on a single day, and each crew cannot work for more than two days in a row. The company uses all planes every day. A Genetic Algorithm is used to work out the best combination of crews on any particular day.

BIS3226

a) Suggest what chromosome could represent an individual in this algorithm? Answer: On each day, a solution is a combination of 3 cabin crews assigned to 5 airplanes. Thus, a chromosome of 3 genes could be used in this algorithm with each gene representing a crew on a certain plain. b) Suggest what could be the alphabet of this algorithm? What is its size? Answer: The alphabet of genes representing the crews can be used. Thus, its size is 5. c) Suggest a tness function for this problem. Answer: You may come up with dierent versions, but it is important for the tness to take into account the condition that cabin crews cannot work more than 2 days in a row. For example, the tness function can take into account how many days each crew has left before a day o (e.g. 1 or 0). The tness could be calculated as the sum of these numbers for all drivers in the chromosome. d) How many solutions are in this problem? Is it necessary to use Genetic Algorithms for solving it? What if the company operated more plains and employed more crews? Answer: The number of solutions is the number of times 3 crews can be selected out of 5 without replacement and without taking into account their order. The rst crew can be selected in 5 dierent ways, the second in 4 ways and the third in 3 dierent ways. These numbers multiplied together will give us total number times how 3 crews can be selected randomly out of 5: 5 4 3 = 60 times. However, there are 6 possible combinations in which 3 crews can be ordered, and because the order does not matter the answer is 60/6 = 10. Thus, there are 10 possible solutions for this problem. It is not really necessary to use GA for a problem with such a small population, because solutions can be checked explicitly. However, as the number of crews and airplanes increases, so does the number of solutions, and the use of GA can be the only option. In fact, if n is the number of cabin crews and k n is the number of airplanes, then the number of solutions is n! . k!(n k)!

BIS3226

For example, if the company operated 10 airplanes and employed 20 cabin crews, then the number of solutions would be 20! = 184, 756 10!(20 10)! .