Exam questions Flashcards
When using PSO, it is essential to keep the swarm coherent. Which of the following
statements is true?
A. Both velocities and positions should be restricted.
B. Only positions should be restricted.
C. Positions should be restricted if particles venture outside the initial range.
D. Only velocities should be restricted.
E. Positions should be restricted if the inertia is smaller than 1.
D. Only velocities should be restricted.
Consider the function 𝑓(𝑥1, 𝑥2) = 4𝑥1^2 + 2𝑥2^2 − 𝑥1𝑥2 and let 𝐻 denote the Hessian
matrix. Which of the following statements is true?
A. The eigenvalues of 𝐻 are both negative, so 𝑓 is convex.
B. The eigenvalues of 𝐻 are both positive, so 𝑓 is convex.
C. One eigenvalue of 𝐻 is positive, and one is negative, so 𝑓 is not convex.
D. The eigenvalues of H are both negative, so 𝑓 is not convex.
E. The eigenvalues of 𝐻 are both positive, so 𝑓 is not convex.
B. The eigenvalues of 𝐻 are both positive, so 𝑓 is convex.
Consider a genetic algorithm in which individuals are selected using tournament
selection, with a given value of 𝑝tour and with a tournament size of three. In a
single selection step (selecting one individual from the tournament with three
individuals), what is the probability (p) of selecting the second-best individual.
A. 𝑝 = 𝑝tour^2
B. 𝑝 = (1 − 𝑝tour)𝑝tour
C. 𝑝 = 𝑝tour^3
D. 𝑝 = (1 − 𝑝tour)𝑝tour^2
E. 𝑝 = (1 − 𝑝tour)^2
B. 𝑝 = (1 − 𝑝tour)𝑝tour
Consider a case in which the Lagrange multiplier method is applied to the problem of finding the minima of a continuously differentiable function 𝑓(𝑥1, 𝑥2 ) subject to a continuously differentiable equality constraint ℎ(𝑥1, 𝑥2) = 0, both defined in a bounded region (i.e., such that it can be contained in a disc of radius R, where R is finite). Which of the following statements is true? For the problem at hand, the points found by the Lagrange multiplier method …
A. … contain local minima and maxima, but not any global minima or maxima.
B. … contain local and global minima, but no maximum, neither local nor global.
C. … contain local and global maxima, but no minimum, neither local nor global.
D. … contain local and global optima, both minima and maxima.
E. … contain only global minima and maxima.
D. … contain local and global optima, both minima and maxima.
What are the stationary points of the function 𝑓(𝑥) = 2𝑥^3 − 3𝑥^2 − 12x + 4?
A. The stationary points are x = 4 and x = 12.
B. The stationary points are x = -2 and x = 1.
C. The stationary points are x = -1 and x = 2.
D. The stationary points are x = 3 and x = 6.
E. The stationary points are x = -1 and x = 1.
C. The stationary points are x = -1 and x = 2.
Consider a genetic algorithm with a population of five individuals, with fitness
values 𝐹1 = 1, 𝐹2 = 3, 𝐹3 = 4, 𝐹4 = 6, and 𝐹5 = 10. Assuming that tournament selection is used, with ptour = 0.75, what is the probability (in a single selection step) of selecting individual 2 (whose fitness is equal to 3)?
A. 0.12
B. 0.10
C. 0.18
D. 0.24
E. 0.16
E. 0.16
Consider a binary chromosome in a GA, which has been generated via selection
and crossover, and is then going to be mutated using the standard mutation
procedure, with mutation rate pmut = 1/𝑚, where 𝑚 is the chromosome length.
Which of the following statements is true?
A. The number of genes that undergo mutation will range from 0 to m
B. The number of genes that undergo mutations will range from 0 to m/2
C. Either 0 or 1 gene will undergo mutation
D. Either 0, 1, or 2 genes will undergo mutation
E. Exactly 1 gene will undergo mutation
A. The number of genes that undergo mutation will range from 0 to m
The Ant system (AS) algorithm can be applied in many different problems. Let 𝜏𝑖𝑗
denote the pheromone matrix and 𝜂𝑖𝑗 the visibility matrix. Which of the following
statements is true: For any problem where AS is applied, at the end of a run lasting
a given (finite) number of iterations …
A. … the pheromone matrix is symmetric, whereas the visibility matrix is not.
B. … the visibility matrix is symmetric, whereas the pheromone matrix is not.
C. … the symmetry (or lack thereof) of either matrix depends on the problem.
D. … both the visibility matrix and the pheromone matrix are symmetric.
E. … neither the visibility matrix nor the pheromone matrix is symmetric.
C. … the symmetry (or lack thereof) of either matrix depends on the problem.
Consider a standard genetic algorithm (GA) where either tournament selection (TS) or (standard) roulette-wheel selection (RWS), without fitness ranking, is used, and where the fitness values (f) are in the range [0,1]. Which of the following statements is true? An individual whose fitness is equal to 0 …
A. … can be selected with TS but not with RWS.
B. … can be selected with RWS but not with TS.
C. … cannot be selected with either method.
D. … can be selected with both methods.
E. … can be selected with both methods, but only in the first generation.
A. … can be selected with TS but not with RWS.
Consider a case in which ant system (AS) is being used for solving the travelling
salesperson problem (TSP), and where three nodes remain to be selected to complete the path of a given ant. From the current node, the visibilities of those nodes are 1, 2, and 5, respectively. Moreover, the parameters 𝛼 and 𝛽 are both equal to 1, and the pheromone level (𝜏) is equal to 1 on all edges. What is the probability of selecting the third node (with visibility 5) as the next node?
A. 0
B. 2/17
C. 3/8
D. 5/8
E. 1
D. 5/8
Premature convergence is a common problem in evolutionary algorithms. There are different ways of avoiding this problem, by modifying or extending the various operators used (or their parameters). Consider a genetic algorithm that (before modification) uses tournament selection (TS) and standard operators for crossover and mutation, with typical parameter settings. How can the algorithm be modified in order to prevent premature convergence (assuming that TS is used even after the modification)? Describe two ways for doing so.
Premature convergence can be prevented either by introducing a varying mutation rate (based on the degree of diversity in the population) or by reducing the crossover probability pcross.
Another alternative is to introduce some form of mating restriction (as is done in diffusion models). Using fitness ranking would have been an alternative if roulette-wheel selection were used, but in this case it was stated that tournament solution would be used, thus excluding fitness ranking as an option.
In genetic algorithms, the concept of genes is central. In the biological counterpart, genes serve the purpose of providing the necessary information for generating proteins by means of a process that involves two major steps. Name and describe the two steps.
Transcription and translation.
In transcription, the information in a gene (in the form of a sequence of bases, from the alphabet A, C, G, and T) is read by RNA polymerase, resulting in an mRNA molecule,
containing the same information (albeit coded slightly differently) as the gene.
x
In translation, the mRNA molecule is used as a template when forming a chain
of amino acids (i.e. a protein). Each codon, i.e. a sequence of three bases in
the mRNA molecule, e.g. CAA, encode a particular amino acid. Some codons
encode the start and stop command. Once the stop command has been reached
the amino acid chain is complete.
ACO is based on the cooperative behavior of ants and, in particular, a special form of communication used by ants. Name and describe this form of communication.
Cooperative behavior in ants depends on stigmergy, which is a form of communication relying on (local) modification of the environment: As the ants move, they deposit pheromones (a form of volatile hydrocarbon) that other ants can (and often will) follow.
For TSP, AS generally finds the nearest-neighbour path (from a given start node) very quickly. Assuming that the pheromone level on all edges is equal to some value τ0 > 0, explain clearly why AS easily finds the nearest-neighbour path.
If the pheromones are equal on all edges (as was assumed here), the probability of following a given edge is proportional to η_{ij}^β = (1/dij)^β. Now, since the value of β generally is (at least) 2, it is evident that the probability of going to the nearest node (for which 1/dij is maximal) will be higher than the probability of going to any other node. Thus, it is not unlikely that at least one or a few ants will follow the nearest-neighbour path in the first iteration (or one of the first iterations).
Swarming is a frequent phenomenon in nature. Describe at least two reasons why this phenomenon occurs.
Two reasons for swarming: (i) Protection against predators (safety in numbers) and (ii) efficient food search (for example ants and some bird species).
