基于Elmore模型的Steiner树问题的求解

Solution for Steiner tree problem based on Elmore model

建立了一种求解基于Elmore延迟模型的Steiner树问题的遗传算法。针对Steiner树问题的特点,在引入一种新的具有自适应性的杂交概率和变异概率的基础上,提出了面向Steinet树问题的遺传算法和一种构造染色体的新方法。提供了遗传算法的结构并讨论了遗传算子。分析了基于时间和空间的算法复杂性。

A genetic algorithm of the Steiner tree problem is given. Accoroling to the character of the problem on the basis of introducing a new method with self-adaptive commute and mutate probability a new genetic algorithm for Steiner tree problem and a new method for constructing chromsome are presented. The structure of genetic algorithms is provided and its genetic algorithm operators are discussed. The complexity of algorithm based on time and space is analyzed.