01691nas a2200205 4500008004100000245006200041210005800103490000700161520114300168653001401311653001101325653001001336100001201346700001301358700001501371700001601386700001601402700001701418856005001435 2011 eng d00aA user-friendly web portal for T-Coffee on supercomputers0 auserfriendly web portal for TCoffee on supercomputers0 v123 aBackground Parallel T-Coffee (PTC) was the first parallel implementation of the T-Coffee multiple sequence alignment tool. It is based on MPI and RMA mechanisms. Its purpose is to reduce the execution time of the large-scale sequence alignments. It can be run on distributed memory clusters allowing users to align data sets consisting of hundreds of proteins within a reasonable time. However, most of the potential users of this tool are not familiar with the use of grids or supercomputers. Results In this paper we show how PTC can be easily deployed and controlled on a super computer architecture using a web portal developed using Rapid. Rapid is a tool for efficiently generating standardized portlets for a wide range of applications and the approach described here is generic enough to be applied to other applications, or to deploy PTC on different HPC environments. Conclusions The PTC portal allows users to upload a large number of sequences to be aligned by the parallel version of TC that cannot be aligned by a single machine due to memory and execution time constraints. The web portal provides a user-friendly solution.10ae-Science10aportal10arapid1 aRius, J1 aCores, F1 aSolsona, F1 aHemert, J I1 aKoetsier, J1 aNotredame, C uhttp://www.biomedcentral.com/1471-2105/12/15002521nas a2200205 4500008003900000245012900039210006900168490000700237520187300244100001702117700001602134700001402150700001902164700001502183700001602198700001602214700001502230700002002245856005002265 2010 d00aCorrecting for intra-experiment variation in Illumina BeadChip data is necessary to generate robust gene-expression profiles0 aCorrecting for intraexperiment variation in Illumina BeadChip da0 v113 aBackground
Microarray technology is a popular means of producing whole genome transcriptional profiles, however high cost and scarcity of mRNA has led many studies to be conducted based on the analysis of single samples. We exploit the design of the Illumina platform, specifically multiple arrays on each chip, to evaluate intra-experiment technical variation using repeated hybridisations of universal human reference RNA (UHRR) and duplicate hybridisations of primary breast tumour samples from a clinical study.
Results
A clear batch-specific bias was detected in the measured expressions of both the UHRR and clinical samples. This bias was found to persist following standard microarray normalisation techniques. However, when mean-centering or empirical Bayes batch-correction methods (ComBat) were applied to the data, inter-batch variation in the UHRR and clinical samples were greatly reduced. Correlation between replicate UHRR samples improved by two orders of magnitude following batch-correction using ComBat (ranging from 0.9833-0.9991 to 0.9997-0.9999) and increased the consistency of the gene-lists from the duplicate clinical samples, from 11.6% in quantile normalised data to 66.4% in batch-corrected data. The use of UHRR as an inter-batch calibrator provided a small additional benefit when used in conjunction with ComBat, further increasing the agreement between the two gene-lists, up to 74.1%.
Conclusion
In the interests of practicalities and cost, these results suggest that single samples can generate reliable data, but only after careful compensation for technical bias in the experiment. We recommend that investigators appreciate the propensity for such variation in the design stages of a microarray experiment and that the use of suitable correction methods become routine during the statistical analysis of the data. 1 aKitchen, R R1 aSabine, V S1 aSims, A H1 aMacaskill, E J1 aRenshaw, L1 aThomas, J S1 aHemert, J I1 aDixon, J M1 aBartlett, J M S uhttp://www.biomedcentral.com/1471-2164/11/13400562nas a2200157 4500008004100000245009800041210006900139300001300208490000700221653001900228653001300247100001400260700001600274700001600290856009800306 2009 eng d00aThe Circulate Architecture: Avoiding Workflow Bottlenecks Caused By Centralised Orchestration0 aCirculate Architecture Avoiding Workflow Bottlenecks Caused By C a221--2350 v1210agrid computing10aworkflow1 aBarker, A1 aWeissman, J1 aHemert, J I uhttp://www.springerlink.com/content/080q5857711w2054/?p=824749739c6a432ea95a0c3b59f4025f&pi=100530nas a2200169 4500008004100000020002200041245008200063210006900145260001300214300001300227490000800240100001600248700001700264700002400281700001500305856004000320 2009 eng d a978-3-540-85151-600aExploiting Fruitful Regions in Dynamic Routing using Evolutionary Computation0 aExploiting Fruitful Regions in Dynamic Routing using Evolutionar bSpringer a131--1490 v1611 aHemert, J I1 aPoutré, J A1 aPereira Babtista, F1 aTavares, J uhttp://research.nesc.ac.uk/node/32100709nas a2200133 4500008003900000245004900039210004900088300001100137490000600148520031000154100001600464700001600480856007900496 2009 d00aGiving Computational Science a Friendly Face0 aGiving Computational Science a Friendly Face a12--130 v13 aToday, most researchers from any discipline will successfully use web-based e-commerce systems to book flights to attend their conferences. But when these same researchers are confronted with compute-intensive problems, they cannot expect elaborate web-based systems to enable their domain-specific tasks.1 aHemert, J I1 aKoetsier, J uhttp://www.beliefproject.org/zero-in/zero-in-third-edition/zero-in-issue-300858nas a2200133 4500008003900000022001400039245005300053210005300106520046900159100001900628700001800647700001600665856004300681 2009 d a1613-007300aPortals for Life Sciences—a Brief Introduction0 aPortals for Life Sciences—a Brief Introduction3 aThe topic ”‘Portals for Life Sciences”’ includes various research fields, on the one hand many different topics out of life sciences, e.g. mass spectrometry, on the other hand portal technologies and different aspects of computer science, such as usability of user interfaces and security of systems. The main aspect about portals is to simplify the user’s interaction with computational resources which are concer- ted to a supported application domain.1 aGesing, Sandra1 aKohlbacher, O1 aHemert, J I uhttp://ceur-ws.org/Vol-513/paper01.pdf01193nas a2200181 4500008003900000245005700039210005700096260001500153300001200168520069400180100001600874700001400890700001800904700001600922700001700938700001600955856004000971 2009 d00aRapid chemistry portals through engaging researchers0 aRapid chemistry portals through engaging researchers aOxford, UK a284-2913 aIn this study, we apply a methodology for rapid development of portlets for scientific computing to the domain of computational chemistry. We report results in terms of the portals delivered, the changes made to our methodology and the experience gained in terms of interaction with domain-specialists. Our major contributions are: several web portals for teaching and research in computational chemistry; a successful transition to having our development tool used by the domain specialist as opposed by us, the developers; and an updated version of our methodology and technology for rapid development of portlets for computational science, which is free for anyone to pick up and use.
1 aKoetsier, J1 aTurner, A1 aRichardson, P1 aHemert, J I1 aTrefethen, A1 aDe Roure, D uhttp://research.nesc.ac.uk/node/51300491nas a2200157 4500008004100000022001400041245005500055210005500110260005200165653001100217100001600228700001600244700001400260700001600274856004300290 2009 eng d a1613-007300aRapid development of computational science portals0 aRapid development of computational science portals aEdinburghbe-Science Institutec14-15 September10aportal1 aKoetsier, J1 aHemert, J I1 aGesing, S1 aHemert, J I uhttp://ceur-ws.org/Vol-513/paper05.pdf01542nas a2200157 4500008004100000245003200041210003200073260000900105300001500114490000800129520112400137653001401261100001901275700001601294856007401310 2009 eng d00aTowards a Virtual Fly Brain0 aTowards a Virtual Fly Brain cJune a2387--23970 v3673 aModels of the brain that simulate sensory input, behavioural output and information processing in a biologically plausible manner pose significant challenges to both Computer Science and Biology. Here we investigated strategies that could be used to create a model of the insect brain, specifically that of Drosophila melanogaster which is very widely used in laboratory research. The scale of the problem is an order of magnitude above the most complex of the current simulation projects and it is further constrained by the relative sparsity of available electrophysiological recordings from the fly nervous system. However, fly brain research at the anatomical and behavioural level offers some interesting opportunities that could be exploited to create a functional simulation. We propose to exploit these strengths of Drosophila CNS research to focus on a functional model that maps biologically plausible network architecture onto phenotypic data from neuronal inhibition and stimulation studies, leaving aside biophysical modelling of individual neuronal activity for future models until more data is available.10ae-Science1 aArmstrong, J D1 aHemert, J I uhttp://rsta.royalsocietypublishing.org/content/367/1896/2387.abstract01322nas a2200145 4500008003900000022001400039245008500053210006900138260001000207490000600217520086100223100002001084700001601104856005601120 2009 d a1746-825600aUsing the DCC Lifecycle Model to Curate a Gene Expression Database: A Case Study0 aUsing the DCC Lifecycle Model to Curate a Gene Expression Databa bUKOLN0 v43 aDevelopmental Gene Expression Map (DGEMap) is an EU-funded Design Study, which will accelerate an integrated European approach to gene expression in early human development. As part of this design study, we have had to address the challenges and issues raised by the long-term curation of such a resource. As this project is primarily one of data creators, learning about curation, we have been looking at some of the models and tools that are already available in the digital curation field in order to inform our thinking on how we should proceed with curating DGEMap. This has led us to uncover a wide range of resources for data creators and curators alike. Here we will discuss the future curation of DGEMap as a case study. We believe our experience could be instructive to other projects looking to improve the curation and management of their data.1 aO’Donoghue, J1 aHemert, J I uhttp://www.ijdc.net/index.php/ijdc/article/view/13400602nas a2200181 4500008004100000245010900041210006900150260001300219300001300232653002800245653002900273653002000302100001300322700001600335700001300351700001600364856004000380 2008 eng d00aContraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem0 aContractionBased Heuristics to Improve the Efficiency of Algorit bSpringer a167--18410aconstraint satisfaction10aevolutionary computation10agraph colouring1 aJuhos, I1 aHemert, J I1 aCotta, C1 aHemert, J I uhttp://research.nesc.ac.uk/node/32201224nas a2200217 4500008004100000245008700041210006900128260002000197300001300217520061500230653001500845653001600860653001100876653001400887100001600901700001700917700001500934700001000949700000700959856004000966 2008 eng d00aMatching Spatial Regions with Combinations of Interacting Gene Expression Patterns0 aMatching Spatial Regions with Combinations of Interacting Gene E bSpringer Verlag a347--3613 aThe Edinburgh Mouse Atlas aims to capture in-situ gene expression patterns in a common spatial framework. In this study, we construct a grammar to define spatial regions by combinations of these patterns. Combinations are formed by applying operators to curated gene expression patterns from the atlas, thereby resembling gene interactions in a spatial context. The space of combinations is searched using an evolutionary algorithm with the objective of finding the best match to a given target pattern. We evaluate the method by testing its robustness and the statistical significance of the results it finds.10abiomedical10adata mining10aDGEMap10ae-Science1 aHemert, J I1 aBaldock, R A1 aElloumi, M1 a\emph1 aal uhttp://research.nesc.ac.uk/node/26101100nas a2200205 4500008004100000245006200041210006200103260002000165300001100185520052700196653001500723653001600738653001100754653001400765100001600779700001700795700001800812700001400830856005000844 2007 eng d00aMining spatial gene expression data for association rules0 aMining spatial gene expression data for association rules bSpringer Verlag a66--763 aWe analyse data from the Edinburgh Mouse Atlas Gene-Expression Database (EMAGE) which is a high quality data source for spatio-temporal gene expression patterns. Using a novel process whereby generated patterns are used to probe spatially-mapped gene expression domains, we are able to get unbiased results as opposed to using annotations based predefined anatomy regions. We describe two processes to form association rules based on spatial configurations, one that associates spatial regions, the other associates genes.10abiomedical10adata mining10aDGEMap10ae-Science1 aHemert, J I1 aBaldock, R A1 aHochreiter, S1 aWagner, R uhttp://dx.doi.org/10.1007/978-3-540-71233-6_601287nas a2200193 4500008004100000245007300041210006900114300001300183490000700196520067600203653002700879653002800906653002900934653002100963653001900984653002401003100001601027856005001043 2006 eng d00aEvolving combinatorial problem instances that are difficult to solve0 aEvolving combinatorial problem instances that are difficult to s a433--4620 v143 aIn this paper we demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances, thereby stress-testing the corresponding algorithms used to solve these instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.10aconstraint programming10aconstraint satisfaction10aevolutionary computation10aproblem evolving10asatisfiability10atravelling salesman1 aHemert, J I uhttp://www.mitpressjournals.org/toc/evco/14/401191nas a2200181 4500008004100000245008500041210006900126260002000195300001300215520063600228653002800864653002000892100001300912700001600925700001600941700001300957856003900970 2006 eng d00aImproving Graph Colouring Algorithms and Heuristics Using a Novel Representation0 aImproving Graph Colouring Algorithms and Heuristics Using a Nove bSpringer-Verlag a123--1343 aWe introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of an algorithm. Moreover, our model provides useful information for guiding heuristics as well as a compact description for algorithms. To verify the potential of the model, we use it in dsatur, in an evolutionary algorithm, and in the same evolutionary algorithm extended with heuristics. An empiricial investigation is performed to show an increase in efficiency on two problem suites , a set of practical problem instances and a set of hard problem instances from the phase transition.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aHemert, J I1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/1101421nas a2200145 4500008004100000245010900041210006900150300001100219490000600230520095200236653002001188100001301208700001601221856003801237 2006 eng d00aIncreasing the efficiency of graph colouring algorithms with a representation based on vector operations0 aIncreasing the efficiency of graph colouring algorithms with a r a24--330 v13 aWe introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of graph colouring algorithms. Moreover, this model provides useful information to aid in the creation of heuristics that can make the colouring process even faster. It also serves as a compact definition for the description of graph colouring algorithms. To verify the potential of the model, we use it in the complete algorithm DSATUR, and in two version of an incomplete approximation algorithm; an evolutionary algorithm and the same evolutionary algorithm extended with guiding heuristics. Both theoretical and empirical results are provided investigation is performed to show an increase in the efficiency of solving graph colouring problems. Two problem suites were used for the empirical evidence: a set of practical problem instances and a set of hard problem instances from the phase transition.10agraph colouring1 aJuhos, I1 aHemert, J I uhttp://research.nesc.ac.uk/node/701469nas a2200217 4500008004100000245011200041210006900153260002200222300001500244490000600259520078400265653002801049653002901077653003401106100001401140700001601154700001501170700002101185700000701206856003801213 2006 eng d00aNeighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO0 aNeighborhood Searches for the Bounded Diameter Minimum Spanning aSeattle, USAbACM a1187--11940 v23 aWe consider the Bounded Diameter Minimum Spanning Tree problem and describe four neighbourhood searches for it. They are used as local improvement strategies within a variable neighbourhood search (VNS), an evolutionary algorithm (EA) utilising a new encoding of solutions, and an ant colony optimisation (ACO).We compare the performance in terms of effectiveness between these three hybrid methods on a suite f popular benchmark instances, which contains instances too large to solve by current exact methods. Our results show that the EA and the ACO outperform the VNS on almost all used benchmark instances. Furthermore, the ACO yields most of the time better solutions than the EA in long-term runs, whereas the EA dominates when the computation time is strongly restricted.10aconstraint satisfaction10aevolutionary computation10avariable neighbourhood search1 aGruber, M1 aHemert, J I1 aRaidl, G R1 aKeijzer, Maarten1 aal uhttp://research.nesc.ac.uk/node/801078nas a2200181 4500008004100000245010300041210006900144260001700213300001300230520050200243653002800745653002200773100001600795700001600811700001600827700001400843856003900857 2005 eng d00aComplexity Transitions in Evolutionary Algorithms: Evaluating the impact of the initial population0 aComplexity Transitions in Evolutionary Algorithms Evaluating the b{IEEE} Press a196--2033 aThis paper proposes an evolutionary approach for the composition of solutions in an incremental way. The approach is based on the metaphor of transitions in complexity discussed in the context of evolutionary biology. Partially defined solutions interact and evolve into aggregations until a full solution for the problem at hand is found. The impact of the initial population on the outcome and the dynamics of the process is evaluated using the domain of binary constraint satisfaction problems.10aconstraint satisfaction10atransition models1 aDefaweux, A1 aLenaerts, T1 aHemert, J I1 aParent, J uhttp://research.nesc.ac.uk/node/1201208nas a2200241 4500008004100000020001800041245007300059210006900132260002000201300001300221520051200234653002800746653002200774100001600796700001600812700001600828700001800844700001700862700001700879700001700896700001400913856003900927 2005 eng d a3-540-28848-100aEvolutionary Transitions as a Metaphor for Evolutionary Optimization0 aEvolutionary Transitions as a Metaphor for Evolutionary Optimiza bSpringer-Verlag a342--3523 aThis paper proposes a computational model for solving optimisation problems that mimics the principle of evolutionary transitions in individual complexity. More specifically it incorporates mechanisms for the emergence of increasingly complex individuals from the interaction of more simple ones. The biological principles for transition are outlined and mapped onto an evolutionary computation context. The class of binary constraint satisfaction problems is used to illustrate the transition mechanism.10aconstraint satisfaction10atransition models1 aDefaweux, A1 aLenaerts, T1 aHemert, J I1 aCapcarrere, M1 aFreitas, A A1 aBentley, P J1 aJohnson, C G1 aTimmis, J uhttp://research.nesc.ac.uk/node/1301085nas a2200193 4500008004100000245007900041210006900120260002800189300001300217520050300230653002800733653002000761100001300781700001300794700001600807700001300823700001600836856003900852 2005 eng d00aHeuristic Colour Assignment Strategies for Merge Models in Graph Colouring0 aHeuristic Colour Assignment Strategies for Merge Models in Graph bSpringer-Verlag, Berlin a132--1433 aIn this paper, we combine a powerful representation for graph colouring problems with different heuristic strategies for colour assignment. Our novel strategies employ heuristics that exploit information about the partial colouring in an aim to improve performance. An evolutionary algorithm is used to drive the search. We compare the different strategies to each other on several very hard benchmarks and on generated problem instances, and show where the novel strategies improve the efficiency.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aTóth, A1 aHemert, J I1 aRaidl, G1 aGottlieb, J uhttp://research.nesc.ac.uk/node/1700968nas a2200169 4500008004100000245010000041210006900141260002800210300001300238520041800251653002100669653002400690100001600714700001300730700001600743856003900759 2005 eng d00aProperty analysis of symmetric travelling salesman problem instances acquired through evolution0 aProperty analysis of symmetric travelling salesman problem insta bSpringer-Verlag, Berlin a122--1313 aWe show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling salesman problem.10aproblem evolving10atravelling salesman1 aHemert, J I1 aRaidl, G1 aGottlieb, J uhttp://research.nesc.ac.uk/node/1601125nas a2200205 4500008004100000245009600041210006900137260001600206300001300222520051000235653002800745653002200773100001600795700001600811700001600827700001400843700001600857700000700873856003900880 2005 eng d00aTransition Models as an incremental approach for problem solving in Evolutionary Algorithms0 aTransition Models as an incremental approach for problem solving b{ACM} Press a599--6063 aThis paper proposes an incremental approach for building solutions using evolutionary computation. It presents a simple evolutionary model called a Transition model. It lets building units of a solution interact and then uses an evolutionary process to merge these units toward a full solution for the problem at hand. The paper provides a preliminary study on the evolutionary dynamics of this model as well as an empirical comparison with other evolutionary techniques on binary constraint satisfaction.10aconstraint satisfaction10atransition models1 aDefaweux, A1 aLenaerts, T1 aHemert, J I1 aParent, J1 aBeyer, H -G1 aal uhttp://research.nesc.ac.uk/node/1401019nas a2200205 4500008004100000020001800041245006900059210006900128260002800197300001300225520041700238653002800655653002000683100001300703700001300716700001600729700001600745700001300761856003900774 2004 eng d a3-540-21367-800aBinary Merge Model Representation of the Graph Colouring Problem0 aBinary Merge Model Representation of the Graph Colouring Problem bSpringer-Verlag, Berlin a124--1343 aThis paper describes a novel representation and ordering model that aided by an evolutionary algorithm, is used in solving the graph \emph{k}-colouring problem. Its strength lies in reducing the search space by breaking symmetry. An empirical comparison is made with two other algorithms on a standard suit of problem instances and on a suit of instances in the phase transition where it shows promising results.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aTóth, A1 aHemert, J I1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/2101484nas a2200301 4500008004100000020001800041245008800059210006900147260003600216300001300252490000900265520058500274653002100859653002900880653002000909100001600929700001700945700001300962700001800975700002000993700001501013700003001028700002401058700001901082700001801101700002401119856003901143 2004 eng d a3-540-23092-000aDynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation0 aDynamic Routing Problems with Fruitful Regions Models and Evolut aBirmingham, UKbSpringer-Verlag a690--6990 v32423 aWe introduce the concept of fruitful regions in a dynamic routing context: regions that have a high potential of generating loads to be transported. The objective is to maximise the number of loads transported, while keeping to capacity and time constraints. Loads arrive while the problem is being solved, which makes it a real-time routing problem. The solver is a self-adaptive evolutionary algorithm that ensures feasible solutions at all times. We investigate under what conditions the exploration of fruitful regions improves the effectiveness of the evolutionary algorithm.10adynamic problems10aevolutionary computation10avehicle routing1 aHemert, J I1 aPoutré, J A1 aYao, Xin1 aBurke, Edmund1 aLozano, Jose, A1 aSmith, Jim1 aMerelo-Guerv\'os, Juan, J1 aBullinaria, John, A1 aRowe, Jonathan1 an, Peter Ti\v1 aSchwefel, Hans-Paul uhttp://research.nesc.ac.uk/node/1901761nas a2200301 4500008004100000020001800041245012300059210006900182260003600251300001300287490000900300520078600309653002901095653002101124653002401145100001601169700001801185700001301203700001801216700002001234700001501254700003001269700002401299700001901323700001801342700002401360856007501384 2004 eng d a3-540-23092-000aPhase transition properties of clustered travelling salesman problem instances generated with evolutionary computation0 aPhase transition properties of clustered travelling salesman pro aBirmingham, UKbSpringer-Verlag a150--1590 v32423 aThis paper introduces a generator that creates problem instances for the Euclidean symmetric travelling salesman problem. To fit real world problems, we look at maps consisting of clustered nodes. Uniform random sampling methods do not result in maps where the nodes are spread out to form identifiable clusters. To improve upon this, we propose an evolutionary algorithm that uses the layout of nodes on a map as its genotype. By optimising the spread until a set of constraints is satisfied, we are able to produce better clustered maps, in a more robust way. When varying the number of clusters in these maps and, when solving the Euclidean symmetric travelling salesman person using Chained Lin-Kernighan, we observe a phase transition in the form of an easy-hard-easy pattern.10aevolutionary computation10aproblem evolving10atravelling salesman1 aHemert, J I1 aUrquhart, N B1 aYao, Xin1 aBurke, Edmund1 aLozano, Jose, A1 aSmith, Jim1 aMerelo-Guerv\'os, Juan, J1 aBullinaria, John, A1 aRowe, Jonathan1 an, Peter Ti\v1 aSchwefel, Hans-Paul uhttp://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz01316nas a2200169 4500008004100000245014000041210006900181300001300250490000700263520073000270653002801000653002901028653002101057100001601078700001301094856003901107 2004 eng d00aRobust parameter settings for variation operators by measuring the resampling ratio: A study on binary constraint satisfaction problems0 aRobust parameter settings for variation operators by measuring t a629--6400 v103 aIn this article, we try to provide insight into the consequence of mutation and crossover rates when solving binary constraint satisfaction problems. This insight is based on a measurement of the space searched by an evolutionary algorithm. From data empirically acquired we describe the relation between the success ratio and the searched space. This is achieved using the resampling ratio, which is a measure for the amount of points revisited by a search algorithm. This relation is based on combinations of parameter settings for the variation operators. We then show that the resampling ratio is useful for identifying the quality of parameter settings, and provide a range that corresponds to robust parameter settings.10aconstraint satisfaction10aevolutionary computation10aresampling ratio1 aHemert, J I1 aBäck, T uhttp://research.nesc.ac.uk/node/1801488nas a2200217 4500008004100000020001800041245013700059210006900196260002800265300001300293520075400306653002801060653002701088653002801115653002901143100001601172700001401188700001601202700001301218856003901231 2004 eng d a3-540-21367-800aA Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems0 aStudy into Ant Colony Optimization Evolutionary Computation and bSpringer-Verlag, Berlin a114--1233 aWe compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, constraint programming, for solving binary constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables.10aant colony optimisation10aconstraint programming10aconstraint satisfaction10aevolutionary computation1 aHemert, J I1 aSolnon, C1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/2201651nas a2200157 4500008004100000245008100041210006900122300001300191490000600204520094500210653002801155100001901183700001501202700001601217856026001233 2003 eng d00aComparing Evolutionary Algorithms on Binary Constraint Satisfaction Problems0 aComparing Evolutionary Algorithms on Binary Constraint Satisfact a424--4440 v73 aConstraint handling is not straightforward in evolutionary algorithms (EA) since the usual search operators, mutation and recombination, are `blind' to constraints. Nevertheless, the issue is highly relevant, for many challenging problems involve constraints. Over the last decade numerous EAs for solving constraint satisfaction problems (CSP) have been introduced and studied on various problems. The diversity of approaches and the variety of problems used to study the resulting algorithms prevents a fair and accurate comparison of these algorithms. This paper aligns related work by presenting a concise overview and an extensive performance comparison of all these EAs on a systematically generated test suite of random binary CSPs. The random problem instance generator is based on a theoretical model that fixes deficiencies of models and respective generators that have been formerly used in the Evolutionary Computing (EC) field.10aconstraint satisfaction1 aCraenen, B G W1 aEiben, A E1 aHemert, J I uhttp://ieeexplore.ieee.org/xpl/abs_free.jsp?isNumber=27734&prod=JNL&arnumber=1237162&arSt=+424&ared=+444&arAuthor=+Craenen%2C+B.G.W.%3B++Eiben%2C+A.E.%3B++van+Hemert%2C+J.I.&arNumber=1237162&a_id0=1237161&a_id1=1237162&a_id2=1237163&a_id3=1237164&a_id4=1201144nas a2200157 4500008004100000020001800041245009000059210006900149260001500218300001500233520063400248653002800882653002100910100001600931856003900947 2003 eng d a0-7803-7804-000aEvolving binary constraint satisfaction problem instances that are difficult to solve0 aEvolving binary constraint satisfaction problem instances that a bIEEE Press a1267--12733 aWe present a study on the difficulty of solving binary constraint satisfaction problems where an evolutionary algorithm is used to explore the space of problem instances. By directly altering the structure of problem instances and by evaluating the effort it takes to solve them using a complete algorithm we show that the evolutionary algorithm is able to detect problem instances that are harder to solve than those produced with conventional methods. Results from the search of the evolutionary algorithm confirm conjectures about where the most difficult to solve problem instances can be found with respect to the tightness.10aconstraint satisfaction10aproblem evolving1 aHemert, J I uhttp://research.nesc.ac.uk/node/2300990nas a2200181 4500008004100000245006900041210006600110300001300176520046400189653002800653653002000681100001300701700001300714700001400727700001200741700001600753856003900769 2003 eng d00aA new permutation model for solving the graph k-coloring problem0 anew permutation model for solving the graph kcoloring problem a189--1993 aThis paper describes a novel representation and ordering model, that is aided by an evolutionary algorithm, is used in solving the graph k-coloring. A comparison is made between the new representation and an improved version of the traditional graph coloring technique DSATUR on an extensive list of graph k-coloring problem instances with different properties. The results show that our model outperforms the improved DSATUR on most of the problem instances.10aconstraint satisfaction10agraph colouring1 aJuhos, I1 aTóth, A1 aTezuka, M1 aTann, P1 aHemert, J I uhttp://research.nesc.ac.uk/node/2401068nas a2200193 4500008004100000245013100041210006900172260002800241300001100269520043700280653002800717100001600745700001500761700001600776700001200792700001800804700001300822856003900835 2002 eng d00aComparing Classical Methods for Solving Binary Constraint Satisfaction Problems with State of the Art Evolutionary Computation0 aComparing Classical Methods for Solving Binary Constraint Satisf bSpringer-Verlag, Berlin a81--903 aConstraint Satisfaction Problems form a class of problems that are generally computationally difficult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of binary constraint satisfaction prob-lems. We find that the evolutionary algorithms are less effective than the classical techniques.10aconstraint satisfaction1 aHemert, J I1 aCagnoni, S1 aGottlieb, J1 aHart, E1 aMiddendorf, M1 aRaidl, G uhttp://research.nesc.ac.uk/node/2901378nas a2200229 4500008004100000020001800041245010800059210006900167260002800236300001100264520063400275653002800909653002100937100001600958700001300974700001600987700001801003700001601021700004801037700002401085856003901109 2002 eng d a3-540-44139-500aMeasuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction0 aMeasuring the Searched Space to Guide Efficiency The Principle a bSpringer-Verlag, Berlin a23--323 aIn this paper we present a new tool to measure the efficiency of evolutionary algorithms by storing the whole searched space of a run, a process whereby we gain insight into the number of distinct points in the state space an algorithm has visited as opposed to the number of function evaluations done within the run. This investigation demonstrates a certain inefficiency of the classical mutation operator with mutation-rate 1/l, where l is the dimension of the state space. Furthermore we present a model for predicting this inefficiency and verify it empirically using the new tool on binary constraint satisfaction problems.10aconstraint satisfaction10aresampling ratio1 aHemert, J I1 aBäck, T1 aMerelo, J J1 aPanagiotis, A1 aBeyer, H -G1 aFern{\'a}ndez-Villaca{\~n}as, Jos{\'e}-Luis1 aSchwefel, Hans-Paul uhttp://research.nesc.ac.uk/node/2701437nas a2200217 4500008004100000245006000041210006000101260006300161300001100224490000900235520080200244653002801046653001501074100001201089700001801101700001201119700001601131700001201147700002101159856003901180 2002 eng d00aUse of Evolutionary Algorithms for Telescope Scheduling0 aUse of Evolutionary Algorithms for Telescope Scheduling bThe International Society for Optical Engineering ({SPIE}) a51--610 v47573 aLOFAR, a new radio telescope, will be designed to observe with up to 8 independent beams, thus allowing several simultaneous observations. Scheduling of multiple observations parallel in time, each having their own constraints, requires a more intelligent and flexible scheduling function then operated before.
In support of the LOFAR radio telescope project, and in co-operation with Leiden University, Fokker Space has started a study to investigate the suitability of the use of evolutionary algorithms applied to complex scheduling problems. After a positive familiarisation phase, we now examine the potential use of evolutionary algorithms via a demonstration project. Results of the familiarisation phase, and the first results of the demonstration project are presented in this paper.10aconstraint satisfaction10ascheduling1 aGrim, R1 aJansen, M L M1 aBaan, A1 aHemert, J I1 aWolf, H1 aAnderson, Torben uhttp://research.nesc.ac.uk/node/2801141nas a2200229 4500008004100000020002000041245008800061210006900149260002800218300001100246520046900257653001600726100001700742700001600759700001400775700001700789700001500806700001200821700002200833700001700855856003900872 2001 eng d a9-783540-41899300aAdaptive Genetic Programming Applied to New and Existing Simple Regression Problems0 aAdaptive Genetic Programming Applied to New and Existing Simple bSpringer-Verlag, Berlin a23--353 aIn this paper we continue our study on adaptive genetic pro-gramming. We use Stepwise Adaptation of Weights to boost performance of a genetic programming algorithm on simple symbolic regression problems. We measure the performance of a standard GP and two variants of SAW extensions on two different symbolic regression prob-lems from literature. Also, we propose a model for randomly generating polynomials which we then use to further test all three GP variants.10adata mining1 aEggermont, J1 aHemert, J I1 aMiller, J1 aTomassini, M1 aLanzi, P L1 aRyan, C1 aTettamanzi, A G B1 aLangdon, W B uhttp://research.nesc.ac.uk/node/3601066nas a2200277 4500008004100000245004800041210004500089260004600134300000800180520030500188653002100493100001600514700001800530700001700548700002100565700001400586700001700600700002400617700001600641700001600657700001800673700002100691700001900712700001800731856003900749 2001 eng d00aAn Engineering Approach to Evolutionary Art0 aEngineering Approach to Evolutionary Art bMorgan Kaufmann Publishers, San Francisco a1773 aWe present a general system that evolves art on the Internet. The system runs on a server which enables it to collect information about its usage world wide; its core uses operators and representations from genetic program-ming. We show two types of art that can be evolved using this general system.10aevolutionary art1 aHemert, J I1 aJansen, M L M1 aSpector, Lee1 aGoodman, Erik, D1 aWu, Annie1 aLangdon, W B1 aVoigt, Hans-Michael1 aGen, Mitsuo1 aSen, Sandip1 aDorigo, Marco1 aPezeshk, Shahram1 aGarzon, Max, H1 aBurke, Edmund uhttp://research.nesc.ac.uk/node/3200629nas a2200181 4500008004100000245010400041210006900145260003700214653002800251653001600279100001600295700001900311700002300330700001800353700001800371700001900389856003900408 2001 eng d00aEvolutionary Computation in Constraint Satisfaction and Machine Learning --- An abstract of my PhD.0 aEvolutionary Computation in Constraint Satisfaction and Machine bVrije Universiteit Brussel (VUB)10aconstraint satisfaction10adata mining1 aHemert, J I1 aDefaweux, Anne1 aManderick, Bernard1 aLenearts, Tom1 aParent, Johan1 aRemortel, Piet uhttp://research.nesc.ac.uk/node/3101049nas a2200193 4500008004100000245005200041210004600093260004600139300001100185520049600196653002100692100001600713700002100729700001800750700001600768700001400784700001800798856003900816 2001 eng d00aA ``Futurist'' approach to dynamic environments0 aFuturist approach to dynamic environments bMorgan Kaufmann Publishers, San Francisco a35--383 aThe optimization of dynamic environments has proved to be a difficult area for Evolutionary Algorithms. As standard haploid populations find it difficult to track a moving target, diffKerent schemes have been suggested to improve the situation. We study a novel approach by making use of a meta learner which tries to predict the next state of the environment, i.e. the next value of the goal the individuals have to achieve, by making use of the accumulated knowledge from past performance.10adynamic problems1 aHemert, J I1 aVan Hoyweghen, C1 aLukschandl, E1 aVerbeeck, K1 aBranke, J1 aB{\"a}ck, Th. uhttp://research.nesc.ac.uk/node/3301195nas a2200157 4500008004100000245008200041210006900123260004800192300001300240520067300253653002800926100001600954700001300970700001500983856003900998 2000 eng d00aConstraint Satisfaction Problems and Evolutionary Algorithms: A Reality Check0 aConstraint Satisfaction Problems and Evolutionary Algorithms A R bBNVKI, Dutch and the Belgian AI Association a267--2743 aConstraint satisfaction has been the subject of many studies. Different areas of research have tried to solve all kind of constraint problems. Here we will look at a general model for constraint satisfaction problems in the form of binary constraint satisfaction. The problems generated from this model are studied in the research area of constraint programming and in the research area of evolutionary computation. This paper provides an empirical comparison of two techniques from each area. Basically, this is a check on how well both areas are doing. It turns out that, although evolutionary algorithms are doing well, classic approaches are still more successful.10aconstraint satisfaction1 aHemert, J I1 aBosch, A1 aWeigand, H uhttp://research.nesc.ac.uk/node/3900669nas a2200145 4500008004100000245002600041210002600067260005100093300001100144490000700155520028500162653002100447100001600468856003900484 2000 eng d00aDe Creatieve Computer0 aDe Creatieve Computer bArtifici{\"e}le Intelligentie gebruikers groep a10--180 v133 aHere we show an application that generates images resembling art as it was produced by Mondriaan, a Dutch artist, well known for his minimalistic and pure abstract pieces of art. The current version generates images using a linear chromosome and a recursive function as a decoder.10aevolutionary art1 aHemert, J I uhttp://research.nesc.ac.uk/node/3801078nas a2200181 4500008004100000245008400041210006900125260004800194300001300242520050100255653001600756653002400772100001700796700001600813700001300829700001500842856003900857 2000 eng d00aStepwise Adaptation of Weights for Symbolic Regression with Genetic Programming0 aStepwise Adaptation of Weights for Symbolic Regression with Gene bBNVKI, Dutch and the Belgian AI Association a259--2663 aIn this paper we continue study on the Stepwise Adaptation of Weights (SAW) technique. Previous studies on constraint satisfaction and data clas-sification have indicated that SAW is a promising technique to boost the performance of evolutionary algorithms. Here we use SAW to boost per-formance of a genetic programming algorithm on simple symbolic regression problems. We measure the performance of a standard GP and two variants of SAW extensions on two different symbolic regression problems.10adata mining10agenetic programming1 aEggermont, J1 aHemert, J I1 aBosch, A1 aWeigand, H uhttp://research.nesc.ac.uk/node/4001462nas a2200229 4500008004100000020001800041245005600059210005600115260002800171300001300199520083300212653001601045653002401061100001701085700001501102700001601117700001201133700001401145700001701159700001701176856003901193 1999 eng d a3-540-65899-800aAdapting the Fitness Function in GP for Data Mining0 aAdapting the Fitness Function in GP for Data Mining bSpringer-Verlag, Berlin a195--2043 aIn this paper we describe how the Stepwise Adaptation of Weights (SAW) technique can be applied in genetic programming. The SAW-ing mechanism has been originally developed for and successfully used in EAs for constraint satisfaction problems. Here we identify the very basic underlying ideas behind SAW-ing and point out how it can be used for different types of problems. In particular, SAW-ing is well suited for data mining tasks where the fitness of a candidate solution is composed by `local scores' on data records. We evaluate the power of the SAW-ing mechanism on a number of benchmark classification data sets. The results indicate that extending the GP with the SAW-ing feature increases its performance when different types of misclassifications are not weighted differently, but leads to worse results when they are.10adata mining10agenetic programming1 aEggermont, J1 aEiben, A E1 aHemert, J I1 aPoli, R1 aNordin, P1 aLangdon, W B1 aFogarty, T C uhttp://research.nesc.ac.uk/node/4201096nas a2200205 4500008004100000245006700041210006700108260004800175300001300223520047900236653001900715653001600734653002400750100001700774700001500791700001600806700001400822700001500836856003900851 1999 eng d00aComparing genetic programming variants for data classification0 aComparing genetic programming variants for data classification bBNVKI, Dutch and the Belgian AI Association a253--2543 aThis article is a combined summary of two papers written by the authors. Binary data classification problems (with exactly two disjoint classes) form an important application area of machine learning techniques, in particular genetic programming (GP). In this study we compare a number of different variants of GP applied to such problems whereby we investigate the effect of two significant changes in a fixed GP setup in combination with two different evolutionary models10aclassification10adata mining10agenetic programming1 aEggermont, J1 aEiben, A E1 aHemert, J I1 aPostma, E1 aGyssens, M uhttp://research.nesc.ac.uk/node/4401397nas a2200229 4500008004100000020001800041245007300059210006900132260002800201300001300229520073400242653001900976653001600995653002401011100001701035700001501052700001601067700001401083700001301097700001801110856003901128 1999 eng d a3-540-66332-000aA comparison of genetic programming variants for data classification0 acomparison of genetic programming variants for data classificati bSpringer-Verlag, Berlin a281--2903 aIn this paper we report the results of a comparative study on different variations of genetic programming applied on binary data classification problems. The first genetic programming variant is weighting data records for calculating the classification error and modifying the weights during the run. Hereby the algorithm is defining its own fitness function in an on-line fashion giving higher weights to `hard' records. Another novel feature we study is the atomic representation, where `Booleanization' of data is not performed at the root, but at the leafs of the trees and only Boolean functions are used in the trees' body. As a third aspect we look at generational and steady-state models in combination of both features.10aclassification10adata mining10agenetic programming1 aEggermont, J1 aEiben, A E1 aHemert, J I1 aHand, D J1 aKok, J N1 aBerthold, M R uhttp://research.nesc.ac.uk/node/4300739nas a2200169 4500008004100000245003100041210003100072260004800103300001300151520028500164653002100449100001600470700001500486700001400501700001500515856003900530 1999 eng d00aMondriaan Art by Evolution0 aMondriaan Art by Evolution bBNVKI, Dutch and the Belgian AI Association a291--2923 aHere we show an application that generates images resembling art as it was produced by Mondriaan, a Dutch artist, well known for his minimalistic and pure abstract pieces of art. The current version generates images using a linear chromosome and a recursive function as a decoder.10aevolutionary art1 aHemert, J I1 aEiben, A E1 aPostma, E1 aGyssens, M uhttp://research.nesc.ac.uk/node/4501356nas a2200241 4500008004100000245005500041210005500096260004600151300001500197520069500212653002100907100001500928700001200943700001600955700001500971700001300986700001500999700001601014700001501030700001501045700001501060856003901075 1999 eng d00aPopulation dynamics and emerging features in AEGIS0 aPopulation dynamics and emerging features in AEGIS bMorgan Kaufmann Publishers, San Francisco a1257--12643 aWe describe an empirical investigation within an artificial world, aegis, where a population of animals and plants is evolving. We compare different system setups in search of an `ideal' world that allows a constantly high number of inhabitants for a long period of time. We observe that high responsiveness at individual level (speed of movement) or population level (high fertility) are `ideal'. Furthermore, we investigate the emergence of the so-called mental features of animals determining their social, consumptional and aggressive behaviour. The tests show that being socially oriented is generally advantageous, while agressive behaviour only emerges under specific circumstances.10adynamic problems1 aEiben, A E1 aElia, D1 aHemert, J I1 aBanzhaf, W1 aDaida, J1 aEiben, A E1 aGarzon, M H1 aHonavar, V1 aJakiela, M1 aSmith, R E uhttp://research.nesc.ac.uk/node/4601203nas a2200181 4500008004100000245008000041210006900121260002400190300001300214520065500227653002800882100001500910700001600925700001300941700001400954700001400968856003900982 1999 eng d00aSAW-ing EAs: adapting the fitness function for solving constrained problems0 aSAWing EAs adapting the fitness function for solving constrained bMcGraw-Hill, London a389--4023 aIn this chapter we describe a problem independent method for treating constrain ts in an evolutionary algorithm. Technically, this method amounts to changing the defini tion of the fitness function during a run of an EA, based on feedback from the search pr ocess. Obviously, redefining the fitness function means redefining the problem to be sol ved. On the short term this deceives the algorithm making the fitness values deteriorate , but as experiments clearly indicate, on the long run it is beneficial. We illustrate t he power of the method on different constraint satisfaction problems and point out other application areas of this technique.10aconstraint satisfaction1 aEiben, A E1 aHemert, J I1 aCorne, D1 aDorigo, M1 aGlover, F uhttp://research.nesc.ac.uk/node/4100652nas a2200181 4500008004100000245013500041210006900176260004800245300001300293653002800306100001500334700001600349700001700365700001900382700001700401700001300418856003900431 1998 eng d00aExtended abstract: Solving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function0 aExtended abstract Solving Binary Constraint Satisfaction Problem bBNVKI, Dutch and the Belgian AI Association a299--30110aconstraint satisfaction1 aEiben, A E1 aHemert, J I1 aMarchiori, E1 aSteenbeek, A G1 aPoutré, J A1 aHerik, J uhttp://research.nesc.ac.uk/node/4801452nas a2200181 4500008004100000245005700041210005700098260003100155300001100186490000600197520093500203653002801138653002001166100001501186700001401201700001601215856003901231 1998 eng d00aGraph Coloring with Adaptive Evolutionary Algorithms0 aGraph Coloring with Adaptive Evolutionary Algorithms bKluwer Academic Publishers a25--460 v43 aThis paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EA). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping GA on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping GA and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.10aconstraint satisfaction10agraph colouring1 aEiben, A E1 aHauw, J K1 aHemert, J I uhttp://research.nesc.ac.uk/node/4701161nas a2200217 4500008004100000245011600041210006900157260002800226300001300254520047200267653002800739100001500767700001600782700001700798700001900815700001500834700001800849700001800867700001900885856003900904 1998 eng d00aSolving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function0 aSolving Binary Constraint Satisfaction Problems using Evolutiona bSpringer-Verlag, Berlin a196--2053 aThis paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in binary CSPs.10aconstraint satisfaction1 aEiben, A E1 aHemert, J I1 aMarchiori, E1 aSteenbeek, A G1 aEiben, A E1 aB{\"a}ck, Th.1 aSchoenauer, M1 aSchwefel, H -P uhttp://research.nesc.ac.uk/node/49