Help us understand the problem. What is going on with this article?

遺伝的アルゴリズムでN-Queen問題の解を求める (2)

More than 3 years have passed since last update.

前回はN=8の場合について、N-Queen問題の解の一つを求めました。
今回はそれを任意のNに拡張します。

方針

基本的には前回の8を任意のNに置き換えるだけです。今回は引数にNの値を指定して実行することで、解を求めるプログラムを書きます。
遺伝子の数は4つのままです。
前回は交叉位置が固定でしたが、今回はNによって変わるようにしています。具体的にはN-4番目以降の要素の入れ替え、N-2番目以降の要素の入れ替えを行います。

まとめ

早速ソースコードに起こします。

n-queen.py
#! /usr/bin/env python
# encoding=utf-8

# N Queens Problem

import sys
import random

gGeneCnt = 4
gMutationSpan = 4
gRange = 0
gVec = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

def makeIniGene(dim):
    ini_gene = []
    for cnt in range(0,gGeneCnt):
        line = []
        for i in range(0, dim):
            val = random.randint(0, dim-1)
            line.append(val)

        ini_gene.append(line)

    return ini_gene

def calcFitness(gene, dim):
    fitness = 0
    board = []
    line = []
    for i in range(0, dim):
        line = []
        for j in range(0, dim):
            if j == gene[i]:
                line.append(1)
            else:
                line.append(0)
        board.append(line)

    for i in range(0, dim):
        for j in range(0, dim):
            val = getCell(board, (i,j), (0,0), dim)
            if val == 1:
                for vec in gVec:
                    for k in range(1, dim):
                        valofst = getCell(board, (i,j), (vec[0]*k, vec[1]*k), dim)
                        if valofst == 1:
                            fitness += 1
                        elif valofst == -1:
                            break

    return fitness

def getCell(board, pos, ofst, dim):
    posx = pos[0] + ofst[0]
    posy = pos[1] + ofst[1]
    if posx >= 0 and posy >= 0 and posx < dim and posy < dim:
        val = board[posx][posy]
    else:
        val = -1

    return val

def simpleGa(gene_list, rank_list, dim):
    new_gene_list = []
    for i in range(0, gGeneCnt):
        if i == rank_list[3]:
            new_gene_list.append(gene_list[rank_list[0]])
        else:
            new_gene_list.append(gene_list[i])

    gaIdx = [dim-4, dim-2]
    updated_gene_list = []
    line1 = []
    line2 = []
    for i in range(0, dim):
        if i < gaIdx[0]:
            line1.append(new_gene_list[rank_list[0]][i])
            line2.append(new_gene_list[rank_list[1]][i])
        else:
            line1.append(new_gene_list[rank_list[1]][i])
            line2.append(new_gene_list[rank_list[0]][i])
    updated_gene_list.append(line1)
    updated_gene_list.append(line2)

    line1 = []
    line2 = []
    for i in range(0, dim):
        if i < gaIdx[1]:
            line1.append(new_gene_list[rank_list[2]][i])
            line2.append(new_gene_list[rank_list[3]][i])
        else:
            line1.append(new_gene_list[rank_list[3]][i])
            line2.append(new_gene_list[rank_list[2]][i])
    updated_gene_list.append(line1)
    updated_gene_list.append(line2)

    return updated_gene_list

def printBoard(gene):
    for i in range(0, len(gene)):
        line = []
        for j in range(0, len(gene)):
            if j == gene[i]:
                line.append(1)
            else:
                line.append(0)

        print line

def main(argv):
    dim = int(argv[1])
    gene_list = makeIniGene(dim)
    print "Initial gene = " + str(gene_list)

    fitness = []
    for i in range(0, gGeneCnt):
        fitness.append(0)

    loop = 0
    while True :
        loop += 1
        idx = 0
        max_fitness_idx = []
        min_fitness_idx = []

        # mutation
        if loop % gMutationSpan == 0:
            geneidx = random.randint(0, gGeneCnt-1)
            posidx = random.randint(0,  dim-1)
            valrand = random.randint(0,  dim-1)
            gene_list[geneidx][posidx] = valrand

        # compare fitness
        for gene in gene_list:
            fitness[idx] = calcFitness(gene, dim)
            if idx == 0:
                max_fitness_idx = (fitness[0], 0)
                min_fitness_idx = (fitness[0], 0)

            if max_fitness_idx[0] < fitness[idx]:
                max_fitness_idx = (fitness[idx], idx)

            if min_fitness_idx[0] > fitness[idx]:
                min_fitness_idx = (fitness[idx], idx)

            print fitness[idx]
            idx += 1

        min_fitness = min(fitness)
        if min_fitness <= gRange:
            print "Loop end = " + str(loop) + ", Fitness = " +  str(min_fitness)
            printBoard(gene_list[min_fitness_idx[1]])
            break

        ranktemp = []
        for i in range(0, gGeneCnt):
            if i !=  max_fitness_idx[1] and i != min_fitness_idx[1]:
                ranktemp.append(i)

        if fitness[ranktemp[0]] > fitness[ranktemp[1]]:
            rank_list = [ min_fitness_idx[1], ranktemp[1], ranktemp[0], max_fitness_idx[1] ]
        else:
            rank_list = [ min_fitness_idx[1], ranktemp[0], ranktemp[1], max_fitness_idx[1] ]

        updated_gene_list = []
        updated_gene_list = simpleGa(gene_list, rank_list, dim)
        gene_list = updated_gene_list


if __name__ == "__main__":
        main(sys.argv)

例としてN=16のときの実行結果を示します。

$./n-queen.py 16
...
...
2
2
2
0
Loop end = 23420, Fitness = 0
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]

収束遅いですね。。。。
収束を早めるには交叉の方法を変更する必要がありそうです。
最後は突然変異の運に頼るので、ちゃんとした突然変異の方法も考える必要があるのかも。
今後の課題です。

参考

はじめての人工知能 Excelで体験しながら学ぶAI ::淺井登 著

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした