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.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

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 algorithm searched all possible combinations of four vertices and found a set that formed a clique. If you want to understand more about it, the problem (and if possible read on). Note that the clique problem is NP-complete, so deterministic search is not practical for large graph sizes. This makes it an ideal candidate for evolutionary exploration. In this problem, we have to assume that we are given the problem of implementing the 4-clique problem as an evolutionary algorithm for an arbitrary graph with an arbitrary number of vertices (an n-vertex graph). If 4 cliques are found, the algorithm succeeds.

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.

Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

Blurred answer
Knowledge Booster
Single source shortest path
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education