蟻群演算法 - 旅行家

by sj82516

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/Faker/3.1.0/faker.min.js"></script>

JavaScript

/*
*  簡單的基因演算法實踐
*  參考內容：http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3
*  題目：旅行家問題
*  Warning：這需要大量運算，所以瀏覽器話卡住一段時間
*/

const CITY_SIZE = 20

function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
    return array;
}

// city
class City {
	constructor(id, name, x, y){
    	this.name = name
        this.id = id
        this.x = x
        this.y = y
    }
}

class Edge {
	constructor(city1_id, city2_id, cost){
    	this.city1_id = city1_id
        this.city2_id = city2_id
        this.cost = cost
    }
}

// tour
class Tour{
	constructor(xRange, yRange, costRange){
        this.xRange = xRange
        this.yRange = yRange
        this.costRange = costRange
        this._cities = []
        this._edges = []
        this.genCity()
        this.genEdge()
    }
    
    calcCostBetweenCity(city1_id, city2_id){
    	if(city2_id < city1_id){
        	let temp = city2_id
        	city2_id = city1_id
            city1_id = temp
        }
        let findedEdge = this._edges.find(e => e.city1_id == city1_id && e.city2_id == city2_id)
        if(findedEdge){
        	return findedEdge.cost
        }
    }
    
    genCity(){
    	for(let i=0; i < CITY_SIZE; i++){
        	let x = Math.floor(Math.random() * this.xRange)
            let y = Math.floor(Math.random() * this.yRange)
        	this._cities.push(new City(i, faker.address.city(), x, y,))
        }
    }
    
    // 預設城市之間必有edge可以相通
    genEdge(){
    	for(let i=0; i < CITY_SIZE; i++){
        	for(let j=i+1; j<CITY_SIZE; j++){
            	let cost = Math.floor(Math.random() * this.costRange)
            	this._edges.push(new Edge(i, j, cost))
            }
        }
    }
    
    getEdgeIndex(start, end){
    	if(start > end){
        	let temp = start
        	start = end
            end = temp
        }
    	return...