4/14(日) 足・靴・木型研究会「第2回研究集会」を開催します☆彡

9-2. 遺伝的アルゴリズム(vcopt)でスケジューリング問題を解く(12種のレシピ編)

本記事の内容は2019年5月13日に更新されました。

やること

巡回セールスマン問題とスケジューリング問題は、どちらも並び替え問題であり似ていますが、後者の方が人間が苦手とする分、最適化の威力が発揮されやすいです。ここでは、朝食の12メニューを最短で作る手順を見つけてみましょう。

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net
Portable Scientific Python 2/3 32/64bit Distribution for Windows

vcoptの使い方についてはチュートリアルをご参照ください。

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

考え方(その1)

レシピを12種類用意しますが、例えば次のようなものです。

[[1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 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 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 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]]

行0~3はマシンを表します。

  • マシン0は人間の仕事(例:卵を割る)
  • マシン1はフライパンの仕事(例:フライパンで卵を焼く)
  • マシン2は電子レンジの仕事(例:3分チンする)
  • マシン3はオーブンの仕事(例:オーブンでパイを焼く)

列0~24は1分単位の時間を表します。 つまり上の例は、

0分目………(人間)卵を割り、フライパンに流し込む
01~05分目…(フライパン)5分間焼く
06~07分目…(人間)卵をフライパンから耐熱容器に移し、オーブンに入れる
08~13分目…(オーブン)6分間焼く

といったレシピを意味しています。卵カチカチになりますね。「最後の盛り付けはどうするのか」という疑問は残りますが気にしないように。すべてのレシピは、必ず人間の仕事から始まることとします。また、0以外の数字はレシピに固有のIDです(IDは1から始まり、paraは0から始まるというちょっとややこしい設定に…)。

考え方(その2)

複数のレシピを、順番に0分から敷き詰めていきます。新しいレシピが、すでに敷き詰められたレシピの工程と競合してはいけませんので、その場合は時間をずらします。最後の工程の時間が早いほど良いこととします。

例えば、次の2つのレシピをpara=[0, 1]に従って敷き詰めると、

