# Recent Tutorials

5th December 2013 at 7:42

# Introduction to Artificial Neural Networks - Part 1

This is the first part of a three part introductory tutorial on artificial neural networks. In this first tutorial we will discover what neural networks are, why they're useful for solving certain types of tasks and finally how they work.

## Introduction

Computers are great at solving algorithmic and math problems, but often the world can't easily be defined with a mathematical algorithm. Facial recognition and language processing are a couple of examples of problems that can't easily be quantified into an algorithm, however these tasks are trivial to humans. The key to Artificial Neural Networks is that their design enables them to process information in a similar way to our own biological brains, by drawing inspiration from how our own nervous system functions. This makes them useful tools for solving problems like facial recognition, which our biological brains can do easily.

## How do they work?

First lets take a look at what a biological neuron looks like.

Our brains use extremely large interconnected networks of neurons to process information and model the world we live in. Electrical inputs are passed through this network of neurons which result in an output being produced. In the case of a biological brain this could result in contracting a muscle or signaling your sweat glands to produce sweat. A neuron collects inputs using a structure called dendrites, the neuron effectively sums all of these inputs from the dendrites and if the resulting value is greater than it's firing threshold, the neuron fires. When the neuron fires it sends an electrical impulse through the neuron's axon to it's boutons. These boutons can then be networked to thousands of other neurons via connections called synapses. There are about one hundred billion (100,000,000,000) neurons inside the human brain each with about one thousand synaptic connections. It's effectively the way in which these synapses are wired that give our brains the ability to process information the way they do.

## Modeling Artificial Neurons

Artificial neuron models are at their core simplified models based on biological neurons. This allows them to capture the essence of how a biological neuron functions. We usually refer to these artificial neurons as 'perceptrons'. So now lets take a look at what a perceptron looks like.

As shown in the diagram above a typical perceptron will have many inputs and these inputs are all individually weighted. The perceptron weights can either amplify or deamplify the original input signal. For example, if the input is 1 and the input's weight is 0.2 the input will be decreased to 0.2. These weighted signals are then added together and passed into the activation function. The activation function is used to convert the input into a more useful output. There are many different types of activation function but one of the simplest would be step function. A step function will typically output a 1 if the input is higher than a certain threshold, otherwise it's output will be 0.

Here's an example of how this might work:
Input 1 (x1)  = 0.6
Input 2 (x2)  = 1.0

Weight 1 (w1) = 0.5
Weight 2 (w2) = 0.8

Threshold = 1.0

First we multiple the inputs by their weights and sum them:
x1w1 + x2w2 = (0.6 x 0.5) + (1 x 0.8) = 1.1

Now we compare our input total to the perceptron's activation threshold. In this example the total input (1.1) is higher than the activation threshold (1.0) so the neuron would fire.

## Implementing Artificial Neural Networks

So now you're probably wondering what an artificial neural network looks like and how it uses these artificial neurons to process information. In this tutorial we're going to be looking at feedforward networks and how their design links our perceptron together creating a functioning artificial neural network. Before we begin lets take a look at what a basic feedforward network looks like:

Each input from the input layer is fed up to each node in the hidden layer, and from there to each node on the output layer. We should note that there can be any number of nodes per layer and there are usually multiple hidden layers to pass through before ultimately reaching the output layer. Choosing the right number of nodes and layers is important later on when optimising the neural network to work well a given problem. As you can probably tell from the diagram, it's called a feedforward network because of how the signals are passed through the layers of the neural network in a single direction. These aren't the only type of neural network though. There are also feedback networks where its architecture allows signals to travel in both directions.

## Linear separability

To explain why we usually require a hidden layer to solve our problem, take a look at the following examples:

Notice how the OR function can be separated on the graph with a single straight line, this means the function is “linearly separable” and can be modelled within our neural network without implementing a hidden layer, for example, the OR function can be modeled with a single perceptron like this:

However to model the XOR function we need to use an extra layer:

We call this type of neural network a 'multi layer perceptron'. In almost every case you should only ever need to use one or two hidden layers, however it make take more experimentation to find the optimal amount of nodes for the hidden layer(s).

## To be continued...

So now you should have a basic understanding of some of the typical applications for neural networks and why we use them for these purposes. You should also have a rough understanding of how a basic neural network operates and how it can process data. In the next tutorial we will be looking at ways to construct a neural network and then how we can 'train' it to do the things we want it to do.

11th April 2013 at 15:17

# Simulated Annealing for beginners

Finding an optimal solution for certain optimisation problems can be an incredibly difficult task, often practically impossible. This is because when a problem gets sufficiently large we need to search through an enormous number of possible solutions to find the optimal one. Even with modern computing power there are still often too many possible solutions to consider. In this case because we can't realistically expect to find the optimal one within a sensible length of time, we have to settle for something that's close enough.

An example optimisation problem which usually has a large number of possible solutions would be the traveling salesman problem. In order to find a solution to a problem such as the traveling salesman problem we need to use an algorithm that's able to find a good enough solution in a reasonable amount of time. In a previous tutorial we looked at how we could do this with genetic algorithms, and although genetic algorithms are one way we can find a 'good-enough' solution to the traveling salesman problem, there are other simpler algorithms we can implement that will also find us a close to optimal solution. In this tutorial the algorithm we will be using is, 'simulated annealing'.

If you're not familiar with the traveling salesman problem it might be worth taking a look at my previous tutorial before continuing.

## What is Simulated Annealing?

First, let's look at how simulated annealing works, and why it's good at finding solutions to the traveling salesman problem in particular. The simulated annealing algorithm was originally inspired from the process of annealing in metal work. Annealing involves heating and cooling a material to alter its physical properties due to the changes in its internal structure. As the metal cools its new structure becomes fixed, consequently causing the metal to retain its newly obtained properties. In simulated annealing we keep a temperature variable to simulate this heating process. We initially set it high and then allow it to slowly 'cool' as the algorithm runs. While this temperature variable is high the algorithm will be allowed, with more frequency, to accept solutions that are worse than our current solution. This gives the algorithm the ability to jump out of any local optimums it finds itself in early on in execution. As the temperature is reduced so is the chance of accepting worse solutions, therefore allowing the algorithm to gradually focus in on a area of the search space in which hopefully, a close to optimum solution can be found. This gradual 'cooling' process is what makes the simulated annealing algorithm remarkably effective at finding a close to optimum solution when dealing with large problems which contain numerous local optimums. The nature of the traveling salesman problem makes it a perfect example.

