Implementation of various Algorithms in Java.
These are search algorithms used in traversing tree-type structures.
- Breath first: Starting at a specific node, explore all the leaf nodes at the present depth prior to moving on to the vertices at the next depth level.
- Depth first: Starting at a specific node, explore as far (deep) as possible along each branch before backtracking.
- Iterative deepening depth first: A depth-limited version of Depth First that runs repeatedly with increasing depth limits until the goal is found. Breath First is performed at each level.
- A-Star: Find shortest path from a specified starting point to a specified destination, by finding a path that minimizes f(x) = g(x) + h(x)
These are search algorithms that are used in searching liner-type functions.
- Bruce force (Iterative): Systematically enumerates through all specified intervals on a range. For example, to find the maximum result of a function within a given start and end boundary for x, given a specific interval, each point is evaluated (this will find the global optimum).
- Stochastic (Metaheuristic): Similar to Brute Force, but instead it iterating through all intervals on the range, random points in the range are evaluated for a given number of iterations. The higher the number of iterations, the higher the probability of finding either the local or global optimum).
- Hill climbing (Iterative): Similar to Brute Force, but instead of going through all intervals on the range, it stops once the local optimum is found. This may not however be the global optimum.
- Tabu (Metaheuristic): Evaluates all adjacent options and choose the best one. Once an option has been chosen it's put into the front of the "Tabu" list (FIFO) for a period to prevent it from being re-selected. Unlike hill climbing search, worsening options can be accepted if no improving options is available (provided the option is not in the tabu list).
- Simulated annealing (Metaheuristic): Similar to Stochastic in that it also uses random intervals on the range. Though unlike Stochastic, a worse result can be accepted depending on some probability based on a reducing "temperature".
Note: Metaheuristics sample a set of solutions which is too large to be completely sampled. Metaheuristics do not guarantee that a globally optimal solution, but do supply a sufficiently good solution.
A simple implementation of a genetic algorithm, to match a pre-defined sequence of values, using a random population using cross-overs and mutations of individuals within that population.
Essentially the steps followed are as followed:
- Define a target solution, for example a sequence of 5 numbers ... {1, 2, 3, 4, 5}.
- Generate a population of random individuals, each with a random sequence of numbers (if the target sequence has 5 numbers, then the individuals random sequence will have 5 numbers).
- Establish the fitness of each individual. This is calculated by establishing how many values match between the individuals sequence and the target sequence (in the same position).
- Create a new population by running two "tournaments" between a random subset of the original population and "breed" the winners of the two tournaments, adding the offspring to the new population (based on cross over rate). This is repeated until the new population reaches its capacity.
- Randomly mutate individuals of the new population (based on mutation rate).
- Repeat from 3, until maximum fitness is reached.
Attempts to optimise a problem by iteratively trying to improve a candidate solution with regard to a specific measure of quality. The individual agents are not intelligence, instead global intelligence emerges.
Essentially particle swarm does the follows:
- Agents move around in the search space according to position and velocity.
- Agent movement is influenced by its local best position.
- Agents moves towards best known positions (updated as better positions are found).
A graph whose nodes are positions in the game (edges = moves). Sometimes it's impossible to include every possible outcome (i.e chess), so smaller portions of the tree need to be sampled (guess with help of a heuristic function).
Minimax: Recursive algorithm for choosing the next move in a game. It assumes that both players will play to the best of their ability. Algorithm aims to MAXimise probability of winning ("maximizer") and MINimise probability of opponent winning ("minimizer"). In this algorithm nodes are assigned +1 for a win, 0 for a draw, -1 for a lose and the tree is tackled in a depth-first manner.
The algorithm works quite simply as follows:
- Lets take 3 moves, if I start then I want optimise outcomes for myself as follows: (1) maximise, (2) minimise, (3) maximise.
- Since it's depth-first, level (3) needs to be resolved, hence the max value of the nodes in the branch are selected (+1, 0, -1).
- Once level (3) is resolved, the same is done for level (2), but this time the min value is selected.
- Once level (2) is resolved, the same is done for level (1), but again the max value is taken.
- This leaves us with the best possible move to make, based on the tree.
Sometimes there are branches we should not visit and these can be removed using Alpha-Beta Pruning. This pruning is achieved through adding an alpha and a beta parameter to each node. The alpha is the best explored path to root for the "maximizer" (initialised to -infinity and can only be modified by maximizer nodes) , while beta is the best explored option to the root fo the "minimizer" (initialised to +infinity and can only be modified by minimizer nodes). When the alpha >= beta then we can prune that branch.
A Hopfield network is a basic neural network that learns a specific "pattern". In this network all nodes are connected, hence if there are 8 neurons (nodes), there will be 56 synapses (8 * 8 - 8).
The essential implementation of the network is as follows:
- Convert pattern to a bipolar format (i.e. 1 0 1 0 - > 1 -1 1 -1).
- Create a weight matrix out of the bipolar format pattern (Hebbian weight change, where w(i,j) = a(i) * a(j)).
- Clear diagonals (set to 0, as there are where the neurons).
- The network has "learnt" the pattern.
Inorder to evaluate a pattern against the "learnt" pattern:
- Convert pattern to a bipolar format (i.e. 1 0 1 0 - > 1 -1 1 -1).
- Multiple the bipolar by the weighted matrix and apply a step function to the result (if >= 0 then 1, else -1), to normalize it.
- Compare the result with the bipolar format of the pattern.
- If they match, then the pattern is recognized, else not.
A perceptron is a neural network unit (an artificial neuron) that takes in certain parameters / values, does a computation on them and produces a result. In a single perceptron model, there are no hidden layers, there is only an input layer and an output layer (the desired results). Inputs are transformed to outputs based on weights and compared to the desired output, weights are adjusted accordingly if the desired output is not met (this is referred to as supervised learning).
... image taken from What is a perceptron tutorial.
The essential implementation of the network is as follows:
- Define the input and desired output.
- Train the network to calculate the desired output based on the provided input.
- Initalise the edge weights (there needs to be one edge weight per input node)
- For each output:
- Calculate the output, based on the inputs and corresponding weights.
- Apply a step function to the result to normalize it (calculatedAnswer).
- Work out the error (error = rightAnswer - calculatedAnswer)
- Adjust the weights based on the current weight, input, error and learning rate (weight(n+1) = weight(n) + input * error * learningRate)
- Once the total error rate is zero, the network is trained.
If a problem is linearly separable, then single layer neural networks (no hidden layers) can be used.
Backpropagation works in a very similar to fashion to the Single Layer (Perceptron) Neural Network, expected that there are usually hidden layers between the input and output layers and that the error is "propagated backwards" in order to
- Pass data through model via forward propagation.
- Calculate the loss on output (error = rightAnswer - calculatedAnswer).
- Calculate the gradient of the loss function, using gradient descent, and update the weights propagating backwards.
- gradient = delta * input
- Change in edge weight = learning rate * gradient * momentum * previous change in edge weight from previous iteration
These are problems which have been implemented using some of these algorithms
- Traveling Salesman: Using simulated annealing.
- Tic-Tac-Toe: Using a game tree graph (225,000 leaf nodes for a 3 x 3 game).