[[[1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
  [0 1 1 1 1 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 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 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]]

 [[2 0 0 2 2 2 2 2 2 2 2 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 2 2 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 0 0 0 0 0 0 0 0 0]
  [0 2 2 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 2 1 1 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 2 2 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 0 0 0 0]
 [0 0 0 0 0 0 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]]

となり、スコアは17(=17分目の仕事で終わる)となります。このスコアが小さくなるようにvcopt.tsp()を実行します。

import

まずは、今回使うパッケージをインポートします。

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

スケジューリング問題の作成

各レシピとも、0分目に人間の仕事を入れ、その後はランダムにマシンを遷移しながらランダムな時間の仕事をします。ずっと人間の仕事が続くこともあるかもしれません。

#スケジューリング問題の作成
def create_recipe(recipe_num):
    
    #レシピを入れる配列
    recipe = np.zeros((recipe_num, 4, 25), dtype=int)
    
    #レシピの生成
    for i in range(recipe_num):
        #まず0分目は人間の作業(=マシンNo.0)
        recipe[i, 0, 0] = i + 1 #レシピIDは1から始める
        #その後、ランダムに遷移しては作業(2~5分)を4回繰り返す
        current_time = 1
        for j in range(4):
            next_machine = nr.randint(4)
            next_time = nr.randint(2, 6)
            #レシピに追加
            recipe[i, next_machine, current_time:current_time+next_time] = i + 1
            current_time += next_time
    
    return recipe

試しに3つのレシピを生成して見てみましょう。

#スケジューリング問題の作成
nr.seed(1)
recipe_num = 3
recipe = create_recipe(recipe_num)
print(recipe)
[[[1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
  [0 1 1 1 1 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 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 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0]]

 [[2 0 0 2 2 2 2 2 2 2 2 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 2 2 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 0 0 0 0 0 0 0 0 0]
  [0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

 [[3 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
  [0 3 3 3 3 3 3 3 3 3 3 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 0 0 0 0 0 0 0 0 0 0 0]]]

(必須)評価関数

レシピを敷き詰める順番を意味するparaを受け取ったら、長めに用意した配列(process)に敷き詰めていきます。そして、最後のプロセスの時刻を返します。

#評価関数
def recipe_score(para):
    
    #全工程を敷き詰める配列
    process = np.zeros((4, len(para)*25), dtype=int)
    
    #各レシピを、paraの順番に0分から敷き詰める
    for i in range(len(para)):
        #このレシピを
        current_recipe = recipe[para[i]]
        #0分から順に
        for t in range(len(para)*25):
            #すでに敷き詰めたレシピと競合しないかチェックして敷き詰める
            mask = process[:, t:t+25] * current_recipe[:, :]            
            if np.sum(mask) == 0:
                process[:, t:t+25] += current_recipe[:, :]
                break
    
    #最後のプロセスの時刻を返す
    process_marge = np.sum(process, axis=0)
    return np.where(process_marge > 0)[0][-1]

(任意)ひとつのパラメータ群を可視化する関数

可視化においても、また敷き詰めを行います。paraの順にレシピを敷き詰めたら、グラフにプロットします。

#paraの可視化
def recipe_show_para(para, **info):
    
    #2-opt処理中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    step_num = info['step_num']
    score = info['score']
    
    #全工程を敷き詰める配列
    process = np.zeros((4, len(para)*25), dtype=int)
    
    #各レシピを、paraの順番に0分から敷き詰める(評価関数と一緒)
    for i in range(len(para)):
        current_recipe = recipe[para[i]]
        for t in range(len(para)*25):
            mask = process[:, t:t+25] * current_recipe[:, :]            
            if np.sum(mask) == 0:
                process[:, t:t+25] += current_recipe[:, :]
                break
    
    #プロット
    plt.figure(figsize=(12, 2))
    for i in range(len(para)):
        #レシピの抽出
        a = np.where(process==i+1)
        #プロット
        plt.plot(a[1], a[0], 'o', color=cm.gist_rainbow(i/len(para)), label=i+1)
        plt.text(a[1][0] - 0.5, a[0][0] - 0.2, str(i+1))
    
    plt.xlabel('time'); plt.ylabel('machine')
    plt.xlim([0, 80]); plt.ylim([3.5, -0.9])
    plt.title('step={}, score={}'.format(step_num, score))
    #plt.savefig('save/{}.png'.format(step_num))
    plt.show()
    print()

(任意)すべてのパラメータ群を可視化する関数

こちらはもう少し見づらいです。poolを受け取ったら、100体までをみんなpool_processに敷き詰め、最後のプロセスを黒線で表示します。また、エリート個体をprocessに敷き詰め、paraの可視化と同様にプロットします。まあ…伝われ(諦め)。

#poolの可視化
def recipe_show_pool(pool, **info):
    
    #GA中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    gen = info['gen']
    best_index = info['best_index']
    best_score = info['best_score']
    mean_score = info['mean_score']
    mean_gap = info['mean_gap']
    time = info['time']
    
    pool_len = len(pool[:100])
    para_len = len(pool[0, :])
    
    #pool(100体まで)の全工程を詰め込む配列
    pool_process = np.zeros((pool_len, 4, para_len*25), dtype=int)
    #詰め込む(伝われ…)
    for n in range(pool_len):
        for i in range(para_len):
            current_recipe = recipe[pool[n, i]]
            for t in range(para_len*25):
                mask = pool_process[n, :, t:t+25] * current_recipe[:, :]            
                if np.sum(mask) == 0:
                    pool_process[n, :, t:t+25] += current_recipe[:, :]
                    break
    
    #pool(100体まで)の最後のプロセスの時刻を縦線でプロット
    plt.figure(figsize=(12, 2))
    for n in range(pool_len):
        process_marge = np.sum(pool_process[n], axis=0)
        last = np.where(process_marge > 0)[0][-1]
        plt.plot([last, last], [-1, 4], '-k', alpha=(2.0/pool_len))
    
    
    #エリートの全工程を敷き詰める
    process = np.zeros((4, para_len*25), dtype=int)
    for i in range(para_len):
        current_recipe = recipe[pool[best_index, i]]
        for t in range(para_len*25):
            mask = process[:, t:t+25] * current_recipe[:, :]            
            if np.sum(mask) == 0:
                process[:, t:t+25] += current_recipe[:, :]
                break
    
    #エリートの全工程をプロット
    for i in range(para_len):
        #レシピの抽出
        a = np.where(process==i+1)
        #プロット
        plt.plot(a[1], a[0], 'o', color=cm.gist_rainbow(i/para_len), label=i+1)
        plt.text(a[1][0] - 0.5, a[0][0] - 0.2, str(i+1))
    
    plt.xlabel('time'); plt.ylabel('machine')
    plt.xlim([0, 80]); plt.ylim([3.5, -0.9])
    plt.title('gen={}, best={} mean={} time={}'.format(gen, best_score, mean_score, time))
    #plt.savefig('save/{}.png'.format(gen_num))
    plt.show()
    print()

2-opt法で最適化

12レシピを生成し、2-opt法で何回か最適化してみます。

#スケジューリング問題の作成
nr.seed(1)
recipe_num = 12
recipe = create_recipe(recipe_num)

#適当に順番を作成
para = np.arange(recipe_num)

#2-opt法で最適化
para, score = vcopt().opt2(para,                             #para
                           recipe_score,                     #score_func
                           0.0,                              #aim
                           show_para_func=recipe_show_para,  #show_para_func=None
                           seed=None)                        #seed=None

#結果の表示
print(para + 1)
print(score)

実行結果

[ 2 11  7  9  8  6 10  5  1  4  3 12]
74
[ 6  5 11 10  9 12  2  1  3  4  7  8]
67
[ 1  7  4 12  8  2 11  3  6  5 10  9]
71

注意点ですが、結果のparaとグラフ中の順番は一致しません。左端から順にチェックして敷き詰めていくので、隙間があれば後のレシピでもそこに入ることがあるからです。

2-opt法はスケージューリング問題には適していないようで、数ステップしか更新されませんでした。とはいえ、2回目の実行では67というスコアが出ました。

GAで最適化

こちらも問題を作成し、GAを実行します。

#スケジューリング問題の作成
nr.seed(1)
recipe_num = 12
recipe = create_recipe(recipe_num)

#パラメータ範囲
para_range = np.arange(recipe_num)

#GAで最適化
para, score = vcopt().tspGA(para_range,                       #para_range
                            recipe_score,                     #score_func
                            0.0,                              #aim
                            show_pool_func=recipe_show_pool,  #show_pool_func=None
                            seed=1)                           #seed=None

#結果の表示
print(para + 1)
print(score)

実行結果

[ 9 12  4 10  5  2 11  3  6  8  1  7]
64.0

後半ものすごい時間がかかりましたが、スコア64にてGAの勝利です。どうやらフライパンがギチギチのようですが、それでもあと5, 6分くらい短縮できる手順があるかもしれません(ないかもしれません)。総評として、入力設計はもう少し工夫する余地がありそうです。

タイトルとURLをコピーしました