Course CS4720 Assignment Experimental Study
Genetic Algorithm
Punit Singh
200083296
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.
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].
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
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.
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].
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
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.
