Side-trip Distanceを用いたStackelberg型配置問題への遺伝的アルゴリズムの応用
20
0
0
全文
(2) 第58巻 1は. 第3号. 本 論 文 で は,先 る 。 こ れ は,平. じめ に. 手 後 手 の 区 別 の あ るStackelberg型. 面 上 の 市 場 に お い て,顧. の 競 合 施 設 配 置 問 題 につ い て 考 察 す. 客 獲 得 に よ る 利 得 最 大 化 を 目 的 と し た2者. の 出店. 競 争 をモ デ ル 化 した も の で あ る。 2者 に よ る 競 合 施 設 配 置 問 題 は,直. 線 上 の 市 場 に お け る 配 置 競 争 を 論 じ たHotelling[1]. の モ デ ル か ら考 え ら れ 始 め た 。Hakimi[2]は1983年. に ネ ッ トワー ク上 で この 問 題 を考 察. し,次. の2つ. の 問 題 を 定 式 化 し た 。 既 存 施 設 に 対 抗 す る 最 適 配 置 を 求 め るMedianoid問. と,後. か ら競 合者 が最 適 配 置 を行 う こ とを 考慮 に 入 れ た上 で 自 己の 施 設 の最 適 配 置 を求 め. るCentroid問. 題 で あ る 。Centroid問. 量 がNP-hardと そ の 後,競. 題 の 解 はStackelberg型. の 解 と な る が,η. 題. 点 で は計 算. な る こ とが示 され て い る。 合 施 設 配 置 問 題 に お い て,場. 所 ・施 設 ・顧 客 ・距 離 な ど に 関 す る さ ま ざ ま な. 性 質 を モ デ ル 化 した 多 様 な 問 題 が 考 察 さ れ て き た[3]。 競 合 関 係 に つ い て は,施 合 だ け で は な く,施. 設 同士 の競. 設 の 設 置 主 体 と住 民 と の 利 害 関 係 の 競 合 を 扱 っ た も の も 研 究 さ れ て い. る[4]。 こ れ ま で 顧 客 の 選 好 に つ い て 最 も よ く 用 い ら れ て き た 仮 定 は,顧 つ だ け を 利 用 し,か. つ,そ. の 施 設 が 遠 く て も 利 用 す る,と. デ ル は ゼ ロ 和 ゲ ー ム と な り,競 結 す る 。 し か し,フ の よ う に,顧 か な い,と. 客 は 最 も 近 い 施 設 を1. い う も の で あ る。 こ の よ う な モ. 合 他 者 の 顧 客 を 減 らす こ と が 自 己 の 顧 客 を 増 や す こ と に 直. ァ ー ス トフ ー ド店,コ. ン ビ ニ エ ン ス ス トア,コ. ー ヒ ー チ ェ ー ン店 な ど. 客 は 近 く て 便 利 な 位 置 に あ る 場 合 だ け 施 設 を 利 用 し,遠. い う タ イ プ の 施 設 も あ る 。 本 論 文 で は,こ. けれ ば わ ざわ ざ 出向. う した性 質 を もつ施 設 の競 合 配 置 問. 題 を 考 察 す る。 さ ら に,本 は,多. 論 文 で は,side-tripdistanceと. い う新 し い 距 離 の 概 念 を 導 入 し た 。 都 市 部 で. くの 人 は 通 勤 通 学 な どで 毎 日 の よ う に 自 宅 と最 寄 り駅 を 周 回 す る。 そ し て,そ. へ の 行 き 帰 りに,つ. い で に 上 記 の 施 設 を 利 用 す る,と. い う行 動 を と る。 こ の よ う な. 道 」 で 利 用 さ れ る タ イ プ の 施 設 ま で の 距 離 を 表 す た め,自. 宅 と 周 回 点 と施 設 の3点. の駅 「 寄 り を使 っ. て 施 設 まで の距 離 を定 義 す る。 ま た,人. に よ っ て 距 離 感 は 異 な る の で,施. ま 用 い る の で は な く,遠 す な わ ち,最. 設 ま で の 物 理 的 なside-tripdistanceを. そのま. い と感 じ る度 合 い で 施 設 を 利 用 す る か 否 か を 決 定 す る と仮 定 し た 。. 寄 りの 駅 に は 必 ず 行 く も の と し,そ. を選 んで 利 用 す る とい うモ デル を考 え る。. 16(566). の 途 中 で な る べ く 「近 い 」 と感 じ る 施 設.
(3) Side-tripDistanceを. 用 い たStackelberg型. 各 企 業 は 提 携 は せ ず,お て,施. 互 い に 自己 が獲 得 で き る利 得 を最 大 に す る こ とだ け を 目的 と し. 設 の 配 置 を 決 定 す る 。 こ こ で,先. こ と を 知 っ て い る の で,最 に 入 れ た 上 で,最. 配 置 問題 へ の遺 伝 的 ア ル ゴ リズ ム の応 用(大 角). 手企 業 は競 合 企 業 が あ とか ら参 入 して くる と い う. 初 に 施 設 を 配 置 す る 際 に,後. 手 企 業 が 参 入 して くる こ とを考 慮. 終 的 な 自分 の利 得 が 最 大 に な る よ うに配 置 を決 定 せ ね ば な らな い。 遠 い. と感 じ る 顧 客 が 施 設 を 利 用 し な い と い う仮 定 の た め,こ. の モ デ ル は 非 ゼ ロ 和 ゲ ー ム と な り,. 競 合 者 の 顧 客 を 奪 う こ と が 必 ず し も 自 己 の 顧 客 を 増 や す こ と に つ な が ら な い 。 換 言 す れ ば, 先 手 に 関 し て,後. 手 と 「 潰 し合 い 」 に な ら な い よ う に,あ. 所 を 空 け て お く こ と で,結. えて 後 手 が 有 利 に な る よ うな場. 果 的 に先 手 が 有 利 に な る よ うな場 合 が 生 じる。 この よ うな具 体. 例 に つ い て は 大 角[5]で 示 さ れ て い る。 競 合 関 係 に あ る 複 数 施 設 に つ い て の 配 置 問 題 に つ い て は,数 が 困 難 な 問 題 や,数 そ の た め,本. 値 計 算 に お い て実 用 的 な 時 間 内 に解 が 得 られ な い 問 題 が 少 な くな い。. 論 文 で は,ヒ. ム(GeneticAlgorithm,以 に よ っ て1975年 を 使 っ て,確. ュ ー リス テ ィッ ク な 近 似 ア ル ゴ リ ズ ム で あ る 遺 伝 的 ア ル ゴ リズ 下GA)を. 応 用 す る こ と い う ア プ ロ ー チ を と る 。GAはHolland. に 提 案 さ れ た 最 適 化 の 手 法 で,選. 択 淘 汰 ・突 然 変 異 と い う生 物 進 化 の 原 理. 率 的 探 索 に 学 習 の 要 素 を 入 れ た 最 適 化 の た め の ア ル ゴ リズ ム で あ る 。 す で に. 一 般 の 施 設 配 置 問 題 へ の 応 用 も あ る が[7][8][9][10] い 。 特 に,本. 理 的 に 厳 密解 を求 め る こ と. ,競 合 施 設 配 置 問 題 へ の 応 用 は ま だ 少 な. 論 文 の よ うに先 手 後 手 の 区 別 の あ る競 合 施 設 配 置 問 題 へ の応 用 は ま だ見 られ. ない 。 本 論 文 で は,Stackelberg型 い て,GAを. の 配 置 問 題 の う ち,従. 用 い て 近 似 解 を 求 め,厳. 来 列挙 法 で しか解 け な か った 問題 につ. 密 解 との 比較 で そ の有 効 性 を示 す。. 2モ. デ ル と定 式 化. 平 面 上 に需 要 点(顧 客)と 周 回 点 が離 散 的 に分布 して い る もの とす る。 以 下 の よ うな仮 定 を設 け る。 1.先 手 企 業 と後 手 企 業 が順 に1つ ず つ施 設 を配 置 す る。 2.顧 客 は施 設 が 近 い と感 じる場 合 のみ,そ の 近 さに応 じた割 合 で 利 用 す る。 3.顧 客 は よ り近 い と感 じる方 の施 設 だ け を利用 す るが,同 じ近 さ と感 じる施 設 は均 等 に 利 用 す る。. 一17(567)一.
(4) 第58巻 4.顧. 客 は 最 も 近 い 周 回 点 を 利 用 す る も の と し,そ. distanceを. 5.地. 第3号 の 最 短 経 路 か ら外 れ た 距 離side-trip. 施 設 まで の 距 離 の 尺度 に用 い る。. 代 は周 回点 に近 い ほ ど高 くな る。. 各 企 業 の 目 的 は,各. 自 の 利 得 の 最 大 化 で あ る 。 た だ し,利. 購 買 力 の 合 計 か ら地 代 を 引 い た も の と す る。 ま た,需. 得 は 各 需 要 点 か ら獲 得 で き る. 要 点 は 離 散 的 に 分 布 し て い る が,施. 設 を配 置 可 能 な場 所 は平 面 上 の 任 意 の 点 で あ る。 以 下 の よ うな記 号 を用 い る。. p活. 需 要 点(1<乞. 競. 需 要 点p歪 の 重 み. 諮,〃. 先 手 後 手施 設 の位 置. 53周. 以 下,本. Voronoi令. 回 点(1≦. く η). ブ ≦m). モ デ ル の 定 式 化 の た め の 定 義 を 行 う。. 頁域:. 周 回 点 集 合{51,…,5m}に. つ い て,あ. る 周 回 点5フ のVoronoi領. 域 を 以 下 の よ う に定 義. す る。. V(8ゴ)={qld(q,5ゴ)d(q,5た)}f・ral1鳶,ん. た だ し,dは. ≠ ブ. 後 述 す る 距 離 関 数 で あ る。. こ の と きp乞 が 利 用 す る 周 回 点8(pの. は,p乞 が 含 ま れ るVoronoi領. 域 のVoronoi母. り,以 下 の よ う に 表 せ る 。. 点で あ. 8(Pの 一{8ゴIP歪 ∈y(53)}. Side-tripDistace: p歪 か ら ω ま で のside-tripdistanceを. 以 下 の よ う に定 義 す る。. 8蝋P②,勾=d(P琶,勾+d@,θ(Pの)-d(Pわ. θ(Pの). こ こ でdは,P=(p1,p2),Q=(g1,q2)と. d(P,Q)一{IP1-qllp+IP2-q21p}石. す る と,以. ユ 18(568). 下 の よ うな距 離 関数 を表 す。.
(5) Side-tripDistanceを Side-tripdistanceで. 用 い たStackelberg型 は,あ. の 場 合 は 八 角 形,p=2(ユ とす る が,第4節. 配 置 問題 へ の遺 伝 的 ア ル ゴ リズ ム の応 用(大 角). る 点 か ら等 距 離 の 点 の 集 合,す. な わ ち 円 は,p=1(直. 角 距 離). ー ク リ ッ ド距 離)の 場 合 は 楕 円 の 形 状 に な る 。 本 論 文 で はp=2. で 述 べ る よ う に,GAの. 性 能 を 評 価 す る テ ス ト問 題 に お い て はp=1と. して 厳 密 解 を 求 め る 。. 近 さ: 需 要 点 α乞か らの 「 近 さ」の度 合 い を表 す 位 置 の フ ァジィ集 合 を考 え,そ の 帰属 度 を以下 の メ ンバ シ ップ関 数 μ鵡 で 特性 づ け る。 す な わ ち,需 要点 砺 か らあ る点 ω まで の 「近 さ」 を 8掘(P乞,勾. 楓@)一. ,γ1乞. ≦ γ1乞. く5畝Pμ)<γ2乞. otherwise. で 表 す 。 γ1乞,γ2乞 は そ れ ぞ れ 需 要 点 に 付 随 す る 距 離 で あ る 。 μ瓦@)=1は 何 の 抵 抗 も な く十 分 近 い と感 じ る こ と を 示 し,μ 瓦@)=0は. ∬ ま で の 寄 り道 に. 近 い と は ま っ た く感 じ な い(遠. す ぎ る)と 感 じ る こ と を 示 す 。. 選 好 と 利 得: 先 手 ∬ と後 手 〃が 配 置 後 に,ω. μ鵡@)ω 言,楓@)〉. μ瓦 ω). 去μ鵡@厩. μ瓦 ω. 9面@,〃)=. μ瓦@)一. o,μ こ こ で,μ 瓦@)=μ 伽@認)=0と 従 っ て,飢. が 砺 か ら獲 得 す る 利 得 を 次 の よ う に 定 義 す る 。. 瓦(勾 く 楓 ω) 一ω)=1な. らg。,、@,㌢)=去 砺 で あ る が,μ 瓦@)=μ. な る。 が 全 需 要 点 か ら獲 得 す る 利 得 は 以 下 の よ う に 表 せ る 。 れ. 砺鞠)一 Σ 偏 鋤 ②=1. 影 に つ い て も 同 様 にgμ,σ 〃 を 定 義 す る。. 地 代: 施 設 を 配 置 す る 場 所 の 地 代 に つ い て,以. 1.周. 回 点8ゴ のVoronoi領. 域y(8ゴ)内. 下 の よ うな仮 定 を設 け る。. で は8ゴ に 近 い ほ ど 高 い. 一19(569)一. 瓦 ω)=0な. ら.
(6) 第58巻. 第3号. 2.周. 回 点8ゴ か らRゴ 以 上 離 れ る と地 代 は 下 が ら な い. 3.周. 回 点8ゴ 上 に お け る 地 代 は,V(8ゴ)内. た だ し,施. の 需 要 量 に依 存 す る. 設 か ら周 回 点 ま で の 距 離 に は,5掘. で は な く4を. 用 い る。. 8ゴに 集 ま る 需 要 量 は 以 下 の よ う に 表 せ る 。. 鴨. 一 Σ. ω・f・ ・allp・. ∈V(・ ゴ). 歪. 5ゴに お け る 地 代 係 数 をcゴ,最. 0@)一. 小 の 地 代 係 数 をCoと. し,あ. 鴨 ・×max{cプ(1-4@,5ゴ)/Rゴ),Co},5プ. る地 点 ωに お け る地 代 を. ∈8@). と 表 す も の と す る。 地 代 を引 い た最 終 的 な先 手 ωの利 得 は. 場@,9)=0臼. じ@ラ宮)-0@). と な る。 影につ い て も 同様 に 馬 を定 義 す る。. 先 手 後 手 の あ る 競 合: あ る ω に 対 す るyの. R"@)一. 最 適 反 応 戦 略(純 戦 略)が 唯 一 に 定 ま る と す る と,. 惚*陽@,9*)-max馬@,宮)} 〃. と表 せ る。諮 に対 す る 宮の 最適 反 応 戦 略 集 合 を. D,一{(矧1諮. ∈ π2,9∈R,@)}. と 表 す 。 こ の と き,oじ*と. ガ が次 の関 係. 凡@*,ツ*)= @瓢. 凡@,〃),ツ*∈R〃(ω*). を 満 す な ら,ω*,g*はStackelberg均. 衡 に あ る と い う。. 以 上 の よ う な 仮 定 と記 号 の も と で,本. Medianoid問. Centroid問. 題:あ. 題:〆. 論 文 で 扱 う 問 題 は 次 の2つ. るoじに 対 し て 〃*す な わ ちR〃@)を. を求 め る問 題. 20(570). に定 式化 で き る。. 求 め る問 題.
(7) Side-tripDistanceを. 用 い たStackelberg型. 配 置 問題 へ の遺 伝 的 ア ル ゴ リズ ム の応 用(大. 角). 先 手 ω は,後 手 が 最 適 反 応 戦 略 を 採 る こ と を 考 慮 に 入 れ た 上 で 自 己 の 最 適 配 置 を 決 定 す る 必 要 が あ る た め,Medianoid問 問 題 の 解 ゲ は,先. 題 よ り もCentroid問. 手 ω に 最 低 限g￠(ω*,〃*)だ け の 利 得 を 保 証 す る,と. と に 注 意 す る 必 要 が あ る 。 こ の 解 は,後 の で あ る か ら,後. 題 を 解 く方 が 難 しい 。 こ こ で,Centroid い う もの で は な い こ. 手 賀が 最 適 反 応 戦 略 ガ を採 る こ と を 前 提 と し た も. 手 が ラ ン ダ ム な 位 置 に 配 置 し た り,後 手 自 身 に 不 利 な 位 置 に 配 置 す る と. い っ た 非 合 理 的 な 行 動 に 出 る 場 合 に は,先. 手 がg、,@*,〃*)よ. り も 少 な い 利 得 しか 得 ら れ な. い と い う 結 果 と な り得 る 。. 3GAの. 適用. 前 節 で 定 義 した 問題 を数 理 的 に解 こ う とす る と,以 下 の よ うな 困 難 に行 き当 た る。 L最. 適 解 の 候 補 と して チ ェッ クす べ き各 需 要 点 の μ亙@)=1お. よび μ亙@)=0と. なる. zz. 境 界 が 楕 円 で あ る た め,そ の 交 わ り判 定 と境 界 で 囲 まれ た領 域 の列 挙 が 困 難 で あ る。 2.そ の領 域 が 最 悪 の 場 合0(2π)で 増 え る。 しか しGAを GAに. 使 えぼ,こ れ らの面 倒 な 問題 を回 避 す る こ とが で き る。. よ る問 題 解 法 の 一般 的 な流 れ は,以 下 の よ うな も の で あ る。. Step1.初. 期 個 体 集 団 の 生成:乱 数 を用 い て 最 初 の 世代 を生 成. Step2.適. 応 度(丘tness)の 評 価:各 個 体 につ い て 問題 へ の適 応 度 を評 価. Step3.選. 択:適 応度 に応 じて交 配 で き る親 個 体 を 選択. Step4.交. 叉:交 配 で 子孫 を残 す 際 に交 叉 率0で. Step5.突. 然 変 異:子 孫 の遺 伝 子 の一 部 が 突 然 変 異 率Mの. Step6.子. 孫 を次 の 世代 の親 と してStep2へ. Step2∼5の1回. 遺 伝 子 の 交 叉 が発 生. の繰 り返 しが1世 代 で,こ の 世代 交代 を繰 り返 しつ つ,各 世 代 の最 も. 適 応 度 の 高 い 個 体 の 遺 伝 子 を 問題 の解 とす る。GAは,こ が 大 きい 。 以 下,本 論 文 の配 置 問 題 をGAで. 3.1遺. 割 合 で変 化. の基 本 的 な考 え方 以 外 は 自 由度. 扱 え る よ うに考 え る。. 伝 子 コー デ ィ ング. 表 現 型(phenotype)に 規 定 さ れ る 空 間 をGA空. よ っ て 規 定 さ れ る 問 題 を 問 題 空 間,遺 間 と呼 ぶ 。 問 題 空 間 か らGA空 21(571). 伝 子 型(genotype)に. よって. 間 へ どの よ う に 対 応 付 け る か を 遺.
(8) 第58巻. 第3号. 伝 子 コー デ ィ ング と呼ぶ 。 こ こ で は,施. 設 を 配 置 す る 位 置 を 求 め る こ と が 目 的 で あ る か ら,あ. るひ とつ の位 置 をひ. と つ の 個 体 と して 表 す こ と に な る。 位 置 の 座 標 値 を 表 す 表 現 型 と し て16ビ 数 を 用 い る 。 こ れ は0か. ら65535ま. で の 整 数 を 表 す こ と が で き る の で,1メ. の 精 度 の 問 題 お よ び 解 を 考 え る な ら ば,65.5km四 して 大 阪 府 の 約2.3倍,ニ. 分 な 広 さ で あ る。 ま た,2012年. 解 像 度 で あ るwQxGA規. 標 用 に16ビ. ビ ッ ト符 号 無 し整 数 の を,以. Grayコ. 下 に 述 べ るGrayコ. 市 部 で の配 置 を. の解 像 度 を持 つ 。 の 遺 伝 子 を持 つ こ と に な り,こ の16. ー ド を用 い て 遺 伝 子 型 に 変 換 す る。. ー ド:. コ ン ピ ュ ー タ 内 部 の2進 ビ ッ トの 数,す. 数 に よ る 符 号 無 し整 数 表 現 で は,隣. な わ ち ハ ミ ン グ 距 離(Hammingdistance)は. で 隣 り合 う1と2と3は,2進 ハ ミ ン グ距 離2,2と3で. 数 で2桁. 質 を 持 つGrayコ. ー ドgを. し く な い 。GAで. 数. あ り,1と2で. は. は 一 般 的 に ビ ッ ト単 位. る 値 と 隣 接 す る 値 の ハ ミ ン グ 距 離 が 常 に1で. ー ド と の 相 互 変 換 を 行 う に は,次. あ る と い う性. の 関 係 を 用 い れ ぼ よ い 。 す な わ ち,. 数 わを 最 上 位 桁 か ら順 に 砺_1々_2,…,わ1,60と 最 上 位 桁 か ら順 にg4_1,g乏_2,…,g1,90と. 偽一{1∴∴ で あ る 。 た だ し,㊦ な お,Grayコ. 一 定 で は な い 。 例 え ぼ10進. ー ドを用 い る 方 が望 ま しい と考 え られ て い る。. 2進 数 か らGrayコ ビ ッ ト長4の2進. り合 っ た 数 値 の 問 で 異 な る. で 書 く と そ れ ぞ れ01,10,llで. は ハ ミ ン グ 距 離1で,等. で 遺 伝 子 を 変 化 させ る の で,あ. Grayコ. ッ ト固 定 長 の2つ. で,都. 現 在 で の 市販 デ ィス プ レイ の最 高. 格(解 像 度2560×1600)の1024倍. 各 個 体 は ω座 標 とy座. ー トル 単 位 で. 方 の領 域 をカバ ー で きる。 これ は面 積 に. ュ ー ヨ ー ク ・マ ンハ ッ タ ン地 区 の 約49倍. 問 題 に す る場 合 に は,十. ッ ト符 号 無 し整. し,同. じ く ビ ッ ト長4の. す る と,. 二. は排他 的論 理 和 を表 す。. ー ドは,隣. 接 す る 値 の ハ ミ ン グ 距 離 が1で. あ る こ と を 保 証 す る だ け で,1. ビ ッ トの 変 化 が 元 の 値 に 及 ぼ す 影 響 は 考 慮 さ れ て い な い 。 そ の た め,1ビ. ッ トの 変 化 が 元 の. 値 に 及 ぼ す 影 響 の 平 均 が 一 定 以 下 に な る よ う な 均 質 コ ー デ ィ ン グ[11]と. 呼ぼれるコーディ. ン グ方 法 も提 唱 され て い る。. 22(572).
(9) Side-tripDistanceを. 3.2適. 用 い たStackelberg型. 配 置 問 題 へ の 遺 伝 的 ア ル ゴ リ ズ ム の 応 用(大. 角). 応 度 と 選 択 方 法:. ル ー レッ トル ー ル あ る世 代 の個 体 集 団 に おい て,個 体 す べ て の 適 応 度(且tness)の 評 価 を行 い,そ れ を も と に交 配 す る こ との で きる個 体 を選 択 す る。 適応 度 に基 づ く選 択 方 法 は い くつ か考 案 され て い るが,本 論 文 で は ル ー レッ トル ー ル を用 い る。 す な わ ち,P個. の 個 体 集 団 の 中 の あ る個. 体 の 適 応 度 を ゐ で 表 す と き,そ の個 体 が選 択 され る確 率p活 は,. P琶=Σ. メ、. 仁. 、カ. で 与 え られ るも の とす る。 この ル ー レ ッ トル ー トル を用 い る際. 適 応 度 ゐ の値 をそ の ま ま選 択 確 率 に 反 映 させ るの. で はな く,ス ケ ー リン グ関 数 を適 用 した値 を使 うこ とも多 い 。 しか し,本 モ デ ル で は,利 得 関 数 の値 は0≦. 馬,馬. ≦ Σ7競. の範 囲 に収 ま り,値 を補 正 す る必 要 性 も薄 い た め,ス. ケー リング関 数 を通 さず 凡,馬 の値 をそ の ま ま ゐ と して 用 い て選 択確 率 を計 算 す る も の と す る。 な お,本 論 文 で は,全 世 代 を通 して 個 体 数 は一 定 と考 え る。 す なわ ち,1回 の 親 か ら2つ の子 が生 まれ て 次 の 世 代 に移 行 す る。 従 って,1世. の交 配 で2つ. 代 あ た りの交 配 はP/2回. 起 き る こ とに な り,そ の た び に ル ー レッ トル ー ル で親 が 選 択 され る。 適 応度 の高 い個 体 は, 1回 の 世 代 交 代 の 問 に 複 数 回 の 交 配 に 選 択 さ れ る 可能 性 が あ る 一方 で,適 応 度 が0の 個 体 は子 孫 を残 せ ず1世 代 で 死 滅 す る。. エ リー ト保 存 戦 略: あ る世 代 の個 体 集 団 の 中で 最 も高 い 適応 度 を持 つ個 体 につ い て は,ル ー レ ッ トル ール を 適 用 せ ず 必 ず 選 択 して 交配 させ る,と い う戦 略 が エ リー ト保 存 戦 略 で あ る。 一 般 に用 い られ る エ リー ト保 存 戦 略 で は. ,エ リー ト遺 伝 子 は後 述 す る 交 叉 や 突然 変 異 か. らも免 れ,遺 伝 子 は そ の ま ま子 に コ ピー され る。 この戦 略 を採 用 す る と,そ の世 代 の最 良 の 解 が 交 叉 や 突 然 変異 に よ って 破 壊 され な い とい う利 点 が あ る。 しか し一 方 で,エ. リー ト. 遺 伝 子 が 集 団 中 に急 速 に広 が り局 所 解 か ら抜 け に く くな る可 能 性 も出 て くる。 本 論 文 の モ デ ル で は,局 所 解 を与 え る領 域 が 多数 あ る こ とが 見 込 まれ る た め,実 装 に あ た って は,エ リー ト個 体 は必 ず 選 択 され るが非 エ リー ト同様 に交 叉 や 突 然 変異 の影 響 も受 け る とい う,現 実 の生 物 進 化 に近 づ け た 弱 エ リー ト保 存 戦 略 とい うも の を考 え,用 い る こ とに した 。 この戦 略 の有 効 性 は,第4節. の数 値 実 験 結 果 で 示 され る。 23(573).
(10) 第58巻 3.3交. 第3号. 叉 と突 然 変 異. 選 択 され た親 個 体 の遺 伝 子 を子 個 体 の 遺 伝 子 に コピ ーす る際,通 常 は親 の遺 伝 子 を その ま ま子 の 遺伝 子 に コ ピー す る。 ただ し,確 率0で. 以 下 の よ うな親 同士 の遺 伝 子 の 交叉 が 起. こ り,そ の結 果 が 子 に コ ピー さ れ る。 ま た,子 の 遺伝 子 に は確 率Mで これ らがGAの. 特 徴 で あ り,最 適 な0,Mの. 突 然 変 異 が起 こ る。. 値 は数 値 実験 を通 して経 験 的 に決 め て い くの. が一 般 的 で あ る。 な お,交 叉 と突 然 変 異 は 排他 的 に起 こ るわ けで はな い。. 交 叉: 長 さ 乏の 固 定 長 の ビ ッ ト列 で 表 現 さ れ た 遺 伝 子 α,bが あ り,最 上 位 桁 か ら順 に α乏_1,α乏_2, …. ,α1,αoお よ び わ乏_1,わ6_2,…,わ1,boと. す る。 こ の と き,乱. 数 で 決 め た2つ. の 整 数 ￠,ゴ(0≦. 乞≦ ブ く の を 使 い,. 砺. と 砿 の 値 を 交 換forallκ,乞. の 操 作 を 行 う こ と が2点 ぶ 。 本 論 文 で は,2点. ≦ κ≦ ブ. 交 叉 で あ る 。 乞だ け を 決 め て ブ=4-1と. す る 場 合 は1点. 交 叉 と呼. 交 叉 を 用 い る。. 1つ の 個 体 は ∬,賀座 標 そ れ ぞ れ に つ い て 遺 伝 子 を 持 っ て い る の で,こ ま と め て か ら 交 叉 を 行 う こ と も 考 え ら れ る が,ス 本 論 文 で は そ れ ぞ れ 別 々 の 遺 伝 子 と し て 扱 い,確. キ ー マ タ(schemata)の 率0で. れ を1本. の 染色 体 に. 保 存 の 観 点 か ら,. い ず れ か 一方 のみ 交 叉 を行 わ せ て. い る。. 突 然 変 異: 長 さ4の …. 固 定 長 の ビ ッ ト列 で 表 現 さ れ た 遺 伝 子 αが あ り,最 上 位 桁 か ら順 に α4_1,α4_2,. ,α1,αoで あ る と す る。 こ の と き,乱. 数 で 決 め た 整 数 双0≦k4)を. 使 い. 砺一{1:に1 とす るの が 最 も一般 的 な 突然 変 異 で あ り,本 論 文 で も これ を採 用 す る。 そ の他,あ. る範 囲. を変 化 させ る摂動 や,要 素 を入 れ 替 え る逆位 ・転 座 や,遺 伝 子 長 を変 化 させ る も の な どが 考 え られ て い る。. 24(574).
(11) Side-tripDistanceを. 用 い たStackelberg型. 配 置 問 題 へ の 遺 伝 的 ア ル ゴ リ ズ ム の 応 用(大. 4GAの. 4.1GAの. 角). 実 装 と 数 値 実 験. 実装. 実 装 に あ た っ て 重 要 な 点 は,滋,宮 の2点 定 問 題 で あ れ ば,偽. 同 時 決 定 で は な い,と. 〃 そ れ ぞ れ の 位 置 の 座 標 を ま と め て1本. す れ ば 良 い だ け で あ る 。 し か し,そ. れ で はMedianoid問. い うこ とで あ る。 同時 決. の 染 色 体 と し て,GAを. 題 やCentroid問. 適用. 題 の 解 を求 め る. こ と に はな らな い。 Medianoid問. 題 に つ い て は,あ. る 認 に つ い て 動@,の. で あ る か ら,ω を 定 数 と考 え る と 影 に つ い てGAを 問 題 に つ い て は,後. 手gの. 適 配 置R〃@の. ず ω に 対 す る 馬@)を. 求 め る た め に は,そ. を 求 め る た め に もGAを. 位 置 を求 め るの. 適 用 す る だ け で 良 い 。 しか し,Centroid. 位 置 が 決 ま ら な け れ ば 罵@,g)の. す る ∬ を 求 め る た め に は,ま 大 に す る 諮 をGAで. を 最 大 に す るgの. 値 が 確 定 しな い 。 罵 を 最 大 に. 求 め る 必 要 が あ る 。 す な わ ち,凡. の 過 程 で,1世. 代 中 の1個. を最. 体 のoじ、に 対 す る 〃 の 最. 適 用 し て い く必 要 が あ る。 こ れ は す な わ ち,GAを. 再 帰 的 に適 用 す る とい うこ とで あ る。 Centroid問 あ る が,実. 題 を 解 く に あ た っ て は,2段 装 に あ た っ て は,状. 階 で 再 帰 的 にGAが. 使 え る よ うに すれ ぼ十 分 で. 態 ス タ ッ ク を 自 前 で 用 意 す る こ と に よ り,メ. モ リの許 す 限. り何 段 階 で も 再 帰 的 に 呼 び 出 せ る よ う に し た 。 実 装 はC言. 語 で 行 な っ た 。 開 発 ・実 行 環 境 は 以 下 の 通 りで あ る。 ハ ー ド ウ ェ ア:ThinkPadX200s,4GBRAM IntelCore2DuoL96002.13GHz OS:LinuxMicroknoppix2.6.31.6 コ ン パ イ ラ:gcc(Debian4.3.4-6)4.3.4. な お,コ. ンパ イ ル 時 に は最 適 化 オ プ シ ョ ンは付 け て い ない 。. 疑 似 乱 数 に つ い て: GAで. は乱 数 を 多 用 す る が,疑 似 乱 数 に つ い て は,gccの. を 用 い た 。 こ れ は,64ビ で248=約280兆. ッ トの 線 形 合 同 法 で 演 算 を行 い,そ. 回 の 合 計5回. の う ち48ビ. の 周 期 を持 つ 。 今 回 の 数 値 実 験 で のdrand480の. 1個 の デ ー タ の 生 成 に3回(座 判 定 に1回,交. 標 準 関 数 で 移 植 性 が 高 いdrand480. 標 値2つ. 叉 の 位 置 決 定 に2回,突 で あ る 。Centroid問. と購 買 力),GAで. の1個. 呼 び 出 し 回 数 は,需 体1世. 然 変 異 有 無 の 判 定 に1回,突. 題 を 解 く に はGAを 25(575). ッ トを 使 用 す る の 要点. 代 につ き交 叉有 無 の 然 変 異 の 位 置 決 定 に1. 再 帰 的 に 呼 び 出 す の で,個. 体 数Pで.
(12) 第58巻. 第3号. 始 め σ 世 代 目 の 最 良 の 解 を 得 る ま で に,3η+5P2σ2回. のdrand480の. 呼 び 出 しが 必 要 で あ. る 。 以 下 の 数 値 実 験 で は,最. も繰 り返 し回 数 が 多 い パ タ ー ンで,η=100,P=50,σ=200. で30回. の 場 合 で もdrand480の. 繰 り返 して お り,こ. ら,280兆 は,メ. GAを. 回 で あ るか. の 周 期 は 十 分 な 長 さ で あ る 。 呼 び 出 し 回 数 が そ れ を 超 え る と見 込 ま れ る 場 合 に. ル セ ン ヌ ・ツ イ ス タ[13]な. 4.2テ. 呼 び 出 し 回 数 は 約150億. ス ト問 題 に よ るGAの. ど を 利 用 す る 必 要 が あ る。. 性能評価. 用 い る場 合,何 世 代 目で どの程 度 の近 似 解 が得 られ るの か を 評価 す る必 要 が あ る。. しか しそ もそ も厳 密 解 がわ か らな い 問題 に対 してGAを. 用 い るの で あ るか ら,そ の ま まで. は解 の 精 度 は 評価 で きな い。 そ こで まず,厳 密 解 が 求 め られ る よ うに 元 問題 を単 純 化 した テス ト問 題 を用 意 し,元 問 題 に用 い るの と同 じGAを を推 定 す る。 また,GAの. 適 用 して,収 束 ス ピー ドと解 の 品質. 性 能 に大 き く影 響 す る交 叉 率0お. よび 突 然 変 異 率Mを. どの 程. 度 の 値 にす るか も,テ ス ト問題 を通 して 見積 も る必 要 が あ る。 こ こで は,元 問題 に お いて 以 下 の よ うな簡 易化 を ほ どこ した テ ス ト問題 を考 え る。. テ ス ト問 題 で の 簡 易 化:. 1.周. 回点 を考 えな い. 2.Side-tripdistanceを. 用 いない. 3.需 要 点 と施 設 問 の距 離 は 直角 距 離 を用 い る 4.近 さ関 数 を用 い な い 5.す べ て の 需 要 点 の 限 界距 離 が 同 じ 6.地 代 を考 えな い この 場 合,需 要 点 の 利 用 圏 を表 す 範 囲 が 同 じ大 きさ の正 方形(直 角 距 離 で の 円)と な り, か つ,最 適 解 の ひ とつ はそれ ら正 方形 の辺 を境 界 とす る領 域 の端 点 に存 在 す る こ とが わ か っ て い る[6]。平 面 走 査 法[12]を 用 い た領 域 の 列挙 に よ り,正 方 形領 域 の重 な り領域 が得 られ る と とも に厳 密 解 の候 補 が 得 られ,そ の候 補 を線 形探 索 す る こ とに よ り最 適解 が 得 られ る。 この 列挙 法 に よ る計 算量 は,各 正 方形 の辺 で 区切 られ た領 域 几 の個 数 に依 存 す る。1つ の 閉 曲線 は平 面 を2つ の領 域 に分 割 す る か ら,一 般 に η個 の 閉 曲線 は平 面 を 最大2π 個 の領 26(576).
(13) Side-tripDistanceを. 用 い たStackelberg型. 配 置 問題 へ の遺 伝 的 ア ル ゴ リズ ム の応 用(大 角). 域 に 分 割 す る 。 し か し こ の 場 合 は 閉 曲 線 は 正 方 形 に 限 定 さ れ て い る た め,η が 追 加 さ れ た と き,既. 存 の π一1個. の 正 方 形 そ れ ぞ れ と 高 々2回 ず つ し か 交 わ ら ず2@-1). 個 の 領 域 が 新 た に 増 え る に す ぎ な い 。 従 っ て,領 Medianoid問 0@2)が. 題 を解 く に は,領. 域 恥. か か る。 ま た,Centorid問. 解 を 探 索 す る た め,0@2×. 個 目 の正 方 形. 域 数 の オ ー ダ ー は0(η2)で. を 線 形 探 索 す る の で,領. 題 に つ い て は,再. η2)=0@4)の. あ る。. 域 の 数 に 比 例 した 計 算 手 間. 帰 的 にMedianoid問. 題 を解 く こ と で. 計 算 手 間 が か か る。. 実 行 時 間: テ ス ト問 題 の 数 値 実 験 用 の デ ー タ と し て は,[0,1]×[0,1]の の 需 要 点 が 存 在 し,そ. れ ぞ れ の 需 要 点 は(0,1]の. 市 場 に,利 用 圏 の 半 径 γ,=0.1. 実 数 の 購 買 力 砺 を 持 つ も の と し て,π. 個. の 需 要 点 デ ー タ を 乱 数 で 生 成 した 。 図1は,π. を 横 軸 と して,列 挙 法(ENUM)とGAを. 問 題 の 解 を 得 る ま で に か か っ た 時 間(秒)の 数P=50,世. 代 数 σ=100で. 需 要 点400点. 用 い た 場 合 そ れ ぞ れ に つ い て,Centroid グ ラ フ で あ る 。 た だ し,GAに. の 場 合 の 実 行 時 間 は,GAが161秒,列. 間,2000点. で 約21日. 増 え な い の で,2000点. 体. 解 の 探 索 を終 了 して い る。 挙 法 は3040秒. 実 行 時 間 を 最 小 二 乗 法 に よ り η4で 近 似 す る と1.1457×10-7η4と は 約31時. つ い て は,個. な り,需 要 点1000点. か か る と 推 定 さ れ る 。 一 方,GAの. の 場 合 で も 約15分. で あ った 。列 挙 法 の で. 実 行 時 間 は 線 形 に しか. と推 定 され る。. 35〔H〕 {3A ENUM-一. 一 一30ao. 三5〔}o. 宮 § 2。。。 旦 15[}0 .垂. 卜. 10㎜ 5曲 o O5〔. 〕1001502〔jo25030〔}35040〔} 囲unlb臼mfdθm即dpoint5. 図1:需. 要 点 の 数 と 解 の 探 索 時 間(Centroid問. 題). 解 の 品 質: 需 要 点 数 を100点 ま た,個. と し て,交. 体 数Pが10,50の. 叉 率Pと. 突 然 変 異 率 一Mが0.02お. 場 合 に つ い て,世. 代 数 σ=200ま. -27(577)一. よ び0.2の. 場 合 に つ い て,. で の 数 値 実験 を お こな っ た。.
(14) 第58巻 図2は,Medianoid問. 第3号. 題 の 解 が 収 束 す る 様 子 で あ り,図3はCentroid問. 様 子 で あ る 。 こ れ ら の グ ラ フ は,い. ず れ も200世. 平 均 を と っ た グ ラ フ で あ る 。 ま た,縦 挙 法 で 求 め た 厳 密 解 を1と. 題 の 解 が収 束 す る. 代 ま で の 数 値 実 験 を30回. 軸 の 且tness値 は,そ. 繰 り返 し,そ. の. れ ぞ れ 場 お よ び 凡 の 値 を,列. し て 正 規 化 し て あ る 。 な お,Medianoid問. 題 に つ い て は,ω. が. 無 限遠 にあ る と きの ガ を求 めて い る。 間. 山恥叫E 匡 牌㎝血三 匡. 以 上 の 結 果 を 見 る と,Medianoid問 の 場 合 で20世 100世. 代 目 で 平 均 的 に 厳 密 解 の90%程. 代 目 あ た りで 厳 密 解 の95%に. さ ら に,こ. 題,Centroid問. 題 と も に,P=50,0=0.2,-M=0.2. 度 の 解 が 得 ら れ て い る こ と が わ か る 。 ま た,. 近 づ き,そ. れ 以 上 の改 善 は遅 い と言 え る。. の 実 装 で 用 い た 弱 エ リー ト保 存 戦 略 の 有 効 性 に つ い て 実 験 結 果 で 示 す 。 図4. は,P=50,0=0.2,M=0.2でMedianoid問 リー ト保 存 戦 略(STRICT),弱. 題 の 解 を 求 め る に あ た っ て,一 エ リ ー ト保 存 戦 略(MILD),エ. リー ト保 存 な し(NON)そ. ぞ れ を用 い た 場 合 に お け る 解 の 収 束 の 様 子 の グ ラ フ で あ る。 こ の グ ラ フ も30回 一28(578)一. 般的なエ れ. の試 行 の平.
(15) Side-tripDistanceを 均 で あ る が,平. 用 い たStackelberg型. 均 的 に 見 て,一. 配 置 問題 へ の遺 伝 的 ア ル ゴ リズ ム の応 用(大 角). 般 的 な エ リ ー ト保 存 戦 略 よ り弱 エ リー ト保 存 戦 略 の 方 が や. や 優 れ て い る と言 え る。. 図4:Medianoid問. 4.3元. 題 に お け るElite保. 存戦略の効果. 問題 へ の 適 用. テ ス ト問 題 で の 数 値 実 験 に お い て,P=50,0=0.2,M=0.2で た め,こ. の収 束 が良 好 で あ った. の 値 を 用 い る。. 実 験 用 の デ ー タ と し て は,[0,1]×[0,1]の. 範 囲 で π=50個. 数 を 用 い て 生 成 し た 。 砺 に つ い て も(0,1]で 周 回 点 ま で の 距 離 の0.Ol倍. 前 後 か ら0.1倍. は,最. 場 合,10m程. 寄 り駅 ま で が1kmの. 元 問 題 の 数 値 実 験 は,90%∼95%の こ と に し た 。m=1の. の 需 要 点 とm個. 生 成 し,r1乞,T%に. つ い て は,そ. 度 か ら100m程. 度 に相 当 す る。. 解 が 得 られ る と 期 待 で き る σ=50ま 示 す 。 図5,6は. 数 値 実 験 の 平 均 値 を と っ た も の で あ る 。 厳 密 解 が 不 明 で あ る か ら,縦. の 解 で あ る 。 図6の 丸),周. 題 に つ い て は,テ. 回 点(灰 色 丸)の 位 置 お よ び,ω*,ガ(白. と した の は,そ 8,9,10はm=2の. でで打ち切 る い ず れ も10回. 軸 の 値 は 動,凡. の の値. ス ト問 題 と 同 じ く ω が 無 限 遠 に あ る 場 合. 解 の 不 安 定 さ に つ い て は 後 述 す る 。 図7は. 例 して い る 。 楕 円 は μ瓦@)=1と. れ ぞれ 最 寄 り. 前 後 と な る よ う に 調 整 した 乱 数 を 用 い た 。 こ れ. 場 合 に つ い て 実 験 結 果 を 図5,6,7に. そ の ま ま で あ る 。Medianoid問. の 周 回点 を乱. 実 験 で 使 用 し た 需 要 点(黒. 丸)の 位 置 を 示 す 。 需 要 点 の 直 径 は 重 み に 比. な る 範 囲 の 境 界 で あ る 。 な お,需. 要 点 の 個 数 を η=50. れ 以 上 増 や す と こ の 楕 円 の 図 示 が 見 づ ら くな る と い う 理 由 の み で あ る 。 図 場 合,図11,12,13はm=4の. 「一 極 集 中 」 が 緩 和 さ れ る 様 子 が 見 て 取 れ る 。. 一29(579)一. 場 合 の結 果 で あ る。 周 回点 が 多 くな る と.
(16) 第58巻. o一 量. 図7:m=1の. 第3号. o-5. 口.4. 場 合 の 解 の 位 置. 口.日. 1. ゴ=(0.697,0.360),〃*=(O.697,0.264). 一30(580)一.
(17) Side-tripDistanceを. 用 い たStackelberg型. 図8:Medianoid問. 題 に お け る 解 の 収 束 、(7η=2). 図9:Centroid問. 図10:皿=2の. 配 置 問 題 へ の 遺 伝 的 ア ル ゴ リ ズ ム の 応 用(大. 題 に お け る 解 の 収 束(7η=2). 場 合 の 解 の 位 置. 〆=(0.398,0.611),〃*=(O.179,0.639). 一31(581)一. 角).
(18) 第58巻. 951015. 第3号. 202530. :}540455口. {諒n日 叩 刊叩. 図11:Medianoid問. 図12:Centroid問. 図13:m=4の. 場 合 の 解 の 位 置. 題 に お け る 解 の 収 束(m=4). 題 に お け る 解 の 収 束(m=4). ♂=(0.725,0.431),〃*=(O.452,0.293).
(19) Side-tripDistanceを. 用 い たStackelberg型. 配 置 問題 へ の遺 伝 的 ア ル ゴ リズ ム の応 用(大 角). 結 果 と 検 討:. 1.周. 回 点1点. のCentroid問. 題 以 外 で は,50世. 代 程 度 で ほ ぼ 収 束 して い る 。. 厳 密 解 と直 接 の 比 較 は で き な い も の の,テ も厳 密 解 の90%以. 2.周. 回 点1点. ス ト問 題 の 結 果 か ら,少. な くと. 上 の 解 が 得 ら れ て い る と推 定 さ れ る 。. の 場 合 にCentroid問. 題 の解 が不 安 定 にな る。. 第2節 で 述 べ た よ うに,後 手 が後 手 に とって の 厳 密 な 最適 解 に配 置 しな い 限 り,先 手 はgω@*,〃*)の 利得 が得 られ な い。 周 回点 が1点 で 地代 が比 較 的 安 い場 合 は,ω,彩 が周 回点 の 近 くに集 ま り互 い に大 き な影 響 を及 ぼ し合 うた め,後 手 の わ ず か な配 置 誤 差 も 先手 の利 得 へ の 影 響 が大 き いた め この よ うな結 果 に な る と思 わ れ る。 3.局 所 解 に陥 る と世代 数 を増 や して も ほ とん ど改 善 され な い場 合 が あ った 。 グ ラ フ は10回 の平 均 を とっ て い る の で,こ の よ うな場 合 は 直接 は表 れ て い な い が,同 じデ ー タ を用 いて も収 束 す る値 が 低 す ぎ る場 合 が あ った 。 こ の よ うな場 合 は,世 代 数 を増 や す よ りも,初 期 条 件 を変 えて(乱 数 系 列 を 変 え て)複 数 回試 行 す る方 が 良 い結 果 が得 られ た 。す な わ ち,100世 実行 す る よ りも,50世. 代 まで. 代 まで を2回 実 行 して 利得 の大 きい 方 を選 ぶ 方 が 良. い。 そ の よ うな 方 式 に切 り替 え るべ き条 件 につ い て は検 討 が必 要 で あ るも の の,実 用 的 には,数 回 の試 行 で 最 も良 い値 を最 適 解 とすれ ぼ良 い だ けな の で,致 命 的 な問 題 と はな らな い。. 5ま 本 論 文 で は,side-tripdistanceを. と め と今 後 の 課 題 使 ったStackelberg型. の競 合 施 設 配 置 問題 にGAを. 用 して解 き,数 値 実験 の結 果 を示 した。 先手 の最 適 配 置 を求 め るCentroid問. 応. 題 にお いて は,. 簡 略 化 した テ ス ト問題 に お いて す ら需 要 点 の個 数 が数 千 点 の オ ー ダー に な る と厳 密 解 を求 め る時 間 が 日数 単 位 に な る一 方 で,GAに 的 に厳 密 解 の90%以. よ る近似 解 法 で は,テ ス ト問題 も元 問題 も平 均. 上 の解 が 実 用 時 間 内 に得 られ る こ と を示 した。 ただ し,周 回 点 が1点. の 場 合 に はCentroid問. 題 の解 が 不安 定 に な る場 合 が あ る こ とが わ か った。 最 悪 の場 合 の解. の 振 幅 を最 小 限 に抑 え る方 法 の検 討 が 今 後 の課 題 で あ る。 -33(583)一.
(20) 第58巻 ま た,GAの. 第3号. 性 能 に大 き く影 響 す る交 叉 率 や 突 然 変 異率 の調 整 を 自動 化 す る こ とも考 え. た い。 選 択 ル ー ル や 突然 変 異 の 方 法,交 叉 の 方 法 に つ いて も,い くつ か の パ タ ー ンを試 し て 最 適 な もの を 自動 的 に選 ぶ よ うな 実 装 を 考 え た い。 さ ら に,GAと. 親 和 性 が 高 い と言 わ れ る免疫 ア ル ゴ リズ ム の考 え を組 み込 む こ とも考 え. た い。 免 疫 ア ル ゴ リズ ム は,母 集 団 の 多様 性 を維 持 しな が ら解 の 探 索 を行 な う とい う性 質 を有 す るた め,特 別 な処 理 を用 い る こ とな く複 数 の局 所 的 最 適 解 を得 る こ とが で き る。 実 装 はGAよ. りも複 雑 にな る こ とが見 込 まれ るが,再 帰性 を持 たせ て 本 論 文 の 問題 に適 用 し. た場 合,ど の よ うな結 果 が得 られ るの か 興 味 深 い とこ ろで あ る。. 参. 考. 文 献. [1]HaroldHotelling,1929,"StabilityinCompetition,,,TheEconomicJournal,V61.30,. pp.41-57. [2]S.L.Hakimi,1983ラ"OnLocatingNewFacilitiesinaCompetitiveEnvironment", EuropeanJournalofOperationalResearch,Vbl.12ラpp.29-35. [3]ZviDrezner(ed.),1995,"FacilityLocation,ASurvayofApplicationsandMethods", Springer. [4]大営 学 角盛 論集 広,石 井 博 昭,2008,「 競 合 基 準 の も と で の 迷 惑 施 設 配 置 問 題 」,神 ,第5巻,第1号,pp.73-89。. 戸学 院大 学 経. [5]大 角 盛 広,塩 出 省 吾,2001,「 フ ァ ジ ィ 限 界 距 離 を 考 慮 し た 競 合 施 設 配 置 問 題 」,日 経 営 シ ス テ ム 学 会 二 十 周 年 記 念 論 文 誌,pp.265-283.. 本. [6]大 角 盛 広,2003,「 最 適 配 置 決 定 の ア ル ゴ リ ズ ム と シ ミ ュ レ ー シ ョ ン ・プ ロ グ ラ ム の 実 装 」,神 戸 学 院 経 済 学 論 集,第35巻,第1・2号,pp.27-43. [7]HaldunAytugandCemSaydamb,2002,"SolvingLarge-scaleMaximumExpected CoveringLocationProblemsbyGeneticAlgorithms:AComparativeStudy",EuropeanJournalofOperationalResearch,Vblume141,Issue3,pp.480-494. [8]ZoricaStanimirovic,JozefKraticaandDjordjeDugosija,2006,"GeneticAlgorithms forSolvingtheDiscreteOrderedMedianProblem",EuropeanJournalofOperational Research,V61umel82,pp.83-1001. [9]M.BischoffandK.klamroth,2006,"AnE伍cientSolutionMethodforW6berProblemswithBariiersBasedonGeneticAlgorithms",EuropeanJournalofOperational Research,Vblume177,pp.22-41. [10]LiliYang,BryanEJonesandShuang-HuaYang,2007,"AFuzzyMulti-objective Programmingf6rOptimizationofFireStationLocationsthroughGeneticAlgorithms",EuropeanJournalofOperationalResearch,pp.903-915. [11]長. 尾 智 晴,1997,「 遺 伝 的 ア ル ゴ リ ズ ム に よ る 数 値 最 適 化 の た め の 均 質 コ ー デ ィ ン グ 」, 電 子 情 報 通 信 学 会 論 文 誌,第80号1,pp。56-62.. [12]HiroshiImai,1982,"FindingConnectedComponentsofAnIntersectionGraphof SquaresinTheEuclideanPlane",InlbrmationProcessingLetters,V61.15,pp。125128. [13]MakotoMatsumotoandTakujiNishimura,1998,"Mersennetwister:a623dimensionallyequidistributeduniformpseudo-randomnumbergenerator,,ラACM TransactionsonModelingandComputerSimulation(TOMACS),Volume81ssue1, pp.3-30.. 34(584).
(21)
関連したドキュメント
例えば，立証責任分配問題については，配分的正義の概念説明，立証責任分配が原・被告 間での手続負担公正配分の問題であること，配分的正義に関する
マーカーによる遺伝子型の矛盾については、プライマーによる特定遺伝子型の選択によって説明す
①物流品質を向上させたい ②冷蔵・冷凍の温度管理を徹底したい ③低コストの物流センターを使用したい ④24時間365日対応の運用したい
・逆解析は，GA（遺伝的アルゴリズム）を用い，パラメータは，個体数 20，世 代数 100，交叉確率 0.75，突然変異率は
基本的金融サービスへのアクセスに問題が生じている状態を、英語では financial exclusion 、その解消を financial
駅周辺の公園や比較的規模の大きい公園のトイレでは、機能性の 充実を図り、より多くの方々の利用に配慮したトイレ設備を設置 全
現状では、3次元CAD等を利用して機器配置設計・配 管設計を行い、床面のコンクリート打設時期までにファ
▶
