Assignments acceptance strategy in a Modified PSO Algorithm to elevate local optima in solving class scheduling problems

Local optima in optimization problems describes a state where no small modification of the current best solution will produce a solution that is better. This situation will make the optimization algorithm unable to find a way to global optimum and finally the quality of the generated solution is not as expected. This paper proposes an assignment acceptance strategy in a Modified PSO Algorithm to elevate local optima in solving class scheduling problems. The assignments which reduce the value of objective function will be totally accepted and the assignment which increases or maintains the value of objective function will be accepted based on acceptance probability. Five combinations of acceptance probabilities for both types of assignments were tested in order to see their effect in helping particles moving out from local optima and also their effect towards the final penalty of the solution. The performance of the proposed technique was measured based on percentage penalty reduction (%PR). Five sets of data from International Timetabling Competition were used in the experiment. The experimental results shows that the acceptance probability of 1 for neutral assignment and 0 for negative assignments managed to produce the highest percentage of penalty reduction. This combination of acceptance probability was able to elevate the particle stuck at the local optima which is one of the unwanted situations in solving optimization problems.