CAJ | 학술논문

图的Steiner最小树问题是经典的组合优化问题，在通信网络和电路设计中有广泛应用。文中在遗传算法的基础上，对交叉率pc和变异率pm采用自适应过程，构造一种新的确定pc和pm的公式，有效解决了参数选取对最终结果的影响问题。再与模拟退火算法相结合，提出了一种解决Steiner最小树问题的混合遗传算法。该算法克服了遗传算法易早熟和收敛性能差的缺点，有效地增强了算法的进化能力。通过对OR-Library的部分实例进行计算结果表明，在大多数情况下混合遗传算法比遗传算法有更好的性能。
도적Steiner최소수문제시경전적조합우화문제，재통신망락화전로설계중유엄범응용。문중재유전산법적기출상，대교차솔pc화변이솔pm채용자괄응과정，구조일충신적학정pc화pm적공식，유효해결료삼수선취대최종결과적영향문제。재여모의퇴화산법상결합，제출료일충해결Steiner최소수문제적혼합유전산법。해산법극복료유전산법역조숙화수렴성능차적결점，유효지증강료산법적진화능력。통과대OR-Library적부분실례진행계산결과표명，재대다수정황하혼합유전산법비유전산법유경호적성능。
The Graphical Steiner tree Problem ( GSP) is a classical combinatorial optimization problem,which has been widely used in communication network and the circuit design. In this paper,on the basis of genetic algorithm,apply the adaptive process for the crossover rate and mutation rate,to construct a new formula determining the crossover rate and mutation rate,effectively solving the problem of pa-rameters selection on the final result. Combined with the simulated annealing algorithm,propose a hybrid genetic algorithm to solve the problem of minimum Steiner tree. The algorithm overcomes the faults of genetic algorithm is easy to premature and poor convergence per-formance,effectively enhancing the capacity of the evolution of the algorithm. By the OR-Library test case calculation results show that, in most cases,the hybrid genetic algorithm has better performance than genetic algorithm.