Optimising cancer chemotherapy using an estimation of distribution algorithm and genetic algorithms

ABSTRACT

This paper presents a methodology for using heuristic search methods to optimise cancer chemotherapy. Specifically, two evolutionary algorithms - Population Based Incremental Learning (PBIL), which is an Estimation of Distribution Algorithm (EDA), and Genetic Algorithms (GAs) have been applied to the problem of finding effective chemotherapeutic treatments. To our knowledge, EDAs have been applied to fewer real world problems compared to GAs, and the aim of the present paper is to expand the application domain of this technique.We compare and analyse the performance of both algorithms and draw a conclusion as to which approach to cancer chemotherapy optimisation is more efficient and helpful in the decision-making activity led by the oncologists.

REFERENCES

• 1: J. Aickelin and J. Li. An Estimation of Distribution Algorithm for Nurse Scheduling. Annals of Operational Research, in print, 2006.
• 2: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 3: Shumeet Baluja , Scott Davies, Using Optimal Dependency-Trees for Combinational Optimization, Proceedings of the Fourteenth International Conference on Machine Learning, p.30-38, July 08-12, 1997
• 4: J. Cassidy and H. McLeod. Is it possible to design a logical development plan for an anti-cancer drug? Pharmaceutical Medicine, 9:95--103, 1995.
• 5: D. Dearnaly, I. Judson, and T. Root, editors. Handbook of adult cancer chemotherapy schedules. The Medicine Group (Education) Ltd., Oxfordshire, 1995.
• 6: R. Fletcher and S. Leyffer. Numerical experience with solving mpecs as nlps. Technical Report NA/210, Department of Mathematics, University of Dundee, UK, 2002.
• 7: Elvis Galic , Markus Höhfeld, Improving the Generalization Performance of Multi-Layer-Perceptrons with Population-Based Incremental Learning, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.740-750, September 22-26, 1996
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. IEEE-EC, 3(4):287, November 1999.
• 10: Holger H. Hoos , Thomas Stützle, Towards a characterisation of the behaviour of stochastic local search algorithms for SAT, Artificial Intelligence, v.112 n.1-2, p.213-232, Aug. 1999 [doi>10.1016/S0004-3702(99)00048-X]
• 11: I. Inza, M. Merino, P. Larrañaga, J. Quiroga, B. Sierra, and M. Girala. Feature subset selection by population-based incremental learning. A case study in the survival of cirrhotic patients with TIPS. Artificial Intelligence in Medicine, In press, 2001.
• 12: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 13: R. Martin and K. Teo. Optimal control of drug administration in cancer chemotherapy. World Scientific, 1994.
• 14: J. McCall and A. Petrovski. A decision support system for cancer chemotherapy using genetic algorithms. In Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation, pages 65--70. IOS Press, 1999.
• 15: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 16: Martin Pelikan , Kumara Sastry , Martin V. Butz , David E. Goldberg, Hierarchical BOA on random decomposable problems, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144077]
• 17: A. Petrovski. An Application of Genetic Algorithms to Chemotherapy Treatment. PhD thesis, The Robert Gordon University, Aberdeen, UK, 1999.
• 18: A. Petrovski, A. Brownlee, and J. McCall. Statistical optimisation and tuning of GA factors. In Proceedings of the IEEE Congress on Evolutionary Computation, pages Vol. 1, 758--764, Edinburgh, Scotland, 2005. IEEE Press.
• 19: Andrei Petrovski , John McCall, Multi-objective Optimisation of Cancer Chemotherapy Using Evolutionary Algorithms, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.531-545, March 07-09, 2001
• 20: A. Petrovski, B. Sudha, and J. McCall. Optimising cancer chemotherapy using particle swarm optimisation and genetic algorithms. In Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, pages 633--641, Birmingham, UK, 2004. Springer: Lecture Notes in Computer Science 3224.
• 21: R. Sanatana, P. Larrañaga, and J. Lozano. Interactions and dependencies in estimation of distribution algorithms. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation, volume 2, pages 1418--1425, Edinburgh, UK, 2005. IEEE press.
• 22: R. Sanatana, P. Larrañaga, and J. Lozano. Protein structure prediction in simplified models with estimation of distribution algorithms. In Proceedings of the IV Congreso Espanol sobre Metaheuristicas, Algoritmos Evolutivos y Bioinspirados (MAEB-2005), pages 245--252, Granada, Spain, 2005.
• 23: Siddhartha Shakya , John McCall , Deryck Brown, Using a Markov network model in a univariate EDA: an empirical cost-benefit analysis, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068130]
• 24: S. K. Shakya, J. A. W. McCall, and D. F. Brown. Updating the probability vector using MRF technique for a Univariate EDA. In E. Onaindia and S. Staab, editors, Proceedings of the Second Starting AI Researchers' Symposium, pages 15--25, Valencia, Spain, 2004. IOS press.
• 25: K. C. Tan, E. F. Khor, J. Cai, C. M. Heng, and T. H. Lee. Automating the drug scheduling of cancer chemotherapy via evolutionary computation. Artificial Intelligence in Medicine, pages 169--185, 2002.
• 26: M. Villasana and G. Ochoa. Heuristic design of cancer chemotherapies. IEEE Transactions on Evolutonary Computation, 8(6):513--521, December 2004.
• 27: T. Wheldon. Mathematical models in cancer research. Adam Hilger, Bristol, Philadelphia, 1988.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes; Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Health

General Terms:
Algorithms, Performance, Theory

Keywords:
estimation of distribution algorithms, evolutionary computation, probabilistic modelling