.png){kind=icon}
Return
Parallel genetic simulated annealing: A massively parallel SIMD algorithm
.png){kind=icon}
PRE
AI
DOI：10.1109/71.663870.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Many significant engineering and scientific problems involve optimization of some criteria over a combinatorial configuration space. The two methods most often used to solve these problems effectively-simulated annealing (SA) and genetic algorithms (GA)-do not easily lend themselves to massive parallel implementations. Simulated annealing is a naturally serial algorithm, while GA involves a selection process that requires global coordination. This paper introduces a new hybrid algorithm that inherits those aspects of GA that lend themselves to parallelization, and avoids serial bottle-necks of GA approaches by incorporating elements of SA to provide a completely parallel, easily scalable hybrid GA/SA method. This new method, called Genetic Simulated Annealing, does not require parallelization of any problem specific portions of a serial implementation-existing serial implementations can be incorporated as is. Results of a study on two difficult combinatorial optimization problems, a 100 city traveling salesperson problem and a 24 word, 12 bit error correcting code design problem, performed on a 16K PE MasPar MP-1, indicate advantages over previous parallel GA and SA approaches. One of the key results is that the performance of the algorithm scales up linearly with the increase of processing elements, a feature not demonstrated by any previous parallel GA or SA approaches, which enables the new algorithm to utilize massive parallel architecture with maximum effectiveness. Additionally, the algorithm does not require careful choice of central parameters, a significant advantage over SA and GA.
Keywords:
genetic algorithms
simulated annealing
parallel algorithms
SIMD
combinatorial optimization
hybrid methods
traveling salesperson
massive parallelism
error correcting codes
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSaveShareSaveRPR203494 a pyrimidine analogue of the p38 inhibitor RPR200765A with an improved in vitro potency
PREAI
ShareSaveDominance of the triplet mechanism in the electron spin polarisation of slowly reacting triplets
PREAI
ShareSave
View more