UNIVERSITY OF EDINBURGH
COLLEGE OF SCIENCE AND ENGINEERING
SCHOOL OF INFORMATICS
INFR11161 NATURAL COMPUTING
Wednesday 18 th December 2019
14:30 to 16:30
INSTRUCTIONS TO CANDIDATES
Answer QUESTION 1 and ONE other question.
Question 1 is COMPULSORY. If both QUESTION 2 and
QUESTION 3 are answered, only QUESTION 2 will be marked.
All questions carry equal weight.
CALCULATORS MAY NOT BE USED IN THIS EXAMINATION
MSc Courses
Convener: V.Nagarajan
External Examiners: W.Knottenbelt, M.Dunlop, M.Niranjan, E.Vasilaki
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
1. THIS QUESTION IS COMPULSORY
(a) How does the diversity within a population of solutions affect the performance of a metaheuristic algorithm? [2 marks]
(b) In the search for the global optimum, Simulated Annealing uses cooling
schemes for the statistical temperature. Explain briefly the rationale behind
this procedure. [2 marks]
(c) Assume you are evaluating a novel metaheuristic algorithm. What criteria
would you consider for this task? [3 marks]
(d) The NFL theorem contains a statement about the equivalency of optimisation algorithms. Regarding what aspects would you disagree to this statement? [3 marks]
(e) Compare how the population of particles finds solutions to an optimisation
problem in particle swarm optimisation (PSO) and in differential evolution
(DE). [3 marks]
(f) Discuss an example of how the schema theorem is relevant for the production
of good solution by a genetic algorithm? [2 marks]
(g) Why is the application of metaheuristic algorithms considered to be promising in multi-objective optimisation problems? [2 marks]
(h) How can Genetic Programming (GP) be used in combination with neural
networks? [3 marks]
(i) Is convergence required for termination of a metaheuristic algorithm? [2 marks]
(j) Assume you are participating in a competition where your algorithm will
be tested on random instances of known benchmark functions. How can
you improve your algorithm such that it has a good chance to win the
competition? [3 marks]
Page 1 of 3
2. ANSWER EITHER THIS QUESTION OR QUESTION 3
(a) The building block hypothesis
i. Building blocks are considered to be important for the function of genetic algorithms (GA). Can you give a proof for this? [2 marks]
ii. Discuss and compare the role of building blocks or GA, evolutionary
algorithms (EA) and particle swarm optimisation (PSO) [6 marks]
iii. Discuss an example of a practical problem and design an algorithm
that can benefit from the existence of building blocks, without prior
information which building blocks could be important for the solution.
[4 marks]
(b) Ant colony optimisation
i. Outline the steps of one variant of ant colony optimisation [2 marks]
ii. How can diversity be improved in the algorithm? Can the algorithm
still be convergent? [3 marks]
iii. If the global optimum has been discovered already by an ant in the
ant colony algorithm and only the best ant (in the sense of best-ever)
contributes to the pheromone trail in every time step, what level of
pheromone will accumulate on the optimal path in the long run? [3 marks]
iv. Describe three hybrid metaheuristic algorithms that include the ant
colony algorithm that you have considered in question 2(b)i. Discuss
the suitability of these hybrids in an application. [5 marks]
Page 2 of 3
3. ANSWER EITHER THIS QUESTION OR QUESTION 2
(a) Genetic programming
i. Explain how Genetic Programming (GP) differs from Genetic Algorithms on the level of the standard algorithms. In addition, discuss also
more recent developments of relevant algorithms. [3 marks]
ii. Do you expect that problems such as local minima, inflated complexity
(bloat”), generation of erroneous code, missing or contradictory data
labels would interfere with the performance of GP? [4 marks]
iii. Financial data, such as stock market prices or currency exchange rates,
are notoriously difficult to predict. One reason might be that predictions
are typically used for trades which then have an effect on the data
themselves. What advantage would a GP provide in this context? Try
to explain the details of the algorithm, if these are relevant here. Hint:
There will be no marks for your ideas about financial data, but you may
like to state them briefly, if this helps to make you point clear. [5 marks]
(b) Metaheuristics and hyperheuristics
i. Why can hyperheuristic algorithms be preferable to standard metaheursitic algorithms? [2 marks]
ii. Discuss whether hyperheuristic algorithms are subject to the no-free
lunch theorem. [3 marks]
iii. Is it possible to find strategies for parameter selection in some metaheuritistic algorithms that do not refer to any specific fitness functions?
Explain your answer and give an example of such a strategy. [3 marks]
iv. Design a hyperheuristic algorithm for the problem of the placement of
advertisements on a set of webpages. [5 marks]
Page 3 of 3
AssignmentTutorOnline
- Assignment status: Already Solved By Our Experts
- (USA, AUS, UK & CA PhD. Writers)
- CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS
