多数目的非線形ナップザック問題の応用と可視化

(1)

その他のタイトル Application and Visualization of the

Many‑objective Nonlinear Knapsack problem

著者仲川勇二, ノーマン・d クック, 上島紳一, 林

武文, 井浦崇

雑誌名情報研究 : 関西大学総合情報学部紀要

巻 38

ページ 23‑34

発行年 2013‑03‑31

URL http://hdl.handle.net/10112/7756

(2)

* 関西大学総合情報学部

多数目的非線形ナップザック問題の応用と可視化

仲川勇二^＊ノーマン・D．クック^＊上島紳一^＊林武文^＊井浦崇^＊

要旨

非線形ナップザック問題（分離形非線形離散最適化問題）は，よく知られたナップザック問題をその特殊な場合として含み応用範囲が広いにも関わらず，研究者は非常に少ない．本稿では，非線形ナップザック問題の研究の歴史を概観し，その拡張形である多目的非線形ナップザック問題（目的関数が 4 個以上の多数目的の場合を含む）の厳密解法を説明し，多目的非形ナップザック問題の実用化についても考察する．また，多目的最適化の場合，複数の評価基準を取り扱うことが必要であり多目的最適化問題を解いて得られたパレート解集合の個々の解は互いに一長一短の特性をもつ．このパレート解の集合から意思決定者にとって最も良い解を選択するために役立つ可視化の技術について提案する．

キーワード：組み合わせ最適化，多目的，多数目的，非線形ナップザック，可視化

Application and Visualization of the Many-objective Nonlinear Knapsack problem

Yuji NAKAGAWA Norman D. COOK Shinichi UESHIMA Takefumi HAYASHI Takashi IURA

Abstract

Nonlinear knapsack problems, which are also called “separate nonlinear discrete optimization problems,” include the （0 1） knapsack problem, which is well known as a special case. Of course the application range of the nonlinear knapsack problem is wide, but the number of researchers is very few.

In this paper, we describe a general view of the history of the research on the nonlinear knapsack problem. We explain the exact method for solving multi-objective nonlinear knapsack problems, which is an extension of the nonlinear knapsack problem and includes four or more objective functions.

Practical usages of the multi-objective nonlinear knapsack problem are considered. Furthermore, we handle two or more criteria of multi-objective optimization problems when we solve the multi-objective

(3)

optimization problem. Each of the obtained Pareto solutions, which have characteristic merits and demerits, is evaluated by using multiple criteria. We propose a visualization technology, which a decision-maker uses in choosing the best compromised solution out of these Pareto solutions.

Key word: Combinational Optimization, Many-objective Optimization, Multi-objective Optimization, Visualization

1 ．はじめに

本稿においては，目的関数が 4 個以上の多数目的の場合を含む多目的非線形ナップザック問題の応用とその際必要となる可視化技術について議論する．

非線形ナップザック問題は，数理計画の重要な分野で組合せ最適化問題のひとつである，多次元非線形ナップザック（multidimensional nonlinear knapsack）問題は，多制約分離形非線形離散最適化問題（multiple-constraint separable nonlinear discrete optimization problem）のことである．非線形ナップザック問題の特別な場合として，非線形の資源配分問題（resource allocation

problem）がある．多次元非線形ナップザック問題は，線形のナップザック問題のほとんどをそ

の特別な場合として含んでおり，ナップザックと名前がつく問題の中ではもっとも解くことが難しい問題である．当然，実用面では他のナップザック問題よりも応用範囲が広く重要な問題である．

非線形ナップザック問題が文献において最初に現れたのはIEEEの信頼性工学の分野であると考えられる．1956 年のMoskowitz，McLean^{［ 1 ］}あるいは日本人として最初の 1959 年のMine^{［ 2 ］} の論文では，信頼度を最大化する最適化問題が取り扱われた．複数のサブシステムからなるシステムは，サブシステムを複数個並列冗長することでシステムの信頼度を向上させることができる．このとき全体のコストが許容制限内で信頼度を最大にする冗長配分を決定する問題が最適冗長配分問題である．この問題は少し規模が大きくなると厳密に解くことができないため，

ヒューリスティック解法が活発に研究されたが，厳密解法の研究は極めて少なかった．非線形ナップザック（Nonlinear Knapsack）という用語が初めて登場するのは，1976 年のMorin，Marsten^{［ 3 ］} においてである．

非線形ナップザック問題の厳密解法としては，1978 年に発表されたMarsten，Morin^{［ 4 ］}の動的計画法と分枝限定法のハイブリッド解法が有名である．しかしこの解法では複数制約の大規模な非線形ナップザック問題を解くことは困難であった．制約が複数であるという困難（DPでいう次元の呪い）を突破するための光が，Glover^{［ 5 ］}の代理制約の考え方である．複数の制約条件式の各制約に重み（代理乗数）を付けて足し合わせ一つの制約（代理制約）とし，複数制約の代わりをさせるという考えである．この代理制約問題の最適な代理制約乗数を決定することは，

線形の問題の場合は比較的簡単であるが，問題が非線形の場合は容易ではなかった．

(4)

この代理制約法に対して，多次元非線形ナップザック問題に利用可能な最適な代理乗数を決定するアルゴリズムを提案したのが，1980 年の英国数学者Dyer^{［ 6 ］}および仲川等の 1981 年^{［ 7 ］}， 1984 年^{［ 8 ］}の研究である．しかし，代理制約法を用いた解法は代理ギャップ（ギャップのため厳密解が見つからない場合）がある問題に対しては無力であった．この代理ギャップの問題を解決することは極めて困難で，Dyerらのグループも新たな成果を出すことができずに十数年が経過した．この代理ギャップの問題を解決したのが 2003 年の仲川^{［ 9 ］}である．このとき用いたのが標的解法で，代理ギャップがある近辺の解を完全列挙することで厳密解を見つけることに成功している．

2007 年にこの代理制約法を信頼性工学の分野で超難問として知られていたマルチコンポーネント混合選択問題に適用し，世界で初めて厳密解と保証された解を見つけることに成功した．

1968 年にFyffeら^［10］は，二つの制約条件のもとで各サブシステムにおいて複数のコンポーネントから一つを選択し並列冗長として用いるマルチコンポーネント選択問題を提案し，また， 2 制約の最適化問題をDP（動的計画法）で解くために制約条件の一つにラグランジュ乗数を掛けて目的関数に移動して，制約条件が一つの非線形ナップザック問題へ変換することを試みた．

このシステム信頼性最適化問題はコンポーネント選択と冗長数を同時に決定するため，当時としては厳密に解くことが極めて難しい問題であった．Nakagawaら^{［ 7 ］}はこのマルチコンポーネント選択問題に対して代理制約を用いて二つの制約条件を一制約条件の問題に変換し原問題の代理双対問題を考え，さらに最適な代理乗数を決定する方法を提案し，Fyffeらのラグランジュ関数を用いたDPと性能比較するために，マルチコンポーネント選択問題の例題を変形し 33 問のテスト問題を作成した．実験結果よりラグランジュ関数を用いたDPよりも代理双対問題を解く代理制約問題の方が代理ギャップの面で優れていることが示された．その後，厳密解法の研究としての進展はなかったが，1996 年にCoit, Smith^［11］はNakagawaら^{［ 7 ］}のマルチコンポーネント選択問題 33 問において，複数のコンポーネントの混合使用を許すことで困難度を更に高くしたマルチコンポーネント混合使用選択問題 33 問として再提案した．この組み合わせ最適化問題は，解空間の規模が 7.6 × 10³³と非常に大きいため，既存の解法では厳密解を求めることができないと考えられ，様々なメタヒューリスティク解法を用いて近似解を求め，得られた解の品質を競う研究が十数年に渡り活発に行われた．大西ら^［12］は，仲川が開発した改良代理制約法

（ISC法：Improved Surrogate Constraint Method）^{［ 9 ］}を，この問題に適用して，短いCPU時間で厳密解を求めることに成功した．

この標的解法を多目的の問題に適用したのが［13］［16］の一連の研究である．文献［13］

において，複数目的の離散最適化問題に対して代理乗数を用いて単一の目的関数の問題（代理目的問題）に変換し，この代理目的問題を解くことで原問題のパレート解（有効解，非劣解とも呼ばれる）を効率よく求めることができることを示した．Isadaら^［14］は単一の制約条件式をもつ多目的問題の大規模問題に対して，意思決定者にとって必要とされるパレート解の部分集合を実用的な時間で求めることが可能であることを示した．この時一部のパレート解が欠ける

(5)

可能性があったが，仲川ら^［15］においては，欠けるパレート解がないように列挙の時の標的の値を決定する方法を提案した．また，仲川ら^［16］においてはある与えられた二目的のナップザック問題に対して厳密に全てのパレート解（欠けることがなくパレート解であることが保障された解）を列挙する解法を提案し，計算機実験で既存の解法と比べ格段に高速であることを示した．

2 ．多目的多次元非線形ナップザック問題

一般的によく知られたナップザック問題は，子供が遠足に行くときに，できるだけ好きな品物をナップザックに一杯詰めて持っていきたいときの問題である．詰め込みすぎると重たくて持っていけなくなる．重さの制約のもとで好ましさを最大にする品物（代替項目）の組み合わせを決定する問題がナップザック問題である．n個の品物の好ましさの度合いと重さをそれぞれc_i，a_iとし，重さの最大許容量をbとすると， 0 1 ナップザック問題は次のように書ける．

P¹: max（f x） =

n

Σ

_{i= 1}^cⁱ^xⁱ

s.t. g（x） =

Σ

_{i= 1}n ^aⁱ^xⁱ^侑 b

x_i ∈ {0, 1}（i ∈ N）

と書ける．ここで，x_i= 1 または 0 はナップザックに品物iをそれぞれ入れるか入れないかを意味する．このナップザック問題で，重さの制約だけではなく容積やコスト等の制約を考えた場合，複数の制約条件式をもつ多次元⁽¹⁾ナップザック問題となる．また，同じ品物を複数個入れることを許した問題は，整数値ナップザック問題と呼ばれる．

ナップザック問題で子供に好きなものばかり入れさせると，弁当を入れずにお菓子ばかり入れてしまうかもしれない．そこで，お菓子のグループからは一つの品物，弁当のグループからは一つの品物というように採用する品物に制約を入れると非線形ナップザックになる．

多次元非線形ナップザック問題（分離形離散最適化問題とも呼ばれる）は，n個のプロジェクトがあり，そのプロジェクトに対して投入可能なm種類の資源（人，費用，原材料等）があるものとする．それぞれのプロジェクトi ∈｛1, 2, … , n｝にはki個の考慮可能なレベル（代替項目）があるものとする．もしプロジェクトiでレベルx_i ∈｛1, … , k_i｝を採用したとき，資源 j ∈｛1, 2, … , m｝の消費量はg（_ji x_i）とし，その時のリターン（満足度，収益等）の量は（f_i x_i）とおく．また，資源jの最大許容消費量はbjとすると

（1）多次元という言葉は，複数の制約条件式をもつナップザック問題を動的計画法（Dynamic Programming）

で解くときに多段決定過程で複数次元の取り扱いを必要とするためこの言葉が使われるようになった．

当初，ナップザック問題は動的計画法が最も有効な解法と考えられていた．

(6)

P: maxf（x） =

Σ

_{i= 1}n ^（x^fⁱ ⁱ^）

s.t. g（_j x） =

Σ

_{i= 1}n ^g^（^ji ^xⁱ^）侑^b^（^j ^j^∈^M^）

xi ∈ K（i ∈ N）i

と書ける．ここでx = （x₁, x₂, … , xn）は決定すべき変数ベクトルで，M = {1, 2, … , m}は資源に対する制約条件式の添え字集合，N = {1, 2, … , n}決定変数の添え字集合，K_i = {1, 2, … , k_i}は各変数x_iの値は採用すべき代替項目を示す．

この多次元非線形ナップザック問題にq個のリターンを考慮したのが多目的多次元非線形ナップザック問題である．すなわち

P: max（x） = f

（

^f（x）, f1 （x）, … , f₂ （x）q

）

s.t. x ∈ X

ただし，f（s x） =

Σ

ⁿⁱ^{= 1}^f^（x^si ⁱ^）（s = 1, 2, …, q）, X=

{

x ∈ K

|

^g（x）侑j b（j j ∈ M）}, K={（x₁, x₂, …, x_n）

|

^xi ∈ K（_i i ∈ N）

}

．

3 ．多目的多次元非線形ナップザック問題の解法

3.1 加重和単一目的問題と代理目的標的問題

多目的多次ナップザック問題に対応した加重和（weighted sum scalarization）単一目的問題 P（^s w）と代理目的標的問題P（^T w, f_T）^［14］は以下のように記述できる．

P（w）: Max^s

Σ

^q^s^{= 1}^w^s^f^（x）^s s.t. x ∈ X および

P（^T w, f_T）: 次の標的に当ったすべての実行可能解を列挙する標的 :

Σ

^q^s^{= 1}^w^s^f^（x）侒^s ^f^T

s.t. x ∈ X，

ここで，w_s 侒 0 （s= 1, 2, … , q）は各目的関数に対する重みで

Σ

^q^{s= 1}^w^s^{= 1 であり，}^f^T^は解を列

挙するための標的値である．

