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**

**NO PLAGIARISM**– CUSTOM PAPER