. 一 番 いい 答 え( 最 適 化 手 法 ) 環 境 問 題 を 解 決 する ということは 結 局,いろいろ な 制 約 条 件 のもとで, 環 境 という 複 雑 なシステムの 最 適 解 を 求 めることなのかもしれない( 井 手 ) この 章 では, 多 変 数 関 数 の 値 を 最 小 化 (あるいは 最 大 化 )する 変 数 値 を 求 めるための 数 値 計 算 法,す なわち 最 適 化 手 法 について 概 説 する. Rosenbrock 関 数 の 解 まず 非 線 形 関 数 の 最 適 化 問 題 を 考 えてみる( 線 形 関 数 の 最 適 化 問 題 は 後 述 する). 非 線 形 関 数 の 最 適 化 を 扱 う 数 学 を 非 線 形 計 画 法 と 呼 ぶ. 非 線 形 関 数 の 数 値 計 算 による 最 適 化 手 法 には 大 きく 言 って, 関 数 の 局 所 的 傾 きから 関 数 値 のより 低 い( 高 い) 方 向 を 求 めていく 方 法 ( 最 急 降 下 法, 共 役 傾 斜 法, 準 ニュートン 法 など)と 試 行 錯 誤 的 に 関 数 値 の 低 い( 高 い) 場 所 に 向 かおうとする 方 法 ( 直 接 探 索 法 )の 二 つがある. 以 下, 非 線 形 計 画 法 の 一 例 として Rosenbrock 関 数 を Excel のソルバー 機 能 で 解 く 方 法 を 解 説 す る.Rosenbrock 関 数 は, 次 式 で 定 義 される 関 数 で あるが, 非 線 形 関 数 の 最 適 化 問 題 を 扱 う 数 値 計 算 法 の 有 効 性 を 検 証 するためによく 使 用 される 関 数 である. ここで C4 セルには Rosenbrock 関 数 = *(B4 - A4^)^ + ( - A4)^ の 式 を 入 力 している. 上 掲 のようなシートを 完 成 させた 後 に,メニ ューの[ルール]から[ソルバー]を 選 択 する.すると 下 図 のような パラメータ 設 定 のダイアローグ ボックスが 現 われる.(ただし, 標 準 インストー ルの Excel ではソルバー 機 能 は 使 用 できないため, 事 前 に[ルール][アドイン]で[ソルバーアドイン]に チェックを 入 れ, 使 用 できるようにしておく 必 要 がある.) f ( x, y) = ( y x ) + ( x) 同 関 数 を 3D プロットしたものを 下 図 に 示 す. 5 4 3 3 - - 図 では 分 かりづらいかもしれないが, 同 関 数 は (,) において 最 小 値 をとる.しかし,その 極 小 値 付 近 に 複 雑 な 曲 面 をもつことから, 最 小 値 ( 最 適 解 )を 求 めにくい 関 数 となっている. さて,この Rosenbrock 関 数 を Excel のソルバ ー 機 能 で 解 くための 方 法 であるが, 先 ずExcel のシート 上 に 次 の 図 のような 文 字 列 や 値, 式 を 打 ち 込 む. 3 この パラメータ 設 定 画 面 で 先 ず,3 最 適 化 の 目 的 セルを 指 定 する(ここでは Rosenbrock 関 数 を 実 際 に 計 算 している$C$4 セルである). 次 に,4 同 目 的 セルをどのように 最 適 化 したいのか を,その 下 の 目 標 値 : の 3 つの 選 択 肢 からラ ジオボタンで 選 ぶ.Rosenbrock 関 数 では 同 目 的 セ ルの 値 を 最 小 にしたいので 最 小 値 を 選 択 する. なお,ここで 値 を 選 び,その 横 のボックスに 値 を 入 力 して, 目 的 セルの 値 を 指 定 した 値 にいか に 近 づけるかといった 最 適 化 の 方 法 もある. さらに 目 的 セルの 値 を 最 小 とするために,5 実 際 に 変 化 させるセル をその 下 のボックスで 指 定 する.ここで 変 化 させるのは $A$4:$B$4 の x と y の 値 を 入 力 するセルである( 上 掲 のシート 上 ではそれぞれ- と の 値 を 入 力 しているが, これはあくまで 初 期 値 であり, 最 初 はどのような 値 でもよい). 次 に,これは 任 意 であるが,[オプション]をク リックして, オプション 設 定 画 面 右 下 にある 検 索 方 法 の[ 共 役 傾 斜 法 ]をラジオボタンで 選 択, 最 後 に[OK]ボタンをクリックして, 同 画 面 を 閉 じる.(Rosenbrock 関 数 に 関 しては, 共 役 傾 斜 法 のほうが 準 ニュートン 法 より 最 適 解 にいたる 計 算 回 数 が 少 ないようである) - 5 -
最 後 に6 パラメータ 設 定 画 面 の 右 上 にある [ 実 行 ]ボタンをクリックして, 最 適 化 を 開 始 する. すると, 変 化 させるとした $A$4:$B$4 のセル の 値 が 変 化 し,それにつれて 目 的 セルである $C$4 の 値 が 変 化 する.その 後,しばらくする と, 下 図 のような 検 索 結 果 の 画 面 が 現 われる. 上 図 が 最 適 化 結 果 を 表 示 した 画 面 である. 図 に 示 されるように,ソルバーによる 最 適 化 の 結 果 は x =.7, y =.5 と,ほぼ 理 論 解 (,) に 近 いものとなった.ただし,この 例 で 示 されるよう に, 数 値 計 算 法 の 限 界 として,その 解 には 常 にい くらかの 誤 差 が 含 まれていることに 留 意 する 必 要 がある. また, 非 線 型 関 数 の 最 適 化 において 注 意 しなけ ればならないのは, 解 がある 一 点 に 収 束 したから といって,その 解 は 単 なる 局 所 解 かもしれず, 変 数 定 義 域 内 の 真 の 最 小 ( 最 適 ) 解 である 保 証 は 何 も ないという 点 である. 県 大 学 食 メニュー 問 題 次 に, 線 形 関 数 の 最 適 化 問 題 として, 県 大 の 学 食 メニューの 最 適 解 を Excel のソルバー 機 能 を 用 いて 解 いてみる. 次 ページに 掲 載 した 表 は 平 成 9 年 の 県 大 学 生 食 堂 のメニューである. 全 部 で 57 品 目 あり, 表 には, それぞれの 品 目 の 横 に 当 時 の 値 段 やカロリーなど が 示 されている.さらにカロリーの 右 にある 赤 緑 黄 が, 栄 養 ポイントと 呼 ばれるものである. それぞれがタンパク 質, 緑 黄 色 野 菜, 炭 水 化 物 の 栄 養 価 を 表 している. 栄 養 ポイントについては, 一 食 につきそれぞれ.8,.9,6.3 以 上 摂 取 する ことが 望 ましいとされている. さらに, 次 ページの 表 は Excel シート 上 に 作 成 されたものであり, 選 んだ 品 目 によって 値 段 やカ ロリー, 栄 養 ポイントの 合 計 点 が 計 算 できるよう になっている. 具 体 的 には,それぞれの 品 目 毎 に 何 皿 を 選 んだかを 入 力 するセル( 皿 数 と 名 付 けた 列 )があり,ここに 皿 数 の 数 値 を 入 力 すると, 行 の 右 側 に 皿 数 を 掛 けた 値 段 とカロリー, 栄 養 ポ イントが 計 算 されるようなっている.さらに, 最 終 行 の 合 計 のところには 値 段 やカロリー, 栄 養 ポイントの 合 計 点 が 表 示 される. さてこの 県 大 学 食 メニューを 用 いる 最 適 化 問 題 の 一 例 として,ここでは 赤 緑 黄 の 合 計 栄 養 ポイントがそれぞれ.8,.9,6.3 以 上 であり, かつ 最 も 値 段 合 計 が 安 いメニュー,すなわち, 最 も 安 く 栄 養 を 摂 るためのメニュー( 品 目 の 組 み 合 わせ)を 求 めることを 考 える. ちなみに,この 問 題 は 線 形 関 数 の 最 適 化 問 題 で ある.なぜならば, 最 適 化 ( 最 小 化 )しようとす る 目 的 関 数 (ここでは 値 段 合 計 )と, 最 適 化 のた めに 操 作 される 変 数 ベクトル(ここでは 皿 数 )と の 間 に 線 形 関 係 が 成 り 立 つからである. 線 形 関 数 の 最 適 化 を 扱 う 数 学 を 線 形 計 画 法 と 呼 ぶが, 線 形 計 画 法 にはシンプレックス 法 と 呼 ば れる 確 立 された 手 法 がある( 非 線 形 計 画 法 にも シ ンプレックス 法 と 呼 ばれる 手 法 があるが,これ は, 語 源 は 同 じでも, 線 形 計 画 法 のシンプレック ス 法 とは 別 物 である). 県 大 の 学 食 メニュー 問 題 をシンプレックス 法 で 解 くためには, 与 えられた 問 題 を 次 のように 定 式 化 する 必 要 がある. 費 用 ベクトル 3 45 c = M 変 数 ベクトル ( 皿 数 ) x x x = M x57 文 字 通 り 値 段 の 列 ベクトル 57 品 目 それぞれの 皿 数 からなる 列 ベクトル - 53 -
平 成 9 年 度 滋 賀 県 立 大 学 学 生 食 堂 メニュー by 加 藤 一 郎 醤 油 ラーメン 3 445.3. 5.... 焼 き 豚 ラーメン 45 54.3. 5.... 若 布 コーンラーメン 35 483.3.6 5.... かけうどん 8 97.. 3.7... かけそば 8 3.. 4.... 若 布 うどん 97.. 3.7... 若 布 そば 3.. 4.... 変 化 させるセル 天 ぷらうどん 6 374.. 4.5... 天 ぷらそば 6 396.. 4.8... きつねうどん 359.5. 3.9... きつねそば 38.5. 4.... にしんそば 35 4.. 4.... 肉 うどん 33 5.. 3.9... 肉 そば 33 54.. 4.... カレーうどん 8 48..5 5.5... 牛 丼 M 35 988 6.9. 5.... カレーライスM 5 553..4 6.5... カレーライスS 474..4 5.3... カツカレーM 4 897..4 9.7... カツ 丼 38 888.7. 8.3... 竜 田 丼 M 35 7.. 6.9... 竜 田 丼 S 33 6.. 5.5... フィッシュフライ 8 46.6. 5.... 豚 肉 野 菜 炒 め 5 58..7.9... 荒 挽 きハンバーグ 3 449 4..3.3... ビーフハンバーグ 和 風 3 394 3.9..8... 和 風 おろしとんかつ 8 56.6. 4.... ささみ 香 り 揚 げ 6 343.. 3.... ささみチーズフライ 3 448.. 4.4... チキン 唐 揚 げ 7 59 3.3..9... 鶏 唐 揚 げ 香 味 ソース 7 557 3.3. 3.5... チキン 南 蛮 5 453.. 4.3... ライスSS 6 77...... ライスS 8 66.. 3.3 8 66.. 3.3 ライスM 384.. 4.8... ライス 3 53.. 6.7... 味 噌 汁 7.3..... 肉 団 子 8...... サバ 味 噌 煮 6 55.6..4... 豆 腐 5 88... 76... ホウレンソウ 6 8...... サンマかつお 煮 6 53.3..9... 鰯 の 梅 煮 74.7..... ヨーグルトサラダ.5.3.5... 大 学 芋 8 3..7.9... マカロニサラダ 6 4...5... 枝 豆 入 りひじき 煮 6 67..3.4... 若 布 コーンサラダ 48..6.... 若 布 ツナサラダ 54.5..... 下 足 唐 揚 げ 3 5.7..8... 目 的 セル 里 芋 煮 4..3.... ナタデココフルーツ...3... 竹 輪 の 天 ぷら.9..7... きんぴらごぼう 8 88..4.7... かぼちゃの 煮 付 け 6 9..7.4 6 9..7.4 ビーフコロッケ 6.3..... かぼちゃコロッケ 84..4 3. 84..4 3. 合 計 5 34 87.. 6.8 最 小 化 >=.8 >=.9 >=6.3-54 -
係 数 ベクトル 3 右 辺 ベクトル 4 零 ベクトル.3 A =. 5..8 b =.9 6.3 O = M 正 準 形 目 的 関 数 : c t Ax b 制 約 条 件 x O.3. 5. x 最 小 化..4 3. シンプレックス 法 では,これ 以 降, 定 式 化 された 問 題 をピボット 選 定 演 算 と 呼 ばれる 方 法 によって 解 いていくことになるが, 詳 細 はここでは 省 略 する. その 代 わりに,ここでは 先 の Rosenbrock 関 数 と 同 様 に,この 問 題 を Excel のソルバー 機 能 で 解 く 方 法 を 解 説 する. 6 制 約 条 件 として 次 の 条 件 を 指 定 する. $G$3:$G$59 = 整 数 $G$3:$G$59 >= $J$6 >=.8 $K$6 >=.9 $$6 >= 6.3 上 記 の 条 件 のうち 最 初 の つは, 変 化 させるセル ( 皿 数 )が 整 数 であり, 負 の 数 ではないと 指 定 する ためのものです.これらをきちんと 指 定 しないと, 数 学 的 には 小 数 点 の 皿 数 やマイナスの 皿 数 が 最 適 解 となる 可 能 性 がある.(マイナスの 皿 数 とはたと えば, 自 宅 である 品 目 を 作 ってきて,それを 学 食 に もってくるということ. 数 学 的 には,もちろんその 品 目 の 分 の 値 段 が, 合 計 金 額 から 差 し 引 かれること になる.) また 最 後 の 3 つの 条 件 は, 栄 養 ポイント 赤 緑 黄 の 合 計 を 計 算 するセルの 値 が,それぞれ.8,.9,6.3 以 上 となることを 指 定 している. これら 制 約 条 件 を 指 定 する 具 体 的 な 方 法 として は パラメータ 設 定 画 面 で 制 約 条 件 の 右 にある[ 追 加 ]ボタンをクリックする.すると 下 のような 画 面 が 現 われる. 県 大 学 食 メニュー 問 題 をソルバー 機 能 で 解 く 手 順 Excel のシート 上 に p.5 のような 文 字 列, 値, 式 を 打 ち 込 む. メニューの[ルール]から[ソルバー]を 選 択.この パラメータ 設 定 画 面 で 次 のように 設 定 する. 同 画 面 で, 左 のセルで 参 照 するセルを, 右 のセル で 制 約 条 件 を, 真 ん 中 のセルで 両 者 の 間 の 関 係 を 条 件 一 つひとつについて 指 定 する.もちろん 一 旦 指 定 した 条 件 を 変 更 したり, 削 除 したりすることも 可 能 である. 7 パラメータ 設 定 画 面 の [オプション]をクリッ クして, 画 面 中 央 にある 線 形 モデルで 計 算 のチ ェックボックスにチェックを 入 れる.これは,ここ で 解 こうとしているのが 線 形 計 画 問 題 であるから である.もし, 線 形 モデルであることを 指 定 してお かないとなかなか 最 適 解 に 収 束 しない( 試 してみよ う). 3 最 適 化 の 目 的 セルとして $H$6 ( 値 段 合 計 を 計 算 するセル)を 指 定 する. 4 目 標 値 : の 3 つの 選 択 肢 から 最 小 値 をラ ジオボタンで 選 択 する. 5 実 際 に 変 化 させるセルとして $G$3:$G$59 ( 皿 数 を 入 力 するセル)を 指 定 する. 3 赤 緑 黄 の 栄 養 ポイントの 行 列 (3 行 57 列 ) 4 栄 養 ポイント 赤 緑 黄 の 最 小 値 - 55 -
6 パラメータ 設 定 画 面 の 右 上 にある[ 実 行 ]ボタ ンをクリックして, 最 適 化 を 開 始 する. 7 最 後 に 検 索 結 果 の 画 面 が 現 われれば 終 了 であ る. 上 記 の 最 適 化 の 結 果 は 次 のようになる. 理 想 型 最 小 化 >=.8 >=.9 >=6.3 ライスS 8 66.. 3.3 8 66.. 3.3 豆 腐 5 88... 76... かぼちゃの 煮 付 け 6 9..7.4 6 9..7.4 かぼちゃコロッケ 84..4 3. 84..4 3. 合 計 5 34 87.. 6.8 すなわち 県 大 の 学 食 において 最 も 安 く 栄 養 を 摂 るためのメニュー( 品 目 の 組 み 合 わせ)は ライス S 膳, 豆 腐 皿, かぼちゃの 煮 付 け 皿, か ぼちゃコロッケ 皿 の 計 5 品 目 で, 合 計 金 額 は 34 円.もちろん 赤 緑 黄 の 栄 養 ポイントのすべて が 推 奨 ポイントを 上 回 っている. とは 言 え(もちろん 数 学 的 には 正 しいのだろう が), 上 記 の 結 果 に 違 和 感 を 覚 える 人 もいるかもし れない.たとえば,いくら 栄 養 価 が 高 いからといっ て 豆 腐 を 皿 も 食 べたくない,あるいは, 調 理 法 が 違 うとは 言 え,かぼちゃばかり 皿 は 嫌 だ,とか. そこで 次 のような 制 約 条 件 を つ 追 加 してやろう. $G$3:$G$59 <= 同 条 件 が 意 味 するところは, 同 じ 品 目 を 皿 以 上 は 選 択 しないということである.この 条 件 を 加 えて, 最 適 化 をやり 直 した 結 果 を 次 に 示 す. 理 想 型 最 小 化 >=.8 >=.9 >=6.3 ライスS 8 66.. 3.3 8 66.. 3.3 肉 団 子 8... 8... 竹 輪 の 天 ぷら.9..7.9..7 かぼちゃの 煮 付 け 6 9..7.4 6 9..7.4 合 計 4 34 75.9.9 6.6 どうだろう. 今 度 の 結 果 は ライス S 膳, 肉 団 子 皿, 竹 輪 の 天 ぷら 皿, かぼちゃの 煮 付 け 皿 の 計 4 品 目, 合 計 金 額 は 34 円 である.これで も 満 足 しない 人 は,また 別 の 制 約 条 件 を 加 えて 最 適 化 をやり 直 してみればよい. なお, 回 目 の 最 適 化 の 結 果 は, 制 約 条 件 を つ 追 加 したことによって, 合 計 値 段 は 同 じであるが, 回 目 の 結 果 と 比 べて 栄 養 ポイントが 若 干 低 下 して いる( 赤 緑 黄 のすべてにおいて 推 奨 ポイント を 上 回 ってはいるが) 点 に 注 意 しよう. では,ニューラルネットという 技 術 が 成 功 をおさめ ている.ニューラルネットとは, 人 間 の 脳 細 胞 およ びその 学 習 機 能 を 数 学 モデル 化 したものである. 脳 細 胞 間 の 情 報 伝 達 ネットワークをモデル 化 したニ ューラルネットに 登 場 する 関 数 は, 非 線 型 関 数 であ る.ニューラルネットの 学 習 (ネットワークの 最 適 化 )のためには, 最 急 降 下 法 などの 非 線 形 計 画 法 が 用 いられている. 参 考 書 わかるコンピュータ 数 値 計 算 J.C.Nash 著 (Ohmsha) 補 足 紙 幣 の 真 贋 などを 判 別 するパターン 認 識 の 分 野 - 56 -