GPS: a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems

Abstract

The multiple knapsack problem (MKP) forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms (GAs) for proving its efficiency. GAs use selfadaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression (GPS) has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to improve the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by replacing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vector and to retain the best genes of the individuals. Each gene’s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene’s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment. The MKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome portrays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.

Keywords

combinatorial problems / evolutionary algorithm / multiobjective problems / multiple knapsack problem / gene position effect / gene suppression

References

[1] Azad M A K, Rocha A M A C, Fernandes E M G P. Improved binary artificial fish swarm algorithm for the 0–1 multidimensional knapsack problems. Swarm and Evolutionary Computation, 2014, 14: 66–75

[2] Petersen C C. Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Science, 1967, 13(9): 736–750

[3] Weingartner H M. Mathematical programming and the analysis of capital budgeting problems. Englewoods Cliffs, NJ: Prentice-Hall, 1963.

[4] Gavish B, Pirkul H. Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Mathematical Programming, 1985, 31(1): 78–105

[5] Shih W. A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society, 1979: 369–378

[6] Pisinger D. Algorithms for knapsack problems. Dissertation for the Doctoral Degree. Copenhagen: University of Copenhagen, 2000

[7] Coello C A C, Lamont G B, Van Veldhuizen D A. Evolutionary Algorithms for Solving Multi-objective Problems. New York: Springer, 2007

[8] He J, Mitavskiy B, Zhou Y. A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem. In: Proceedings of IEEE Congress on Evolutionary Computation. 2014: 141–148

[9] Ibarra O H, Kim C E. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM(JACM), 1975, 22(4): 463–468

[10] Bansal J C, Deep K. A modified binary particle swarm optimization for knapsack problems. Applied Mathematics and Computation, 2012, 218(22): 11042–11061

[11] Deb K, Pratap A, Agarwal S, Meyarivan T A M T. A fast and elitist multiobjective genetic algorithm: NSGA–II. IEEE Transaction on Evolutionary Computation, 2002, 6(2): 182–197

[12] Li Z Y, Rudolph G, Li K L. Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms. Computers and Mathematics with Applications, 2014, 57: 1843–1854

[13] Kumar R, Rockett P. Multiobjective genetic algorithm partitioning for hierarchical learning of high-dimensional pattern spaces: a learning follows-decomposition strategy. IEEE Transactions on Neural Networks, 1998, 9(5): 822–830

[14] Bosman P A N, Thierens D. The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Transaction on Evolutionary Computation, 2003, 7(2): 174–188

[15] T Erlebach T, Kellerer H, Pferschy U. Approximating multiobjective knapsack problems. In: Proceedings of Workshop on Algorithms and Data Structures. 2001, 210–221

[16] Kumar R, Banerjee N. Analysis of a multiobjective evolutionary algorithm on the 0–1 knapsack problem. Theoretical Computer Science, 2006, 358(1): 104–120

[17] Paul P V, Ramalingam A, Baskaran R, Dhavachelvan P, Vivekanandan K, Subramanian R. A new population seeding technique for permutation-coded genetic algorithm: service transfer approach. Journal of Computational Science, 2014, 5(2): 277–297

[18] van Kampen A H C, Strom C S, Buydens L M C. Lethalization, penalty and repair functions for constraint handling in the genetic algorithm methodology. Chemometrics and Intelligent Laboratory Systems, 1996, 34(1): 55–68

[19] Uyar S, Eryiˇgit G. Improvements to penalty-based evolutionary algorithms for the multi-dimensional knapsack problem using a gene-based adaptive mutation approach. In: Proceedings of the 7th ACM Annual Conference on Genetic and Evolutionary Computation. 2005, 1257–1264

[20] Glover F. Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems. European Journal of Operational Research, 2013, 230(2): 212–225

[21] Gorski J, Paquete L, Pedrosa F. Greedy algorithms for a class of knapsack problems with binary weights. Computers & Operations Research, 2012, 39(3): 498–511

