Archives for : Uncategorized

Javascript: Travelling Salesman Problem using Genetic Algorithms

<!DOCTYPE html>

<head>
  <title>Traveling Salesman Problem with Genetic Algorithm</title>
  <script src='ga_tsp.js'></script> remove comments
</head>

<body>
    <h1>Genetic Algorithm for Traveling Salesman Problem</h1>
    <br>
    
    NO_CITIES: <input style='position: absolute; left:200px' id='no-cities' value='20'><br>
    MAP_WIDTH: <input style='position: absolute; left:200px' id='map-width' value='400'><br>
    MAP_HEIGHT: <input style='position: absolute; left:200px' id='map-height' value='400'><br>
    POPULATION_SIZE: <input style='position: absolute; left:200px' id='population-size' value='200'><br>
    CROSSOVER_RATE: <input style='position: absolute; left:200px' id='crossover-rate' value='0.8'><br>
    MUTATION_RATE: <input style='position: absolute; left:200px' id='mutation-rate' value='0.05'><br>
    MAX_GENERATIONS: <input style='position: absolute; left:200px' id='max-generations' value='1000000'><br>
    
    <br>
    <button id='start'>Start</button>
    <button id='stop' disabled>Stop</button>
    
    <br>
    <br>
    <canvas id='tsp-canvas' width='400' height='400' style='border:1px solid black'>
    </canvas>
    
    <br>
    <div id='output'>
    </div>
</body>

