Research article Special Issues

A self-adaptive mechanism using weibull probability distribution to improve metaheuristic algorithms to solve combinatorial optimization problems in dynamic environments

  • Received: 24 July 2019 Accepted: 09 October 2019 Published: 11 November 2019
  • In last decades, the interest to solve dynamic combinatorial optimization problems has increased. Metaheuristics have been used to find good solutions in a reasonably low time, and the use of self-adaptive strategies has increased considerably due to these kind of mechanism proved to be a good alternative to improve performance in these algorithms. On this research, the performance of a genetic algorithm is improved through a self-adaptive mechanism to solve dynamic combinatorial problems: 3-SAT, One-Max and TSP, using the genotype-phenotype mapping strategy and probabilistic distributions to define parameters in the algorithm. The mechanism demonstrates the capability to adapt algorithms in dynamic environments.

    Citation: Cesar J. Montiel Moctezuma, Jaime Mora, Miguel González Mendoza. A self-adaptive mechanism using weibull probability distribution to improve metaheuristic algorithms to solve combinatorial optimization problems in dynamic environments[J]. Mathematical Biosciences and Engineering, 2020, 17(2): 975-997. doi: 10.3934/mbe.2020052

    Related Papers:

  • In last decades, the interest to solve dynamic combinatorial optimization problems has increased. Metaheuristics have been used to find good solutions in a reasonably low time, and the use of self-adaptive strategies has increased considerably due to these kind of mechanism proved to be a good alternative to improve performance in these algorithms. On this research, the performance of a genetic algorithm is improved through a self-adaptive mechanism to solve dynamic combinatorial problems: 3-SAT, One-Max and TSP, using the genotype-phenotype mapping strategy and probabilistic distributions to define parameters in the algorithm. The mechanism demonstrates the capability to adapt algorithms in dynamic environments.


    加载中


    [1] Y. Majid and K. Esmaile, Solving the vehicle routing problem by a hybrid metaheuristic algorithm, J. Industr. Eng. Int., 8 (2012), 11.
    [2] S. X. Yang, T. T. Nguyen, C. H. Li, Evolutionary dynamic optimization test and evaluation environments, Evolut. Comput. Dyn. Opt. Probl., 490 (2013), 3.
    [3] S. X. Yang and X. Yao, Evolutionary computation for dynamic optimization problems, Springer-Verlag Berlin Heidelberg, 2013. Available from: https://doi.org/10.1007/978-3-642-38416-5
    [4] H. Q. Liu, L. Pretorius and D. D. Jiang, Optimization of cold chain logistics distribution network terminal, EURASOP J. Wireless Commun. Network., 2018, 158.
    [5] E. M. Cepolina and A. Farina, A new urban freight distribution scheme and an optimization methodology for reducing its overall cost, Europ. Transp. Res. Rev., 7 (2014), 1.
    [6] F. F. Razi, A hybrid DEA-based K-means and invasive weed optimization for facility location problem, J. Ind. Eng. Int., 2018. Available from: https://doi.org/10.1007/s40092-018-0283-5.
    [7] V. M. Kumar, A. Murthy and K. Chandrashekara, A hybrid algorithm optimization approach for machine loading problem in flexible manufacturing system, J. Ind. Eng. Int., 8 (2012), 3. Available from: https://doi.org/10.1186/2251-712X-8-3.
    [8] M. Tayyab, B. Sarkar and B. N. Yahya, Imperfect multi-stage lean manufacturing system with rework under fuzzy demand, Mathematics, 7 (2019), 13.
    [9] S. Khorasgani, S. Mahdi and M. Ghaffari, Developing a cellular manufacturing model considering the alternative routes, tool assignment, and machine reliability, J. Ind. Eng. Int., 14 (2018): 627.
    [10] S. X. Yanga, J. G. Yong and T. T. Nguyenc, Metaheuristics for Dynamic combinatorial optimization problems, IMA J. Manage. Math., 24 (2012). Available from: https://doi.org/10.1093/imaman/dps021.
    [11] R. M. Karp, Reducibility among combinatorial problems, Compl. Comput. Computat., 1972. Available from: https://doi.org/10.1007/978-1-4684-2001-2_9.
    [12] C. H. Li, M. Yang and L. S. Kang, A new approach to solving dynamic traveling salesman problems, SEAL, 2006, 4247. Available from: https://doi.org/10.1007/11903697_31.
    [13] T. Volling, M. Grunewald and T. S. Spengler, An integrated inventory—transportation system with periodic pick-ups and leveled replenishment, Business Res., 6 (2013), 173. Available from: https://doi.org/10.1007/BF03342748.
    [14] G. P. Lechuga, Optimal logistics strategy to distribute medicines in clinics and hospitals, J. Math. Industry, 8 (2018), 2. Available from: https://doi.org/10.1186/s13362-018-0044-5.
    [15] S. Henn, S. Koch, K. F. Doerner, et al., Metaheuristics for the order batching problem in manual order picking systems, Business Res., 3(2018), 82. Available from: https://doi.org/10.1007/BF03342717
    [16] R. Srikakulapu and U. Vinatha, Optimized design of collector topology for offshore wind farm based on ant colony optimization with multiple travelling salesman problem, J. Modern Power Syst. Clean Energy, 6 (2018), 1181. Available from: https://doi.org/10.1007/s40565-018-0386-4.
    [17] G. Moslemipour, A hybrid CS-SA intelligent approach to solve uncertain dynamic facility layout problems considering dependency of demands, J. Ind. Eng. Int., 14(2018), 429. Available from: https://doi.org/10.1007/s40092-017-0222-x.
    [18] J. H. Holland, Adaptation in natural and artificial systems [Master's thesis], University of Michigan Press, Ann Arbor, MI, 1975.
    [19] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning, 1st rev. Addison-Wesley Longman Publishing Co, 1989. ISBN: 0201157675.
    [20] K. A. De Jong, Genetic algorithms a 10 year perspective, International Conference Genetic Algorithms, 1985, 169-177. ISBN: 0-8058-0426-9.
    [21] Y. H. Liao and C. T. Sun, An educational genetic algorithms learning tool, IEEE Transact. Educ., 2001. Available from: http://www.ewh.ieee.org/soc/es/May2001/14/Begin.htm.
    [22] J. A. B. Vera, J. Mora-Vargas, M. González-Mendoza, et al., Brief review of techniques used to develop adaptive evolutionary algorithms, Open Cybern. Syst. J., 11(2017), 1-12.
    [23] J. A. B. Vera, Investigación del rol del mapeo genotipo-fenotipo y del operador de mutación en algoritmos genéticos aplicados a problemas dinámicos [Master's thesis], Mexico, Tecnologico de Monterrey, 2011, Spanish.
    [24] R. E. Keller and W. Banzhaf, Genetic programming using genotype-phenotype mapping from linear genomes into linear phenotypes, Proceedings of the First Annual Conference on Genetic Programming, 1996, 116-122. ISBN: 0-262-61127-9.
    [25] J. Mora, C. Stephens and H. Waelbroeck, Symmetry breaking and adaptation: Evidence from a toy model of a virus, Biosystems, 51 (1997), 1-14.
    [26] F. Rothlauf and D. E. Goldberg, Redundant representations in evolutionary computation, Evol. Comput., 11 (2003), 381-415.
    [27] K. Ohnishi and K. Yoshida, Evolutionary change in developmental timing, GECCO 2005, 2005, 1561-1562. Available from: https://doi.org/10.1145/1068009.1068259.
    [28] D. Fagan, Genotype-phenotype mapping in dynamic environments with grammatical evolution, GECCO 2011, 2011. Available from: https://doi.org/10.1145/2001858.2002091.
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2870) PDF downloads(407) Cited by(0)

Article outline

Figures and Tables

Figures(15)  /  Tables(11)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog