Parallelization of population-based evolutionary algorithms for combinatorial optimization problems

摘要: The objective of the present work is to make efficient parallelization evolutionary algorithms (EA) easier in order solve large instances difficult combinatorial optimization problems within an acceptable amount time, on parallel computer architectures. No known technique allows one exactly such (NP-complete). Moreover, traditional heuristics that are used find sub-optimal solutions not always satisfactory since they easily attracted by local optima. Evolutionary (EA), inspired natural evolution mechanisms, explore different regions search space concurrently. They thus rarely trapped a optimum and well suited treat problems. Their behavior can be improved hybridizing (i.e., combining) them with other (EA or not). Unfortunately, greedy computation power memory space. It interesting parallelize them. Indeed, use computers (with dozens processors) speed up execution EAs provides require. possible take benefit intrinsic parallelism (e.g., for concurrent exploration space) design implementations. However each EA has its own characteristics therefore general rule cannot defined. This thesis starts description state art which existing approaches terminologies outlined. fundamental ingredients then detailed these grouped classification tool called TEA (Table Algorithms). table taken as basis analysis criteria influence define rules. considers especially implementation hybrid MIMD-DM1 A notation granularity proposed. Further this analysis, object-oriented library named APPEAL (Advanced Parallel Population-based Algorithm Library) applies rules designed experimentally validate During experiments, executed network workstations two problems: first best set transceiver sites mobile radio second classical graph coloring problem. Finally, comparison results discussion about future conclude thesis. --------------------1MIMD-DM stands Multiple Instruction stream, Data Distributed Memory.