You may be wondering if there is any real advantage to implementing simulated annealing over something like a simple hill climber. Although hill climbers can be surprisingly effective at finding a good solution, they also have a tendency to get stuck in local optimums. As we previously determined, the simulated annealing algorithm is excellent at avoiding this problem and is much better on average at finding an approximate global optimum.

To help better understand let's quickly take a look at why a basic hill climbing algorithm is so prone to getting caught in local optimums.

A hill climber algorithm will simply accept neighbour solutions that are better than the current solution. When the hill climber can't find any better neighbours, it stops.

In the example above we start our hill climber off at the red arrow and it works its way up the hill until it reaches a point where it can't climb any higher without first descending. In this example we can clearly see that it's stuck in a local optimum. If this were a real world problem we wouldn't know how the search space looks so unfortunately we wouldn't be able to tell whether this solution is anywhere close to a global optimum.

Simulated annealing works slightly differently than this and will occasionally accept worse solutions. This characteristic of simulated annealing helps it to jump out of any local optimums it might have otherwise got stuck in.

## Acceptance Function

Let's take a look at how the algorithm decides which solutions to accept so we can better understand how its able to avoid these local optimums.

First we check if the neighbour solution is better than our current solution. If it is, we accept it unconditionally. If however, the neighbour solution isn't better we need to consider a couple of factors. Firstly, how much worse the neighbour solution is; and secondly, how high the current 'temperature' of our system is. At high temperatures the system is more likely accept solutions that are worse.

The math for this is pretty simple:
exp( (solutionEnergy - neighbourEnergy) / temperature )

Basically, the smaller the change in energy (the quality of the solution), and the higher the temperature, the more likely it is for the algorithm to accept the solution.

## Algorithm Overview

So how does the algorithm look? Well, in its most basic implementation it's pretty simple.
• First we need set the initial temperature and create a random initial solution.
• Then we begin looping until our stop condition is met. Usually either the system has sufficiently cooled, or a good-enough solution has been found.
• From here we select a neighbour by making a small change to our current solution.
• We then decide whether to move to that neighbour solution.
• Finally, we decrease the temperature and continue looping

## Temperature Initialisation

For better optimisation, when initialising the temperature variable we should select a temperature that will initially allow for practically any move against the current solution. This gives the algorithm the ability to better explore the entire search space before cooling and settling in a more focused region.

## Example Code

Now let's use what we know to create a basic simulated annealing algorithm, and then apply it to the traveling salesman problem below. We're going to use Java in this tutorial, but the logic should hopefully be simple enough to copy to any language of your choice.

First we need to create a City class that can be used to model the different destinations of our traveling salesman.

City.java
/*
* City.java
* Models a city
*/

package sa;

public class City {
int x;
int y;

// Constructs a randomly placed city
public City(){
this.x = (int)(Math.random()*200);
this.y = (int)(Math.random()*200);
}

// Constructs a city at chosen x, y location
public City(int x, int y){
this.x = x;
this.y = y;
}

// Gets city's x coordinate
public int getX(){
return this.x;
}

// Gets city's y coordinate
public int getY(){
return this.y;
}

// Gets the distance to given city
public double distanceTo(City city){
int xDistance = Math.abs(getX() - city.getX());
int yDistance = Math.abs(getY() - city.getY());
double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );

return distance;
}

@Override
public String toString(){
return getX()+", "+getY();
}
}

Next let's create a class that can keep track of the cities.

TourManager.java
/*
* TourManager.java
* Holds the cities of a tour
*/

package sa;

import java.util.ArrayList;

public class TourManager {

// Holds our cities
private static ArrayList destinationCities = new ArrayList();

public static void addCity(City city) {
}

// Get a city
public static City getCity(int index){
return (City)destinationCities.get(index);
}

// Get the number of destination cities
public static int numberOfCities(){
return destinationCities.size();
}

}

Now to create the class that can model a traveling salesman tour.

Tour.java
/*
* Tour.java
* Stores a candidate tour through all cities
*/

package sa;

import java.util.ArrayList;
import java.util.Collections;

public class Tour{

// Holds our tour of cities
private ArrayList tour = new ArrayList();
// Cache
private int distance = 0;

// Constructs a blank tour
public Tour(){
for (int i = 0; i < TourManager.numberOfCities(); i++) {
}
}

// Constructs a tour from another tour
public Tour(ArrayList tour){
this.tour = (ArrayList) tour.clone();
}

// Returns tour information
public ArrayList getTour(){
}

// Creates a random individual
public void generateIndividual() {
// Loop through all our destination cities and add them to our tour
for (int cityIndex = 0; cityIndex < TourManager.numberOfCities(); cityIndex++) {
setCity(cityIndex, TourManager.getCity(cityIndex));
}
// Randomly reorder the tour
Collections.shuffle(tour);
}

// Gets a city from the tour
public City getCity(int tourPosition) {
return (City)tour.get(tourPosition);
}

// Sets a city in a certain position within a tour
public void setCity(int tourPosition, City city) {
tour.set(tourPosition, city);
// If the tours been altered we need to reset the fitness and distance
distance = 0;
}

// Gets the total distance of the tour
public int getDistance(){
if (distance == 0) {
int tourDistance = 0;
// Loop through our tour's cities
for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) {
// Get city we're traveling from
City fromCity = getCity(cityIndex);
// City we're traveling to
City destinationCity;
// Check we're not on our tour's last city, if we are set our
// tour's final destination city to our starting city
if(cityIndex+1 < tourSize()){
destinationCity = getCity(cityIndex+1);
}
else{
destinationCity = getCity(0);
}
// Get the distance between the two cities
tourDistance += fromCity.distanceTo(destinationCity);
}
distance = tourDistance;
}
return distance;
}

// Get number of cities on our tour
public int tourSize() {
}

@Override
public String toString() {
String geneString = "|";
for (int i = 0; i < tourSize(); i++) {
geneString += getCity(i)+"|";
}
return geneString;
}
}

Finally, let's create our simulated annealing algorithm.

SimulatedAnnealing.java
package sa;

