js 基因演算法找八皇后

 

const userInputNum = process.argv[2]

//100 皇后跑不太出來
//50 皇后有機會
const population = 100
const numOfQueen = userInputNum
let geneList = []
let counterArr = []

geneList = initGeneList(population, numOfQueen)
let counter = 1
while (true) {

    const currentBest = geneList.reduce((minItem, current) => {
        return current.total < minItem.total ? current : minItem;
    }, geneList[0])


    if (counter % 100 === 0) {
        console.log(`目前最佳衝突數 ${currentBest.total} 狀態 ${currentBest.simple.join(' ')}`)
        console.log(counter)
        counterArr.push(counter)
    }

    let ans = geneList.filter(item => item.total === 0)
    if (ans.length > 0) {
        console.log(`第 ${counter} 代找到最佳解`)
        console.log(ans)
        // console.log('node index.js ' + `${ans[0].simple.length}` + ' ' + `'${ans[0].simple.join(' ')}'`)
        console.log('ans: ' + `'${ans[0].simple.join(' ')}'`)

        let queens = getQueens(ans[0].simple)

        //初始化棋盤
        let board = initEmptyBoard(ans[0].simple.length)


        //放入皇后
        board = fillQueen(board, ans[0].simple)
        printBoard(board)

        return
    }

    //陷入 local optima
    //只保留前 N 名的基因, 然後重新殺了所有個體
    if (counterArr.length >= 2) {
        let top10Percent = population * 0.1
        geneList = createNext(population, geneList).slice(0, top10Percent)
        let newGeneList = initGeneList(population, numOfQueen).slice(population * 0.1, population)
        geneList = geneList.concat(newGeneList)
        counterArr = []
    } else {
        geneList = createNext(population, geneList)
    }


    geneList = createNext(population, geneList)

    counter++
}


function initGeneList(population, numOfQueen) {
    let geneList = []
    for (let i = 0; i < population; i++) {
        let current = initialState(numOfQueen)
        let emptyBoard = initEmptyBoard(current.length)
        let queens = getQueens(current)
        let board = fillQueen(emptyBoard, current)
        let currentScore = calcResult(board, queens)
        geneList.push(currentScore)
    }

    //排序
    geneList.sort((a, b) => a.total - b.total)

    return geneList
}

function crossover(parentA, parentB) {
    const numOfQueen = parentA.simple.length
    let childGene = []

    //隨機選父母基因
    for (let i = 0; i < numOfQueen; i++) {
        if (Math.random() < 0.5) childGene.push(parentA.simple[i])
        else childGene.push(parentB.simple[i])
    }

    return childGene
}



function createNext(population, geneList) {
    //前 K% 進入下一代
    let topK = Math.ceil(population * 0.1)

    //存活者
    let survivor = geneList.slice(0, topK)

    let lastNPercent = geneList.slice(population * 0.5)


    let nextGeneList = []

    //產生下一代
    for (let i = 0; i < population - topK; i++) {
        //隨機選兩個人 包含保證進入的存活者
        //菁英父母

        let a = Math.floor(Math.random() * survivor.length)

        //後段父母
        let b = Math.floor(Math.random() * lastNPercent.length)

        let parentA = survivor[a]
        let parentB = lastNPercent[b]

        let mutationRate = 0.2

        //crossover
        let childGene = crossover(parentA, parentB)


        //mutation 突變率越大越隨機
        //自然界千分之三突變率太低
        if (Math.random() < mutationRate) {
            //更隨機一點突變
            for (let m = 0; m < 10; m++)
                childGene = mutation(childGene)
        }

        let emptyBoard = initEmptyBoard(childGene.length)
        let queens = getQueens(childGene)
        let board = fillQueen(emptyBoard, childGene)
        let child = calcResult(board, queens)
        nextGeneList.push(child)
    }
    nextGeneList = nextGeneList.concat(survivor)
    nextGeneList.sort((a, b) => a.total - b.total)

    return nextGeneList
}



function mutation(current) {
    // console.log('randomSuccessor', current)
    let pos = Math.floor(Math.random() * current.length)
    while (true) {
        let newPosY = Math.floor(Math.random() * current.length)
        if (current[pos] !== newPosY) {
            let result = [...current]
            result[pos] = newPosY
            return result
        }
    }
}


//亂數建立皇后在棋盤位置的 array
function initialState(num) {
    let result = []
    for (let i = 0; i < num; i++) {
        let pos = Math.floor(Math.random() * num)
        result.push(pos)
    }
    return result
}


/** 計算結果*/
function calcResult(board, queens) {
    let result = []
    let total = 0
    for (let i = 0; i < queens.length; i++) {
        let queen = queens[i]
        let count = scan(queen, board)
        result.push({ x: queen.x, y: queen.y, count: count })
        // console.log(`queen:(${queen.x},${queen.y})-${count}次`)
        total += count
    }

    // console.log(`共:${total}次`)

    return { 'board': result, 'total': total, 'simple': result.map(item => item.y) }

    // return total
}

/**印出棋盤 */
function printBoard(board) {
    for (let y = 0; y < board.length; y++) {
        let str = ''
        for (let x = 0; x < board.length; x++) {
            str += board[y][x] + ' '
        }
        console.log(str)
    }
}


/**組合所有掃描的函數 */
function scan(queen, board) {
    let count = 0
    count += scanRow(queen, board)

    //左上至右下
    count += scanToTopLeft(queen, board)
    count += scanToBottomRight(queen, board)

    //右上至左下
    count += scanToTopRight(queen, board)
    count += scanToBottomLeft(queen, board)

    return count
}

/**掃描目前棋子到左下 */
function scanToBottomLeft(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x -= 1
    y += 1

    while (true) {
        if (x < 0 || y >= board.length) break
        if (board[y][x] === 'Q') count++
        x -= 1
        y += 1
    }
    return count
}

/**掃描目前棋子到右上 */
function scanToTopRight(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x += 1
    y -= 1

    while (true) {
        if (x >= board.length || y < 0) break
        if (board[y][x] === 'Q') count++
        x += 1
        y -= 1
    }
    return count
}

/**掃描目前棋子到左上 */
function scanToTopLeft(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x -= 1
    y -= 1

    while (true) {
        if (x < 0 || y < 0) break
        if (board[y][x] === 'Q') count++
        x -= 1
        y -= 1
    }
    return count
}


/**掃描目前棋子到右下 */
function scanToBottomRight(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x += 1
    y += 1

    while (true) {
        if (x >= board.length || y >= board.length) break
        if (board[y][x] === 'Q') count++
        x += 1
        y += 1
    }
    return count
}

/**掃描整個橫向 */
function scanRow(queen, board) {
    let num = board.length
    let y = queen.y
    let count = 0
    for (let x = 0; x < num; x++) {
        if (x === queen.x) continue
        if (board[y][x] === 'Q') count++
    }
    return count
}

/**簡化取得皇后 xy 位置 */
function getQueens(initQueenPos) {
    let queens = []
    for (let i = 0; i < initQueenPos.length; i++) {
        let queen = { x: i, y: initQueenPos[i] }
        queens.push(queen)
    }
    return queens
}

/**建立棋盤 */
function initEmptyBoard(num) {
    let board = []
    for (let y = 0; y < num; y++) {
        board.push([])
        for (let x = 0; x < num; x++) {
            board[y].push('X')
        }
    }
    return board
}

/**填滿皇后 */
function fillQueen(board, initQueenPos) {
    for (let i = 0; i < initQueenPos.length; i++) {
        //取得皇后位置
        let queen = initQueenPos[i]
        //填入皇后
        board[queen][i] = 'Q'
    }
    return board
}