「クラスタ平均法を組み込んだ遺伝的アルゴリズムによるジョブショップスケジューリング問題の解法」をPython DEAPで実装した 4/5

# はじめに

平野廣美氏による1995年の論文[クラスタ平均法を組み込んだ遺伝的アルゴリズムによるジョブショップスケジューリング問題の解法](https://www.jstage.jst.go.jp/article/jjsai/10/5/10_769/_article/-char/ja/)に記載の方法をPythonのDEAPモジュールを使用して実装した。

https://www.jstage.jst.go.jp/article/jjsai/10/5/10_769/_article/-char/ja/

今回実装を5章に分けて紹介する。この記事は第4章である。

1. [ジョブショップスケジューリング問題について](https://qiita.com/YosukeKentuckyFriedChicken/items/80d1cb70d96bd4586f59)
1. [ジョブショップスケジューリング問題の解表現](https://qiita.com/YosukeKentuckyFriedChicken/items/4db6a1ce5da402913ad6)（←この記事） 
1. [ジョブショップスケジューリング問題向きの遺伝的操作](https://qiita.com/YosukeKentuckyFriedChicken/items/f6cf6a9e903b6cf6bb80)
1. [DEAPライブラリ](https://qiita.com/YosukeKentuckyFriedChicken/items/8fff7f92411506c660eb)
1. [メイン処理、実行結果とまとめ](https://qiita.com/YosukeKentuckyFriedChicken/items/4b344b925bd9f9e4a16f)

なおソースコード全体は以下に置いてある。

https://github.com/shigeta-technoface/public-jsp-cam/tree/v1.1

なお、論文補足のため同氏による2000年初版の書籍 [遺伝的アルゴリズムと遺伝的プログラミング オブジェクト指向フレームワークによる構成と応用](https://www.personal-media.co.jp/book/comp/173/) での記述および付属ソースコードを参考にしている。ただしクラス構成などはオリジナルとは異なる。オリジナルは洗練されており参照してほしい。
 
https://www.personal-media.co.jp/book/comp/173/

# DEAPライブラリ

Python用の遺伝的アルゴリズムライブラリを探したところDEAPをみつけた。そこそこ使用例もみつかりよさそうなので今回はこれをつかってみる。

https://deap.readthedocs.io/en/master/

https://darden.hatenablog.com/entry/2017/04/18/225459

https://qiita.com/tyoshitake/items/e76f6f8e4110731606bc

DEAPライブラリはpipその他の方法でインストール可能である。

https://deap.readthedocs.io/en/master/installation.html

```shell-session
> pip install deap
```

DEAPライブラリの特徴は以下記事が分かりやすい。動的なクラス生成やToolboxオブジェクトによる遺伝的操作を含む各種関数呼び出しの抽象化が特徴となる。

https://qiita.com/junjis0203/items/04cd34e90705e2d5399b

まずは`initialize()`関数で、今回の問題向けの個体クラスの生成やToolboxオブジェクトの初期化を行うことにする。
引数の`is_test`はプログラム起動時に指定可能なパラメータの1つである。開発用に問題の規模や総世代数を小さくする。
別の引数の`no_cam`もプログラム起動時に指定可能なパラメータの1つである。前章で紹介した通常の置換操作を行う。指定がない場合はクラスタ平均法（CAM）による置換操作を行う。

```python:initialize()
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`）を取得する。

```python:initialize()
	jmTable = getJmTable ( is_test )
	MAX_JOBS = jmTable.getJobsCount()
	MAX_MACHINES = jmTable.getMachinesCount()
```

`getJmTable()`では最初の章で紹介した問題オブジェクトを取得する。
開発時は問題規模の小さな`MT6_6`オブジェクト（未紹介）、通常時は`MT10_10`オブジェクトを取得する。

```python:getJmTable()
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`パラメータの引数がタプルになっているのは、多目的最適化にも対応できるようにするためらしい。

```python:initialize()
	# makespan最小化
	creator.create ( "FitnessMin", base.Fitness, weights=(-1.0,) )
```

次に`Individual`クラスを生成する。
パラメータに指定の`array.array`を継承したクラスで、その`typecode`はsigned charである。つまり各個体の遺伝子には-256から255までの値がセット可能である。ジョブ数が255を超える場合は`typecode`の検討が必要。
また、パラメータ`fitness`で指定の`creator.FitnessMin`クラスをメンバ変数として注入している。このクラスは1つ前の行で生成したクラスである。

```python:initialize()
	# 個体はジョブ番号のリスト
	creator.create ( "Individual", array.array, typecode='b', fitness=creator.FitnessMin ) # 'b' is signed char
```

`base.Toolbox()`オブジェクトを作成し、今回使う遺伝的操作を含むさまざまな操作を登録する。

```python:initialize()
	toolbox = base.Toolbox()
```

まず1個体を生成する`individual`関数を`toolbox`オブジェクトに登録する。
これは、`tools.initIterate`関数に、`creator.Individual`クラスと`gen_ind`関数オブジェクトを渡している。

```python:initialize()
	# ゼロからMAX_MACHINES未満までがMAX_JOBS回ランダムに並ぶ個体と設定
	gen_ind = partial ( initIndividual, MAX_JOBS, MAX_MACHINES )
	toolbox.register ( "individual", tools.initIterate, creator.Individual, gen_ind )
```

`tools.initIterate()`は、フレームワークが提供する関数でその実態は次のようになっている。

```python:deap.tools.init.initIterate()
def initIterate(container, generator):
		# コメント省略
    return container(generator())
```

つまり`gen_ind`関数オブジェクトを実行して得られた値を初期値とする`creator.Individual`オブジェクトを生成する。
`gen_ind`を実行すると、`initIndividual()`関数にパラメータ`MAX_JOBS`および`MAX_MACHINES`を指定したのと同じ結果を得られる。

```python:initIndividual()
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()`関数は以下のコードと同等となる。

```python
	array.array ( 'b', initIndividual ( MAX_JOBS, MAX_MACHINES ) )
```

この`toolbox.individual()`を使って初期世代を生成する`population()`を`toolbox`に登録する。

```python:initIndividual()
	# 初期世代をIndividualのリストとして設定
	toolbox.register ( "population", tools.initRepeat, list, toolbox.individual )
```

`tools.initRepeat()`関数は以下のような実装になっている。

```python:deap.tools.init.initRepeat()
def initRepeat(container, func, n):
	# コメント省略
	return container(func() for _ in xrange(n))
```

つまり`toolbox.population(n)`の実行は以下のコードの実行と同等である。
なおtoolbox登録時に指定していないパラメータ`n`は関数実行時に与えることができる。
得られるものは初期化された`n`個の`Individual`オブジェクトのリストである。

```python
	list ( toolbox.individual() for _ i xrange ( n ) )
```

以下同様に評価、交叉、突然変異、選択を行う関数を登録する。
ここで、`schedule.eval()`、`schedule.crossover()`、`schedule.mutation()`関数はすでに紹介済みである。

```python:initIndividual()
	# 評価関数を登録
	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()`関数はすでに紹介済みである。

```python:initIndividual()
	# 置換操作を登録
	if no_cam :
		# 通常の置換操作
		toolbox.register ( "getArgWorst", schedule.getArgWorst )
	else :
		# クラスタ平均法（CAM）による置換操作
		toolbox.register ( "getArgWorst", schedule.getArgWorstCAM )
```

この関数全体をまとめると以下のようになる。
ここで登録した関数を上述した`test2()`などで利用している。

```python:initIndividual()
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`モジュールに格納している。

https://github.com/shigeta-technoface/public-jsp-cam/blob/main/main.py

（つづく）

---

次の章「メイン処理、実行結果とまとめ」はこちら

https://qiita.com/YosukeKentuckyFriedChicken/items/4b344b925bd9f9e4a16f

前の章「ジョブショップスケジューリング問題向きの遺伝的操作」はこちら

https://qiita.com/YosukeKentuckyFriedChicken/items/f6cf6a9e903b6cf6bb80