public class SimulatedAnnealing {

// Calculate the acceptance probability
public static double acceptanceProbability(int energy, int newEnergy, double temperature) {
// If the new solution is better, accept it
if (newEnergy < energy) {
return 1.0;
}
// If the new solution is worse, calculate an acceptance probability
return Math.exp((energy - newEnergy) / temperature);
}

public static void main(String[] args) {
// Create and add our cities
City city = new City(60, 200);
City city2 = new City(180, 200);
City city3 = new City(80, 180);
City city4 = new City(140, 180);
City city5 = new City(20, 160);
City city6 = new City(100, 160);
City city7 = new City(200, 160);
City city8 = new City(140, 140);
City city9 = new City(40, 120);
City city10 = new City(100, 120);
City city11 = new City(180, 100);
City city12 = new City(60, 80);
City city13 = new City(120, 80);
City city14 = new City(180, 60);
City city15 = new City(20, 40);
City city16 = new City(100, 40);
City city17 = new City(200, 40);
City city18 = new City(20, 20);
City city19 = new City(60, 20);
City city20 = new City(160, 20);

// Set initial temp
double temp = 10000;

// Cooling rate
double coolingRate = 0.003;

// Initialize intial solution
Tour currentSolution = new Tour();
currentSolution.generateIndividual();

System.out.println("Initial solution distance: " + currentSolution.getDistance());

// Set as current best
Tour best = new Tour(currentSolution.getTour());

// Loop until system has cooled
while (temp > 1) {
// Create new neighbour tour
Tour newSolution = new Tour(currentSolution.getTour());

// Get a random positions in the tour
int tourPos1 = (int) (newSolution.tourSize() * Math.random());
int tourPos2 = (int) (newSolution.tourSize() * Math.random());

// Get the cities at selected positions in the tour
City citySwap1 = newSolution.getCity(tourPos1);
City citySwap2 = newSolution.getCity(tourPos2);

// Swap them
newSolution.setCity(tourPos2, citySwap1);
newSolution.setCity(tourPos1, citySwap2);

// Get energy of solutions
int currentEnergy = currentSolution.getDistance();
int neighbourEnergy = newSolution.getDistance();

// Decide if we should accept the neighbour
if (acceptanceProbability(currentEnergy, neighbourEnergy, temp) > Math.random()) {
currentSolution = new Tour(newSolution.getTour());
}

// Keep track of the best solution found
if (currentSolution.getDistance() < best.getDistance()) {
best = new Tour(currentSolution.getTour());
}

// Cool system
temp *= 1-coolingRate;
}

System.out.println("Final solution distance: " + best.getDistance());
System.out.println("Tour: " + best);
}
}

Output
Initial solution distance: 1966
Final solution distance: 911
Tour: |180, 200|200, 160|140, 140|180, 100|180, 60|200, 40|160, 20|120, 80|100, 40|60, 20|20, 20|20, 40|60, 80|100, 120|40, 120|20, 160|60, 200|80, 180|100, 160|140, 180|

## Conclusion

In this example we were able to more than half the distance of our initial randomly generated route. This hopefully goes to show how handy this relatively simple algorithm is when applied to certain types of optimisation problems.

20th August 2012 at 7:58

# Applying a genetic algorithm to the traveling salesman problem

Imagine you are given a map like the one opposite. It contains a total of 20 different cities and it's your job to visit each of these cities. Before you set off on your journey you'll probably first want to plan a route so you can minimize your travel time. As humans we're pretty good at this, we can easily work out a reasonably good route without needing to do much more than glance at the map. But when we've found a route that we believe is optimal how can we test if it really is the optimal route? Well in short, we can't. Well, we can, but not really. To understand the problem here let's consider there are now just 3 cities to visit instead of the original 20. To get a single route, we would first have to choose from a choice of 3 different starting cities, then we'd have a choice of 2 second cities then there is just 1 final city left to pick to complete our route. This would give us 3 x 2 x 1 different routes in total. That's only 6 in this example, so it's pretty simple to check every route for the shortest if there are just 3 cities. If you're good at maths you may have already realized this is a factorial and factorials grow in size remarkably quick. A factorial of 10 is 3628800 and a factorial of 20 would be 2432902008176640000. So if we wanted to find the shortest route in our 20 city example we would have to test 2432902008176640000 different routes! Even with modern computing power this is unpractical and with bigger problems, it's close to impossible.

## Finding a solution

Although it isn't practical to find the best solution for a problem like ours, we have algorithms that let us discover close to optimum solutions such as the nearest neighbor algorithm and swarm optimization. These algorithms can find 'good-enough' solutions to the travelling salesman problem surprisingly quickly. In this tutorial we will be looking at using a genetic algorithm to find a solution to the travelling sales man problem. If you're not familiar with what a genetic algorithm is and how they work then please have a look at the introductory tutorial below:
Creating a genetic algorithm for beginners

Finding a solution to the travelling salesman problem requires we set up our genetic algorithm in a certain specialized way. For instance, a valid solution would need to represent a route where every city is included at least once and only once. This would mean adjusting our mutation function so it doesn't just add a random city to the route, possibility causing a duplicate. The crossover function will also need to be similarly altered. One type of mutation we could use to prevent us evolving invalid solutions is swap mutation. In swap mutation if we have a set of objects we select two objects at random then simply swap their positions. Because we are only swapping objects around we don't risk causing duplicate objects within our solution.

Now we've dealt with our mutation function we need to sort out our crossover function. One algorithm we could use to produce valid offspring for our next generation is ordered crossover. In this algorithm we select a subset from our first parent, then add that subset to our child. Finally we add the objects which are not yet in our child to our child in the second parent's order.

## Creating our GA

Now let's look at the code of our GA. The first step is to create a class that can encode the tour cities.

### City.java

/*
* City.java
* Models a city
*/

package tsp;

public class City {
int x;
int y;

// Constructs a randomly placed city
public City(){
this.x = (int)(Math.random()*200);
this.y = (int)(Math.random()*200);
}

// Constructs a city at chosen x, y location
public City(int x, int y){
this.x = x;
this.y = y;
}

// Gets city's x coordinate
public int getX(){
return this.x;
}

// Gets city's y coordinate
public int getY(){
return this.y;
}

// Gets the distance to given city
public double distanceTo(City city){
int xDistance = Math.abs(getX() - city.getX());
int yDistance = Math.abs(getY() - city.getY());
double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );

return distance;
}

@Override
public String toString(){
return getX()+", "+getY();
}
}

Now we can create a class that holds all of our destination cities for our tour

