Abstract
Most of works on the time complexity analysis of evolutionary algorithms have always focused on some artificial binary problems. The time complexity of the algorithms for combinatorial optimisation has not been well understood. This paper considers the time complexity of an evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximum cardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matching with nearly maximum cardinality in average polynomial time.
| Original language | English |
|---|---|
| Pages (from-to) | 450-458 |
| Number of pages | 9 |
| Journal | Journal of Computer Science and Technology |
| Volume | 19 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - Jul 2004 |
| Externally published | Yes |
Bibliographical note
The work was reported at UK 2002 Workshop on Computational IntelligenceFunding
The work is partially supported by Engineering and Physical Sciences Research Council (GR/R52541/O1) and State Key Lab of Software Engineering at "Wuhan University.
Keywords
- Combinatorial optimisation
- Evolutionary algorithm (EA)
- Maximum matching
- Time complexity