Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2018, Vol. 12 Issue (1) : 101-121    https://doi.org/10.1007/s11704-016-5195-1
RESEARCH ARTICLE
GPS: a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems
Jayanthi MANICASSAMY(), Dinesh KARUNANIDHI, Sujatha POTHULA, Vengattaraman THIRUMAL, Dhavachelvan PONNURANGAM, Subramanian RAMALINGAM
Department of Computer Science, Pondicherry University, Pondicherry 605 014, India
 Download: PDF(839 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Jayanthi MANICASSAMY   
Just Accepted Date: 14 July 2016   Online First Date: 27 November 2017    Issue Date: 12 January 2018
 Cite this article:   
Jayanthi MANICASSAMY,Dinesh KARUNANIDHI,Sujatha POTHULA, et al. GPS: a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems[J]. Front. Comput. Sci., 2018, 12(1): 101-121.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5195-1
https://academic.hep.com.cn/fcs/EN/Y2018/V12/I1/101
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
https://doi.org/10.1016/j.swevo.2013.09.002
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
https://doi.org/10.1287/mnsc.13.9.736
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
https://doi.org/10.1007/BF02591863
5 Shih W. A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society, 1979: 369–378
https://doi.org/10.1057/jors.1979.78
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
https://doi.org/10.1109/CEC.2014.6900442
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
https://doi.org/10.1145/321906.321909
10 Bansal J C, Deep K. A modified binary particle swarm optimization for knapsack problems. Applied Mathematics and Computation, 2012, 218(22): 11042–11061
https://doi.org/10.1016/j.amc.2012.05.001
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
https://doi.org/10.1109/4235.996017
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
https://doi.org/10.1016/j.camwa.2008.10.046
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
https://doi.org/10.1109/72.712155
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
https://doi.org/10.1109/TEVC.2003.810761
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
https://doi.org/10.1016/j.tcs.2006.03.007
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
https://doi.org/10.1016/j.jocs.2013.05.009
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
https://doi.org/10.1016/0169-7439(96)00010-X
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
https://doi.org/10.1016/j.ejor.2013.04.010
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
https://doi.org/10.1016/j.cor.2011.02.010
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
https://doi.org/10.1016/j.eswa.2011.11.058
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
https://doi.org/10.1016/j.neucom.2014.04.069
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
https://doi.org/10.1016/j.asoc.2014.10.030
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
https://doi.org/10.1162/106365602760234117
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
https://doi.org/10.1016/j.apm.2013.08.009
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
https://doi.org/10.1007/BF02927830
28 Mount S M, Anderson P. Expanding the definition of informational suppression. Trends in Genetics, 2000, 16(4): 157
https://doi.org/10.1016/S0168-9525(99)01964-2
29 Manicassamy J, Dhavachelvan P. Gene transinfection directs towards gene functional enhancement using genetic algorithm. IERI Procedia, 2013, 4: 268–274
https://doi.org/10.1016/j.ieri.2013.11.038
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
https://doi.org/10.1038/nbt.1855
32 Barabasi A L, Oltvai Z N. Network biology: understanding the cell’s functional organization. Nature Reviews Genetics, 2004, 5(2): 101–113
https://doi.org/10.1038/nrg1272
33 Hartman P E, Roth J R. Mechanisms of suppression. Advances in Genetics, 1973, 17: 1–105
https://doi.org/10.1016/S0065-2660(08)60170-4
34 Prelich G. Mechanisms of suppression: themes from variations. Trends Genetics, 1999, 15(7): 261–266
https://doi.org/10.1016/S0168-9525(99)01749-7
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
https://doi.org/10.1186/1756-8935-7-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
https://doi.org/10.1101/gad.8.2.147
38 Sturtevant A H. The vermillion gene and gynandromorphism. Experimental Biology and Medicine, 1920, 17(4): 70–71.
https://doi.org/10.3181/00379727-17-42
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
https://doi.org/10.1093/nar/gks657
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
https://doi.org/10.1371/journal.pone.0108796
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
https://doi.org/10.1016/j.compbiolchem.2011.11.002
[1] Shuaiqiang WANG, Yilong YIN. Polygene-based evolutionary algorithms with frequent pattern mining[J]. Front. Comput. Sci., 2018, 12(5): 950-965.
[2] Yong WANG, Zhi-Zhong LIU, Jianbin LI, Han-Xiong LI, Jiahai WANG. On the selection of solutions for mutation in differential evolution[J]. Front. Comput. Sci., 2018, 12(2): 297-315.
[3] Maoguo GONG, Xiangming JIANG, Hao LI. Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework[J]. Front. Comput. Sci., 2017, 11(3): 362-391.
[4] Hanyang QUEK, Chunghoong WOO, Kaychen TAN, Arthur TAY. Evolving Nash-optimal poker strategies using evolutionary computation[J]. Front Comput Sci Chin, 2009, 3(1): 73-91.
[5] Maryjane TREMAYNE, Samantha Y. CHONG, Duncan BELL. Optimisation of algorithm control parameters in cultural differential evolution applied to molecular crystallography[J]. Front Comput Sci Chin, 2009, 3(1): 101-108.
[6] Carlos A. COELLO COELLO. Evolutionary multi-objective optimization:some current research trends and topics that remain to be explored[J]. Front Comput Sci Chin, 2009, 3(1): 18-30.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed