Category: Community Feeds

Editorial introduction

Editorial introduction

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9054-6
  • Authors
    • Wolfgang Banzhaf, Memorial University of Newfoundland Department of Computer Science St. John’s NL Canada AlB 3X5

Editorial introduction

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9054-6
  • Authors
    • Wolfgang Banzhaf, Memorial University of Newfoundland Department of Computer Science St. John’s NL Canada AlB 3X5

Acknowledgment

Acknowledgment

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9055-5

Acknowledgment

  • Content Type Journal Article
  • DOI 10.1007/s10710-007-9055-5

Sporadic model building for efficiency enhancement of the hierarchical BOA

Abstract  Efficiency enhancement techniques—such as parallelization and hybridization—are among the most important ingredients of practical
applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary
computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation
of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure
of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only
model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters
is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time
complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of

\Uptheta(n0.26)

to

\Uptheta(n0.5),

where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional
model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on
the problem of finding ground states of 2D and 3D Ising spin glasses.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9052-8
  • Authors
    • Martin Pelikan, University of Missouri in St. Louis Missouri Estimation of Distribution Algorithms Laboratory, 321 CCB, Department of Mathematics and Computer Science One University Blvd. St. Louis MO 63121 USA
    • Kumara Sastry, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA
    • David E. Goldberg, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA

Abstract  Efficiency enhancement techniques—such as parallelization and hybridization—are among the most important ingredients of practical
applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary
computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation
of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure
of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only
model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters
is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time
complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of


\Uptheta(n0.26)

to


\Uptheta(n0.5),

where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional
model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on
the problem of finding ground states of 2D and 3D Ising spin glasses.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9052-8
  • Authors
    • Martin Pelikan, University of Missouri in St. Louis Missouri Estimation of Distribution Algorithms Laboratory, 321 CCB, Department of Mathematics and Computer Science One University Blvd. St. Louis MO 63121 USA
    • Kumara Sastry, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA
    • David E. Goldberg, University of Illinois at Urbana-Champaign Illinois Genetic Algorithms Laboratory, 117 TB, Department of Industrial and Enterprise Systems Engineering 104 S. Mathews Ave. Urbana IL 61801 USA

A genetic algorithm for discrete tomography reconstruction

Abstract  The aim of this paper is the description of an experiment carried out to verify the robustness of two different approaches
for the reconstruction of convex polyominoes in discrete tomography. This is a new field of research, because it differs from
classic computerized tomography, and several problems are still open. In particular, the stability problem is tackled by using
both a modified version of a known algorithm and a new genetic approach. The effect of both, instrumental and quantization
noises has been considered too.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9051-9
  • Authors
    • Cesare Valenti, Università di Palermo Dipartimento di Matematica e Applicazioni Via Archirafi 34 90123 Palermo Italy

Abstract  The aim of this paper is the description of an experiment carried out to verify the robustness of two different approaches
for the reconstruction of convex polyominoes in discrete tomography. This is a new field of research, because it differs from
classic computerized tomography, and several problems are still open. In particular, the stability problem is tackled by using
both a modified version of a known algorithm and a new genetic approach. The effect of both, instrumental and quantization
noises has been considered too.

  • Content Type Journal Article
  • Category Original Paper
  • DOI 10.1007/s10710-007-9051-9
  • Authors
    • Cesare Valenti, Università di Palermo Dipartimento di Matematica e Applicazioni Via Archirafi 34 90123 Palermo Italy

Maja J. Matarić: The Robotics Primer

Maja J. Matarić: The Robotics Primer

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-007-9053-7
  • Authors
    • Andrew Vardy, Memorial University of Newfoundland Computer Science/Engineering & Applied Science (Joint) St. John’s Canada

Maja J. Matarić: The Robotics Primer

  • Content Type Journal Article
  • Category Book Review
  • DOI 10.1007/s10710-007-9053-7
  • Authors
    • Andrew Vardy, Memorial University of Newfoundland Computer Science/Engineering & Applied Science (Joint) St. John’s Canada

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