Biomedical subjects

Peter Merz

Publications and source records attributed to Peter Merz.

3 recordsLinked to original sources

PubMed2004

Memetic algorithms for the unconstrained binary quadratic programming problem.

This paper presents a memetic algorithm, a highly effective evolutionary algorithm incorporating local search for solving the unconstrained binary quadratic programming problem (BQP). To justify the approach, a fitness landscape analysis is conducted experimentally for several instances of the BQP. The results of the analysis show that recombination-based variation operators are well suited for the evolutionary algorithms with local search. Therefore, the proposed approach includes--besides a highly effective randomized k-opt local search--a new variation operator that has been tailored specially for the application in the hybrid evolutionary framework. The operator is called innovative variation and is fundamentally different from traditional crossover operators, since new genetic material is included in the offspring which is not contained in one of the parents. The evolutionary heuristic is tested on 35 publicly available BQP instances, and it is shown experimentally that the algorithm is capable of finding best-known solutions to large BQPs in a short time and with a high frequency. In comparison to other approaches for the BQP, the approach appears to be much more effective, particularly for large instances of 1000 or 2500 binary variables.

Algorithms↗

PubMed2004

Advanced fitness landscape analysis and the performance of memetic algorithms.

Memetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used to discuss efficiency and effectiveness for local search and evolutionary meta-search. It is shown that the efficiency of MAs can be increased drastically with the use of domain knowledge. However, effectiveness highly depends on the structure of the problem. As is well-known, identifying this structure is made easier with the notion of fitness landscapes: the local properties of the fitness landscape strongly influence the effectiveness of the local search while the global properties strongly influence the effectiveness of the evolutionary meta-search. This paper also introduces new techniques for analyzing the fitness landscapes of combinatorial problems; these techniques focus on the investigation of random walks in the fitness landscape starting at locally optimal solutions as well as on the escape from the basins of attractions of current local optima. It is shown for NK-landscapes and landscapes of the unconstrained binary quadratic programming problem (BQP) that a random walk to another local optimum can be used to explain the efficiency of recombination in comparison to mutation. Moreover, the paper shows that other aspects like the size of the basins of attractions of local optima are important for the efficiency of MAs and a local search escape analysis is proposed. These simple analysis techniques have several advantages over previously proposed statistical measures and provide valuable insight into the behaviour of MAs on different kinds of landscapes.

Algorithms↗

PubMed2003

Analysis of gene expression profiles: an application of memetic algorithms to the minimum sum-of-squares clustering problem.

Microarrays have become a key technology in experimental molecular biology since they allow monitoring of gene expression for more than 10,000 genes in parallel producing huge amounts of data. In the exploration of transcriptional regulatory networks, an important task is to cluster gene expression data to identify groups of genes with similar patterns and hence similar function. In this paper, memetic algorithms (MAs)-evolutionary algorithms incorporating local search-are proposed for minimum sum-of-squares clustering (MSSC). In a fitness landscape analysis, it is shown that the MSSC problem has correlation structure exploitable by MAs. The proposed MAs are shown to be superior to multi-start k-means as well as five other clustering algorithms from the bioinformatics literature including hierarchical algorithms and self-organizing maps. Although the fitness values of the different clustering solutions lie close together, it is shown that the solutions differ significantly from each other in terms of cluster memberships which is extremely important for the biological interpretation of the clustering results.

Algorithms↗