基于复杂网络特征的背包问题优化算法

• 作者: 王孙安 袁明新 邸宏宇 陈乃建
• 来源期刊: 系统工程与电子技术
• 学科: 工学
• 关键词: 优化算法 复杂网络 马尔科夫链 背包问题 无标度 小世界现象
• 年，卷（期）: 2009,（9）
• 所属期刊栏目: 软件、算法与仿真
• 页码范围: 2232-2237
• 页数: 6页
• 分类号: TP18
• 字数: 7390字
• 语种: 中文
• DOI: 10.3321/j.issn:1001-506X.2009.09.045

摘要

根据复杂网络演化过程中的小世界现象及无标度特征,提出了基于复杂网络的背包问题优化算法.该算法基于无标度特征的背包问题形成优化空间,通过节点增长和加权节点度偏好连接,产生优化空间网络及其节点度分布;在该优化空间网络中,以小世界网络的聚类及小世界效应为基础,以节点度分布为先验知识,提出局部聚类、小世界效应、链集优化和节点寻优4个算子,实现网络节点连接优化.利用马尔科失链的相关性质,证明了该算法的收敛性.针对具有相关性的0/1背包问题的实验结果表明,该算法解决组合优化问题是有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王孙安	西安交通大学机械工程学院	128	2802	30.0	48.0
2	陈乃建	西安交通大学机械工程学院	6	27	3.0	5.0
3	邸宏宇	西安交通大学机械工程学院	2	21	2.0	2.0
4	袁明新	西安交通大学机械工程学院	6	38	3.0	6.0