20-1. 遺伝的アルゴリズム（vcopt）でペントミノの敷き詰め（回転・反転なし）

pip install vcopt

import numpy as np
import numpy.random as nr
import matplotlib.pyplot as plt
from vcopt import vcopt

#===============================================
#ペントミノの作成
#===============================================
def make_pentominos():
    pentominos = []
    pentominos.append(np.array([[1,1,1,1,1]], dtype=int)) #棒も２次元配列とすること
    pentominos.append(np.array([[2,0,0,0],
                                [2,2,2,2]], dtype=int))
    pentominos.append(np.array([[0,0,3,0],
                                [3,3,3,3]], dtype=int))
    pentominos.append(np.array([[0,0,4,4],
                                [4,4,4,0]], dtype=int))
    pentominos.append(np.array([[5,0,5],
                                [5,5,5]], dtype=int))
    pentominos.append(np.array([[0,6,6],
                                [6,6,6]], dtype=int))
    pentominos.append(np.array([[0,0,7],
                                [0,0,7],
                                [7,7,7]], dtype=int))
    pentominos.append(np.array([[0,8,8],
                                [0,8,0],
                                [8,8,0]], dtype=int))
    pentominos.append(np.array([[9,9,9],
                                [0,9,0],
                                [0,9,0]], dtype=int))
    pentominos.append(np.array([[ 0,10,10],
                                [10,10, 0],
                                [ 0,10, 0]], dtype=int))
    pentominos.append(np.array([[ 0,11, 0],
                                [11,11,11],
                                [ 0,11, 0]], dtype=int))
    pentominos.append(np.array([[12, 0, 0],
                                [12,12, 0],
                                [ 0,12,12]], dtype=int))
    return pentominos

#ペントミノの作成
pentominos = make_pentominos()
print(pentominos)

#===============================================
#敷き詰める順序を受け取り、Bottom-Left法で左上から敷き詰め、フィールドを返す
#===============================================
def bottom_left(para):
    
    #フィールドの作成（高さは多めにとっておく）
    f = np.zeros((30, w), dtype=int)
    
    #paraの順序にしたがってBottom-Left法で左上から敷き詰める
    for n in para:
        
        pentomino = pentominos[n]
        next_mino = False
        
        #左上から順番に、入れられるかチェック
        for i in range(30):
            for j in range(w):
                
                #ミノの幅、高さ
                p_h, p_w = pentomino.shape
                
                #幅がフィールドを超えてしまうならNG、for文をひとつ抜ける
                if w < j + p_w:
                    break
                
                #入れられるかチェック（該当スペースに掛け算＝ANDして、全部０なら入れられる）
                #入れられるなら入れて、for文をふたつ抜ける
                if np.sum(f[i:i+p_h, j:j+p_w] * pentomino) == 0:
                    #入れる
                    f[i:i+p_h, j:j+p_w] += pentomino #代入だとダメ、足す
                    next_mino = True
                    break
                
            if next_mino == True:
                break
    
    #ミノが置かれている矩形領域を検出
    last_line = np.where(f > 0)[0][-1]
    
    #その部分を返す
    return f[:last_line + 1, :]


#フィールドの幅
w = 6

#敷き詰める順番（ID順）
para = range(12)

#敷き詰めてみる
print(bottom_left(para))

#===============================================
#敷き詰める順序を受け取り、Bottom-Left法で左上から敷き詰め、敷き詰めて表示
#===============================================
def BL_show(para):
    
    #paraの順番に敷き詰める
    f = bottom_left(para)
    
    #表示
    plt.figure(figsize=(10, 10))
    plt.imshow(f, cmap='gist_ncar_r', vmin=0)
    plt.show(), print()


#敷き詰める順番（ID順）
para = range(12)

#敷き詰めて表示
BL_show(para)

#===============================================
#敷き詰める順序を受け取り、Bottom-Left法で左上から敷き詰め、隙間の数をスコアとして返す
#===============================================
def BL_score(para, **info):
    
    #paraの順番に敷き詰める
    f = bottom_left(para)
    
    #隙間の数
    score = np.sum(f == 0)
    
    return score

#===============================================
#2-opt法で局所最適化
#===============================================

#para初期値
para = range(12)

#2-opt法で局所最適化
para, score = vcopt().opt2(para,      #並び替えたい要素の１次元配列
                           BL_score,  #評価関数
                           0.0)       #評価値をいくつに近づけるか

#結果の表示
print(para)
print(score)
BL_show(para)

#===============================================
#GAで大域最適化
#===============================================
#paraを並べたもの
para_range = range(12)

#GA
para, score = vcopt().tspGA(para_range,              #paraを並べたもの
                            BL_score,                #評価関数
                            0.0,                     #評価値をいくつに近づけるか
                            show_pool_func='print',  #簡易表示機能を使う
                            pool_num=20)             #個体数をデフォルトの120から20に減らす

#結果の表示
print(para)
print(score)
BL_show(para)