### TourManager.java

/*
* TourManager.java
* Holds the cities of a tour
*/

package tsp;

import java.util.ArrayList;

public class TourManager {

// Holds our cities
private static ArrayList destinationCities = new ArrayList();

public static void addCity(City city) {
}

// Get a city
public static City getCity(int index){
return (City)destinationCities.get(index);
}

// Get the number of destination cities
public static int numberOfCities(){
return destinationCities.size();
}
}

Next we need a class that can encode our routes, these are generally referred to as tours so we'll stick to the convention.

### Tour.java

/*
* Tour.java
* Stores a candidate tour
*/

package tsp;

import java.util.ArrayList;
import java.util.Collections;

public class Tour{

// Holds our tour of cities
private ArrayList tour = new ArrayList();
// Cache
private double fitness = 0;
private int distance = 0;

// Constructs a blank tour
public Tour(){
for (int i = 0; i < TourManager.numberOfCities(); i++) {
}
}

public Tour(ArrayList tour){
this.tour = tour;
}

// Creates a random individual
public void generateIndividual() {
// Loop through all our destination cities and add them to our tour
for (int cityIndex = 0; cityIndex < TourManager.numberOfCities(); cityIndex++) {
setCity(cityIndex, TourManager.getCity(cityIndex));
}
// Randomly reorder the tour
Collections.shuffle(tour);
}

// Gets a city from the tour
public City getCity(int tourPosition) {
return (City)tour.get(tourPosition);
}

// Sets a city in a certain position within a tour
public void setCity(int tourPosition, City city) {
tour.set(tourPosition, city);
// If the tours been altered we need to reset the fitness and distance
fitness = 0;
distance = 0;
}

// Gets the tours fitness
public double getFitness() {
if (fitness == 0) {
fitness = 1/(double)getDistance();
}
return fitness;
}

// Gets the total distance of the tour
public int getDistance(){
if (distance == 0) {
int tourDistance = 0;
// Loop through our tour's cities
for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) {
// Get city we're travelling from
City fromCity = getCity(cityIndex);
// City we're travelling to
City destinationCity;
// Check we're not on our tour's last city, if we are set our
// tour's final destination city to our starting city
if(cityIndex+1 < tourSize()){
destinationCity = getCity(cityIndex+1);
}
else{
destinationCity = getCity(0);
}
// Get the distance between the two cities
tourDistance += fromCity.distanceTo(destinationCity);
}
distance = tourDistance;
}
return distance;
}

// Get number of cities on our tour
public int tourSize() {
}

// Check if the tour contains a city
public boolean containsCity(City city){
}

@Override
public String toString() {
String geneString = "|";
for (int i = 0; i < tourSize(); i++) {
geneString += getCity(i)+"|";
}
return geneString;
}
}

We also need to create a class that can hold a population of candidate tours

### Population.java

/*
* Population.java
* Manages a population of candidate tours
*/

package tsp;

public class Population {

// Holds population of tours
Tour[] tours;

// Construct a population
public Population(int populationSize, boolean initialise) {
tours = new Tour[populationSize];
// If we need to initialise a population of tours do so
if (initialise) {
// Loop and create individuals
for (int i = 0; i < populationSize(); i++) {
Tour newTour = new Tour();
newTour.generateIndividual();
saveTour(i, newTour);
}
}
}

// Saves a tour
public void saveTour(int index, Tour tour) {
tours[index] = tour;
}

// Gets a tour from population
public Tour getTour(int index) {
}

// Gets the best tour in the population
public Tour getFittest() {
Tour fittest = tours[0];
// Loop through individuals to find fittest
for (int i = 1; i < populationSize(); i++) {
if (fittest.getFitness() <= getTour(i).getFitness()) {
fittest = getTour(i);
}
}
return fittest;
}

// Gets population size
public int populationSize() {
}
}

Our next class will need to evolve our population of solutions

### GA.java

/*
* GA.java
* Manages algorithms for evolving population
*/

package tsp;

public class GA {

/* GA parameters */
private static final double mutationRate = 0.015;
private static final int tournamentSize = 5;
private static final boolean elitism = true;

// Evolves a population over one generation
public static Population evolvePopulation(Population pop) {
Population newPopulation = new Population(pop.populationSize(), false);

// Keep our best individual if elitism is enabled
int elitismOffset = 0;
if (elitism) {
newPopulation.saveTour(0, pop.getFittest());
elitismOffset = 1;
}

// Crossover population
// Loop over the new population's size and create individuals from
// Current population
for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
// Select parents
Tour parent1 = tournamentSelection(pop);
Tour parent2 = tournamentSelection(pop);
// Crossover parents
Tour child = crossover(parent1, parent2);
// Add child to new population
newPopulation.saveTour(i, child);
}

// Mutate the new population a bit to add some new genetic material
for (int i = elitismOffset; i < newPopulation.populationSize(); i++) {
mutate(newPopulation.getTour(i));
}

return newPopulation;
}

// Applies crossover to a set of parents and creates offspring
public static Tour crossover(Tour parent1, Tour parent2) {
// Create new child tour
Tour child = new Tour();

// Get start and end sub tour positions for parent1's tour
int startPos = (int) (Math.random() * parent1.tourSize());
int endPos = (int) (Math.random() * parent1.tourSize());

// Loop and add the sub tour from parent1 to our child
for (int i = 0; i < child.tourSize(); i++) {
// If our start position is less than the end position
if (startPos < endPos && i > startPos && i < endPos) {
child.setCity(i, parent1.getCity(i));
} // If our start position is larger
else if (startPos > endPos) {
if (!(i < startPos && i > endPos)) {
child.setCity(i, parent1.getCity(i));
}
}
}

// Loop through parent2's city tour
for (int i = 0; i < parent2.tourSize(); i++) {
// If child doesn't have the city add it
if (!child.containsCity(parent2.getCity(i))) {
// Loop to find a spare position in the child's tour
for (int ii = 0; ii < child.tourSize(); ii++) {
// Spare position found, add city
if (child.getCity(ii) == null) {
child.setCity(ii, parent2.getCity(i));
break;
}
}
}
}
return child;
}

