# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 3 A MVC Solver Based on MEA--Q-MaeMetaVC
### Bipartite Graph Solving Algorithm
#### 3.3.1 Create a Membrane Structure
```
Input: Population C.MP; Output: population;
1 for \(\forall\) C.M\({}_{i}\) in C.MP do
2 repairIndividual(C.M\({}_{i}\), | C.best | -1);
3 return C.MP;
```
**Algorithm 7**repairPopulation//Population repair algorithm

#### 3.4.3 Implementation of Division and Fusion Operator

The division operator refers to dividing a membrane to form a new one. The fusion operator refers to the combination of two membranes into a new membrane, and the object set of the new one is the union of the object sets of the two membranes. If the utilization of the membrane is improved, the fusion operator will not destroy the fused membrane. Referring to local search, the M membrane of Q-MaeMetaVC will divide an element each time, and the divided element will be placed in the population MP' and then try to fuse the membranes in MP'. As shown in Algorithm 9, each M membrane is executed in parallel. If the M finds an MVC, back up the elements in the M (line 3) and adjust the number of elements (line 4). Afterwards, split an element (line 5) through the division operator (Algorithm 10). Then, add an element (line 6) through the fusion operator (Algorithm 11). ```
Input: population C.MP, number of iterations iterCount, edge extraction times \(bms\_e\), vertex extraction times \(bms\_v\); Output: population C\({}_{i}\).MP; // Each C\({}_{i}\).M\({}_{j}\) membrane is executed in parallel
1\(i=1\); for\(i\leq iterCount\) do
3 while(UCE(C\({}_{i}\).M\({}_{j}\)) == 0) do:
4\({}_{i}\).best\({}_{i}\) = C\({}_{i}\).M\({}_{j}\);
5 repairIndividual(C\({}_{i}\).M\({}_{j}\), | C\({}_{i}\).best\({}_{j}\) | -1);
6 end while
7 Division(C\({}_{i}\).M\({}_{j}\), bms\_e\));
8 Fusion(C\({}_{i}\).M\({}_{j}\), bms\_e\));
9\(i\)++;
10 end for
11 return population C\({}_{i}\).MP;
```
**Algorithm 8**repairIndividual/Individual repair algorithm
```
Input: M membrane, C\({}_{i}\).M\({}_{j}\) membrane, target size targetSize; Output: M membrane;
1 while | C\({}_{i}\).M\({}_{j}\) | > targetSize do
2 v = age > 0 in C\({}_{i}\).M\({}_{j}\) and the vertex with the smallest fitness, when the fitness is the same, select the element with older age;
3 C\({}_{i}\).M\({}_{j}\)-v;
4 end while
5 while | C\({}_{i}\).M\({}_{j}\) | < targetSize do
6 v = age > 0 in V\({}_{i}\)-C\({}_{i}\).M\({}_{j}\) and the vertex with the largest fitness, select the element with older age when the fitness is the same;
7 C\({}_{i}\).M+v;
8 end while
9 return C\({}_{i}\).M\({}_{j}\) membrane;
```
**Algorithm 9**Division and Fusion

#### 3.4.4 Implementation of Division and Fusion Operator

The division operator refers to dividing a membrane to form a new one. The fusion operator refers to the combination of two membranes into a new membrane, and the object set of the new one is the union of the object sets of the two membranes. If the utilization of the membrane is improved, the fusion operator will not destroy the fused membrane. Referring to local search, the M membrane of Q-MaeMetaVC will divide an element each time, and the divided element will be placed in the population MP' and then try to fuse the membranes in MP'. As shown in Algorithm 9, each M membrane is executed in parallel. If the M finds an MVC, back up the elements in the M (line 3) and adjust the number of elements (line 4). Afterwards, split an element (line 5) through the division operator (Algorithm 10). Then, add an element (line 6) through the fusion operator (Algorithm 11). This paper adopts the BMS strategy to divide an element with low fitness in a short time overhead to improve efficiency. Refer to Algorithm 10 for the division operator: when the number of elements in the M membrane is less than _bms_v_, the candidate subset S is all the elements in the M membrane. Otherwise, it is a set composed of _bms_v_ elements extracted from S (line 1); the M membrane will split out an element with the lowest fitness in S and select the older element when the fitness is the same (lines 2-3). The split element will be put into the membrane M' (line 4).