Tag: Genetic Programming and Evolvable Machines

Environmental effects on the coevolution of pursuit and evasion strategies

Abstract  The game of tag is frequently used in the study of pursuit and evasion strategies that are discovered through competitive
coevolution. The aim of coevolution is to create an arms race where opposing populations cyclically evolve in incremental
improvements, driving the system towards better strategies. A coevolutionary simulation of the game of tag involving two populations
of agents; pursuers and evaders, is developed to investigate the effects of a boundary and two obstacles. The evolution of
strategies through Chemical Genetic Programming optimizes the mapping of genotypic strings to phenotypic trees. Four experiments
were conducted, distinguished by speed differentials and environmental conditions. Designing experiments to evaluate the efficacy
of emergent strategies often reveal necessary steps needed for coevolutionary progress. The experiments that excluded obstacles
and boundaries provided design pointers to ensure coevolutionary progress as well as a deeper understanding of strategies
that emerged when obstacles and boundaries were added. In the latter, we found that an awareness of the environment and the
pursuer was not critical in an evader’s strategy to survive, instead heading to the edge of the boundary or behind an obstacle
in a bid to ‘throw-off or hide from the pursuer’ or simply turn in circles was often sufficient, thereby revealing possible
suboptimal strategies that were environment specific. We also observed that a condition for coevolutionary progress was that
the problem complexity must be surmountable by at least one population; that is, some pursuer must be able to tag an opponent.
Due to the use of amino-acid building blocks in our Chemical Genetic Program, our simulations were able to achieve significant
complexity in a short period of time.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9049-3
  • Authors
    • Joc Cing Tay, Nanyang Technological University Evolutionary and Complex Systems Program, School of Computer Engineering Singapore 639798 Singapore
    • Cheun Hou Tng, Nanyang Technological University Evolutionary and Complex Systems Program, School of Computer Engineering Singapore 639798 Singapore
    • Chee Siong Chan, Nanyang Technological University Evolutionary and Complex Systems Program, School of Computer Engineering Singapore 639798 Singapore

Abstract  The game of tag is frequently used in the study of pursuit and evasion strategies that are discovered through competitive
coevolution. The aim of coevolution is to create an arms race where opposing populations cyclically evolve in incremental
improvements, driving the system towards better strategies. A coevolutionary simulation of the game of tag involving two populations
of agents; pursuers and evaders, is developed to investigate the effects of a boundary and two obstacles. The evolution of
strategies through Chemical Genetic Programming optimizes the mapping of genotypic strings to phenotypic trees. Four experiments
were conducted, distinguished by speed differentials and environmental conditions. Designing experiments to evaluate the efficacy
of emergent strategies often reveal necessary steps needed for coevolutionary progress. The experiments that excluded obstacles
and boundaries provided design pointers to ensure coevolutionary progress as well as a deeper understanding of strategies
that emerged when obstacles and boundaries were added. In the latter, we found that an awareness of the environment and the
pursuer was not critical in an evader’s strategy to survive, instead heading to the edge of the boundary or behind an obstacle
in a bid to ‘throw-off or hide from the pursuer’ or simply turn in circles was often sufficient, thereby revealing possible
suboptimal strategies that were environment specific. We also observed that a condition for coevolutionary progress was that
the problem complexity must be surmountable by at least one population; that is, some pursuer must be able to tag an opponent.
Due to the use of amino-acid building blocks in our Chemical Genetic Program, our simulations were able to achieve significant
complexity in a short period of time.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9049-3
  • Authors
    • Joc Cing Tay, Nanyang Technological University Evolutionary and Complex Systems Program, School of Computer Engineering Singapore 639798 Singapore
    • Cheun Hou Tng, Nanyang Technological University Evolutionary and Complex Systems Program, School of Computer Engineering Singapore 639798 Singapore
    • Chee Siong Chan, Nanyang Technological University Evolutionary and Complex Systems Program, School of Computer Engineering Singapore 639798 Singapore

Theoretical foundations of evolutionary computation

Theoretical foundations of evolutionary computation

  • Content Type Journal Article
  • Category Editorial
  • DOI 10.1007/s10710-007-9047-5
  • Authors
    • Xiaodong Li, RMIT University School of Computer Science and IT 376-392 Swanston Street Melbourne VIC 3001 Australia
    • Wenjian Luo, RMIT University School of Computer Science and IT 376-392 Swanston Street Melbourne VIC 3001 Australia
    • Xin Yao, RMIT University School of Computer Science and IT 376-392 Swanston Street Melbourne VIC 3001 Australia

Theoretical foundations of evolutionary computation

  • Content Type Journal Article
  • Category Editorial
  • DOI 10.1007/s10710-007-9047-5
  • Authors
    • Xiaodong Li, RMIT University School of Computer Science and IT 376-392 Swanston Street Melbourne VIC 3001 Australia
    • Wenjian Luo, RMIT University School of Computer Science and IT 376-392 Swanston Street Melbourne VIC 3001 Australia
    • Xin Yao, RMIT University School of Computer Science and IT 376-392 Swanston Street Melbourne VIC 3001 Australia

