Internet中基于启发式遗传算法的受限镜像放置问题求解  

Solving Constrained Mirror Placement Problem Based on Heuristic Genetic Algorithm in Internet

作　　者：郭常杰[1] 钟玉琢[1] 林闯[1] 

机构地区：[1]清华大学计算机系,北京100084

出　　处：《电子学报》2002年第5期689-693,共5页Acta Electronica Sinica

基　　金：国家自然科学基金 (No .699730 2 5);973项目 (No.G1 9990 32 70 0 )

摘　　要：求解受限镜像放置问题对于Internet内容提供商具有重要的应用价值 ,但其在数学上归结为k supplier问题 ,是一个NPC问题 .本文提出了一种求解受限镜像放置问题的启发式遗传算法 ,该算法采用启发式交叉和变异算子 ,本质上是对标准两点交叉和单点变异产生的非法染色体进行启发式修正 ,以提高算法的局部搜索能力 ,加速收敛 .仿真实验详细考察了启发式算子对收敛速度与全局优化性能的影响 ,并与两种常用启发式算法进行了性能比较 .实验结果表明本文算法具有快速收敛 ,高性能 ,全局收敛等优点 。Solving constrained mirror placement problem is very valuable to content providers in Internet.Constrained mirror placement problem can be modeled as a k supplier problem,which belongs to NP Complete problem and has only best possible 3 approximate algorithm.A heuristic genetic algorithm is presented in this paper,which uses the heuristic algorithm to revise the new illegal chromosome generated by standard two points crossover and one point mutation operations.The simulation results suggest that the algorithm is feasible and effective.

关 键 词：INTERNET 启发式遗传算法 受限镜像放置问题求解 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术]