|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|