Use of genetic programming to diagnose venous thromboembolism in the emergency department

Abstract  Pulmonary thromboembolism as a cause of respiratory complaints is frequently undiagnosed and requires expensive imaging modalities
to diagnose. The objective of this study was to determine if genetic programming could be used to classify patients as having
or not having pulmonary thromboembolism using exhaled ventilatory and gas indices as genetic material. Using a custom-built
exhaled oxygen and carbon dioxide analyzer; exhaled flows, volumes, and gas partial pressures were recorded from patients
for a series of deep exhalation and 30 s tidal volume breathing. A diagnosis of pulmonary embolism was made by contrast-enhanced
computerized tomography angiography of the chest and indirect venography supplemented by 90-day follow-up. Genetic programming
developed a series of genomes comprising genes of exhaled CO2, O2, flow, volume, vital signs, and patient demographics from these data and their predictions were compared to the radiological
results. We found that 24 of 178 patients had pulmonary embolism. The best genome consisted of four genes: the minimum flow
rate during the third 30 s period of tidal breathing, the average peak exhaled CO2 during the first 30 s period of tidal breathing, the average peak of the exhaled O2 during the first 30 s period of tidal breathing, and the average peak exhaled CO2 during the fourth period of tidal breathing, which immediately followed a deep exhalation. This had 100% sensitivity and
91% specificity on the construction population and 100% and 82%, respectively when tested on the separate validation population.
Genetic programming using only data obtained from exhaled breaths was very accurate in classifying patients with suspected
pulmonary thromboembolism.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9050-x
  • Authors
    • Milo Engoren, University of Toledo, Medical University of Ohio, St. Vincent Mercy Medical Center Department of Anesthesiology 2213 Cherry Street Toledo OH 43608 USA
    • Jeffrey A. Kline, Carolinas Medical Center Department of Emergency Medicine Charlotte NC USA

Abstract  Pulmonary thromboembolism as a cause of respiratory complaints is frequently undiagnosed and requires expensive imaging modalities
to diagnose. The objective of this study was to determine if genetic programming could be used to classify patients as having
or not having pulmonary thromboembolism using exhaled ventilatory and gas indices as genetic material. Using a custom-built
exhaled oxygen and carbon dioxide analyzer; exhaled flows, volumes, and gas partial pressures were recorded from patients
for a series of deep exhalation and 30 s tidal volume breathing. A diagnosis of pulmonary embolism was made by contrast-enhanced
computerized tomography angiography of the chest and indirect venography supplemented by 90-day follow-up. Genetic programming
developed a series of genomes comprising genes of exhaled CO2, O2, flow, volume, vital signs, and patient demographics from these data and their predictions were compared to the radiological
results. We found that 24 of 178 patients had pulmonary embolism. The best genome consisted of four genes: the minimum flow
rate during the third 30 s period of tidal breathing, the average peak exhaled CO2 during the first 30 s period of tidal breathing, the average peak of the exhaled O2 during the first 30 s period of tidal breathing, and the average peak exhaled CO2 during the fourth period of tidal breathing, which immediately followed a deep exhalation. This had 100% sensitivity and
91% specificity on the construction population and 100% and 82%, respectively when tested on the separate validation population.
Genetic programming using only data obtained from exhaled breaths was very accurate in classifying patients with suspected
pulmonary thromboembolism.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9050-x
  • Authors
    • Milo Engoren, University of Toledo, Medical University of Ohio, St. Vincent Mercy Medical Center Department of Anesthesiology 2213 Cherry Street Toledo OH 43608 USA
    • Jeffrey A. Kline, Carolinas Medical Center Department of Emergency Medicine Charlotte NC USA

Detecting the epistatic structure of generalized embedded landscape

Abstract  Working under the premise that most optimizable functions are of bounded epistasis, this paper addresses the problem of discovering
the linkage structure of a black-box function with a domain of arbitrary-cardinality under the assumption of bounded epistasis.
To model functions of bounded epistasis, we develop a generalization of the mathematical model of “embedded landscapes” over
domains of cardinality M. We then generalize the Walsh transform as a discrete Fourier transform, and develop algorithms for linkage learning of epistatically
bounded GELs. We propose Generalized Embedding Theorem that models the relationship between the underlying decomposable structure
of GEL and its Fourier coefficients. We give a deterministic algorithm to exactly calculate the Fourier coefficients of GEL
with bounded epistasis. Complexity analysis shows that the epistatic structure of epistatically bounded GEL can be obtained
after a polynomial number of function evaluations. Finally, an example experiment of the algorithm is presented.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9045-7
  • Authors
    • Shude Zhou, Tsinghua University Department of Computer Science and Technology Beijing 100084 China
    • Robert B. Heckendorn, University of Idaho Department of Computer Science Moscow ID 83844-1010 USA
    • Zengqi Sun, Tsinghua University Department of Computer Science and Technology Beijing 100084 China

