Name
Title | ||
|---|---|---|
Hard test generation for augmenting path maximum flow algorithms using genetic algorithms: Revisited |
Abstract | ||
|---|---|---|
To estimate performance of computer science algorithms reliably, one has to create worst-case execution time tests. For certain algorithms this task can be difficult. To reduce the amount of human effort, authors attempt using search-based optimization techniques, such as genetic algorithms. Our previous paper addressed test generation for several maximum flow algorithms. Genetic algorithms were applied for test generation and showed promising results. However, one of the aspects of maximum flow algorithm implementation was missing in that paper: parallel edges (edges which share source and target vertices) were not merged into one single edge (which is allowed in solving maximum flow problems). In this paper, parallel edge merging is implemented and new results are reported. A surprising fact is shown that fitness functions and choices of genetic operators which were the most efficient in the previous paper are much less efficient in the new setup and vice versa. What is more, the set of maximum flow algorithms, for which significantly better tests are generated, changed completely as well. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/CEC.2015.7257146 | Evolutionary Computation |
Keywords | Field | DocType |
genetic algorithms,program testing,search problems,computer science algorithms,fitness functions,genetic algorithms,genetic operators,hard test generation,parallel edge merging,path maximum flow algorithms,search-based optimization techniques,worst-case execution time tests | Analysis of parallel algorithms,Computer science,Analysis of algorithms,Genetic programming,Artificial intelligence,Quality control and genetic algorithms,Mathematical optimization,Algorithm,Evolutionary computation,Probabilistic analysis of algorithms,Genetic representation,Cultural algorithm,Machine learning | Conference |
Citations | PageRank | References |
2 | 0.44 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxim Buzdalov | 1 | 141 | 25.29 |
| Anatoly Shalyto | 2 | 98 | 20.06 |