<script>
	var __message = '';
	function display_message(m)
    {
        __message = m;
        document.getElementById('output').innerHTML = __message;
    }
    
    var NO_CITIES = 20;
    var MAP_WIDTH = 400;
    var MAP_HEIGHT = 400;
    var POPULATION_SIZE = 200;  // use even number
    var CROSSOVER_RATE = 0.8;
    var MUTATION_RATE = 0.05;  // for each new individual
    var MAX_GENERATIONS = 1000000;
    var crossed_generation = [];
    var canvas;
    var ctx;

	var elite = [];
    var cities;
    var population;
    var previous_population_fitness;
    var current_population_fitness;

    var previous_population_fitness;
    var current_population_fitness;
    var improvement;
    var the_best = [];
    var previous_population_best = [];
    var timer;
    var count;
	var low;
    
    document.getElementById('start').addEventListener('click', function() {
        this.disabled = true;
        document.getElementById('stop').disabled = false;
        
        NO_CITIES = document.getElementById('no-cities').value;
        MAP_WIDTH = document.getElementById('map-width').value;
        MAP_HEIGHT = document.getElementById('map-height').value;
        POPULATION_SIZE = document.getElementById('population-size').value;
        CROSSOVER_RATE = document.getElementById('crossover-rate').value;
        MUTATION_RATE = document.getElementById('mutation-rate').value;
        MAX_GENERATIONS = document.getElementById('max-generations').value;
        
        canvas = document.getElementById("tsp-canvas");
        canvas.width = MAP_WIDTH;
        canvas.height = MAP_HEIGHT;
        ctx = canvas.getContext("2d");

        cities = initial_cities(NO_CITIES, MAP_WIDTH, MAP_HEIGHT);  // It is like a map.
                                                                // cities[i].x, cities[i].y
		console.log('start = ')												
		population = get_initial_population(POPULATION_SIZE, cities);  // Each inidividual is an array of city numbers from 0 to NO_CITIES-1.
                                                                 // E.g., population[i] = [2, 5, 12, 56, 22, ...]
	
		low = get_tour_length(population[0],cities);//assign the first population to the best
        the_best = get_best_individual(population, cities);
        draw_individual(the_best, cities, ctx, canvas);

        count = 0;
        timer = setInterval(run, 5);  // every 5 ms
    });
    
    document.getElementById('stop').addEventListener('click', stop);
    function stop() {
        clearInterval(timer);
        this.disabled = true;
        document.getElementById('start').disabled = false;
    };
    
    /*
    * main loop for the genetic algorithm
    */
    
    function run()//dont modify
    {
		
        var next_population = get_next_population(population, cities);
        population = next_population;
        
        the_best = get_best_individual(population, cities);
		
        draw_individual(the_best, cities, ctx, canvas);
        
        if (!(count++ < MAX_GENERATIONS))
            clearInterval(timer);
    }
	
    function get_next_population(population, cities)
    {
        var next_population = [];
		
		//do the whole ga thing here
        for(var i = 0; i < POPULATION_SIZE; i++){
		
			fitness_evaluation(population[i]);
			next_population = population.slice();//transfer to next population array
		}
		
        return next_population;
    }
	
    function get_best_individual(population, cities)     
    {	
		var the_best_individual = [];//transfer to new array
		var temp = 0;
        //check the best distance value
        for(var i = 0; i < POPULATION_SIZE; i++){
			temp = get_tour_length(population[i],cities);
			console.log('trying... ' + i + ' ' + population[i]);
			console.log('Score ' + temp);
			if(temp < low){
				low = temp;
				elite.push(population[i]);
				
				the_best_individual = population[i].slice();
				previous_population_best = population[i].slice();
				console.log('low ' + low);
			}
			
		}
		if(the_best_individual.length > 0){   
			//there was a good one we do nothing since it was chosen already
		}else{
		   //out of this population there was no good individual that beat the last one
		   the_best_individual = previous_population_best;
		}
			
		
        display_message('Generation = ' + count + ' Tour length = ' + Math.floor(low) + '\n' +
		'Best Route = ' + the_best_individual);
        return the_best_individual;
    }
    
    
	function fitness_evaluation(population){
		var lengths = [];
		for (var i = 0; i < POPULATION_SIZE; i++) {
			lengths[i] = get_tour_length(population, cities);
		}
		var sum = 0;
		for (var i = 0; i < POPULATION_SIZE; i++)
			sum += 1 / lengths[i];
		var fitnesses = [];
		
		sum2 = 0;
		for (var i = 0; i < POPULATION_SIZE; i++){
			fitnesses[i] = (1.0 / lengths[i]) /  sum;  // The sum of fitnesses[i]’s = 1
		}
		//select parents
		parent_selection(fitnesses);//includes crossover, and roulette
		mutation();
		
		

	}
	function roulette_selection(fitnesses){
		var r = Math.random();  // r is in [0, 1)
		var sum = 0;//have to sum up the roulette 
		var selected_individual_index;
		
		for (var i = 0; i < POPULATION_SIZE; i++){
			
			if (r <= sum) {
				selected_individual_index = i;
				break;
			}
			sum += fitnesses[i];
			
		}
		
		//else didn't find r, just assume last one
		if(selected_individual_index == null)
			selected_individual_index = POPULATION_SIZE-1; 
			
		//returns the roulette parent
		return selected_individual_index;

	}
	function parent_selection(fitnesses){
		//Select two parent individuals with CROSSOVER_RATE;
		var roulette = [];
		var fitIndex = 0;
		var parent1;
		var parent2;
		var crossover_point1;
		var crossover_point2;
		var r = Math.random();
		var same_parent = false;
		if(r <= 100){
			//I am using a different crossover method: ordered crossover..
			
			//elitism crossover, preserve the good genes to next generation
			var eliteoffset = elite.length;
			for(var i = 0; i < eliteoffset; i++){
				roulette[i] = elite[i];
				//console.log('elite working? = ' + elite[i]);
			}
			//roulette selection to get fit parents
			for(var i = eliteoffset; i < POPULATION_SIZE; i++){
			    fitIndex = roulette_selection(fitnesses);
				roulette[i] = population[fitIndex]; //select the new individuals based on fitness
			}
			
			
			//cross them
			for(var i = 0; i < POPULATION_SIZE-1; i++){
				//parent i crosses with parent i+1 to produce two new chilren
				crossover_point1 = get_crossover_point(NO_CITIES);  // [1, individual_size); Math.floor(Math.random() * (individual_size-1)) + 1
				crossover_point2 = get_crossover_point(NO_CITIES);
				
				//ensure crossover_point1 is always smaller
				if(crossover_point1 > crossover_point2){
					var temp = crossover_point1;
					crossover_point1 = crossover_point2;
					crossover_point2 = temp;
				
				}
				//create the new population with the child
				crossed_generation[i] = cross(roulette[i], roulette[i+1], crossover_point1, crossover_point2);
				
			}
			//last one..
			crossed_generation[POPULATION_SIZE-1] = cross(roulette[crossover_point1], roulette[crossover_point2], crossover_point1, crossover_point2).slice();
			
			//copy children to the population
			for(var i = 0; i < POPULATION_SIZE; i++){
				//ensure only the good generation gets passed on to the next one
				if(get_tour_length(crossed_generation[i],cities) < get_tour_length(population[i],cities))
					population[i] = crossed_generation[i];
			}
		}//else don't cross parents
	}
	
	//ordered crossover
	function cross(parent1, parent2, startPos, endPos){
		var child=[];
		
		for(var i = 0; i < NO_CITIES;i++){
			child[i] = -1;
		}
		// Loop and add the sub tour from parent1 to our child
        for (var i = 0; i < NO_CITIES; i++) {
            // If our start position is less than the end position
            if (i > startPos && i < endPos) {
                child[i] = parent1[i];
            } 
        }
		// Loop through parent2's city tour
        for (var i = 0; i < NO_CITIES; i++) {
            // If child doesn't have the city add it
			if (!containsCity(child, parent2[i])) {
                // Loop to find a spare position in the child's tour
				for (var j = 0; j < NO_CITIES; j++) {
						// Spare position found, add city
						if (child[j] == -1) {
							child[j] = parent2[i];
							break;
						}
				}
			}
        }
		return child;
	}
	function containsCity(individual,city){
		var i = individual.length;
		while (i--) {
		   if (individual[i] === city) {
			   return true;
		   }
		}
		return false;
	}
	
	function mutation(){
	
		for (i = 0; i < POPULATION_SIZE; i++) {
			var r = Math.random();
			//If it is with MUTATION_RATE,
			if(r < MUTATION_RATE){
				//idea 1: move the second to follow the first, shifting rest along
				//shift_city ZzZZZZzz
				
				var a = Math.floor(Math.random() * (NO_CITIES-1))+1; //[0, no-cities-1] 0 - 19;
				var b = Math.floor(Math.random() * (NO_CITIES-1))+1; //[0, no-cities-1] 0 - 19;
				var temp;
				//swap if a > b
				if(a > b){
					temp = a;
					a = b;
					b = temp;
				}
				//console.log(i + ' pop:' + population[i] + ' a = ' + a +' b = ' + b);
				for(var j = a; j < b-1; j++){
					arraymove(population[i],a+1,b);
				}
				//idea 2: swap mutation for permuatations
				//swap
				/*
				var a = Math.floor(Math.random() * (NO_CITIES-1)); //[0, no-cities-1] 0 - 19;
				var b = Math.floor(Math.random() * (NO_CITIES-1)); //[0, no-cities-1] 0 - 19;
				var temp = population[i][a];
				population[i][a] = population[i][b];
				population[i][b] = temp;
				*/
			}//else no mutation
		}
			

	}
	
	function arraymove(arr, fromIndex, toIndex) {
		var element = arr[fromIndex];
		arr.splice(fromIndex, 1);
		arr.splice(toIndex, 0, element);
	}

	function get_tour_length(population, cities){
		var tour = 0;
		var distance = 0;

		for(var i = 0; i < NO_CITIES-1; i++){
			//get distance from city of population i and i+1
			distance = get_distance_between_two_cities(population[i], population[i+1], cities);
			tour += distance;	
		}
		
		//connect the last city to the first one to make an actual tour, not just a path
		lastCity = population[population.length-1];
		firstCity = population[0];
		distance = get_distance_between_two_cities(firstCity, lastCity, cities);
		tour += distance;
		
		return tour;
	}
	