[22] Wang L, Wang S Y, Xu Y. An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem. Expert Systems with Applications, 2012, 39(5): 5593–5599

[23] Martins J P, Fonseca C M, Delbem A C B. On the performance of linkage-tree genetic algorithms for the multidimensional knapsack problem. Neurocomputing, 2014, 146: 17–29

[24] Chih M. Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem. Applied Soft Computing, 2015, 26: 378–389

[25] Kumar R, Rockett P. Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm. Evolutionary computation, 2002, 10(3): 283–314

[26] Chih M, Lin C J, Chern M S, Ou T Y. Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Applied Mathematical Modelling, 2014, 38(4): 1338–1350

[27] Michailidis J, Graves J A M, Murray N D. Suppression of positioneffect variegation in Drosophila melanogaster, by fatty acids and dimethylsulphoxide: implications for the mechanism of position-effect variegation. Journal of Genetics, 1989, 68(1): 1–8

[28] Mount S M, Anderson P. Expanding the definition of informational suppression. Trends in Genetics, 2000, 16(4): 157

[29] Manicassamy J, Dhavachelvan P. Gene transinfection directs towards gene functional enhancement using genetic algorithm. IERI Procedia, 2013, 4: 268–274

[30] Costantini F D, Roberts S, Evans E P, Burtenshaw M D, Lacy E. Position Effects and Gene Expression in the Transgenic Mouse, Transfer and Expression of Eukraryotic Genes. New York: Academic Press, 1984

[31] Magtanong L, Ho C H, Barker S L, Jiao W, Baryshnikova A, Bahr S, Smith A M, Heisler L E, Choy J S, Kuzmin E, Andrusiak K, Kobylianski A, Li Z J, Costanzo M, Basrai M A, Giaever G, Nislow C, Andrews B, Boone C. Dosage suppression genetic interaction networks enhance functional wiring diagrams of the cell. Natures Biotechnology, 2011, 29: 505–511

[32] Barabasi A L, Oltvai Z N. Network biology: understanding the cell’s functional organization. Nature Reviews Genetics, 2004, 5(2): 101–113

[33] Hartman P E, Roth J R. Mechanisms of suppression. Advances in Genetics, 1973, 17: 1–105

[34] Prelich G. Mechanisms of suppression: themes from variations. Trends Genetics, 1999, 15(7): 261–266

[35] Ma A N, Wang H, Guo R, Wang Y X, Li W, Cui J W, Wang G J, Hoffman A R, Hu J F. Targeted gene suppression by inducing de novo DNA methylation in the gene promoter. Journal of Epigenetics and Chromatin, 2014, 7(1): 20

[36] Lissemore J L, Currie P D, Turk C M, Maine E M. Intragenic dominant suppressors of GLP-1, a gene essential for cell-signaling in Caenorhabditis elegans, support a role for cdc10/SWI6/Ankyrin motifs in GLP-1 function. Genetics, 1993, 135(4): 1023–1034

[37] Wu Y, Han M. Suppression of activated Let-60 ras protein defines a role of Caenorhabditis elegans Sur-1 MAP kinase in vulval differentiation. Genes & Development, 1994, 8(2): 147–159

[38] Sturtevant A H. The vermillion gene and gynandromorphism. Experimental Biology and Medicine, 1920, 17(4): 70–71.

[39] Lai X, Schmitz U, Gupta S K, Bhattacharya A, Kunz M, Wolkenhauer O, Vera J. Computational analysis of target hub gene repression regulated by multiple and cooperative miRNAs. Nucleic Acid Research, 2012, 40(18): 8818–8834

[40] Guo S W. Proportion of genes survived in offspring conditional on inheritance of flanking markers. Genetics, 1994, 138(3): 953–962

[41] Yang N, Hu F, Zhou L X, Tang J J. Reconstruction of ancestral gene orders using probabilistic and gene encoding approaches. PloS One, 2014, 9(10): e108796

[42] Seo M, Oh S. Derivation of an artificial gene to improve classification accuracy upon gene selection. Computational Biology and Chemistry, 2012, 36: 1–12

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature