本研究においては，多次元0－1ナップサック問題を取り上げ,遺伝的アルゴリズムによる近似解法を考える.多次元0－1ナップサック問題に対してシンプル遺伝的アルゴリズムを適用すると，制約条件を満たさない実行不可能な個体が生成され，良好な解が得られにくいという問題点がある．制約条件を満たした個体のみを生成するためには，決定変数の順列を個体表現として採用し,その順列を優先順位とみなすことで,優先順位の高い順に制約式を満たす範囲で決定変数の値を１とすればよいことがわかる．このような操作を行うことで実行可能な解のみを生成することが可能となるが,決定変数の順列をそのまま遺伝子として扱っているために通常の1点交叉や多点交叉を用いることができず,それらに比べて複雑な操作を伴う順序交叉や部分一致交叉を用いなければならないという問題が新たに生じる．そこで，決定変数の順列を用いて，通常の１点交叉や多点交叉をオペレータとして採用するために，巡回セールスマン問題を解くための遺伝的アルゴリズムに適用されその有効性が指摘されているランダムキーを個体表現として用いる．また，遺伝的アルゴリズムによる解法の特徴の一つに，並列処理が可能な点がある．すなわち個体あるいは個体対ごとの交叉，突然変異，適合度の計算を複数のプロセッサに割り当て，同時進行させることができる．他方において，大規模数理計画問題の考え方と同様に，問題の特殊構造を利用して遺伝的アルゴリズムの計算 (交叉，突然変異) を分解して行う方法が提案されている．この分解計算では通常の遺伝的アルゴリズムと異なった並列処理が可能となることが報告されている．しかしながら分解しない通常の遺伝的アルゴリズムの並列計算も可能であることからどちらの並列化が有効であるかを調べる必要がある．そこで本研究においては，まず，ランダムキーを用いた遺伝的アルゴリズムと決定変数の順列をそのまま個体表現として採用した遺伝的アルゴリズムの性能を比較するために数値実験を行い，得られた解と実行時間からランダムキーを用いた遺伝的アルゴリズムの有効性を検証する．次に，遺伝的アルゴリズムの計算（交叉）を分解した場合の並列化と通常の遺伝的アルゴリズムの並列化の有効性を検証するために数値実験を行い，得られた解と計算時間の両面から考察を行う．
