NIC Flashcards
Base principle of evolution
Beneficial mutations in children will be carried forward and become widespread in future generations
What are the steps to making a Genetic EA?
Generate Population Calculate fitness of pop Select two parents Apply variation Possibly recombine Reintroduce/replace population
What is a fitness function?
Evaluates how well a candidate solution solves the problem at hand
What is an approximate algorithm?
Delivers solutions in a reasonable time
Finds near-optimal solutions
Cannot guarantee an optimal solution
What is Hillclimbing?
The process of keeping/rejecting mutated candidate solutions depending on if they are better or worse than their previous solution - when graphed this looks like a hill
The issue can be finding local maxima instead of the main hill
What is a neighborhood?
A set of all mutants of a candidate solution
The neighbourhood can be searched using a local search to try to find an improved version of the solution
What are the different types of fitness landscapes?
Unimodal
Plateau
Multimodal
Deceptive
What is a population-based search?
Create a population of possible solutions, rather than just a single solution (as with local search)
Requires a selection method (maybe monte carlo)
What are the features of Genetic Algorithms?
- Generational (new populations generated)
- Steady state (genetic operators are applied n times)
What is the problem with random candidate selection?
Result in little to no evolutionary progress
What is the problem with high pressure candidate selectoin?
You’ll probably get stuck on a local maximum
What is roulette wheel selection?
Probability of getting picked is proportional to the fitness of the solution
What is rank based selection?
Population’s fitnesses are ranked from n to 1, selection probabilities are proportional to the rank
Sometimes a function is applied to rank such as rank^0.5 or rank^2
What is tournament selection?
Select a random subset of pop. Rank the subset. Return the best candidate
Easy and cheap to implement
Avoids superfit and superpoor solutions
What is K-ary encoding?
K is a parameter - when k = 2 its binary encoding, when 3, its ternary etc.
A candidate solution is a list L of numbers ranging from 0 to k-1
How does mutation work in k-ary encoding?
Single gene mutation (choose at random - change to random new value) M-gene mutation (single mutation M times) Swap mutation (choose two genes at random and swap)
What is the 1-point crossover in k-ary recombination?
Pick an index in the list L, take the head of L up to the index of parent 1 and the tail of L from the index of parent 2
Swap these two parts making two children
What is the 2-point crossover in k-ary recombination?
Pick two indexes, swap parts of parents 1 and 2 which are inside and outside of those indices
What is uniform crossover in k-ary recombination?
Make a binary mask of length L filled with randomised 1s and 0s
Apply to parents
Create two children where any 1s in the binary mask swap P1 to P2 and where any 0s in the mask swap P2 to P1
What is direct encoding?
A feature is directly described by one gene
Straightforward genotype to phenotype encoding
Easy to estimate the effects of mutation
Fast interpretation
What is indirect encoding?
Easier to exploit domain knowledge
Possible to encode away undesirable features
Can seriously cut down the size of the search space
Slow interpretation
neighborhoods are highly rugged
What is the best representation for generating random computer programs in chromosomes?
Trees are the best way of achieving this in tandem with fixed rules regarding syntax and which functions can be used with which functions
To mutate a random program, select a random subtree and replace with a random subtree
How do you compute the fitness of a random genetic program?
Counting the number of errors - i.e. how close is its result to the desired result.
What is semantic mutation?
When a child is semantically similar to its parents
What is semantic crossover?
When a child is semantically intermediate to its parents
What is swarm intelligence?
When a collection of animals collectively complete a task together which they’d be unable to complete alone
The ability to perform the task is an emergent property of the swarm
Every element is the same there is no central controller
What are the two main types of Swarm Algorithm?
Ant Colony Optimisation (ACO)
Particle Swarm Optimisation (PSO)
What is stigmergy?
Indirect communication via interaction with the environment
e.g. ants don’t communicate with each other directly they leave pheromone to change the environment
What is semantic stigmergy?
The action of the agent directly related to problem-solving and affects behavior
E.g. an individual may position itself in the environment to influence others
What is sign-based stigmergy?
The action of agent affects the environment not directly related to problem-solving activity
Swarm behaviour emerges from the way individuals communicate through and affect their environment
Ants have highly sophisticated sign-based stigmergy va pheromones
What is a flocking behavior?
Collective movement focusing on coordinated movements (e.g. formation flying)
Flocking requires some form of local interaction
What are the characteristics of flocking?
Rapid directed movement of whole flock Reactivity to predators No collisions Coalescing and splitting of flocks No dedicated leader
What are the flocking mechanisms?
Attraction and repulsion
Self organised coordination based on mimicking neighbor
What are the benefits of flocking?
Energy saving (formation flying allows for drafting)
Dealing with predators
Reduce overall error of system (reduce navigation error)
What is involved in a basic Particle Swarm Optimisation?
Update the positions of all particles based upon their velocity
Velocity calculated by taking current velocity and adding a random multiple of the difference between its current position and it’s best recorded position
What are the main parameters of a PSO?
Swarm size
Neighborhood size
Number of iterations
Acceleration coefficients
What are the applications of a PSO?
Theoretically any task that EAs can be applied to
Design of : aircraft antennae, controllers, circuits etc.
What is a PSO?
Based loosely on principles of swarming
Has simple formula to update positions according to vellocity
Has intuitive set of parameters
What is the purpose of a Multi-Objective Evolutionary Algorithm?
Finding the best tradeoff between multiple factors in a problem
What is a Pareto Front?
A curve of the best solutions consisting of non-dominated points
What are the most desirable characteristics of the Pareto front?
Evenly spaced solutions covering the largest possible area of the front
How does a MO-EA discriminate between multiple objectives?
It uses a ranking approach to discriminate between different sets/fronts of solutions
How do we tell the difference between two MO-EA solutions which are non-dominated?
The use of a Pareto Domination tournament:
Selection of two random solutions a & b and a comparison set c, if a & b are non dominated WRT c then select
How is crowding distance computed in an MO-EA?
For each objective of the MO-EA sort the pop by that objective
Set crowding distance sum to 0
For each pop item (i) add to the sum (i+1)*m - (i-1) *m
What is NSGAII execution?
Process of:
create an initial population (size N)
select, crossover and mutate
create sorted intermediate population with children (size 2N)
sort intermediate pop by crowding distance
split sorted crowding distances into ranks
discard all but first 3 ranks
Why have elitist MO-EAs superseded non-elitist versions?
They execute and converge faster
Require no extra parameters (NSGAII for example)
What is Hebbian Learning?
Learning is essentially the strengthening of neuron pathways
When 2 neurons fire together the connection between the neurons is strengthened
What are the two categories of Neural Network?
Supervised
Unsupervised
What are the differences between supervised and unsupervised neural networks?
Supervised: NN output compared to known result, weightings tweaked based on error from actual result
Unsupervised: network organises itself based on patterns in the data, no external output provided
What is a perceptron?
A set of weighted connectors, the neuron, and the output axion
Uses a threshold/activation function
Learning is the process of tweaking the weights until the output is consistent with the input
How are weights modified in a perceptron?
if output = desired then no change
if output < desired then increase weight by factor
if output > desired then decrease weight by factor
What does a learning rate parameter do in a perceptron?
Learning rate is a factor which adjusts how much a weight is tweaked on each iteration
Sometimes learning rate is tweaked proportionally to the error in a perceptron
What are the limitations of a perceptron?
A problem is only solvable by a perceptron if it is linearly separable into two group
XOR is not solvable by a perceptron for this reason
What is a multi-layer perceptron?
A set of perceptrons which feed into each other
Overcomes limitations of a single perceptron
Basic example is three layer: input, hidden, output§
What is the Feed Forward Algorithm?
Initialises weights and thresholds to small random values
Present input and desired output
Calculate actual output: multiply incoming signal by weight, pass through activation func (sigmoid), pass on output to units in the next layer
What is the Back Propagation Algorithm?
Starts at output layer and works backwards
New weight = old weight + (learning rate * error)
What are the two ways to update weights?
Batch updating - update weights after all patterns have been presented and all errors have been calculated
Online updating - weights are updated after the presentation of each pattern
What is the difference between Symbolic AI and Connectionism?
Symbolic AI grounded in cognitive psychology whereas connectionism grounded in neuroscience
What are the properties of a Neural Network?
Able to relate input variables to the required output
Able to generalize between samples
Shows graceful degradation
What is the difference between classification and regression?
Classification: function learns a class (discrete)
Regression: function learns a value (continuous)
What is graceful degradation?
In regular programs, the removal of a component will likely cause total failure
In NNs removal of neurons will likely reduce performance but not result in overall failure
How does generalization differ from NNs to Symbolic AI?
NNs can learn common patterns in data
Symbolic AI is programmed rather than learned meaning it has to be changed for each implementation and will quickly fail if taken out of environment
How do set up NNs for classification?
Create two datasets: training and testing
Overcome any data representation issues
Work out any discrete categories so that the NN does not become confused
What is underfitting and overfitting?
Underfitting is when nothing is really learned - e.g using too simple a model etc
Overfitting is when too much is learned from the data, i.e. noise is also learned and the model becomes less general as false results will arise from new data
What is the best way to apply a NN to a dynamic problem?
Using a shifting time window on the most recent data to try to predict the future
What are Recurrent Neural Networks?
Similar to Multi Layer Perceptrons however they have links to previous layer allowing for a short term memory
This can be useful for stock market analysis, protein sequence analysis etc as knowledge of previous values can be useful
Generally harder to train
What are cellular automata?
Method of simulating large scale problems on small scale using simple rules affecting local interactions
Automatons are grids of cells with a binary set of states
Each cell has a neighborhood (cells immediately adjacent to them)
State transition rules define how a cell’s state changes over time subject to other cell’s states
What is Conway’s game of life?
A famous example of cellular automata
What are the applications of cellular automata?
Modelling of spatial processes (forest fires, diseases)
Modelling of physical processes (crystal formation)
Modelling biological processes (self-replication)
Solving computational models
Parallel processing architectures
What are fractals?
Geometric shapes that can be subdivided into parts which is exactly or statistically a reduced sized copy of the whole
