主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
邓亮,赵进,王新.基于遗传算法的网络编码优化.软件学报,2009,20(8):2269-2279
基于遗传算法的网络编码优化
Genetic Algorithm Solution of Network Coding Optimization
投稿时间:2007-12-10  修订日期:2008-04-30
DOI:
中文关键词:  组播  网络编码  优化  启发式  遗传算法
英文关键词:multicast  network coding  optimization  heuristic  genetic algorithm
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60702054 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z203 (国家高技术研究发展计划(863)); the Shanghai Rising-Star Program of China under Grant No.08QA14009 (上海市科委启明星计划); the Shanghai Educational Development Foundation of China under Grant No.2007CG07 (上海市教育发展基金会)
作者单位
邓亮 复旦大学 计算机科学技术学院,上海 200433 
赵进 复旦大学 计算机科学技术学院,上海 200433 
王新 复旦大学 计算机科学技术学院,上海 200433 
摘要点击次数: 4132
全文下载次数: 4218
中文摘要:
      在前人优化研究方法的基础上,结合网络编码优化问题自身的特点提出了新的解决方案.首先是算法的预处理部分:1) 给出了统一的方法由不同的资源描述函数生成遗传算法所必须的适应值函数,使得各种不同的网络编码资源优化问题都能利用同样的遗传算法模型;2) 通过检验有多条输入链路的输出链路进一步缩小优化算法的搜索范围.其次,针对网络编码资源优化问题随机解几乎不能让所有接收者都达到组播速率的特点,在一般的遗传算法中加入以下新的处理:1) 在初始化阶段使用更为精细的算法产生更高质量的初始成员.2) 在遗传算法每次循环开始时额外调用初始成员生成算法,加入一定数量的新成员,从而避免了局部性问题.3) 对于不能达到最大组播速率的网络编码方案,基于各个接收者各自的接收速率确定更为合适的适应值而不是统一设为?1,从而使这些方案也能参与算法的进一步处理而不是完全被淘汰.模拟实验结果显示,新的优化算法不仅运行得更快,而且输出的网络编码方案所消耗的资源也更少.
英文摘要:
      After the best optimizing approach of network coding is being studied, some methods are proposed based on the characteristics of the network coding overhead optimization problem. First, two modifications are added to the preprocessing phase: 1) How to generate a fitness value to a network coding scheme under a certain network coding optimization request is presented. This makes different network coding optimization problems be solved with the same genetic algorithm. 2) An additional exam processing of the multi-in outgoing links is imported to reduce the solution space. Second, experimental results show that the random generated solution of network coding optimization problem can hardly achieve the multicast rate, three new steps are suggested be taken with the common genetic algorithm: 1) use more delicate member generating function to generate initial members; 2) add new members at the beginning of each round of the genetic algorithm to avoid localized optimization; 3) assign a fitness value based on each receiver’s data rate rather than ?1 to those network coding solutions which cannot achieve the max multicast rate. Experimental results show dramatic improvements in terms of both efficiency and result.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利