Given a graph G=(V,E), a vertex cover is a subset of vertices containing at least one endpoint of every edge. A minimum vertex cover uses the fewest possible vertices; the full set V is always a valid but usually nonminimum cover. section 18.3
Figure 18.19 Three examples of minimum vertex covers on graphs. The thicker circles (red vertices) are the only ones needed to cover all edges for these graphs.
Use the graph examples to distinguish minimum covers, alternative optimal solutions, and covers that fail to cover every edge. section 18.3
A practical solution design follows these decisions:
- Represent each candidate subset as a bit string, with one gene per vertex. section 18.3.2
- Prefer fewer selected vertices, while penalizing every uncovered edge. section 18.3.2
- Use a penalty multiplier greater than 1; the suggested default is 2, so invalid candidates do not appear better merely because they contain fewer vertices. section 18.3.2
- Retain nearly valid candidates because a small mutation may add the missing endpoint and produce a strong cover. section 18.3.2
Camera placement
Model warehouse cross points and dead ends as vertices and alleys as edges. A camera covering incident alleys corresponds to selecting a vertex, so the minimum number of cameras is the minimum vertex cover. section 18.3.1
Listing 18.13 Vertex cover: fitness function
function vertexCoverFitness(graph, chromosome) #1
fitness ← 0 #2
for gene in chromosome do #3
if gene == 1 then #4
fitness ← fitness + 1
for edge in graph.edges do #5
if chromosome[edge.source] == 0
and chromosome[edge.destination] == 0 then #6
fitness ← fitness + 2
return fitness
The fitness function counts selected vertices and adds two for each edge whose endpoints are both unselected. section 18.3.2
