A Differential BPSO-GA Hybrid Algorithm for Discrete Combination Optimization
详细信息 查看官网全文
- 英文论文题名：A Differential BPSO-GA Hybrid Algorithm for Discrete Combination Optimization
- 论文作者：Yimin Zhou ; Zhifei Li ; Chaofang Hu
- 英文论文作者：Yimin Zhou ; Zhifei Li ; Chaofang Hu ; Shenzhen Institutes of Advanced Technology ; Chinese Academy of Sciences ; The Chinese University of Hong Kong ; Tianjin University
- 年：2017
- 作者机构：Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences;The Chinese University of Hong Kong;Tianjin University;
- 英文论文关键词：Combination optimization ; Particle swarm optimization ; Genetic algorithm ; Traveling salesman problem ; Knapsack problem
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：O221.7;TP18
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：5
- 文件大小：365k
- 原文格式：D
- 会议级别：全国
摘要
There are a lot of typical statistical problems in discrete combination optimization, including integer linear programming, covering problem, knapsack problem, graph theory, network flow and dispatching. As for the NPC(Non-deterministic Polynomial complete) problems, many algorithms have been developed for the discrete optimization where the heuristic algorithm is one kind of the important and effective methods. In this paper, a new swarm intelligent algorithm is proposed, combined with BPSO(Binary Particle Swarm Optimization), GA(Genetic Algorithm) and maximum difference calculation, to solve the TSP and Knapsack two typical discrete combination optimal problems. The proposed algorithm can search the historical memory and differentiated search strategy is introduced to keep the diversity of the group so as to select the elite gene features as the candidates. Experiments are designed and performed to analyze the convergence of the algorithm and the solutions are obtained in high-dimensional searching space. As for the binary combination problem, results demonstrate that the developed algorithm has faster convergence speed and higher quality compared to the traditional swarm intelligent algorithms.
There are a lot of typical statistical problems in discrete combination optimization, including integer linear programming, covering problem, knapsack problem, graph theory, network flow and dispatching. As for the NPC(Non-deterministic Polynomial complete) problems, many algorithms have been developed for the discrete optimization where the heuristic algorithm is one kind of the important and effective methods. In this paper, a new swarm intelligent algorithm is proposed, combined with BPSO(Binary Particle Swarm Optimization), GA(Genetic Algorithm) and maximum difference calculation, to solve the TSP and Knapsack two typical discrete combination optimal problems. The proposed algorithm can search the historical memory and differentiated search strategy is introduced to keep the diversity of the group so as to select the elite gene features as the candidates. Experiments are designed and performed to analyze the convergence of the algorithm and the solutions are obtained in high-dimensional searching space. As for the binary combination problem, results demonstrate that the developed algorithm has faster convergence speed and higher quality compared to the traditional swarm intelligent algorithms.
There are a lot of typical statistical problems in discrete combination optimization, including integer linear programming, covering problem, knapsack problem, graph theory, network flow and dispatching. As for the NPC(Non-deterministic Polynomial complete) problems, many algorithms have been developed for the discrete optimization where the heuristic algorithm is one kind of the important and effective methods. In this paper, a new swarm intelligent algorithm is proposed, combined with BPSO(Binary Particle Swarm Optimization), GA(Genetic Algorithm) and maximum difference calculation, to solve the TSP and Knapsack two typical discrete combination optimal problems. The proposed algorithm can search the historical memory and differentiated search strategy is introduced to keep the diversity of the group so as to select the elite gene features as the candidates. Experiments are designed and performed to analyze the convergence of the algorithm and the solutions are obtained in high-dimensional searching space. As for the binary combination problem, results demonstrate that the developed algorithm has faster convergence speed and higher quality compared to the traditional swarm intelligent algorithms.
引文
[1]Korte B.,Vygen J.,Korte B.,et.al.‘Combinatorial optimization’,Heidelberg:Springer,2012.
[2]Nemhauser G.L,Savelsbergh M.and Sigismondi G.C.‘Constraint classification for mixed integer programming formulations’,Coal Bulletin,1991,pp.1-10.
[3]Cormen T.H.,Leiserson C.E.,Rivest R.L.and Stein C.‘Greedy algorithms,in Introduction to Algorithms’,The 3rd Edition,Cambridge,MA,USA:MIT Press,2009,ch.16,sec.16.2,pp.423C428.
[4]Adubi S.A.and Misra S.‘A comparative study on the ant colony optimization algorithms’,The 11th IEEE International Conference on Electronics,Computer and Computation(ICECCO),2014,pp.1-4.
[5]Socha K,Dorigo M.‘Ant colony optimization for continuous domains’,European journal of operational research,2008,185(3):1155-1173.
[6]Gajpal Y.and Abad P.L.,‘Multi-ant colony system(MACS)for a vehicle routing problem with backhauls’,European Journal of Operational Research,2009,196(I):102-117.
[7]Rahim S.,Khan S.A.,Javaid N.,et.al.,‘Towards multiple knapsack problem approach for home energy management in smart grid’,The 18th IEEE International Conference on Network-Based Information Systems(NBi S),2015,pp.48-52.
[8]Jemai J.,Chaieb M.and Mellouli K.‘The home care scheduling problem:A modeling and solving issue’,The 5th IEEE International Conference on Modeling,Simulation and Applied Optimization(ICMSAO),2013,pp.1-6.
[9]Bali O.,Elloumi W.,Kromer P.,et al.‘GPU Particle Swarm Optimization Applied to Travelling Salesman Problem’,IEEEInternational Symposium on Embedded Multicore/many-Core Systems-On-Chip,2015,pp.112-119.
[10]Kaur K.,Dua A.,Jindal A.,et.al.‘A novel resource reservation scheme for mobile PHEVs in V2G environment using game theoretical approach’,IEEE Transactions on Vehicular Technology,2015,64(12):5653-5666.
[11]Sheikhalishahi M.,Ebrahimipour V.and Shiri H.‘A hybrid GACPSO approach for reliability optimization in redundancy allocation problem’,The International Journal of Advanced Manufacturing Technology,2013,68(1):317-338.
[12]Jaengchuea S.and Lohpetch D.‘A hybrid genetic algorithm with local search and tabu search approaches for solving the post enrolment based course timetabling problem:outperforming guided search genetic algorithm’,The 7th IEEE International Conference on Information Technology and Electrical Engineering(ICITEE),2015,pp.29-34.
[13]Ke L.,Zhang Q.and Battiti R.‘Hybridization of decomposition and local search for multi-objective optimization’,IEEEtransactions on cybernetics,2014,44(10):1808-1820.
[14]Eusuff M.M.and Lansey K.E.‘Water distribution network design using the shuffled frog leaping algorithm’,Water and Environmental Resources Congress.2001,pp.1-8.
[15]Zhang Y.,Wang S.and Ji G.‘A comprehensive survey on particle swarm optimization algorithm and its applications’,Mathematical Problems in Engineering,2015,1:1-38.
[16]Babatunde O.,Armstrong L.,Leng J.,et al.‘A genetic algorithm-based feature selection’,British Journal of Mathematics&Computer Science,2014,4(21):889-905.
[17]http://yarpiz.com/53/ypea103-ant-colony-optimization
[18]Papadimitriou C.H.‘The Euclidean travelling salesman problem is NP-complete’,Theoretical computer science,1977,4(3):237-244.
[19]Martello S.and Toth P.‘Knapsack problems:algorithms and computer implementations’,John Wiley&Sons,Inc.,1990.
[2]Nemhauser G.L,Savelsbergh M.and Sigismondi G.C.‘Constraint classification for mixed integer programming formulations’,Coal Bulletin,1991,pp.1-10.
[3]Cormen T.H.,Leiserson C.E.,Rivest R.L.and Stein C.‘Greedy algorithms,in Introduction to Algorithms’,The 3rd Edition,Cambridge,MA,USA:MIT Press,2009,ch.16,sec.16.2,pp.423C428.
[4]Adubi S.A.and Misra S.‘A comparative study on the ant colony optimization algorithms’,The 11th IEEE International Conference on Electronics,Computer and Computation(ICECCO),2014,pp.1-4.
[5]Socha K,Dorigo M.‘Ant colony optimization for continuous domains’,European journal of operational research,2008,185(3):1155-1173.
[6]Gajpal Y.and Abad P.L.,‘Multi-ant colony system(MACS)for a vehicle routing problem with backhauls’,European Journal of Operational Research,2009,196(I):102-117.
[7]Rahim S.,Khan S.A.,Javaid N.,et.al.,‘Towards multiple knapsack problem approach for home energy management in smart grid’,The 18th IEEE International Conference on Network-Based Information Systems(NBi S),2015,pp.48-52.
[8]Jemai J.,Chaieb M.and Mellouli K.‘The home care scheduling problem:A modeling and solving issue’,The 5th IEEE International Conference on Modeling,Simulation and Applied Optimization(ICMSAO),2013,pp.1-6.
[9]Bali O.,Elloumi W.,Kromer P.,et al.‘GPU Particle Swarm Optimization Applied to Travelling Salesman Problem’,IEEEInternational Symposium on Embedded Multicore/many-Core Systems-On-Chip,2015,pp.112-119.
[10]Kaur K.,Dua A.,Jindal A.,et.al.‘A novel resource reservation scheme for mobile PHEVs in V2G environment using game theoretical approach’,IEEE Transactions on Vehicular Technology,2015,64(12):5653-5666.
[11]Sheikhalishahi M.,Ebrahimipour V.and Shiri H.‘A hybrid GACPSO approach for reliability optimization in redundancy allocation problem’,The International Journal of Advanced Manufacturing Technology,2013,68(1):317-338.
[12]Jaengchuea S.and Lohpetch D.‘A hybrid genetic algorithm with local search and tabu search approaches for solving the post enrolment based course timetabling problem:outperforming guided search genetic algorithm’,The 7th IEEE International Conference on Information Technology and Electrical Engineering(ICITEE),2015,pp.29-34.
[13]Ke L.,Zhang Q.and Battiti R.‘Hybridization of decomposition and local search for multi-objective optimization’,IEEEtransactions on cybernetics,2014,44(10):1808-1820.
[14]Eusuff M.M.and Lansey K.E.‘Water distribution network design using the shuffled frog leaping algorithm’,Water and Environmental Resources Congress.2001,pp.1-8.
[15]Zhang Y.,Wang S.and Ji G.‘A comprehensive survey on particle swarm optimization algorithm and its applications’,Mathematical Problems in Engineering,2015,1:1-38.
[16]Babatunde O.,Armstrong L.,Leng J.,et al.‘A genetic algorithm-based feature selection’,British Journal of Mathematics&Computer Science,2014,4(21):889-905.
[17]http://yarpiz.com/53/ypea103-ant-colony-optimization
[18]Papadimitriou C.H.‘The Euclidean travelling salesman problem is NP-complete’,Theoretical computer science,1977,4(3):237-244.
[19]Martello S.and Toth P.‘Knapsack problems:algorithms and computer implementations’,John Wiley&Sons,Inc.,1990.