時間割の作成

　　この報告との直接的な関係はありませんが，反復改善法と似た方法によって，時間割生成プログラム（ Java 版，JavaScript 版，及び，C++ 版）を作成してみました．興味のある方はご覧下さい．

1. 問題設定

   　　大学の時間割作成は，人間にとっても非常に困難な問題の一つである．大学によってかなり事情は異なると思われるので，ここでは，本大学の場合を例に取り検討してみる．本大学には，4学科が存在し，各学科共通の科目も多くある中，それらが学科固有の科目と混在した形で時間割が作成されている．時間割作成を困難にしている原因をいくつかあげてみると以下のようになる．

   • 非常勤講師（開講日時を指定される場合が多く，その空いた時間に他の講義を埋めていく必要がある）
   • 講義室（講義によって使用講義室が限定される，講義室をすべての学科で共有している，使用率が50％を越えるような講義室がかなり存在する，等）
   • 教員（適当に時間割を作成すると，教員の衝突がしばしば発生する）
   • 複数学科を対象とした講義，また，同一学科，同一時間に複数の講義を同時開講するような場合がある．
   • 一つの講義を複数の教員が担当したり，また，複数の講義室を使用する講義が存在する．

   　　ここでは，以下に示す評価関数を最小にする時間割をコンピュータにより自動的に生成することを目的とする．

   f　=　Σwt_i　*　C_i　　(1)　　　（和は，1から11）
   ただし，C_i及びwt_iは，以下に示すような制約条件を侵した箇所数及びそれに付加された重みであり，実際に使用した重みの値は括弧内に示してある．

   1. 配置できない．後に述べるように，コンピュータ内部では，1週間に開講される講義を月曜日1時限目から順番に並べたものによって時間割を表している．したがって，配列順序によっては，2コマ以上にわたる講義が5時限目と明くる日の1時限目に配置されたり，または，開講日時が指定された科目を挟んで配置される場合がある．（200）
   2. 講義室がない．（100）
   3. 教員が衝突している．（100）
   4. 実験等の連続して開講すべき科目が昼休みで分断された．（100）
   5. 教員の都合が悪い日時に開講された．（100）
   6. 可能ならば連続して開講してほしい科目が昼休みで分断された．（0.2)
   7. 必修科目間に選択科目または講義がない時間がある．（1）
   8. 講義間に講義のない時間がある．（1）
   9. 教員にとって可能ならば避けて欲しい日時に開講された．（1）
   10. ある教員の講義が1週間に4日以上ある（講義のある日をなるべくまとめる）．（3）
   11. 指定されたある必修科目が，他学年の必修科目と重なった（再履修のため）．（0.1）

   以上のように，教員にとって，また，学生にとっての様々な条件が存在するが，少なくとも，iからvまでの条件が満足されないと物理的に実行可能な時間割とはならない．

   方法

   1. 遺伝的アルゴリズム
      　　遺伝的アルゴリズム（Genetic Algorithm，以下GAと略す）を巡回セールスマン問題（Traveling Salesman Problem，以下TSPと略す）や時間割作成問題に適用した例は多い．

      　　GAを利用するに当たり，まず問題になるのが，時間割を染色体上にどのように表現するかの問題である．すべての学科，学年の時間割を一つの個体として染色体上に表現する方法もあるが，交叉の段階で特別な工夫が必要（他学科，他学年の講義との混在を避ける必要がある）になるため，本論文では，各学科，各学年を異なる種の個体とみなして処理を行うこととした．本学には，4学科4学年が存在するため，16種類の個体が必要となるが，4年生に対する講義は非常に少ないため，4年生に対する時間割を省略し，12種類だけを考慮することとした．

      　　各個体の染色体は，その学科，学年に対して開講される講義（講義番号）を，月曜日の1時限目から順番に1列に並べたものとする（講義のないコマも含む）．また，1週間には25コマあるため，各個体の遺伝子長は25が基本となるが，

      • 2コマ以上を必要とする講義が存在する．
      • 染色体には，開講日時を指定された講義を含まない．
      • 複数学科を対象として開講される講義は，代表的な個体の染色体だけに記述し，他の個体の染色体には記述しない．

      ため，一般には25より小さくなり，種毎に遺伝子長は異なってくる．

      　　GAは，初期集団を発生させた後，交叉，突然変異，適応度（(1)式の符号を変えたもの）の計算，淘汰を繰り返して最適解を得ようとするものである．突然変異作用素として，ランダムに選ばれた2点間の遺伝子順序を逆に並べ替える方法（逆位）を採用した（突然変異率：0.05）．また，交叉方法としては，一様順序交叉，順序交叉，一様位置交叉，部分的交叉を比較した結果，循環（周期）交叉を採用することとした．循環交叉では，染色体上にランダムに1点を選択し，その位置にある親1（2）の遺伝子をそのまま子1（2）が選択する．その位置にある親2（1）の遺伝子を，その遺伝子の親1（2）の場所に，子1（2）が受け継ぐ．この手続きを，すでに受け継いだ遺伝子の位置が選択されるまで繰り返す．残りの遺伝子については，子1（2）は，親2（1）の遺伝子をその順番通りに受け継ぐ．循環交叉の具体的な例を下に示す．

      　　　　親１　　　2 4 1 3 6 5    + + 1 + + 5    3 2 1 4 6 5
      　　　　　　　　　    *       →　            →　
      　　　　親２    　3 2 5 4 1 6    + + 5 + 1 +    2 4 5 3 1 6
      				

      　　なお，交叉に関しては，同じ種の間だけで行っている．これは，他学科，他学年の講義を含むような致死遺伝子の増加を防ぐためである．しかしながら，淘汰に関しては，各種毎の最適な個体を組み合わせることによって全体としての最適なものが得られるとは限らないため，各種毎に行うわけにはいかない．そこで，各種の集団の同じ位置（配列上の同じ位置）にある個体を種の種類だけ繋げたものを１つの個体として考え，適応度を計算する．この拡張された個体に対して，ルーレット選択にエリート戦略（エリート：集団サイズの2割）を組み合わせた方法により淘汰を実行した．

      反復改善法

      　　反復改善法は，TSPに対する近似解法としてよく知られた方法である．TSPの一つの経路において，その中のλ本の枝を入れ換えて得られる経路の集合をλ近傍と呼ぶ．このλ近傍に含まれる経路の一つが，元の経路より短い経路であればそれに置き換え，再びそのλ近傍を考えるという手順を，改善が得られなくなるまで続ける方法である．

      　　本論文においては，λ近傍をλ個の講義を入れ替えることとみなし，2近傍または3近傍（2近傍を含む）に対する反復改善法を利用した．

      マルチエージェントシステム

      　　複数のエージェントが協調しながら問題を解決するシステム（マルチエージェントシステム，以後，MASと略す）に対する研究が多くの分野で注目を集めている．しかしながら，その形式的な定義に関しては，十分確立されたものが存在するとは言えない状況である．一つの問題を完全に独立した副問題に分割でき，かつ，各副問題を各エージェントが独立に解けるような設定が可能であれば，それほど多くの問題は発生しない．しかし，一般的には，完全に独立した副問題に分割することは不可能であり，各エージェントの自律的な行動は，全体システムに常に利益を与えるようなものになるとは限らない．従って，交渉等を通して，互いに協調しながら問題を解く必要が生じてくる．その際，各エージェントはある程度の資源，情報等を共有する必要性が生じるが，それをどの程度にするかによっても問題設定は大きく異なってくる．一般に，共有するものを少なくすればシステムは単純になるが，全体システムにとっての最適解は得にくくなるであろう．逆に，多くすれば，最適解が得やすくなるであろうが，計算時間等の点から，問題を分散化した意味がなくなってしまう可能性がある．

      　　ここにおいては，以下に述べるような前提で，時間割作成問題を解くことを試みる．

      • GAに対する説明で述べた各種（ある学科のある1学年の時間割）を自律したエージェントとみなす．
      • 各エージェントは，その中に限った最適化を実行可能である．
      • 各エージェントは，全体システムに対する評価値を知ることはできないが，交渉相手に関する情報，及び，自分に所属する講義を行う講義室の有無，担当する教員が空いているか否か（空いていなければ，どの講義と衝突しているかの情報）の資源に関する情報を得ることは可能である．
      • 同時に交渉可能なのは，2つのエージェントだけである（交渉方法については後述）．

      　　以上述べた前提の元で，以下のようにして処理は進行する．

      1. 講義日時を指定された科目を時間割表（全学科，学年を含むもの）に配置する
      2. 各エージェント毎に，i，及び，iv～ixの制約条件を対象として最適化を行う．最適化の方法としては，2近傍の反復改善法を使用する．今回のケースの場合，この段階では，各エージェントにとっての最適な解（制約条件をすべて満たす解）が得られる場合が多かった．
      3. ある特定の学科，学年から順番に講義室及び教員を確定し時間割表を埋めていく．一般に，この過程において，割り当てるべき講義室が無くなったり，ある教員が既に他の講義を担当することになっている（教員の衝突）ような事態が発生する．また，この割り当ての際，各エージェントの強さを(1)式によって計算する．ただし，複数エージェントにまたがる制約条件を知ることはできないため，x及びxiの制約条件に関する項を除く．このようにエージェントの強さとは，制約条件を侵している量に対応し，内容的には弱さという言葉の方が適当であるが，説明の都合上強さという言葉を使用する．
      4. 一つのエージェント（主体）を選択する．主体の選択は以下に示すいずれかの方法による．
         • ある確率（主体選択確率）pで最も強いエージェント，確率(1-p)でランダムに選ぶ．
         • ランダムに選択する（上記のpを0にした場合）
      5. 交渉相手（対象）を下に示すいずれかの方法によって選ぶ．もし，相手を選ぶことに失敗すれば，Ｄに戻る．
         • もし，教員の衝突している講義がエージェント（主体）内にあれば，衝突している相手の講義を含むエージェントを選ぶ．さもなければ，ランダムに選択する．（教員戦略）
         • 常にランダムに選択する．（ランダム戦略）
         なお，上記の方法で選ばれた交渉相手に対し，主体は必ず勝てなければならない．もし，勝てなければ，別の交渉相手を捜すことになる．2つのエージェント間の勝敗は，各エージェントの強さによって決まり，以下の3つの場合について検討する．

         • 常に，強い方が勝つ．（強者戦略）
         • 主体の強さをstr，相手の強さをo_strとしたとき，以下の式で計算される確率に従って決める．ただし，以下の値が0.1以下の時は0.1とする．（確率戦略）
           0.5　+　1.0　*　(str　-　o_str)　/　str　　　(2)
         • ランダムに決定する．（ランダム戦略）

         主体及び交渉相手の評価値を計算する．基本的に，各エージェント毎に最適化を行う場合の計算方法と同様であるが，2つのエージェント間の範囲内で他の条件も考慮する．

         選択された2つのエージェント間で交渉を行う．交渉結果として，勝者（主体）は，自分の中の2つの講義順序を変更する．交渉に関して，以下の4つの場合について検討する．

         • 2つの講義を入れ換えることによって，Ｆで計算された評価値が改善されれば交渉が成立する．ただし，相手の評価値の変化は無視する．（無視戦略）
         • 上とほぼ同様であるが，改善される量が自分の評価値に現れる最も大きな重み以上でなければならない．（重み戦略）
         • 上とほぼ同じであるが，相手の評価値も改悪されない必要がある．（協調戦略）
         • ランダムに2つの講義を入れ換える．（ランダム戦略）

         Ｃへ戻る．

   結果

   1. 入力データ
      　　入力データは，各方法固有のデータ（たとえば，GAにおける集団サイズ等）と時間割用のデータからなっている．時間割用のデータを特別に作成することは非常に困難であるため，本論文では本学におけるデータをそのまま使用した．従って，得られた結果は，そのまま，実際の時間割として使用できるものになっている．

      　　時間割用データは，各方法において共通であり，また，問題点等を理解する上においても重要と思われるので，この節で簡単に説明する．なお，以下の説明において，固有名詞等，一部のデータは変更してある．時間割用データは，大きく分けて，教員データ，講義室データ，及び，講義データの3種類からなっている．まず，教員データは，教員の名前と講義日時の都合を入力する部分であり．たとえば，以下のように記述される．

      山田太郎 水曜日 3 4 金曜日 -5 end
      このデータは，山田太郎という教員が，水曜日の3，4限目には講義不可能であり，また，金曜日の5限目は出きる限り避けて欲しいことを意味している．

      　　講義室データは，講義室の種類，実際の部屋等を入力するものであり，たとえば，以下のように記述される．

      中講義室 101 102 103 end
      代替 小講義室 中講義室 end
      最初のデータは，中講義室として，101，102，及び，103講義室の3つが存在するということ，また，2番目のデータは，小講義室が足りないときは中講義室を使用することを意味している．

      　　最も複雑なのが，講義データであり，講義名と担当教員，使用講義室などが指定され，たとえば，以下のように記述される．

      数学及び演習 [学科] 機械 電子 [学年] 1
      　　　[教員] 山田 鈴木 [コマ] 2 [講義室] 中 小 end
      物理 [学科] 機械 [学年] 1 [教員] 田中
      　　　[コマ] 1 [講義室] 中 [必修] [重複] end
      ドイツ語 [学科] 機械 [学年] 1 [教員] 佐藤
      　　　[コマ] 1 [講義室] 小 [指定] 金曜 1 end
      各データの意味するところはほとんど明らかであると思われるので詳細は省略し，理解しにくいと思われる点だけを説明する．2番目のデータの[重複]というキーワードによって，この科目と，機械工学科の他学年の必修科目を同じ時間に開講しないように指示している．また，3番目のデータにおけるキーワード[指定]とそれに続くデータによって，この科目の開講日時を指定している．

      　　なお，講義データに対する補助的なデータとして，同時開講を指定するデータが存在する．たとえば，

      機械工学科 ドイツ語 フランス語 end
      と指定することにより，機械工学科のドイツ語とフランス語が同じ時間に開講されることになり，学生はいずれかの科目だけを選択可能となる．

      実行結果

      表１　交渉戦略の比較（強者）

      交渉	対象	主体	評価値(最小)	可能率	条件数
      初期状態			2723.4(1835.5)	-	40.1
      ﾗﾝﾀﾞﾑ	ﾗﾝﾀﾞﾑ	ﾗﾝﾀﾞﾑ	1357.9( 973.3)	-	40.3
      無視	教員	1.0	162.9( 11.9)	0.50	18.3	*
      		0.8	94.1( 7.7)	0.77	13.4	*
      		0.0	166.1( 18.5)	0.70	16.4
      	ﾗﾝﾀﾞﾑ	1.0	216.3( 120.0)	-	20.4
      		0.8	173.4( 17.6)	0.40	17.3
      		0.0	441.1( 23.8)	0.10	18.9
      重み	教員	1.0	133.6( 7.5)	0.57	16.6	*
      		0.8	129.1( 10.3)	0.73	13.7	*
      		0.0	197.9( 10.4)	0.40	12.9
      	ﾗﾝﾀﾞﾑ	1.0	208.8( 12.3)	0.20	16.1
      		0.8	158.7( 20.7)	0.20	14.9
      		0.0	436.2( 115.4)	-	16.7
      協調	教員	1.0	232.9( 8.4)	0.43	16.7	*
      		0.8	178.8( 12.1)	0.47	13.7	*
      		0.0	299.1( 116.8)	-	15.7
      	ﾗﾝﾀﾞﾑ	1.0	422.6( 20.8)	0.10	19.6
      		0.8	358.2( 15.6)	0.10	17.3
      		0.0	489.1( 230.3)	-	20.5

      表２　交渉戦略の比較（確率）

      交渉	対象	主体	評価値(最小)	可能率	条件数
      無視	教員	1.0	71.5( 3.5)	0.83	13.3	*
      		0.8	54.3( 14.7)	0.80	16.2	*
      		0.0	376.1( 133.7)	-	21.4
      	ﾗﾝﾀﾞﾑ	1.0	117.1( 13.6)	0.40	18.6
      		0.8	312.8( 20.4)	0.20	19.3
      		0.0	577.2( 335.8)	-	24.1
      重み	教員	1.0	68.8( 3.5)	0.83	12.7	*
      		0.8	47.7( 3.1)	0.83	10.8	*
      		0.0	201.1( 14.2)	0.30	17.0
      	ﾗﾝﾀﾞﾑ	1.0	107.4( 6.8)	0.60	13.9
      		0.8	177.7( 9.4)	0.30	16.0
      		0.0	559.4( 319.6)	-	18.5
      協調	教員	1.0	156.8( 6.5)	0.70	14.1	*
      		0.8	73.3( 4.4)	0.83	12.6	*
      		0.0	219.7( 18.3)	0.20	15.8
      	ﾗﾝﾀﾞﾑ	1.0	292.3( 18.7)	0.10	13.8
      		0.8	190.3( 17.8)	0.20	18.1
      		0.0	535.0( 205.4)	-	16.2

      表３　交渉戦略の比較（ランダム）

      交渉	対象	主体	評価値(最小)	可能率	条件数
      無視	教員	1.0	65.4( 9.0)	0.83	14.2	*
      		0.8	64.8( 9.4)	0.83	16.2	*
      		0.0	328.0( 118.5)	-	22.6
      	ﾗﾝﾀﾞﾑ	1.0	102.2( 6.6)	0.60	16.2
      		0.8	118.3( 23.5)	0.30	19.1
      		0.0	526.5( 219.4)	-	24.2
      重み	教員	1.0	80.3( 3.6)	0.83	11.9	*
      		0.8	62.6( 3.7)	0.83	11.5	*
      		0.0	202.9( 15.7)	0.30	19.2
      	ﾗﾝﾀﾞﾑ	1.0	97.8( 8.5)	0.70	15.1
      		0.8	177.2( 5.7)	0.30	16.7
      		0.0	489.1( 130.7)	-	20.5
      協調	教員	1.0	182.9( 5.5)	0.77	13.7	*
      		0.8	67.2( 3.4)	0.83	12.1	*
      		0.0	337.9( 18.7)	0.10	17.8
      	ﾗﾝﾀﾞﾑ	1.0	208.0( 8.9)	0.50	15.0
      		0.8	218.6( 16.4)	0.30	15.1
      		0.0	440.6( 211.6)	-	18.7

      　　MASにおいて，交渉戦略，対象選択戦略，及び，主体選択確率を変えた場合に対する結果を表１から３に示す．各表の違いは，勝敗戦略の違いであり，表１は強者が必ず勝つ場合，表２は確率によって勝敗を決める場合，また，表３はランダムに勝敗を決める場合に対応している．試行回数（交渉回数）を1000回とした場合であり，比較のため，表１に，初期状態とすべてをランダムにした場合（偶然性による改善）の結果を示してある．これらの結果は，異なる10個（ただし，各表の最も右の列に*印を記したものについては30個）の乱数初期値に対する結果を平均したものであり，次節以下のシミュレーションにおいても同様である．

      　　評価値の欄は，10（30）個の試行の平均評価値と最小評価値（カッコ内）を示している（0が最適値）．可能率の欄は，10（30）個の試行の内，物理的に実行可能な時間割（つまり，制約条件iからvを満足している時間割）が作成された割合である（1.0であることが望ましい）．また，条件数の欄は，制約条件を侵している箇所数の平均値である（0であることが望ましい）．

      　　表１に示されるように，単に偶然性によって最適解が得られているわけでは無いことは明らかである．また，初期状態（各個体毎の最適化を行った後の結果）における評価値等からも明らかなように，個々のエージェントの最適化だけでは実行可能な時間割を作成できない．勝敗，交渉方法，主体及び対象の選び方，いずれに関してもその戦略の違いは結果に大きな影響を与えている．各戦略の違いに関して一般的な論議をすれば以下のようになる．勝敗に関して，強者が必ず勝つような戦略をとると，ある特定な状態に素早く達した後は，ほとんど変化しなくなる．また，ランダム戦略を採用すると，収束も遅く，かつ，十分な結果も得られない．交渉戦略として，協調戦略を採ると，無視や重み戦略に比べ探索範囲が狭まり十分な結果が得られない．また，当然予想されたように，主体や対象の選択に関しては，より多くの情報を利用した方がよい結果が得られた．結果として，勝敗戦略として確率，交渉戦略として重み戦略を採用し，確率0.8で最も強いエージェントを主体として選び，かつ，交渉相手を教員戦略によって選択した場合に最も良い結果が得られた．8割以上の確率で実行可能な時間割が得られ，そのいずれもが実際の時間割として十分使用可能なものであった．

      

      　　MASでは，当然，ある評価値を達成した後，その評価値を維持していくわけではない．全体の評価値を知らない各エージェント間で交渉を行っているため，評価値はかなり変動する．あるエージェントの2つの科目の順番を変えることにより，他のエージェントまたはその間で複数個の制約条件が侵されるようなことがしばしば発生するからである．図１は，評価値及び侵されている制約条件数（図では100倍してある）の変化の一例を示したものである．

      表４　方法の比較

      方法	侵している条件数と割合											評価 最小	可能	時間 (分)
      	i	ii	iii	iv	v	vi	vii	viii	ix	x	xi
      ＧＡ	0.0 0.00	0.0 0.00	0.0 0.00	0.0 0.00	0.0 0.00	0.4 0.09	1.9 0.40	0.6 0.13	0.0 0.00	0.3 0.06	1.5 0.32	3.8 0.3	1.0	64.7
      ２近傍	0.2 0.04	0.1 0.02	0.0 0.00	0.4 0.07	0.0 0.00	0.2 0.04	2.1 0.38	0.3 0.05	0.0 0.00	0.8 0.15	1.4 0.25	95.2 3.2	0.4	3.5
      ３近傍	0.1 0.03	0.0 0.00	0.0 0.00	0.1 0.03	0.0 0.00	0.3 0.09	1.8 0.53	0.0 0.00	0.0 0.00	0.2 0.06	0.9 0.26	32.8 1.1	0.9	69.0
      ＭＡＳ	0.0 0.00	0.0 0.00	0.2 0.02	0.2 0.02	0.0 0.00	0.4 0.04	2.0 0.18	1.3 0.12	0.0 0.00	2.3 0.21	4.5 0.41	47.7 3.1	0.8	6.4

      表５　集団サイズの比較

      集団サイズ	子供の数	世代数	1000世代目			最終世代			時間 (分)
      			評価値	可能(率)	条件数	評価値	可能(率)	件数
      50	50	1000	138.7	0.4	47.7	-	-	-	37.9
      50	150	1000	225.3	0.3	45.0	-	-	-	74.0
      30	30	1500	52.7	0.9	32.1	23.4	1.0	20.4	35.2
      30	90	1500	76.3	0.8	31.4	40.2	0.9	22.3	68.9
      10	10	4000	53.3	0.7	13.1	37.0	0.8	7.3	36.4
      10	30	4000	28.9	0.9	9.3	3.8	1.0	4.7	64.7
      5	6	6000	77.5	0.5	16.5	35.3	0.7	6.6	29.3
      5	16	6000	99.1	0.7	10.7	44.2	0.6	5.3	56.7

      　　表４は，GA，反復改善法，及び，MASを比較したものである．GAに対しては，最適な個体に対応する値を示してある．表中に示すiからxiまでの番号が付してある欄は，11個の各制約条件（制約条件(ix)に対応するデータは使用されていない）を侵している数の平均値と，侵しているすべての制約条件数に対する割合である．

      　　一般的に，GAを使用した場合，集団サイズや子供の数を増加させると収束までに要する世代数は減少するのが普通である．しかし，ここで扱っている時間割問題の場合は，表５に示すように，そのような結果が得られなかった．1000世代実行したときの結果（1000と書かれた欄）からも明らかなように，表に示した集団サイズの範囲では，集団サイズを増加させることによって得られた結果はむしろ悪くなっている．これは，時間割問題における局所解の多さに原因するものと思われる．たとえば，最も適応度が高い個体の動きを見てみる．その個体の適応度が1だけ変化したとき，集団サイズが小さい場合は，侵されている制約条件の内，重みが1である制約条件数が1だけ減り，他の制約条件数はそのままである場合が多い．しかし，集団サイズが大きい場合は，侵している制約条件数の分布が大きく変化することが多い．これは，集団サイズが大きい場合は，集団の中に様々な局所解の近傍を含んでいるが，集団サイズが小さくなると，ある局所解の近傍だけを含む確率が高くなり，そこに含まれる個体だけで適当な交叉，突然変異が実行されるため，その局所解に収束しやすくなるのであろう．これは，GAの特徴である局所解に陥りにくい性質を逆用していることになるが，得られた局所解を見る限り，十分満足できる結果であり，膨大な時間をかけ真の最適解を得る必要はないであろう．なお，表４に示された値は，最も良好な結果を示した集団サイズが10，子供の数が30の場合に対する結果である．

      　　表４によって3つの方法を比較すると，表に与えられた値を見る限り，GA及び3近傍を使用した反復改善法が最も良い方法であるといえる．しかし，いずれの方法においても，実際の時間割として十分使用可能な結果が得られている．したがって，実行時間の点を考慮すれば，2近傍を使用した反復改善法及びMASも非常に有効な方法であるといえる．

      　　ただし，MASは他の2つの方法と比較すると，多少特徴的な性質を示している．各条件数と率の欄において，他の2つの方法では，制約条件の内，制約条件vii及びxiが侵されている割合が高い．しかし，MASの場合は，制約条件xとxiが侵されている割合が高くなっている．制約条件xiに関しては，それに付加された重みが小さいことも影響しているであろうが，MASにおいては，これら2つの制約条件が，2つの個体間の交渉によっては解決しにくい制約条件であることが強く影響しているものと思われる．特にこれらの制約条件を満足させたいような場合に対しては，MASの使用は困難となるであろう．