// Mutate a tour using swap mutation
private static void mutate(Tour tour) {
// Loop through tour cities
for(int tourPos1=0; tourPos1 < tour.tourSize(); tourPos1++){
// Apply mutation rate
if(Math.random() < mutationRate){
// Get a second random position in the tour
int tourPos2 = (int) (tour.tourSize() * Math.random());

// Get the cities at target position in tour
City city1 = tour.getCity(tourPos1);
City city2 = tour.getCity(tourPos2);

// Swap them around
tour.setCity(tourPos2, city1);
tour.setCity(tourPos1, city2);
}
}
}

// Selects candidate tour for crossover
private static Tour tournamentSelection(Population pop) {
// Create a tournament population
Population tournament = new Population(tournamentSize, false);
// For each place in the tournament get a random candidate tour and
for (int i = 0; i < tournamentSize; i++) {
int randomId = (int) (Math.random() * pop.populationSize());
tournament.saveTour(i, pop.getTour(randomId));
}
// Get the fittest tour
Tour fittest = tournament.getFittest();
return fittest;
}
}

Now we can create our main method, add our cities and evolve a route for our travelling salesman problem.

### TSP_GA.java

/*
* TSP_GA.java
* Create a tour and evolve a solution
*/

package tsp;

public class TSP_GA {

public static void main(String[] args) {

// Create and add our cities
City city = new City(60, 200);
City city2 = new City(180, 200);
City city3 = new City(80, 180);
City city4 = new City(140, 180);
City city5 = new City(20, 160);
City city6 = new City(100, 160);
City city7 = new City(200, 160);
City city8 = new City(140, 140);
City city9 = new City(40, 120);
City city10 = new City(100, 120);
City city11 = new City(180, 100);
City city12 = new City(60, 80);
City city13 = new City(120, 80);
City city14 = new City(180, 60);
City city15 = new City(20, 40);
City city16 = new City(100, 40);
City city17 = new City(200, 40);
City city18 = new City(20, 20);
City city19 = new City(60, 20);
City city20 = new City(160, 20);

// Initialize population
Population pop = new Population(50, true);
System.out.println("Initial distance: " + pop.getFittest().getDistance());

// Evolve population for 100 generations
pop = GA.evolvePopulation(pop);
for (int i = 0; i < 100; i++) {
pop = GA.evolvePopulation(pop);
}

// Print final results
System.out.println("Finished");
System.out.println("Final distance: " + pop.getFittest().getDistance());
System.out.println("Solution:");
System.out.println(pop.getFittest());
}
}

### Output:

Initial distance: 1996
Finished
Final distance: 940
Solution:
|60, 200|20, 160|40, 120|60, 80|20, 40|20, 20|60, 20|100, 40|160, 20|200, 40|180, 60|120, 80|140, 140|180, 100|200, 160|180, 200|140, 180|100, 120|100, 160|80, 180|

As you can see in just 100 generations we were able to find a route just over twice as good as our original and probably pretty close to optimum.

#### Final Results:

If you liked this tutorial you might also enjoy, Simulated Annealing for beginners

5th March 2012 at 7:00

# Node.js for beginners - Callbacks

Hello, if you haven't checked out part 1 yet then go back and take a look. It's good, promise =)

So far we've covered how to do some basic things in Node.js, now we're going to take a look at callbacks and what makes them so useful.

## Why Node.js?

There are many different programming languages available and they all have different strengths and weaknesses. Being able to compare languages and select the best one for your problem is an important step in building scalable and reliable products. Just like every other language Node.js has its strengths and weaknesses, but first let's take a look at when and why we would want to use Node.js.

Strengths:
• Node.js is great if you need to handle loads of concurrent connections with little overhead. If you're going to be creating an application that needs to deal with thousands of requests then Node.js is definitely a good choice.
• It's JavaScript which means anyone who's ever used JavaScript on the client side can transfer their skill to Node.js. It's also built on Google's V8 JavaScript engine so it's pretty fast compared to with languages.
• If you're using JavaScript on both the client and server side it can make programming easier and quicker. For example if you have to validate some form data you can use the same code for the client and server. It's also makes it super easy to transfer data structures back and forth from and client and server.
• You'll impress your PHP scripting buddies!

Now let's take a look at some of the weaknesses.

Weaknesses:
• It's a new language and developers haven't had the time to create strong well tested modules for it just yet. It's worth noting there is also a lack of good IDEs, example code and support when compared to other, older languages. If you run into a problem you're unlikely to get as many search results and well documented solutions as you would for a problem in say, PHP. Although this is a disadvantage today, as Node.js becomes increasingly more popular amongst developers more resources will be available making it progressively quicker and easier to develop in.
• Code can get easily messy and confusing. To make your Node.js code run well you will need to use a lot of anonymous functions and callbacks (more on this in a bit!). These callbacks get increasingly deeper as your application gets larger resulting in the code being more complicated to read and debug.
• It's not the best number cruncher, but then neither is PHP or Ruby!

It's important to know what Node.js' strengths and weaknesses are when deciding if it best fits your applications requirements, but if your code sucks it's not going to make much difference what language you pick! Before we learn what callbacks are and how to implement them into our code, we should first take a quick look at what blocking and non-blocking means, and how it affects the performance of our code.

## Blocking and non-blocking

Blocking is simply when your code can't execute because something else is preventing it from running. This can happen because your application is waiting on another resource, for example, the CPU, network, memory or disk. To better explain how blocking can occur in your code let's take the following example:

var http = require('http');
var url = require('url');

http.createServer(function (request, response) {

if( url.parse(request.url).pathname == '/wait' ){
var startTime = new Date().getTime();
while (new Date().getTime() < startTime + 15000);
response.write('Thanks for waiting!');
}
else{
response.write('Hello!');
}

response.end();
}).listen(8080);

console.log('Server started');

Save this code as “blocking.js” and run it with the command “node blocking.js”.

Here we're running a blocking script, a loop that runs for 15 seconds when the user calls '/wait'. Navigate your browser to http://localhost:8080/wait first, then straight after to http://localhost:8080 you should notice that even though the second script shouldn't be running the blocking script, it still hangs. So why does this happen?

Node.js was designed to only use one thread; this makes it behave differently to a language like PHP, which creates a new thread for every new connection. If we're dealing with all our requests within one thread any code that takes up 5 seconds of the CPU's thread to run will stop our other requests for 5 seconds as well. Because we have to wait for our first request to finish before we can proceed; we call this code “blocking” due to our first request effectively “blocking” our second request from running.

So how can we stop this? Well first we need to make our code non-blocking, and do this we need to make use of callbacks.

