Binary accelerated particle swarm algorithm (BAPSA) for discrete optimization problems. (English) Zbl 1315.90033

Beheshti, Zahra; Shamsuddin, Siti Mariyam; Yuhaniz, Siti Sophiayati

J. Glob. Optim. 57, No. 2, 549-573 (2013).

Summary: The majority of Combinatorial Optimization Problems (COPs) are defined in the discrete space. Hence, proposing an efficient algorithm to solve the problems has become an attractive subject in recent years. In this paper, a meta-heuristic algorithm based on Binary Particle Swarm Algorithm (BPSO) and the governing Newtonian motion laws, so-called Binary Accelerated Particle Swarm Algorithm (BAPSA) is offered for discrete search spaces. The method is presented in two global and local topologies and evaluated on the 0-1 Multidimensional Knapsack Problem (MKP) as a famous problem in the class of COPs and NP-hard problems. Besides, the results are compared with BPSO for both global and local topologies as well as Genetic Algorithm (GA). We applied three methods of Penalty Function (PF) technique, Check-and-Drop (CD) and Improved Check-and-Repair Operator (ICRO) algorithms to solve the problem of infeasible solutions in the \(0-1\) MKP. Experimental results show that the proposed methods have better performance than BPSO and GA especially when ICRO algorithm is applied to convert infeasible solutions to feasible ones.

MSC:

90C27

Combinatorial optimization

Keywords:

combinatorial optimization problem; NP-hard problem; meta-heuristic algorithm; binary particle swarm optimization; binary accelerated particle swarm algorithm; multidimensional knapsack problem

Software:

OR-Library; MINTO

References:

[1]	Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.: Combinatorial Optimization. Springer, Berlin (1997)
[2]	Neapolitan R., Naimipour K.: Foundations of Algorithms Using C++ Pseudo Code, 3rd edn. Jones and Bartlett, Massachusetts (2004) · Zbl 1227.68001
[3]	Chu P.C., Beasley J.E.: A genetic algorithm for the multidimensional knapsack problem. J. Heuristics 4(1), 63-86 (1998) · Zbl 0913.90218
[4]	Snyder L.V., Daskin M.S.: A random-key genetic algorithm for the generalized traveling salesman problem. Eur. J. Oper. Res. 174, 38-53 (2006) · Zbl 1116.90091
[5]	Din D.: Heuristic and simulated annealing algorithms for wireless ATM backbone network design problem. J. Inf. Sci. Eng. 24, 483-501 (2008)
[6]	Andresen M., Bräsel H., Mörig M., Tusch J., Werner F., Willenius P.: Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop. Math. Comput. Model. 48, 1279-1293 (2008) · Zbl 1187.90127
[7]	Engin O., Döyen A.: A new approach to solve hybrid flowshop scheduling problems by artificial immune system. Future Gener. Comput. Syst. 20(6), 1083-1095 (2004)
[8]	Du W., Du H., Li M.: Hyper-mutation antibody clone algorithms for TSP. J. Xidian Univ. 36, 527-534 (2009)
[9]	Kong M., Tian P., Kao Y.C.: A new ant colony optimization algorithm for the multidimensional Knapsack problem. Comput. Oper. Res. 35(8), 2672-2683 (2008) · Zbl 1169.90435
[10]	Yang J., Shi X., Marchese M., Liang Y.: An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 18(11), 1417-1422 (2008)
[11]	Labed S., Gherboudj A., Chikhi S.: A modified hybrid particle swarm optimization algorithm for multidimensional knapsack problem. Int. J. Comput. Appl. 34(2), 11-16 (2011)
[12]	Shi X.H., Liang Y.C., Lee H.P., Lu C., Wang Q.X.: Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf. Process. Lett. 103(5), 169-176 (2007) · Zbl 1187.90238
[13]	Fadlaoui K., Galinier P.: A tabu search algorithm for the covering design problem. J. Heuristics 17(6), 659-674 (2011) · Zbl 1237.90192
[14]	James T., Rego C., Glover F.: Multistart tabu search and diversification strategies for the quadratic assignment problem. IEEE Trans. Syst. Man Cybern. Part A 39(3), 579-596 (2009)
[15]	Zhu W., Curry J., Marquez A.: SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration. Int. J. Prod. Res. 48, 1035-1047 (2009) · Zbl 1197.90281
[16]	Leung Y., Gao Y., Xu Z.B.: Degree of population diversity—a perspective on premature convergence in genetic algorithms and its Markov chain analysis. IEEE Trans. Neural Netw. 8(5), 1165-1176 (1997)
[17]	Hrstka O., Kučerová A.: Improvements of real coded genetic algorithms based on differential operators preventing premature convergence. Adv. Eng. Softw. 35, 237-246 (2004)
[18]	Moslemipour G., Lee T.S., Rilling D.: A review of intelligent approaches for designing dynamic and robust layouts in flexible manufacturing systems. Int. J. Adv. Manuf. Technol. 60, 11-27 (2012)
[19]	Gao W.F., Liu S.Y., Huang L.L.: Particle swarm optimization with chaotic opposition based population initialization and stochastic search technique. Commun. Nonlinear Sci. Numer. Simul. 17(11), 4316-4327 (2012) · Zbl 1254.90300
[20]	Mendes R., Kennedy J., Neves J.: The fully informed particle swarm: simpler maybe better. IEEE Trans. Evol. Comput. 8(3), 204-210 (2004)
[21]	Liang J.J., Qin A.K., Suganthan P.N., Baskar S.: comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans. Evol. Comput. 10(3), 281-295 (2006)
[22]	Zhan Z.H., Zhang J., Li Y., Chung H.S.: Adaptive particle swarm optimization. IEEE Trans. Syst. Man Cybern. Part B 39(6), 1362-1381 (2009)
[23]	Holland J.H: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan (1975)
[24]	Lau H.C.W., Chan T.M., Tsui W.T., Pang W.K.: Application of genetic algorithms to solve the multidepot vehicle routing problem. IEEE Trans. Autom. Sci. Eng. 7(2), 383-392 (2010)
[25]	Ahuja P.K., Orlin J.B., Tiwari A.: A greedy genetic algorithm for the quadratic assignment problem. Comput. Oper. Res. 27((10), 917-934 (2000) · Zbl 0970.90067
[26]	Zhang Q., Manier H., Manier M.A.: A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraint and bounded processing times. Comput. Oper. Res. 39, 1713-1723 (2012) · Zbl 1251.90208
[27]	Lee Z.J., Su S.F., Chiang C.C., Liu K.H.: Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Appl. Soft Comput. 8(1), 55-78 (2008)
[28]	Defersha F.M., Chen M.Y.: A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots. Int. J. Prod. Res. 48(6), 1705-1726 (2010) · Zbl 1197.90201
[29]	Kirkpatrick S., Gelatto C.D., Vecchi M.P.: Optimization by simulated annealing. Science 220, 671-680 (1983) · Zbl 1225.90162
[30]	Defersha F.M., Chen M.: A simulated annealing algorithm for dynamic system reconfiguration and production planning in cellular manufacturing. Int. J. Manuf. Tech. Manage. 17(1-2), 103-124 (2009)
[31]	Sun Y., Zhang M., Liu W., Li H., Zhang L.: Permutation algorithm with simulated annealing for laser antimissile problem. Appl. Mech. Mater. 44(47), 265-269 (2011)
[32]	Safari E., Sadjadi S.J., Shahanaghi K.: Scheduling flowshops with condition-based maintenance constraint to minimize expected makespan. Int. J. Adv. Manuf. Technol. 46, 757-767 (2010)
[33]	Hashemi S.M., Rezapour M., Moradi A.: An effective hybrid PSO-based algorithm for planning UMTS terrestrial access networks. Eng. Optim. 42(3), 251-311 (2010)
[34]	Glover F., McMillan C.: The general employee scheduling problem: an integration of MS and AI. Comput. Oper. Res. 13(5), 563-573 (1986)
[35]	Glover F.: Tabu search—part 1. Inf. J. Comput. 1(2), 190-206 (1989) · Zbl 0753.90054
[36]	Glover F.: Tabu search—part 2. Inf. J. Comput. 2(1), 4-32 (1990) · Zbl 0771.90084
[37]	James T., Rego C., Glover F.: A cooperative parallel tabu search algorithm for the quadratic assignment problem. Eur. J. Oper. Res. 195, 810-826 (2007) · Zbl 1156.90400
[38]	Eswaramurthy V.P., Tamilarasi A.: Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems. Int. J. Adv. Manuf. Technol. 40, 9-10 (2009) · Zbl 1184.90173
[39]	Kennedy, J., Eberhart, R.C.: A discrete binary version of the particle swarm algorithm. In: Proceedings of IEEE International Conference on Computational Cybernetics and Simulation, pp. 4104-4109. Orlando, USA (1997) · Zbl 0771.90084
[40]	Al-Kazemi, B., Mohan, C.K.: Discrete multi-phase particle swarm optimization. In: Grana, M., Duro, R., d’Anjou, A., Wang, P.P. (eds.) Information Processing with Evolutionary Algorithms. Advanced Information and Knowledge Processing, pp. 305-327. Springer, Heidelberg (2005)
[41]	Clerc, M.: http://clerc.maurice.free.fr/pso/
[42]	Anghinolfi D., Paolucci M.: A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. Eur. J. Oper. Res. 193(1), 73-85 (2009) · Zbl 1152.90423
[43]	Liao C.J., Tseng C.T., Luarn P.: A discrete version of particle swarm optimization flow shop scheduling problems. Comput. Oper. Res. 34(10), 3099-3111 (2007) · Zbl 1185.90083
[44]	Jin Y.X., Cheng H.Z., Yan J.Y., Zhang L.: New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electr. Power Syst. Res. 77(3-4), 227-233 (2007)
[45]	Pan Q.K., Tasgentiren M.F., Liang Y.C.: A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Comput. Oper. Res. 35(9), 2807-2839 (2008) · Zbl 1144.90393
[46]	Tseng C.T., Liao C.J.: A discrete particle swarm optimization for lot-streaming flow shop scheduling problem. Eur. J. Oper. Res. 191(2), 360-373 (2008) · Zbl 1149.90064
[47]	Lian Z., Gu X., Jiao B.: A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan. Chaos Solitons Fractals 35(5), 851-861 (2008) · Zbl 1146.90418
[48]	Gherboudj, A., Chikhi, S.: BPSO algorithms for knapsack problem (2011). doi:10.1007/978-3-642-21937-5_20 · Zbl 0970.90067
[49]	Dorigo, M.: Optimization, learning and natural algorithms (in Italian). PhD thesis, Department of Electronics and Information Polytechnic of Milan, Italy (1992)
[50]	Dorigo M., Maniezzo V., Colorni A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B 26(1), 29-41 (1996)
[51]	Dorigo M., Caro G.D., Gambardella L.M.: Ant algorithms for discrete optimization. Artif. Life 5(2), 1-36 (1999)
[52]	Saber A.Y., Senjyu T.: Memory-bounded ant colony optimization with dynamic programming and a local search for generator planning. IEEE Trans. Power Syst. 22(4), 1965-1973 (2007)
[53]	Jang S.H., Roh J.H., Kim W., Sherpa T., Kim J.H., Park J.B.: A novel binary ant colony optimization: application to the unit commitment problem of power systems. J. Electr. Eng. Technol. 6(2), 174-181 (2011)
[54]	Agarwal M., Sharma V.K.: Ant colony approach to constrained redundancy optimization in binary systems. Appl. Math. Model. 34(4), 992-1003 (2010) · Zbl 1185.90055
[55]	Garey M., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) · Zbl 0411.68039
[56]	Gaivoronski A.A., Lisser A., Lopez R., Hu X.: Knapsack problem with probability constraints. J. Glob. Optim. 49(3), 397-413 (2011) · Zbl 1213.90213
[57]	Argyris N., Figueira J.R., Morton A.: Identifying preferred solutions to multi-objective binary optimization problems, with an application to the multi-objective knapsack problem. J. Glob. Optim. 49(2), 213-235 (2011) · Zbl 1209.90309
[58]	Mavrotas G., Figueira J.R., Antoniadis A.: Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems. J. Glob. Optim. 49(4), 589-606 (2011) · Zbl 1225.90112
[59]	Visée M., Teghem J., Ulungu E.L.: Two-phase method and branch and bound procedures to solve the bi-objective knapsack problem. J. Glob. Optim. 12, 139-155 (1998) · Zbl 0908.90191
[60]	Crowder H., Johnson E.L., Padberg H.W.: Solving large scale zero-one linear programming problems. Oper. Res. Soc. 31, 803-834 (1983) · Zbl 0576.90065
[61]	Nemhauser G.L., Savelsbergh M.W.P, Sigismondi G.C.: MINTO, a mixed INTeger optimizer. Oper. Res. Lett. 15, 47-58 (1994) · Zbl 0806.90095
[62]	Senju S., Toyoda Y.: An approach to linear programming with 0-1 variables. Manage. Sci. 15, 196-207 (1968)
[63]	Balev S., Yanev N., Fréville A., Andonov R.: A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem. Eur. J. Oper. Res. 186(1), 63-76 (2008) · Zbl 1138.90015
[64]	Shih W.: A branch and bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. 30, 369-378 (1979) · Zbl 0411.90050
[65]	Mansini R., Speranza M.G.: A multidimensional knapsack model for the asset-backed securitization. J. Oper. Res. Soc. 53, 822-832 (2002) · Zbl 1130.90391
[66]	Gilmore P.C., Gomory R.E.: The theory and computation of knapsack functions. Oper. Res. 14, 1045-1075 (1966) · Zbl 0173.21502
[67]	Chor B., Rivest R.L.: A knapsack-type public key cryptosystem based on arithmetic infinite fields. IEEE Trans. Inf. Theory. 34, 1-22 (1988) · Zbl 0664.94011
[68]	Drexl A.: A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing 40, 1-8 (1988) · Zbl 0638.65053
[69]	Cotta C., Troya J.M.: A hybrid genetic algorithm for the 0-1 multiple knapsack problem. Artif. Neural Nets. Genet. Alg. 3, 250-254 (1998)
[70]	Li, H.; Jiao, Y. C.; Zhang, L.; Gu, Z.-W.; Jiao, L. (ed.); Wang, L. (ed.); Gao, X. B. (ed.); Liu, J. (ed.); Wu, F. (ed.), Genetic algorithm based on the orthogonal design for multidimensional knapsack problems, 696-705 (2006), Heidelberg
[71]	Fidanova, S.; Margenov, S. (ed.); Vulkov, L. G. (ed.); Wasniewski, J. (ed.), Ant colony optimization for multiple knapsack problem and model bias, 280-287 (2005), Heidelberg · Zbl 1118.65337
[72]	Kong, M.; Tian, P.; Rutkowski, L. (ed.); Tadeusiewicz, R. (ed.); Zadeh, L. A. (ed.); Zurada, J. M. (ed.), Apply the particle swarm optimization to the multidimensional knapsack problem, 1140-1149 (2006), Heidelberg
[73]	Angelelli E., Mansini R., Speranza M.G.: Kernel search: a general heuristic for the multi-dimensional knapsack problem. Comput. Oper. Res. 37(11), 2017-2026 (2010) · Zbl 1188.90207
[74]	Holliday D., Resnick R., Walker J.: Fundamentals of Physics. Wiley, New York (1993)
[75]	OR-Library, Beasley, J.E.: http://people.brunel.ac.uk/ mastjjb/jeb/orlib/mknapinfo.html