Darwinian PSO

Results Discussion

We compare the Darwinian PSO algorithm to that of a single swarm. We also attempt to study the impact of our selection process by comparing the Darwinian swarms to a collection of static swarms.

The Three Types of Swarms Evaluated

Traveling Salesman Problem (TSP)

The Darwinian PSO algorithm is evaluated by applying it to the TSP. In our variant of the TSP, distances are Euclidean and we are minimizing the total tour length with the constraint that the tour end on the start city.

The size of the single swarm is selected by first running the Darwinian algorithm on the configuration of cities and computing the average number of particles that participate in the optimization. This is done to ensure that both algorithms have the same number of particles on average participating. The number of static swarms and their size is similarly selected by computing the average number of swarms, and the average number of particles per swarm in the Darwinian PSO algorithm. This parameter selection is done using the circular configuration of cities and the same parameters are used when applying the algorithms to a random configuration of cities. The algorithm is executed 15 times for both a circular configuration of cities and a random configuration of cities. Note that the 3 different algorithms are always applied to the same set of cities to enable comparison. In the case of a random configuration of cities, there are 15 different configurations and each algorithm is applied to each.

Circular City Configuration

Note that in all trials, the algorithms are halted after 500 iterations.

Single Swarm vs. Darwinian Swarm
A circular configuration of cities is selected because the global optimum is known. From the results of executing each algorithm 15 times on a circular configuration of cities, we find the the Darwinian algorithm finds the optimal solution in the allotted time in 8/15 of the trials whereas the single swarm finds the optimal solution in the allotted time in 6/15 of the trials.

Static Swarms vs. Darwinian Swarm
From the results of executing each algorithm 15 times on a circular configuration of cities, we find the the Darwinian algorithm finds the optimal solution in the allotted time in 8/15 of the trials whereas the single swarm finds the optimal solution in the allotted time in 13/15 of the trials. It seems that this result indicates that static swarms are preferred. However, one must ask the question: How were 11 swarms with 23 particles per swarm selected to begin with? The answer is that the Darwinian algorithm was executed and its average number of swarms and average number of particles per swarm was computed a posteriori for the circular configuration of cities. It was these values that were used to define the parameters of the static swarms. The result can be interpreted as, the selection process found an optimal configuration of swarms for solving the problem. This hypothesis can be tested, but leave that as future work. Another interpretation is that the circular configuration of 25 cities is not hard enough to reveal all of the underlying relationships between the 3 algorithms. To further attempt to determine if the selection process circumvents local optima, we execute the same 3 algorithms on 15 random configurations of 25 cities.

Random City Configuration

Single Swarm vs. Darwinian Swarm
From the results of executing each algorithm on a random configuration of 15 cities, we find that the Darwinian algorithm find a better fitness in 13 of 15 trials. Also note that the Darwinian algorithm typically converges at a higher rate.

Static Swarms vs. Darwinian Swarm
From the results of executing each algorithm on a random configuration of 15 cities, we find that the Darwinian algorithm find a better fitness in 9 of 15 trials. There were only 2 trials in which the static swarms achieved a better fitness than the Darwinian swarms. Our interpretation is that although 11 swarms, with 23 particles per swarm may have been optimal for the circular configuration of cities, it is not for the random configuration. It is the adaptive quality imbued by the selection process that allows the Darwinian swarm to outperform the static swarms. Note that I should look at the average number of swarms and average number of particles per swarm used by the Darwinian algorithm and run the static algorithm again to see if the 2 performances converged. That would certainly boost the argument for the selection process.