1. Provide an algebraic expression, in terms of n, for the size of the phenotypic search space (the number of possible combinations of 4 vertices), for an n-vertex graph. You may assume that n ≥ 4.
The clique problem is finding cliques in a diagram. A clique is a set of vertices that are adjacent to each other. The 4-clique is a set of four knots all connected. So, in this example of the 4-clique problem, we have a graph with 7 vertices. A brute force
1. Provide an algebraic expression, in terms of n, for the size of the phenotypic search space (the number of possible combinations of 4 vertices), for an n-vertex graph. You may assume that n ≥ 4.
2. Explain how to represent the valid genotypes as integer subpermutations and give an example for n=7.
3. If you choose to represent each genotype as a subpermutation, express the size of the genetic search space (the number of possible valid genotypes) with respect to n in an algebraic expression with respect to n. Again, we can assume n ≥ 4.
4. Please compare your answers to questions 1 and 3 above and briefly comment on how this reflects genotype-to-phenotype mapping.
5. Suppose a candidate solution p. where p is a phenotype consisting of four vertices. Suppose that minimum fitness occurs when no pair of vertices in p is connected, and maximum fitness occurs when every pair of vertices in p is connected. Explain, using pseudocode, how the goodness of fit F of p is computed.
6. Suppose you decide to use the swap mutation. Please explain why it's a good or bad idea.
7. Give two reasons why a stopping criterion that stops only if a valid solution is found is not sufficient.
8. Please suggest additional exit criteria to resolve the issue in question 7 above.
Step by step
Solved in 2 steps with 1 images