## What are callbacks?

If you've had any experience with JavaScript before, there's a good chance you've seen callbacks already. The basic idea is that if we have to do something which could take a long time, let's say we're trying to read a large file, we don't want our node.js server waiting around for the file to be read when it could be dealing with other incoming requests. So to deal with this we tell Node.js to do what it has to do in the background and to call a function when it's finished. This way Node.js can carry on dealing with other requests while it's reading the file, making our code non-blocking. When we have multiple things going on at the same time, like we have in our example, we can also call this code asynchronous.

To help visualise how our non-blocking, asynchronous works, take the following example:

You're driving down a narrow lane in your car but you can't get where you want because there's a car stopped in front while the driver is busy on his phone (our blocking code). Before you can continue, you'll have to wait for the driver in front to finish what he is doing.

Now imagine there is a lay-by in this lane, the driver in front can now happily pull over into the lay-by to use his phone, leaving you room to pass and carry on with your journey. When he's finished on his phone, he can carry along the lane, just as he would have before he pulled over. This is similar to how asynchronous code works; it allows multiple processes to happen at the same time, just how multiple cars can use our lane at the same time.

Lets use our new knowledge to create a non-blocking version of what we just did.

First lets put our blocking code in a new file.

var startTime = new Date().getTime();
while (new Date().getTime() < startTime + 10000);

Save the blocking code as "block.js".
Now lets create our server.

var http = require('http');
var url = require('url');
var cp = require('child_process');

function onRequest(request, response) {
var pathname = url.parse(request.url).pathname;
if( pathname == '/wait' ){
cp.exec('node block.js', myCallback);
}
else{
response.write('Hello!\n');
response.end();
}

console.log('New connection');

function myCallback(){
response.write('Thanks for waiting!\n');
response.end();
}
}
http.createServer(onRequest).listen(8080);
console.log('Server started');

Here we're using the "child process" module so we can create a second Node thread allowing us to run our blocking code in the background. As it's in a new thread our main Node thread can continue on happily serving other incoming requests. We call .exec() function of the child process module to start the new thread and run our blocking script on. The .exec() function takes two parameters, the first is our node command to start our blocking script, and the second is our callback function.  When our .exec() command has finished it runs the callback function, myCallback, and prints, 'Thanks for waiting!'.

To test it, save the code above as "nonblocking.js" then run it with the command, "node nonblocking.js".

You should notice that if you navigate to http://localhost:8080/wait and then to http://localhost:8080 we no longer have to wait for our blocking script to finish. Obviously this is a pointless example because our blocking script isn't doing anything worthwhile. So lets look at a slightly more interesting example of a non-blocking script we can create that uses callbacks.

Luckily for us Node.js comes with many non-blocking, asynchronous methods that we can easily implement into our applications. So let's take a look at how to implement a non-blocking file reader into our code:

var http = require('http');
var fileSystem = require('fs');

http.createServer(function (request, response) {

function writeCallback(data){
response.write(data);
}

function closeCallback(){
response.end();
}

}).listen(8080);

console.log('Server started');

Here we're using the file system module that's built into Node.js. We can call the file system's .createReadStream() method to read our file, and then attach a couple of callback functions onto the 'data' and 'close' events. These functions are then executed when the events are fired.

To try it for yourself save our code above as 'fileReader.js', then create a text file with some text output in, and save it as, "myfile.txt". Now you can run it with the command, "node fileReader.js". Navigate to http://localhost:8080 and you should see your file printed to the page.

## Conclusion

Whenever you have a process that could take a long time to execute, you should always ensure that you're dealing with it in a non-blocking way. When implemented right, good use of callbacks and asynchronous code can provide huge improvements to the speed and scalability of your code.

12th February 2012 at 11:19

# Creating a genetic algorithm for beginners.

## Introduction

A genetic algorithm (GA) is great for finding solutions for complex problems. They're used in engineering to design all sorts of products because they're brilliant at finding just the right materials and the right shapes to create stronger, faster and overall better products. They're also used to design computer algorithms, to schedule tasks, and to solve other optimization problems. Genetic algorithms work by mimicking the way life finds solutions to real world problems using the process of evolution. Although genetic algorithms are capable of solving incredibly complicated problems, they are themselves pretty simple to understand.

The basic idea is:
1. Initialization - Create an initial population, this population is usually generated randomly and can be any size desired, from just a few individuals to thousands.
2. Evaluation - Each member of the population is then evaluated and we calculate a 'fitness' for that individual. The fitness is calculated by how well it fits our desired requirements. These requirements can be simple, 'faster algorithms are better', or more complex, 'stronger materials are better but they shouldn't be too heavy'.
3. Selection - We want to be constantly improving our populations overall fitness, selection helps us discard bad designs and only keep the best individuals.  There are a few different selection methods but the basic idea is the same, make it easier for fitter individuals to be selected for our next generation.
4. Crossover - During crossover we create new individuals by creating crosses of our selected individuals, we call these our parents. The idea is the combination of these parents will create an even 'fitter' offspring for our next population which inherits the best bits of both individuals.
5. Mutation - We need to add a little bit randomness into our populations' genetics otherwise every combination of solutions we can create would be in our initial population.
6. And repeat! - Now we have our next generation we can start again from step two.

## Termination

There are a few reasons why you would want to stop your genetic algorithm from running. For example you might have reached the minimum solution criteria or you've found the optimum solution, sometimes other constraints such as time or money could be the reason for termination.

## Creating a basic binary genetic algorithm

Let's take a look at the classes we're going to create for our GA:
• Population - Manages all individuals of a population
• Individual - Manages an individuals
• Algorithm - Manages our evolution algorithms such as crossover and mutation
• FitnessCalc - Allows us set a candidate solution and calculate an individual's fitness

### Population.java

package simpleGa;

public class Population {

Individual[] individuals;

/*
* Constructors
*/

// Create a population
public Population(int populationSize, boolean initialise) {
individuals = new Individual[populationSize];
// Initialise population
if (initialise) {
// Loop and create individuals
for (int i = 0; i < size(); i++) {
Individual newIndividual = new Individual();
newIndividual.generateIndividual();
saveIndividual(i, newIndividual);
}
}
}

/* Getters */
public Individual getIndividual(int index) {
return individuals[index];
}

public Individual getFittest() {
Individual fittest = individuals[0];
// Loop through individuals to find fittest
for (int i = 0; i < size(); i++) {
if (fittest.getFitness() <= getIndividual(i).getFitness()) {
fittest = getIndividual(i);
}
}
return fittest;
}

/* Public methods */
// Get population size
public int size() {
return individuals.length;
}

// Save individual
public void saveIndividual(int index, Individual indiv) {
individuals[index] = indiv;
}
}

