Week 1 - Basics

Question 1

Which natural systems can benefit computing?

Answer 1

Evolution

Human-like activity (e.g. brain, immune system)

Collective behaviours (e.g. ant colonies, swarms)

Question 2

Why should natural systems be used as inspiration for new algorithms?

Answer 2

Evolution - created some of the most complex objects we know of (ourselves)

Human-like activity - we solve many seemingly difficult problems

Collective behaviours - a collection of seemingly unintelligent individuals can display intelligence as a part of a collective.

Question 3

What problems can be solved by using nature inspired
computation?

Answer 3

Some tasks that organisms have had to evolve to be good at, are also
tasks we’re interested in in computing:

• Recognising patterns
• Finding shortest paths
• Searching (e.g. for food etc..)

Question 4

Name an advantage of nature-inspired computation, and give 3 examples.

Answer 4

Nature-Inspired techniques tend to produce good results in
reasonable computational time on a vast array of real-world
problems

Examples:

• Evolutionary algorithms are able to optimise complex systems on
  relatively modest hardware – generally better than classical
  optimisation methods.
• Artificial neural networks are generally more successful than the
  classical methods for pattern recognition.
• Artificial immune system methods are better at spotting potential
  threats than classical rule-based monitoring methods.

Question 5

Name 6 application areas of nature-inspired computation.

Answer 5

1. Planning (Routing, scheduling, packing)
2. Design (Electronic circuits, neural networks, structure design)
3. Simulation (Model economic interactions of competing firms in a market)
4. Identification (Fit a function to medical data to predict future values)
5. Control (Design a controller for gas turbine engine, design control system for mobile robots)
6. Classification (Game playing, diagnosis of heart disease, detecting SPAM)

Question 6

What are the 3 basic steps of EAs?

Answer 6

Selection, variation, population update.

Question 7

Give some examples of uses for EAs.

Answer 7

Scheduling university lecture timetables.

Pipe network designs for delivering water.

Antenna designs within given requirements.

A formula that best fits a curve.

Placement strategy for mobile phone masts.

Finding the most efficient orbits for satellites.

Strategy for flying a fighter aircraft.

Finding the most accurate neural network for a data mining or control problem.

Finding the best treatment plan (beam shapes and angles) for radiotherapy cancer treatment.

Question 8

What is optimisation?

Answer 8

Trying to find the best solution (usually in a short time) to a given problem. S is the set of possible solutions, which may be small or large or infinitely large.

Question 9

What is a fitness function?

Answer 9

Every candidate solution s in S can be given a score, or a “fitness”, by a so-called fitness function. We usually write f(s) to indicate the fitness of solution s. We want to find the s in S which has the best score. The fitness function determines how “good” a solution is.

Question 10

What is an exhaustive search?

Answer 10

Generate every possible solution, compute its fitness, and hence discover which is best (aka enumeration).

Question 11

What is an Exact Algorithm?

Answer 11

An algorithm that can solve a problem, guaranteeing to find the best answer.

Question 12

Describe problems with polynomial complexity.

Answer 12

These are called tractable, and easy problems. Fast algorithms are known which provide the best solution. Pairwise alignment of vectors is one such problem. Sorting is another.

Question 13

Describe problems with exponential complexity.

Answer 13

These are called intractable, and hard problems. The fastest known algorithm which exactly solves it is usually not significantly faster than exhaustive search. An exponential curve always takes over a polynomial one.

Question 14

What is Prim’s algorithm?

Answer 14

Start with empty tree (no edges)

Repeat: choose cheapest edge which feasibly extends the tree.

Until: n-1 edges have been chosen.

Question 15

What do approximate algorithms do?

Answer 15

Deliver solutions in reasonable time.

Try to find pretty good (`near optimal’) solutions, and often get optimal ones.

Do not (cannot) guarantee that they have delivered the optimal solution.

Question 16

Describe generalisation, connectionism and graceful degradation.

Answer 16

Connectionism:
Connectionism refers to the computational paradigm or approach in neural networks that emphasizes the importance of interconnected units or nodes. In connectionist models, information processing occurs through the activation and propagation of signals across interconnected nodes. These nodes, often referred to as artificial neurons or units, perform simple computations and communicate with each other through weighted connections.

Graceful Degradation:
Graceful degradation refers to the ability of a neural network or a system to maintain a certain level of functionality or performance even when faced with partial damage, failures, or missing information. In the context of neural networks, graceful degradation implies that the network can continue to provide useful outputs or responses even when some of its units or connections are disrupted or compromised.

Generalizability:
Generalizability refers to the ability of a trained neural network or model to perform well on unseen or new inputs that are different from the ones it was trained on. A neural network with good generalizability can effectively generalize the patterns and knowledge learned from the training data to make accurate predictions or classifications on new, unseen data.