Parallel GA Implementation

The objective of this project is to garner experience working with genetic algorithms (GAs) in a parallel processing environment while developing an understanding of the relationship between computation time and speedup. The UNR Research grid‘s massively-parallel computational power (720 processor cores!) was utilized to facilitate running a simple GA (proportional fitness selection, one-point crossover, and one-point mutation) with the following criteria:

  1. Populations: 500, 2500, 5000
  2. Generations: 1000, 5000, 10000
  3. Probability of Crossover: 0.9
  4. Probability of Mutation: 0.001

Chris Miles’ Parallel GA design was adapted for this experiment. The fitness calculation developed for the GA trials is very simple: A bit-string consisting of 50 bits is evaluated based upon its ability to adhere to successive inversion. That is, for each successive bit that is analyzed in a genotype, if the succeeding bit is a complement of the current bit, the genotype’s fitness is awarded a point. For each duplicate successive bit, fitness is deducted one point.

The first data point on the left represents 2 processors. Subsequent datapoints represent 4, 8, 16, and 32 processors respectively. One processor was not examined as I was having trouble meshing that scenario with OpenMPI. Time is measured as 1/Duration of run (inverse of the elapsed time) as instructed. As one can see, there are inconsistencies in the performance assumption that more processors would lead to a decrease in overall algorithm processing time. In the case of population values 500 and 2,500, there is a relative performance increase; however, in the 2,500 population, processing time does tick up marginally when at 16 and 32 processors after a huge drop from 4 to 8 processors. The trials with population 5,000 show a more clear distinction in performance decrease with 16 and 32 processors.

Traveling Salesperson Problem (TSP)

A steady-state genetic algorithm described by DeJong was utilized to optimize five traveling salesperson benchmark problems. The normal steady-state GA employs overlap within the populations, cloning subsequent generations of populations, adding new members to the subsequent population, and rejecting poor performers as to keep the population number stable. Selection is accomplished via the roulette-wheel methodology.

Edge recombination operator (ERO) crossover (Whitley, Starkweather, and Fuquay) is utilized in the pursuit of relevant, efficient paths. This works by taking unions of parent adjacency matrices for nodes and applying simple selection criteria to form a series of nodes with shortest edge-length. This method is superior to indirect one-point crossover in that it produces a greater amount of “legal” node connections.

For each of the TSP problems, the goal was to minimize Cartesian distance traveled to visit every city within a specific set of nodes. Throughout all of the trials, a population size of 50, along with a generational limit of 100 was employed. Mutation was set at 1/10,000 and the probability of ERO crossover was set at 100%.

Berlin52

Mutation [0.1] Crossover [1.0] Pop size [100] Generations [500]

Tour: 35 34 33 43 0 21 30 20 41 6 1 52 29 22 19 49 28 15 45 36 38 39 37 47 23 4 14 5 3 24 11 27 26 25 46 12 13 51 10 50 32 42 8 9 7 40 18 44 2 16 17 31 48

Mean score for final population: 8228.61

Eil51

Mutation [0.1] Crossover [1.0] Pop size [100] Generations [500]

Tour: 32 14 4 37 48 9 38 29 33 49 8 15 20 28 19 34 35 2 21 0 26 50 45 31 10 1 27 30 25 7 47 6 42 23 22 5 13 24 17 3 40 12 51 39 18 41 16 46 11 36 43 44

Mean score for final population: 496.854

Eil76

Mutation [0.1] Crossover [1.0] Pop size [100] Generations [500]

Tour: 25 11 39 43 2 31 24 54 17 49 8 38 30 9 71 57 37 64 65 58 13 10 52 34 7 18 53 12 56 14 69 59 70 68 35 19 36 4 46 20 47 44 28 26 51 33 45 6 66 3 29 73 27 60 21 63 76 41 40 42 55 22 48 23 15 0 61 72 32 62 50 5 1 67 74 75 16

Mean score for final population: 645.923

Lin105

Mutation [0.1] Crossover [1.0] Pop size [50] Generations [500]

Tour: 105 0 1 5 6 2 8 12 3 4 13 16 36 34 25 32 39 103 43 50 47 44 48 37 38 42 46 49 54 55 56 61 104 58 63 62 68 75 89 88 97 98 84 77 67 70 81 76 71 66 79 94 93 99 80 91 83 82 92 100 101 96 95 90 85 78 72 74 73 69 60 64 65 87 86 59 33 41 45 51 53 52 57 40 35 31 29 30 27 23 26 17 24 15 18 14 28 102 20 21 19 22 7 11 9 10

Mean score for final population: 27840.5

Lin318

Mutation [0.2] Crossover [1.0] Pop size [500] Generations [100]

Tour: 13 133 15 5 17 11 2 6 32 39 30 20 31 21 104 51 316 68 57 46 52 40 41 4 106 131 149 201 205 190 221 217 226 213 237 242 253 118 108 121 107 129 113 122 116 249 238 261 283 282 250 256 243 235 180 59 88 23 29 318 1 24 14 102 0 22 26 28 12 114 110 124 115 136 35 42 135 207 308 298 273 271 277 174 185 195 38 33 111 216 232 241 117 128 239 167 170 295 292 203 202 293 175 159 188 153 137 138 225 255 251 264 164 165 193 204 306 301 289 198 246 224 143 156 152 144 134 123 130 141 160 179 73 78 76 63 81 101 100 84 80 67 43 18 36 16 8 3 7 10 9 27 19 25 125 126 140 150 184 177 196 86 66 50 45 56 54 158 257 172 77 82 71 315 49 91 70 47 151 146 148 103 48 199 191 305 155 87 61 85 75 92 200 171 99 182 169 197 286 309 278 310 206 187 181 168 209 37 74 90 69 176 186 263 254 260 189 234 161 280 288 93 72 64 58 96 83 97 95 98 300 178 183 60 65 62 163 162 173 166 157 127 105 132 34 279 266 272 270 244 222 223 214 227 212 211 230 194 302 307 314 268 311 275 274 290 276 299 262 313 259 296 304 303 192 294 291 281 284 297 317 269 248 247 252 154 145 139 119 112 215 228 236 109 210 219 220 312 147 245 231 265 267 287 285 142 240 218 208 53 44 55 79 120 233 229 258 89 94

Mean score for final population: 244395

Simple GA tested on DeJong Functions

A simple genetic algorithm with a population of 50 is run for 100 generations with varying parameters against the 5 standard DeJong functions. The algorithm is run with the following parameters:

  1. p(xOver) = 0.2, p(mut) = 0.0001
  2. p(xOver) = 0.2, p(mut) = 0.001
  3. p(xOver) = 0.2, p(mut) = 0.01
  4. p(xOver) = 0.67, p(mut) = 0.0001
  5. p(xOver) = 0.67, p(mut) = 0.001
  6. p(xOver) = 0.67, p(mut) = 0.01
  7. p(xOver) = 0.99, p(mut) = 0.0001
  8. p(xOver) = 0.99, p(mut) = 0.001
  9. p(xOver) = 0.99, p(mut) = 0.01

The Google Charts API does not seem to have an easy methodology of showing the x-axis labels on their LineChart implementation. The data for the charts below is taken from a complete dataset of 5000 generations; however, for efficiency in rendering the charts, only every 25th datapoint is plotted after the first 100 datapoints.