最速网络消息传播问题及其模拟进化算法  

Fastest network message spreading problem and its simulated evolutionary algorithm

作　　者：何胜学[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机应用研究》2011年第8期3097-3099,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(70672110);上海市(第三期)重点学科项目(S30504);上海市优秀青年教师基金资助项目(slg08018);上海市教委科技创新项目(10YS105);上海理工大学博士启动基金资助项目(1D-00-307005)

摘　　要：首次提出了最速网络消息传播问题族,建立了其基本问题的严格数学模型,并给出了相应的模拟进化求解算法。通过分析最速网络消息传播基本问题的特征,包括决策变量的特点、决策的网络时空影响特殊模式以及网络消息分布状态特点,构建了问题的最优化模型,并分析了该模型的可扩展性。利用决策变量的二元取值特点和单一轮次信息交互模式的相对独立性,设计了操作灵活的遗传算法复制、交叉和变异算子,实现了模型的模拟进化求解。数值算例验证了模型和算法的有效性。研究表明,最速网络消息传播问题基本模型可扩展性强;遗传算法是该问题的一种有效的求解方法。For the first time,this paper proposed the class of fastest network message spreading problems.Formulated the ba-sic problem of the class in strict mathematics.Provided the corresponding simulated evolutionary algorithm.Through analysing the characteristics of the basic fastest network message spreading problem that including the features of decision variables,the special pattern of the spatial and temporal impacts of decision-makings and the distribution features of network messages,built the optimal model of the problem.Analysed the extendibility of the model.Taking advantage of the binary feature of decision variables and the relative independence of the pattern of single round information interchanging,designed the reproduction operator,the crossover operator and the mutation operator of genetic algorithm that could be manipulated flexibly.So realized the simulated evolutionary solving of the model.The numerical example demonstrates the effectiveness of the model and the algorithm.The results show that the basic model of fastest network message spreading problems has strong extendibility and genetic algorithm is an effective way to solve these problems.

关 键 词：系统工程 网络优化 消息传播 遗传算法 网络信息 

分 类 号：O221[理学—运筹学与控制论] O157.6[理学—数学]