原問題Pの有効解の種類としては，加重和単一目的問題P（w）を解くことで得られる支持^s

（supported）有効解と，加重和問題を解くことでは得られない非支持（unsupported）有効解があ

る．支持有効解はウエイトwの値を変化させて加重和問題P（^s w）を厳密に解くことで比較的簡単に得られるが，くぼんだ場所に存在する非支持有効解を求めるには何らかの工夫が必要となる（図 1 参照）．

(7)

本論文で扱うパレート解を求めるための標的解法は，あるウエイトw^（l）（l ∈ L ={1, 2, … , l_U}）とある標的値f^（l）_T をもつ標的問題P（^T w^（l）, f_T^（l））を改良代理制約法^{［ 9 ］}で厳密に解き得られた標的解集合（f（l）T 以上の標的値を持つ実行可能解の集合）の中だけで比較することで原問題Pの有効解が得られることに着目した解法である．この事実は下記の定理 1 で示される．問題P（^T w^（l）, f^（l）_T ）に対して制約条件x ∈ Xを満たし標的値f^（l）_T 以上の目的関数値をもつ標的解の集合をX_T^（l）

とする．また，原問題Pの二個の目的関数を用いてX^（l）_T 内のすべての要素間において優越操作を行い，明らかに劣った解を取り除き得られた解集合をX^（l）_E とする．すなわち，

X（l）E =

