Dynamic Probability Distribution. To select which move operator to select next, a random variable is generated. In case the distribution is uniform, a random integer between 1 and the number of available moves is generated. The probability of a certain move to be selected is (1/numberOfMoves*100)% in each iteration. However, Section 4.1.5.2 showed that not every move has the same expected performance and the performance is dependent on the selected instance or competition. Therefore a dynamic move selection was proposed with an adapting probability for each operation in each iteration. If a move results in a better feasible or infeasible schedule, its selection probability is increased, whereas the probability of all other moves decreases. For this dynamic move selection, 2 variants exist. One variant implements a limitation on the probability a move can be chosen. In this master’s dissertation, 50% was chosen as a benchmark, by doing this in theory every one in two moves should be different. The second variant does not restrict the probability of an operator with the result that the probability of a move operator can converge to 100% and no other operator can be selected. Figures 11c and 11d show a comparison between those 3 types of methods. Figure 11c compares the uniform move selection method to the dynamic move selection with a limitation of 50%. The triangles represent the uniform distribution and are lower for all instances, except for NL10 and NL12 where both methods have approximately the same gap to the best known solution. For NL14 and NL16, the difference is more than 2% in favor of the uniform distribution. This difference in performance can have several explanations. A first one is that the variety of different moves throughout the program can be effective to find new, potentially better solutions. This reduction of variety by lowering the probability of selection for certain moves can cause the algorithm to get stuck in a local minimum where no move is able to get out. A second explanation can be the one of coincidence. This comparison is based on 3 runs of 30 minutes for both methods and if the right move is selected at the right time, a high-quality schedule can be produced. A third potential explanation can be the extra computational effort that is required to calculate the probability of each move after every iteration. Although these calculations are rather limited, doing it thousands or millions of times might lower the efficiency of the program. The conclusion is th...
