基于细菌觅食算法求解折扣{0-1}背包问题的研究
|
摘要
折扣{0-1}背包问题(D{0-1}KP)是新型的0-1背包问题。提出了基于细菌觅食算法(BFO)求解D{0-1}KP的方法,首先描述了D{0-1}KP的两个数学模型,然后将BFO分别与两个数学模型相结合,即细菌个体分别采用二进制向量和四进制向量的编码方法,并利用贪心策略优化初始解和修复非正常编码个体,给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明,FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例,能得到最优解或近似比接近1的近似解。
The Discounted {0-1} Knapsack Problem(D{0-1}KP)is an extension of the classical 0-1 Knapsack Problem(0-1 KP). In this paper, it uses Bacterial Foraging Optimization algorithm(BFO)to solve D{0-1}KP, Firstly, the two mathematical models of the D{0-1}KP are described, and then BFO is combined with the two mathematical models, the bacterial individual uses the binary vector and the four binary vector coding method, and the greedy strategy is used to optimize the initial solution and repair the non normal coding individuals, Fir BFO and Sec BFO algorithms for solving D{0-1}KP are given. The calculations of four instances show that, Fir BFO and Sec BFO are suitable for solving large scale hard D{0-1}KP. And they can also obtain the approximate solution whose approximation rate is almost equal to 1.
The Discounted {0-1} Knapsack Problem(D{0-1}KP)is an extension of the classical 0-1 Knapsack Problem(0-1 KP). In this paper, it uses Bacterial Foraging Optimization algorithm(BFO)to solve D{0-1}KP, Firstly, the two mathematical models of the D{0-1}KP are described, and then BFO is combined with the two mathematical models, the bacterial individual uses the binary vector and the four binary vector coding method, and the greedy strategy is used to optimize the initial solution and repair the non normal coding individuals, Fir BFO and Sec BFO algorithms for solving D{0-1}KP are given. The calculations of four instances show that, Fir BFO and Sec BFO are suitable for solving large scale hard D{0-1}KP. And they can also obtain the approximate solution whose approximation rate is almost equal to 1.
引文
[1]Asho I.Interactive knapsacks:theory and applications[D].Department of Computer and Information Sciences,University of Tampere,2002.
[2]Cord J.A method for allocating funds to investment projects when returns are subject to uncertainty[J].Management Science,1964,10(2):335-341.
[3]Kellerer H,Pferschy U,Pisinger D.Knapsack problems[M].Berlin:Springer,2004.
[4]Alsuwaiyel M H.Algorithms design techniques and analysis[M].[S.l.]:World Scientific Publishing Company,2009.
[5]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].2nd ed.Cambridge:the MIT Press,2001.
[6]Guldan B.Heuristic and exact algorithms for discounted knapsack problems[D].Germany:University of ErlangenNürnberg,2007.
[7]Rong Aiying,Figueira J R,Klamroth K.Dynamic programming based algorithms for the discounted{0-1}knapsack problem[J].Applied Mathematics and Computation,2012,218:6921-6933.
[8]贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2015.
[9]Passino K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems,2002,22(3):52-67.
[10]Mu?oz M A,López J A,Caicedo E.Bacteria swarm foraging optimization for dynamical resource allocation in a multizone temperature experimentation platform[C]//Electronics,Robotics and Automotive Mechanics Conference,2006:137-142.
[11]崔静静,孙延明,车兰秀.改进细菌觅食算法求解车间作业调度问题[J].计算机应用研究,2011,28(9):3325-3326.
[12]Acharya D P,Panda G,Mishra S,et al.Bacteria foraging based independent component analysis[C]//International Conference on Computational Intelligence and Multimedia Applications,2007:527-531.
[13]Majhi R,Panda G,Majhi B,et al.Efficient prediction of stock market indices using Adaptive Bacterial Foraging Optimization(ABFO)and BFO based techniques[J].Expert Systems with Applications,2009,36(6):10099-10104.
[14]王雪松,程玉虎,郝名林.基于细菌觅食行为的分布估计算法在预测控制中的应用[J].电子学报,2010,38(2):333-339.
[15]Panda R,Naik M,Panigrahi B.Face recognition using bacterial foraging strategy[J].Swarm and Evolutionary Computation,2011,1(3):138-146.
[16]Pisinger D.Where are the hard knapsack problems?[J].Computers&Operations Research,2005,32:2271-2284.
[17]Michalewicz Z.A modified genetic algorithm for optimal control problems[J].Computer Math Application,1992,23(12):83-94.
[2]Cord J.A method for allocating funds to investment projects when returns are subject to uncertainty[J].Management Science,1964,10(2):335-341.
[3]Kellerer H,Pferschy U,Pisinger D.Knapsack problems[M].Berlin:Springer,2004.
[4]Alsuwaiyel M H.Algorithms design techniques and analysis[M].[S.l.]:World Scientific Publishing Company,2009.
[5]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].2nd ed.Cambridge:the MIT Press,2001.
[6]Guldan B.Heuristic and exact algorithms for discounted knapsack problems[D].Germany:University of ErlangenNürnberg,2007.
[7]Rong Aiying,Figueira J R,Klamroth K.Dynamic programming based algorithms for the discounted{0-1}knapsack problem[J].Applied Mathematics and Computation,2012,218:6921-6933.
[8]贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2015.
[9]Passino K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems,2002,22(3):52-67.
[10]Mu?oz M A,López J A,Caicedo E.Bacteria swarm foraging optimization for dynamical resource allocation in a multizone temperature experimentation platform[C]//Electronics,Robotics and Automotive Mechanics Conference,2006:137-142.
[11]崔静静,孙延明,车兰秀.改进细菌觅食算法求解车间作业调度问题[J].计算机应用研究,2011,28(9):3325-3326.
[12]Acharya D P,Panda G,Mishra S,et al.Bacteria foraging based independent component analysis[C]//International Conference on Computational Intelligence and Multimedia Applications,2007:527-531.
[13]Majhi R,Panda G,Majhi B,et al.Efficient prediction of stock market indices using Adaptive Bacterial Foraging Optimization(ABFO)and BFO based techniques[J].Expert Systems with Applications,2009,36(6):10099-10104.
[14]王雪松,程玉虎,郝名林.基于细菌觅食行为的分布估计算法在预测控制中的应用[J].电子学报,2010,38(2):333-339.
[15]Panda R,Naik M,Panigrahi B.Face recognition using bacterial foraging strategy[J].Swarm and Evolutionary Computation,2011,1(3):138-146.
[16]Pisinger D.Where are the hard knapsack problems?[J].Computers&Operations Research,2005,32:2271-2284.
[17]Michalewicz Z.A modified genetic algorithm for optimal control problems[J].Computer Math Application,1992,23(12):83-94.