### Individual.java

package simpleGa;

public class Individual {

static int defaultGeneLength = 64;
private byte[] genes = new byte[defaultGeneLength];
// Cache
private int fitness = 0;

// Create a random individual
public void generateIndividual() {
for (int i = 0; i < size(); i++) {
byte gene = (byte) Math.round(Math.random());
genes[i] = gene;
}
}

/* Getters and setters */
// Use this if you want to create individuals with different gene lengths
public static void setDefaultGeneLength(int length) {
defaultGeneLength = length;
}

public byte getGene(int index) {
return genes[index];
}

public void setGene(int index, byte value) {
genes[index] = value;
fitness = 0;
}

/* Public methods */
public int size() {
return genes.length;
}

public int getFitness() {
if (fitness == 0) {
fitness = FitnessCalc.getFitness(this);
}
return fitness;
}

@Override
public String toString() {
String geneString = "";
for (int i = 0; i < size(); i++) {
geneString += getGene(i);
}
return geneString;
}
}

### Algorithm.java

package simpleGa;

public class Algorithm {

/* GA parameters */
private static final double uniformRate = 0.5;
private static final double mutationRate = 0.015;
private static final int tournamentSize = 5;
private static final boolean elitism = true;

/* Public methods */

// Evolve a population
public static Population evolvePopulation(Population pop) {
Population newPopulation = new Population(pop.size(), false);

// Keep our best individual
if (elitism) {
newPopulation.saveIndividual(0, pop.getFittest());
}

// Crossover population
int elitismOffset;
if (elitism) {
elitismOffset = 1;
} else {
elitismOffset = 0;
}
// Loop over the population size and create new individuals with
// crossover
for (int i = elitismOffset; i < pop.size(); i++) {
Individual indiv1 = tournamentSelection(pop);
Individual indiv2 = tournamentSelection(pop);
Individual newIndiv = crossover(indiv1, indiv2);
newPopulation.saveIndividual(i, newIndiv);
}

// Mutate population
for (int i = elitismOffset; i < newPopulation.size(); i++) {
mutate(newPopulation.getIndividual(i));
}

return newPopulation;
}

// Crossover individuals
private static Individual crossover(Individual indiv1, Individual indiv2) {
Individual newSol = new Individual();
// Loop through genes
for (int i = 0; i < indiv1.size(); i++) {
// Crossover
if (Math.random() <= uniformRate) {
newSol.setGene(i, indiv1.getGene(i));
} else {
newSol.setGene(i, indiv2.getGene(i));
}
}
return newSol;
}

// Mutate an individual
private static void mutate(Individual indiv) {
// Loop through genes
for (int i = 0; i < indiv.size(); i++) {
if (Math.random() <= mutationRate) {
// Create random gene
byte gene = (byte) Math.round(Math.random());
indiv.setGene(i, gene);
}
}
}

// Select individuals for crossover
private static Individual tournamentSelection(Population pop) {
// Create a tournament population
Population tournament = new Population(tournamentSize, false);
// For each place in the tournament get a random individual
for (int i = 0; i < tournamentSize; i++) {
int randomId = (int) (Math.random() * pop.size());
tournament.saveIndividual(i, pop.getIndividual(randomId));
}
// Get the fittest
Individual fittest = tournament.getFittest();
return fittest;
}
}

### FitnessCalc.java

package simpleGa;

public class FitnessCalc {

static byte[] solution = new byte[64];

/* Public methods */
// Set a candidate solution as a byte array
public static void setSolution(byte[] newSolution) {
solution = newSolution;
}

// To make it easier we can use this method to set our candidate solution
// with string of 0s and 1s
static void setSolution(String newSolution) {
solution = new byte[newSolution.length()];
// Loop through each character of our string and save it in our byte
// array
for (int i = 0; i < newSolution.length(); i++) {
String character = newSolution.substring(i, i + 1);
if (character.contains("0") || character.contains("1")) {
solution[i] = Byte.parseByte(character);
} else {
solution[i] = 0;
}
}
}

// Calculate inidividuals fittness by comparing it to our candidate solution
static int getFitness(Individual individual) {
int fitness = 0;
// Loop through our individuals genes and compare them to our cadidates
for (int i = 0; i < individual.size() && i < solution.length; i++) {
if (individual.getGene(i) == solution[i]) {
fitness++;
}
}
return fitness;
}

// Get optimum fitness
static int getMaxFitness() {
int maxFitness = solution.length;
return maxFitness;
}
}

Now let's create our main class.

First we need to set a candidate solution (feel free to change this if you want to).
FitnessCalc.setSolution("1111000000000000000000000000000000000000000000000000000000001111");

Now we'll create our initial population, a population of 50 should be fine.
Population myPop = new Population(50,true);

Now we can evolve our population until we reach our optimum fitness
int generationCount = 0;
while(myPop.getFittest().getFitness() < FitnessCalc.getMaxFitness()){
generationCount++;
System.out.println("Generation: "+generationCount+" Fittest: "+myPop.getFittest().getFitness());
myPop = Algorithm.evolvePopulation(myPop);
}
System.out.println("Solution found!");
System.out.println("Generation: "+generationCount);
System.out.println("Genes:");
System.out.println(myPop.getFittest());

Here's the complete code for our main class:

### GA.java

package simpleGa;

public class GA {

public static void main(String[] args) {

// Set a candidate solution
FitnessCalc.setSolution("1111000000000000000000000000000000000000000000000000000000001111");

// Create an initial population
Population myPop = new Population(50, true);

// Evolve our population until we reach an optimum solution
int generationCount = 0;
while (myPop.getFittest().getFitness() < FitnessCalc.getMaxFitness()) {
generationCount++;
System.out.println("Generation: " + generationCount + " Fittest: " + myPop.getFittest().getFitness());
myPop = Algorithm.evolvePopulation(myPop);
}
System.out.println("Solution found!");
System.out.println("Generation: " + generationCount);
System.out.println("Genes:");
System.out.println(myPop.getFittest());

}
}