</script>

Output:

Javascript: 8 Puzzle using A star algorithm

<!DOCTYPE html>

<head>
  <title>n-Puzzle Game</title>
  <script src='api.js'></script>
</head>
<body>
    <div id='output'>
    </div>
</body>

<script>
    var __message = '';
    function print_message(m)
    {
        __message += m + '<br>';
        document.getElementById('output').innerHTML = __message;
    }
    
    var SIZE = 3;  // 3 x 3 game board
    var EMPTY_CELL = 0;
    
    var visited_queue = new Queue();
    var expanded_queue = new Queue();// Queue also can be used
    
    var board = initial_board(SIZE);  // get the initial board
    print_message('Initial board = ' + board);
    
	//first time
    var current_board = board;
    var node = {
        id: get_id_of_board(current_board),  // get_id_of_board() should be implemented
        board: current_board, 
        gvalue: 0, 
        hvalue: get_heuristic_value(current_board),  // get_heuristic_value() should be implemented
        fvalue: 0 + get_heuristic_value(current_board), 
        parent: null  // to keep the track of path from the initial board to the goal board
    };
    visited_queue.push(node.id, node.fvalue, node);  // node.fvalue is the priority
	
	
    //expanded_queue.push(id, p, obj)
    while ( !is_final_state(node.board))//if current_board is solved (goal)
    {	
		get_neighbor_node(node);

        //select next node to visit:
        node = expanded_queue.popTheHighestPriorityOne();
		console.log('best value of g ' +node.id);
		current_board = visited_queue.push(node.id,node.fvalue,node);
		
		
    }
    
    /*
    *   Put the boards on the solution path into a queue
    */
    var path = [];
    path.push(node.board);  // node is the goal node.
    while (node.parent != null) {
	   node = node.parent;
       path.push(node.board);
    }
    
    /*
    *   Print the boards from the initial board to the goal board
    */
    var g =0;
    for (var i = path.length-1; i >=0; i--) 
    {   
		print_message('tree level ' + g + ' = '  + path[i]);
		g++;
	}
	print_message('END');
	
	function get_id_of_board(board){
		var str ="";
		for(var i = 0; i < board.length; i++){
			str += board[i];
		}
		console.log(str);
		return parseInt(str);
	}
	
	function put_in_queue(current_node, expanded_board)
    {
        if (!visited_queue.isIn(get_id_of_board(expanded_board)))
		{
            var expanded_node = 
			{
				id: get_id_of_board(expanded_board), 
				board: expanded_board, 
				gvalue: current_node.gvalue + 1, 
				hvalue: get_heuristic_value(expanded_board), 
				fvalue: current_node.gvalue + 1 + get_heuristic_value(expanded_board), 
				parent: current_node
			};
				
            if (expanded_queue.isIn(expanded_node.id)) 
			{
                var temp_node = expanded_queue.get(expanded_node.id);
				console.log(expanded_node.gvalue + '<' + temp_node.gvalue);
                if (expanded_node.gvalue < temp_node.gvalue)
				{
					console.log('a better g value, update');
                    expanded_queue.update(expanded_node.id, expanded_node.fvalue, expanded_node);
					
				}
            }
            else{
				console.log('a new state, add');
                expanded_queue.push(expanded_node.id, expanded_node.fvalue, expanded_node);
			}
		}
    }
	
	function get_neighbor_node(puzzle){
		var empty = puzzle.board.indexOf(0);
		//empty index to decide where it can move
		console.log('index of 0: '+empty);
;		if(empty == 0){
			//first cell 
			put_in_queue(puzzle, exchange(0,1,puzzle.board));
			put_in_queue(puzzle, exchange(0,3,puzzle.board));
		}else if(empty == 1){
			put_in_queue(puzzle, exchange(1,0,puzzle.board));
			put_in_queue(puzzle, exchange(1,4,puzzle.board));
			put_in_queue(puzzle, exchange(1,2,puzzle.board));
		}else if(empty == 2){
			put_in_queue(puzzle, exchange(2,1,puzzle.board));
			put_in_queue(puzzle, exchange(2,5,puzzle.board));
		}else if(empty == 3){
			put_in_queue(puzzle, exchange(3,0,puzzle.board));
			put_in_queue(puzzle, exchange(3,4,puzzle.board));
			put_in_queue(puzzle, exchange(3,6,puzzle.board));
		}else if(empty == 4){
			put_in_queue(puzzle, exchange(4,1,puzzle.board));
			put_in_queue(puzzle, exchange(4,5,puzzle.board));
			put_in_queue(puzzle, exchange(4,7,puzzle.board));
			put_in_queue(puzzle, exchange(4,3,puzzle.board));
		}else if(empty == 5){
			put_in_queue(puzzle, exchange(5,2,puzzle.board));
			put_in_queue(puzzle, exchange(5,8,puzzle.board));
			put_in_queue(puzzle, exchange(5,4,puzzle.board));
		}else if(empty == 6){
			put_in_queue(puzzle, exchange(6,7,puzzle.board));
			put_in_queue(puzzle, exchange(6,3,puzzle.board));
		}else if(empty == 7){
			put_in_queue(puzzle, exchange(7,4,puzzle.board));
			put_in_queue(puzzle, exchange(7,6,puzzle.board));
			put_in_queue(puzzle, exchange(7,8,puzzle.board));
		}else if(empty == 8){
			put_in_queue(puzzle, exchange(8,7,puzzle.board));
			put_in_queue(puzzle, exchange(8,5,puzzle.board));
			
		}
	}
	
	function exchange(i,j,puzzle)//swap tile with EMPTY_CELL
    {
        var temp_board = [];
        for (var x = 0; x < puzzle.length; x++)
            temp_board[x] = puzzle[x];
            
        var temp = temp_board[i];
        temp_board[i] = temp_board[j];
        temp_board[j] = temp;
        
        return temp_board;
    }
    	
	//Manhatan function
	function get_heuristic_value(state) 
	{
		var tboard = state;
		var distance = 0;

		// the heuristic of the Manhatan distance
		for (var i = 0; i < tboard.length; i++)
			if (tboard[i] != EMPTY_CELL) {
				if (tboard[i]-1 != i) {
					var c_row, c_col, t_row, t_col;
					c_row = Math.floor(i / SIZE); c_col = i % SIZE; 
					t_row = Math.floor((tboard[i]-1) / SIZE); t_col = (tboard[i]-1) % SIZE; 
					distance += Math.abs(c_row - t_row) + Math.abs(c_col - t_col);
			}
		}

	return distance;

	}
	
	//check if is goal
	function is_final_state(state) 
	{
	  for (var i = 0; i < SIZE*SIZE-1; i++)  // should be length-1, not length
	    if (state[i]-1 != i)
		  return false;
	  return true;  // 1 2 3 4 ... empty
	}
	
</script>


Output: