## 3 The Proposed Algorithms  
### Description of the Proposed PSO Algorithm  
The population of the proposed PSO algorithm consists of 15 particles, each one comprising a two-dimensional array. Although the population size is different from the one used in [20], the particle encoding is the same. The number of rows of each particle equals the number of different classes of each school, while the number of columns is 35, since the timeslots of a weekly Greek school timetable are 35 at the most [20]. Each particle's cell contains a number ranging from 1 to the number of different teachers of each school or a \"\(-1\)\" value. For example, if cell \([ij]\) equals \"4\", that means that the 4 th teacher teaches one of his/her lessons at the \(i\)-th class at the \(j\)-th timeslot. If cell \([ij]\) equals \"\(-1\)\", that means that the \(i\)-th class has the \(j\)-th timeslot empty. The interested reader can find more details about the particle encoding used in [20]. In Algorithm 1, the pseudo code of the proposed PSO based algorithm is presented. The algorithm is a hybrid one consisting of two basic components:  
* the main algorithm, which has four basic differences compared to the algorithm presented in [20]. * a local search procedure, which is the same as the one used in [20] and aims improving the quality of the resulted timetable after the execution of the main algorithm. In this contribution we limit our description on the main algorithm, since all differences between the proposed PSO algorithm and the one presented in [20] lie there. The interested reader can find more details about the local search procedure in [20]. The differences of the proposed PSO algorithm compared to the algorithm presented in [20] are the following:  
* Line 3: The number of particles P (_i.e._, the population size) is set to 15, while in [20] equals 50. * Lines 22-23: Procedure _SwapWithProbability_() is applied to two randomly selected timeslots, while in [20] one of the two timeslots selected should have a hard clash (if such a timeslot exists). * Line 22: Procedure _SwapWithProbability_() accepts swaps causing a hard clash with probability equal to 50%, while in [20] this probability equals 2.2%. * Line 22: Procedure _SwapWithProbability_() accepts swaps which cause a raise in the individual's fitness with probability equal to 0.5%, while in [20] this probability equals 2.2%. * Lines 29-34: The probability of exiting the _While Loop Structure_ is set to 1.08%, while in [20] equals 1.1%. +++ ==ERROR: No output for this page==
```
1:Input:\(\{\}\)



++

As seen in Algorithm 1, the main algorithm involves three major components, namely, procedure _SwapWithProbability_(), procedure _InsertColumn_() and a _While Loop Structure_. These three parts are described in short in the next paragraphs. The interested reader can find more details about these parts in [20]. The parameters of procedure _SwapWithProbability_() are the current particle (particle(p)) and two different timeslots t1 and t2. Procedure _SwapWithProbability_() investigates all swaps between the cells of timeslots (columns) t1 and t2 for all classes of particle(p). Swaps that cause no hard clash and result in a smaller or equal fitness value are always accepted and executed. Swaps that cause hard constraint violations are accepted with probability equal to 50%. Swaps that do not cause hard constraint violations but lead to larger (worse) fitness function values are accepted with probability equal to 0.5%. Note that the acceptance of invalid swaps permits the algorithm to escape from local optima in most cases. Procedure _InsertColumn_() is used in order to substitute timeslots of current particle (particle(p)) with timeslots either from the personal best of current particle (Personal_best(p)) or the global best (Global best) found until that point.