# Solving the Urban Transit Routing Problem Using a Cat Swarm Optimization-Based Algorithm
## 3 The Proposed CSO-Based Algorithm  
CSO-based algorithms imitate the collective behavior of non-distributed, self-organized physical systems. The capability of natural systems to demonstrate collective intelligent behavior is generally reported in publications as swarm intelligence [50]. These systems are usually composed of several autonomous agents: entities that are meant to execute different and specific operations. These agents interact locally either with each other or with their environment. Their interactions, although with no centralized control of behavior, often lead to a prospective collective one [51]. CSO algorithms were firstly proposed by [PERSON] et al. in 2006 [52] and have been successfully applied to other optimization problems, as presented in the related work section (see Section 1.1)  
According to the classic CSO approach [50; 52], there are two different states in which a cat can be during the optimization process: a) seeking mode and b) tracing mode. In seeking mode, each cat rests while examining its environment in order to decide which move should be its next one. In tracing mode, each cat moves rapidly hunting for food. The value of a Boolean variable determines whether a cat is in seeking mode or tracing mode. The way a cat is acting in seeking mode is affected by four parameters: (i) seeking memory pool (_SMP_), (ii) seeking range of the selected dimension (_RSD_), (iii) count of dimensions to change (_CDC_) and (iv) self-position consideration (_SPC_) [50; 52]. The steps (in pseudocode) that each cat \(k\) (_cat\({}_{k}\)_) is going to execute while in seeking mode are presented below:* Create \(j\) copies of the current position of \(cat_{k}\) (Note: \(j=SMP\)) If (the value of parameter \(SPC\) is true) \(j=(SMP-1)\) Add the current position into the pool of candidate position to be moved to
* For (each copy) Change the value of \(CDC\) dimensions at random (Note: these changes cannot exceed a percent \(\pm RSD\))
* Calculate the fitness value for all candidate positions
* If (the calculated finesses are not equal with each other) Calculate the probability \(P_{i}\) of selecting each candidate position Else \(P_{i}\)= 1.0, (Note: for all \(i\))
* Pick at random, among candidate positions, the position to which \(cat_{k}\) will be moved Place \(cat_{k}\) to this position Probability \(P_{i}\), which is the probability of each candidate position to be selected for moving \(cat_{k}\) there, is computed using Equation (1): \[P_{i}=\frac{|FS_{i}-FS_{b}|}{FS_{max}-FS_{min}}\] (1) where \(FS_{i}\) is the fitness value of position \(i\), \(FS_{max}\) is the biggest fitness value found, \(FS_{min}\) is the smallest fitness value found and \(FS_{b}\) is equal to \(FS_{max}\) for maximization problems and equal to \(FS_{min}\) for minimization problems, respectively. The steps (in pseudocode) that each cat \(k\) (\(cat_{k}\)) is going to execute while in tracing mode are presented below:  
* Update the velocity of each dimension of \(cat_{k}\)
* If (the value of a velocity is outside allowed range) Set it equal to the maximum allowed value
* Update the position of \(cat_{k}\)  
The velocity of each dimension of \(cat_{k}\) is updated according to Equation (2):  
\[v_{k,d}=v_{k,d}+r_{1}\cdot c_{1}\left(x_{best,d}-x_{k,d}\right),\ d=1,2,\ldots,\ M \tag{2}\]  
where \(x_{best,d}\) is the position of the cat with the best fitness value up to that moment, \(x_{k,d}\) is the position of \(cat_{k}\), \(c_{1}\) is a constant affecting the change in the velocity of each dimension (most of the times set equal to 2.0 [50,52]) and \(r_{1}\) is a random value belonging to [0, 1]. The position of \(cat_{k}\) is updated according to Equation (3):  
\[x_{k,d}=x_{k,d}+v_{k,d} \tag{3}\]  
These two modes (seeking mode and tracing mode) are combined in the original CSO algorithm using a ratio determined by the parameter mixture ratio (\(MR\)) [50,52].