Abstract  Working under the premise that most optimizable functions are of bounded epistasis, this paper addresses the problem of discovering
the linkage structure of a black-box function with a domain of arbitrary-cardinality under the assumption of bounded epistasis.
To model functions of bounded epistasis, we develop a generalization of the mathematical model of “embedded landscapes” over
domains of cardinality M. We then generalize the Walsh transform as a discrete Fourier transform, and develop algorithms for linkage learning of epistatically
bounded GELs. We propose Generalized Embedding Theorem that models the relationship between the underlying decomposable structure
of GEL and its Fourier coefficients. We give a deterministic algorithm to exactly calculate the Fourier coefficients of GEL
with bounded epistasis. Complexity analysis shows that the epistatic structure of epistatically bounded GEL can be obtained
after a polynomial number of function evaluations. Finally, an example experiment of the algorithm is presented.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9045-7
  • Authors
    • Shude Zhou, Tsinghua University Department of Computer Science and Technology Beijing 100084 China
    • Robert B. Heckendorn, University of Idaho Department of Computer Science Moscow ID 83844-1010 USA
    • Zengqi Sun, Tsinghua University Department of Computer Science and Technology Beijing 100084 China

Interactive evolution for cochlear implants fitting

Abstract  Cochlear implants (CI) are devices that become more and more sophisticated and adapted to the need of patients, but at the
same time they become more and more difficult to parameterize. After a deaf patient has been surgically implanted, a specialised
medical practitioner has to spend hours during months to precisely fit the implant to the patient. This process is a complex
one implying two intertwined tasks: the practitioner has to tune the parameters of the device (optimisation) while the patient’s
brain needs to adapt to the new data he receives (learning). This paper presents a study that intends to make the implant
more adaptable to environment (auditive ecology) and to simplify the process of fitting. Real experiments on volunteer implanted
patients are presented, that show the efficiency of interactive evolution for this purpose.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9048-4
  • Authors
    • Pierrick Legrand, UMR CNRS 5251, Université de Bordeaux 2 IMB, Institut de Mathématiques de Bordeaux 146 rue Léo Saignat 33076 Bordeaux cedex France
    • Claire Bourgeois-Republique, LE2I, UMR 5158 CNRS 9 Avenue A. Savary B.P. 47870 21078 Dijon cedex France
    • Vincent Péan, CRT Innotech 1 Promenade Jean Rostand 93005 Bobigny cedex France
    • Esther Harboun-Cohen, Hôpital Avicenne, Service ORL 125 rte de Stalingrad 93000 Bobigny France
    • Jacques Levy-Vehel, COMPLEX Team – INRIA Rocquencourt B.P. 105 78153 Le Chesnay cedex France
    • Bruno Frachet, Hôpital Avicenne, Service ORL 125 rte de Stalingrad 93000 Bobigny France
    • Evelyne Lutton, COMPLEX Team – INRIA Rocquencourt B.P. 105 78153 Le Chesnay cedex France
    • Pierre Collet, FDBT-LSIIT Boulevard Sébastien Brant BP 10413 67412 ILLKIRCH Cedex France

Abstract  Cochlear implants (CI) are devices that become more and more sophisticated and adapted to the need of patients, but at the
same time they become more and more difficult to parameterize. After a deaf patient has been surgically implanted, a specialised
medical practitioner has to spend hours during months to precisely fit the implant to the patient. This process is a complex
one implying two intertwined tasks: the practitioner has to tune the parameters of the device (optimisation) while the patient’s
brain needs to adapt to the new data he receives (learning). This paper presents a study that intends to make the implant
more adaptable to environment (auditive ecology) and to simplify the process of fitting. Real experiments on volunteer implanted
patients are presented, that show the efficiency of interactive evolution for this purpose.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9048-4
  • Authors
    • Pierrick Legrand, UMR CNRS 5251, Université de Bordeaux 2 IMB, Institut de Mathématiques de Bordeaux 146 rue Léo Saignat 33076 Bordeaux cedex France
    • Claire Bourgeois-Republique, LE2I, UMR 5158 CNRS 9 Avenue A. Savary B.P. 47870 21078 Dijon cedex France
    • Vincent Péan, CRT Innotech 1 Promenade Jean Rostand 93005 Bobigny cedex France
    • Esther Harboun-Cohen, Hôpital Avicenne, Service ORL 125 rte de Stalingrad 93000 Bobigny France
    • Jacques Levy-Vehel, COMPLEX Team – INRIA Rocquencourt B.P. 105 78153 Le Chesnay cedex France
    • Bruno Frachet, Hôpital Avicenne, Service ORL 125 rte de Stalingrad 93000 Bobigny France
    • Evelyne Lutton, COMPLEX Team – INRIA Rocquencourt B.P. 105 78153 Le Chesnay cedex France
    • Pierre Collet, FDBT-LSIIT Boulevard Sébastien Brant BP 10413 67412 ILLKIRCH Cedex France