遺伝的アルゴリズムの向き、不向きについて

Question

###前提・実現したいこと
エクセルVBAマクロ、遺伝的アルゴリズムを用いて10人前後の従業員のチームの一月分のシフト生成ソフトの作成を行っています。
その中でシフトが満たさなければならない条件（以下条件の中の一部）を元に、評価値を計算するため遺伝的アルゴリズムを使用しています。
1.勤務Aの翌日は勤務Bとなっている（必須）
2.勤務Cの翌日は勤務Dとなっていない（禁止）
3.1月での休日の数が規定日数以下となっている
4.規定時間帯は1人または2人の従業員が勤務している
上記条件を含め計10項目程の条件が存在

###発生している問題・質問事項
上記条件にて実行したところ、条件1と条件2以外を全て満たすことが出来るものの条件1と条件2を満たすことが出来るシフトを解として探索出来ませんでした。
また条件1と条件2のみで探索しても同様の結果となりました。
条件1と条件2、その他の条件の違いとして以下があります。
【条件1と条件2】
特定の値（A or C）の翌日の値が特定の値（C or D以外）となっている

【その他の条件】
特定の範囲（人毎または日毎）で規定値となっている

ここで質問なのですが、
①遺伝的アルゴリズムの特性として「特定の値（A or C）の翌日の値が特定の値（C or D以外）となっている」ような条件は難しいのでしょうか？
②もしくは現在局所解に陥っているのでしょうか？
③当該対象問題にて参考になりそうな手法 or URL等ありましたら教えて戴ければと思います。

###試したこと
・遺伝的アルゴリズム(SGA)をMGGに変更
SGAでは全条件×8日分のシフト作成まで、全条件を満たすシフトを探索可能だったのですが、
MGGでは全条件×15日分のシフト作成まで、全条件を満たすシフトを探索可能になりました。

・個体生成後（交叉、突然変異後）条件1と条件2に習い、勤務Aの後は勤務Bに、勤務Cの後は勤務D以外に置き換える処理を追加
MGGでは全条件×31日分のシフト作成まで、全条件を満たすシフトを探索可能になりました。

Answer 1

GA(Genetic Algorithm)についてそれほど詳しく調べたことがあるわけではないので意見として聞いていただければと思います。

1, 2は評価値というより「解が満たさなければならない絶対条件」なのですが、これは遺伝的アルゴリズムであてずっぽうに探索することで求めるものの評価関数の対象とすることはいささか向いていないのではと感じます。質問者さんもそこに疑問を持たれているのではないでしょうか。
評価値は「取り得る候補」の中でなるべく良い条件のものを選び出すためのもので、大抵の場合「連続値」をとるようなものというイメージがあります。

例えばSGAでは一点交差による交配、突然変異、選択の中から次世代を求め選択はルーレット選択ということなので「元々の世代にある候補が制約条件を満たすような従業員の組み合わせになるようなうまい状態のものでない」場合は突然変異によって制約条件を満たすような候補が「偶然によって生まれる」ことの依存度が高くなる気がします。もしかしたら「制約条件に従った前向き推論のようなアプローチ」の方が素直に求めることができて、それの非常に高価で非効率なシミュレーションをＧＡでしていることになるのかも知れません。

(1)遺伝的アルゴリズムの特性として「特定の値（A or C）の翌日の値が特定の値（C or D以外）となっている」ような条件は難しいのでしょうか？

個体をどのように設定しているか分かりませんが、平易に考えると30日分の全シフトの割り当て従業員のデータであるような気がします。こういう個体の評価をするのに特定の日と次の日のシフトの状態から評価値を計算することに遺伝的アルゴリズムで解くために向き不向きはないと思います。
むしろ前述したように評価関数がOKかNGの2値に基づいたものである点に難しさがある気がします。

(2)もしくは現在局所解に陥っているのでしょうか？

個体情報をどうしているか、世代あたりの個体数、交配率、突然変異率、計算世代数などなどいろいろ不明なので追試できませんが、充分と考えられるぐらい世代交代を繰り返しても1,2の条件を満たす個体が出現させられなかったとしても不思議はない気がします。前述したように満たさなければならないと分かっている制約条件をランダムな世代交代でたまたま当たりを引くまでがむしゃらに計算してもあまり効率がいいとはいえない気がするからです。局所解に陥っているかどうかとは次元が違う問題かも知れませんね。

(3)当該対象問題にて参考になりそうな手法

前述した前向き推論的なものはどうだろうと思いました。ただ、制約による探索のしかたの論理の良し悪しに効率が非常に左右されるので、ＧＡのように「評価関数を与えてとにかく計算機の力でなんとかする」というアプローチに比べると、プログラミングが難しくなりそうです。それでもうまくプログラミングできれば非常に効率的に解の空間を狭められると思います。

それはさておき、条件の中から「満たすことが絶対に必要な条件」は遺伝的アルゴリズムでの「ランダムな個体生成」により求めるのではなく「制約条件に従った個体の生成をする」というアプローチを利用したいところではないでしょうか。質問者さんがやっておられる

個体生成後（交叉、突然変異後）条件1と条件2に習い、勤務Aの後は勤務Bに、勤務Cの後は勤務D以外に置き換える処理を追加

という手段もそれに該当する考え方になると思います。

なお、個体の設定のしかたですが、条件1から「ある日の勤務Ａが決まれば次の日の勤務Ｂは必然的に決まる」ので、そもそも個体の中に勤務Bの情報を持つ必要がないとも言えます。明確な制約条件についてはそういう工夫をすることで「明らかに無駄な個体を生成しないように工夫」する必要があるのではないでしょうか。そうしないと、本来ＧＡで解きたいよりよい組み合わせを求める障害になってしまうと思います。

一つの個体＝＞
[1日: [勤務A=aさん、勤務B=bさん、勤務C=cさん、勤務D=dさん],
 2日: [勤務A=cさん、勤務B=aさん、勤務C=eさん、勤務D=fさん], //勤務Bは制約を満たしている
 3日: [勤務A=gさん、勤務B=hさん、勤務C=iさん、勤務D=aさん], //勤務Bは制約を満たしていない
 ...
 30日: [...]]

// 上記のような個体ではなく、以下のような個体にしたい

一つの個体＝＞
[1日: [勤務A=aさん、勤務C=cさん、勤務D=dさん], //勤務Bは前月の最終日の従業員
 2日: [勤務A=cさん、勤務C=eさん、勤務D=fさん], //勤務Bはaさん
 3日: [勤務A=gさん、勤務C=iさん、勤務D=aさん], //勤務Bはcさん
 ...
 30日: [...]]

Comments

[taroTanaka1]

御返答＆詳細な説明ありがとうございます。
ご提示いただいた前向き推論ですが、ざっくり目を通したところ、今回の対象問題には合致しそうではあるのですが、どのように実装するかが見えていないのでもう少し調査をしてみようと思います。
(1)、(2)については御回答にありました内容で間違いないと思いますので、教えて戴いた方法で検討してみようと思います。
(3)については上述のようにもう少し調査をした後に検討したいと思います。
ありがとうございました。