摘要
针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题,提出了一种解决多维背包问题的二进制编码小世界算法(BSWA).BSWA算法依据社会学中的小世界现象搜索机理,采用类似遗传变异操作的局部搜索,而非遗传算法中的交叉操作.针对多维背包问题的多约束性,BSWA算法还按照价值资源比大小对不可行解进行贪婪修正,以保证求解的正确性.与遗传算法相比,BSWA可以在一定程度上克服早熟收敛,在保持种群多样性和求解精度方面均体现出较大的优势,具有解决复杂组合优化问题的潜力.对55个标准的多约束0-1背包问题进行了50次随机实验,结果表明,BSWA算法对于其中72.73%的问题可以次次获得最优解,对于其他不能次次求解到最优解的问题,也可以获得非常接近全局最优解的满意解.
In order to overcome the shortcomings of genetic algorithms （GA）, an optimization algorithm called the binary-coding small world algorithm （BSWA） is proposed. The GA always loses diversity in the set of the candidate solutions and prematurely converges when it is used to solve complex combinatorial optimization problems. The BSWA is based on the searching mechanisms in social networks, and emphasizes local （as mutation in GA） rather than global search （as crossover in GA） to find solutions for optimization problems. Compared with the GA, the BSWA is capable of preserving diversity and avoiding premature convergence, and converges faster. These properties suggest that the BSWA is a useful method for solving complicated optimization problems. Simulation results show that the best known solutions of 72.73% of the 55 standard 0- 1 knapsack problems can be found by the BSWA in each of the 50 independent runs, and the final solutions found by the BSWA for the other problems are very close to the best known ones.
出处
《西安交通大学学报》
EI
CAS
CSCD
北大核心
2009年第2期10-14,共5页
Journal of Xi'an Jiaotong University
基金
国家自然科学基金资助项目(70671083)
教育部新世纪优秀人才支持计划资助项目(NCET-07-0668)
长江学者奖励计划项目
美国Santa Fe Institute国际基金资助项目
斯坦福大学联合资助项目
西安交通大学"985工程"二期重点资助项目(07200701)
关键词
小世界算法
多维背包问题
贪婪修正算子
small world algorithm
multidimensional knapsack problem
greedy correcting operator
