## 4 The Proposed Algorithm
### A Proposed Local Version of PSO for Discrete Search Space  
There are a lot of PSO variations for continuous search space. Theoretically, any of them can be used to solve any optimization problem with a continuous domain. Of course, the quality of the solution depends on the choice of the PSO variation. However, the situation is different when the optimization problem involves a discrete search space. Even though the relative literature is rich with published attempts dealing with optimization problems with discrete domains using PSO implementations, none of them can be universally applied to handle discrete search space optimization problems. The reason for this it the lack of a universal model representation for such problems. Combinatorial problems, such as timetabling, can be represented by various models that differ significantly from one another. Moreover, the application of the original PSO version is inappropriate in the case of a discrete domain. For instance, considering the velocity vector and adding it to the position vector of a particle would clearly cause the search to move beyond the problem's feasible region. We have to mention that we indeed tried to apply the binary version of PSO [40] but the outcome was of a rather poor quality. Therefore, it is clear that creating and deploying new algorithms for each discrete problem is necessary when it comes to the PSO case. However, any algorithm claiming to be PSO-based must maintain the essence of the original PSO. In our contribution, we present a PSO-based algorithm for solving the Greek school timetabling problem. We retained some basic design structures, while several fundamental changes were implemented as well. The most significant change was that we used the local version of PSO, unlike the global one used in other works. That is, instead of considering the swarm of particles as a whole neighborhood in which particles exchange position information with each other, we split the swarm to several neighborhoods. Each neighborhood is dedicated to a particle and consists of a standard number of particles--neighbors. The neighborhoods are not necessarily disjointed, and their topology is similar to those proposed at the respective website [41]. To be more precise, we used the random topology, i.e., we periodically update the neighborhood of each particle, at each generation, by selecting other particles as neighbors at random. Of course, each particle has a neighborhood, and within each neighborhood, there is a particle that is considered the best, known as the \"local best\" of that particle's neighborhood. In previous works [8; 9; 10], each particle exchanged positional information with all the other particles through the \"global best\", i.e., the particle with best quality in the total swarm. In addition, its trajectory is influenced by both the global best and its personal best, i.e., the best structure it ever had during the evolution, up to the current point. In the current work, the local best plays the role of the global best, while the personal best and global best keep informing each particle and influencing its trajectory as well. Since the trajectory of each particle is influenced by the local best, the personal best, and the global best, the claim that our algorithm constitutes a local version of PSO for a discrete domain problem such as the school timetabling one is rather justified. The exact way in which the local best, personal best, and global best particles influence the trajectory of each particle, allowing it to \"fly\" over the discrete search space is briefly described here in Section 4.4.2. The outcome of our algorithm indicates that the use of the local version of PSO outperforms the global PSO. Additionally, this fact was rather expected, and it is in accordance to what is already known for the PSO versions applied in continuous domain problems [42; 43]. Another fundamental point in which our current work differs from previous ones is the use of a backtracking schema.