If everything's right, you should get an output similar to the following:
Generation: 1 Fittest: 40
Generation: 2 Fittest: 43
Generation: 3 Fittest: 50
Generation: 4 Fittest: 50
Generation: 5 Fittest: 52
Generation: 6 Fittest: 59
Generation: 7 Fittest: 59
Generation: 8 Fittest: 61
Generation: 9 Fittest: 61
Generation: 10 Fittest: 61
Generation: 11 Fittest: 63
Generation: 12 Fittest: 63
Generation: 13 Fittest: 63
Generation: 14 Fittest: 63
Generation: 15 Fittest: 63
Solution found!
Generation: 15
Genes:
1111000000000000000000000000000000000000000000000000000000001111

Remember you're output isn't going to be exactly the same as above because of the inherent characteristics of a genetic algorithm.

And there you have it, that's a very basic binary GA. The great thing about a binary GA is that it is easy to represent any problem, although it might not always be the best way of going about it.

Want to apply a genetic algorithm to a real search problem? Check out the following tutorial, applying a genetic algorithm to the traveling salesman problem

2nd February 2012 at 8:27

# Node.js for beginners, part 1 - Hello world, and a bit of fun!

## Introduction

This is the first part in a series of tutorials I want to write on Node.js. I should make it clear that I'm no expert on Node.js, but a good way to check you understand something is to try to explain it to someone else. If you see something that you don't think is quite right please let me know so I can correct the mistake, I'll make sure to give you credit.

I decided to learn Node.js recently due to its increasing popularity. The programming industry moves incredibly fast and it's dangerous to fall behind. Learning new languages is important because if you don't you're likely you'll get left behind and out of a job. Think about all of them flash developers who can't find any work anymore.

So lets begin with a little bit of information (blegh!).

Node.js is a server-side version of JavaScript. That means all the things all them cool things about JavaScript apply here. It also means if you're already quite familiar with JavaScript you're going to have a nice advantage. Node.js is only a few years old and that means even the people that have been working with it from the very beginning have only been using it for a few years. Compare this to how long some people have been writing in C. Being such a new language it also means there aren't many people out there who know it and that means from the simple rule of supply and demand your skill is worth more than your average PHP programmer.

## Creating Hello World

Let's create a hello world. First head over to http://www.nodejs.org and download node.js. When it's installed and ready create a new JavaScript file with the following:

console.log("Hello World");

Now save the file, call it something like "hello.js" and run it with the following command:

node hello.js

So you should get 'Hello World' appear in your terminal. That's all good but I'm sure more importantly you want to know how to print 'Hello World' to new HTTP connections.

Open back up your text editor and type:

var http = require('http');

http.createServer(function (request, response) {
response.end('Hello World\n');
}).listen(8080);

console.log('Server started');

Now save your file and run it with:

node hello.js

Let's take a closer look at our code.
The first line is just getting the http module and saving it to the variable 'http'. The http is included with Node.js to make it easy for us to create Node.js applications.

We can then use the http module to create our http server by calling it's function 'createServer'. This function returns an object and takes a function in a parameter.

We're calling the function 'listen' on our new server object which takes in a numeric value which tells our server what port we want it to listen on. In our case we're using port 8080 which is why we connected our browser to http://localhost:8080

We also create a function and use it as a parameter for the 'createServer' function. This is quite a standard thing to do in JavaScript because functions can be parameters just like variables and objects can be. What's going to happen is that every time our server receives and new connection on port 8080 it's going to run our function we gave it. Interestingly the function we are passing to it is called an anonymous function, and it's called this because we don't give it a name.

You might have noticed our anonymous function takes two parameters, 'request' and 'response'. These parameters get passed to our anonymous function by the HTTP server when it receives a new connection. They are both objects which we can use in our response to the incoming request.

You notice the first thing we do is call the 'writeHead' function this lets us set the HTTP status as the first parameter and send some response headers as a second parameter. We're setting status code 200 which is telling our web browser everything's OK and we're also passing it a 'Content-Type' header which lets our browser know what we're sending it. In our case it's just plain text.

Next we're using the response object to write our 'Hello World'. We do this by simply calling it's write function and passing it our text. At this point we're done with our response so we tell the response object by calling its 'end' function.

## Making our response more interesting

Hello world is pretty boring so let's do something a little more entertaining. We can create a user counter very easily in Node.js and we don't even need to use a database like we might do in PHP.

Create a new JavaScript file called, 'counter.js' and type the following:

var http = require('http');

var userCount = 0;
http.createServer(function (request, response) {
console.log('New connection');
userCount++;

response.write('Hello!\n');
response.end();
}).listen(8080);

console.log('Server started');

Now let's run it with the command,

node counter.js

When you navigate your browser to 'http://localhost:8080' you should now get a view counter.

Note: You might see the counter going up by two for each request, this is because your browser is requesting the favicon from the server (http://localhost:8080/favicon.ico).
You should also see that Node.js is logging each request it receives to the console.

The main thing we're doing here is setting a 'userCount' variable and incrementing on each request. We're then writing the 'userCount' in the response text.

In PHP to do the same thing you would need to save the information to something like a text file or database.

This tutorial is also avalible in Chinese: http://www.laonan.net/blog/63/
Thanks to laonan for the translation

If you liked this tutorial check out part 2, Node.js for beginners - Callbacks

27th November 2011 at 12:31

# Binding a click function to an element with an updating class

If you're dynamically updating an elements class with Javascript you will find your JQuery events binded to that elements class won't work.

JQuery offers a way to easily deal with this problem. If you're using a version of JQuery pre 1.7 the easiest way to do this is with the .live() function. Using the following code will attach the event for elements that match the selection currently and in the future.

\$('.exampleClass.').live('click', function(){
});

Although this will work in JQuery 1.7 onwards, it's not recommended as better methods have been implemented. For example to do the above code in JQuery 1.7 you should use the following code:

\$(document).on("click", '.exampleClass', function(){
});

This code could be used for something similar to the following example:

<html>
<style type="text/css">
.red{
color:#f00;
}
.blue{
color:#00f;
}
</style>
<script src="http://code.jquery.com/jquery-latest.js"></script>

<body>
<script>
\$(document).on("click", ".red, .blue", function(){
\$(this).toggleClass("red blue");
});

</script>

<a class="red">Change color</a>
</body>
</html>