多目的0-1計画問題に対する遺伝的アルゴリズムに基づくファジィ意思決定手法とマーケティング問題への応用
7
0
0
全文
(2) リズ ムで は、 変 数 の値 の列 とそ の添 え字 の列. 化 され 、 そ の 制 約 式 の 係数 が正 、 負 と も に混. を 二 段 に並 べ た二 重 構 造 の ス ト リング に対 し. 在 して い る よ う な広 告 媒体 選 択 問題[12]に. て 適 当 な交 叉 オ ペ レー タを定 義 し、 オ ペ レー. 適 用 し、 提 案 した手 法 の有 効 性 を検 討 す る。. タ適 用後 に生 成 さ れ た個 体 が制 約 条 件 を破 っ た場 合 の み、 一 部 の構 成 要 素(変 数)を. 強制. 的 に1か ら0に 置 き換 え て常 に実 行 可 能 とな る よ う に工夫 さ れ て い る。 しか し、 こ こで は、. 2.フ. ァ ジー 多 目的0-1計 画 問題. 本 論 文 で は、 以 下 の よ うな 多 目的0-1計. 画. 問題 に つ い て 考 察 す る。. ナ ップサ ック問題 、 集 合 被 覆 問 題、 集 合 分 割 問 題 の よ う に、 線 形 制 約 式 の 係 数 が す べ て 正 で あ る こ とを前 提 と して い る。4番 C.Bean[1]に. 目 は、J.. よ り提 案 さ れ た ラ ンダ ム キ ー. ここで 、 , ,…, は、 κ個 の相 競 合. に よ る方 法 で、 変 数 の 構 成 要 素 の次 数 η に. す る 目的 関 数 で 任 意 の実 数 値 関 数 、 制 約 式 は. 対 応 す る ラ ンダ ムキ ー空 間[0,1]η 上 で 生 成. す べ て 線 形 関 数 で、、 . され た個 体 群 に対 して 、 遺 伝 的 オペ レー タを. 実数値行列、. 適 用 し、 生 成 され た ラ ンダ ム キ ーの 構 成 要 素. 数 値 ベ ク トルで あ り、 各 構 成 要 素 は任 意 の符. の大 小 順 か ら、 変 数 の 順 番 を決 定 、 そ の 順 番. 号 を もつ もの と す る。. に従 って 、 各 要 素 を 順 次1に 固 定 して ゆ き、 制 約 条 件 を満 た さな くな った段 階 で それ 以 降. は. 次 次実. 本論 文 で は、 意 思 決 定 者 は 、 各 目的 関 数 に対 して あ い ま いな 目標(フ. ァ ジー 目. の要 素 をす べ て0に 設 定 す る。 しか し、 この. 標)を 持 ち、 主 観 的 に彼 の フ ァ ジー 目標 を メ. 方 法 で も、3番. ンバ シ ッ プ関 数. 目の 方 法 と同様 に、 線 形 制 約. に よ り規 定 す る こ. 不等 式 の係 数 はす べ て 正 で あ る こ とを前 提 と. とが で き る もの と仮 定 す る。 この時 、 も との. して い る。 ま た、 変 数 の要 素 数 とそ の個 体 群. 問 題(1)は、 次 の よ うな各 メ ンバ シ ップ関 数 を. サ イ ズに対 応 す る実 数 変 数 の配 列 が必 要 とな. 最 大 化 す る フ ァ ジー 多 目的0-1計 画 問 題 に変. り、対 象 とす る問 題 の変 数 の個 数 と個 体 群 サ. 換 され る。. イ ズ に依 存 して莫 大 な記 憶 容 量 が必 要 と な る と い う、 数 値 計 算 上 の問 題 点 が あ る。 この よ うな状 況 に お い て、 本 論 文 で は、 制 約 式 は線 形 不 等 式 で あ るが そ の係 数 の符 号 は. さ らに、 本 論 文 で は、意 思 決 定 者 は、 これ ら. 任 意 で あ るよ うな0-1整 数 計 画 問題 を 対 象 と. の メ ンバ シ ッ プ 関 数 を 統 合 す る オ ペ レ ー タ と. して 、遺 伝 的 ア ル ゴ リズ ムに基 づ く最 適 化 ア. し て フ ァ ジ ー決 定[2]を. ル ゴ リズム を提 案 す る。 また、 提 案 した ア ル. 定 す る 。 こ の 時 、 フ ァ ジ ー 多 目 的0-1計. ゴ リズ ムを フ ァ ジー環 境 に お け る多 目的0-1. 題 は 、 以 下 の よ う な 通 常 の0-1計. 計 画 問題 に組 み込 み、 遺 伝 的 アル ゴ リズ ムに. 着 で き る。. 基 づ く意 思 決 定 手 法 を提 案 す る。 さ らに、 具 体 例 と して、 多 目 的0-1計 画 問題 と して 定 式. 採 用 す る も の と仮 画 問. 画 問 題 に帰.
(3) しか し、 この よ うな ペ ナ ル テ ィ関数 を含 む 適 応 度 関 数 に対 して は、 制 約 条 件 が非 常 に厳 しい問 題 の場 合 、 生 成 した個 体 の ほ とん どが こ こで、 制 約 式 の係 数 が 任 意 の符 号 で あ る た め、 制 約 式 の係 数 が正 で あ る こ と を前 提 に して い る坂 和 らの2重 構 造 の ス トリ ング に よ る改 良 型 遺 伝 的 ア ル ゴ リズ ム[8],[9]や Bean[1]の. 、. ラ ン ダム キ ー に よ る方 法 は、 直. 適 応 度 ゼ ロ に な って しま い、 効 率 的 な最 適 解 の探 索 は期 待 で き な い。 こ の よ うな問 題 点 に対 処 す る た め、 本 論 文 で は、(3)の制 約 式 の 係 数 行 列 ・A、係 数 ベ ク トルbの. 各 要 素 の 符 号 が 任 意 で あ る よ うな. 接 適 用 す る こ と はで き な い ことに注意 しよ う。. 最 適 化 問 題(3)に対 して 、SGAに. 例 え ば 、 右 辺 定 数 が 負 の場 合 や 、 た とえ 正 で. ゴ リズ ムを 提 案 す る。 そ の前 に、 まず 、SGA. あ って も1番 目 に選 ばれ た構 成 要 素 の係 数 の. の 基 本 ア ル ゴ リズ ム を以 下 に示 す 。 この アル. 値 よ り も小 さ い場 合 な ど は、 個 体 が 実 行 可 能. ゴ リズ ム にお いて 、 目的 関 数 にペ ナル テ ィ項. で あ る に も関 わ らず 、1番. を 付 け加 え た式(4)を適 応 度 関 数 と して採 用 し. 目 に選 ば れ た構 成. 基 づ くア ル. 要 素 を1に して も0に して も実 行不可 能 とな っ. て い る。. て し ま う。 以 下 で は、 この よ うな0-1計 画 問. [SGAの. 題 に 対 して も対 処 しう る遺 伝 的 アル ゴ リズ ム. ス テ ップ1解. を提 案 す る。. 応 して η個 の 要 素 か らな る0-1ア ル フ ァベ ッ. 基 本 ア ル ゴ リズム] 空 間 を、 変 数 の 次 数 π に対. トの ス ト リン グ に符 号化 す る。 3.遺. 伝 的 ア ル ゴ リズ ム. ス テ ップ2. 0-1整 数 計 画 問題(3)に対 してGoldberg[3] に よ り提 案 さ れ た単 純GA(SGA)を. 適用 し. 0-1ア ル フ ァベ ッ トの ス ト リ ン. グを設 定 した 個数(個 体 群 サ イ ズ:pop _size) だ け ラ ン ダム に発 生 させ て、 初 期 個 体 群 を生. た場 合 、 交 叉 ・突 然 変 異 に よ り生 じた個 体 は、. 成 す る。 初 期 世 代 t=1と. 制 約 条 件 を満 た さ な い可 能 性 が高 い。 そ こで、. ス テ ップ3各. こ の よ う な制 約 条 件 付 き最 適 化 問 題 に対 して. 関 数 の値 を計 算 す る。i=0と. 遺 伝 的 ア ル ゴ リズ ム を適 用 す る場 合 、 しば し. ス テ ップ4選. ば 、 制 約 条 件 を破 れ ば対 応 す る 目的 関 数 に ペ. 群 の中 か ら適 応 度 関 数 の値 に応 じて、2つ の. ナ ル テ ィを 課 す(こ. ス ト リ ング を選 択 す る。. る)こ F(x)が. こで は、 ゼ ロ に置 き換 え. と に よ って 、 次 の よ う な 適 応 度 関 数 採 用 され て い る。. は、. が(3)の 制 約 条 件 を. そ う で な い 場 合 に は0を. す る。. 択 オ ペ レー タ を用 いて、 個 体. ばれ た ス ト リン グの ペ ア に対. して 、 確 率. で 交 叉 オペ レー タを適 用 す る 。. ステ ップ6選. ばれ た ス ト リン グの ペ ア に対 で 突 然変 異 オ ペ レ ー タ を 適 用. す る。 ス テ ッ プ7. 満 た せ ば1、. ス トリ ング に対 して、 適 応 度. ステ ップ5選. して、 確 率 ここで、. 設 定 す る。. と して 、 も し、. と るペ. な らば、 新 た に生 成 され た 個 体 ナ ル テ ィ関 数 で あ る。.
(4) 群 を 旧 個 体 群 と入 れ 替 え て 、 世 代t=t+1. らば、. と して 次 の ス テ ップ へ い く。 そ うでな ければ、. ス テ ップ7 . ス テッ プ4へ. 番 目の制 約 式. も ど る。. を 満 た す場 合 、 あ る い は、. ス テ ップ8 世 代t<T(最 ス テ ップ3へ. とす る。. 終 世 代)な. らば. も ど る。 そ うで な け れ ば、 次 の. =η の場 合 に は. と して、 ス テ ッiプ. 3へ 戻 る。 そ うで な け れば、i=i+1と. ス テ ップ へ い く。. ス テ ッ プ5へ 戻 る。. ステ ップ9 . この アル ゴ リズ ム をSGAの. 最 終 世 代 丁 ま で の集 団 の 中 で. して、. 基本アルゴリ. 最 大 適 応 度 を もつ ス トリン グを、 も との解 空. ズ ムの ス テ ップ3に 組 み込 む こと に よ り、 修. 間 に デ コ ー ド化 して それ を近 似最 適解 とす る。. 正 され た 遺伝 的 ア ル ゴ リズ ム を構 成 す る こ と. 厳 しい 制 約 条 件 を有 す る最 適 化 問題 に対 し. が で き る。 す な わ ち 、SGAの. て、 この 遺 伝 的 ア ル ゴ リズムを適 用 した場合、. 次 の ス テ ップ3'に 置 き換 え る。. 生成 され る個 体 群 の ほ とん どす べ て が ゼ ロ と. ステ ップ3'各. な って しま い、 解 の改 善 が 進 ま な い可能 性 が. ダ ム0-1反 転 法 を適 用 し、 適 応 度 関 数 の値 を. あ る。 そ こ で、 本 稿 で は、 制 約 条 件 を破 る個. 計 算 す る。i=0と. 体 に対 して 、 係 数 の符 号 情 報 と構 成要 素 の値. この 修 正 され た遺 伝 的 アル ゴ リズ ム に お い. の情 報 を も と に して、 ラ ンダ ム な順序 で各 制. て 、 た とえ ス テ ップ3'で ラ ン ダ ム0-1反 転 法. 約式 を 満 たす よ うに0,1を. いれかえ るとい. を 適 用 して も必 ず実 行 可 能 解 が得 られ る とい. う、 ラ ンダ ム0-1反 転 法 を提 案 す る。 す な わ. う保 証 はな い の で、 ス テ ッ プ3'の 適 応 度 関. ち、 生 成 さ れ た各 個 体 に対 して 、 少 な く と も. 数 は ペ ナル テ ィ項 を付 け加 え た(4)式で定 義 し. 1つ の 制 約 条 件 を満 た さ ない ものが あ る場合 、. て い る こ とに注 意 しよ う。. ス テ ッ プ3を. ス ト リ ン グ に対 して 、 ラ ン. す る。. 以下 の 処 理 を行 う。 4.広. [ラ ンダ ム0-1反 転 法] ス テ ッ プ1 実 行 可 能 で な い制 約 式(. 個. 告 媒体 選 択 問題 へ の応 用. この節 で は、 提 案 した アル ゴ リズ ムの有 効 性. とす る)に 対 して、 ラ ンダ ム に順 位 付 けを行. を 検 討 す る ため に、Wiedey and Zimmermann. い 、 そ れ らの 添 字 集 合 を{. [12]に よ り定 式 化 され た 広 告 媒 体 選 択 問 題. }と. に適 用 し検討 を加 え る。. お く。 ス テ ッ プ2 . とお く。 決 定 変 数 の 添 字 集 合. トに対 して 新製 品投 入 に際 して効 果 的 な広 告. ラ ン ダム に並 び替 え 、 そ れ ら. キ ャ ンペ ー ンを行 うた め に、 限 られ た予 算 の. ス テ ッ プ3 {1,2,…,n}を. こ の問題 は、 あ る地域 に限定 され たマ ー ケ ッ. を、{. }と お く。. な らば 、. 中 で 各 種 広告 媒 体(全. 国版 新 聞、地 方版 新聞 、. 週 刊 誌 、 ジ ャー ナ ル)を. 終 了 す る。 ス テ ップ4 i=1と. べ きか と い う意 思 決 定 問題 を、 多 目 的0-1計. お く。. ス テ ッ プ5 . も し、. ら ば、. とす る。. ス テ ッ プ6 . も し、. どの よ うに選 択 す る. か つ. な. 画 問 題 と して定 式 化 した もの で あ る。 目 的関 数 と して は、 累 積 到 達 率(広 告 を少 な く と も. かつ. な. 一 回 は視 た視 聴 者 の割 合 で広 告 の広 が りを表.
(5) す 指 標)、 延 べ 到 達 率 、 視 聴 の 深 さ を 測 る指 標 の3目 標 を取 り上 げ て、 各 目標 に対 して意 思 決 定 者 が主 観 的 に彼 の フ ァ ジ ー 目標 を線 形 メ ンバ シ ッ プ関 数 に よ り規 定 す る もの とす る。 ま た、 決 定 変 数 と して は、 あ る期 間、 あ る広 告 媒 体 を、 何 本 購 入 す る か を、04変. 数 によ. り表 現 し、 結 局 、 以 下 の よ うな19制 約 式30変 数 に よ り構 成 され る フ ァ ジ ィ多 目的0-1計 画 問 題 と して定 式 化 した。.
(6) ら0.9ま で0.1き ざ み で 設 定 し た 場 合 の 適 用 結 果 を 表1に. 示 す。 表1 SGAの. 適用結果. 最適解F(）. 交 叉 率Pc. 最適解が得 られる世代 7361. 0.2. 0.446964 0.492418. 0.3 0.4 0.5. 0.000000 0.477327 0.472782. 0.6 0.7 0.8 0.9. 0.457509 0.465145 0.442418 0.465145. 10000 8015 3541 2475 444. 0.1. 5463. 9871 9586. こ の 表 か ら、 交 叉 率 =0.2の. と き、 最. 大 適 応 度 =0.492418, (000010010001000006010001001010) が5463世. 代 で得 られ た。 この 値 は真 の 最適 目. 的 関 数 値(0.492418)と. 一 致 す る。 し か し、. そ れ 以 外 の 交 叉 率 で は す べ て 、10000世. 代. ま で に得 られ た最 大 適 応 度 は真 の 最 適 目的 関 数 値 に は 程 遠 く 、 交 叉 率 =0.3の は、10000世. 場合 に. 代 まで に生 成 さ れ た 個 体 の す べ. て が 制 約 式 を 満 た さな か った た め、 最 大 適 応 度 が ゼ ロ と な っ て い る。 以 上 の こ と か ら、 対 象 とす る問 題 は、制 約 条 件 が きわ めて 厳 しい た め 、 制 約 条 件 を ペ ナ ル テ ィ と して 適 応 度 関 数 に組 み 込 ん だSGAを. この 問題 で は、 制 約 式 の係 数 値 や 右 辺 定 数 の 符 号 が正 負 混 在 して い る た め 、 坂 和 ら[8],. の 改 善 が な か な か 進 ま な い こ と が 推 測 で き る。 こ れ に 対 して 、 ラ ン ダ ム0-1反 転 法 を 組 み 込 ん だSGAの. [9]の 二 重 構 造 の ス ト リングやBean[1]の ラ ン ダ ムキ ー に よ る方 法 は適 用 で き な い こ と. リ ズ ム の ス テ ッ プ3を3'に. =0. まず、 この 問 題 に対 して、 単 純 遺 伝 的 ア ル ゴ リズ ム(SGA)を. ア ル ゴ リ ズ ム(SGAの. 全 く 同 じ 条 件(個. に注意 しよ う。. 以 下 の 条 件 の も とで 適. 用 した。 制 約 式 を ペ ネ ル テ ィ項 と して 目 的関. 直 接 適 用 して も、 解. .01)と. 体 数100個. アル ゴ. 置 き 換 え る)を. 、. 、 突 然 変 異 率. して 、 交 叉 率 を0.1か. ま で0.1ず つ 変 更 し た 場 合 の 結 果 を 表2に. ら0.9 示. す。. 数 に組 み込 む ため、 適応 度 関数 を(4)式で定 義 し、 個 体数100個 、 突 然 変 異 率 最 大 世 代 数10000と. 、. して 、 交 叉 率 を0.1か. この 表 か ら、 きわ め て 小 さ な世 代 で、 しか も、 す べ て の交 叉 率 に対 して 、 真 の最 適 目的 関 数 値(0.492418)に. 到 達 して お り、 表1の.
(7) 表2 . ラ ン ダ ム0-1反 転 法 に よ る適 用結 果. 交 叉 率Pc. 最適解F( ）. 最適解が得 られ る世代. 0.1 0.2 0.3 0.4. 0.492418. 42 44 44. 0.5 0.6 0.8. 0.492418 0.492418 0.492418 0.492418. 0.9. 0.492418. 0.492418 0.492418 0.492418. 0.7. Learning",Addison-Wesley,(1989). [4] . Herrera, . F., . Zimmermann, . Fuzzy . 32 16 30 31. J.L. . H.-J.:"Boolean . ing Problems . 35 35. Verdegay, . with . Sets and . and. Programm-. Fuzzy . Constraints",. Systems,55, . pp.285-293. (1993). [5]Herrera,F:and Models . Verdegay,J.L.:"Three. of Fuzzy . gramming", . European . 結 果 と比 較 す れ ば、 提 案 す る アル ゴ リズ ムが. Operational . た い へ ん有 効 で あ る こ とが 理 解 で き る。. (1995).. Programming . Fuzzy costs:A. そ の係 数 や右 辺 定 数 の符 号 は任意 で あ るよ う. pp.57-76(1996). Z.:"Genetic . Second . Springer-Verlag(1994).. 手 法 を提 案 した。 ま た、 提 案 した手 法 を広 告. [8]坂. 媒 体 選 択 問 題 に適 用 し、 従 来 のSGAに. よる. J.L.:"Fuzzy with Sets. Algorithms. Structures=Evolution . grams", . 和,乾. 口,砂. of. pp.581-593. Study",Fuzzy . [7]Michalewicz, . 伝 的 ア ル ゴ リズ ム に基 づ く フ ァ ジィ意 思 決 定. Pro-. Problems . General . and Systems,81, . 十Data . な フ ァ ジー多 目 的0-1計 画 問題 に対 して 、 遺. 83, . F. and Verdegay, . Boolean . 本 論 文 で は、 制 約 式 はす べ て 線形 関数 で、. Linear Journal . Research, . [6]Herrera, . お わ りに. Integer . Pro-. extended . 田 、 澤 田:"改. edition,. 良型 遺 伝 的 ア. ル ゴ リ ズ ム に よ る フ ァ ジ ー 多 目 的 組 合 せ 最 適 化", 日本 フ ァ ジ ー 学 会 誌,6(1)pp.177.186(1994).. 方 法 と比 較 して き わ め て効 果 的 で あ る こ とを. [9]坂. 示 した。 ラ ンダ ム0-1反 転 法 は、 ヒ ュ ー リス. 問 題 に対 す る改 良 型 遺 伝 的 ア ル ゴ リズ ム に よ る. テ ック な手 法 で は あ る が、 現 在 の と ころ、 係. 対 話 型 フ ァ ジ ー 満 足 化 手 法",日. 和,加. 藤,砂. 田 、 園 田:"多. 目 的0-1計. 画. 本 フ ァ ジ ー学 会. 誌,7(2)pp.361-370(1995).. 数 の 符 号 が 正 負 混 在 す る よ うな線 形 制 約 式 を 持 つ0-1最 適 化 問 題 に対 して、 遺 伝 的 ア ル ゴ リズ ムを適 用 す るた め の有 効 な手 法 と思 わ れ. [10]田. 口,玄,井. 田:"遺. る 多 目 的 非 線 形 整 数 計 画 問 題 の 一 解 法",信. 学会. 論(A),J79-App.1221-1223(1996). [11]Ulungu,E.L. . る。. 伝 的 ア ル ゴ リズ ム に よ. objective . and Teghem,」.:"MultiCombinatorial . Problems:A. Survey", . Criteria . Decision . Optimization Journal . Analysis,3, . of Multipp.83-104. (1994).. 注. [12]Wiedey, [1]Bean, . J.C.:"Genetic . Algorithms . "Media Random . Keys . for . Optimization",ORSA . Sequencing Journal . and. on Comput-. ing,6(2),pp.154-160(1994). [2]Bellmann, "Decision . Making . ment",Management . and . Zadeh, . in a Fuzzy . L.A.: Environ-. Science,17, . pp.141-164. (1970). 3]Goldberg, in Search, . D.E.:"Genetic Optimization, . Algorithms and . Machine. Selection . gramming", Research (1978).. R.E. . G. and Zimmermann, . H.-J.:. and. and Fuzzy . Journal Society,29 . Linear . Pro-. of the Operational (11), pp.1071-1084.
(8)
関連したドキュメント
「聞こえません」は 聞こえない という意味で，問題状況が否定的に述べら れる。ところが，その状況の解決への試みは，当該の表現では提示されてい ない。ドイツ語の対応表現
介護問題研究は、介護者の負担軽減を目的とし、負担 に影響する要因やストレスを追究するが、普遍的結論を
Hungarian Method Kuhn (1955) based on works of K ő nig and
of IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp..
・逆解析は，GA（遺伝的アルゴリズム）を用い，パラメータは，個体数 20，世 代数 100，交叉確率 0.75，突然変異率は
基本的金融サービスへのアクセスに問題が生じている状態を、英語では financial exclusion 、その解消を financial
教育現場の抱える現代的な諸問題に応えます。 〔設立年〕 1950年.
優越的地位の濫用は︑契約の不完備性に関する問題であり︑契約の不完備性が情報の不完全性によると考えれば︑
