Search

Testing can be key to software quality assurance. Automated verification may increase throughput and reduce human fallibility errors. Test scripts supply inputs, run programs and check their outputs mechanically using test oracles. In software engineering implicit oracles automatically check for universally undesirable behaviour, such as the software under test crashing. We propose 4 properties (probability distributions, fixed qubit width, reversibility and entropy conservation) which all quantum computing must have and suggest they could be implicit test oracles for automatic, random, or fuzz testing of quantum circuits and simulators of quantum programs.

Tuning the parameters and prompts for improving AI-based text-to-image generation has remained a substantial yet unaddressed challenge. Hence we introduce GreenStableYolo, which improves the parameters and prompts for Stable Diffusion to both reduce GPU inference time and increase image generation quality using NSGA-II and Yolo. Our experiments show that despite a relatively slight trade-off (18%) in image quality compared to StableYolo (which only considers image quality), GreenStableYolo achieves a substantial reduction in inference time (266% less) and a 526% higher hypervolume, thereby advancing the state-of-the-art for text-to-image generation., Comment: This paper is published in the SSBSE Challenge Track 2024

By their very name caches are often overlooked and yet play a vital role in the performance of modern and indeed future hardware. Using MAGPIE (Machine Automated General Performance Improvement via Evolution of software) we show genetic improvement GI can reduce the cache load of existing computer programs. Operating on lines of C and C++ source code using local search, Magpie can generate new functionally equivalent variants which generate fewer L1 data cache misses. Cache miss reduction is tested on two industrial open source programs (Google's Open Location Code OLC and Uber's Hexagonal Hierarchical Spatial Index H3) and two 2D photograph image processing tasks, counting pixels and OpenCV's SEEDS segmentation algorithm. Magpie's patches functionally generalise. In one case they reduce data misses on the highest performance L1 cache dramatically by 47 percent.

We summarise how a 3.0 GHz 16 core AVX512 computer can interpret the equivalent of up to on average 1103370000000 GPop/s. Citations to existing publications are given. Implementation stress is placed on both parallel computing, bandwidth limits and avoiding repeated calculation. Information theory suggests in digital computing, failed disruption propagation gives huge speed ups as FDP and incremental evaluation can be used to reduce fitness evaluation time in phenotypically converged populations. Conversely FDP may be responsible for evolution stagnation. So the wider Evolutionary Computing, Artificial Life, Unconventional Computing and Software Engineering community may need to avoid deep nesting., Comment: 9 pages, 5 figures

We inject a random value into the evaluation of highly evolved deep integer GP trees 9743720 times and find 99.7percent Suggesting crossover and mutation's impact are dissipated and seldom propagate outside the program. Indeed only errors near the root node have impact and disruption falls exponentially with depth at between exp(-depth/3) and exp(-depth/5) for recursive Fibonacci GP trees, allowing five to seven levels of nesting between the runtime perturbation and an optimal test oracle for it to detect most errors. Information theory explains this locally flat fitness landscape is due to FDP. Overflow is not important and instead, integer GP, like deep symbolic regression floating point GP and software in general, is not fragile, is robust, is not chaotic and suffers little from Lorenz' butterfly. Keywords: genetic algorithms, genetic programming, SBSE, information loss, information funnels, entropy, evolvability, mutational robustness, optimal test oracle placement, neutral networks, software robustness, correctness attraction, diversity, software testing, theory of bloat, introns, Comment: Long version of GECCO 2022 poster

Information theoretic analysis of large evolved programs produced by running genetic programming for up to a million generations has shown even functions as smooth and well behaved as floating point addition and multiplication loose entropy and consequently are robust and fail to propagate disruption to their outputs. This means, while dependent upon fitness tests, many genetic changes deep within trees are silent. For evolution to proceed at reasonable rate it must be possible to measure the impact of most code changes, yet in large trees most crossover sites are distant from the root node. We suggest to evolve very large very complex programs, it will be necessary to adopt an open architecture where most mutation sites are within 10 to 100 levels of the organism's environment., Comment: Accepted for publication by SIGEVOlution newsletter of the ACM Special Interest Group on Genetic and Evolutionary Computation, ISSN 1931-8499, evolution.sigevo.org (publication expected 2022). 4 pages, 1 figure http://www.cs.ucl.ac.uk/staff/W.Langdon/gif/random_graph.svg.gz

C++ code snippets from a multi-core parallel memory-efficient crossover for genetic programming are given. They may be adapted for separate generation evolutionary algorithms where large chromosomes or small RAM require no more than M + (2 times nthreads) simultaneously active individuals., Comment: 11 pages, 3 figures

