Abstract: In order to overcome the drawbacks of the simple and normal hybrid Genetic Algorithm (GA), which has poor local searching ability and low computing efficiency, respectively, an asynchronous hybrid GA frame was proposed. Such algorithm frame mainly consists of three parts, which are genetic algorithm, niche operation and simulated annealing. To such proposed algorithm, simulated annealing running in asynchronous way made the main difference when being compared with others. Two computers connected by a switch made up the parallel computing environment. One of the two computers executed genetic algorithm and niche operation and the other executed simulated annealing. The Parallel Virtual Machine (PVM) was used for exchanging data between two computers. Experimental results on Traveling Salesman Problem (TSP) demonstrate that the proposed algorithm is viable and efficient.

Key words: Genetic Algorithm (GA), hierarchy genetic algorithm, simulated annealing, asynchronous operation, Travelling Salesman Problem (TSP), Parallel Virtual Machine (PVM)

摘要： 为克服遗传算法(GA)局部搜索能力差和混合遗传算法计算效率低的不足,提出一个异步混合遗传算法框架。该框架主要由遗传算法、小生境操作和模拟退火三部分组成,模拟退火相对遗传算法和小生境操作采用异步执行方式。并行计算环境由两台计算机通过交换机连接构成,一台计算机计算遗传算法和小生境操作,另外一台计算机计算模拟退火,两台计算机之间通过并行虚拟机进行数据交换。以旅行商问题(TSP)作为算例,实验结果验证了新算法的有效性和高效性。

关键词: 遗传算法, 小生境, 模拟退火, 异步操作, 旅行商问题, 并行虚拟机