# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 4 Example Analysis
(6.3) Division: Since the number of objects in the M membrane is less than the parameter \(bms\_v\) (720), the M\({}_{1}\) membrane splits v\({}_{15}\), an element with the lowest fitness, into M\({}_{1}\)'; similarly, M\({}_{2}\) transfers v\({}_{16}\) to M\({}_{2}\)', and M\({}_{3}\) splits v\({}_{15}\) to M\({}_{3}\)' (all splitted vertices are marked in blue), as shown in Figure 11c. (6.4) Fusion: Since the element v\({}_{16}\) (green mark) in M\({}_{2}\)' has a higher fitness than the element v\({}_{15}\) just split from M\({}_{1}\) (fitness(v\({}_{16}\), M\({}_{1}\)) = 2, fitness(v\({}_{15}\), M\({}_{1}\)) = 1), M\({}_{1}\) will merge a copy of M\({}_{2}\)', while M\({}_{2}\) and M\({}_{3}\) cannot find such elements in MP'. The membrane structure is shown in Figure 11d. (6.5) Fast addition: Since \(\mid\)M\({}_{2}\) \(\mid\) \(\mid\) \(\mid\) best\({}_{2}\) \(\mid\) -1, quickly add elements using the quick_AddOne algorithm. E(M\({}_{2}\)) = \(\mid\)\(<\)v\({}_{2}\), v\({}_{8}\)\(>\), \(<\)v\({}_{15}\)\(>\), \(\mid\) E(M\({}_{2}\)) \(\mid\) \(<\)bms\({}_{e}\), so find the oldest edge \(<\)v\({}_{2}\), v\({}_{8}\)\(>\). Because the two endpoints have the same fitness (fitness(v\({}_{2}\), M\({}_{2}\)) = 1, fitness(v\({}_{8}\), M\({}_{2}\)) = 1), add an older endpoint v\({}_{2}\) (red mark) to M\({}_{2}\). Similarly, add v\({}_{4}\) to M\({}_{3}\). The membrane structure is shown in Figure 11e. At this time, \(\mid\) UCE(M\({}_{1}\)) \(\mid\) = 0, \(\mid\) UCE(M\({}_{3}\)) \(\mid\) = 0, M\({}_{1}\) and M\({}_{3}\) have found a better vertex cover. Then, back up this solution, control the number of elements, and start the next round of iterations (starting from stage 6.3) until the number of iterations reaches _iterCount_. Carry out the synchronization work of the global information. When the termination is reached, enter stage \(\copyright\); otherwise, enter stage (6.6). Assume that on a certain search path, the membrane structure changes as shown in Figure 12a. After jumping out of the division and fusion stage, the termination condition is not reached, and enters the selection and cytolysis stage (as shown in Figure 12). (6.6) Selection and cytolysis: Since the number of membranes is 3, M\({}_{1}\), M\({}_{2}\), and M\({}_{3}\) form a unique group. Fit(M\({}_{1}\)) = \(-\)1, Fit(M\({}_{2}\)) = \(-\)2, Fit(M\({}_{3}\)) = \(-\)4. Because M\({}_{1}\) has the highest fitness, it will break the local optimum through the cytolysis operator; M\({}_{2}\) has the second-best fitness, so it will refer to M\({}_{1}\).bestPart (\(\mid\)v\({}_{20}\)), the set of vertexes with the highest fitness) by selection operator to optimize itself. Similarly, the fitness of M\({}_{3}\) ranks third, so it will refer to M\({}_{1}\).worstPart (\(\mid\)v\({}_{1}\), v\({}_{3}\), v\({}_{4}\)), a set of vertexes with the lowest fitness) to optimize itself by selection operator. M\({}_{1}\) randomly discards four objects {v\({}_{1}\), v\({}_{7}\), v\({}_{9}\), v\({}_{15}\)}; M\({}_{2}\) selects the objects ({v\({}_{20}\)) in M\({}_{1}\).bestPart that are not in M\({}_{2}\) and whose fitness is not 0 one by one, and copies them to the membrane; M\({}_{3}\) selects and copies the objects in M\({}_{1}\).worstPart that are not in M\({}_{3}\) and whose fitness is not 0 to the membrane (add v\({}_{3}\) first, then add v\({}_{1}\)). The membrane structure at this time is shown in Figure 12b. The vertices that change during this process are marked in purple. (6.7) Repair after selection and cytolysis: After the selection and cytolysis phase, each M membrane is repaired by a greedy strategy so that the number of membranes is \(\mid\) best \(\mid\) -1.