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

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

Knapsack-problem optimization algorithm based on complex network

Based on the small world phenomenon and the characters of scale-free network in evolutions of complex network,a new optimization algorithm,knapsack-problem optimization algorithm based on complex network(KOABCN),is put forward.There are two main steps in proposed algorithm: Firstly,knapsack-problem optimization space,with nodes increasing and weighted nodes’ degree preferential attachments,is formed,the scale-free network and degree distribution of nodes are presented.Secondly,taking nodes’ degree distribution in optimization space as prior knowledge,four operators,clustering,small world effect,adjust and optimal,are proposed to optimize attachments between nodes based on clustering and small world effect.Using Markov chain,the algorithm is proved to be convergent.Compared with other algorithms,KOABCN is shown to be an effective strategy to solve the combination optimization problem,such as 0/1 knapsack problem.