# Parallelized Swarm Intelligence Approach for Solving TSP and JSSP Problems
## 2 Materials and Methods  
### MPA Algorithm  
The proposed mushroom-picking algorithm is a metaheuristic constructed from the following components:  
* Population of solutions;
* Set of different solution-improving agents;
* Common memory from where the current solutions can be removed and stored by solution improving agents. The initial population of feasible solutions is generated randomly and stored in the common memory. MPA works in cycles. A cycle involves randomly partitioning the solutions from the common memory into several subpopulations of equal size. Each subpopulation is served by a group of the solution-improving agents. Groups are replicated to take care of each subpopulation. Each agent within a group reads the required number of solutions from the subpopulation and tries to improve them. If successful, a worse solution in the population is replaced by the improved one. The required number of solutions depends on the construction of the particular agent. A single argument agent requires a single solution. Double argument agents require two solutions, etc. All groups of agents work in parallel threads. A sequence of improvement attempts within a group is random. After the time span set for the cycle has elapsed the cycle is closed and all current solutions from subpopulations are returned to the common memory. Solutions in the common memory are then shuffled and the next cycle begins. The final stopping criterion is defined as no improvement of the best result (fitness) after the given number of cycles were run. Defining the stopping criterion aims at finding a balance between the quality of the final solution and the overall computation time. The parallelization of the solutions improvement process is carried out using the Apache Spark, a general-purpose framework for parallel computing [40]. The general scheme of the MPA is shown in pseudo-code as Algorithm 1. ```
\(n=\) the number of parallel threads \(\textit{solutions}=\) a set of generated solutions while\(\textit{lstoppingCriterion}\)do{ populations = solutions randomly split into \(n\) subsets of equal size \(\textit{populationsRDD}=\textit{populations}\) parallelized in Apache Spark (\(n\) threads) \(\textit{populationsRDD}=\textit{populationsRDD.map}\)(\(\textit{p}{=>}\textit{p.applyOptimizations}\)) \(\textit{solutions}=\textit{populationsRDD.collect}\) \(\textit{bestSolution}=\) solution from solutions with the best fitness } returnbestSolution
```  
**Algorithm 1** MPA  
_ApplyOptimizations_ attempts to improve current results in each subpopulation of solutions by running the solution-improving agents. The process is carried out for the time span of a given length, called _searchTime_ set by the user. During this period, _applyOptimizations_ draws at random an optimizing agent from the available set of agents and applies it to a random solution from the subpopulation. The number of solutions drawn from the respective subpopulation and temporarily allocated to an agent must be equal to the number of arguments that the agent requires to be able to act. If the agent finds a solution that is different and better than originally obtained as its arguments, _applyOptimizations_ replaces some worse solution with the improved one. A single solution in the MPA is represented by the ordered list of numbers. The length of the list depends on the problem at hand, but for instances of a particular problem, the length of such a listis constant. For example, for a TSP problem with 6 nodes the solution could be represented by the following: _List_ (2, 1, 4, 3, 5).