はじめに
平野廣美氏による1995年の論文クラスタ平均法を組み込んだ遺伝的アルゴリズムによるジョブショップスケジューリング問題の解法に記載の方法をPythonのDEAPモジュールを使用して実装した。
今回実装を5章に分けて紹介する。この記事は第4章である。
- ジョブショップスケジューリング問題について
- ジョブショップスケジューリング問題の解表現（←この記事）
- ジョブショップスケジューリング問題向きの遺伝的操作
- DEAPライブラリ
- メイン処理、実行結果とまとめ
なおソースコード全体は以下に置いてある。
なお、論文補足のため同氏による2000年初版の書籍 遺伝的アルゴリズムと遺伝的プログラミング オブジェクト指向フレームワークによる構成と応用 での記述および付属ソースコードを参考にしている。ただしクラス構成などはオリジナルとは異なる。オリジナルは洗練されており参照してほしい。
DEAPライブラリ
Python用の遺伝的アルゴリズムライブラリを探したところDEAPをみつけた。そこそこ使用例もみつかりよさそうなので今回はこれをつかってみる。
DEAPライブラリはpipその他の方法でインストール可能である。
> pip install deap
DEAPライブラリの特徴は以下記事が分かりやすい。動的なクラス生成やToolboxオブジェクトによる遺伝的操作を含む各種関数呼び出しの抽象化が特徴となる。
まずはinitialize()関数で、今回の問題向けの個体クラスの生成やToolboxオブジェクトの初期化を行うことにする。
引数のis_testはプログラム起動時に指定可能なパラメータの1つである。開発用に問題の規模や総世代数を小さくする。
別の引数のno_camもプログラム起動時に指定可能なパラメータの1つである。前章で紹介した通常の置換操作を行う。指定がない場合はクラスタ平均法（CAM）による置換操作を行う。
import array
from deap import base
from deap import creator
from deap import tools
def initialize ( is_test, no_cam ) :
"""job machine Tableをもとに個体、世代の初期設定"""
まずgetJmTable()を使って対象とする問題オブジェクトを取得する。
またこのオブジェクトからジョブ数（MAX_JOBS）や工程数（MAX_MACHINES）を取得する。
jmTable = getJmTable ( is_test )
MAX_JOBS = jmTable.getJobsCount()
MAX_MACHINES = jmTable.getMachinesCount()
getJmTable()では最初の章で紹介した問題オブジェクトを取得する。
開発時は問題規模の小さなMT6_6オブジェクト（未紹介）、通常時はMT10_10オブジェクトを取得する。
def getJmTable ( is_test ) :
jmTable = None
if is_test :
jmTable = JobMachineTable.MT6_6()
else :
jmTable = JobMachineTable.MT10_10()
return jmTable
これらをつかって個体クラスの生成を行う。
DEAPフレームワークが提供するbase.Fitnessを基底としてFitnessMinクラスを生成する。
今回の問題は適応度最小化を目的とするため、weightsパラメータには負値を指定する。
なおweightsパラメータの引数がタプルになっているのは、多目的最適化にも対応できるようにするためらしい。
# makespan最小化
creator.create ( "FitnessMin", base.Fitness, weights=(-1.0,) )
次にIndividualクラスを生成する。
パラメータに指定のarray.arrayを継承したクラスで、そのtypecodeはsigned charである。つまり各個体の遺伝子には-256から255までの値がセット可能である。ジョブ数が255を超える場合はtypecodeの検討が必要。
また、パラメータfitnessで指定のcreator.FitnessMinクラスをメンバ変数として注入している。このクラスは1つ前の行で生成したクラスである。
# 個体はジョブ番号のリスト
creator.create ( "Individual", array.array, typecode='b', fitness=creator.FitnessMin ) # 'b' is signed char
base.Toolbox()オブジェクトを作成し、今回使う遺伝的操作を含むさまざまな操作を登録する。
toolbox = base.Toolbox()
まず1個体を生成するindividual関数をtoolboxオブジェクトに登録する。
これは、tools.initIterate関数に、creator.Individualクラスとgen_ind関数オブジェクトを渡している。
# ゼロからMAX_MACHINES未満までがMAX_JOBS回ランダムに並ぶ個体と設定
gen_ind = partial ( initIndividual, MAX_JOBS, MAX_MACHINES )
toolbox.register ( "individual", tools.initIterate, creator.Individual, gen_ind )
tools.initIterate()は、フレームワークが提供する関数でその実態は次のようになっている。
def initIterate(container, generator):
# コメント省略
return container(generator())
つまりgen_ind関数オブジェクトを実行して得られた値を初期値とするcreator.Individualオブジェクトを生成する。
gen_indを実行すると、initIndividual()関数にパラメータMAX_JOBSおよびMAX_MACHINESを指定したのと同じ結果を得られる。
import random
def initIndividual ( job_num, machine_num ) :
# 0からmachine_numまでの数がそれぞれjob_numあるリストを作成しシャッフルする
src = list ( range ( job_num ) ) * machine_num
random.shuffle ( src )
return src
fitnessを考慮しなければtoolbox.individual()関数は以下のコードと同等となる。
array.array ( 'b', initIndividual ( MAX_JOBS, MAX_MACHINES ) )
このtoolbox.individual()を使って初期世代を生成するpopulation()をtoolboxに登録する。
# 初期世代をIndividualのリストとして設定
toolbox.register ( "population", tools.initRepeat, list, toolbox.individual )
tools.initRepeat()関数は以下のような実装になっている。
def initRepeat(container, func, n):
# コメント省略
return container(func() for _ in xrange(n))
つまりtoolbox.population(n)の実行は以下のコードの実行と同等である。
なおtoolbox登録時に指定していないパラメータnは関数実行時に与えることができる。
得られるものは初期化されたn個のIndividualオブジェクトのリストである。
list ( toolbox.individual() for _ i xrange ( n ) )
以下同様に評価、交叉、突然変異、選択を行う関数を登録する。
ここで、schedule.eval()、schedule.crossover()、schedule.mutation()関数はすでに紹介済みである。
# 評価関数を登録
toolbox.register ( "evaluate", schedule.eval, jmTable )
# 交叉関数を登録
toolbox.register ( "mate", schedule.crossover )
# 突然変異を登録
toolbox.register ( "mutate", schedule.mutation )
# ルーレット選択を登録
toolbox.register ( "select", tools.selRoulette )
最後に置換操作を行う関数を登録する。
起動パラメータのno_camで登録する置換操作を制御する。
schedule.getArgWorst()、schedule.getArgWorstCAM()関数はすでに紹介済みである。
# 置換操作を登録
if no_cam :
# 通常の置換操作
toolbox.register ( "getArgWorst", schedule.getArgWorst )
else :
# クラスタ平均法（CAM）による置換操作
toolbox.register ( "getArgWorst", schedule.getArgWorstCAM )
この関数全体をまとめると以下のようになる。
ここで登録した関数を上述したtest2()などで利用している。
def initialize ( is_test, no_cam ) :
"""job machine Tableをもとに個体、世代の初期設定"""
from functools import partial
jmTable = getJmTable ( is_test )
MAX_JOBS = jmTable.getJobsCount()
MAX_MACHINES = jmTable.getMachinesCount()
# makespan最小化
creator.create ( "FitnessMin", base.Fitness, weights=(-1.0,) )
# 個体はジョブ番号のリスト
#creator.create ( "Individual", list, fitness=creator.FitnessMin )
creator.create ( "Individual", array.array, typecode='b', fitness=creator.FitnessMin ) # 'b' is signed char
toolbox = base.Toolbox()
# ゼロからMAX_MACHINES未満までがMAX_JOBS回ランダムに並ぶ個体と設定
gen_ind = partial ( initIndividual, MAX_JOBS, MAX_MACHINES )
toolbox.register ( "individual", tools.initIterate, creator.Individual, gen_ind )
# 初期世代を生成する関数を登録、初期世代はIndividualのリストとして設定
toolbox.register ( "population", tools.initRepeat, list, toolbox.individual )
# 評価関数を登録
toolbox.register ( "evaluate", schedule.eval, jmTable )
# 交叉関数を登録
toolbox.register ( "mate", schedule.crossover )
# 突然変異を登録
toolbox.register ( "mutate", schedule.mutation )
# ルーレット選択を登録
toolbox.register ( "select", tools.selRoulette )
# 置換操作を登録
if no_cam :
# 通常の置換操作
toolbox.register ( "getArgWorst", schedule.getArgWorst )
else :
# クラスタ平均法（CAM）による置換操作
toolbox.register ( "getArgWorst", schedule.getArgWorstCAM )
return toolbox, jmTable
ここで紹介したinitialize()関数は以下mainモジュールに格納している。
（つづく）
次の章「メイン処理、実行結果とまとめ」はこちら
前の章「ジョブショップスケジューリング問題向きの遺伝的操作」はこちら