Following Prof. Mark Harman of Facebook's keynote and formal presentations (which are recorded in the proceedings) there was a wide ranging discussion at the eighth international Genetic Improvement workshop, GI-2020 @ ICSE (held as part of the 42nd ACM/IEEE International Conference on Software Engineering on Friday 3rd July 2020). Topics included industry take up, human factors, explainabiloity (explainability, justifyability, exploitability) and GI benchmarks. We also contrast various recent online approaches (e.g. SBST 2020) to holding virtual computer science conferences and workshops via the WWW on the Internet without face-2-face interaction. Finally we speculate on how the Coronavirus Covid-19 Pandemic will affect research next year and into the future., Comment: 7 pages, 2 figures. Write up of GI @ ICSE 2020 workshop. Submitted to ACM SIGSOFT Software Engineering Notes

random_tree() is a linear time and space C++ implementation able to create trees of up to a billion nodes for genetic programming and genetic improvement experiments. A 3.60GHz CPU can generate more than 18 million random nodes for GP program trees per second., Comment: C++ code: http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/gp-code/rand_tree.cc_r1.43

We report the discussion session at the sixth international Genetic Improvement workshop, GI-2019 @ ICSE, which was held as part of the 41st ACM/IEEE International Conference on Software Engineering on Tuesday 28th May 2019. Topics included GI representations, the maintainability of evolved code, automated software testing, future areas of GI research, such as co-evolution, and existing GI tools and benchmarks., Comment: University College London, Computer Science

We evolve floating point Sextic polynomial populations of genetic programming binary trees for up to a million generations. Programs with almost four hundred million instructions are created by crossover. To support unbounded Long-Term Evolution Experiment LTEE GP we use both SIMD parallel AVX 512 bit instructions and 48 threads to yield performance of up to 139 billion GP operations per second, 139 giga GPops, on a single Intel Xeon Gold 6126 2.60GHz server., Comment: 20 pages, 17 figures

Report on Humies competition at GECCO 2018 in Japan, Comment: To appear in SIGEVOlution

The distribution of reversible programs tends to a limit as their size increases. For problems with a Hamming distance fitness function the limiting distribution is binomial with an exponentially small chance (but non~zero) chance of perfect solution. Sufficiently good reversible circuits are more common. Expected RMS error is also calculated. Random unitary matrices may suggest possible extension to quantum computing. Using the genetic programming (GP) benchmark, the six multiplexor, circuits of Toffoli gates are shown to give a fitness landscape amenable to evolutionary search. Minimal CCNOT solutions to the six multiplexer are found but larger circuits are more evolvable., Comment: Published as Chapter 11, pp173-187, in Genetic Programming Theory and Practice, 2003, Rick L. Riolo and Bill Worzel (editors)

We evolve binary mux-6 trees for up to 100000 generations evolving some programs with more than a hundred million nodes. Our unbounded Long-Term Evolution Experiment LTEE GP appears not to evolve building blocks but does suggests a limit to bloat. We do see periods of tens even hundreds of generations where the population is 100 percent functionally converged. The distribution of tree sizes is not as predicted by theory., Comment: Longer version of Langdon:2017:GECCO, July 2017, ACM, Berlin, RN/17/05 http://www.cs.ucl.ac.uk/fileadmin/UCL-CS/research/Research_Notes/RN_17_05.pdf

BarraCUDA is a C program which uses the BWA algorithm in parallel with nVidia CUDA to align short next generation DNA sequences against a reference genome. The genetically improved (GI) code is up to three times faster on short paired end reads from The 1000 Genomes Project and 60percent more accurate on a short BioPlanet.com GCAT alignment benchmark. GPGPU Barracuda running on a single K80 Tesla GPU can align short paired end nextgen sequences up to ten times faster than bwa on a 12 core CPU., Comment: UCL, Department of Computer Science, technical report RN/15/03

We study a generic program to investigate the scope for automatically customising it for a vital current task, which was not considered when it was first written. In detail, we show genetic programming (GP) can evolve models of aspects of BLAST's output when it is used to map Solexa Next-Gen DNA sequences to the human genome., Comment: As UCL computer science Technical Report RN/13/12

We have recently used genetic programming to automatically generate an improved version of Langmead's DNA read alignment tool Bowtie2 Sect.5.3 RN/12/09. We find it runs more than four times faster than the Bioinformatics sequencing tool (BWA) currently used with short next generation paired end DNA sequences by the Cancer Institute, takes less memory and yet finds similar matches in the human genome., Comment: 4 pages, 2 tables

We assess when electron trapping nonlinearity is expected to be important in Langmuir waves. The basic criterion is that the inverse of the detrapping rate nu_d of electrons in the trapping region of velocity space must exceed the bounce period of deeply-trapped electrons, tau_B = (n_e/delta n)^{1/2} 2pi/omega_pe. A unitless figure of merit, the "bounce number" N_B = 1/(nu_d tau_B), encapsulates this condition and defines a trapping threshold amplitude for which N_B=1. The detrapping rate is found for convective loss (transverse and longitudinal) out of a spatially finite Langmuir wave. Simulations of driven waves with a finite transverse profile, using the 2D-2V Vlasov code Loki, show trapping nonlinearity increases continuously with N_B for transverse loss, and is significant for N_B ~ 1. The detrapping rate due to Coulomb collisions (both electron-electron and electron-ion) is also found, with pitch-angle scattering and parallel drag and diffusion treated in a unified manner. A simple way to combine convective and collisional detrapping is given. Application to underdense plasma conditions in inertial confinement fusion targets is presented. The results show that convective transverse loss is usually the most potent detrapping process in a single f/8 laser speckle. For typical plasma and laser conditions on the inner laser cones of the National Ignition Facility, local reflectivities ~3% are estimated to produce significant trapping effects., Comment: 16 pages, 15 figures, accepted for publication in Phys. Plasmas

The human genome sequence database contains DNA sequences very like those of mycoplasma molds. It appears such moulds infect not only molecular Biology laboratories but were picked up by experimenters from contaminated samples and inserted into GenBank as if they were human. At least one mouldy EST (Expressed Sequence Tag) has transferred from public databases to commercial tools (Affymetrix HG-U133 plus 2.0 microarrays). We report a second example (DA466599) and suggest there is a need to clean up genomic databases but fear current tools will be inadequate to catch genes which have jumped the silicon barrier., Comment: data directory contains results of AF241217 and DA466599 blast runs by EBI in Cambridge

Ensembl's human non-coding and protein coding genes are used to automatically find DNA pattern motifs. The Backus-Naur form (BNF) grammar for regular expressions (RE) is used by genetic programming to ensure the generated strings are legal. The evolved motif suggests the presence of Thymine followed by one or more Adenines etc. early in transcripts indicate a non-protein coding gene. Keywords: pseudogene, short and microRNAs, non-coding transcripts, systems biology, machine learning, Bioinformatics, motif, regular expression, strongly typed genetic programming, context-free grammar., Comment: 12 pages, 2 figures

RNAnet provides a bridge between two widely used Human gene databases. Ensembl describes DNA sequences and transcripts but not experimental gene expression. Whilst NCBI's GEO contains actual expression levels from Human samples. RNAnet provides immediate access to thousands of Affymetrix HG-U133 2plus GeneChip measurements Homo sapiens genes in most medically interesting tissues. Without RNAnet comparison across experiments in GEO is very labour intensive requiring man months of effort to down load and clean data. With RNAnet anyone can access cleaned quantile normalised data in seconds. It can be used to data mine patterns of co-expression. The network of strongly correlated genes is huge but sparse. Thousands of genes interact strongly with thousands of others. Conversely there are tens of thousands of genes which interact strongly with less than 100 others. I.e. RNAnet gives new views for RNA Systems Biology., Comment: 1 page, 0 figures

The temperature equilibration rate in dense hydrogen (for both T_{i}>T_{e} and T_i1, a model by Gericke-Murillo-Schlanges (GMS) [Gericke et al., PRE 65, 036418 (2002)] based on a T-matrix method and the approach by Brown-Preston-Singleton [Brown et al., Phys. Rep. 410, 237 (2005)] agrees with the simulation data to within the error bars of the simulation. For smaller Coulomb logarithms, the GMS model is consistent with the simulation results. Landau-Spitzer models are consistent with the simulation data for L>4.

We rewrite Riemann Zeta function as a sum over the primes. Each term of the sum is a product that depends only on the summation index (a prime) and the primes following it.

We study stimulated Raman scattering (SRS) in laser-fusion conditions with the Eulerian Vlasov code ELVIS. Back SRS from homogeneous plasmas occurs in sub-picosecond bursts and far exceeds linear theory. Forward SRS and re-scatter of back SRS are also observed. The plasma wave frequency downshifts from the linear dispersion curve, and the electron distribution shows flattening. This is consistent with trapping and reduces the Landau damping. There is some acoustic ($\omega\propto k$) activity and possibly electron acoustic scatter. Kinetic ions do not affect SRS for early times but suppress it later on. SRS from inhomogeneous plasmas exhibits a kinetic enhancement for long density scale lengths. More scattering results when the pump propagates to higher as opposed to lower density., Comment: 4 pages, 6 figures. Submitted to "Journal of Plasmas Physics" for the conference proceedings of the 19th International Conference on Numerical Simulation of Plasmas