CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Adaptive Mutation Rate at Genetic Algorithms with Multi-Chromosome Representation in Multi-department Hospital Process Optimization

by Matthias Kühn, Thomas Severin, Joachim Lippold, Horst Salzwedel, Volker Nissen
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 182 - Number 21
Year of Publication: 2018
Authors: Matthias Kühn, Thomas Severin, Joachim Lippold, Horst Salzwedel, Volker Nissen
10.5120/ijca2018917980

Matthias Kühn, Thomas Severin, Joachim Lippold, Horst Salzwedel, Volker Nissen . Adaptive Mutation Rate at Genetic Algorithms with Multi-Chromosome Representation in Multi-department Hospital Process Optimization. International Journal of Computer Applications. 182, 21 ( Oct 2018), 41-52. DOI=10.5120/ijca2018917980

@article{ 10.5120/ijca2018917980,
author = { Matthias Kühn, Thomas Severin, Joachim Lippold, Horst Salzwedel, Volker Nissen },
title = { Adaptive Mutation Rate at Genetic Algorithms with Multi-Chromosome Representation in Multi-department Hospital Process Optimization },
journal = { International Journal of Computer Applications },
issue_date = { Oct 2018 },
volume = { 182 },
number = { 21 },
month = { Oct },
year = { 2018 },
issn = { 0975-8887 },
pages = { 41-52 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume182/number21/30060-2018917980/ },
doi = { 10.5120/ijca2018917980 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T01:12:04.346751+05:30
%A Matthias Kühn
%A Thomas Severin
%A Joachim Lippold
%A Horst Salzwedel
%A Volker Nissen
%T Adaptive Mutation Rate at Genetic Algorithms with Multi-Chromosome Representation in Multi-department Hospital Process Optimization
%J International Journal of Computer Applications
%@ 0975-8887
%V 182
%N 21
%P 41-52
%D 2018
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The performance of Metaheuristics in general and Evolutionary Algorithms (EA) in particular depends on good settings of algorithm parameter values, such as population size, mutation rate or crossover probability. To increase performance, researchers still try to find optimal settings. At present, researchers are adapting the parameter settings during an evolutionary run (parameter control). Thus, no hand tuning is needed upfront of an evolutionary run. In this paper we analyze algorithm performance when using adaptable algorithm parameters on Genetic Algorithms (GA) with multi-chromosome representation. Most of the research in the field of EA has been done on a theoretical basis. Often the proposed solutions do not deliver what they promise, when applying them to complex problems of real-world. Thus, experimental studies on complex problems of real-world are needed to ascertain performance improvement of adaptive parameter control. This paper is an experimental study on such a complex optimization problem of real-world (dynamically coupled System of Systems). In our approach of parameter control new individuals are generated by adapting the mutation rate. Therefore, we calculate a dedicated mutation rate for each chromosome of the individual. This happens in relation to the fitness of each chromosome. We analyzed and have statistically proven the outperformance of our approach upfront with the De Jong’s (Sphere) and the Schwefel’s test function. In this paper, we are now applying our approach to a real world based complex optimization problem (nonstationary, dynamic, noisy), to prove the outperformance of our approach. Therefore, we made a performance comparison with non-adaptive GA, which demonstrates the superiority of the adaptive approach. More specifically, we use a stochastic simulation model of university hospital processes. Inpatient admission, outpatient admission and op-theater planning of elective patients must be optimized simultaneously, while emergencies occur. Every hospital area has its own objectives and constraints (dedicated systems). The number of patients and utilization of resources must be maximized in every hospital area, while waiting times, lead times and schedule variances must be minimized. In that, a system of systems can be seen. It is shown how our approach can be used to optimize such dynamically coupled system of systems (SoS) in an efficient way.

References
  1. Holland, J. H. 1975. Adaption in natural and artificial systems, Ann Arbor, Michigan, USA: Univ. of Michigan Press.
  2. De Jong, K. A. “Parameter setting in EAs: a 30 year perspective”. In Lobo et al. , pp. 1–18.
  3. De Jong, K. A. 1975. An analysis of the behavior of a class of genetic adaptive, Ph.D. thesis, University of Michigan.
  4. Schaffer, J. D., Caruana, R. A., Eshelman, L. J. and Das, R. “A study of control parameters affecting online performance of genetic algorithms for function optimization”. In Proceedings of 3rd Int. Conf. Genetic Algorithms, 1989, pp. 51–60.
  5. Eiben, A. E. and Smith, J. E. (2015). Introduction to evolutionary computing. 2nd ed. (Natural Computing Series), Berlin, Heidelberg, Germany: Springer, doi: 10.1007/978-3-662-05094-1.
  6. Eiben, A. E., Hinterding, R. and. Michalewicz, Z. “Parameter control in evolutionary algorithms”. IEEE Trans. on Evolutionary Computation, 3(2), 1999, pp 124–141.
  7. Bäck, T. 1996. Evolutionary algorithms in theory and practice. Oxford. UK: Oxford University Press.
  8. Reeves, C. “Using Genetic Algorithms with small Populations”. In Procedings of 5th Int. Conf. Genetic Algorithms, 1993, pp. 92–99.
  9. Rechenberg, I. 1973. Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart. Germany: Frommann-Holzboog.
  10. Schwefel, H.-P. 1981. Numerical Optimization of Computer Models. New York. USA: Wiley.
  11. Beyer, H.-G. and Schwefel, H.-P. “Evolution strategies - A comprehensive introduction”. In Natural Comput, 2002, vol. 1. no.1, pp. 3-52.
  12. Eiben, A. E., Michalewicz, Z., Schoenauer, M. and Smith, J. E. “Parameter control in Evolutionary Algorithms”. In Lobo et al. , pp. 19-46.
  13. Fogarty, T. C., “Varying the probability of mutation in the genetic algorithm”. In Proceedings of 3rd Int. Conf. Genetic Algorithms. 1989, pp. 104–109.
  14. Hesser, J. and Männer, R. “Towards an Optimal Mutation Probability for Genetic Algorithms”, Parallel Problem Solving from Nature (Lecture Notes in Computer Science vol. 496). Berlin, Heidelberg. Germany: Springer. 2005, ch. 4, pp. 23–32, doi: 10.1007/Bfb0029727.
  15. Grefenstette, J. J. “Optimization of control parameters for genetic algorithms”. In IEEE Trans. Syst., Man, Cybern., vol. 16, no. 1, (Jan. 1986), pp. 122–128, doi: 10.1109/TSMC.1986.289288.
  16. Bäck, T. 1992. Self-Adaption in Genetic Algorithms. In Proceedings of 1st European Conf. Artificial Life, pp. 263–271.
  17. Bäck, T. “Optimal mutation rates in genetic search”. In Proceedings of 5th Int. Conf. Genetic Algorithms, 1993, pp. 2–8.
  18. Smith, J. “Parameter perturbation mechanism in binary coded gas with self-adaptive mutation”. 7th Int. Workshop FOGA, 2003, pp. 329-346.
  19. Hinterding, R. “Self-adaptation using multi-chromosomes”. In Proceedings of IEEE Int. Conf. Evol. Comput., 1997, pp. 87–91.
  20. Kühn, M., Severin, T. and Salzwedel, H. “Variable Mutation Rate at Genetic Algorithms: Introduction of Chromosome Fitness in Connection with Multi-Chromosome Representation”. Int. Journal Comput. Appl., vol. 72, no. 17, 2013, pp. 31–38.
  21. Lippold, J. 2014. Aufbau eines prozessorientierten Simulationsmodells für klinische Einrichtungen zur abteilungsübergreifenden Termin- und Reihenfolgeplanung. Dipl.-thesis, Tec. Univ. Ilmenau.
  22. Gonçalves, J. F., de Magalhães, M. J. J. and Resende, M. G. C. 2002. A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem. AT&T Labs Research. Technical Report TD-5EAL6J.
  23. Keedwell, E. and Khu, S.-T. “A hybrid genetic algorithm for the design of water distribution networks”. Engineer Appl. of Artificial Intell., vol. 18, no. 4, Jun. 2005, pp. 461–472, doi:10.1016/j.engappai.2004.10.001.
  24. Kühn, M., Baumann, T. and. Salzwedel, H. “Genetic Algorithm for process optimization in hospitals”. In Proceedings of 26th Eur. Conf. Modelling Simulation, 2012, pp. 103–107.
  25. Gao, W. “Study on New Improved Hybrid Genetic Algorithm”. Advances in Information Technology and Industry Applications (Lecture Notes in Electrical Engineering vol. 136), ch. 66, 2012, pp. 505–512 doi: 10.1007/978-3-642-26001-8_66.
  26. Davidor, Y. “Genetic Algorithms and Robotics - A Heuristic Strategy for Optimization” World Scientific Series in Robotics and Intelligent Systems vol.1, 1991. Singapore: World Scientific.
  27. Juliff, K. “A multi-chromosome genetic algorithm for pallet loading”. In Proceedings of 5th Int. Conf. Genetic Algorithms 1993, pp. 467–473.
  28. Pierrot, H. J. and Hinterding, R. “Using multi-chromosomes to solve a simple mixed integer problem”. Lecture Notes in Computer Science, vol. 1342, 1997, pp. 137–146.
  29. Ronald, S., Kirby, S. and Eklund, P. “Multi-Chromosome Mixed Encodings for Heterogenous Problems”. In Proceedings of 4th Int. Conf. Evol. Comput., 1997, pp. 37–42.
  30. Wight, J. and Zhang, Y. “An ‘Ageing’ Operator and Its Use in the Highly Constrained Topological Optimization of HVAC System Design”. In Proceedings of 2005 GECCO, pp. 2075–2082.
  31. Cavill, R., Smith, S. and Tyrrell, A. “Multi-Chromosomal Genetic Programming”. In Proceedings of 2005 GECCO, pp. 1753–1759.
  32. Kerati, S., Moudani, W. E. L., de Coligny, M. and Mora-Camino, F. “A Heuristic Genetic Algorithm Approach for the Airline Crew Scheduling Problem”. In IEEE Congr. Evol. Comput., 2009, pp. 1383–1390.
  33. Peng, J. and Chu, Z. S. “A Hybrid Multi-Chromosome Genetic Algorithm for the Cutting Stock Problem”. In ICIII, 2010, pp. 508–511.
  34. Lobo, F. G., Lima, C. F. and Michalewicz, Z. (Ed.) “Parameter Setting in Evolutionary Algorithms”. In Studies in Computational vol. 54, Berlin, Heidelberg, Germany: Springer, 2007.
  35. Meyer-Nieberg, S. and Beyer, H.-G. “Self-Adaptation in Evolutionary Algorithms”, in Lobo et al. , pp. 47–75.
  36. Eiben, A. E. and Smit, S. K. “Parameter tuning for configuring and analysing evolutionary algorithms”, Swarm, Evol. Comput., vol. 1, no. 1, pp. 19–31, Mar. 2011, doi: DOI: 10.1016/j.swevo.2011.02.001.
  37. Karafotias, G. H. M. and Eiben, A. E. “Parameter Control in Evolutionary Algorithms: Trends and Challenges”. IEEE Trans. Evol. Comput., vol. 19, no. 2, Apr. 2015, pp. 167-187, doi: 10.1109/TEVC.2014.2308294.
  38. Fernandes, C. M., Merelo, J. J., Ramos, V. and Rosa, A.C. “A Selforganized criticality mutation operator for dynamic optimization problems”. In Proc. 2008 GECOO, pp. 937–944
  39. Severin, T. 2014. Implementierung eines Genetischen Algorithmus mit Multichromosomenansatz zur abteilungsübergreifenden Termin- und Reihenfolge-planung in Kliniken“, Dipl.-thesis, Tec. Univ. Ilmenau.
  40. Aleti, A. and Moser, I. “A Systematic Literature Review of Adaptive Parameter Control Methods for Evolutionary Algorithms”. ACM Computing Survey CSUR, vol. 49, no. 3, Article 56, 2016.
  41. Eiben, A. E., Hinterding, R. and Michalewicz, Z. „Parameter Control in Evolutionary Algorithms”. IEEE Trans. Evol. Comput., vol. 3, no. 2, 1998, pp. 124–141.
  42. Serpell, M. and Smith, J. E. “Self-adaptation of mutation operator and probability for permutation representations in genetic algorithms. J. Evol. Comput., vol. 18, no. 3, Sep. 2010, pp. 491-514, doi: 10.1162/EVCO_a_00006.
  43. Yuan, B. and. Gallagher, M. “Combining Meta-EAs and Racing for Difficult EA Parameter Tuning Tasks”, in Lobo et al. , pp. 121-142.
  44. Kühn, M., Lippold, J. and Salzwedel, H. “Automatic transformation of hospital processes into executable model with EPML”. Int. J. Comput. Appl., vol. 80, no. 9, 2013, pp. 20–30.
  45. Page, B. 1991. Diskrete Simulation: Eine Einführung mit Modula-2 (Springer Lehrbuch). Berlin. Heidelberg. Germany: Springer.
  46. Cayirli, T., Veral, E. “Outpatient scheduling in health care: a review of literature”. Prod., Operations Manage., vol. 12, no. 4, pp. 519–549, doi: 10.1007/978-3-662-05094-1, Jan. 2009.
  47. Gupta, D., Wang, W.-Y. “Patient Appointments in ambulatory Care”. Handbook of Healthcare System Scheduling (Int. Series in Operations Research & Management vol. 168), R. Hall, Ed. Boston, MA, USA: Springer, ch. 4, pp. 65–104, doi: 10.1007/978-1-4614-173-7_4, Nov. 2011.
  48. Cardoen, B., Demeulemeester, E. and Beliën, J. “Operating room planning and scheduling: A literature review”, Eur. J. Oper. Res., vol. 201, no. 3, pp. 921–932, doi: 10.1016/j.ejor.2009.04.011, Mar. 2010.
  49. Helm, J. E., Lapp, M., See, B. D. “Characterizing an effective hospital admissions scheduling and control management system: A genetic algorithm approach”. In Proceedings of 2010 WSC, 2010, pp. 2387–2398.
  50. Gemmel, P., van Dierdonck, R. “Admission scheduling in acute care hospitals: does the practice fit with the theory?”. Int. J. Operations, Prod. Manage., vol. 19, no. 9, Sep. 1999, pp. 863–871, doi: 10.1108/01443579910280188.
  51. Nissen, V. and. Biethahn, J. „Ein Beispiel zur stochastischen Optimierung mittels Simulation und einem Genetischen Algorithmus“. In Simulation als betriebliche Entscheidungshilfe. State of the Art und neuere Entwicklungen, Biethahn, J., Hummeltenberg, W., Schmidt, B., Stähly P., and Witte, TH. (Ed.) Heidelberg, Germany: Physica, 1999, ch. 6, pp. 108–125, doi: 10.1007/978-3-642-58671-2_6.
  52. Pohlheim, H. 2000. Evolutionäre Algorithmen. Verfahren, Operatoren und Hinweise für die Praxis, Berlin, Germany: Springer.
  53. Kühn, M., Baumann, T., Salzwedel, H. “Genetic algorithm for process optimization in hospitals”. In Proceedings of 26th European Conference on Modeling and Simulation, 2012, pp. 103–107.
Index Terms

Computer Science
Information Sciences

Keywords

Genetic algorithms hospital inpatient admission multi-chromosome mutation rate op-theater planning. optimization outpatient admission parameter control self-adapting computer simulation real world problem system of systems optimization.

Powered by PhDFocusTM