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

Cesar J. Montiel Moctezuma; Jaime Mora; Miguel González Mendoza; Cesar J. Montiel Moctezuma; Jaime Mora; Miguel González Mendoza

doi:10.3934/mbe.2020052

Mathematical Biosciences and Engineering

2020, Volume 17, Issue 2: 975-997. doi: 10.3934/mbe.2020052

Previous Article Next Article

Research article Special Issues

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

1.
Instituto Mexicano del Transporte, Querétaro
2.
Tecnologico de Monterrey

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.
- genetic algorithm,
- self-adaptive mechanism,
- dynamic combinatorial optimization problems
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:

Abstract

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.

References

[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

Your name:*

Email:*
© 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)