Course CS4720 Assignment Experimental Study

Genetic Algorithm

Punit Singh

200083296

Contents

Abstract

2

1

Solution 1: Single Crossover + Mutation - Recursive

2

 

1.1

Crossover

2

 

1.2

Mutation

3

 

1.3

Selection

3

2

Solution 2: Multiple candidate solutions - Elitism

5

 

2.1

Crossover

5

 

2.2

Mutation

6

 

2.3

Selection (Elitism)

6

3

Results

9

1

Abstract

In this report, I explain both of my approaches to solving the experimental study problem where we had to maximize the revenue generated by setting the prices of goods given an initial set of prices for 20 goods.

I used genetic algorithm as a base for both my solutions and developed two di erent archi- tectures which although related to each other, are still quite di erent and produce di erent results. Although we were given only one set of prices, I also used a second set of prices which I generated from the given set itself.

1Solution 1: Single Crossover + Mutation - Recursive

The rst solution employs a simple genetic algorithm which follows the Algorithm [1]. We were given one randomly generated list of prices as the initial prices, but since genetic algorithm techniques like crossover require more than one candidate solutions, I generated a second set of prices by reversing the rst array. I decided to reverse the original array because I did not want to introduce any external values into the prices list. After reversing, I now have two candidate solutions to begin with. I apply crossover, mutations and selection process on these two solutions.

1.1Crossover

For this solution, I set a crossover point of length=5. I evaluate the tness of both the candidate solutions and compare the results and then cross the values of the solution with higher tness over to the one with the lower tness and continue on to the mutation process.

Crossover Process.

2

1.2Mutation

The mutation process is fairly simple in that unlike some genetic algorithms, where mutation is done by ipping some bits, I am selecting 2 indices in each half of the array and swapping the values at both the indices mutation is carried out with a MutationProbability of 15%. A visual representation of the crossover technique that I am using is shown in image 1.2.

Mutation process.

1.3Selection

The selection process in this solution is used to decide whether the candidate solutions generated after crossover and mutation are t enough to be considered the next generation or not. Both of the candidate solutions are evaluated and their tness recorded. If the tness of any of the potential next generations is less than the tness of the previous generation, then the getNextGeneration method is called again and the candidate solution goes through the process of crossover and mutation recursively until a candidate solution is reached whose tness is greater than that of the previous generation.

The complete algorithm of this solution is given on the next page [1].

3

Algorithm 1 Pseudo code Solution 1

Require: SOLUT ION1, SOLUT ION2 reverse(SOLUT ION1)

1:

REV ENUE1

evaluate(SOLUT ION1)

2:

REV ENUE2

evaluate(SOLUT ION2)

3:

if REV ENUE1 > REV ENUE2 then

4:

BEST REV ENUE REV ENUE1

5:else

6: BEST REV ENUE REV ENUE2

7:end if

8:while iteration < maxIteration do

9:

REV ENUE1

evaluate(SOLUT ION1)

10:

REV ENUE2

evaluate(SOLUT ION2)

11:if REV ENUE1 > REV ENUE2 then

12:

CROSSOV ER2[15 : 20] SOLUT ION1[15 : 20]

13:else

14:

CROSSOV ER1[15 : 20] SOLUT ION2[15 : 20]

15:end if

16:index1 randomInt(0; 9)

17:index2 randomInt(10; 19)

18: mutationP rob randomDouble(0; 1)

19:while i < 2 do

20:if mutatioP rob > 0:85 then

21:

MUT AT ED1

swap(CROSSOV ER1[index1]; CROSSOV ER1[index2])

22:

MUT AT ED2

swap(CROSSOV ER2[index1]; CROSSOV ER2[index2])

23:end if

24:end while

25:NEXT REV1 evaluate(MUT AT ED1)

26:NEXT REV2 evaluate(MUT AT ED2)

27:if NEXT REV1 > REV ENUE1 then

28:SOLUT ION1 MUT AT ED1

29:end if

30:if NEXT REV2 > REV ENUE2 then

31:SOLUT ION2 MUT AT ED2

32:end if

33:if REV ENUE1 > BEST REV ENUE then

34:

BEST REV ENUE REV ENUE1

35:end if

36:if REV ENUE2 > BEST REV ENUE then

37:

BEST REV ENUE REV ENUE2

38:end if

39:end while

40:return BEST REV ENUE

4

2Solution 2: Multiple candidate solutions - Elitism

The architecture of this solution is quite similar to that of solution 1, but with some major changes which are discussed below. Here also I use two sets of initial prices as the starting point and again the second set again is generated by reversing the given set of prices. The di erence is that after crossover, this algorithm generates 4 di erent candidate solutions followed by mutations on all of them only then to be tested and from among these four candidate solutions, only two are returned as the next generation prices.

2.1Crossover

In this solution, the crossover method used takes 2 arrays of prices as input and evaluates them. The solution with a higher tness is then crossed over to the lower tness solution at four crossover points, thus creating four di erent candidate solutions. A visual representation can be see in image [2.1].

Crossover Process.

5

2.2Mutation

The mutation method used in this method is the same as that used in the previous solution. Although I did try to use a method of changing the values of randomly generated indices to a completely random value, the results of that experiments were varying too much with each run; performing extremely well at times and not good enough most of the other times. The same mutation method is applied to all four candidate solutions and the mutated can- didates are forwarded to the selection method.

Mutation Process.

2.3Selection (Elitism)

The selection method used in this solution is elitism where only the best two algorithms from the population of 4 candidate solutions are chosen as the next generation. This ensures that only the best traits are carried on to the next generation. A visual representation of the selection method for this solution is shown in image [2.3].

6

Selection Process.

7

Algorithm 2 Pseudo code solution 2

Require: SOLUT ION1, SOLUT ION2 reverse(SOLUT ION1)

1:

REV ENUE1

evaluate(SOLUT ION1)

2:

REV ENUE2

evaluate(SOLUT ION2)

3:

if REV ENUE1 > REV ENUE2 then

4:

BEST REV ENUE REV ENUE1

5:else

6: BEST REV ENUE REV ENUE2

7:end if

8:while iteration < maxIteration do

9:

REV ENUE1

evaluate(SOLUT ION1)

10:

REV ENUE2

evaluate(SOLUT ION2)

11:BEST REV ENUE max(SOLUT ION1; SOLUT ION2)

12:if REV ENUE1 > REV ENUE2 then

13:

CROSSOV ER1

[0 : 4]

SOLUT ION1[0 : 4]

14:

CROSSOV ER2

[5 : 9]

SOLUT ION1[5 : 9]

15:

CROSSOV ER3

[10 : 14]

SOLUT ION1[10 : 14]

16:

CROSSOV ER4

[15 : 19]

SOLUT ION1[15 : 19]

17:else

18:

CROSSOV ER1

[0 : 4]

SOLUT ION2[0 : 4]

19:

CROSSOV ER2

[5 : 9]

SOLUT ION2[5 : 9]

20:

CROSSOV ER3

[10 : 14]

SOLUT ION2[10 : 14]

21:

CROSSOV ER4

[15 : 19]

SOLUT ION2[15 : 19]

22:end if

23:index1 randomInt(0; 9)

24:index2 randomInt(10; 19)

25: mutationP rob randomDouble(0; 1)

26:while i < 2 do

27:if mutatioP rob > 0:85 then

28:

MUT AT ED[1:4] swap(CROSSOV ER1[index1]; CROSSOV ER1[index2])

29:end if

30:end while

31:NEXT REV[1:4] evaluate(MUT AT ED1)

32:SOLUT ION1; SOLUT ION2 getMaxPopulation(NEXT REV1; NEXT REV2;

NEXT REV3; NEXT REV4)

33:end while

34:return BEST REV ENUE

8

3Results

After experimenting with di erent parameters and settings in both the solutions, I can conclude that both the algorithms give similar results. Although the rst solution almost always performs slightly better than the second solution. After 2000 generations, the Best revenue generated by both the solutions is around 3000, which, I believe is a substantial improvement from the inital revenue of 2467:78.

Output plots of the solutions.

9