{

x ∈ X（l）T

|

^{（x'）侒 f}^f ^{（x）かつ}^（x'）^f ^≠^{（x）となる}^f ^x' ∈ X^（l）^T ^{が存在しない}

}

このとき次の定理 1^［13］が成り立つ．

［定理 1 ］解x ∈ X^（l）_E は原問題Pの有効解である．証明略．

定理 1 より，標的解集合X^（l）_T の中だけで比較することで得られた有効解集合X^（l）_E は原問題Ｐの有効解集合である．

18500 18600 18700 18800 18900 19000 19100

18200 18300 18400 18500 18600 18700 18800 18900 19000 19100 19200 feasible soluons unsupported eﬃ. sol.

supported eﬃ. Sol.

1( ) f x

2( )

f x

図 1 実行可能標的解，支持有効解および非支持有効解

図 2 有効三角形

(8)

次にすべての有効解を欠けることなく列挙するために，有効三角形（図 2 ）を利用する．本論文では，支持有効解だけではなく既に得られている非支持有効解も含めて，目的関数値において隣接する二個の有効解により構成される有効三角形（図 2 ）を考える．この有効三角形全体が列挙領域内に完全に含まれていれば，この隣接する二個の有効解の区間は列挙が終了したことになる．有効三角形部分が完全に列挙されているかどうかを検査することを，二個の有効解に対する有効三角形テストと呼ぶ．これをq個の目的関数の場合に拡張したのが，次の定理である．

［定理 2 ］目的関数値において隣接するq個の有効解x¹, x², …, x^qを考える．ある有効解x（^r r ∈ {1, 2, … , q}）に対して隣接したq 1 個の x（s ∈ ^s ｛1, 2, … , q｝, s ≠ r）の参照点は，

f（^R x^r, x^s） = ρrs（f x^s）（s = 1, … , q）

となる．ここで，

ρrs = minj=1, … , q

{

^f （^（xf_j^jx^s^r）^）

}

^（^s^∈^{^{1, … ,}^q}^,^r^≠^s^）である．証明略．

定理 2 より有効解の目的関数値集合f（x¹），f（x²），…，f（x^q）と原点 0 で構成された凸包には，

新たな有効解が存在しないことが分かる．

3.2 複数制約を持つ代理目的標的問題を解くための解法

複数制約を持つ標的問題（代理目的標的問題）を厳密かつ効率よく解くために，代理制約法

を用いる^{［ 9 ］}．代理制約法は複数の制約条件式を持つ原問題に対して，代理乗数を用いて単一制

約条件式の代理問題からなる代理双対問題へ変換し，この双対問題を解くことで原問題の最適解を求めようとする方法である．しかし多くの離散最適化問題では，代理双対問題に双対ギャップ（duality gap）が存在することが多く，代理制約法は解決が困難な問題点を持つ解法と考えられていた^{［ 7 ］}．この問題点を解決するために，仲川^{［ 9 ］}は標的（標的に当たった解を列挙する）問題を解くことで代理双対ギャップを閉じ，原問題の厳密解を求めることができる改良代理制約法（ISC法）を提案した．この解法により 3 個の制約条件式を持ち 1000 変数で各変数 20 個の代替項目を持つ問題や 8 制約で 500 変数 50 代替項目の問題のように，極めて大規模な多制約非線形ナップザック問題も厳密解を求めることが可能になった．従来の解法では 30 変数でも解くことができなかったことを考えると，500 変数や 1000 変数の問題が厳密に解けるようになったことからＩＳＣ法が卓越した計算性能をもつことがわかる．

代理目的標的問題を厳密に解くためにISC法を用いるとき，代理制約法の代理双対ギャップを閉じるための最適な代理乗数をもつP（^T w, f_T）の双対問題は，

P˜（^T w, f_T）: 次の標的に当ったすべての実行可能解を列挙する標的 :

Σ

^q^{s= 1}^w^s^f^{（x）侒 f}^s ^T

(9)

s.t. x ∈ X

と表せる．ただし，X =

{

x ∈ K

| Σ

^m^{j= 1}^u^^j^g^（^j ^x^）侒

Σ

^m^j^{= 1}^u^^j^b^j

^}

^．

ここで，最適な代理制約乗数uは，仲川ら^{［ 8 ］,}^［17］によって提案されたCOP（Cutting-Off Polyhedron）

アルゴリズムで求めることができる．双対問題P˜（^T w, fT）を解き原問題の実行可能領域x ∈ X を満たす標的解を求めることでP（^T w, f_T）の標的解が得られる．

双対問題P˜（^T w, f_T）は，制約条件式が一つである．この代理双対問題は，モジュラ法^［18］，^［19］を用いて高速に解くことが可能である．モジュラ法は分枝限定法の分枝操作で幅優先探索を用いた場合を拡張したもので，次の 1 ）と 2 ）の操作を繰り返して原問題をより規模の小さい等価問題へ変換する．

1 ）等価問題に対して深測操作を適用し決定空間（変数の項目空間）を縮小する．

2 ）等価問題の変数の中から二個の変数を選び一つの変数に統合することで，変数の数を一つ減らした等価問題を作る．ここで，決定空間とは探索する解空間のことであり，深測操作とは等価問題の決定空間を狭めるために，変数の項目を固定してできた部分問題に対して次の二つのテストを行う操作である．

1 ）実行可能性テスト

部分問題が実行可能解を含むかどうかテストする．

2 ）限界値テスト

部分問題の限界値を求め，標的値fTと比較し標的値よりも良い解を含むかどうかを判定する．

また，二つの変数を一つの変数に統合する統合政策は，各変数に対して上界値の最大と最小の差（上界値差）の大きい二つの変数を優先選択する．この上界値差は後の研究^［20］で，変数の困難度と密接に関係していることが分かった．仲川^［20］では複数制約の 0 1 ナップザック問題の計算の困難度を測るために，エントロピーを用いた新しい推定法を提案している．問題の各変数において，代替項目（変数がとりうる値 0 または 1 ）がよく似た特質を持ち共に最適解となる可能性が高い場合と，全く違う特質を持ち明らかに一方の代替項目が最適解になる可能性が高い場合が考えられる．代替項目がよく似た特質（上界値差で測る）を持ちどちらが最適解になるか予想しにくい変数を困難度の高い変数と呼ぶと，難しい問題は困難度の高い変数を多く含む問題であることが実験的にも示された．

また，モジュラ法で代理双対問題P（w, ^T fT）を解く際に計算効率を更によくするために，変数を統合し変数の数が十分少なくなった（約 20 個）後に，Jamesら^［21］は変数の数が少なくなった問題に対してConstraint-based ApproachとState Search enumeration等の全実行可能解を列挙する方法を適用することを提案している．計算実験ではナップザック問題に対しては世界で最も高速と評価の高いCPLEXよりも計算効率で優れていることを示している．本論文の計算実験では，モジュラ法と全実行解列挙法（State Search enumeration）のハイブリッド法^［21］を用いている．

(10)

3.3 意思決定者の求めるパレート解の列挙

意思決定者が希望するパレート解を求めるための手順を図 3 に示す．初期代理目的乗数w^（l）

と初期標的値fTの決定は，経験的な数値を用いる．また，標的解集合XTの大きさについてはプログラムの中では要素の数で判定している．

YES

ೋᦼᮡ⊛୯ ࠍ᳿ቯߔࠆ

ઍℂ෺ኻ໧㗴 ࠍ⸃߈㧘ታⴕน⢻ߥ

ᮡ⊛⸃㓸ว ࠍ᳞߼ࠆ.

ᮡ⊛⸃㓸ว ߩਛߢᲧセߒࡄ࡟࡯࠻⸃㓸ว ࠍ᳞߼ࠆ.

ᮡ⊛୯ ࠍዊߐߊߔࠆ

YES ߣߒ㧘ೋᦼઍℂ⋡⊛ਸ਼ᢙ ࠍ᳿ቯߔࠆ

Ꮧᦸߔࠆࡄ࡟࡯࠻⸃߇ߥ޿

ᮡ⊛⸃㓸ว ߇ⓨ߹ߚߪዊߐㆊ߉ࠆ

ߣߒ㧘ᣂߚߥઍℂ⋡⊛

ਸ਼ᢙ ࠍ⸳ቯߔࠆ.

図 3 意思決定者にとって好ましいパレート解列挙の手順

4 ．多数目的最適化のための情報可視化

q（侒 4 ）個の評価関数（目的関数）の情報を可視化することで，意思決定者が最善の妥協解を見つけることを支援する．提案する支援システムは，まず意思決定者が重要と考える 3 つの評価関数を選択する．得られたパレート最適解集合XE

（l）（l ∈ L）に対して，この 3 つの評価関数値を用いて図 4 のように三角グラフ（ternaryplot）を描く，この三角グラフ上においてカーソルで選択されたパレート解のq個の評価関数値をレーダーチャートで表示することができる．

このレーダーチャートを参考に意思決定者が最善の妥協解見つける．

(11)

5 ．多目的最適化の応用例

1 ）応用例 1 ．テキサス州の道路補修問題

単一年度だけを考えて道路補修をしていくと，各年度の予算を有効に使えず数年後に多大の出費を強いられる場合がある．そこで今後 5 年間を考えて補修計画を作るものとする．n個の補修すべき区間があり，区間i ∈{1, 2, … , n}には代替案としてk_i個の 5 年間の補修計画があるものとする．目的関数としては 5 年間の年度ごとの道路状況を用いる．制約条件は各年度の予算執行額が許容予算額内であることを用いる．

2 ）応用例 2 ．動圧気体軸受の設計システムの開発

動圧気体軸受は，相対運動する軸と軸受間の微少な隙間で発生する動圧力によって負荷能力と剛性を確保している．この適用事例として，磁気ディスク装置の浮上型ヘッドスライダが挙げられる．高速走行するディスク表面とヘッドスライダの間の隙間を 10nm程度に保ち，ディスクの振動や外乱に対して安定に動作させるためには，軸受面の形状の最適設計が不可欠となる．通常，軸受面は，イオンビームエッチングで形成された 6 〜12 程度のパーツで構成されるが，パーツの数，縦横寸法，配置，押付荷重，溝深さなどのパラメータによって軸受の性能が決められる．これまで試行錯誤の繰り返しにより，パラメータの選択を行っていたが，本研究の結果を適用することにより設計効率の飛躍的な向上が期待される^［22］．

㪽㪪㫌㫄㪽㪈㪽㪉㪽㪊㪽㪈㪆㪽㪪㫌㫄㪽㪉㪆㪽㪪㫌㫄㪽㪊㪆㪽㪪㫌㫄㫎㪽㪈㫎㪽㪉㫎㪽㪊

㪈㪉㪐㪈㪋㪍㪈㪈㪐㪌㪇㪐㪍㪋㪐㪎㪌㪋㪎㪇㪅㪋㪈㪇㪅㪊㪊㪈㪇㪌㪎㪇㪅㪉㪌㪏㪐㪊㪏㪇㪇㪅㪍㪌㪈㪉㪏㪊㪇㪅㪊㪈㪎㪈㪊㪊㪈㪉㪊㪇㪇㪋㪏㪈㪈㪎㪍㪉㪐㪋㪏㪍㪏㪏㪇㪇㪇㪅㪊㪐㪈㪋㪋㪇㪅㪊㪈㪌㪍㪐㪌㪇㪅㪉㪐㪉㪏㪍㪌㪇㪇㪅㪍㪌㪊㪌㪋㪎㪇㪅㪊㪌㪏㪍㪏㪌㪊㪊㪇㪈㪈㪌㪈㪈㪐㪉㪉㪐㪐㪋㪎㪏㪉㪋㪍㪇㪅㪊㪐㪌㪏㪏㪇㪅㪊㪊㪇㪊㪇㪈㪇㪅㪉㪎㪊㪏㪈㪎㪇㪇㪅㪍㪍㪇㪎㪊㪊㪇㪅㪊㪊㪌㪊㪌㪍㪋㪊㪇㪎㪍㪉㪈㪈㪎㪏㪈㪈㪇㪉㪈㪍㪏㪎㪍㪌㪇㪅㪊㪏㪉㪐㪎㪇㪅㪊㪊㪉㪇㪐㪏㪇㪅㪉㪏㪋㪐㪉㪐㪇㪇㪅㪍㪎㪈㪈㪊㪊㪇㪅㪊㪋㪏㪐㪍㪍㪌㪉㪐㪌㪏㪉㪈㪈㪐㪋㪋㪈㪇㪌㪊㪍㪎㪈㪇㪉㪇㪅㪋㪇㪊㪎㪍㪇㪅㪊㪌㪍㪈㪍㪊㪇㪅㪉㪋㪇㪇㪎㪏㪇㪇㪅㪍㪎㪊㪋㪌㪈㪇㪅㪉㪐㪋㪇㪊㪌㪍㪊㪇㪏㪉㪐㪈㪈㪐㪋㪈㪈㪇㪍㪎㪎㪏㪉㪈㪈㪇㪅㪊㪏㪎㪊㪊㪇㪅㪊㪋㪍㪊㪊㪇㪅㪉㪍㪍㪊㪋㪇㪇㪅㪍㪎㪏㪈㪈㪌㪇㪅㪊㪉㪍㪈㪐㪐㪎㪊㪇㪍㪐㪈㪈㪈㪋㪐㪈㪈㪇㪊㪌㪎㪏㪏㪋㪊㪇㪅㪊㪎㪋㪋㪈㪇㪅㪊㪊㪎㪋㪍㪇㪅㪉㪏㪏㪈㪊㪇㪇㪅㪍㪏㪇㪐㪏㪇㪅㪊㪌㪉㪏㪏㪍㪏㪊㪇㪌㪌㪈㪈㪈㪐㪈㪍㪈㪇㪏㪊㪋㪎㪏㪇㪈㪇㪅㪊㪐㪇㪇㪋㪇㪅㪊㪌㪋㪍㪉㪇㪅㪉㪌㪌㪊㪋㪋㪇㪇㪅㪍㪏㪉㪇㪍㪋㪇㪅㪊㪈㪉㪎㪊㪈㪐㪊㪇㪌㪋㪈㪈㪈㪏㪉㪈㪈㪇㪎㪍㪋㪎㪐㪌㪍㪇㪅㪊㪏㪎㪇㪌㪇㪅㪊㪌㪉㪋㪋㪋㪇㪅㪉㪍㪇㪌㪇㪉㪇㪇㪅㪍㪏㪉㪍㪊㪋㪇㪅㪊㪈㪐㪇㪋㪐㪈㪇㪊㪇㪐㪇㪊㪈㪈㪍㪇㪊㪈㪇㪍㪈㪍㪏㪍㪏㪋㪇㪅㪊㪎㪌㪋㪎㪇㪅㪊㪋㪊㪌㪉㪎㪇㪅㪉㪏㪈㪇㪇㪏㪇㪇㪅㪍㪏㪋㪌㪉㪊㪇㪅㪊㪋㪋㪈㪍㪊㪈㪈㪊㪈㪈㪍㪉㪈㪈㪎㪍㪊㪈㪇㪐㪊㪍㪏㪋㪍㪊㪇㪅㪊㪎㪎㪋㪏㪇㪅㪊㪌㪇㪐㪋㪇㪅㪉㪎㪈㪌㪏㪈㪇㪇㪅㪍㪏㪏㪊㪋㪈㪇㪅㪊㪊㪉㪍㪈㪎㪈㪉㪊㪇㪎㪍㪉㪈㪈㪋㪌㪊㪈㪇㪍㪍㪌㪏㪍㪋㪋㪇㪅㪊㪎㪉㪊㪈㪇㪅㪊㪋㪍㪍㪐㪋㪇㪅㪉㪏㪇㪐㪐㪍㪇㪇㪅㪍㪏㪏㪐㪐㪋㪇㪅㪊㪋㪋㪈㪋㪏㪈㪊㪉㪐㪊㪐㪐㪈㪈㪎㪊㪏㪈㪈㪈㪎㪊㪍㪋㪏㪏㪇㪅㪊㪐㪐㪉㪎㪇㪅㪊㪏㪇㪇㪋㪎㪇㪅㪉㪉㪇㪍㪏㪏㪇㪇㪅㪍㪐㪊㪌㪈㪎㪇㪅㪉㪎㪇㪉㪏㪍㪈㪋㪊㪇㪏㪏㪋㪈㪈㪎㪊㪏㪈㪈㪇㪐㪊㪏㪇㪌㪊㪇㪅㪊㪏㪇㪇㪎㪇㪅㪊㪌㪐㪈㪏㪊㪇㪅㪉㪍㪇㪎㪌㪇㪇㪅㪍㪐㪉㪊㪊㪐㪇㪅㪊㪈㪐㪊㪌㪉㪈㪌㪊㪇㪏㪏㪏㪈㪈㪌㪋㪇㪈㪇㪐㪋㪇㪏㪋㪇㪏㪇㪅㪊㪎㪊㪍㪈㪇㪅㪊㪌㪋㪈㪏㪊㪇㪅㪉㪎㪉㪉㪇㪐㪇㪇㪅㪍㪐㪊㪊㪎㪈㪇㪅㪊㪊㪊㪊㪏㪎㪈㪍㪊㪈㪉㪊㪍㪈㪈㪋㪉㪌㪈㪇㪏㪎㪌㪏㪐㪊㪍㪇㪅㪊㪍㪌㪎㪍㪇㪅㪊㪋㪏㪈㪌㪍㪇㪅㪉㪏㪍㪇㪏㪇㪇㪅㪍㪐㪋㪍㪌㪍㪇㪅㪊㪌㪇㪊㪎㪌㪈㪎㪊㪇㪍㪊㪍㪈㪈㪍㪋㪇㪈㪈㪉㪋㪋㪎㪎㪌㪉㪇㪅㪊㪎㪐㪐㪌㪇㪅㪊㪍㪎㪇㪈㪐㪇㪅㪉㪌㪊㪇㪊㪍㪇㪇㪅㪍㪐㪎㪐㪍㪎㪇㪅㪊㪇㪐㪐㪇㪋㪈㪏㪊㪇㪏㪈㪍㪈㪈㪍㪈㪏㪈㪈㪉㪇㪍㪎㪐㪐㪉㪇㪅㪊㪎㪎㪇㪈㪇㪅㪊㪍㪊㪍㪋㪉㪇㪅㪉㪌㪐㪊㪋㪍㪇㪇㪅㪍㪐㪎㪍㪌㪊㪇㪅㪊㪈㪎㪍㪊㪉㪈㪐㪊㪈㪉㪎㪉㪈㪈㪋㪊㪎㪈㪈㪇㪋㪉㪏㪎㪐㪊㪇㪅㪊㪍㪌㪎㪊㪇㪅㪊㪌㪊㪇㪐㪌㪇㪅㪉㪏㪈㪈㪎㪏㪇㪇㪅㪍㪐㪏㪈㪎㪌㪇㪅㪊㪋㪋㪊㪎㪈㪉㪇㪊㪈㪊㪊㪐㪈㪈㪌㪐㪎㪈㪈㪌㪇㪊㪏㪉㪊㪐㪇㪅㪊㪎㪇㪇㪌㪇㪅㪊㪍㪎㪇㪌㪈㪇㪅㪉㪍㪉㪏㪐㪐㪇㪇㪅㪎㪇㪋㪐㪏㪍㪇㪅㪊㪉㪈㪐㪏㪌㪉㪈㪊㪇㪈㪋㪏㪈㪈㪍㪎㪌㪈㪈㪍㪎㪇㪍㪏㪇㪊㪇㪅㪊㪏㪎㪉㪍㪇㪅㪊㪏㪎㪇㪐㪇㪅㪉㪉㪌㪍㪌㪊㪇㪇㪅㪎㪇㪍㪐㪐㪇㪅㪉㪎㪍㪊㪍㪏㪉㪉㪊㪇㪐㪎㪐㪈㪈㪌㪌㪎㪈㪈㪌㪎㪊㪎㪏㪋㪐㪇㪅㪊㪎㪊㪇㪍㪇㪅㪊㪎㪊㪌㪎㪍㪇㪅㪉㪌㪊㪊㪍㪌㪇㪇㪅㪎㪇㪎㪋㪎㪉㪇㪅㪊㪈㪇㪊㪇㪏㪉㪊㪊㪈㪊㪊㪉㪈㪈㪋㪍㪌㪈㪈㪋㪏㪊㪏㪊㪏㪋㪇㪅㪊㪍㪌㪐㪉㪇㪅㪊㪍㪍㪋㪐㪋㪇㪅㪉㪍㪎㪌㪏㪍㪇㪇㪅㪎㪇㪎㪌㪈㪊㪇㪅㪊㪉㪎㪎㪉㪋㪉㪋㪊㪇㪎㪈㪌㪈㪈㪋㪌㪇㪈㪈㪌㪏㪋㪎㪍㪏㪈㪇㪅㪊㪎㪉㪎㪏㪇㪅㪊㪎㪎㪈㪋㪌㪇㪅㪉㪌㪇㪇㪎㪊㪇㪇㪅㪎㪈㪇㪈㪐㪉㪇㪅㪊㪇㪍㪉㪎㪍㪉㪌㪊㪈㪇㪌㪋㪈㪈㪋㪋㪇㪈㪈㪍㪋㪇㪎㪐㪎㪋㪇㪅㪊㪍㪏㪊㪐㪇㪅㪊㪎㪋㪏㪊㪈㪇㪅㪉㪌㪍㪎㪎㪐㪇㪇㪅㪎㪈㪈㪍㪍㪈㪇㪅㪊㪈㪋㪋㪏㪏㪉㪍㪊㪈㪈㪇㪌㪈㪈㪍㪋㪋㪈㪈㪏㪋㪏㪎㪍㪈㪊㪇㪅㪊㪎㪋㪊㪋㪇㪅㪊㪏㪇㪐㪇㪊㪇㪅㪉㪋㪋㪎㪌㪉㪇㪇㪅㪎㪈㪈㪎㪋㪋㪇㪅㪉㪐㪐㪎㪌㪏㪉㪎㪊㪇㪐㪈㪈㪈㪈㪋㪊㪎㪈㪈㪍㪏㪍㪎㪎㪏㪏㪇㪅㪊㪎㪇㪅㪊㪎㪏㪇㪌㪊㪇㪅㪉㪌㪈㪐㪋㪐㪇㪇㪅㪎㪈㪉㪏㪇㪊㪇㪅㪊㪇㪏㪌㪎㪊㪉㪏㪊㪈㪍㪎㪉㪈㪈㪋㪈㪐㪈㪈㪎㪍㪉㪏㪋㪐㪈㪇㪅㪊㪍㪇㪌㪋㪇㪅㪊㪎㪈㪊㪍㪐㪇㪅㪉㪍㪏㪇㪐㪉㪇㪇㪅㪎㪈㪋㪎㪍㪌㪇㪅㪊㪉㪏㪊㪋㪋㪉㪐㪊㪇㪋㪊㪉㪈㪈㪊㪊㪈㪈㪇㪇㪊㪎㪐㪇㪍㪋㪇㪅㪊㪎㪉㪊㪋㪇㪅㪊㪉㪐㪏㪈㪎㪇㪅㪉㪐㪎㪏㪋㪋㪇㪇㪅㪍㪎㪎㪇㪋㪇㪅㪊㪍㪋㪎㪏㪊㪊㪇㪊㪇㪍㪐㪌㪈㪈㪉㪐㪊㪈㪇㪉㪇㪋㪐㪈㪐㪏㪇㪅㪊㪍㪎㪐㪈㪇㪅㪊㪊㪉㪋㪊㪉㪇㪅㪉㪐㪐㪍㪌㪏㪇㪇㪅㪍㪏㪉㪇㪉㪇㪅㪊㪍㪎㪇㪇㪌㪊㪈㪊㪈㪈㪋㪍㪈㪈㪊㪌㪇㪈㪇㪎㪍㪎㪐㪇㪉㪐㪇㪅㪊㪍㪋㪋㪈㪇㪅㪊㪋㪌㪍㪐㪋㪇㪅㪉㪏㪐㪏㪐㪊㪇㪇㪅㪍㪐㪊㪏㪎㪈㪇㪅㪊㪌㪌㪇㪋㪌㪊㪉㪊㪈㪉㪇㪊㪈㪈㪋㪈㪌㪈㪈㪈㪌㪏㪏㪍㪊㪇㪇㪅㪊㪍㪌㪏㪊㪇㪅㪊㪌㪎㪌㪐㪋㪇㪅㪉㪎㪍㪌㪎㪍㪇㪇㪅㪎㪇㪈㪉㪏㪊㪇㪅㪊㪊㪏㪎㪊㪌㪊㪊㪊㪈㪋㪏㪊㪈㪇㪐㪎㪋㪈㪇㪏㪎㪊㪐㪍㪊㪍㪇㪅㪊㪋㪏㪌㪎㪇㪅㪊㪋㪌㪊㪍㪈㪇㪅㪊㪇㪍㪇㪎㪇㪇㪅㪎㪇㪋㪏㪊㪏㪇㪅㪊㪎㪋㪏㪌㪏㪊㪋㪊㪈㪊㪉㪉㪈㪈㪊㪎㪇㪈㪈㪋㪈㪊㪏㪌㪊㪐㪇㪅㪊㪍㪊㪇㪅㪊㪍㪋㪊㪎㪍㪇㪅㪉㪎㪉㪍㪉㪇㪇㪅㪎㪇㪏㪇㪎㪏㪇㪅㪊㪊㪊㪏㪐㪊㪌㪊㪈㪏㪐㪌㪈㪈㪉㪏㪎㪈㪈㪉㪍㪋㪐㪊㪋㪋㪇㪅㪊㪌㪊㪏㪏㪇㪅㪊㪌㪊㪈㪌㪐㪇㪅㪉㪐㪉㪐㪍㪈㪇㪇㪅㪎㪇㪍㪌㪐㪎㪇㪅㪊㪌㪏㪏㪇㪊㪊㪍㪊㪈㪌㪌㪇㪈㪈㪈㪊㪋㪈㪈㪊㪊㪋㪐㪇㪏㪉㪇㪅㪊㪌㪉㪐㪇㪅㪊㪌㪐㪉㪊㪐㪇㪅㪉㪏㪎㪏㪍㪈㪇㪇㪅㪎㪈㪈㪌㪏㪐㪇㪅㪊㪌㪉㪌㪌㪍㪊㪎㪊㪈㪐㪌㪉㪈㪈㪊㪌㪉㪈㪈㪍㪌㪌㪏㪐㪋㪌㪇㪅㪊㪌㪌㪉㪏㪇㪅㪊㪍㪋㪎㪍㪍㪇㪅㪉㪎㪐㪐㪌㪈㪇㪇㪅㪎㪈㪊㪏㪈㪉㪇㪅㪊㪋㪉㪏㪍㪐㪊㪏㪊㪈㪈㪎㪐㪈㪈㪊㪇㪍㪈㪈㪎㪏㪎㪏㪇㪏㪍㪇㪅㪊㪍㪉㪍㪉㪇㪅㪊㪎㪏㪇㪋㪊㪇㪅㪉㪌㪐㪊㪋㪈㪇㪇㪅㪎㪈㪏㪇㪈㪌㪇㪅㪊㪈㪎㪍㪉㪎㪊㪐㪊㪈㪍㪇㪋㪈㪈㪉㪐㪐㪈㪈㪏㪎㪌㪏㪋㪊㪇㪇㪅㪊㪌㪎㪌㪉㪇㪅㪊㪎㪌㪎㪋㪋㪇㪅㪉㪍㪍㪎㪊㪏㪇㪇㪅㪎㪈㪐㪐㪐㪋㪇㪅㪊㪉㪍㪍㪏㪍㪋㪇㪊㪈㪈㪋㪍㪈㪈㪉㪐㪍㪈㪉㪇㪎㪇㪎㪎㪏㪇㪇㪅㪊㪍㪉㪍㪏㪇㪅㪊㪏㪎㪌㪊㪇㪅㪉㪋㪐㪎㪐㪈㪇㪇㪅㪎㪉㪋㪍㪎㪐㪇㪅㪊㪇㪌㪐㪊㪈㪋㪈㪊㪈㪊㪐㪈㪈㪈㪇㪍㪋㪈㪈㪎㪋㪍㪏㪌㪏㪈㪇㪅㪊㪌㪉㪋㪍㪇㪅㪊㪎㪋㪈㪏㪋㪇㪅㪉㪎㪊㪊㪌㪐㪇㪇㪅㪎㪉㪉㪋㪍㪐㪇㪅㪊㪊㪋㪎㪐㪌㪋㪉㪊㪈㪊㪊㪇㪈㪇㪐㪍㪎㪈㪈㪎㪊㪐㪏㪍㪉㪋㪇㪅㪊㪌㪇㪇㪌㪇㪅㪊㪎㪋㪍㪏㪐㪇㪅㪉㪎㪌㪉㪍㪊㪇㪇㪅㪎㪉㪋㪌㪊㪈㪇㪅㪊㪊㪎㪈㪉㪎㪋㪊㪊㪈㪈㪊㪐㪈㪈㪈㪍㪋㪈㪉㪇㪌㪇㪎㪐㪉㪌㪇㪅㪊㪌㪏㪌㪉㪇㪅㪊㪏㪍㪐㪎㪌㪇㪅㪉㪌㪋㪌㪇㪋㪇㪇㪅㪎㪉㪎㪉㪉㪍㪇㪅㪊㪈㪈㪎㪇㪉㪋㪋㪊㪈㪋㪉㪉㪈㪈㪇㪌㪊㪈㪈㪐㪊㪏㪏㪋㪊㪈㪇㪅㪊㪌㪈㪎㪍㪇㪅㪊㪎㪐㪐㪉㪌㪇㪅㪉㪍㪏㪊㪈㪌㪇㪇㪅㪎㪉㪎㪇㪉㪉㪇㪅㪊㪉㪏㪍㪈㪏㪋㪌㪊㪈㪉㪎㪌㪈㪈㪊㪋㪍㪈㪉㪊㪐㪌㪎㪌㪊㪋㪇㪅㪊㪍㪉㪎㪏㪇㪅㪊㪐㪍㪊㪉㪊㪇㪅㪉㪋㪇㪏㪐㪌㪇㪇㪅㪎㪊㪇㪏㪉㪋㪇㪅㪉㪐㪌㪇㪊㪌㪋㪍㪊㪈㪊㪐㪎㪈㪈㪈㪉㪎㪈㪉㪉㪇㪇㪏㪇㪎㪇㪇㪅㪊㪌㪋㪋㪇㪅㪊㪏㪏㪌㪎㪉㪇㪅㪉㪌㪎㪇㪊㪈㪇㪇㪅㪎㪊㪈㪉㪎㪉㪇㪅㪊㪈㪋㪎㪐㪎㪋㪎㪊㪈㪋㪏㪐㪈㪈㪉㪈㪊㪈㪉㪊㪐㪐㪎㪏㪎㪎㪇㪅㪊㪌㪍㪇㪐㪇㪅㪊㪐㪊㪎㪌㪎㪇㪅㪉㪌㪇㪈㪌㪈㪇㪇㪅㪎㪊㪊㪎㪊㪐㪇㪅㪊㪇㪍㪊㪎㪈㪋㪏㪊㪈㪋㪎㪐㪈㪈㪈㪈㪏㪈㪉㪊㪉㪐㪏㪇㪊㪉㪇㪅㪊㪌㪊㪈㪐㪇㪅㪊㪐㪈㪍㪌㪏㪇㪅㪉㪌㪌㪈㪌㪋㪇㪇㪅㪎㪊㪋㪊㪇㪐㪇㪅㪊㪈㪉㪋㪐㪐㪋㪐㪊㪈㪏㪋㪉㪈㪈㪈㪉㪈㪈㪉㪊㪇㪐㪏㪋㪈㪉㪇㪅㪊㪋㪐㪉㪍㪇㪅㪊㪏㪍㪌㪍㪌㪇㪅㪉㪍㪋㪈㪎㪐㪇㪇㪅㪎㪊㪊㪋㪏㪏㪇㪅㪊㪉㪊㪌㪌㪉㪌㪇㪊㪈㪏㪊㪉㪈㪈㪇㪉㪍㪈㪉㪉㪊㪐㪏㪌㪍㪎㪇㪅㪊㪋㪍㪊㪏㪇㪅㪊㪏㪋㪋㪏㪎㪇㪅㪉㪍㪐㪈㪊㪉㪇㪇㪅㪎㪊㪋㪇㪌㪉㪇㪅㪊㪉㪐㪍㪈㪏

0.25 0.27 0.29 0.31 0.33 0.35 0.37 0.39 0.41

0.6 0.65 0.7 0.75 0.8

図 4 パレート解の三角グラフとレーダーチャート

(12)

3 ）応用例 3 ．棚割りシステムの開発

商品の陳列の仕方は，販売実績に大きな影響を与えることが知られている．陳列対象の商品は店舗規模が大きくなると商品数も増加し，陳列方法の組み合わせの数が指数関数的に増え複雑になってくる．そのため従来の人が作成する棚割り表では最適なものを作成するのが困難であった．この棚割り最適化では，事業目標や制約事項が数多く重なり，競合し合う状況で利益を最大にすることである．利益を最大にする為に，基礎需要量，位置効果，フェイシング効果を考慮してモデル化を行なう．最終的に得られたパレート解（商品を制約条件の下で最適化された解）から最適な妥協解を求めるために棚割り表として可視化をおこなう．

〔謝辞〕本研究の一部は，平成22，23年度関西大学重点研究による成果である．

参考文献

［ 1 ］ Moskowitz, F., & McLean, J. W. （1956） Some reliability aspects of system design, IRE Trans. on Qual.

Contr. Vol.RQC 8, pp. 7 35.

［ 2 ］ Mine, H. （1959） Reliability of physical system, IRE Trans. on Information Theory, Vol. 5, pp. 138 151.

［ 3 ］ Morin, T. L., & Marsten, R. E. （1976） An algorithm for nonlinear knapsack problems, Management Science, Vol. 22, pp. 1147 1158.

［ 4 ］ Marsten, R. E., & Morin, T. L. （1978） A hybrid approach to discrete mathematical programming, Mathematical Programming, Vol. 14, pp.21 40.

［ 5 ］ Glover, F. （1968） Surrogate constraints. Operations Research, Vol. 16, pp. 741 749.

［ 6 ］ Dyer, M. E. （1980） Calculating surrogate constraints, Mathematical Programming, Vol. 19, pp. 255 278.

［ 7 ］ Nakagawa, Y., & Miyazaki, S. （1981） Surrogate constraints algorithm for reliability optimization problems with two constraints, IEEE Trans. on Reliability, Vol.R30, No. 2, pp. 175 180.

［ 8 ］ Nakagawa, Y., Hikita, M., & Kamada, H. （1984） Surrogate constraints algorithm for reliability optimization problems with multipleconstraints, IEEE Trans. on Reliability, Vol.R 33, No. 4, pp. 301 305.

［ 9 ］ Nakagawa, Y. （2003） An improved surrogate constraints method for separable nonlinear integer programming. J. Oper. Res. Soc. Jpn. Vol. 46, pp. 145 163.

［10］ Fyffe, D. E., Hines, W. W., & Lee, N. K. （1968） System reliability allocation and a computation algorithm, IEEE Trans. on Reliability, Vol.R 17, pp. 64 69.

［11］ Coit, D. W., & Smith, A. E. （1996） Reliability Optimization of Series-Parallel Systems Using a Genetic Algorithm, IEEE Trans. on Reliability, Vol. 45, pp. 254 260.

［12］ Onishi, J., Kimura, S., James, R.J.W., & Nakagawa, Y. （2007） Solving the Redundancy Allocation Problem with a Mix of Components using the Improved Surrogate Constraint Method, IEEE Trans. on Reliability, Vol.R 56, No. 1, pp. 94 101.

［13］仲川，疋田，（2000）多目的離散最適化問題のための対話型意思決定アルゴリズム，日本経営工学会

論文誌，Vol. 51，No. 3，pp. 197 202.

［14］ Isada, Y., James, R. J. W., & Nakagawa, Y. （2005） An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint, Euro. J. Oper. Res., Vol. 162, pp. 503 513

［15］仲川勇二，施，阿辻，木村，仲川希（2010）二目的多制約非線形ナップザック問題のための対話型改良代理制約アルゴリズム，日本経営工学会論文誌，Vol. 61，No. 1，pp. 17 22．

［16］仲川勇二，檀寛成，疋田光伯，仲川希（2011）二目的多次元ナップザック問題の全有効解列挙のための標的解法，電子情報通信学会論文誌，Vol.J94 A，No. 8，pp. 639 648．

(13)

［17］仲川勇二，並川哲郎，木村作郎，太田垣博一（2004）代理制約法における最適代理乗数の決定法，電子情報通信学会論文誌，Vol.J87A，No. 3，pp. 364 374.

［18］仲川勇二（1990）離散最適化問題のための新解法，電子情報通信学会論文誌，Vol.J73A，No. 3，

pp. 550 556.

［19］ Nakagawa, Y., & Iwasaki, A. （1999） Modular Approach for Solving Nonlinear Knapsack Problems, IEICE Trans. Fundamentals, Vol.E82 A, No. 9, pp. 1860 1864.

［20］仲川勇二（2004）多次元非線形 0 1 ナップザック問題のためのエントロピーを用いた問題困難度推定法，電子情報通信学会論文誌，Vol.J87A，No. 3，pp. 406 408.

［21］ James, R. J. W., & Nakagawa, Y. （2005） Enumerations Methods for Repeatedly Solving Multidimen- sional Knapsack Sub-Problems, Trans. IEICE Inf & Syst, Vol.E88D, No. 10, pp. 2329 2340.

［22］ Hayashi, T., Yoshida, H., & Mitsuya, Y. （2009） A Numerical Simulation Method to Evaluate the Static and Dynamic Characteristics of Flying Head Sliders on Patterned Disk Surfaces, Trans. ASME J. Tribology, Vol. 131, No. 2, 02190̲1 5.