Comments
Description
Transcript
Microsoft Excel - Palisade Corporation
ユーザー ガイド Evolver 遺伝的アルゴリズムを使った Microsoft Excel 解決ツール アドイン バージョン 5.7 2010 年 9 月 Palisade Corporation 798 Cascadilla St. Ithaca, NY 14850 USA +1-607-277-8000 +1-607-277-8001 (fax) http://www.palisade.com (Web サイト) [email protected] (電子メール) 著作権表記 Copyright © 2010, Palisade Corporation. 商標について Microsoft、Excel、Windows は Microsoft Corporation の登録商標です。 IBM は International Business Machines, Inc. の登録商標です。 Palisade、Evolver、TopRank、BestFit、RISKview は Palisade Corporation の登録商標 です。 RISK は Tonka Corporation の一部である Parker Brothers の商標であり、商標保有者 の許可を元に使用されています。 目次 第 1 章: はじめに 1 はじめに ................................................... 3 インストール方法 ........................................... 7 第 2 章: Evolver について 11 Evolver について .......................................... 13 第 3 章: Evolver: ステップバイステップ 19 はじめに .................................................. 21 Evolver の基本操作 ........................................ 23 第 4 章: 実用例 41 はじめに .................................................. 43 広告ミックス .............................................. 45 アルファベット順の並べ替え ................................ 47 タスクの割り当て .......................................... 49 ベーカリー ................................................ 51 予算の配分 ................................................ 53 化学平衡 .................................................. 55 授業のスケジュール ........................................ 57 目次 i コードのセグメント化 ...................................... 59 ノースダコタ: 制限付きの経路判断........................... 63 製作工場のスケジュール..................................... 65 ラジオ塔の配置 ............................................ 67 ポートフォリオの分散 ...................................... 69 ポートフォリオの配分 ...................................... 71 ラジオ送信機 .............................................. 73 購入判断 .................................................. 75 巡回セールスマンの問題..................................... 77 スペースシャトル .......................................... 79 証券トレーダー ............................................ 81 変圧器 .................................................... 83 輸送費 .................................................... 85 第 5 章: Evolver リファレンス ガイド 87 [モデルの定義] コマンド.................................... 89 [最適化設定] コマンド .................................... 113 [最適化の開始] コマンド................................... 119 [ユーティリティ] コマンド................................. 121 Evolver ウオッチャー ..................................... 125 第 6 章: 最適化 135 最適化の手法 ............................................. 137 Excel ソルバー ........................................... 143 ii 問題の種類 ............................................... 147 第 7 章: 遺伝的アルゴリズム 151 はじめに ................................................. 153 歴史的背景 ............................................... 153 生物の例 ................................................. 157 コンピュータの例 ......................................... 159 第 8 章: Evolver のその他の機能 163 制限の追加 ............................................... 165 処理速度の改善 ........................................... 175 Evolver の最適化の実装 ................................... 176 付録 A: Evolver の自動化 179 付録 B: トラブルシューティングと Q&A 181 トラブルシューティングと Q&A ............................. 181 付録 C: 参考文献 185 参考文献 ................................................. 185 目次 用語集 191 索引 199 iii iv 第 1 章: はじめに はじめに ................................................... 3 インストールの前に ....................................... 製品パッケージの確認 ..................................... このバージョンについて ................................... ご利用のオペレーティング環境での作業 ..................... サポートについて ......................................... お問い合わせの前に ................................ Palisade へのお問い合わせ.......................... ステューデント版 .................................. Evolver システム必要条件 ................................. 3 3 3 4 4 4 5 6 6 インストール方法 ........................................... 7 一般的なインストール方法 ................................. 7 Evolver のコンピュータからの削除................... 7 DecisionTools Suite ...................................... 8 Evolver アイコンおよびショートカットの設定................ 8 起動時に表示されるマクロのセキュリティ警告メッセージ ...... 9 Evolver に関する追加の情報 .............................. 10 Evolver の「お読みください (Readme)」 ............. 10 Evolver の自己学習 ............................... 10 Evolver の自己学習 ...................................... 10 第 1 章: はじめに 1 2 はじめに Evolver は一般市場で現在入手できる製品のうち、最も高速で高機能 な遺伝的アルゴリズム ベースの最適化ツールです。Evolver は、遺 伝的アルゴリズム (GA: Genetic Algorithm) に基づく強力な最適化 手法を用いて、線形処理や非線形処理による一般の最適化ツールでは 解くことのできない問題を解決できます。Evolver は、ニーズに合わ せてプロフェッショナル版とインダストリアル版の 2 種類から選択 することができます。 この『Evolver ユーザー ガイド』では、まず Evolver とその仕組み について概要を説明した後、Evolver 特有の遺伝的アルゴリズムを用 いた最適化の実用例をいくつか紹介します。このマニュアルは、 Evolver の各機能の説明が記載された索引付きリファレンス ガイド としてご利用いただくこともできます。 インストールの前に Evolver をインストールして使用する前に、Evolver の製品パッケー ジに必要なものがすべて含まれているか確かめ、お使いのコンピュー タが特定用途の最小要件を満たしていることを確認してください。 製品パッケージの確認 Evolver は、独立した製品として購入する場合と、DecisionTools Suite プロフェッショナル版またはインダストリアル版の一部として 出荷される場合があります。Evolver CD-ROM には、Evolver Excel ア ド イ ン 、 Evolver の サ ン プ ル フ ァ イ ル 、 お よ び 索 引 付 き の Evolver オンライン ヘルプ システムがそれぞれ含まれています。 DecisionTools Suite プロフェッショナル版およびインダストリアル 版には、上記すべてとさらに追加のアプリケーションが含まれていま す。 このバージョンについて このバージョンの Evolver は、Microsoft Excel 2000 またはそれ以 降に 32 ビット プログラムとしてインストールできます。 第 1 章: はじめに 3 ご利用のオペレーティング環境での作業 このユーザー ガイドは、Windows オペレーティング システムおよび Excel についての一般的な知識がある読者を対象としています。特に 以下の知識が必要です。 ♦ ご利用のコンピュータ、およびマウスの使い方に精通してい ること。 ♦ アイコン、クリック、ダブルクリック、メニュー、ウィンド ウ、コマンド、およびオブジェクトといった用語に精通して いること。 ♦ ディレクトリ構造やファイルの命名といった、基礎的な概念 を理解していること。 サポートについて テクニカル サポートは、有効なメンテナンス プランをお持ちの Evolver 登録ユーザー様に対して無償で、あるいはインシデントごと に有償で提供しております。Evolver 登録ユーザーになるには、 http://www.palisade.com/support/register.asp にてオンライン登 録を行ってください。 電話でのお問い合わせの際には、あらかじめ製品のシリアル番号とユ ーザー ガイドを手元にご用意ください。また、コンピュータで作業 できる状態でご連絡いただければ、さらに効果的なテクニカル サポ ートを受けることができます。 お問い合わせの 前に 4 テクニカル サポートへのお問い合わせの前に、次の事柄をご確認く ださい。 • オンライン ヘルプを参照しましたか？ • 本ユーザー ガイドを確認し、オンライン マルチメディア チュ ートリアルの内容を参照しましたか？ • 「お読みください」(README.WRI) ファイルを読みましたか？こ のファイルには、マニュアルに収録されていない、Evolver に関 する最新情報が記載されています。 • 問題となっている障害は再現することが可能ですか？また、別の コンピュータやモデルでも問題点を再現することは可能ですか？ • 弊社の Web サイトをご覧になりましたか？弊社サイトの URL ア ドレスは http://www.palisade.com です。Web サイトのテクニ カル サポートのセクションには、最新の FAQ (テクニカル サポ ートに寄せられた質問とその回答集を収録した検索可能なデータ ベース) と Evolver ソフトウェア用のパッチが掲載されていま す。Evolver およびその他の Palisade ソフトウェアの最新情報 はじめに をいち早く入手できるよう、弊社のサイトには定期的にアクセス されることをお勧めします。 Palisade へのお 問い合わせ Palisade 社では、Evolver に関するご質問、ご意見、およびご提案 をお待ちしております。テクニカル サポートには、以下のいずれか の方法でご連絡いただけます。 • 電子メール: [email protected] • 電話: +1-607-227-8000 (米国)、米国東海岸時間平日午前 9 時 から午後 5 時まで。テクニカル サポートへの電話案内の指示に 従ってください。 • ファックス: +1-607-227-8001 (米国) • 郵便: Technical Support Palisade Corporation 798 Cascadilla St Ithaca, NY 14850 USA Palisade Europe へのお問い合わせ: • 電子メール: [email protected] • 電話: +44 1895 425050 (英国) • ファックス: +44 1895 425051 (英国) • 郵便: Palisade Europe 31 The Green West Drayton Middlesex UB7 7PN United Kingdom Palisade Asia-Pacific へのお問い合わせ: • 電子メール: [email protected] • 電話: +61 2 9252 5922 (オーストラリア) • ファックス: +61 2 9252 2820 (オーストラリア) • 郵便: Palisade Asia-Pacific Pty Limited Suite 404, Level 4 20 Loftus Street Sydney NSW 2000 Australia 第 1 章: はじめに 5 いずれの方法でお問い合わせいただく場合でも、必ず製品名、正確な バージョン番号、およびシリアル番号をご連絡ください。正確なバー ジョンは、Excel の Evolver メニューから [Evolver について] コ マンドを選択することで確認できます。 ステューデント 版 ステューデント版の Evolver に対する電話サポートは提供しており ません。サポートが必要な場合は、以下の方法をご検討ください。 ♦ 担当の教授または教育助手に相談する。 ♦ http://www.palisade.com にアクセスして FAQ を参照する。 ♦ 電子メールまたはファックスで弊社のテクニカル サポート部 門に連絡する。 Evolver システム必要条件 Evolver の必要システム条件は以下のとおりです。 6 • ハードディスクが備わった Pentium 以上のパーソナル コンピュ ータ • Microsoft Windows 2000 SP4 またはそれ以降 • Microsoft Excel バージョン 2000 またはそれ以降 はじめに インストール方法 Evolver は、Microsoft Excel のアドイン プログラムです。Evolver は Excel のメニュー バーにコマンドを追加して、スプレッドシート プログラムの機能を強化します。 一般的なインストール方法 Evolver のセットアップ プログラムは、ユーザーが指定したハード ディスク上のディレクトリに Evolver システム ファイルをコピーし ます。Windows 2000 およびそれ以降でのセットアップ プログラム実 行方法は、以下のとおりです。 1) CD-ROM ドライブに Evolver あるいは DecisionTools Suite プ ロフェッショナル版またはインダストリアル版の CD-ROM を挿入 します。 2) [スタート] ボタンをクリックし、[設定] > [コントロール パネ ル] をクリックします。 3) [プログラムの追加と削除] アイコンをダブルクリックします。 4) [インストール/アンインストール] タブの [インストール] ボタ ンをクリックします。 5) 画面に表示されるセットアップ手順に従います。 Evolver のインストール中に問題が発生する場合は、インストール対 象のドライブに十分な空きスペースがあることを確認してください。 十分な空きスペースが確保できたら、再度、インストール手順を実行 してください。 Evolver のコン ピュータからの 削除 第 1 章: はじめに ご利用のコンピュータから、Evolver または DecisionTools Suite を削除したい場合は、コントロール パネルの [プログラムの追加と 削 除 ] ユ ー テ ィ リ テ ィ を 起 動 し 、 Evolver ま た は DecisionTools Suite の項目を選択します。 7 DecisionTools Suite Evolver は、Palisade 社が提供しているリスク分析・意思決定分析 のためのセット製品、DecisionTools Suite と連携させて使用するこ とができます。デフォルトの Evolver インストール手順では、メイ ン ディレクトリである「Program Files\Palisade」のサブディレク トリに Evolver がインストールされます。これは、「Microsoft Office」ディレクトリのサブディレクトリに Excel がインストール されるのと同じ要領です。 Program Files\Palisade ディレクトリに作成されるサブディレクト リの 1 つが、Evolver ディレクトリ (デフォルト名「Evolver5」) です。このディレクトリには、Evolver アドイン プログラム ファイ ル (EVOLVER.XLA) に加えて、サンプル モデルおよび、Evolver を実 行 す る た め に 必 要 な 関 連 フ ァ イ ル が 含 ま れ て い ま す 。 Program Files\Palisade には、SYSTEM というサブディレクトリも作成されま す。このディレクトリには、共通のヘルプ ファイルやプログラム ラ イブラリなど、DecisionTools Suite のすべてのプログラムで必要と されるファイルが含まれています。 Evolver アイコンおよびショートカットの設定 Evolver のセットアップ プログラムは、タスクバーのプログラム メ ニューに、Evolver コマンドを自動的に作成します。ただし、セット アップ作業中に問題が発生した場合、あるいは、後日このコマンドを 手動で作成する場合は、以下の手順に従います。 8 1) [スタート] ボタンをクリックし、[設定] を選択します。 2) [タスク バーと [スタート] メニュー] をクリックし、[[スター ト] メニュー] タブをクリックします。 3) [カスタマイズ]、[追加] の順にクリックし、[参照] をクリック します。 4) EVOLVER.EXE ファイルを見つけてダブルクリックします。 5) [次へ] をクリックし、プログラムのショートカットを保存する メニューをダブルクリックします。 6) 名前として「Evolver」と入力し、[完了] をクリックします。 インストール方法 起動時に表示されるマクロのセキュリティ警告メッ セージ Microsoft Office には、Office アプリケーション上で不要なマクロ、 または悪意をもって作成されたマクロが実行されるのを防止するため に、さまざまなセキュリティ設定 ([ツール] > [マクロ] > [セキュ リティ]) が用意されています。最低限のセキュリティ設定を使用し ない限り、マクロ付きのファイルを読み込むたびに警告メッセージが 表示されます。Palisade 社のアドインを実行するたびにこのような メッセージが表示されることを防ぐため、Palisade では自社のアド イン ファイルにデジタル署名を付与しています。したがって、いっ たん Palisade Corporation を信頼できる作成元として登録すれば、 Palisade 社のすべてのアドインを警告メッセージの表示なしに開く ことができます。以下の手順に従ってください。 z 第 1 章: はじめに Evolver の起動時に、次のような [セキュリティの警告] ダイア ログが表示されたら、[この発行者のドキュメントをすべて信頼 する] ラジオ ボタンをオンにします。 9 Evolver に関する追加の情報 Evolver に関する追加の情報は、以下の方法で入手できます。 Evolver の「お 読みください (Readme)」 このファイルには、Evolver の概要と、最新バージョンに関する新し い情報が記載されています。「お読みください」ファイルを表示する に は 、 Windows の [ ス タ ー ト ] メ ニ ュ ー か ら [ プ ロ グ ラ ム ] > [Palisade DecisionTools] > [Readmes] を選択し、[Evolver 5.0 お読みください] をクリックします。Evolver をお使いになる前に、 このファイルの内容を確認することをお勧めします。 Evolver の自己 学習 Evolver オンライン チュートリアルでは、Evolver を初めて利用さ れるユーザーを対象に、Evolver および遺伝的アルゴリズムの概要に ついて説明しています。このチュートリアルはごく短時間で修了でき ます。チュートリアルへのアクセス方法については、次の「Evolver の自己学習」セクションを参照してください。 Evolver の自己学習 Evolver の使い方を素早く習得するには、オンラインの Evolver チ ュートリアルを利用するのが一番簡単です。このムービー形式のチュ ートリアルでは、エキスパートがサンプル モデルを使って基礎を紹 介しています。このチュートリアルは、Evolver の主要機能について 解説したマルチメディア プレゼンテーションです。 チュートリアルを実行するには、Evolver [ヘルプ] メニューの [基 礎チュートリアル] コマンドを選択します。 10 インストール方法 第 2 章: Evolver について Evolver について .......................................... 13 Evolver の仕組み ........................................ 遺伝的アルゴリズム ............................... 最適化について .......................................... Excel でモデルを構築する理由 ............................ Evolver の利点 .......................................... 推測が不要になる ................................. より正確で意味のある分析.......................... 優れた柔軟性 ..................................... 高機能 ........................................... 使いやすさ ....................................... コスト効率 ....................................... 第 2 章: Evolver について 14 14 15 16 16 16 17 17 17 18 18 11 12 Evolver について Evolver ソフトウェア パッケージを使用して、あらゆるタイプの問 題に対する最適な解を簡単に見つけることができます。Evolver は、 目標とする出力を得るために最も適した入力を判断するためのツール です。例えば Evolver を使って、利益を最大限にしたりリスクを最 小限に抑えるための最適な条件の組み合わせや順序を判断したり、最 小量の原料から得ることのできる最大商品数などを求めることができ ます。Evolver は Microsoft Excel スプレッドシート プログラムの アドインとして機能します。まず Excel を使って問題のモデルを設 定してから、Evolver でその問題を解決します。 まず Excel で問題のモデルを作成してから、Evolver アドインで解決します。 Excel は、問題の実用的なモデルを作成するために大半のユーザーが 必要とする、すべての数式、関数、グラフ、およびマクロ機能を提供 します。Evolver は、モデルに含まれる不確実性と、探している解を 指定するためのインターフェイスおよび、その解を見つけるためのエ ンジンを提供します。この 2 つのプログラムを連携させることによ り、実質的にモデル化が可能なすべての問題に対する答えを見つける ことが可能になります。 第 2 章: Evolver について 13 Evolver の仕組み Evolver は、Palisade 社独自の一連の遺伝的アルゴリズムを使用し て問題の最適な解を検索し、確率分布とシミュレーションを用いてモ デルに含まれる不確実性に対応します。 遺伝的アルゴリ ズム Evolver では、モデルの最適な解を見つけるために遺伝的アルゴリズ ムを使用しています。遺伝的アルゴリズムはダーウィンの進化論の原 理を模倣したもので、ある問題に対して何百もの起こりうる解が存在 する中で、これらが互いに競争し合った結果「適者」のみが生存する ような環境を作り出します。生物の進化と同じように、各解がその優 れた「遺伝子」を子孫の解に受け渡し、解の集団全体がさらにより良 い解へと進化し続けていきます。 遺伝的アルゴリズムの分野では、その基盤である進化論の分野と似た 用語がよく使われます。例えば、「交差」関数を使って解の検索を絞 り込む、「突然変異」率により「遺伝子プール」の多様化を促進する、 解または「個体」の「個体群」全体を評価する、などという言い方を します。Evolver の遺伝的アルゴリズムの仕組みについて詳しくは、 「第 7 章: 遺伝的アルゴリズム」を参照してください。 14 Evolver について 最適化について 最適化とは、数多くの起こりうる解の中から最適なものを見つけ出す 過程のことです。通常の場合、問題には特定の数式や制限に基づいて 相互に作用する、多くの変数が関与しています。例えば、それぞれ異 なる数量の複数の商品を生産している 3 つのプラントを所有する企 業があると想定します。各商品の生産費、各プラントから各店舗への 出荷コスト、そして各プラントの制限を前提とした場合、運送費を最 小限に抑えた状態で各地のリテール店舗の需要を満たすには、どのよ うな生産方法が一番適しているでしょうか。最適化ツールは、こうし たタイプの問題を解決するために設計されています。 一般的な最適化では、特定のリソースを前提とした場合に 最高の利益につながる組み合わせを見つけます。 上記の例で可能な各解は、どのプラントがどの商品を生産しており、 それがどのトラックでどのリテール店舗に運送されるかを完全に指定 したリストで構成されます。最適化の問題のその他の例としては、利 益を最大限にする方法、コストを最小化する方法、最多数の人命を救 助する方法、回路のノイズを最小化する方法、一連の都市間の経路を 最短化する方法、そして最も効果のある広告メディアの購入ミックス の判断、などが挙げられます。また、最適化の問題の重要なカテゴリ として、スケジュール管理が挙げられます。これには、特定の勤務シ フト中の効率の最大化や、さまざまなグループの会議時間の予定重複 を最小化する問題などが含まれます。最適化について詳しくは、「第 6 章: 最適化」を参照してください。 第 2 章: Evolver について 15 Excel でモデルを構築する理由 どのような体系であっても、その効率を上げるには、まずその動作を 理解する必要があります。体系のモデルを構築する理由は、ここにあ ります。複雑な体系を調査する場合、これを抽象化したモデルが必要 となりますが、そのモデルから実世界に通用する結果を得るには、変 数間の因果関係を単純化し過ぎないことが肝心です。今日ではソフト ウェアの機能改善やプロセッサ処理能力の向上により、経済学者は経 済のより現実的なモデルを構築し、科学者は化学反応の予測精度を高 め、またビジネスマンは企業モデルの感度をより高めることが可能に なっています。 この数年間でコンピュータ ハードウェアおよび Microsoft Excel な どのソフトウェア プログラムが飛躍的な進歩を遂げ、パーソナル コ ンピュータさえあれば誰もが複雑な体系の現実的なモデルを構築でき るようになりました。Excel の組み込み関数、マクロ機能、そしてク リーンでわかりやすいインターフェイスを使えば、初心者であっても 複雑な問題のモデル化と分析を簡単に行うことができます。モデルに ついて詳しくは、「第 8 章: Evolver のその他の機能」を参照して ください。 Evolver の利点 Evolver 特有の技術によって、パーソナル コンピュータと Windows 版 Excel さえあれば最適化ツールを利用して問題を解決することが できます。Evolver が発売される以前には、生産効率を上げたり最適 な解を見つけ出す方法としては、機能の劣る問題最適化ソフトウェア を使う、推測する、最適化を専門とするコンサルタントに依頼してカ スタムのソフトウェアを設計・作成する、という 3 つのオプション に限られていました。Evolver の主な利点としては次のようなものが あります。 推測が不要にな る 16 相互に作用する多くの変数を前提として、これらの変数の最適な組み 合わせ、順位、またはグループ分けを判断する必要がある場合、人は つい知識と経験に基づく推測をしがちです。そして、単なる推測にと どまらずモデル化や分析を行うためには、複雑なプログラミングや難 解な統計または数学的なアルゴリズムが必要だと思っている人も沢山 います。優れた最適な解が見つかれば、数億円の資金や、大量の燃料、 また数ヶ月分の作業時間を節約することが可能になります。高速なデ スクトップ コンピュータを安価で入手でき、Excel や Evolver とい ったソフトウェアも手軽に購入できるようになった今日では、単なる 推測だけに頼ったり、貴重な時間を割いて手作業で多くのシナリオを 試したりする必要はありません。 Evolver について より正確で意味 のある分析 Evolver では Excel のすべての数式とマクロを使用して、あらゆる 問題のより現実的なモデルを構築できます。Evolver を使用する場合、 特定のアルゴリズムが実世界の複雑さに対処できないためにモデルの 精度が落ちる、ということはありません。従来の一般的なソルバー (統計および線形プログラミング ツール) では、ユーザーが問題の変 数間の相互作用について無理に推測する必要があるため、結果として 極度に単純化された非現実的なモデルが出来上がります。これらの解 決ツールで対応できるレベルにまで問題を単純化してしまうと、得ら れる解も抽象化された非実用的なものとなります。そして、問題に多 くの変数、非線形関数、ルックアップ テーブル、if-then 文、デー タベース クエリー、または確率的 (ランダム) な要素が含まれてい る場合には、モデルをいかに単純化したとしても、こうしたツールで 問題を解決することは不可能です。 優れた柔軟性 シンプルで規模の小さい線形・非線形タイプの問題を処理できる解決 アルゴリズムは数多くあります。これには、山登り法やソルバー、そ の他の数学的方法が含まれます。こうした汎用の最適化ツールはスプ レッドシートのアドインとして提供されていますが、処理の対象とな るのは数値計算による最適化に限られます。より複雑で規模の大きい 問題の場合、特定のカスタム アルゴリズムを作成することで良い結 果を得ることができたとしても、これには多くの調査や開発努力が必 要となります。また、このような方法で作成したプログラムは、モデ ルが変化するごとに変更を加える必要があります。 Evolver では、数値計算の問題を処理できるだけでなく、一般に市販 されている世界で唯一のプログラムとして、ほとんどの順列組み合わ せ問題を解決することができます。組み合わせ問題には、さまざまな 順列や組み合わせを試す必要のある変数が含まれています。例えば、 野球チームの打順決定は、選手がバッター ボックスに入る順番を決 める順列組み合わせ問題です。また、複雑なスケジュール管理も順列 組み合わせ問題の 1 つです。Evolver があれば、このようにほかの ツールでは対処が不可能なさまざまなタイプの問題を、1 つのツール で解決することができます。Evolver 独自の遺伝的アルゴリズムによ り、ほぼあらゆるタイプ、サイズ、そして複雑度のモデルを最適化す ることが可能です。 高機能 Evolver を使用すればさらに優れた解を見つけ出すことができます。 大半のソフトウェアは数学的かつ体系的な手法により最適な解を求め ます。これらの手法では、既存の解に基づいてより優れた一番近い解 を検索することしかできません。しかしこのような「局所的」な解は、 実際の最適解とはかけ離れていることがあります。Evolver では、イ ンテリジェントな方法により可能性のある領域全体から標本を抽出す るため、一段と優れた「大局的」な解を見つけることができます。 第 2 章: Evolver について 17 使いやすさ Evolver は強力な機能と優れた柔軟性を備えていますが、その基盤と なる複雑な遺伝的アルゴリズムを用いた手法をユーザーが理解する必 要はまったくなく、使い方はごく簡単です。Evolver にいわゆる問題 の「要点」を理解させる必要はありません。必要なのは、各シナリオ の適性を評価できるスプレッドシート モデルを指定するだけです。 変数が入っているスプレッドシート セルを選択し、探している答え を Evolver に指定します。Evolver を使用するのに難しい技術を理 解する必要は一切なく、問題分析における仮説の処理を自動的に行う ことができます。 数学的プログラミングおよびモデル構築用に開発されたプログラムは いくつも市販されていますが、スプレッドシートは毎月何百万という ユーザーが購入する、最もよく使われるプログラムです。行と列を使 ったわかりやすい形式を採用したスプレッドシートには、ほかの専用 製品よりも設定や管理がしやすいという利点があります。さらに、ワ ードプロセッサやデータベースといったほかのプログラムとの互換性 にも優れ、どのスタンドアロン型製品よりも多くの数式、書式設定オ プション、グラフ オプション、およびマクロ機能が用意されていま す。Evolver は Microsoft Excel のアドインとして機能するので、 多様な関数や開発ツールを利用して問題の現実的なモデルを手軽に構 築することができます コスト効率 多くの企業では、専門家に依頼してカスタムの最適化システムを構築 しています。このようなシステムは優れたパフォーマンスを発揮しま すが、その開発と導入には何か月もの時間と大規模な投資が必要です。 また、カスタムのシステムは使い方が難しいために多額のトレーニン グ費用を必要とし、日々のメンテナンスも欠かせません。さらに、い ったん構築したシステムに変更を加える場合、最適な解を求めるため のまったく新しいアルゴリズムを開発する必要が出てくることも多々 あります。これに対して Evolver を利用すれば、今日市販されてい る最も強力な遺伝的アルゴリズムが低コストで手に入り、さまざまな タイプの問題について迅速で正確な解を得ることが可能になります。 使い慣れたわかりやすい作業環境で使用できるので、トレーニングや メンテナンス費用もほぼ不要です。 また、Evolver の最適化機能を自社のカスタム プログラムに取り入 れたい場合には、Visual Basic を使って専用のスケジュール管理、 製造、そして財務管理システムを短時間で開発することができます。 Evolver ベースのアプリケーションを開発する方法の詳細については、 Evolver デベロッパー キットを参照してください。 18 Evolver について 第 3 章: Evolver: ステップバイ ステップ はじめに .................................................. 21 Evolver の基本操作 ........................................ 23 Evolver の起動 .......................................... Evolver ツールバー ............................... サンプル モデルを開く ............................ [Evolver - モデル] ダイアログ ........................... ターゲット セルの選択 ................................... 調整可能セルの範囲の追加 ................................ 解法の選択 ....................................... 制限 .................................................... 制限の追加 ....................................... シンプルな値の範囲と数式による制限 ................ その他の Evolver オプション ............................. 停止条件 ......................................... [表示] タブのオプション........................... 最適化の実行 ............................................ Evolver ウオッチャー ............................. 最適化の停止 ..................................... 概要レポート ..................................... 結果によるモデルの更新............................ 第 3 章: Evolver: ステップバイステップ 23 23 23 24 25 25 27 28 29 29 32 32 34 35 36 37 38 39 19 20 はじめに この章では、Evolver の最適化の処理全体についてステップごとに解 説します。ハードディスクに Evolver がインストールされていない 場合、このチュートリアルを始める前に、まず「第 1 章: はじめ に」のインストール方法を参照して Evolver をインストールしてく ださい。 このチュートリアルでは、事前作成されたスプレッドシート モデル を開き、確率分布と Evolver のダイアログを使って Evolver に問題 を指定します。その後、Evolver が解を検索する間に進行状況を確認 し、Evolver ウオッチャーのいくつかのオプションについて考察しま す。特定のトピックについて詳しくは、このマニュアルの索引または、 「第 5 章: Evolver リファレンス ガイド」を参照してください。 注意:以下の画面は Excel 2007 の例です。それ以外のバージョンの Excel ではウィンドウの表示が若干異なる場合があります。 問題を解決するには、まずその問題を正確に表せるモデルが必要です。 このモデルは、特定の一連の入力値 (調整可能セル) を評価して、こ れらの入力により問題がどの程度解決されるかを示す数値 (評価、ま たは「適応度」関数) を生成できなければなりません。Evolver が解 を探す間、この適応度関数によって各推測の適応度についてのフィー ドバックを Evolver に返し、Evolver がさらに優れた推測を行える ようにします。問題のモデルを作成する際には、この適応度関数に十 分注意する必要があります。Evolver は、このセルの値を最大化また は最小化できるような最適な解を探します。 第 3 章: Evolver: ステップバイステップ 21 22 Evolver の基本操作 Evolver の起動 Evolver を起動する方法は 2 つあります。1) Windows デスクトップ の [Evolver] アイコンをクリックするか、2) Windows の [スター ト] > [プログラム] の項目から[Palisade DecisionTools] を選択し、 さら に [Evolver] を選択し ます。どち らの手順で も、Microsoft Excel と Evolver の両方が起動します。 Evolver ツール バー Evolver が読み込まれると、Excel に Evolver リボンまたはツール バーが表示されます。このツールバーには、Evolver の設定や、最適 化の開始、一時停止、そして停止などを行うボタンがあります。 サンプル モデル を開く ここでは Evolver と一緒にインストールされたサンプル モデルを使 いながら Evolver の機能について説明します。以下の手順に従って ください。 1) [ヘルプ] メニューの [サンプル スプレッドシート] コマンドか ら、「Bakery – Tutorial Walkthrough.XLS」ワークシートを開 きます。 第 3 章: Evolver: ステップバイステップ 23 このサンプル シートには、ベーカリーを経営するためのシンプルな 利益最大化問題が設定されています。このベーカリーでは 6 種類の パンを作っています。ここでは売上高、コスト、および生産利益を管 理するベーカリーのマネージャとして、生産限度のガイドラインを満 たす範囲内で利益を最大限にするには各種類のパンをそれぞれ何ケー ス生産すればよいかを判断することにします。生産限度のガイドライ ン項目は以下のとおりです。1) 低カロリー パンの特定数量を生産す ること。2) 高ファイバー パンと低カロリー パンの比率を特定範囲 内に保つこと。3) 5 グレイン パンと低カロリー パンの比率を特定 範囲内に保つこと。4) 生産時間を特定の所要人時限度内に留めるこ と。 [Evolver - モデル] ダイアログ このワークシート用に Evolver のオプションを設定するには、次の 手順を行います。 1) Evolver ツールバーの一番左にある Evolver モデルのアイコン をクリックします。 [Evolver - モデル] ダイアログ ボックスが表示されます。 [Evolver - モデル] ダイアログは、問題をわかりやすく簡潔に指定 できるように設計されています。このチュートリアルの例では、全体 的な利益を最大限にするために、各種類のパン製品を何ケースずつ生 産したらよいかを判断しようとしています。 24 Evolver の基本操作 ターゲット セルの選択 サンプル モデルにある「合計利益」というセルが、いわゆるターゲ ット セルです。ターゲット セルには、最小化または最大化しようと している値、または、あらかじめ設定された値にできるだけ近づける 必要のある値が含まれています。ターゲット セルを指定するには、 次の手順を行います。 1) [最適化ゴール] オプションを [最大] に設定します。 2) [セル] フィールドに、ターゲット セル「$I$11」を入力しま す。 Evolver ダイアログのフィールドにセル参照を入力する方法は 2 つ あります。1) カーソルでフィールドをクリックし、フィールド内に 直接参照を入力します。または、2) 選択したフィールドにカーソル を置いた状態で、[参照入力] アイコンをクリックして、マウスで直 接ワークシート セルを選択します。 調整可能セルの範囲の追加 次に、Evolver が解を見つけるために調整することのできる値を含む セルの場所を指定する必要があります。これらの変数の追加と編集は、 [モデル] ダイアログの [調整可能セルの範囲] セクションを使って 1 ブロックずつ行います。[調整可能セルの範囲] に入力できるセル の数は、お使いの Evolver のバージョンによって異なります。 1) [調整可能セルの範囲] セクションの [追加] ボタンをクリック します。 2) 調整可能セルとして追加するセルとして、Excel で $C$4:$G$4 を選択します。 調整可能セルの 最小 - 最大範囲 の入力 通常の場合は調整可能セルの取りうる値を、最小 - 最大の範囲を指 定して制限する必要があります。Evolver ではこの制限のことを「範 囲」制限と呼びます。この最小 - 最大の範囲は、一連の調整可能セ ルを選択して、簡単に入力できます。ベーカリーの例では、生産でき る各種類のパンのケース数の最小値が 0、最大値が 100,000 です。 この範囲制限を入力するには、次の手順を行います。 1) [最小] セルに 0 を入力し、[最大] セルに 100,000 を入力し ます。 2) [値] セルのドロップダウン リストから [整数] を選択しま す。 第 3 章: Evolver: ステップバイステップ 25 次に、2 番目の調整可能セル範囲を入力します。 1) [追加] をクリックして 2 番目の調整可能セルを入力します。 2) セル B4 を選択します。 3) [最小] に 20,000、[最大] に 100,000 を入力します。 すると低カロリー パンの生産レベルを示す最後の調整可能セル B4 が指定されます。 ほかにも追加の変数がある場合は、ここで一連の調整可能セルの入力 を続けます。Evolver で作成できる調整可能セルのグループの数に制 限はありません。セルをさらに追加するには、[追加] ボタンをクリ ックします。 26 Evolver の基本操作 一度設定した調整可能セルを、後日あらためて確認したり変更したり する場合もあります。これには、テーブル内で最小 - 最大の範囲を 編集します。また、一連のセルを選択してから [削除] ボタンをクリ ックすると、セルを削除できます。 解法の選択 調整可能セルを定義するときに、使用する解法を指定できます。調整 可能セルのタイプによって、それぞれ異なる解法により処理されます。 解法は調整可能セルのグループに対して設定します。解法を変更する には、[グループ] ボタンをクリックして [調整可能セルのグループ 設定] ダイアログ ボックスを表示します。デフォルト値の [レシピ] 解法は、一般によく使用される解法で、各セルの値をほかのセルとは 独立した値として変更できます。この解法はデフォルトとしてすでに 選択されています。 最もよく使われる解法は [レシピ] と [順序] です。この 2 つを一 緒に使用して、複雑な順列組み合わせ問題を解くことができます。 「レシピ」解法は、各変数をレシピの材料として扱い、各変数の値を 個別に変更することにより、「ベストな組み合わせ」を探し出します。 これに対して「順序」解法は、変数間で値をスワップして、初期の値 の位置を動かすことで「ベストな順序」を探し出します。 このモデルでは解法は [レシピ] のままにし、次の手順を行います。 ♦ [説明] フィールドに「生産ケース数」と入力します。 第 3 章: Evolver: ステップバイステップ 27 制限 Evolver では制限を入力できます。制限とは、解を有効とみなすには 満たされなければならない条件のことです。このサンプル モデルで は、各種類のパンの生産レベルの可能な組み合わせが有効とみなされ るには、3 つの追加の制限を満たす必要があります。これらの制限は、 調整可能セルに対して入力した範囲制限とは別個のものです。ここで 使用する制限は次のとおりです。 1) 高ファイバー パンと低カロリー パンの比率を許容範囲内に保つ (高ファイバーの生産ケース数 >= 1.5 * 低カロリーの生産ケー ス数) 2) 5 グレイン パンと低カロリー パンの比率を許容範囲内に保つ (5 グレインの生産ケース数 >= 1.5 * 低カロリーの生産ケース 数) 3) 生産時間を所要人時制限内に留める (合計所要人時 < 50,000) Evolver でモデルの起こりうる解を生成するたびに、ここで入力した 制限が満たされているかが確認されます。 制限は [Evolver - モデル] ダイアログの下部にある [制限] セクシ ョンに表示されます。Evolver では次の 2 種類の制限を指定できま す。 28 ♦ ハード制限。ハード制限は、解を有効とみなすには満たさなけれ ばならない条件です。(例えば、ハードな反復試行制限として C10<=A4 という条件を指定すると、解で生成された C10 の値が セル A4 の値より大きい場合はその解が破棄されます。) ♦ ソフト制限。ソフト制限は、できる限り満たすことが望ましい 条件ですが、適応度やターゲット セルの結果が大きく改善され る場合には妥協することが可能なものです。(例えば、ソフト制 限として C10<100 と指定すると、C10 の値が 100 を超えること は可能ですが、その場合はターゲット セルの計算値が所定のペ ナルティ関数に基づいて減算されます。) Evolver の基本操作 制限の追加 制限を追加するには、次の手順を行います。 1) Evolver のメイン ダイアログの [制限] セクションにある [追 加] ボタンをクリックします。 モデルの制限を入力するための [制限設定] ダイアログ ボックスが 表示されます。 シンプルな値の 範囲と数式によ る制限 制限の入力には、「シンプル」と「数式」の 2 つの形式を使用でき ます。「シンプル」な値の範囲を指定する場合、<、<=、>、>=、また は = のシンプルな関係を使用して制限を入力できます。シンプルな 値の範囲を使った一般的な制限としては、例えば「0< A1 の値 <10」 があります。この場合、[セル範囲] ボックスに A1、[最小] ボック スに 0、[最大] ボックスに 10 を入力します。演算子はドロップダ ウン リストから選択します。シンプルな値の範囲を使った制限では、 [最小] ボックスのみ、[最大] ボックスのみ、またはその両方を指定 することができます。 これに対して「数式」形式の制限では、有効な任意の Excel 式 (例 えば A19<(1.2*E7)+E8 など) を制限として入力できます。Evolver は、可能なすべての解について、入力された数式の真偽を確認し、制 限が満たされているかどうかを判断します。ワークシート セルに制 限としてブール演算式を使用するには、[制限設定] ダイアログ ボッ クスの [数式] フィールドでそのセルを参照します。 第 3 章: Evolver: ステップバイステップ 29 ベーカリーのモデルの制限を入力するには、新しい制限を 3 つ入力 する必要があります。これらはハード制限であり、ここに入力した条 件を満たさない可能な解は Evolver によって破棄されます。まず、 シンプルな値の範囲形式のハード制限を入力します。 30 1) 説明ボックスに「許容合計作業時間」と入力します。 2) [制限対象の範囲] に「I8」と入力します。 3) [制限対象の範囲] の右から [<=] 演算子を選択します。 4) [最大] ボックスに「50,000」と入力します。 5) [最小] ボックスのデフォルト値 (0) を消去します。 6) [制限対象の範囲] の左のドロップダウン リストで空白を選択 し、演算子を消去します。 7) [OK] をクリックしてこの制限を設定します。 Evolver の基本操作 次に、数式形式のハード制限を入力します。 1) [追加] をクリックして [制限設定] ダイアログ ボックスをもう 一度表示します。 2) 説明ボックスに「高ファイバーと低カロリーの許容比率」と入力 します。 3) [エントリー スタイル] ボックスで [数式] を選択します。 4) [制限数式] ボックスに「C4>= 1.5*B4」と入力します。 5) [OK] をクリックします。 6) [追加] をクリックして [制限設定] ダイアログ ボックスをもう 一度表示します。 7) 説明ボックスに「5 グレインと低カロリーの許容比率」と入力し ます。 8) [エントリー スタイル] ボックスで [数式] を選択します。 9) [制限数式] ボックスに「D4>= 1.5*B4」と入力します。 10) [OK] をクリックします。 [モデル] ダイアログの [制限] セクションに、追加した制限が表示 されます。 第 3 章: Evolver: ステップバイステップ 31 その他の Evolver オプション 表示の更新、乱数シード、最適化の停止条件などのオプションを使用 して、最適化の処理中の Evolver の動作を制御することができます。 ここでは停止条件と表示の設定をいくつか指定してみます。 停止条件 Evolver は、指定の条件が満たされるまで処理を継続します。停止条 件により、次のいずれかが満たされると Evolver が自動的に処理を 停止するようにします。a) 所定数のシナリオ (つまり「解」) を試 行した後、b) 所定の時間が経過した後、c) 最後の n 個のシナリオ で改善が見られない場合、d) 入力した Excel 数式が真になった場合。 停止条件を表示したり編集したりするには、次の手順を行います。 1) Evolver ツールバーの [最適化設定] アイコンをクリックしま す。 2) [実行詳細] タブを選択します。 [最適化設定] ダイアログでは、最適化の停止条件の任意の組み合わ せを選択できます。または、停止条件を一切指定しないことも可能で す。複数の停止条件を選択すると、Evolver はそのうち 1 つでも満 たされる条件がある場合に停止します。停止条件を 1 つも選択しな いと、ユーザーが Evolver ツールバーの [停止] ボタンをクリック して手動で停止するまでの間、Evolver は処理を続行します。 32 Evolver の基本操作 試行 時間 進行 数式が真 このオプション は、Evolver で実 行する試行の数を 設定します。各試 行につき Evolver は問題のすべての 変数のセット (つ まり 1 つの可能な 解) を評価しま す。 指定した時間が経 過すると Evolver が停止します。こ の時間には 4.25 などの小数も入力 できます。 これは、改善度が低下 した時点で Evolver を 停止するオプション で、一番よく使われま す。例えば、これまで に見つかったベストの 解が、その後 100 回の 試行で改善されなかっ た場合に、Evolver を 停止させることができ ます。 指定した Excel 数式がモデルの再 計算中に真になる と、Evolver が停 止します。 ♦ Evolver の処理を条件に関係なく継続させるには、すべての停止 条件をオフにします。 第 3 章: Evolver: ステップバイステップ 33 [表示] タブのオ プション [表示] タブにある一連のオプションを使って、Evolver の実行中に 画面に表示される情報を指定することができます。 [最適化時] セクションには、次のオプションがあります。 試行ごと 新たなベスト試行ごと 再計算を実行するたびに 画面が更新され、Evolver が変数を調整して出力を 計算する様子を確認でき ます。Evolver の使い方 を学習する際や、新しい モデルに対して Evolver を実行する場合にはこの オプションをオンにする ことをお勧めします。モ デルの計算が正しく行わ れているかどうか確認で きます。 Evolver が新しいベストの解 を生成するたびに画面が更新 されるので、最適化の処理中 にいつでも現在の最適な解を 確認できます。 ♦ 34 表示しない 最適化の処理中に画面を 一切更新しません。最適 化の処理速度は最短にな りますが、実行中は計算 結果に関するフィードバ ックがほとんど得られま せん。 [試行ごと] をオンにします。 Evolver の基本操作 最適化の実行 これまでの手順で、生産制限のガイドラインを満たしながら合計利益 が最大になるようモデルを最適化する準備ができました。以下の手順 を行います。 1) [OK] をクリックして [最適化設定] ダイアログを閉じます。 2) [最適化の開始] アイコンをクリックします。 Evolver が問題の最適化を開始し、スプレッドシートに調整可能セル (生産ケース数) の現在のベストの値が表示されます。強調表示され たセルに「合計利益」のベスト値が表示されます。 最適化の実行中、進行状況ウィンドウに次の情報が表示されます。1) これまでの最適な解。2) Evolver による最適化の開始時の、ターゲ ット セルの初期値。3) モデルですでに実行した試行数および、その うち有効な (つまり制限を満たす) 試行数。4) 最適化を開始してか らの経過時間。 実行中は [Excel の更新オプションの表示] アイコンをいつでもクリ ックして、各試行の画面を随時更新することができます。 第 3 章: Evolver: ステップバイステップ 35 Evolver ウオッ チャー Evolver では、各試行解について実行される処理のログを随時表示す ることもできます。このログは Evolver の実行中、Evolver ウオッ チャーに表示されます。Evolver ウオッチャーを使用して、最適化の 実行中に問題のさまざまな設定を確認したり変更したりすることがで きます。実行中の試行のログを表示するには、次の手順を行います。 1) 進行状況ウィンドウにある、ウオッチャー (虫眼鏡) のアイコン をクリックして Evolver ウオッチャーを表示します。 2) [ログ] タブをクリックします。 このレポートには、各試行解の実行結果が表示されます。[結果] 列 は、最小化・最大化する必要のあるターゲット セルの試行ごとの値 です。この例ではセル $I$11 の「合計利益」がこれに相当します。 C4 から G4 の各列は、調整可能セルに使用した値です。 36 Evolver の基本操作 最適化の停止 Evolver は 5 分経過した時点で最適化を停止します。または、次の 手順で最適化を停止することもできます。 1) Evolver ウオッチャーまたは [進行状況] ウィンドウで、[停止] アイコンをクリックします。 Evolver の処理が停止すると、次のオプションが含まれた [停止オプ ション] タブが表示されます。 [Evolver - 最適化設定] ダイアログで設定した停止条件が 1 つでも 満たされると、これらのオプションが自動的に表示されます。 第 3 章: Evolver: ステップバイステップ 37 概要レポート Evolver では、実行日時、使用した最適化設定、ターゲット セルの 計算値、および各調整可能セルの値などが含まれた、最適化の概要レ ポートを作成できます。 このレポートは、最適化を繰り返し行った結果を比較する場合に便利 です。 38 Evolver の基本操作 結果によるモデ ルの更新 ベーカリーのモデル ワークシートの 6 種類の各パンの値を、最適化 された新しい値で更新するには、次の手順を行います。 1) [停止] ボタンをクリックします。 2) [表示されたワークブックの調整可能セル値を更新する対象] オ プションが [ベスト] に設定されていることを確認します。 すると BAKERY – TUTORIAL WALKTHROUGH.XLS スプレッドシートが、 ベストな解を生成した新しい変数値をすべて反映した状態で表示され ます。 重要事項: この例では Evolver が 3,645.773 の合計利益を生み出す 解を見つけましたが、実際の結果はこの値と異なることもあります。 その理由は、Evolver とほかのすべての問題解決アルゴリズムとの重 要な相違点にあります。Evolver の遺伝的アルゴリズム エンジンの ランダムな性質は、多様な問題を解決して最適な解を見つける機能に とって不可欠なものです。 第 3 章: Evolver: ステップバイステップ 39 Evolver を実行した後でスプレッドシートを保存すると、Evolver の 実行後にシートの値を元に戻した場合でも、Evolver ダイアログのす べての設定がそのシートに保存されます。次回このシートを開くと、 Evolver の最新の設定がすべて自動的に読み込まれます。ほかのすべ てのサンプル ワークシートには Evolver の設定がすでに入力されて いるので、最適化をすぐに実行することができます。 注意: 最適化設定がすべて指定済みのベーカリーのモデルを確認する には、「Bakery.XLS」というサンプル モデルを開いてください。 40 Evolver の基本操作 第 4 章: 実用例 はじめに .................................................. 43 広告ミックス .............................................. 45 アルファベット順の並べ替え ................................ 47 タスクの割り当て .......................................... 49 ベーカリー ................................................ 51 予算の配分 ................................................ 53 化学平衡 .................................................. 55 授業のスケジュール ........................................ 57 コードのセグメント化 ...................................... 59 ノースダコタ: 制限付きの経路判断 .......................... 63 製作工場のスケジュール .................................... 65 ラジオ塔の配置 ............................................ 67 ポートフォリオの分散 ...................................... 69 ポートフォリオの配分 ...................................... 71 ラジオ送信機 .............................................. 73 購入判断 .................................................. 75 巡回セールスマンの問題 .................................... 77 第 4 章: 実用例 41 スペースシャトル .......................................... 79 証券トレーダー ............................................ 81 変圧器 .................................................... 83 輸送費 .................................................... 85 42 はじめに この章では、Evolver のさまざまな実用例について解説します。これ らの実用例は、実際のモデルに必要な特徴をすべて網羅しているとは 限りません。アイデアを得るためや、テンプレートとして活用してく ださい。すべての実用例で、ワークシートにすでに指定されている関 係に基づいて Evolver が解を見つける方法が取られています。した がって、解決対象の問題を正確に表すようなワークシート モデルを 作成することが重要です。 これらの Excel ワークシート例はすべて、EVOLVER5 ディレクトリ内 の EXAMPLES というサブディレクトリに保存されています。実用例で は色を使って内容を次のように区別しています。 ♦ 青枠のセル. . . Evolver によって調整される調整可能セルを 示します。 ♦ 赤枠のセル. . . 目標となるターゲット セルを示します。 各例には、ターゲット セル、調整可能セル、解法、制限など、すべ ての Evolver 設定がすでに指定されています。最適化を行う前に、 これらの設定内容を確認することをお勧めします。数式を確認したり、 さまざまな設定を試すことで、Evolver の使い方がよくわかるように なります。また、モデルのデータ例を独自のユーザー データに置き 換えることもできます。サンプル シートを変更したりカスタマイズ する場合には、ファイルを別名で保存して、オリジナルのサンプルを 維持しておくことをお勧めします。 第 4 章: 実用例 43 44 広告ミックス 広告エージェンシーが、対象視聴者の数を最大限にできるように PR 予算を配分するための一番効率的な方法を見つけようとしています。 ただし予算を超過することはできず、テレビの宣伝費がラジオの宣伝 費を下回ることができないという制限が課されます。 モデルの仕組み 第 4 章: 実用例 サンプル ファイル: Advertising Selection.xls ゴール: 広告費用を枠内に抑えながらさまざまな価格割引の ある各メディアに配分する。アピールできる視聴者 数を最大限にする。 解法: 予算 類似問題: 追加の制限が課される予算の問題。 まず、Evolver に対して変数の処理方法を指示する解法を選択する必 要があります。各解法の説明は「第 5 章: Evolver リファレンス ガ イド」を参照してください。 45 これは基本的には予算タイプの問題に、テレビの宣伝コストがラジオ の宣伝コストを上回らなければならないという制限が追加されたもの です。 解決方法 46 Evolver で調整する変数はセル範囲 C5:C9 に入っています。ここで は Evolver に対して「予算」解法を使ってこれらの変数を調整し、 各変数を独立値として扱うように指示します。合計視聴者数はセル G13 で SUM 関数により計算されます。Evolver にはこのセルを最大 化するよう指定します。ハード制限により、テレビの広告費がラジオ の広告費より大きくなるよう指定します。 広告ミックス アルファベット順の並べ替え この例では Evolver を使って 7 つの名前のリストをアルファベット 順に並べ替えます。これは単純な例ですが、Evolver では各データが 独立した複雑な並べ替えを処理したり、モデル内のその他の情報に基 づいて名前に重み付けをして並べ替えを処理することもできます。 モデルの仕組み 第 4 章: 実用例 サンプル ファイル: Alphabetize.xls ゴール: 名前のリストをアルファベット順に並べ替える。 解法: 順序 類似問題: Excel では処理できないあらゆる並べ替え問題。 「Alphabetize.xls」ファイルは Evolver の並べ替え機能を示す、ご くシンプルなモデルです。B 列に 7 人の人物のファースト ネームが 入っていて、A 列には各人に対応する ID 番号が含まれています。D 列では Excel の VLOOKUP 関数を使用して C 列で選択された番号に 対応する名前を求めます。セル範囲 E4:E9 はシンプルなペナルティ 関数を使用して、それより前の名前が後ろの名前の後に並べられるた びに 1 の値を割り当てています。ターゲット セルの E11 には、こ れらのエラーの合計値が含まれています。 47 解決方法 このモデルで調整する変数は、C 列 (C3:C9) に入っています。ここ では「順序」解法を使ってセル範囲 C3:C9 の値を調整するよう指定 します。「順序」解法は Evolver に対して、選択値の順序を入れ替 えて、新しい値を試行する代わりに変数のさまざまな組み合わせを試 行するように指示します。セル E11 のエラー合計が 0 に最も近くな る値を見つけるよう指示します。このターゲット セルが 0 の場合、 すべての名前の順序が正しいことを示します。 [Evolver - 最適化設定] ダイアログで停止条件を一切選択しないの で、Evolver ツールバーの [停止] ボタンをクリックして手動で停止 しない限りは Evolver が処理を続行します。ただしこのモデルでは 「最近似値」オプションを選択してあるので、Evolver はこの値が 0 に最も近くなる解を見つけた時点で、自動的に処理を停止します。 最適な個体群サイズを選択するための絶対の規則はないため、個体群 のサイズを小さく設定しています。これは、可能な解の合計数が少な い問題の場合には小さな個体群サイズでも十分であり、パフォーマン スの優れた解の交差に作業を集中しやすくなるためです。この問題で は 7 つの名前の可能な順序は 5,040 種類しか存在しません。 48 アルファベット順の並べ替え タスクの割り当て この例はリソースの割り当てに関するごく一般的な問題を表していま す。あるマネージャが 16 のタスクに 16 名の従業員をそれぞれ割り 当てようとしています。各従業員の各タスクを遂行する能力は 1 ～ 10 (1= 遂行不可能、10= 最適任) のスケールにより格付けされてい ます。ここでは各従業員をどのタスクに割り当てれば全体的な生産性 を最大限に伸ばすことができるかを判断することが課題となります。 第 4 章: 実用例 サンプル ファイル: Assignment of Tasks.xls ゴール: 全体の生産性を最大化できるように 16 名の従業 員を 16 のタスクに割り当てる。 解法: 順序 類似問題: 割り当ての問題、大半の従業員にとって都合の良 い会議スケジュールの設定、一連の作業に最適な 機械の選択問題。 49 このモデルは 16×16 のグリッド (セル範囲 B4:Q19) で構成されて いて、各従業員の各タスクへの適格度が指定されています。グリッド の右にある選択されたタスクの列 (S 列) では、各従業員をいずれか のタスクに任意に割り当てています。その次の列 (U 列) ではどのタ スクが割り当てられているかをチェックし、各従業員のそのタスクへ の適格度が入力されます。個々の適格度をすべて加算した合計した値 が、解全体の合計スコア (セル U21) となります。 モデルの仕組み 各タスクに割り当てる従業員は 1 名だけなので、タスク番号は重複 が不可能で 1 度しか使用できません。各従業員のタスク適格度は INDEX() 関数を使用して U 列に記録されます。これらのスコアがセ ル U21 で加算され、特定の割り当てのセットの合計スコアが求めら れます。 解決方法 Evolver では S 列にある選択されたタスクの変数 (S4:S19) を調整 します。ここでは「順序」解法を使ってセルの値を調整するよう指定 します。この解法ではセルの既存値を入れ替えるので、最適化を開始 する前に各値が 1 度だけ使われていることを確認する必要がありま す。Evolver でターゲット セル U21 の値を最大化するよう指定しま す。このセルの値が大きいほど割り当て全体の生産性が向上します。 50 タスクの割り当て ベーカリー この例は製造業によく見られる意思決定問題を表しています。製品の 種類が多くない場合でも、各製品の適正な生産数量を判断するのは困 難を極めます。ここではベーカリー経営者が、合計利益を最大化する ために各種類のパンの生産ケース数を判断しようとしています。従業 員の労働時間合計数や各製品の適切な比率などの制限についても以下 のように考慮する必要があります。(注意: このモデルについては 「第 3 章: Evolver ステップバイステップ」で説明済みです。) 第 4 章: 実用例 サンプル ファイル: Bakery.xls ゴール: 必要な生産量をすべて満たして利益を最大限にす るための各種類のパンの最適な生産量を求める。 解法: レシピ 類似問題: ポートフォリオ開発、製造計画。 51 モデルの仕組み この問題では表の一番上にある 4 行目に生産する各パン製品の数量 が入っています。各変数の値 (セル B4:G4) を調整すると、モデルに よって必要な労働時間とコストおよび、その生産量から得られる利益 が計算されます。利益 (セル範囲 B11:G11) の合計値が含まれている セル I11 が、最大化するターゲット セルとなります。 このモデルには 3 つの制限があります。これらはすべてハード制限 として設定されています。そのうち 1 つはシンプルな値の範囲形式 の制限で、あとの 2 つは Excel 数式を使った入力されています。 解決方法 52 Evolver はセル I11 (合計利益) の値が最大になるようなセル範囲 B4:G4 (生産量) の値を見つける必要があります。ここでは各値がほ かの値に依存しないので、「レシピ」解法を使用します。セル C4、 D4、および I8 の制限を満たすように指定します。 ベーカリー 予算の配分 ここでは上級管理者が、利益を最大限にするために最も効果的な各部 署への資金の配分方法を見つけようとしている場合の例を見てみます。 以下に、この企業のモデルと向こう 1 年間の予想利益を示します。 このモデルでは、年度予算に基づいて広告活動の売上げへの影響など について推測することにより、来年度の利益を予想しています。この モデルでは内容が簡素化されていますが、あらゆるケースをモデル化 し、Evolver で入力を提供して最善の出力を見つけるための方法を示 しています。 第 4 章: 実用例 サンプル ファイル: Budget Allocation.xls ゴール: 来年度の利益を最大化できるような方法で、5 つ の部署に年度予算を配分する。 解法: 予算 類似問題: 限られたリソース (労力、資金、ガソリン、時間 など) を、さまざまな方法や効率でこれを消費す るエンティティ間に配分する問題。 53 モデルの仕組み 「Budget Allocation.xls」ファイルは、企業の予算が将来の売上げ と利益にもたらす影響をモデル化しています。セル範囲 C4:C8 (変 数) には、5 つの部署それぞれに配分する金額が含まれています。こ の合計値がセル C10 で、この企業の予算総額を示します。この予算 は企業により設定されており、変更することはできません。 セル範囲 F6:F10 では、広告およびマーケティング予算に基づいて、 企業の製品に対する来年度の需要を計算しています。実際の売上げは、 計算された需要と供給のうち小さい方の値になります。需要は、製造 部と業務部に割り当てられた資金に依存しています。 解決方法 「予算」解法を使用してセル範囲 C4:C8 の値を調整することで、セ ル I16 の利益を最大限にします。各部署の予算の各調整可能セルに それぞれ個別の範囲を設定し、Evolver が負の値や、その部署の予算 に解として不適切な値 (広告に全額を割り当て、製造予算を 0 にす るなど) を使わないようにします。 「予算」解法は、選択された変数の適切な「ミックス」を見つけよう とする点で、「レシピ」解法に似ています。ただし、予算解法を用い る場合、すべての変数の和が Evolver での最適化をはじめる前の値 と等しくならなければならないという制限が追加されます。 54 予算の配分 化学平衡 いくつかの初期条件を前提としてある結果を生み出すようなモデルを 構築できる過程であれば、Evolver を使って最適化を行うことが可能 です。この例では Evolver を使用して、化学反応が平衡状態に至っ た後の自由エネルギーが最小になるような、さまざまな化学物質 (生 成物と反応物) のレベルを見つけます。複雑な化学過程では化合物の 濃度が一定して平衡状態に至るまでの間、成分 (試薬) と生成物が相 互に反応し合います。平衡状態に至ると、平衡化学物の反応物と生成 物の比率は例えば 5% と 95% というように一定します。 第 4 章: 実用例 サンプル ファイル: Chemical Equilibrium.xls ゴール: 反応環境の自由エネルギーを計算し、ソフト制限 を満たすような物質の量を見つける (一部の化学 物質量はほかの物質の量に比例)。 解法: レシピ 類似問題: 最も安定した市場均衡が得られる条件を判断する 問題。 55 モデルの仕組み この問題のセル範囲 B4:B13 にある変数は、混合する化学物質量を示 します。セル B15 で計算される合計量は、ペナルティに従って特定 の範囲内に収める必要があります。 F20:F22 の制限はソフト制限です。ソフト制限では Evolver に有効 な解のみを受け入れるよう強制するのではなく、特定の化学物質のほ かの物質に対する比率が所定の範囲内にない場合にそのペナルティを 計算します。これらのソフト制限は、ワークシート モデルに直接指 定されているペナルティ関数を使用します。ペナルティはセル F17 の自由エネルギーの合計値に加算されます。Evolver はターゲットの 値を最小化しようとするので、結果的にはペナルティの課されていな い解を探すことになります。 解決方法 56 セル範囲 B4:B13 にレシピ解法を使用します。セル F17 を最小化し ます。 化学平衡 授業のスケジュール 大学で 25 のクラスを 6 つの時間枠に割り当てる必要があります。 各クラスの時間はすべて 1 時間です。このような問題は通常「グル ーピング」解法を用いて解決します。ただしこの例では、クラスをス ケジュールする際にいくつもの制限が適用されます。例えば、医学部 の学生は同じ学期に生物学と化学の両方を取る必要があるため、これ らのクラスは同じ時間枠に設定できません。ここではこのような制限 を満たすため、「スケジュール」解法を使用します。「スケジュー ル」解法は「グルーピング」解法に似ていますが、特定のタスクをほ かのタスクの前、後、または最中に行う (あるいは行わない) 必要が あるという制限が課される点で異なります。 第 4 章: 実用例 サンプル ファイル: Class Scheduler.xls ゴール: 25 のクラスを 6 つの時間枠に割り当て、クラス がいっぱいで受講できない学生の数を最小限に抑 える。特定のクラスの時間枠に関する一連の制限 を満たす。 解法: スケジュール 類似問題: すべてのタスクの所要時間が同じで、事前に決め られた任意数の時間枠に割り当てることのでき る、すべてのスケジュール問題。特定の項目を割 り当てられるグループについて制限がある、すべ てのグループ化問題。 57 モデルの仕組み 「Class Scheduler.xls」ファイルには、数々の制限を満たす必要の ある、一般的なスケジュール問題のモデルが含まれています。セル範 囲 C5:C29 は、25 のクラスを 6 つの時間枠に割り当てています。使 える講義室は 5 つだけなので、1 つの時間枠に 6 つ以上のクラスを 割り当ててしまうと、実施できないクラスが出てきます。 セル範囲 K17:M25 には制限が含まれており、制限の説明は各項目の 左側に書かれています。制限には数値コードか、テキストの説明のい ずれかを使用できます。スケジュール問題の制限コードのリストにつ いては、「第 5 章: Evolver リファレンス ガイド」の「解法」セク ションを参照してください。 起こりうる各スケジュールは、a) 実施できないクラス数および、b) 講義室が満席でクラスに参加できない学生の数、の両方を計算するこ とにより評価されます。上記の制限 b) により、Evolver が学生数の 多いクラスをすべて同時にスケジュールしないようにします。1 つの 時間枠に割り当てられた大人数のクラスが 1 つか 2 つに限られてい れば、大きい講義室を使うことができます。 セル範囲 I8:N8 は、Excel 関数の DCOUNT を使用して、各時間枠に 割り当てられたクラス数を数えます。セル範囲 I9:N9 のすぐ下の部 分では、その時間枠で講義室が割り当てられなかったクラスの数を計 算しています。講義室がないクラスの合計数はセル K10 で求められ ます。 特定のクラスで必要な席数が、使用可能な席数を超えた場合、セル範 囲 I12:N12 でその超過数が計算され、K13 で席のない学生数が計算 されます。セル F6 では、席のない学生の総数が平均のクラス サイ ズに追加され、これに講義室のないクラスの数を掛け合わせています。 これにより、すべてのペナルティを 1 つのセルに組み合わせて、こ のセルの値が低いほど優れたスケジュールであることがわかるように します。 解決方法 58 セル範囲 C5:C29 を調整することにより F6 のペナルティ値を最小化 します。「スケジュール」解法を使用します。この解法を選択すると、 ダイアログ ボックス下部の [最適化のパラメータ] セクションに、 いくつかの関連オプションが表示されます。時間枠 (タイム ブロッ ク) の数を 6 に設定し、制限セルを K17:M25 に設定します。 授業のスケジュール コードのセグメント化 Windows プログラマがプログラムをいくつかのコード セグメントに 分け、使用中のコード セグメントのみをメモリに保存することで Windows のメモリ消費を効率化したいと考えています。 これは類似項目をいくつかのグループに分類する問題の例です。各項 目は同じグループ内のほかの項目とは簡単に相互作用できますが、異 なるグループにある項目同士の相互作用は難しくなります。各項目が ほかの全項目と直接作用するのを妨げるような自然な境界が存在する 場合 (例えばすべてのコンピュータ ユーザーが 1 台のプリンタに直 接接続したい場合など)、これらの項目をグループに分ける必要があ ります。効率的なグルーピングによって、全体の生産性を大幅に向上 させることができます。 第 4 章: 実用例 サンプル ファイル: Code Segmenter.xls ゴール: プログラムの処理速度が最短になるような方法 でプログラム ルーチンを 8 つのコード セグメ ントに分ける。 解法: グルーピング 類似問題: グルー プ間 の 通信コ スト が 最小に なる よ うな LAN 上のワークステーションのクラスタ化、ま たはマイクロチップ回路の区分。 59 モデルの仕組み Windows プログラマは、プログラムの効率を上げるためにプログラム をいくつかのセグメントに分けることがよくあります。Windows では 別のセグメントのルーチンを実行する必要がある場合、まず呼び出し 側のセグメントを破棄して、呼び出されたセグメントをディスクから 読み込みます。2 Mb のプログラムをそれぞれが 20 Kb の 80 セグメ ントに分けた場合、そのプログラムを実行するには 20 Kb のメモリ が必要となります。ただし、プログラムのパフォーマンスを維持する ためにセグメントの分け方を慎重に判断する必要があります。別のセ グメントにある関数を呼び出すと、同じセグメント内にある関数を呼 び出すよりも長い処理時間がかかります。別のセグメント間との関数 呼び出しを最小限に抑える問題のことを、コードのセグメント化問題 と呼びます。 アプリケーションの一部を最適化した結果、全体のパフォーマンスが 低下してしまう可能性もあるので、ここでは Evolver を使って大局 的な最適化を行うことにします。 「Code Segmenter.xls」サンプル ファイルでは、すでにセグメント 化されたコンパイル済みのアプリケーションを前提としています。こ のアプリケーションをユーザーが使用する場合と同じように実行し、 パフォーマンス追跡ルーチンによって各関数がほかの全関数を呼び出 す回数を追跡しています。この追跡結果はアプリケーションの一般的 な使用における各呼び出しの性質を表しており、これに基づいてさま ざまなセグメント化によって得られるアプリケーションの処理速度に ついての予測を立てることができます。 このワークシートは「SegCost」というカスタム関数を使用していま す。SegCost は、一般的な使用統計を取得するのと同じ方法でユーザ ーがプログラムを実行する場合の所要時間を計算します。所要時間は セグメント内呼び出しとセグメント間呼び出しの数をカウントし、こ れに各種類の呼び出しのコストを掛け合わせることで求められます。 ここでは 386 コンピュータを前提とし、セグメント内呼び出し (near call) にかかる時間を 7 クロックサイクル、セグメント間 (far call) の所要時間は 34 サイクルとして計算しています。 60 コードのセグメント化 SegCost 関数は Excel VBA マクロで次のように定義されています。 Function segCost(segs, calls, inP, outP) As Double Dim inCost#, outCost#, total#, temp#, tempPtr# Dim i%, j%, wide%, funcNumber%, ThisSeg%, OtherSeg% Dim NumCalls%, NumInCall%, NumOutCall%, SegOrder$, CallOrder$ SegOrder = Application.Names("segs").RefersTo CallOrder = Application.Names("calls").RefersTo NumInCall = 0 NumOutCall = 0 inCost = Range("k2") outCost = Range("k3") total = 0 wide = Range(CallOrder).Columns.Count For i = 1 To Range(SegOrder).Rows.Count ThisSeg = Range(SegOrder).Rows(i) For j = 1 To wide temp = Range(CallOrder).Rows(i).Columns(j) If temp <> 0 Then funcNumber = Int(temp) OtherSeg = Range(SegOrder).Rows(funcNumber + 1) NumCalls = 10000 * (temp - funcNumber) If ThisSeg = OtherSeg Then temp = NumCalls * inCost NumInCall = NumInCall + 1 Else temp = NumCalls * outCost NumOutCall = NumOutCall + 1 End If total = total + temp End If Next Next segCost = total End Function サンプル アプリケーションには 80 の関数が使われています。各関 数がほかの関数を呼び出す回数は「呼び出し」のセル範囲 (C5:I104) に保存されます。この例では 80 × 80 の行列を作成して呼び出しパ ターンを表すことも可能です。ただし n × n 式の表現は、Excel で は列数が 256 に制限されること、また必要なメモリ容量が増大する ことから、関数が 256 以上ある場合には使用できません。 第 4 章: 実用例 61 したがって、ここでは短縮表記を使って呼び出しパターンを表します。 まず、すべての関数が呼び出すほかの関数の数が特定の範囲を超える ことはないと仮定します。サンプル ファイルではこの上限を 7 に設 定しているために呼び出し範囲が 7 列になっていますが、この限度 は任意に設定できます。さらに、各関数がほかの関数から呼び出され る回数についても 9,999 回を超えることはないと仮定します。 では、関数 1 についてセル C5 から順に見てみることにします。関 数 1 は関数 3、9、81、41 をそれぞれ呼び出します。呼び出しの最 初の行 C5:I5 には、呼び出される各関数につき 1 つの実数が含まれ ています (例: 3.0023)。この整数部分 (3) は呼び出される関数を表 し、小数部分に 10,000 を掛けた値 (.0023 x 10,000 = 23) はアプ リケーションの標準的な使用において関数 1 が関数 3 を呼び出した 回数を表しています。したがって 9.1117 という値は、この関数が関 数 9 を 1,117 回呼び出したことを示します。この短縮形式によりメ モリを節約し、Excel で使用できる列数を最大限に活用することがで きます。 セル範囲 A5:A104 (セグメントのセル範囲) には、各関数が割り当て られたセグメントの番号が含まれています。セル K4 で「SegCost」 を実行して現在のセグメント化方法の全体的なパフォーマンスが計算 されます。 解決方法 62 ここではセル範囲 A5:A104 を調整して、セル K4 の値を最小化しま す。解法は「グルーピング」を使用します。「グルーピング」解法は、 Evolver に対して変数を x 個のグループに分けるよう指定します。x は、最適化の開始時に調整可能セルにある異なる値の数です。 コードのセグメント化 ノースダコタ: 制限付きの経路判断 ある不動産業者がノースダコタ州の物件をすべて見て回りたいと考え ています。その際、一部の物件をほかの物件の前に訪れる必要があり ます。これは、いくつもの都市を訪れる際に各都市を 1 度ずつ訪れ るための最短経路を見つけるという点では典型的な巡回セールスマン 問題と似ています。ただしここでは、特定の都市をほかの都市の前に 訪れる必要がある (例えば 都市 2 は都市 4 の後に訪れる必要があ るなど) という追加の制限が課されます。したがって、「順序」解法 の代わりに「プロジェクト」解法を使います。 プロジェクトでは、あるタスクをほかのタスクの前に完了するという 必要条件を満たしながら、一連のタスクの順序を決定します。カスタ ム関数と「プロジェクト」解法を使用して、完了期日やリソース使用 率などの任意数の条件の組み合わせに基づいてプロジェクトの最適な 遂行順序を求めることができます。 第 4 章: 実用例 サンプル ファイル: Dakota.xls ゴール: ノースダコタ州 41 都市を巡回する経路を計画 し、特定都市をほかの都市の前に訪れる必要条 件を満たす最短経路を見つける。 解法: プロジェクト 類似問題: リソース使用率が最適になるようなプロジェク トのスケジュール調整。一部の作業をほかより 先に完了し、合計労働時間を削減するための機 械工場の作業フロー管理。 63 モデルの仕組み セル範囲 F3:F43 には各都市を訪れる順序が含まれています。順序と x,y 座標による各都市のロケーション (セル範囲 C3:D43) に基づい て、セル H10 で経路の合計距離が求められます。セル H10 で合計距 離を迅速に計算するために「BigRouteLength」というカスタム関数を 使用しています。 セル範囲 J3:L43 には順序の制限が指定されています。この表は、ど の都市の前にどの都市を訪れる必要があるかを示したものです。ここ では 8 つの都市 (1、2、3、4、5、7、11、13) について、その前に 訪れる必要のある都市が指定されています。 解決方法 64 セル範囲 F3:F43 を調整することにより H10 の合計距離を最小化し ます。「プロジェクト」解法を使用し、J3:L43 にタスク順序を指定 します。タスクの順序は [調整可能セルのグループ設定] ダイアログ の [直前のタスク] フィールドで設定します。 ノースダコタ: 制限付きの経路判断 製作工場のスケジュール 金属加工工場が、さまざまな機械で処理される工程に分割できる一連 のジョブをスケジュールする最適な方法を探しています。各ジョブは 5 つのタスクから構成され、これらのタスクは決まった順序で行う必 要があります。各タスクは特定の機械で処理する必要があり、それぞ れの所要時間も決まっています。機械は 5 台あり、ジョブの数も 5 つです。 シート上部の「スケジュールの図化」ボタンをクリックすると、棒グ ラフが再描画されて各ジョブ タスクの実行スケジュールが表示され ます。 第 4 章: 実用例 サンプル ファイル: Job Shop Scheduling.xls ゴール: すべてのジョブの合計所要時間が最小限になる ような方法で、ジョブの各工程 (タスク) を機 械に割り当てる。 解法: 順序 類似問題: スケジュールやプロジェクト管理の問題。 65 モデルの仕組み セル D5 は、最初のタスクの開始から最後のタスクが完了するまでの 経過時間を計算します。ここではこの合計時間を最小限にする必要が あります。セル範囲 G11:G35 には、最適な割り当て順序を見つける ために入れ替えることのできる変数 (タスク) が含まれています。ワ ークシートの方程式により、各タスクを適切な機械で行えるようにな るまでの時間が計算されます。 解決方法 一連の調整可能セル G11:G35 を選択し、順序解法を選択します。セ ル D5 を最小化します。 66 製作工場のスケジュール ラジオ塔の配置 ラジオ局が 12 の主要な町で構成される地域に放送塔を建設したいと 考えています。各町の人口はさまざまで、信号の届く範囲も各ラジオ 塔によって異なります。ここでは、塔の放送半径内に入る聴取者の数 が最大限になるような位置にラジオ塔を配置するのが目標です。 y x 1 1 より複雑なロケーション判断の問題の例としては、複数の工場を a) ベンダーと顧客の両方に近い地域内に、b) 安価な空き地を利用して、 c) 技術訓練を受けた人材が多くいるような場所に配置する問題など があります。こうしたモデルには、ほかにも税制上の優遇措置などの 条件による影響も追加することができます。Evolver を使用して、 x,y 座標やときには x,y,z 座標で指定される領域内の最適なロケー ションを見つけ出すことができます。 第 4 章: 実用例 サンプル ファイル: Radio Tower Location.xls ゴール: 放送範囲内の潜在的な聴取者数が最大になるよう に、ラジオ塔の最適な位置を x,y 座標値として 判断する。 解法: レシピ 類似問題: 倉庫と店舗間で必要な出荷が最小限になるような 倉庫の場所の判断。住宅密度などの要素を考慮に 入れながら、限られた数の消防署で最大数の住人 をカバーできるような消防署の配置。 67 モデルの仕組み 「Radio Tower Location.xls」ファイルのモデルでは、2 次元座標を 使って、3 つのラジオ塔の配置によって聴取範囲内に入る聴取者の数 を判断します。セル範囲 C6:D8 には 3 つのラジオ塔の x,y 座標が 含まれています。モデルの図には、Windows ペイント プログラムか ら貼り付けた人口密度のビットマップ画像 (緑色) と、自動再計算に よりラジオ塔の場所を表示する Excel の散布グラフが含まれていま す。 12 の 町 は そ れ ぞ れ 点 で 表 さ れ て い ま す 。 こ の Excel モ デ ル は K4:M15 で町とラジオ塔間の距離を計算し、各町が聴取範囲内にある か (○)、範囲外にあるか (×) を判断します。範囲内にあるすべて の町の人口合計 (これが最大化するターゲットです) は、セル O17 で計算されます。 解決方法 ラジオ塔の配置 (C6:D8) を調整することでセル O17 の聴取者数を最 大化します。「レシピ」解法を使用し、変数の範囲を 0 ～ 50 (当該 地域の限界) に設定します。 「レシピ」解法は、Evolver に対して変数の値を自由に調整するよう 指定します。パンを焼くためのレシピと同様に、最適な結果が得られ る材料 (x,y 座標値) の組み合わせを見つけることが目標です。 68 ラジオ塔の配置 ポートフォリオの分散 ある金融ブローカーが、それぞれ時価の異なる 80 銘柄の証券を抱え ています。このブローカーは、これら銘柄を 5 つのパッケージ (ポ ートフォリオ) にグループ化し、各パッケージの時価がなるべく均等 になるようにしたいと考えています。 これは、箱詰め問題と呼ばれる種類の問題です。箱詰め問題には、例 えば貨物船の積荷をなるべく均等な重さになるよう配分する場合など も該当します。船倉への穀物の積み込みなど、無数の小さなアイテム をいくつかのグループに分ける場合は、各グループがほぼ均等な重量 になるように配分を推測することができます。ただし、重量やサイズ のそれぞれ異なる数十個のパッケージをさまざまな組み合わせで積み 込んで、効率的な荷積みによりバランスを改善することも可能です。 第 4 章: 実用例 サンプル ファイル: Portfolio Balancing.xls ゴール: 銘柄リストを時価総額がなるべく均等になるよ うな方法で 5 つのポートフォリオに分ける。 解法: グルーピング 類似問題: チームごとの能力がほぼ均等になるようにチー ム分けをする。重量が均等に分散されるような 方法で貨物船の船倉にコンテナを積み込む。 69 モデルの仕組み 「Portfolio Balancing.xls」ファイルは、一般的なグルーピングの 問題をモデル化したものです。A 列には特定の銘柄の ID 番号、B 列 には各銘柄の時価がドルで指定されています。C 列は各銘柄を 5 つ のポートフォリオのいずれかに割り当てています。グルーピングや箱 詰めの問題を設定してグルーピング解法を使用する場合、Evolver を 起動する前に、現在のシナリオで各グループ (1 ～ 5) が少なくとも 1 度は使われていることを確認する必要があります。 セル範囲 F6:F10 では 5 つのポートフォリオそれぞれの時価総額を 求めます。この計算には画面外のデータベース条件 (I 列) とセル範 囲 F6:F10 の DSUM() 式が使われます。例えば、セル F6 は、C 列で グループ 5 に割り当てられたすべての値 (B 列) の DSUM を計算し ます。 セル F12 は、STDEV() 関数を使ってポートフォリオ全体の時価の標 準偏差を計算します。これにより、各ポートフォリオの時価総額が互 いにどの程度近くなるかを推測できます。グラフには、各ポートフォ リオの合計額が示されています。参照ラインは、すべてが均等である 場合の金額、つまりゴールを表します。 解決方法 セル範囲 C5:C104 を調整することにより、セル F12 の値を最小化し ます。ここでは「グルーピング」解法を使用します。1、2、3、4、5 の各値が C 列に少なくとも 1 度は使われていることを確認します。 「グルーピング」解法は、Evolver に対して変数を x 個のグループ に分けるよう指定します。x は、最適化の開始時に調整可能セルにあ る異なる値の種類の数です。 70 ポートフォリオの分散 ポートフォリオの配分 ある若夫婦がそれぞれ異なる利率、予想成長率、リスクの伴うさまざ まなタイプの投資からなる資産を保有しています。この夫婦はいくつ かの数式によりさまざまな重み付けを行い、これら投資の特定の組み 合わせにより彼らのニーズがどの程度満たされるかを示すカスタムの 「スコア」を計算しました。 第 4 章: 実用例 サンプル ファイル: Portfolio Mix.xls ゴール: リスクと収益の現在のニーズに基づいて、利益 を最大限に伸ばせる投資配分を見つける。 解法: 予算 71 モデルの仕組み これは、投資収益と損失リスクの最適なバランスを見つけようとする、 典型的な金融モデルです。A 列にある各資産に対して C 列で重み付 けがされています。このモデルはポートフォリオ内の各資産の重みを 収益率に掛け合わせ、セル C18 で合計収益率を求めています。また、 セル C19 で計算される合計リスクがセル D19 にある許容リスクを超 えないようにする必要があります。 解決方法 セル C22 の合計スコアは、合計収益率からペナルティ (リスクが許 容範囲を上回る場合) を差し引いた値です。このスコアを最大化しま す。 72 ポートフォリオの配分 ラジオ送信機 あるラジオ局が、9 つの主要な町から構成される地域にある使用廃止 となった放送塔を 3 つ購入しました。このラジオ局は新しいラジオ 送信機を購入してこれらの放送塔に設置し、放送を再開したいと考え ています。 ただし予算が限られるため、9 つすべての町で受信できる範囲で送信 機のコストを最小限に抑えるのが目標です。ここでは送信機のコスト が信号強度に直接比例する線形の価格モデルを想定し、信号が最も弱 い放送機を探しますが、送信機の実際のタイプと価格を指定したルッ クアップ テーブルを簡単に作成することもできます。 第 4 章: 実用例 サンプル ファイル: Power Stations.xls ゴール: 周辺 9 つの町で聴取できる範囲で、古いラジオ 塔に設置する最小 (安価) の放送機を見つけ る。 解法: レシピ 類似問題: 一連の要素を、定義の明確な少数のセットによ りカバーする必要のある問題。 73 モデルの仕組み これはラジオ塔の配置問題 (Radio Tower Location.xls) とよく似て いますが、塔の場所はすでに決まっており、セル範囲 E5:E7 にある 各塔の信号強度が調整可能な変数となります。3 つの塔のコストを合 計したセル E12 をターゲットとして最小化します。 セル範囲 K4:M12 で各町から塔までの距離を計算し、その町がいずれ かの送信機の受信エリアに入っている場合は N 列の値が TRUE にな ります。これらすべての制限が「全域聴取可能」という 1 つのハー ド制限によってチェックされます。この制限は AND($N$4:$N$12) と いう式で定義され、N 列の値がすべて TRUE の場合のみに TRUE を返 します。 解決方法 74 セル範囲 E5:E7 のラジオ塔放送範囲を調整することにより、必要な 信号強度 (セル E12) を最小化します。「レシピ」解法を使用し、変 数の範囲を 0 ～ 100 に設定します。Excel 式を使用して、上記のハ ード制限を 1 つ設定します。 ラジオ送信機 購入判断 複数の品目を組み合わせて注目する場合、数量割引があるためにコス ト効率を最小限にするにはどうしたらよいかを判断するのは困難です。 このモデルではシンプルな価格表に特殊な溶剤の数量割引価格が一覧 されています。少なくとも 155 リットルの溶剤を購入する必要があ ります。容器のサイズは小、中、大、特大の 4 種類です。 コストを最小化するには各サイズの容器をいくつずつ購入すればよい かを判断します。 第 4 章: 実用例 サンプル ファイル: Purchasing.xls ゴール: 155 リットルの溶液を最も安価に購入する方法 を判断する。 解法: レシピ 類似問題: 上記と逆に、注文数量が多いほどコストも安価 になるような価格表を作成する。 75 モデルの仕組み 溶剤はそれぞれ 3、6、10、または 14 リットルの容器に入って販売 されています。セル範囲 D6:H9 はこれら各サイズの価格表です。セ ル範囲 H13:H16 は各サイズの購入数量を示します。K 列で各サイズ の合計金額を計算し、セル K18 に注文全体の合計金額が入っていま す。このモデルでは、必要な購入量 (セル I19) を 155 以上の値に 変更することができます。セル I18 には購入した合計量がリットル で示されており、このセルの値はセル I19 の必要量 (155) と等しい かそれ以上でなければなりません。ハード制限を 1 つ設定し、合計 購入量が必要条件を満たすように指定します。 必要量は 155 リットルなので、特大サイズを 11 個 (154 リットル) と小サイズを 1 個 (3 リットル) 購入すれば合計 157 リットルで必 要条件を満たすことができます。その場合、価格表によると合計額は $1,200 です。しかし最適化を行うことにより、さらにコスト効率の 良いサイズの組み合わせを見つけることができます。 解決方法 76 セル範囲 H13:H16 の購入数量を調整することにより、セル K18 のコ ストを最小化します。「レシピ」解法を使用して値を調整し、変数の 範囲を 1 ～ 20 に設定します。容器の一部のみを購入することはで きないので、[調整可能セル] ダイアログの整数オプションをオンに して Evolver に整数のみを試行するよう指定します。155 リットル に満たない量を購入することもできないので、「I18>155」というハ ード制限を 1 つ設定します。 購入判断 巡回セールスマンの問題 セールスマンが担当地域の各都市を 1 度ずつ訪問する必要がありま す。すべての都市を最短距離で巡回するには、どの順序で移動すれば よいでしょうか？これは典型的な最適化問題ですが、都市の数が多く 50 を超えるような場合、この不確実要素に従来の手法で対処するこ とは非常に難しくなります。 これと類似した問題に、工場で行うタスクの最適な順序を見つけると いう問題が挙げられます。例えば、白い塗料の後で黒い塗料を塗布す る方が、その反対の順序で行うよりもずっと簡単な場合があります。 Evolver でこうしたタイプの問題を解決するには、「順序」解法が一 番適しています。 第 4 章: 実用例 サンプル ファイル: Salesman Problem.xls ゴール: n 個の都市をそれぞれ 1 度ずつ訪問できる最 短経路を見つける。 解法: 順序 類似問題: 回路板の穴を最短時間で空ける方法を見つけ る。 77 モデルの仕組み 「Salesman Problem.xls」ファイルは、都市間の距離をテーブルで調 べ、各都市への移動距離を計算します。A 列には特定の都市の ID 番 号が入っています。B 列では、ルックアップ関数を使ってこれらの番 号が表す都市名を求めます。都市 (とその番号) の表示順序は、訪問 順序を表します。例えば、セル A3 に 9 と入力した場合、最初にオ タワを訪れることになります。同様に、A4 に 6 (ハリファックス) が指定されている場合は、ハリファックスを 2 番目に訪問します。 都市間の移動距離は、C25 以降のテーブルに指定されています。この テーブルの移動距離は対称的です (つまり A から B への距離と、B から A への距離は同じです)。現実的なモデルの場合には、非対称の 走行距離を設定して、料金所、利用できる移動方法、風向き、道の傾 斜などのために、往復で移動時間が異なる点を考慮に入れることも可 能です。 次に、関数を使用してこれらの都市間の経路の距離を計算する必要が あります。経路の合計距離はセル G2 に保存されます。最適化する必 要があるのはこのセルです。この計算には RouteLength 関数を使い ます。これは Salesman Problem.xls に含まれている、カスタムの VBA 関数です。 解決方法 セル範囲 A3:A22 を調整することにより、セル G2 の値を最小化しま す。「順序」解法を使用します。また、最適化を始める前に、調整可 能セル (A3:A22) に 1 ～ 20 の値が入っていることを確かめます。 「順序」解法は、選択した変数を並べ替えて既存の変数のさまざまな 順列を試すよう、Evolver に指定します。 78 巡回セールスマンの問題 スペースシャトル スペースシャトル Evolver III 号の乗組員が、ロケット噴射の推力 と方向を求めて最少量の燃料で目的地に達する方法を判断しようとし ています。付近の太陽の重力によるスイングバイ効果を利用して燃料 を節約すると、さらに優れた解となります。 第 4 章: 実用例 サンプル ファイル: Space Navigator.xls ゴール: 消費燃料が最小限になるような方法でスペース シャトルを目的地に到達させる。付近の惑星の 重力を利用する。 解法: レシピ 類似問題: プロセス管理の問題。 79 モデルの仕組み セル範囲 Q5:R15 には、10 ステップある各噴射の推力と方向値が入 っています。ここではセル Q16 を最小化します。この値は 10 のス テップで燃焼される燃料の合計です (Q4:Q13)。 ハード制限は、シャトルの最終位置が目的地から a) 10 水平単位以 内および、b) 10 垂直単位以内であることです。 解決方法 80 セル Q16 を最小化します。選択範囲 Q5:R13 に対してレシピ解法を 使用する調整可能セル グループを 1 つ作成します。「噴射サイズ」 セル (Q5:Q13) の値は 0 ～ 300、「方向変化」セル (R5:R13) は -3 ～ 3 でなければなりません。噴射の方向はラジアンを使って表され ます。1 ラジアンは約 57 度に相当します。 スペースシャトル 証券トレーダー S&P 500 のトレーダーが、従来のファンダメンタル分析に比べてテク ニカル分析の方がより正確な株式予測を行うことができ、いったんシ ステムを構築すれば最終的に時間を節約できると判断しました。一見 したところ取引判断を左右するルールが無限にあるように思えますが、 実際に相当な収入を生むことのできるルールはほんの僅かです。そこ でインテリジェントなコンピュータ検索を利用して、過去のケースに ついて、どのルールに従った場合に特定期間の利益が最大になったか を判断することにします。 第 4 章: 実用例 サンプル ファイル: Trader.xls ゴール: 特定な期間に利益を最大化できるような 3 つの ルールを見つける。 解法: レシピ 類似問題: 最良の結果につながる最適な平均移動値を見つ ける問題、ルールまたは条件を見つけようとす るすべての問題。 81 モデルの仕組み このモデルではいくつかの調整可能セル グループを使って全体的な 問題を解決します。各取引日につき 3 つのルールを評価します。3 つすべてのルールが真である場合はコンピュータがその日に銘柄を購 入し、そうでない場合は売却します。(より現実的なトレーディング システムでは、購入と売却だけでなく持ち株をホールドすることもあ ります。) 各ルールはセル範囲 C5:E8 にある 4 つの数値のセットにより次のよ うに記述されます。1) ルールが参照するデータ ソース、2) データ 値が基準値を上回るべきか下回るべきか、3) ルールが真かどうかを 判断するための基準値、4) 値自体を検査するか、または前日の値ま たは前日以降の変化を検査するかを判断する修正値。 基準値の範囲は 0 ～ 1 で、データ ソースの範囲の割合を表します。 例えば出来高の範囲が 5,000 ～ 10,000 であり、基準値が 0.0 の場 合は出来高 5,000 に一致し、基準値が 1.0 の場合は出来高 10,000 に一致し、さらに基準値が 0.5 の場合は出来高 7,500 に一致します。 この方法によってルールが実際のデータ値には関係なく、すべてのデ ータ ソースを参照することができます。 解決方法 82 「レシピ」解法を使って調整可能セル グループを作成します。C5:E5、 C6:E6、C7:E7、および C8:E8 の各行は個別に作成し、各グループを 整数や範囲など独自のオプションに簡単に割り当てることができるよ うにします。各変数セットの設定は F5:F8 に指定されます。セル E10 を最大化します。このセルはこれらのルールを使って行われたト レーディングのシミュレーションを実行するマクロを呼び出します。 その結果、履歴データベースに含まれる各取引日のトレーディングの シミュレーション後の合計利益がセル E10 に返されます。 証券トレーダー 変圧器 定格容量 1080 VA、負荷損 28 ワット未満、表面放熱 0.16 ワット /cm2 以下の二巻線変圧器を設計する際に、パフォーマンスの必要条 件を満たす範囲でコストを最小限にしたいとします。 第 4 章: 実用例 サンプル ファイル: Transformer.xls ゴール: 変圧器の導入および運用コストを最小化する。 解法: レシピ 類似問題: 回路の設計、橋の設計。 83 モデルの仕組み 定格、負荷損失、および放熱に関する制限はソフト制限として設定し ます。ソフト制限を作成するには、必要条件を満たさない解や無効な 解にペナルティを適用します。指定の条件を満たさなければならない ハード制限と異なり、Evolver は無効な解でも試行できますが、これ らの解にはモデル内の違反を検査する関数によってペナルティが課さ れるため、ターゲット セルの値は有効な解に比べて低くなります。 したがって最終的には、進化を続ける可能な解の個体群からこれらの 解は破棄されます。 ソフト制限を使用したモデルでは、問題の制限がそれほど厳しくない 場合にはハード制限よりも優れた解が見つかることがあります。また、 ソフト制限の場合、制限に多少違反していても非常に優秀な解を Evolver が受け入れることができるので、すべての制限を満たすそれ ほど優れない解より望ましい結果を生み出す可能性があります。 解決方法 84 セル F11 とセル F12 で材料費 (導入費用) と運用費用 (電気料金 * 廃棄電気量) を計算します。これらに F18:F20 に設定されたペナル ティ関数の値を加味した、制限適用後の最終コストをセル F22 で求 めます。レシピ解法を使用してこのターゲット セルの値を最小化し ます。 変圧器 輸送費 ここでは国内のさまざまな場所にトラックで製品を輸送する一番安価 な方法を判断します。この典型的な問題は、従来からある Microsoft ソルバーの例を拡張したものです。 各工場の供給限度を超えずに各都市区域からの需要を満たす範囲で、 製造工場から都市部の需要中心地近辺の倉庫へ製品を輸送する費用を 最小化します。 問題をさらに現実的なものにするには、トラックの必要台数によって 配送費用が決まるように設定を変更できます。トラック 1 台で最大 6 つの製品を運送できるとすると、14 の製品を運ぶには 3 台のトラ ックが必要です (6 + 6 + 2 = 12)。 第 4 章: 実用例 サンプル ファイル: Transportation.xls ゴール: 3 つの工場から 3 つの倉庫へ製品をトラックで 輸送する、最も安価な方法を判断する。 解法: レシピ 類似問題: 通信ネットワークの設計。 85 モデルの仕組み セル範囲 C5:E7 には各工場から各倉庫に配送する製品の数が含まれ ています。セル範囲 C13:E13 では、これらの製品の輸送に必要なト ラックの台数を計算します。以下のハード制限を設定します。1) 各 工場から発送する合計数が、各工場の在庫量を超えないこと、2) す べての工場から各倉庫へ発送する合計数が、各倉庫で必要な数と等し いかそれ以上であること。この制限により、各倉庫に必要数の製品が 配送されると同時に、工場の生産能力に負荷がかからないようにしま す。 解決方法 0 ～ 500 の整数を使用して、レシピ解法をセル範囲 C5:E7 に適用し ます。一連のハード制限を各工場について入力し、その工場からの発 送数が工場の供給能力を超えないようにします。次に 2 番目のハー ド制限を各倉庫について入力し、その倉庫への配送合計数が倉庫の需 要を下回らないようにします。セル B22 の配送費用を最小化します。 86 輸送費 第 5 章: Evolver リファレンス ガイド [モデルの定義] コマンド ................................... 89 調整可能セルの範囲 ...................................... 91 調整可能セル グループ ................................... 93 レシピ解法 ....................................... 95 順序解法 ......................................... 96 グルーピング解法 ................................. 97 予算解法 ......................................... 98 プロジェクト解法 ................................. 99 スケジュール解法 ................................ 100 交差と突然変異率 ................................ 103 タイム ブロックと制限セルの数.................... 104 直前のタスク .................................... 104 演算子 .......................................... 105 制限 ................................................... 107 追加 - 制限の追加 ............................... 107 シンプルな制限と数式による制限................... 108 ソフト制限 ...................................... 109 [最適化設定] コマンド .................................... 113 [最適化設定] コマンドの [最適化設定] コマンドの [最適化実行詳細] [最適化設定] コマンドの [最適化設定] コマンドの [一般] タブ .................... [実行詳細] タブ................. のオプション.................... [表示] タブ .................... [マクロ] タブ .................. 113 114 115 117 118 [最適化の開始] コマンド .................................. 119 [ユーティリティ] コマンド ................................ 121 [アプリケーション設定] コマンド ........................ 121 [制約ソルバー] コマンド ................................ 122 第 5 章: Evolver リファレンス ガイド 87 Evolver ウオッチャー ..................................... 125 [Evolver [Evolver [Evolver [Evolver [Evolver [Evolver 88 ウオッチャー] ウオッチャー] ウオッチャー] ウオッチャー] ウオッチャー] ウオッチャー] の の の の の の [進行] タブ ................... 126 [サマリー] タブ ............... 128 [ログ] タブ ................... 129 [個体群] タブ ................. 130 [相違] タブ ................... 131 [停止オプション] タブ ......... 132 輸送費 [モデルの定義] コマンド モデルのゴール、調整可能セル、および制限を定義 Evolver の [モデルの定義] コマンドを選択するか、Evolver ツール バーで [モデルの定義] アイコンをクリックすると、[モデル] ダイ アログが表示されます。 [Evolver - モデル] ダイアログ [Evolver - モデル] ダイアログを使って、Evolver に最適化する問 題を指定します。このダイアログを新しい Excel ワークブックで開 くと、すべての値が空の状態で表示されますが、いったん指定した情 報は各ワークブックに保存されます。同じシートをもう一度開くと、 保存された値が表示されます。このセクションでは、このダイアログ の各要素について説明します。 第 5 章: Evolver リファレンス ガイド 89 [モデル] ダイアログには、次のオプションがあります。 z [最適化ゴール] - [最適化ゴール] オプションを使用して、 Evolver にどのような解を探しているかを指定します。[最小] を選択すると、Evolver は、ターゲット セルの値が可能な限り 最小になるような変数値を探します (検索可能な最小値は 1e300 です)。[最大] を選択すると、Evolver は、ターゲット セルの値が最大値になるような変数値を探します (検索可能な最 大値は +1e300 です)。 [ターゲット値] を選択すると、Evolver は、ターゲット セルの 値がユーザーの指定した値にできるだけ近づくような変数値を探 します。Evolver はこのような結果を生み出す解を見つけると自 動的に停止します。例えば Evolver に対して、結果が 14 に一 番近くなる解を検索するよう指定すると、値が 13.7 や 14.5 な どになるシナリオが見つかります。ここで、13.7 の方が 14.5 よりも 14 という値に近いことに注意してください。Evolver で は、値が指定の値より大きいか小さいかは関係なく、目標値との 差異のみが考慮されます。 z [セル] - セル、つまり「ターゲット セル」には、モデルの出力 が含まれます。Evolver が生成した各「試行解」(調整可能セル の可能な値の各組み合わせ) に対して、このターゲット セルの 値が 1 つ生成されます。ターゲット セルには、調整可能セルに 直接、あるいは一連の計算を介して間接的に依存する数式が含ま れている必要があります。この数式は、SUM() などの Excel の 標準の式か、ユーザーが定義する VBA マクロ関数を使って指定 できます。VBA マクロ関数を使用すると、Evolver でより複雑な モデルを処理できるようになります。 Evolver は解を検索する際に、ターゲット セルの値を「適応度 関数」として使用して、各シナリオの適性を評価し、その結果か ら変数値の異種交配を続けるか破棄するかを判断します。個体群 に受け渡す遺伝子を決定する「適応度関数」は、生物の進化に喩 えれば死に相当します。モデルの構築にあたっては、Evolver が 起こりうる結果を計算する際にその進展状況を正確に測定できる よう、ターゲット セルには特定のシナリオの適応度、つまりフ ィットが反映されるようにする必要があります。 90 [モデルの定義] コマンド 調整可能セルの範囲 [調整可能セルの範囲] テーブルには、Evolver が調整できるセルま たは値の各範囲と、これらのセルに入力した説明が表示されます。各 行に 1 セットの調整可能セルが表示されます。[調整可能セルのグル ープ] には、1 つ以上の調整可能セルが含まれています。特定の調整 可能セル グループ内のすべてのセル範囲には、共通の解法、交差率、 突然変異率、および演算子が設定されています。 調整可能セルには問題の変数が含まれるので、Evolver を使用する前 に、少なくとも 1 つの調整可能セル グループを定義する必要があり ます。大半の問題は 1 つの調整可能セル グループで定義できますが、 より複雑な問題の場合には、さまざまな解法を同時に使用して複数の 変数セットを処理することもあります。この独自のアーキテクチャに よって、調整可能セルのグループをいくつも使って複雑な問題も簡単 にモデル化することが可能になります。 調整可能セルの範囲を入力するには、次のオプションを使用できます。 z [追加] - 新しい調整可能セルを追加するには、[調整可能セル] リスト ボックスの隣にある [追加] ボタンをクリックします。 追加するセルまたはセル範囲を選択すると、[調整可能セルの範 囲] テーブルに新しい行が追加されます。このテーブルに、その 範囲のセルの [最小] 値と [最大] 値および、テストする値の種 類 (指定範囲内の [整数] 値、または [すべて] の値など) を入 力できます。 z [最小]、[最大] - 調整可能セルの位置を指定したら、次に [最 小] と [最大] を入力して各調整可能セルの値の許容範囲を設定 します。デフォルトでは、各調整可能セルは正と負の無限大の範 囲内の実数 (倍精度浮動小数点) 値を取ることができます。 第 5 章: Evolver リファレンス ガイド 91 範囲の設定は、制限として強制的に適用されます。Evolver では、 変数が所定の範囲を超える値を取ることは許可されません。 Evolver のパフォーマンスを向上させるには、変数の範囲をでき るだけ小さくすることをお勧めします。例えば、変数が負の値を 取りえない場合や、特定の変数の値として Evolver で検討する 範囲を 50 ～ 70 に限定できる場合などもあります。 z [範囲] - [範囲] フィールドには、調整するセル (範囲) の参照 を入力します。参照を入力するには、マウスでスプレッドシート の 範 囲 を 選 択 す る か 、 範 囲 名 ま た は 有 効 な Excel 参 照 (Sheet1!A1:B8 など) を入力することもできます。[範囲] フィ ールドは、すべての解法で使用できます。ただし、レシピ解法と 予算解法では、調整可能セルの範囲を入力するための [最小]、 [最大]、[値] の各オプションが追加されることもあります。 注意: 変数の範囲を小さくすることで、検索の対象範囲を制限 し、Evolver による解の収束の処理時間を短縮することができま す。ただし、変数値の範囲をあまり小さくしすぎると、Evolver で最適な解が見つからない可能性があるので、注意が必要です。 z [値] - [値] オプションを使用して、指定範囲のすべての変数 を実数ではなく整数として処理するよう (例えば、22.395 を 22 として処理するよう)、Evolver に指定します。このオプション は、「レシピ」と「予算」の解法を使用する場合のみ利用できま す。デフォルトでは変数が実数として処理されます。 モデルで変数を使用してテーブルからアイテムを検索する場合 (例え ば HLOOKUP()、VLOOKUP()、INDEX()、OFFSET() を使用する場合など)、 必ず [整数] オプションを選択してください。整数オプションを設定 すると、選択した範囲のすべての変数が影響を受ける点に注意してく ださい。一部の変数のみを実数として扱い、残りを整数として扱うに は、調整可能セルのグループを 2 つ作成し、一方のグループを整数、 もう片方を実数として処理することができます。これを行うには、調 整可能セルのレシピ グループを 1 つ追加して、[値] を [すべて] のままにします。次に、セル範囲をもう 1 つ追加し、その値オプシ ョンに [整数] を設定して、整数の調整可能セルのみを選択します。 92 [モデルの定義] コマンド 調整可能セル グループ 調整可能セルの各グループに、複数のセル範囲を指定することができ ます。これにより、関連のあるセル範囲グループの「階層」を構築で きます。各グループ内にある各セル範囲ごとに最小 - 最大の範囲制 限を指定できます。 特定の調整可能セル グループ内のすべてのセル範囲には、共通の解 法、交差率、突然変異率、および演算子が設定されています。これら は [調整可能セルのグループ設定] ダイアログで指定できます。この ダイアログを開くには、[調整可能セルの範囲] テーブルの隣にある [グループ] ボタンをクリックします。新しいグループを作成してこ れに調整可能セルの範囲を追加したり、既存のグループの設定を変更 することができます。 第 5 章: Evolver リファレンス ガイド 93 [調整可能セルのグループ設定] ダイアログの [一般] タブには、次 のオプションがあります。 z [説明] - ダイアログやレポートに、調整可能セル範囲のグルー プについての説明として表示されます。 z [解法] - グループ内の各調整可能セル範囲に適用する解法を選 択します。 Evolver で調整するセルの範囲を選択するときに、それらの調整可能 セルに適用する「解法」も選択します。基本的には、各解法がまった く異なる遺伝的アルゴリズムを用いており、それぞれ独自の最適解選 択、交差、突然変異のルーチンを使用しています。変数の値を変化さ せる方法は解法によって異なります。 例えば「レシピ」解法は、選択された各変数をレシピの材料として扱 うため、各変数の値をほかの変数値とは独立して個別に変更すること ができます。これに対して「順序」解法は、調整可能セル間で既存の 値をスワップして、元々あった値を異なる変数に割り当てます。 Evolver には 6 つの解法が用意されています。このうち 3 つの解法 (レシピ、順序、グルーピング) は、まったく異なるアルゴリズムを 使用しています。残りの 3 つは最初の 3 つの「子孫」で、追加の制 限が適用されます。 次のセクションでは、各解法の機能について説明します。各解法の使 い方について詳しく理解するには、Evolver に付属のサンプル ファ イルの内容および、「第 4 章: 実用例」を参照してください。 94 [モデルの定義] コマンド レシピ解法 「レシピ」解法は、最もシンプルで一番よく使われる種類の解法です。 レシピ解法は、一連の変数があり、その各変数をほかの変数とは独立 して調整できる場合に使用します。この解法では各変数をケーキの各 材料のように扱います。「レシピ」解法を指定すると、Evolver がこ れらの変数をさまざまな値に設定してベストな組み合わせを見つけま す。レシピの変数に適用される唯一の制限は、これらの値が取りうる 範囲 (最小値と最大値) です。この範囲 (例えば「1 ～ 100」の範 囲) は [調整可能セル] ダイアログの [最小] フィールドと [最大] フィールドで設定します。また、整数 (1、2、7) と実数 (1.4230024、 63.72442) のどちらを使用して処理を実行するかも指定します。 次の表に、Evolver を呼び出す前にシートに設定されていた一連の変 数の初期値と、レシピ解法を使用した後に起こりうる 2 つのシナリ オの例を示します。 変数セットの初期値 レシピ解法で起こりう る変数値のセット A レシピ解法で起こりう る変数値のセット B 23.472 15.344 37.452 145 101 190 9 32.44 7.073 65,664 14,021 93,572 第 5 章: Evolver リファレンス ガイド 95 順序解法 「順序」解法は、「レシピ」の次に最もよく使われる種類の解法です。 順序とはアイテムのリストの順列のことを指し、この解法では一連の 特定値を並べ替えて、最適な順序を見つけ出します。選択された変数 の値を Evolver が生成する「レシピ」や「予算」解法とは異なり、 「順序」解法ではモデルに設定されている既存の値が使用されます。 ここでいう順序は、一連のタスクを実行する順序などのことです。例 えば、1 ～ 5 の番号が付いた 5 つのタスクを実行する順序を判断し たいと仮定します。「順序」解法は、1 ～ 5 の番号を例えば 3、5、 2、4、1 という順序に入れ替えます。順序解法ではユーザーが設定し たシートの変数値を Evolver がそのまま用いるので、最小 - 最大の 範囲は入力しません。 次の表に、Evolver を呼び出す前にシートに設定されていた一連の変 数の初期値と、順序解法を使用した後に起こりうる 2 つのシナリオ の例を示します。 96 変数セットの初期値 順序解法で起こりうる 変数値のセット A 順序解法で起こりうる 変数値のセット B 23.472 145 65,664 145 23.472 9 9 65,664 145 65,664 9 23.472 [モデルの定義] コマンド グルーピング解 法 「グルーピング」解法は、複数の変数をいくつかのグループに分ける 必要がある問題に使用します。Evolver が作成するグループの数は、 最適化の開始時に調整可能セルに設定されている、一意の値の数に等 しくなります。したがって、状況のモデルを作成する際に、モデル内 で各グループが少なくとも 1 度は使用されるようにする必要があり ます。 例えば、50 個のセルで取りうる値が 2、3.5、17 の 3 つに限られる とします。この 50 のセルを選択して「グルーピング」解法で値を調 整する場合、Evolver が 50 個すべてのセルを 2、3.5、17 のグルー プのいずれかに割り当てます。ここでは各グループに調整可能セルの うち少なくとも 1 つが割り当てられます。これは 50 個の変数をい くつかの箱に投げ入れ、それぞれの箱に少なくとも 1 つの変数が入 るようにするのと同じです。この解法の例には、1、0、-1 の各値を 取引システムに割り当て、買い、売り、ホールドの各ポジションを示 す場合なども当てはまります。「順序」解法と同様、Evolver が既存 の値を並べ替えるだけなので、最小 - 最大の範囲や整数オプション は定義しません。 注意: 「グルーピング」解法を使用する場合、すべてのセルに必ず値 を入力してください。値を入力しないと、0.0 という値が 1 つのグ ループであると解釈されます。 「グルーピング」解法は、一見すると「レシピ」解法の整数オプショ ンをオンにして範囲を 1 ～ 3 (またはその他のグループ数) に設定 した場合と似ています。ただし、レシピとグルーピングでは、検索の 処理方法が異なります。この 2 つの解法では、それぞれ異なる選択、 突然変異、交差のルーチンを用いています。グルーピングでは、ある グループからの一連の変数をほかのグループからの一連の変数とスワ ップできるので、レシピ解法の場合に比べてすべての変数の値が重視 されます。 次の表に、Evolver を呼び出す前にシートに設定されていた一連の変 数の初期値と、グルーピング解法を使用した後に起こりうる 2 つの シナリオの例を示します。 変数セットの初期値 グルーピング解法で起 こりうる変数値のセッ ト A グルーピング解法で起 こりうる変数値のセッ ト B 6 6 8 7 6 7 8 8 6 8 7 7 第 5 章: Evolver リファレンス ガイド 97 予算解法 「予算」解法は「レシピ」解法に似ていますが、変数のすべての値の 合計が特定の値になる必要がある点で異なります。この特定の値とは、 最適化の開始時に設定されていた変数値の合計です。 例えば、年度予算をいくつかの部署に分配する最適な方法を判断した いとします。「予算」解法では各部署の現在の値の合計を計算し、そ の値を予算の合計額とみなし、その最適な分配方法を探します。次の 表に、予算解法を使用した後に起こりうるシナリオの 2 つの例を示 します。 一連の 予算額の初期値 予算解法で起こり うる予算額のセット A 予算解法で起こ りうる予算額のセット B 200 93.1 223.5 3.5 30 0 10 100 -67 10 .4 67 さまざまな値が試されますが、その合計は常に 223.5 です。 98 [モデルの定義] コマンド プロジェクト解 法 「プロジェクト」解法は「順序」解法に似ていますが、特定のアイテ ム (タスク) をほかのタスクの前に配置する必要がある点で異なりま す。「プロジェクト」解法は、その直前のタスクに関する制限を常に 満たしながら、タスクの遂行順序を並べ替える必要のある、プロジェ クト管理などに使用します。 「プロジェクト」解法を使ってモデル化した問題は、タスク順序を含 む調整可能セルが横 1 行ではなく縦 1 列に並んでいる方がわかりや すく、作業もしやすくなります。これは、この解法では直前のタスク のセルが横並びではなく縦並びになっていると仮定して処理が行われ、 またユーザーにとっても調整可能セルが縦に並んでいる方がワークシ ートを確認しやすいためです。 調整可能セルの場所を指定したら、ダイアログの [直前のタスク] セ クションで、そのタスクに先行するタスクのセルの場所を指定します。 次の表は、どのタスクの前にどのタスクを行う必要があるかを示した ものです。プロジェクト解法はこの表を使って、先行タスクの制限が 満たされるようになるまで、シナリオの変数の順序を並べ替えます。 調整可能セルの各タスクにつき、直前のタスク範囲を示す行が 1 つ 必要になります。直前のタスク範囲の 1 列目以降に、そのタスクが 依存する各タスクの ID 番号を各列に指定します。 プロジェクト解法の先行条件の設定方法の例 先行タスクの範囲は n 行× m 列で指定します。ここで n はプロジ ェクトに含まれるタスク (調整可能セル) の数、m は 1 つのタスク に先行するタスクの最大数です。 第 5 章: Evolver リファレンス ガイド 99 次の表に、Evolver を呼び出す前にシートに設定されていた一連の変 数の初期値と、プロジェクト解法を使用した後に起こりうる 2 つの シナリオの例を示します。 スケジュール解 法 変数セットの初期値 プロジェクト解法で起 こりうる値のセット A プロジェクト解法で起 こりうる値のセット B 1 1 1 2 3 2 3 2 4 4 4 3 スケジュールは、タスクを時間に割り当てるという点でグルーピング に似ています。学校の授業時間がすべて同じであるように、各タスク の所要時間は一定しているものと仮定されます。ただし、グルーピン グと異なり、「スケジュール」解法の [調整可能セルのグループ設 定] ダイアログでは、使用するタイム ブロック (またはグループ) の数を直接指定できます。「スケジュール」解法を選択すると、ダイ アログ ボックスの下部にこの解法のオプションがいくつか表示され ます。 [最適化のパラメータ] セクションでは、制限セルの範囲を設定する こともできます。この範囲の行数は任意の長さにできますが、列数は 3 列でなければなりません。ここでは 8 種類の制限を適用できます 。 1) [とともに] (with) - 1 列目と 3 列目のタスクを同じ時間ブロ ックに割り当てる必要があります。 2) [ともにではなく] (not with) - 1 列目と 3 列目のタスクを同 じ時間ブロックに割り当てることができません。 3) [前] (before) - 1 列目のタスクを 3 列目のタスクの前に割り 当てる必要があります。 4) [において] (at) - 1 列目のタスクを 3 列目のタイム ブロック 内に割り当てる必要があります。 5) [後ではなく] (not after) - 1 列目のタスクを 3 列目のタスク と同じ時間か、その前に割り当てる必要があります。 100 [モデルの定義] コマンド 6) [前ではなく] (not before) - 1 列目のタスクを 3 列目のタス クと同じ時間か、その後に割り当てる必要があります。 7) [においてではなく] (not at) - 1 列目のタスクを 3 列目のタ イム ブロック内に割り当てることはできません。 8) [後] (after) - 1 列目のタスクを 3 列目のタスクの後に割り当 てる必要があります。 制限の入力には 1 ～ 8 の数値コードか、テキストの説明 (「後」、 「においてではなく」など) を使用できます。(注意: 制限の入力で はすべての言語の Evolver で、その言語および英語で入力された説 明の両方が認識されます。) スケジュール解法では、問題に指定した すべての制限が満たされます。制限を作成するには、ワークシートの 空いている場所に表を作成し、1 列目と 3 列目にタスクを指定して、 2 列目に制限の種類を指定します。1 ～ 8 の数値は、前のセクショ ンで説明した制限の種類を表します。制限範囲内のセルには、最適化 を開始する前に制限データを入力しておく必要があります。 タスク 制限 タスク 5 4 2 12 2 8 2 3 1 7 1 5 6 2 4 9 3 1 第 5 章: Evolver リファレンス ガイド 101 次の表に、Evolver を呼び出す前にシートに設定されていた一連の変 数の初期値と、スケジュール解法を使用した後に起こりうる 2 つの シナリオの例を示します。 変数セットの初期値 スケジュール解法で起 こりうる値のセット A スケジュール解法で起 こりうる値のセット B 1 1 1 2 1 3 3 3 1 1 1 2 2 2 2 3 3 2 注意: スケジュール解法を選択した場合、調整可能セルの初期値に関 係なく、1 からの整数 (1、2、3、…) が使用されます。 102 [モデルの定義] コマンド 交差と突然変異 率 果てしない数のシナリオが想定できる問題に対して最適な解を探す場 合、問題のどの部分にエネルギーを集中したらよいかは特に難しい課 題となります。解空間の新しい領域を検索するためにかける処理時間 と、個体群内のすでに良質であることがわかっている解の微調整にか ける処理時間はどのように判断したらよいでしょうか？ 遺伝的アルゴリズム (GA: Genetic Algorithm) が効果的である大き な理由として、この 2 者間のバランスを本質的に維持できることが 挙げられます。GA はその構成上、良質な解を「繁殖」させながら、 潜在遺伝子が最終的な解にとって重要なものとなる可能性を考慮した 上で「適応度の低い」個体も残すことで、多様性を維持できます。 交差と突然変異率の 2 つのパラメータは、検索の対象範囲に影響を 与えます。Evolver では、これらのパラメータを進化の過程の前、ま たはその最中にユーザーが変更することができます。したがって知識 が豊富なユーザーは、集中すべき領域を指定することにより、GA の 処理を助けることができます。通常は、交差と突然変異のデフォルト 設定 (.5 と .1) を変更する必要はありません。状況に合わせてアル ゴリズムを微調整したり、比較調査を行ったり、実験を行いたい場合 などには、次の概要を参考にしてください。 z [交差率] - 交差率は 0.01 ～ 1.0 の範囲で設定できます。この 数値は、将来のシナリオ (個体) にその前世代の親からの情報の 組み合わせが含まれる確率を示します。経験の豊かなユーザーは この率を変更して、複雑な問題を解決する場合の Evolver のパ フォーマンスを微調整することができます。 交差率が 0.5 の場合、子孫の個体の変数の約 50% が一方の親か ら継承され、残りがもう片方の親から継承されることを意味しま す。交差率が 0.9 の場合は、子孫の個体の値の約 90% が一方の 親から継承され、残りの 10% がもう片方の親から継承されます。 交差率が 1 の場合には交差が起こらず、親のクローンのみが評 価されます。 Evolver では、デフォルトの交差率が 0.5 に設定されています。 Evolver で問題の処理を開始した後は、Evolver ウオッチャーを 使って交差率を変更できます (この章の「Evolver ウオッチャ ー」セクションを参照してください)。 第 5 章: Evolver リファレンス ガイド 103 z [突然変異率] - 突然変異率は 0.0 ～ 1.0 の範囲で設定できま す。この数値は、将来のシナリオにランダムな値が含まれる確率 を示します。突然変異率が高いと、より多くの突然変異、つまり ランダムな「遺伝子」値が個体群に取り入れられることを意味し ます。突然変異は交差の後で起こります。したがって、突然変異 率を 1 (つまり 100% がランダムな値) に設定すると、交差の効 果がゼロになり、Evolver が完全にランダムなシナリオを生成す ることになります。 最適な解のすべてのデータが個体群のどこかに含まれている場合 は、交差演算子のみで解を見つけ出すことができるはずです。突 然変異は、生物界において強い力を持つことが証明されています が、遺伝的アルゴリズムに突然変異が必要である理由も、生物学 の場合と似ています。突然変異は、個体の集団内に多様性を維持 し、個体群があまりに固定化され環境の変化に適応できななるの を防ぐために不可欠な現象です。遺伝的アルゴリズムと同様、動 物の進化においても、突然変異が新しい機能の進化につながるこ とはよくあります。 通常の場合、デフォルトの突然変異率を変更する必要はありませ ん。ただし、複雑な問題を処理する場合に経験豊富なユーザーが この値を変更して Evolver のパフォーマンスを微調整すること は可能です。例えば、Evolver の個体群がほぼ均質であり、最後 の数百試行で新しい解が見つかっていない場合などは、突然変異 率を高く設定することができます。この設定を変更する場 合、.06 から .2 に変えるのが一般的です。Evolver で問題の処 理を開始した後は、Evolver ウオッチャーを使って突然変異率を 変更できます (この章の「Evolver ウオッチャー」セクションを 参照してください)。 [突然変異率] フィールドのドロップダウン リストで [自動] を 選択すると、突然変異率の自動調整機能が使用されます。突然変 異率の自動調整では、個体が非常に古くなった場合 (つまり何回 試行しても変わらなくなった場合) に、Evolver が突然変異率を 自動的に上げることができます。多くのモデルでは、特に最適な 突然変異率が判断できない場合に [自動] を選択すると、優れた 結果がより迅速に見つかることがあります。 タイム ブロック 数と制限セル これらのオプションについて詳しくは、この章の「解法」セクション にある、「スケジュール解法」の説明を参照してください。 直前のタスク これらのオプションについて詳しくは、この章の「解法」セクション にある、「プロジェクト解法」の説明を参照してください。 104 [モデルの定義] コマンド 演算子 Evolver では、「レシピ」解法を使用する際に遺伝演算子を選択する ことができます。[調整可能セルのグループ設定] ダイアログの [演 算子] タブをクリックすると、一連の調整可能セルの可能な値を生成 するときに使用する、特定の遺伝演算子 ([ヒューリスティック交差] や [境界突然変異] など) を選択できます。または、利用できるすべ ての演算子を Evolver で自動的に試行して、状況に最も適したもの を判断させることも可能です。 遺伝的アルゴリズムは遺伝演算子を使用して、個体群の現在のメンバ ーから新しいメンバーを生成します。Evolver が使用する遺伝演算子 には「突然変異」と「交差」の 2 種類があります。突然変異演算子 は、遺伝子 (変数) にランダムな変化が発生させるかどうかおよび、 その発生方法を決定します。交差演算子は、個体群のメンバーのペア の遺伝子をスワップして、親よりも優れた解となりうる「子孫」を生 成する方法を決定します。 Evolver には、次の特殊な遺伝演算子があります。 ♦ [算術交差] - 遺伝子を単に交換する代わりに 2 つの親を組み 合わせて、算術的な方法で新しい子孫を作成します。 ♦ [ヒューリスティック交差] - 親により生成された値を使用して、 子孫の作成方法を判断します。最も有望と思われる方向に検索を 続け、局所的な微調整を行うことができます。 ♦ [コーシー突然変異] - 大半の場合、変数をごくわずかに変更す るだけですが、大きな変化をもたらすことがあります。 第 5 章: Evolver リファレンス ガイド 105 ♦ [境界突然変異] - 単調な方法で結果に影響を与える、制限に違 反せずにその範囲の極限に近い値に設定できる変数を、迅速に最 適化するための演算子です。 ♦ [非一様突然変異] - 試行の計算回数を重ねるごとに、突然変異 の量をより少なくします。これにより、Evolver が解を「微調 整」することができます。 ♦ [線形] - 最適な解が、制限で定義された検索空間の境界にある 問題を処理するための演算子です。突然変異と交差を行うこの演 算子ペアは、線形の最適化問題を解決するのに向いています。 ♦ [ローカル検索] - 以前の解の周辺の解空間を検索する演算子で す。結果が改善される方向へ解空間を拡張し、悪化する方向の解 空間を縮小します。 最適化の問題の種類によっては、交差と突然変異の各演算子をさまざ まに組み合わせて、より良い結果を見つけ出すことも可能です。レシ ピ解法を使用する場合、[調整可能セルのグループ設定] ダイアログ の [演算子] タブで任意数の演算子を選択することができます。複数 の演算子を選択すると、Evolver がこれらの演算子の有効な組み合わ せをテストして、そのモデルに一番適したパフォーマンスの演算子を 判断します。実行後、[最適化サマリー] ワークシートに、選択され た各演算子のパフォーマンス順位が報告されます。その後、同じモデ ルを実行するときは、パフォーマンスが上位の演算子だけを選択する と、処理がより迅速になり、より良い最適化を行うことができます。 注意: 調整可能セルのグループを複数作成するときは、スプレッドシ ートの 1 つのセルが複数のグループに重複して含まれていないこと を確認してください。調整可能セルの各グループには、一意の調整可 能セルを含める必要があります。セルが重複していると、最初のグル ープの値が無視され、2 番目のグループの値で上書きされます。問題 を解決するために複数の解法が必要であると思われる場合には、変数 を複数のグループに振り分けることが必要になります。 106 [モデルの定義] コマンド 制限 Evolver では制限を入力できます。制限は、解が有効であるためには 満たさなければならない条件です。入力した制限は、[モデル] ダイ アログ ボックスの [制限] テーブルに表示されます。 追加 - 制限の追 加 [制限] テーブルの隣にある [追加] ボタンをクリックすると、制限 を入力するための [制限設定] ダイアログ ボックスが表示されます。 このダイアログ ボックスを使って、制限の説明、種類、定義、そし て評価時間を入力できます。 第 5 章: Evolver リファレンス ガイド 107 制限の種類 シンプルな制限 と数式による制 限 Evolver では次の 2 種類の制限を指定できます。 z [ハード] - ハード制限は、解を有効とみなすには満たさなけれ ばならない条件です。(例えば、ハード制限として C10<=A4 とい う条件を指定すると、解で生成された C10 の値がセル A4 の値 より大きい場合、その解は破棄されます。) z [ソフト] - ソフト制限は、できる限り満たすことが望ましい条 件ですが、適応度やターゲット セルの結果が大幅に改善される 場合には妥協することが可能なものです。(例えば、C10 の値が 100 を超えることは可能ですが、その場合にはターゲット セル の計算値が、指定したペナルティ関数に基づいて減算されます。 制限の入力には、「シンプル」と「数式」の 2 つの形式を使用でき ます。制限に入力できる情報の種類は、使用する形式によって異なり ます。 z シンプルな形式 - [シンプル] 形式では、<、<=、>、>=、また は = のシンプルな関係と、セルの値を比較する対象値を入力し ます。典型的なシンプルな制限の例として、次が挙げられます。 0 < A1 の値 < 10 この場合、[制限対象の範囲] ボックスに A1 を、[最小] ボック スに 0 を、[最大] ボックスに 10 を入力します。演算子はドロ ップダウン リストから選択します。シンプルな値の範囲を使っ た制限では、[最大] ボックスを指定せずに [最小] ボックスだ けを指定することもできます。入力する最小値と最大値は、シン プルな値の範囲の制限形式の数値である必要があります。 z 108 数式形式 - [数式] 形式の制限では、有効な任意の Excel 式 (例えば A19<(1.2*E7)+E8) を制限として入力できます。Evolver は、入力された数式の真偽を確認し、制限が満たされているかど うかを判断します。 [モデルの定義] コマンド ソフト制限 ソフト制限は、できる限り満たすことが望ましい条件ですが、適応度 やターゲット セルの結果が大幅に改善される場合には妥協すること が可能なものです。ソフト制限が満たされない場合、ターゲット セ ルの結果に、最適な値との差が大きくなるようなペナルティが課され ます。ソフト制限違反による値の変化量は、ソフト制限の指定時に入 力するペナルティ関数を使って計算されます。 ここではペナルティ関数について詳しく説明します。 z ペナルティ関数の入力。Evolver でソフト制限を最初に入力す るときに、デフォルトのペナルティ関数が表示されます。ただし、 ここに任意の有効な Excel 式を入力して、ソフト制限が満たさ れない場合に適用するペナルティを計算することができます。入 力したペナルティ関数には、「deviation」(偏差値) というキ ーワードを含める必要があります。これは、制限を越えている絶 対量を表します。Evolver は、特定の試行解の各シミュレーショ ンの終了時に、ソフト制限が満たされているか確認し、満たされ ていない場合は入力されたペナルティ関数に偏差値を代入してか ら、ターゲット セル統計に適用するペナルティの量を計算しま す。 ペナルティは、最適な値との差が広がるような方法で、ターゲッ ト セルに計算された統計に加算または減算されます。例えば、 [Evolver - モデル] ダイアログの [最適化ゴール] フィールド で [最大] を選択した場合、ペナルティはターゲット セルの統 計から差し引かれます。 第 5 章: Evolver リファレンス ガイド 109 z 入 力 し た ペ ナ ル テ ィ 関 数 の 効 果 の 確 認 。 Evolver に は 、 PENALTY.XLS という Excel ワークシートが付属しています。こ れを使って、さまざまなペナルティ関数が特定のソフト制限とタ ーゲット セルの結果に与える影響を評価できます。 PENALTY.XLS では、効果を分析するソフト制限を、モデルから選択す ることができます。その後、ペナルティ関数を変更して、制限が満た されない場合に特定の値が、ペナルティの課された特定のターゲット 値にどうマッピングされるかを確認できます。例えば A10<100 とい うソフト制限があるとすると、PENALTY.XLS を使用して、セル A10 の計算値が 105 のときにターゲット値がどうなるかを確認できます。 z 適用されたペナルティの確認。ソフト制限が満たされないため にターゲット セルにペナルティが適用された場合、そのペナル ティ量を Evolver ウオッチャーで確認することができます。ペ ナルティ値は、最適化の後にオプションで作成することのできる、 「最適化ログ」ワークシートにも表示されます。 注意: [停止] ダイアログの [調整可能セル値を更新する] オプショ ンを使ってワークシートに解を配置した場合、スプレッドシートに表 示されるターゲット セルの計算結果には、ソフト制限違反のために 適用されたペナルティが一切含まれません。ペナルティが適用された ターゲット セルの結果および、違反した各ソフト制限ごとに適用さ れたペナルティの量は、最適化ログのワークシートを確認してくださ い。 110 [モデルの定義] コマンド z ワークシートの数式を使ったソフト制限の指定。ペナルティ関 数は、ワークシートの数式に直接指定することができます。ソフ ト制限をワークシートで直接指定する場合、メインの Evolver ダイアログに同じ制限を入力しないでください。ワークシートで のペナルティ関数の指定について詳しくは、「第 8 章: Evolver のその他の機能」の「ソフト制限」セクションを参照してくださ い。 第 5 章: Evolver リファレンス ガイド 111 112 [最適化設定] コマンド [最適化設定] コマンド [最適化設定] コマンドの [一般] タブ 最適化の一般設定を定義 [最適化設定] ダイアログの [一般] タブには、個体群サイズ、表示 の更新、および乱数ジェネレータのシードの設定が含まれています。 [一般] タブの [最適化のパラメータ] オプションには次があります。 z [個体群サイズ] - 個体群サイズにより、メモリに一度に保管さ れる個体 (変数の完全なセット) の数を Evolver に指定します。 各種の問題に最適な個体群サイズについては現在でも研究が進め られていますが、一般に個体群には問題のサイズに応じて 30 ～ 100 個の個体を使用することをお勧めします (大きな問題にはよ り大きな個体群を使用します)。個体群が大きいと解を見つける ための所要時間が長くなりますが、遺伝子プールが多様になるた め、より大局的な解答が得られるという見方が一般的です。 z [乱数ジェネレータ シード] - [乱数ジェネレータ シード] オプ ションでは、Evolver で使用する乱数ジェネレータの初期シード を設定できます。同じシード値を使用した最適化では、モデルに 変更を加えない限り、同一のモデルに対して同一の解が見つかり ます。シード値は、1 ～ 2,147,483,647 の整数でなければなり ません。 第 5 章: Evolver リファレンス ガイド 113 [最適化設定] コマンドの [実行詳細] タブ 最適化の実行時の詳細設定を定義 [最適化設定] ダイアログの [実行詳細] タブには、Evolver の最適 化の実行時間を指定する設定が表示されます。これらの停止条件は、 Evolver が最適化の処理を停止するタイミングとその方法を指定しま す。[最適化の開始] コマンドをいったん選択すると、Evolver は選 択された停止条件が満たされるまで、より良い解を探してシミュレー ションを実行する処理を継続します。任意数の条件をオンにすること ができますが、手動で停止するまでの間 Evolver を実行し続ける場 合は、条件をまったく指定しないことも可能です。複数の条件を選択 した場合、そのうちいずれかの条件が満たされた時点で Evolver は 処理を停止します。ここで選択した条件は、Evolver ウオッチャーま たは [進行状況] ウィンドウにある [停止] ボタンを使って、いつで もオーバーライドすることができます。 114 [最適化設定] コマンド [最適化実行詳 細] のオプショ ン [実行詳細] タブの [最適化実行詳細] オプションには次があります。 z [試行] - このオプションを設定すると、特定数の試行解を生成 した後で Evolver が停止します。 [試行] の設定は、さまざまなモデリング手法を試すときに Evolver の効率を比較するのに特に便利です。問題をモデル化す る手法を変更したり、異なる解法を選択することによって、 Evolver の効率が向上する可能性があります。モデルで特定数の 試行を処理するよう指定すると、選択された変数の数の違いや、 コンピュータ ハードウェアの処理速度、また画面の再描画にか かる時間などとは関係なく、Evolver がどの程度の効率で解を収 束できるかがわかります。各実行の結果を比較するには、 Evolver の最適化サマリー ワークシートも役立ちます。最適化 サマリー ワークシートについて詳しくは、この章の「[Evolver ウオッチャー] の [停止オプション] タブ」セクションを参照し てください。 z [時間] - このオプションを設定すると、所定の時間数、分数、 または秒数が経過すると Evolver がシナリオの実行を停止しま す。任意の正の実数 (600 や 5.2 など) を入力できます。 z [進行] - このオプションを設定すると、ターゲット セルの改 善度が所定の量 (変量) より少なくなった時点で、Evolver がシ ナリオの実行を停止します。改善度を確認する頻度を、試行回数 として整数で指定できます。[最大変量] フィールドには、最大 の変化量を 1% などのパーセント値で入力できます。 例えばターゲット セルの平均値を最大化する必要があり、500 回の試行後に見つかった最適な解が 354.8 であるとします。[進 行] オプションが唯一の停止条件として選択されている場合、 Evolver が 600 回目の試行で一時停止し、最後の 100 の試行で 354.9 かそれ以上の解を見つけることができた場合にのみ、処理 を続行します。つまり、最後の 100 の試行による改善量が 0.1 を超えていないので、Evolver がそれ以上の改善はあまり期待で きないと判断し、処理を停止します。複雑な問題を処理する場合、 Evolver で改善の度合いが十分かどうか評価するまでの試行数を、 例えば 500 などに増やすことができます。 このオプションでは、改善度が低下しそれ以上の優れた解は 見つからないと思われる時点で、ユーザーが Evolver を停 止することができるので、停止条件として一番よく使われま す。Evolver ウオッチャーの [進行状況] タブに最適な結果 のグラフを表示している場合、この条件が満たされて Evolver が停止する前に、このグラフがしばらくの間横ばい 第 5 章: Evolver リファレンス ガイド 115 状態を続けます。改善度が横ばいになるまで実行を継続する [進行] オプションは、ユーザーがグラフに基づいて手動で 処理を停止する作業を自動化したものです。 z [数式が真] - この停止条件では、最適化の最中に、入力 (ま たは参照) された Excel の数式が真になった時点で処理を 停止します。 z [エラー時に停止] - この停止条件では、ターゲット セルの 計算結果がエラー値となった時点で処理を停止します。 注 意 : 停 止 条 件 を 1 つ も 選 択 せ ず に Evolver を 実 行 し 続 け 、 [Evolver ウオッチャー] ウィンドウの停止ボタンを使って手動で停 止することもできます。 116 [最適化設定] コマンド [最適化設定] コマンドの [表示] タブ 最適化の表示設定を定義 [最適化設定] ダイアログの [表示] タブには、Evolver の最適化の 処理中に表示されるものを指定する設定が含まれています。 [表示] タブには次のオプションがあります。 z [開始時に Excel を最小化] - 最適化の開始時に Excel を最小 化するよう指定します。 z [Excel の再計算を表示] - Excel を [新たなベスト試行ごと] または [試行ごと] に更新するよう指定します。 z [全試行のログを記録] - 新しい各試行の実行ログを記録するよ う、Evolver に指定します。このログは [Evolver ウオッチャ ー] ウィンドウで確認できます。 第 5 章: Evolver リファレンス ガイド 117 [最適化設定] コマンドの [マクロ] タブ 最適化の処理中に実行するマクロを定義 最適化の処理中や、各試行解の実行中に、さまざまなタイミングで VBA マクロを実行できます。これにより、最適化の処理中に呼び出さ れるカスタムの計算を設定することができます。 マクロは最適化の処理中に次のタイミングで実行できます。 z [最適化の開始時] - [実行] アイコンをクリックした後、最初 の試行解が生成される前に、マクロが実行されます。 z [各試行の再計算前] - 実行される各試行の再計算の前に、マク ロが実行されます。 z [各試行の再計算後] - 実行される各試行の再計算の後に、マク ロが実行されます。 z [出力の保存後] - 各試行を実行し、ターゲット セルの値を保 存した後で、マクロが実行されます。 z [最適化の終了時] - 最適化の処理が完了した時点でマクロが実 行されます。 この機能によって、マクロの使用が必要な計算を、最適化中に実施す ることができます。マクロによって実施される計算の例には、反復的 な「ループ」計算や、外部ソースの新規データを必要とする計算が挙 げられます。 [マクロ名] には、実行するマクロを指定します。 118 [最適化設定] コマンド [最適化の開始] コマンド 最適化を開始 [最適化の開始] コマンドを選択するか、[最適化の開始] ボタンをク リックすると、アクティブなモデルとワークブックの最適化が開始さ れます。Evolver の処理が開始されると、次の [Evolver 進行状況] ウィンドウが表示されます。 [進行状況] ウィンドウには、次の情報が表示されます。 z [試行] - すでに実行された試行の合計数です。[ 個が有効] は、このうちすべての制限が満たされた試行の数です。 z [実行時間] - 実行を開始してからの経過時間です。 z [オリジナル] - ターゲット セルの初期値です。 z [ベスト] - 最小化または最大化する必要のある、ターゲット セルの現在のベストの値です。 第 5 章: Evolver リファレンス ガイド 119 [進行状況] ウィンドウの Evolver ツールバーには、次のオプション があります。 120 z [Excel の更新オプションの表示] - Excel の表示の更新オプシ ョンを、[試行ごとに再計算]、[新たなベスト試行ごとに再計 算]、または [更新しない] のいずれかを選択します。ただし、 最適化が一時停止された場合など、これらの設定とは関係なく画 面が更新されることもあります。 z [Evolver ウオッチャーの表示] - [Evolver ウオッチャー] ウ ィンドウを表示します。 z [実行] - [実行] アイコンをクリックすると、[Evolver - モデ ル] ダイアログの現在の設定内容に基づいて Evolver が解の検 索を開始します。Evolver を一時停止した場合でも、[実行] ア イコンをクリックしてより良い解を見つけるために処理を再開す ることができます。 z [一時停止] - Evolver の処理を一時停止するには、[一時停止] ボタンをクリックします。すると Evolver の処理が一時的に停 止されます。一時停止中、Evolver ウオッチャーを表示してパラ メータの確認や変更、個体群全体の確認、ステータス レポート の表示、グラフのコピーなどを行うことができます。 z [停止] - 最適化を停止します。 [最適化の開始] コマンド [ユーティリティ] コマンド [アプリケーション設定] コマンド プログラムのデフォルト設定を指定する [アプリケーション設 定] ダイアログを表示 Evolver に は 、 実 行 す る た び に デ フ ォ ル ト 値 と し て 使 用 さ れ る Evolver 設定がいくつもあります。これらの設定には、停止のデフォ ルト、デフォルトの交差率と突然変異率、などが含まれます。 第 5 章: Evolver リファレンス ガイド 121 [制約ソルバー] コマンド 制約ソルバーを実行 制約ソルバーを使用して、Evolver によるモデル制限の処理能力を向 上させることができます。Evolver による最適化の実行では、調整可 能セルの初期値がすべてのハード制限を満たしていること、つまりオ リジナルの解が有効であることを前提としています。そうでない場合、 最初の有効な解が見つかるまで、アルゴリズムにより何度も繰り返し 試行が処理される可能性があります。ただし、複数の制限が含まれて いるモデルでは、すべての制限を満たしている調整可能セルの値を判 断するのが難しいこともあります。 Evolver モデルに複数のハード制限が含まれていて、すべての解が無 効となり最適化が失敗した場合、これを通知するメッセージが表示さ れて制約ソルバーを実行できるようになります。制約ソルバーは、最 適化を特殊なモードで実行し、すべてのハード制限を満たす解を見つ けようとします。通常の最適化の場合と同様に、ユーザーには最適化 の進行状況が表示されます。進行状況ウィンドウには、オリジナルの 解およびベストな解で満たされている制限の数が表示されます。 122 [ユーティリティ] コマンド 進行状況ウィンドウにあるボタンを使用して、Evolver ウオッチャー に切り替えることができます。制約ソルバー モードでも通常の最適 化モードと同様に [進行]、[サマリー]、[ログ]、[個体群]、[相違] という各タブに最適化処理の詳細が表示されます。ただし制約ソルバ ー モードでは、ウオッチャーに [制約ソルバー] という追加のタブ も表示されます。このタブには、ベスト、オリジナル、最終の解の各 ハード制限のステータス (達成または不達成) が表示されます。 制約ソルバー モードの最適化は、すべてのハード制限を満たす解が 見つかると自動的に停止されますが、進行ウィンドウまたは Evolver ウオッチャーにあるボタンをクリックして手動で停止することも可能 です。制約ソルバーの実行後、通常モードの最適化と同じように Evolver ウオッチャーの [停止オプション] タブでベスト、オリジナ ル、または最終の解を保持するように指定できます。 制約ソルバーは、これを実行する前に設定する必要はありません。制 約ソルバーはモデル内で指定されている設定を使用しますが、最適化 のゴールが変更されて、すべてのハード制限を満たす解を見つけよう とします。 第 5 章: Evolver リファレンス ガイド 123 124 [ユーティリティ] コマンド Evolver ウオッチャー [Evolver 進行状況] ウィンドウのツールバーにある虫眼鏡のアイコ ン を ク リ ッ ク す る と 、 Evolver ウ オ ッ チ ャ ー が 表 示 さ れ ま す 。 Evolver ウオッチャーは、Evolver のすべての操作を制御し、これら の操作に関する報告を行います。 Evolver ウオッチャーを使用してパラメータを変更したり、最適化の 進行状況を分析したりできます。また、Evolver ウオッチャーの下部 のステータス バーで、問題に関するリアルタイムの情報や、Evolver の進行状況を確認することもできます。 第 5 章: Evolver リファレンス ガイド 125 [Evolver ウオッチャー] の [進行] タブ ターゲット セル値の進行状況のグラフを表示 Evolver ウオッチャーの [進行] タブには、選択されたターゲット セルの結果が試行ごとにどう進行しているかが、グラフに表示されま す。 進行状況のグラフの X 軸は試行数を、Y 軸はターゲット セルの値を 示します。軸の限界をクリックして新しいスケール値にドラッグする と、進行状況グラフのスケールを変更できます。または、進行状況グ ラフを右クリックして [グラフのオプション] ダイアログを表示し、 グラフをカスタマイズすることもできます。 126 Evolver ウオッチャー [グラフのオプシ ョン] ダイアロ グ [グラフのオプション] ダイアログには、グラフのタイトル、凡例、 スケール、およびフォントを指定する設定が表示されます。 第 5 章: Evolver リファレンス ガイド 127 [Evolver ウオッチャー] の [サマリー] タブ 調整可能セルの値の詳細を表示 Evolver ウオッチャーの [サマリー] タブには、最適化でテストした 調整可能セルの値のサマリー テーブルおよび、モデルの各調整可能 セル グループの交差率と突然変異率を調整するためのツールが表示 されます。 [調整可能セル グループの設定] では、最適化の処理中に遺伝的アル ゴリズムの交差率と突然変異率を変更することができます。ここで行 った変更は、これらのパラメータの初期設定を上書きして直ちに有効 になり、[表示中のグループ] フィールドで選択した個体群 (または 調整可能セルのグループ) に反映されます 通常の場合、交差率にはデフォルト設定の 0.5 を使用するようお勧 めします。突然変異率は、最も適した解を見つける必要があり、処理 時間が長くなっても構わない場合には、多くのモデルでは 0.4 程度 にまで上げることができます。Evolver では交差の後に突然変異を実 行するので、突然変異率を最大値の 1 に設定すると、完全にランダ ムな推測が行われます。この場合、選択された 2 つの親を交差して 子孫の解を作成した後で、その解の遺伝子の 100% の突然変異が起こ り、すべてが乱数で置き換えられます (詳しくは、索引の「交差率、 機能」および「突然変異率、機能」の項を参照してください)。 128 Evolver ウオッチャー [Evolver ウオッチャー] の [ログ] タブ 最適化中に実行された各試行のログを表示 Evolver ウオッチャーの [ログ] タブには、最適化中に実行された各 試行のサマリー テーブルが表示されます。このログにはターゲット セル、各調整可能セル、および入力した制限の結果が含まれています。 ログを表示するには、[最適化設定] ダイアログの [表示] タブで [全試行のログを記録] オプションを選択する必要があります。 [表示] オプションで、[すべての試行] のログを表示するか、[進行 ステップ] のあった (つまり最適化結果が改善された) 試行のみを表 示するかを選択します。ログには次の情報が含まれています。 1) [経過時間] - 試行の経過時間。 2) [反復試行] - 実行された反復試行の数。 3) [結果] - ソフト制限のペナルティを適用した後の、最小化・最 大化する必要のあるターゲット セルの統計値。 4) [出力平均]、[出力標準偏差]、[出力最小]、[出力最大] - 計算 されたターゲット セルの確率分布の統計値。 5) 入力値の列 - 調整可能セルに使用した値。 6) 制限の列 - 制限が満たされたかどうかを示します。 第 5 章: Evolver リファレンス ガイド 129 [Evolver ウオッチャー] の [個体群] タブ 現在の個体群に含まれる各個体 (起こりうる各解) のすべての 変数を表示 個体群のテーブルには、現在の個体群に含まれる各個体 (起こりうる 各解) の全変数のリストが表示されます。これらの個体は、最悪なも のから最良のものへと並んでいます。このテーブルには個体群のすべ ての個体が含まれるので、ここに表示される個体の数は [Evolver 最適化設定] ダイアログの [個体群サイズ] の設定によって決まりま す (デフォルトの数は 50 です)。また、この表の 2 列目には各個体 のターゲット セルの結果値が表示されます。 130 Evolver ウオッチャー [Evolver ウオッチャー] の [相違] タブ 現在の個体群のすべての変数のカラー プロットを表示 [相違] タブのプロット図では、特定の時点でメモリに保管されてい る個体 (解) 群において特定セルの値にどの程度の差異が見られるか によって、調整可能セルの値に色が割り当てられます。(これは遺伝 的最適化の分野においては、遺伝子プールにどの程度の多様性が存在 するかを示します。)プロット図の縦の各列は 1 つの調整可能セルを 表し、列内の各行は、異なる個体 (解) におけるその調整可能セルの 値を表します。各行の色は、特定の調整可能セルの最小値から最大値 までの範囲を 16 等分し、その各区間にそれぞれ異なる色を割り当て ることによって決まります。例えば、2 番目の調整可能セルを表す縦 の列がすべて同じ色になっているのは、メモリ内のすべての解でこの セルの値が同じであることを示します。 第 5 章: Evolver リファレンス ガイド 131 [Evolver ウオッチャー] の [停止オプション] タブ 最適化の停止オプションを表示 [停止] ボタンをクリックすると、[Evolver ウオッチャー] ダイアロ グの [停止オプション] タブが表示されます。このタブには、ワーク シートを調整可能セルのベストな計算値で更新したり、元の値を復元 したり、最適化サマリー レポートを生成したりするためのオプショ ンが表示されます。 [OK] をクリックすると Evolver の解の個体群が破棄され、選択され た値がスプレッドシートに代入されます。個体群の値や、試行の実行 時間と数などを含む、Evolver セッションについての情報を保存する には、最適化サマリー レポートを作成するオプションを必ず選択し てください。 このダイアログは、ユーザーの指定した停止条件が満たされた場合 (例えば、指定の試行数に達したり、指定の分数が経過した場合) に も表示されます。停止の警告メッセージには、スプレッドシートの調 整可能セル値を更新するオプションとして、ベスト、オリジナル、最 後、の 3 つが表示されます。 z 132 [ベスト] - Evolver の結果を受け入れて、より良い解の検索を 終了します。このオプションを選択すると、Evolver の処理によ り見つかったベスト シナリオの値が、スプレッドシートの調整 可能セルに設定されます。 Evolver ウオッチャー z [オリジナル] - このオプションは、調整可能セルの値を Evolver を実行する前の値に戻して、より良い解の検索を終了し ます。 z [最後] - Evolver が、最適化処理で最後に計算した値をワーク シートに挿入します。最後の計算値のオプションは、モデルのデ バッグを行う際に特に便利です。 [生成するレポート] セクションのオプションを使って、実行の結果 をレポートしたり複数の実行結果を比較するのに役立つ、最適化サマ リー ワークシートを生成します。レポートのオプションには次があ ります。 z [最適化サマリー] - 最適化の実行日時、使用した最適化設定、 ターゲット セルの計算値、および各調整可能セルの値などが含 まれています。 このレポートは、最適化を繰り返し行った結果を比較する場合に便利 です。 第 5 章: Evolver リファレンス ガイド 133 134 z [全試行のログ] - 実行されたすべての試行の結果が記録されて います。 z [進行ステップのログ] - ターゲット セルの結果が改善された すべての試行の結果が記録されています。 Evolver ウオッチャー 第 6 章: 最適化 最適化の手法 ............................................. 137 山登り法アルゴリズムについて ........................... 139 Excel ソルバー ........................................... 143 Evolver とソルバーの違い ............................... 144 Evolver の適用ケース ................................... 145 問題の種類 ............................................... 147 線形の問題 ...................................... 非線形の問題 .................................... テーブルベースの問題 ............................ 順列組み合わせの問題 ............................ 第 6 章: 最適化 147 147 149 150 135 136 最適化の手法 最適化問題の例についてはすでにチュートリアルでいくつか説明しま した。最適化問題の中には、ほかの問題に比べて解決するのが難しい ものもあります。例えば 1,000 都市間の最短経路を見つけるといっ た困難な問題では、起こりうるすべての解を考慮することは不可能で す。このような方法は、最高速のコンピュータを使っても計算を完了 するのに何年もかかります。 こうした問題を解決するには、起こりうるすべての解のサブセットを 検索することが必要になります。解のサブセットを考慮することによ り、さらに良い解を見つけ出す方法を判断できます。これを行うには 「アルゴリズム」を使用します。アルゴリズムは、問題を解決するた めのアプローチを順を追って指定したものです。例えば、すべてのコ ンピュータ プログラムは、多くのアルゴリズムの組み合わせで構築 されています。 ここではまず、一般的な問題解決アルゴリズムで問題がどのように表 されるかを見てみましょう。大半の問題は、入力、何らかの関数、そ の結果の出力、という 3 つの基本要素に分割することができます。 探している答え 前提条件 最適化の対象 問題の構成要素 入力 関数 出力 Evolver/Excel の 構成要素 変数 モデル ゴール 例として、X と Y の 2 つの変数がある問題の場合を想定します。こ れらの変数を方程式に代入した結果が Z であるとします。Z の値が 最大になるような X と Y の値を見つけるにはどうしたらよいでしょ うか。ここで Z を、特定の X と Y の組み合わせの質についての 「評価」であると考えることができます。 この例の問題 第 6 章: 最適化 探している答え 前提条件 最適化の対象 X と Y 方程式 Z 137 X と Y の組み合わせとその結果である Z を 1 つのセット値として、 そのすべてをプロットすると、次のような 3 次元の面グラフになり ます。 起こりうるシナリオ、または解の「地形」 X 値と Y 値の各交点により Z (高さ) の値が生成されます。この 「地形」で高点は良い解を示し、低点は不適切な解を示します。すべ ての解を 1 つずつ検討することにより、この関数の最大値 (最も高 い位置) を見つけ出すには、いかに最高速のコンピュータで最先端の プログラムを用いた場合でも、多大な時間がかかります * 。ここで Excel には関数自体のみを提供し、関数のグラフは提供しないこと、 そして実際にはこの例のように 2 次元ではなく、200 次元で表され る問題が多いことに注意してください。そこで、実行する計算の数を 減らしても最適な答えを見つけられるような方法が必要となります。 * 上の図では関数がスムーズな地形として表されています。関数がシンプルでスムーズ な (微分可能な) 場合、微積分により最小値と最大値を見つけることは可能ですが、 実際にはほとんどの問題がこのようにスムーズな関数で表されることはありません。 138 最適化の手法 山登り法アルゴリズムについて ここでは山登り法というシンプルなアルゴリズムについて見てみます。 山登り法アルゴリズムは次のような仕組みになっています。 1) 地形のランダムな地点から処理を開始します (ランダムな推 測をします)。 2) 任意の方向にわずかな距離だけ進みます。 3) 新しい位置が前の位置よりも高い場合、その地点からステッ プ 2 を繰り返します。新しい位置が前の位置よりも低い場合 には、元の地点に戻ってもう一度最初から繰り返します。 このように山登り法は、1 度に 1 つの解、またはシナリオのみを試 行します。次のプロット図では、起こりうる 1 つの解 (X、Y、Z 値 のセット) を黒い点 (• ) で表しています。この点をランダムな開始 位置に配置して、山登り法でグラフの一番高い位置に到達するよう試 してみるとします。 上の図を見れば、この点をその右方向にある高地の部分に向かわせる のが望ましいことがわかります。ただし、これがわかるのは、地形全 体が把握できているからです。このアルゴリズムでは、現在地点のす ぐ周りの部分だけが見えています。つまり、個々の木は見えても、森 林全体を把握することができません。 第 6 章: 最適化 139 実世界の問題においては、この地形がスムーズではなく計算に何年も かかるため、現在のシナリオとそのすぐ周辺のシナリオだけを計算す ることになります。上図の点は、なだらかな丘が続く風景の中に、目 隠しをされて立っている男性だと考えることができます。山登り法ア ルゴリズムでは、この男性は各方向に 1 歩ずつ踏み出してみて、現 在の場所よりも高くなっていると思われる方向だけに進むことになり ます。すると、彼はより高いところへと登り続け、最終的に丘の頂上、 つまり周りの全方向が今の位置よりも低いと感じられる地点に到達し ます。これは理論的にはごく簡単です。しかし、もしもこの男性が別 の場所から出発した場合には、間違った丘を登ってしまうことになり ます (下の図を参照してください)。 関数がスムーズであっても、違う場所から 出発すると、山登り法は失敗します (右図)。 山登り法では一番近くの山頂、つまり「極大値」のみを見つけること ができます。ほとんどの現実的なモデルでは問題の解の地形が非常に 荒く、起伏が激しいため、山登り法では一番近くの山よりも高い山頂 を見つけることは不可能です。 山登り法には、現在位置の周りの地勢をどのようにして把握するかと いう、もう 1 つの問題があります。地形をスムーズな関数で表せる 場合は、どの方向にある坂の傾斜が一番大きいかを微分により求める ことができます。ところが実世界の問題では、地形が不連続で微分が 不可能であるため、周囲のシナリオの「適応度」(フィットネス) を 計算する必要が出てきます。 140 最適化の手法 例えば、銀行が 9:00 am ～ 5:00 pm 勤務の警備員を 1 名採用する 場合を想定してみましょう。この警備員には、30 分の休憩時間を 2 度与える必要があります。この問題のゴールは、生産性と疲労度の関 係についての通則と、顧客のアクティビティ レベルを考慮した上で、 最適な休憩時間のスケジュールを見つけることです。まず、休憩時間 のさまざまな組み合わせを見つけて、これらを評価することから始め ます。現在のスケジュールでは 11:00 am と 3:00 pm に休憩時間が 設けられているとして、その周りの時間帯の生産性を計算してみまし ょう。 方向 休憩時間 1 (x) 休憩時間 2 (x) スコア (z) 現在の解 11:00 am 3:00 pm = 46.5 西のシナリオ 10:45 am 3:00 pm = 44.67 東のシナリオ 11:15 am 3:00 pm = 40.08 北のシナリオ 11:00 am 3:15 pm = 49.227 南のシナリオ 11:00 am 2:45 pm = 43.97 ここで、調整可能セル (休憩時間) を 2 回ではなく 3 回設けるとな ると、8 つのシナリオを検討する必要が出てきます。実際、中規模の 問題では変数の数が 50 個ほどになることがよくあります。すると、 一人の警備員につき 2 の 50 乗、つまり 1,000 兆通りの生産性を計 算する必要があることになります。 山登り法に変更を加えて、大局的な最大値 (地形全体における最高山 頂) を見つける能力を向上させることができます。山登り法は単峰型 の (峰が 1 つの) 問題に向いていることから、一部の分析プログラ ムで好んで使用されます。しかし、複雑な問題や大規模な問題に対す る用途は非常に限られます。 第 6 章: 最適化 141 142 最適化の手法 Excel ソルバー Excel には「ソルバー」という最適化ユーティリティが付属していま す。ソルバーの目的は最適な解を見るけることであり、Evolver と似 ています。ソルバーでは、線形タイプの問題とシンプルな非線形タイ プの問題の 2 種類を解決することができます。線形の問題の解決に は、線形プログラミング ルーチンを使用します。この典型的な数学 的手法は、シンプレックス手法とも呼ばれ、小規模で純粋に線形の問 題に対して常に完璧な答えを見つけ出すことができます。 大半のソルバーと同様、Microsoft ソルバーでは山登り法のルーチン (GRG2 ルーチン) を使用して非線形の問題を解決します。山登り法の ルーチンは、現在の変数値から開始して、モデルの出力がこれ以上改 善されなくなるまで、値を調整し続けます。したがって、複数の解が 考えられる問題をソルバーでうまく解決するのは不可能です。これは、 ソルバーが「局所的」な解に辿り着くことはできても、「大局的」な 解にジャンプすることができないためです (下図を参照)。 起こりうる解の地形 さらにソルバーでは、モデルの表す関数が連続的である必要がありま す。これは、入力値の調整に応じて出力がスムーズに変化することを 意味します。例えばモデルでルックアップ テーブルを使用する場合 や、別のプログラムからノイズの多いリアルタイム データを受け取 る場合、ランダムな要素が含まれる場合、または if-then 規則を使 用する場合などには、モデルが非連続型になります。ソルバーでは、 このような問題を解決することができません。 また、ソルバーでは問題に使用できる変数および制限の数が 200 に 制限されるため、これを超えた場合にはより強力な解決手法が必要と なります。 第 6 章: 最適化 143 Evolver とソルバーの違い Excel ソルバーと Evolver にはそれぞれ利点と欠点があります。一 般に規模の小さいシンプルな問題の場合はソルバーの方が短時間で処 理できますが、それ以外のさまざまな問題の解決には Evolver が必 要となります。また、実世界に見られるような複雑で大規模な問題の 処理では Evolver の方がずっと優れた解を見つけることができます。 Evolver は、ソルバーでは処理できないタイプの多くの問題を解決す ることができます。Excel でモデル化できる数値的な問題であれば、 ほとんどの場合は Evolver で最適化を行うことができます。 Evolver は線形、非線形、テーブルベース、または確率的 (ランダ ム) な数値問題に対して最適な解を見つけることができます。 Evolver ではこれらの性質のあらゆる組み合わせで構成される問題を 解決することが可能です。既存値の順列の生成、値の並べ替え、さま ざまな方法による値のグループ化などにより、最適な解を求めること ができます。モデル内の変数を調整することでその出力に影響を与え るようなスプレッドシート モデルさえあれば、Evolver を使ってイ ンテリジェントな方法で変数値の検索を自動化して無数のシナリオを 計算し、ベストな解を見つけ出すことが可能です。 Evolver の遺伝的アルゴリズムによる処理は、ソルバーよりも簡単に 一時停止することができます。Evolver の処理はいつでも一時停止し て、その時点でのベストな解を確認することができます。その後、問 題自体に変更を加えてから処理を継続することも可能です。例えば、 機械にタスクを割り当てる最適な方法を見つけるという作業スケジュ ールの問題を処理するとします。その場合、ある機械が使用可能にな った時点で遺伝的アルゴリズム処理を停止して、その機械に最も適し たタスクを見つけて割り当てることができます。するとこのタスクを 問題から除外できるので、残りの作業タスクのみに関して最適化を続 行することができます。 Evolver では遺伝的アルゴリズムを使ってあらゆるタイプの問題を処 理できますが、その一方で従来の数学的および統計的なソルバーなど を使うより長い処理時間がかかります。問題の種類によっては、効果 的な最適化ルーチンがすでに確立されている場合もあります。こうし た問題では Evolver の汎用アルゴリズムを使用する代わりに、カス タムの手法を用いた方がより迅速に解を得ることができます。 144 Excel ソルバー Evolver の適用ケース Evolver は一般に次のような場合に使用します。 1) 従来のアルゴリズムでは大局的な優れた解が得られない場合。 2) 既存のアルゴリズムで処理するには問題の規模が大きすぎたり、 変数の数が多すぎる場合。 3) ほかの方法で解決するには問題が複雑すぎる場合。 4) モデルに乱数、ルックアップ テーブル、if-then 条件文、また はその他の非連続型の関数が含まれているために従来のソルバー を使用できない場合。 5) 解の結果が推測不可能なため、従来のソルバーで検索を開始する ために必要な初期の予測値を設定できない場合。 6) 問題中で一部のハード制限 (例えば「X が Y と等しくなければ ならない」という制限) をソフト制限として扱うことでより正確 な結果を得られるようにし (例えば「X が Y と等しくなる必要 がある。そうでない場合は Z が失われる」という制限)、一部の 制限に違反していてもより優れた可能な解を、より広範囲に探索 したい場合。 7) 長い時間をかけて完璧な解を得るよりも、妥当な解を短時間で見 つけたい場合。 8) ベストの解に近い、複数の解を求める必要がある場合。 9) 独自のカスタム アプリケーションにシンプルで堅牢な検索アル ゴリズムを組み込みたい場合 (詳しくは Evolver デベロッパー キットを参照してください)。 注意: 時間的な余裕がある場合、ほかの手法に Evolver を追加して その精度を確認することができます。Evolver の処理はほかの手法よ りも時間がかかりますが、より優れた解が見つかるので処理時間をか けるだけの価値はあります。 Evolver では最適化する問題の詳細を指定する必要がないので、線形 プログラミング手法や最適化理論、数学、統計学などの知識を持たな いユーザーでも問題を解決することができます。Evolver の使用に必 要な操作は、変数 (調整可能な値を含むセル) とゴール (出力を含む セル) の設定および、最適な解を検索する際に Evolver で使用でき る値を指定することだけです。 第 6 章: 最適化 145 146 問題の種類 問題の種類 一般に最適化の対象となる問題にはいくつか種類があります。問題の 種類について理解しておくと、独自のモデルに Evolver を適用する のも容易になります。 線形の問題 線形の問題では、すべての出力が入力の単純な線形関数として、例え ば y=mx+b のように表されます。加算や減算などのシンプルな数式と TREND() や FORCAST() などの Excel 関数のみを使用する問題は、変 数間の純粋な線関係によって表されています。 線形の問題は、コンピュータの進歩と George Dantzig が編み出した シンプレックス手法によって比較的簡単に解決することができます。 シンプルな線形の問題は、線形プログラミング ユーティリティを使 うと最も迅速かつ正確に解決できます。Excel に付属のソルバー ユ ーティリティは、線形モデルを前提とするオプションをオンにすると、 線形プログラミング ツールを使用するようになります*。すると、ソ ルバーは線形プログラミング ルーチンを使って完璧な解を見つけ出 します。純粋な線形関数で問題を表すことができる場合は、線形プロ グラミングを使用するのが一番良い方法です。ただし残念なことに、 実世界の問題のほとんどは線形関数では表せません。 非線形の問題 5,000 個の小型装置を製造して出荷するコストが 5,000 ドルである 場合、1 台の装置の製造と出荷コストが 1 ドルということは、まず ありえないはずです。たとえ 1 台の装置であっても、製造工場の燃 料費、各部署で必要な事務処理、素材の一括購入、運送トラックのガ ソリン代、そしてドライバーの日給などが、装置の数や積荷の量に比 例するとは限りません。実世界において、変数と単純な線関係で処理 できる問題はほとんどありません。線形の問題には、乗算、除算、指 数、また SQRT() や GROWTH() といった Excel 関数が使われます。 変数間の関係が不均衡である場合、その問題は常に非線形になります。 * Microsoft のソルバー ユーティリティについて詳しくは、Excel のユーザー ガイド を参照してください。 第 6 章: 最適化 147 非線形問題の典型的な例として、化学プラントの製造過程管理が挙げ られます例えば、いくつかの化学反応物を混合して化学薬品を製造す る場合を想定してみましょう。この化学反応率は、利用できる反応物 の量に応じて非線形の関数に従い変化する可能性があります。触媒が 飽和状態に達すると、それ以上の過剰な反応物は邪魔になります。次 の図は、この関係を示しています。 反応率を最大化する反応物の最小量を見つけるには、グラフの任意の 場所から開始して、山登り法で曲線を辿り頂上に到達すればよいこと になります。このような解決手法は、山登り法と呼ばれます。 山登り法で最適な解を見つけるには、a) 関数がスムーズであること、 b) 変数の初期値が一番高い山の側面にあること、の 2 つの条件が必 要となります。このどちらかの条件が満たされない場合には、全体の 解ではなく局所的な解を見つけた時点で山登り法の処理は完了してし まいます。 実世界によく見られる非線形の問題では、複雑な地形の上に複数の解 が存在しています。問題に多くの変数が含まれていたり、使用する数 式にノイズが多かったり、曲線式であると、たとえ多くの異なる開始 地点を試した場合であっても、山登り法で最適な解を見つけるのは困 難を極めます。大半のケースでは、局所的な最適でない解が見つかる ことになります (下図を参照)。 山登り法では大局的な最大値でなく極大値 が見つかります。 148 ノイズの多いデータ: 何度試行しても山 登り法は効果がありません。 問題の種類 Evolver は山登り法を使用せず、遺伝的アルゴリズムと呼ばれる、確 率的な方向付けされた検索手法を使用します。これにより Evolver は解空間を自由に移動しながら、極大値に惑わされることなく、入力 値のさまざまな組み合わせを試すことができます。また、Evolver で は、解の地形全体に関する貴重な情報を得るために優れたシナリオ同 士が互いにやり取りすることができ、その情報を元に、どのようなシ ナリオが成功するかをより正確に推測できるようにします。複雑な問 題や非線形傾向の強い問題を処理する場合には Evolver が適してい ます。 Evolver では多くの可能なシナリオを生成し、 そのフィードバックに基づいて検索方法を調整します。 テーブルベース の問題 多くの問題では、ルックアップ テーブルとデータベースの使用が必 要となります。例えば、さまざまな素材の購入量を決定するには、各 数量ごとの購入価格を調べる必要があります。 テーブルとデータベースを使用すると、問題が非連続型になり、スム ーズでなくなります。そのため、ソルバーなどの山登り法ルーチンで 最適な解を見つけるのは困難です。Evolver では、評価対象の関数が 連続型である必要はなく、テーブルベースの問題でも良い解を見つけ ることができます。これは大きなテーブルや、相互に関連する複数の テーブルを使用する問題にも該当します。 データベースや Excel のテーブル データから値を取得する必要があ り、テーブル アイテムのインデックスが変数または変数の関数であ る場合には、Evolver を使用する必要があります。テーブルで 1 つ の定数アイテムのみを検索する場合 (テーブルから取得される値が、 入力変数の値とは関係ない場合) は、定数値を使用しているだけなの で、通常はソルバーでうまく解決できます。 第 6 章: 最適化 149 順列組み合わせ の問題 これまで見てきた数値的な問題とはまったく異なる種類の問題もあり ます。既存の入力変数やそのサブセットの順序の並べ替えが出力結果 となる問題のことを、順列組み合わせ問題と呼びます。これらの問題 の解決にかかる時間は指数関数的に増大するため、解決するのが非常 に難しいことがあります。例えば、4 つの変数が関与する問題の解決 にかかる時間が 4 x 3 x 2 x 1 であるとすると、変数の数が 8 に増 えた場合には、解決にかかる時間が 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1、 つまり 1,680 倍に増えることになります。変数の数が 2 倍になった だけで、検討が必要な起こりうる解の数は 1,680 倍に膨らみます。 例えば、野球チームの打順は順列組み合わせ問題です。ここでは 9 名の選手のうち 1 名を第 1 打者として選ぶ必要があります。その後、 第 2 打者として残りの 8 名から 1 名を選び、第 3 打者として 7 名から 1 名を選ぶ、という方法で選択していきます。したがって、9 名の打順は 9x8x7x6x5x4x3x2x1 (9 の階乗) 通りあることになります。 つまり、可能な打順は 362,880 通りあります。ここで、選手の数が 倍 に 増 え た 場 合 、 打 順 の 組 み 合 わ せ は 18 の 階 乗 、 つ ま り 6,402,373,705,000,000 通り考えられることになります。 Evolver の遺伝的アルゴリズムでは、起こりうる順列をインテリジェ ントに検索します。これは、すべての可能な解を検索するよりも実用 的であり、純粋にランダムな順列組み合わせを使うよりもずっと効率 的です。この手法では、優れたシナリオからの部分的な打順を維持し、 さらに優れたシナリオを作成するために活用することができます。 150 問題の種類 第 7 章: 遺伝的アルゴリズム はじめに ................................................. 153 歴史的背景 ............................................... 153 生物の例 ................................................. 157 コンピュータの例 ......................................... 159 第 7 章: 遺伝的アルゴリズム 151 152 はじめに はじめに Evolver は遺伝的アルゴリズムを使用して、シミュレーション モデ ルの最適な解を探します。この章では、遺伝的アルゴリズムについて の基礎的な情報および、シミュレーション モデルの最適化における その役割について解説します。 歴史的背景 遺伝的アルゴリズムは、1970 年代初頭にミシガン大学のジョン ホラ ンドにより開発されました。ホランドは、最高速のスーパーコンピュ ータを使っても不可能なタスクを、生物体系が難なくこなす点に注目 しました。例えば動物は、周囲にある物体を正確に認識し、音を理解 して解釈し、環境の変化に瞬時にして対応することができます。 科学者は何十年も前からこのような能力をいずれ機械でも実現できる ようになると提唱してきましたが、今日ではこれがいかに困難なタス クであるかが明らかになってきています。科学者の大半は、こうした 能力のあるすべての複雑な生物体系は、進化を経てその能力を取得し たという説に同意しています。 進化論 進化論によれば、以下のように比較的単純なルールに従い自己繁殖を する構成要素を通じて、進化により驚くべき能力を備えた体系が生ま れたとされています。 1) 進化は染色体レベルで起こる。個体そのものは進化せず、遺伝子 を伝播するための容器に過ぎません。遺伝子の各組み合わせごと に動的に変化するのは、染色体です。 2) 自然は、より「適応度の高い」個体を生み出す染色体をより多く 複製する傾向を持つ。個体が長い間存続し、健康であれば、その 遺伝子が繁殖により次世代の個体に受け継がれる可能性も大きく なります。この原理のことを「適者生存」の法則と呼びます。こ こで言う「適者」とはあくまで相対的な意味であり、個体が現在 の集団の中で「成功」するためには、その集団のほかの個体より も適応度が高ければよいわけです。 3) 集団の多様性は維持しなければならない。自然界では一見してラ ンダムな突然変異が頻繁に発生し、個体の多様性が維持されるよ うになっています。こうした遺伝子の突然変異は、その種の存続 に役立つ、または場合によっては不可欠な、特性につながること が多くあります。起こりうる組み合わせの範囲が広まれば、その 第 7 章: 遺伝的アルゴリズム 153 母集団の全個体を破壊しうる弱点 (ウイルスなど) や、同系交配 から起こるその他の問題の発生率を低くすることができます。 進化について上記の基本的な構成要素に分けて考えると、これらの手 法をコンピュータの分野に応用しやすくなり、より柔軟で自然な動作 をする機械の誕生へと近づくことができます。 ホランドは、こうした進化の特性を、染色体を表す単純な数値の文字 列に適用しました。まずは問題を、染色体を表すバイナリ文字列 (1 と 0 の行) にエンコードしてから、コンピュータでこれらの「ビッ ト」文字列を多く生成して、その母集団 (または個体群) を作り上げ ます。そして各ビット文字列を評価するための適応度関数をプログラ ミングで記述し、そのうち「適応度が高い」と判断された全文字列が、 「交差」ルーチンを使ってほかの文字列とデータを交換し、ビット文 字列の「子孫」を生成します。さらにホランドは、このデジタル染色 体に「突然変異」演算子を適用し、生成された「子孫」の染色体にラ ンダム性を導入して集団の多様性が保たれるようにしました。この適 応度関数は、生物界にたとえれば死の役割を果たすもので、どの文字 列に交配を続けるだけの価値があり、またどの文字列をプログラムか ら排除すべきかを判断します。 このプログラムは特定数の「染色体」をメモリに保持し、文字列の 「個体群」全体が、適応度関数の解が最大になるまで進化を続けます。 そしてその結果をデコードして元の値に戻すことで、解を求めます。 ジョン ホランドは今でもこの分野の先駆者として活躍を続けており、 現在では彼のほかにも数多くの科学者が従来の線形型のプログラム的、 数学的、統計的な手法に代わる、遺伝的アルゴリズムの研究に力を注 いでいます。 ホランドが開発した初代の遺伝的アルゴリズムはごくシンプルであり ながら非常に堅牢で、広範に及ぶ問題の最適な解を見つけることがで きました。非常に大規模で複雑な実世界の問題を解決するカスタム プログラムの多くは、このオリジナルの遺伝的アルゴリズムにごく若 干の変更を加えただけのバージョンを今でも用いています。 154 歴史的背景 遺伝的アルゴリ ズムの現在 一般のデスクトップ コンピュータに本格的な計算能力が備わり、 Microsoft Windows や Excel といった標準ソフトによる複雑なモデ ルの管理が行いやすくなると、各学界の関心を呼ぶようになりました。 ビット文字列表現の代わりに実数を使用することで、染色体のエンコ ードとデコードという困難なタスクが不要になりました。 遺伝的アルゴリズムの人気は今でも急増しており、この分野の関連セ ミナー、書籍、雑誌、コンサルタントはあらゆるところで次々と出現 しています。International Conference of Genetic Algorithms (遺 伝的アルゴリズム国際会議) では、すでに実用的な用途に焦点を当て ており、人工知能技術のほかの分野には見られない成熟度を示してい ます。証券ブローカーから発電所、電話会社、チェーン レストラン、 自動車メーカー、そしてテレビ局まで、多くの Fortune 500 企業が 日常業務に関する問題を解決するために遺伝的アルゴリズムを利用し ています。実際のことろ、誰もが今までに何らかの形で遺伝的アルゴ リズムを使ったことがあると言っても過言ではありません。 第 7 章: 遺伝的アルゴリズム 155 156 生物の例 生物の例 では、生物界における進化の簡単な例を見てみましょう。ここで言う 「進化」とは、個体群における遺伝子の分布または頻度の変化のこと を指します。一般には進化の結果として、個体群がその環境の変化に 随時適応する能力が備わることになります。 この例では、ハツカネズミの個体群について見てみます。これらのハ ツカネズミにはサイズが小と大の 2 通りあり、色も淡色と濃色の 2 通りあります。この個体群は、次の 8 匹のハツカネズミで構成され ています。 ある日、数匹の猫がどこからかやって来て、このネズミ達を餌にし始 めました。猫にとって、濃色のネズミと小さいネズミは、ほかのタイ プのネズミに比べて見つけるのが困難です。したがって、このネズミ たちが繁殖する前に猫に食べられてしまう確率は、ネズミのタイプに よって異なります。その結果、次世代のネズミの特性が影響を受けま す。ネズミは生殖後間もなく死亡すると仮定した場合、次世代のネズ ミの構成は次のようになります。 大きいネズミ、淡色のネズミ、そして大きくて淡色のネズミは特に、 生殖に至るまで生存するのが難しいことがわかります。さらにその次 の世代は、次のような構成になります。 この世代の個体群のほとんどが、この環境においてほかのタイプのネ ズミよりも生存に適している、小さい濃色のネズミで構成されていま す。同様に、捕獲できるネズミの数が減り空腹感を覚えた猫たちは、 第 7 章: 遺伝的アルゴリズム 157 いずれ草食を好むようになり、草食嗜好の遺伝子を次世代の猫に受け 渡す可能性があります。これが、「適者生存」の法則と呼ばれる原理 です。より正確に言えば、この生存とは「生殖までの生存」を指して います。進化論の観点から見た場合、個体群内で一番健康な独身男性 であること自体には価値がありません。これは、自分の遺伝子により 後の世代に影響を与えるには、生殖を行う必要があるからです。 158 生物の例 コンピュータの例 ここでは X と Y の 2 つの変数があり、結果として Z を生成する問 題について考えてみます。X と Y の可能なすべての値に対して結果 の Z を計算し、プロット図にすると、解の「地形」が現れます (詳 しくは、「第 6 章: 最適化」を参照してください)。ここでは Z が 最大になる解を探しているので、各山頂は「良い」解であり、谷は 「悪い」解となります。 遺伝的アルゴリズムを使って関数を最大化する場合、1 箇所から開始 するのではなく、いくつかの可能な解、つまりシナリオ (グラフ上の 黒い点) を無作為に作成することから始めます。その後、各シナリオ の関数の出力を計算し、各シナリオを 1 つの点としてプロットしま す。次に、すべてのシナリオをその高度によって評価し、昇順に並べ ます。上位半分のシナリオを維持し、残りは破棄します。 まず、起こりうる解の「個体群」全体を作成 します。このうち一部はほかのシナリオより 高度が高くなります。 第 7 章: 遺伝的アルゴリズム 次に、すべての解を評価し て、優れた結果を生む解だ けを維持します。 159 残った 3 つのシナリオをそれぞれ複製し、シナリオの数を 6 つに増 やします。この 6 つのシナリオは、それぞれ 2 つの調整可能値 (X 座標と Y 座標) で構成されています。各シナリオの値を、ほかのシ ナリオの値と無作為に入れ換えます。つまり、各シナリオが 2 つの 調整可能値のうち最初の値をその親の値と交換することになります。 たとえば、次のような使い方があります。 交換前 交換後 シナリオ 1 3.4, 5.0 2.6, 5.0 シナリオ 2 2.6, 3.2 3.4, 3.2 この操作のことを「交差」と呼びます。6 つのシナリオを無作為に交 差した結果、例えば次のような新しい一連のシナリオが得られます。 上記の例では、オリジナルの 3 つのシナリオ a、b、c が、それぞれ の複製である A、B、C と交差され、aB、bC、bA というペアが生まれ ると仮定しました。その後、これらのペアの最初の調整可能セルを交 換しました。これは、上の図では点のペア間で X と Y の座標値を交 換する操作に相当します。これでシナリオの個体群が死と生のサイク ルを繰り返し、1 世代を経たことになります。 160 コンピュータの例 新しいシナリオのうち、一部の出力 (高度) は最初の世代よりも低下 しています。しかし、このうち 1 つのシナリオは前世代よりも進歩 し、一番高い山頂近くに達しています。 この個体群の進化をもう 1 世代だけ続けると、例えば次のような結果となる可能性があります。 この一番新しい世代ではシナリオ群のパフォーマンスが平均して高く なっていることがわかります。この例では、これ以上の改善の余地は あまりありません。各個体に遺伝子が 2 つしかなく、個体の数も 6 つだけであり、新しい遺伝子が作成される可能性もないからです。こ れは、つまり遺伝子プールが限られていることを意味します。遺伝子 プールは、その個体群に含まれるすべての個体の全遺伝子を合計した ものです。 生物界の進化に組み込まれたより多くの優れた特性を複製することに より、遺伝的アルゴリズムを強化することができます。これには例え ば、各個体の遺伝子数を増やす、個体群に含まれる個体の数を増やす、 ランダムな突然変異を発生させる、などの方法があります。また、よ り自然な形で生存し繁殖するシナリオを選択することもできます。こ うしたシナリオは、単にパフォーマンスが最高の個体を選んで交差す る代わりに、優れたパフォーマンスをわずかに重視するランダムな要 素を含んでいます (いかに大きく力強いライオンであっても、稲妻に 打たれる可能性があるということです)。 これらすべての手法では、遺伝子の調整を刺激して遺伝子プールの多 様性を維持し、さまざまな組み合わせで役立つ可能性のある、いろい ろなタイプの遺伝子を残しておくことができます。Evolver には、こ うした手法がすべて自動的に組み込まれています。 第 7 章: 遺伝的アルゴリズム 161 162 コンピュータの例 第 8 章: Evolver のその他の機能 制限の追加 ............................................... 165 範囲制限 ............................................... カスタムのハード制限 ................................... ソフト制限 ............................................. ペナルティ関数 .................................. ペナルティ関数の入力 ............................ 入力したペナルティ関数の効果の確認 ............... 適用されたペナルティの確認....................... ワークシートへのソフト制限の入力................. ペナルティ関数の例 .............................. ペナルティ関数の使用 ............................ ゴールが複数ある問題 ................................... 166 167 168 169 169 170 170 171 172 173 174 処理速度の改善 ........................................... 175 Evolver の最適化の実装 ................................... 176 選択 ............................................ 交差 ............................................ 突然変異 ........................................ 置換 ............................................ 制限 ............................................ 第 8 章: Evolver のその他の機能 176 177 178 178 178 163 164 制限の追加 実世界の問題には、最適な解を探す際に満たさなければならない条件 がいくつも存在します。例えば、コストを最小限に抑えた変圧器のデ ザインを見つけ出すチュートリアルの問題では、変圧器からの放熱量 が 0.16 ワット/cm2 以下でなければならないという条件が課されて います。 モデルの条件をすべて満たすシナリオのことを「有効」な解と呼びま す。モデルに対して有効な解、特に最適かつ有効な解を見つけるのが 困難な場合もあります。これは、例えば問題がとても複雑で有効な解 がごく少数しかなかったり、問題に規則が多すぎる (制限が多すぎた り、一部の条件がほかの条件と競合する場合など)、といった理由か ら、有効な解が存在しないことが原因です。 制限には、調整可能セルに適用される範囲制限 (最小 - 最大の範囲)、 常に満たす必要のあるハード制限、できる限り満たすことが望ましい が、適応度が大幅に改善される場合には妥協が可能なソフト制限、の 3 つの基本タイプがあります。 第 8 章: Evolver のその他の機能 165 範囲制限 最も単純なハード制限は、変数自体に課されるものです。各変数に特 定の範囲を設定すると、Evolver が試行する可能な解の合計数が減り、 検索の処理時間を短縮することができます。[モデル] ウィンドウの [調整可能セルの範囲] セクションにある [最小] フィールドと [最 大] フィールドに値を入力し、各変数で許容される値の範囲を指定し ます。 Evolver が、指定のセルで 0 ～ 5,000 の値のみを試します。 変数に適用されるハード制限の 2 つ目のタイプは、Evolver の各解 法 (レシピ、順序、グルーピングなど) に組み込まれています。例え ば、予算解法を使って変数を調整する場合、Evolver には合計が同じ 値になる値のセットのみを試行するよう、ハード制限が課されます。 範囲制限と同様、このハード制限によっても、検索対象となる可能な シナリオの数を減らすことができます。 [モデル] ダイアログ ボックスの [整数] オプションもハード制限の うちの 1 つで、変数値を調整するときに、実数 (1.34 や 2.034 な ど) ではなく整数 (1、2、3 など) のみを使用するよう Evolver に 指定します。 166 制限の追加 カスタムのハード制限 Evolver の変数制限に含まれていない制限は、[制限設定] ダイアロ グ ボックスを使って入力することができます。 注意: 自然界の進化と同様、遺伝的アルゴリズムの問題解決能力は、 可能性のある多くの解の組み合わせを自由に試し、自然と最適な解に 近づくという特性を基盤にしています。したがって、Evolver に対し て所定の制限を満たさない解は一切検討しないよう指定すると、遺伝 的アルゴリズムを使った最適化の処理に支障をきたす場合がありま す。 Evolver では、ワークシートに指定されたオリジナルのシナリオです べてのハード制限が満たされていると、これらのハード制限を満たす 解も見つけやすくなります。このようなモデルでは、Evolver が有効 な解の空間内から最適化を開始することができます。制限がすべて満 たされるシナリオを判別できない場合には、Evolver に何らかのシナ リオを設定して実行すると、Evolver がこれらの制限を満たす範囲内 で最適な解を見つけようとします。 第 8 章: Evolver のその他の機能 167 ソフト制限 すべての制限を満たす解のみを検索するようプログラムに強要すると、 有効な解が見つからないこともあります。その場合には、いくつかの 解で制限が満たされなくても、ほぼ有効な解を見つける方が有用です。 常に満たす必要のあるハード制限を使用する代わりに、「ソフト制 限」を使用すると、これらの制限をなるべく満たすように Evolver に指定することができます。ソフト制限はハード制限よりも実用的で、 Evolver が試行できるオプションの数を増やすことができます。制限 が厳しい (すべての制限を満たすような可能な解が少ない) 問題の場 合、Evolver の遺伝的アルゴリズムでは、制限をほぼ満たすような解 からのフィードバックを得られるようにすると、最適な解の見つかる 可能性が高くなります。 制限が、例えば「ナイフの 2 倍の数のフォークを生産する」という ような設計目標である場合、これらの制限を満たすのはそれほど重要 でないことがあります。これは、完璧にバランスの取れた生産スケジ ュールを見つけるための最適化処理に、終日かかる場合などは特に当 てはまります。このような状況では、制限がほぼ満たされる (例えば フォークの生産数が 40%、ナイフが 23%、スプーンが 37% になるよ うな) 良い解を短時間で得る方が、1 日中処理を続けた後で、すべて の制限が満たすことが不可能なために解が 1 つも見つからないとい う結果よりも好ましいと言えます。 168 制限の追加 ペナルティ関数 ソフト制限はペナルティ関数を使用して Excel で簡単に設定できま す。ソフト制限では、解の検索に特定の値は絶対に使用しないよう指 定する代わりに、無効な値の使用を許可し、その結果得られた解にペ ナルティを適用します。例えば、トラックを 3 台だけ使用するとい う制限の下に、商品を流通させる最も効率的な方法を探していると想 定します。より現実的なモデルを構築するには、4 台以上のトラック も使用できるようにして、その場合には利益に大きな悪影響を及ぼす ペナルティ関数を含めます。ペナルティ関数の指定は、[制限設定] ダイアログで指定するか、これを表す数式をモデルに直接入力して追 加することもできます。 ペナルティ関数 の入力 Evolver では、ソフト制限を最初に入力するときにデフォルトのペナ ルティ関数が表示されます。ただし、ここに任意の有効な Excel 式 を入力して、ソフト制限が満たされない場合に適用するペナルティを 計算することができます。入力したペナルティ関数には、 「deviation」(偏差値) というキーワードを含める必要があります。 これは、制限を越えている絶対量を表します。Evolver は、特定の試 行解のシミュレーションの終了時に、ソフト制限が満たされているか 確認し、満たされていない場合は入力されたペナルティ関数に偏差値 を代入してから、ターゲット セル統計に適用するペナルティの量を 計算します。 ペナルティはターゲット セルの計算結果に加算または減算され、最 適な値との差を広げる役割を果たします。例えば、[Evolver - モデ ル] ダイアログの [最適化ゴール] フィールドで [最大] を選択した 場合、ペナルティはターゲット セルの計算値から差し引かれます。 第 8 章: Evolver のその他の機能 169 入力したペナル ティ関数の効果 の確認 Evolver には、PENALTY.XLS という Excel ワークシートが付属して います。これを使って、さまざまなペナルティ関数が特定のソフト制 限とターゲット セルの結果に与える影響を評価できます。 PENALTY.XLS では、効果を分析するソフト制限を、モデルから選択す ることができます。その後、ペナルティ関数を変更して、制限が満た されない場合に特定の値が、ペナルティの課された特定のターゲット セル統計にどうマッピングされるかを確認できます。例えば A10<100 というソフト制限があるとすると、PENALTY.XLS を使用して、セル A10 の計算値が 105 のときにターゲット値がどうなるかを確認でき ます。 適用されたペナ ルティの確認 170 ソフト制限が満たされないためにターゲット セルにペナルティが適 用された場合、そのペナルティ量を Evolver ウオッチャーで確認す ることができます。ペナルティ値は、最適化の後にオプションで作成 することのできる、「最適化ログ」ワークシートにも表示されます。 制限の追加 ワークシートへ のソフト制限の 入力 ペナルティ関数はワークシートに直接入力することもできます。ブー ル演算子のペナルティ関数は、指定された制限を満たさないすべての シナリオに、指定されたペナルティ値を適用します。例えば、セル B1 (供給) の値がセル A1 (需要) の値と同じかそれ以上になるよう にするには、別のセルに「=IF(A1>B1, -1000, 0)」というペナルティ 関数を指定します。このセルの結果をターゲット セルの統計に追加 すると、Evolver がこの制限に違反する解 (つまり供給が需要を満た さない解) を試行するたびに、最大化するターゲット セルの統計は 実際の結果より 1,000 低い値に設定されます。この制限に違反する すべての解でターゲット セルの統計値が低くなり、最終的には Evolver でこれらの個体は破棄されます。 ペナルティ関数には、制限を超えた度合いに応じてより正確なペナル ティ値を解に適用する、スケーリング ペナルティ関数を使用するこ ともできます。実世界では、スケーリングを使う方が実用的なことが あります。これは、供給が需要レベルを大幅に下回る解よりは、供給 が需要レベルをわずかに下回っている解の方が好ましいためです。簡 単なスケーリング ペナルティ関数により、制限のゴール値とその実 際の値との絶対差を計算します。例えば、A1 (需要) が B1 (供給) を越えることのできない上記の問題には、「=IF(A1>B1, (A1-B1)^2, 0)」というペナルティ関数を設定することができます。この種のペナ ルティ関数は、実際の値が制限をどの程度満たしているかを求め、そ の差異を 2 乗して増大します。したがって、制限の違反の程度によ ってペナルティ値が変化することになります。 第 8 章: Evolver のその他の機能 171 ペナルティ関数 の例 例えば、木材の使用量がプラスチックの使用量と等しくなければなら ないという制限のある製造業のモデルを構築したと想定します。この 制限は、「AmountWood (木材の量) = AmountPlastic (プラスチック の量)」の場合に満たされます。ここではこの 2 つの素材の量が均等 になる解を見つける必要があるので、ゴールと異なる結果を生む解に 対して、関数を使ってペナルティを課します。「=ABS(AmountWoodAmountPlastic)」という数式により、木材とプラスチックの使用量の 絶対差を計算します。ABS() 関数を使用するので、木材がプラスチッ クより 20 多い場合でも少ない場合でも、ペナルティの値は同じにな ります。このモデルを最適化する際のゴールは、この絶対差に対する シミュレーション結果の平均値を最小化することです。 では仮に、上記の代わりに、木材の使用量がプラスチックの 2 倍で なければならないという制限を課すとします。この場合のペナルティ 関数は次のようになります。 =ABS(AmountWood-AmountPlastic*2) または、木材の量がプラスチックの量の 2 倍以上でなければならな いという制限も考えられます。この前の例では木材の量が少なすぎて も多すぎてもペナルティを適用しましたが、ここでは木材が少なすぎ る場合にのみペナルティが課されます。したがって、AmountWood が AmountPlastic の 10 倍である場合はペナルティを適用しません。こ の例のペナルティ関数は次のようになります。 =IF(AmountWood<AmountPlastic*2, ABS(AmountPlastic*2-AmountWood),0) AmountWood が少なくとも AmountPlastic の 2 倍ある場合にはペナ ルティ関数の値が 0 になり、そうでない場合は AmountWood の量が AmountPlastic の 2 倍の量をどれだけ超えているかを返します。 172 制限の追加 ペナルティ関数 の使用 モデルのソフト制限を指定するペナルティ関数を作成したら、これを ターゲット セルの数式に組み合わせて制限が適用されたターゲット セル式を設定します。次の例では、セル C8 でプロジェクトの総費用 が計算され、セル範囲 E3:E6 に 5 つのペナルティ関数が設定されて いるので、セル C10 には「=SUM(C8, E3:E6)」などの数式を作成する ことができます。 合計値に制限を加えるセルを作成し、そのセルのシミュレーション結果の平均値を最 小化します。 ここでは C10 で E 列 のペナルティを C8 の費用に加算して、ペナ ルティ適用後の費用を求めています。ただし、最大化を行う問題の場 合には、ペナルティ値をオリジナルのターゲット セル値に加算する のではなく、減算することになるので注意してください。Evolver を 使用する場合、制限適用後のセル C10 のみを、最適化の対象となる シミュレーション統計を得るターゲット セルとして選択します。 すると、Evolver が制限適用後のターゲット セルの統計を最適化す る際、ペナルティ関数により、制限を満たすシナリオを重視して検索 が行われるようになります。そして最終的には、すべての制限を満た しているか、ほぼ満たしている (つまりペナルティ関数の値が 0 に 近い)、優れた解答のみが Evolver の解として残ります。 第 8 章: Evolver のその他の機能 173 ゴールが複数ある問題 Evolver のターゲット セル フィールドに指定できるセルは 1 つだ けですが、2 つのゴールを 1 つのゴールに組み合わせる関数を使用 することにより、ゴールが複数ある問題を解決することもできます。 例えば、高分子化学者が柔軟性と強度の両面で優れた物質を合成しよ うとしている場合を想定してみます。このモデルでは、特定の化学物 質の組み合わせから得られる強度、柔軟性、重量を計算します。この 問題の変数は、各化学物質の使用量です。 物質の強度 (セル S3) と柔軟性 (セル F3) の両方を最大限にしたい ので、新しいセルに「=(S3+F3)」という数式を入力します。これが新 しいターゲット セルとなり、この値が大きいほど解全体が優れてい ることになります。 強度よりも柔軟性を重視する場合には、ターゲット セルの数式を 「=(S3+(F3*2))」に変更します。すると柔軟性が特定量だけ高まるシ ナリオの方が、強度がこれと同じ量だけ高まるシナリオよりも評価が 良くなります (適応度が高くなります)。 物質の強度 (セル S5) を最大限にし、それと同時に重量 (セル W5) を最小限にするには、新しいセルに「=(S5^2)-(W5^2)」という数式を 入力します。この式の計算値は、合成物質が頑丈で軽量な場合に高く なり、弱くて重い物質の場合は低くなります。また、弱くて軽い物質 と強くて重い物質では均等な値となります。したがって、強度と重量 の両方のゴールを満たすには、このセルをターゲットとして使用し、 その平均値を最大化します。 174 制限の追加 処理速度の改善 Evolver を使用した問題の解決処理では、Evolver のコンパイル済み ルーチン ライブラリを使って処理が制御され、Excel のスプレッド シート評価機能を使ってさまざまなシナリオが検討されます。実際に は Evolver の処理時間の大部分は、Excel でスプレッドシートの再 計算に費やされます。Evolver での最適化と Excel の再計算の処理 速度を向上させるには、いくつかの方法があります。 ♦ Evolver の処理速度はコンピュータ プロセッサの処理速度と直 接関係があります。Pentium 2.0 GHz の速度は Pentium 1.0 GHz の約 2 倍です。したがって、Evolver が同じ時間内に 2 倍の数 のシナリオを処理できることになります。 ♦ Evolver の解がほぼ収束し、最適な解がしばらくの間 (例えば最 後の 1,000 試行において) 改善されなくなった場合、主に交差 のみを使用して現在の個体群内での解の微調整を続ける代わりに、 突然変異率を大きくして Evolver による解の検索対象を広くす ることもできます。突然変異率を増やすには、 [Evolver - 最適 化設定] ダイアログの [個体群サイズ] コマンドを使用します。 ♦ 調整可能セルの範囲を狭くします。すると、Evolver で解を検索 する範囲が小さくなり、結果として処理時間を短縮できます。た だし、Evolver が現実的な解をすべて検討するのに十分な自由が 与えられるような範囲を設定してください。 第 8 章: Evolver のその他の機能 175 Evolver の最適化の実装 このセクションでは、Evolver の最適化アルゴリズムの実装について 説明します。 注意: Evolver を使用するために、このセクションの内容を理解する 必要はありません。 レシピ解法や順序解法など、Evolver で採用されている遺伝的アルゴ リズム技術のほとんどは、遺伝的アルゴリズムの分野における過去 10 年にわたる学術研究の成果に基づいています。ただし、Evolver に含まれているほとんどの派生解法を始めとして、複数の調整可能セ ル グループを使用できる機能、バックトラック機能、戦略、そして 確率機能などは、Evolver 固有のものです。 Evolver では定常状態法を採用しています。これは、世代全体を 1 度に置換するのではなく、1 度に 1 つの個体のみを置換することを 意味します。定常状態法は、世代置換法と同等かそれ以上の効果があ ることが証明されています。Evolver で実行された「世代」の数を求 めるには、処理した試行の数を個体群のサイズで割り算します。 選択 新しい個体が作成される場合、現在の個体群から 2 個の親が選択さ れます。適応度スコアの高い個体は、親として選択される確率が高く なります。 Evolver では、順位に基づいて親が選択されます。繁殖時の親の選択 確率がその適応度に直接比例する一部の遺伝的アルゴリズム体系より も、順位付けを用いた方が、選択確率の曲線が滑らかになります。こ れにより、進化の初期段階から優秀な個体が完全に支配するという状 況を防ぐことができます。 176 Evolver の最適化の実装 交差 変数の調整方法は各解法ごとに異なるため、Evolver では特定の問題 のタイプに最も適した交差ルーチンが使用されます。 基本的なレシピ解法は、一様交差ルーチンを使って交差を実行します。 一様交差では、特定のシナリオの変数のリストを途中で分割して 2 つの各ブロックを処理する (一点交差または二点交差と呼ばれます) のではなく、アイテムを無作為に選びどちらかのグループに割り当て ることによって 2 つのグループが形成されます。従来の一点交差や 二点交差では、変数の位置が不適切なために検索が偏る可能性があり ますが、一様交差ではスキーマを維持しやすく、2 つの親からあらゆ るスキーマを生成することができます。 順序解法は、L デイビス著の『Handbook of Genetic Algorithms』 * で説明されている順序交差演算子に似たアルゴリズムを使用して交差 を実行します。このアルゴリズムは一方の親から無作為にアイテムを 選択し、もう片方の親のこれに相当する位置を見つけて、残りのアイ テムを最初の親に見られるのと同じ順序で 2 番目の親にコピーしま す。これにより、元の親の順序の一部が維持されると同時に、順序の 一部は新しく作成されます。 * Davis, Lawrence (1991).Handbook of Genetic Algorithms.New York: Van Nostrand Reinhold. 第 8 章: Evolver のその他の機能 177 突然変異 交差と同様に、突然変異の方法も各解法に応じてカスタマイズされて います。例えば基本的なレシピ解法は、各変数を個別に検討して突然 変異を実行します。個体の各変数に対して 0 ～ 1 の範囲のランダム 値が生成され、突然変異率と同じかそれ以下の値 (例: 0.06) となっ た場合、その変数の突然変異が行われます。突然変異の量と性質は、 Palisade 社独自のアルゴリズムによって自動的に決定されます。変 数の突然変異では、その値が最小 - 最大の有効範囲内で無作為に生 成された値に置き換えられます。 順序解法では、オリジナルの値をすべて維持するため、個体の一部の 変数の位置をスワップする方法で突然変異を実行します。実行するス ワップの数は、突然変異率の設定 (0 ～ 1) に比例して増減します。 置換 Evolver では世代置換ではなく順位による置換を用いるので、パフォ ーマンスが最下位の個体は、その適応度のスコアに関係なく、常に選 択、交差、突然変異により作成された新しい個体で置換されます。 制限 ハード制限は、Palisade 社独自の「バックトラック」技術を用いて 実装されています。新しい子孫が外部から課された制限に違反すると、 Evolver はその親のどちらかにバックトラックして、有効な解の範囲 内に収まるような子孫ができるまで、子の値を調整します。 178 Evolver の最適化の実装 付録 A: Evolver の自動化 Evolver には、その機能を使用するカスタム アプリケーションを構 築するための完全なマクロ言語が付属しています。Evolver のカスタ ム関数を Visual Basic for Applications (VBA) で使用して、最適 化処理の実行や最適化の結果を表示することもできます。このプログ ラミング インターフェイスの詳細については、Evolver デベロッパ ー キットのヘルプ マニュアルを参照してください。このマニュアル は Evolver の [ヘルプ] メニューからアクセスできます。 付録 A: Evolver の自動化 179 180 付録 B: トラブルシューティング と Q&A トラブルシューティングと Q&A このセクションには、Evolver に関して頻繁に寄せられる質問とその 答えが記載されています。ここで一般的な質問、問題、および推奨事 項についての最新情報を確認できます。このセクションに目を通して も疑問が解決しない場合は、このマニュアルの最初に記載されている Palisade 社カスタマ サポートまでお問い合わせください。 Q: Evolver で有効な答えが得られないのはなぜですか？ A: Evolver のダイアログが正しく設定されているか確認してくださ い。ほとんどの問題は変数の設定に関連しています。調整可能セ ルの各グループは排他的でなければなりません。つまり、1 つの セルやセル範囲を複数の解法で処理することはできません。 Q: Evolver で数値ではなく概念やカテゴリの処理を行うことはでき ますか？ A: 数値は単なる記号に過ぎないため、Evolver ではあらゆる種類の データを間接的に処理できます。整数とテキスト文字列のマッピ ングを行うには、Excel のルックアップ テーブルを使用しま す。Evolver もほかのすべてのコンピュータ プログラムと同 様、究極的には数値のみを処理します。しかし、適切なインター フェイスによりこれらの数値を使ってあらゆる文字列を表現する ことが可能です。 付録 B: トラブルシューティングと Q&A 181 Q: ダイアログを同じように設定して Evolver での処理を同じ時間 だけ実行しても、見つかる解が違うことがあるのはなぜですか？ A: 生物界の自然淘汰と同じく、Evolver の遺伝的アルゴリズムも解 の検索において常に同じ経路を辿るとは限りません (ただし乱数 生成のシード値を固定する場合は除きます)。皮肉なことに、こ の「意外性」こそは、Evolver が従来の手法と比べてより多くの 種類の問題に対して優れた解答を見つけ出せる理由でもありま す。Evolver の遺伝的アルゴリズム エンジンでは、あらかじめ プログラミングされたコマンドを単に実行したり、数式を使って 値を代入したりするだけではなく、多くの無作為な仮説を同時に 使って効率的な実験を行い、その結果、ランダムな要素を含む 「適者生存」演算子を通じて検索を絞り込んでいきます。 Q: ベストな解が変化しないのはなぜですか？ A: [Evolver - モデル] ダイアログで、ターゲット セルを誤って指 定している可能性があります。Evolver が空白のセルをターゲッ ト セルとして処理していると、そこに数式がないために値が変 化しません。これを修正するには、[Evolver - モデル] ダイア ログを表示して適切なターゲット セル、つまり起こりうる各解 の適応度を正確に反映しているセルを選択します。ターゲット セルには、Evolver が調整する変数 (調整可能セル) に直接ある いは間接的に依存する数式が入っている必要があります。 Q:スプレッドシート モデルのセルの一部に「####」という記号が表 示されるのはなぜですか？ A: セルが小さすぎてその値がすべて収まらない場合、一連の # 記 号が表示されます。セルのサイズを大きくしてください。 182 トラブルシューティングと Q&A Q: Evolver は一応機能していますが、より優れた結果を得る簡単な 方法はありますか？ A: 問題の制限を現在よりも緩く設定します。これには変数の範囲も 含まれます。ハード制限の一部を、ペナルティ関数を使用したソ フト制限に変更してみます (「第 8 章: Evolver のその他の機 能」の「制限の追加」セクションを参照してください)。Evolver が試行できる対象にあまり多くの制限があると、より良い解につ ながる可能性のある領域を検索できなくなることがあります。 Evolver の処理時間が長くなるほど、最適な解が見つかる可能性 は高くなります。Evolver の微調整を行うためのヒントは、「第 8 章: Evolver のその他の機能」を参照してください。 Evolver で試行するシナリオの数が多いほど、最適化の結果は改 善されます。Evolver の処理速度を向上させるには、再計算ごと に表示を更新するオプションをオフにします。 付録 B: トラブルシューティングと Q&A 183 184 付録 C: 参考文献 参考文献 以下は、遺伝的アルゴリズムおよび人工知能について参考になる文献 のリストです。アスタリスク (*) が付いているのは、弊社が特に推 奨する文献です。 書籍 • Bolles, R.C., & Beecher, M.D. (Eds.). Learning. Lawrence Erlbaum. (1988). Evolution and • Beer, R.D. (1990). Intelligence as Adaptive Behavior: An Experiment in Computational Neuroethology. Academic Press. • Davis, Lawrence (1987). Genetic Algorithms and Simulated Annealing. Palo Alto, CA: Morgan Kaufman. * Davis, Lawrence (1991). Handbook of Genetic Algorithms. Van Nostrand Reinhold. • Darwin, Charles (1985). On The Origin of Species. Penguin Classics. (originally 1859) * Dawkins, Richard. Press. (1976). The Selfish Gene. New York: London: Oxford University • Eldredge, N. (1989). Macroevolutionary Dynamics: Species, Niches, and Adaptive Peaks. McGraw-Hill. • Fogel, L., Owens, J., and Walsh, J. (1966). Artificial Intelligence through Simulated Evolution. New York: John Wiley and Sons. • Goldberg, David (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley Publishing. • Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press. 付録 C: 参考文献 185 • Koza, John (1992). Press. * Langton, C.L. Genetic Programming. (1989). • Levy, Steven (1992). Artificial Life. Artificial Life. Cambridge, MA: MIT MIT Press. [ALife I] New York: Pantheon. • Meyer, J.-A., & S.W. Wilson (Eds.). (1991). Proceedings of the First International Conference on Simulation of Adaptive Behavior: From Animals to Animats. MIT Press/Bradford Books. * Proceedings of the Sixth International Conference (ICGA) on Genetic Algorithms (1995). San Mateo, CA: Morgan Kaufman Publishing. (Also available; the first five ICGA proceedings). • Proceedings of the Workshop on Artificial Life (1990). Christopher G. Langton, Senior Editor. Reading, MA: AddisonWesley Publishing. • Rawlins, Gregory (1991). Foundations of Genetic Algorithms. Mateo, CA: Morgan Kaufman Publishing. San • Richards, R.J. (1987). Darwin and the Emergence of Evolutionary Theories of Mind and Behavior. U. Chicago Press. • Williams, G.C. (1966). Princeton U. Press. Adaptation and Natural Selection. 論文・記事 * Antonoff, Michael (October, 1991). Popular Science, p. 70-74. Software by Natural Selection. • Arifovic, Jasmina (January, 1994). Genetic Algorithm Learning and the Cobweb Model. In Journal of Economic Dynamics & Control v18 p.3 * Begley, S (May 8, 1995). “Software au Naturel” In Newsweek p. 70 • Celko, Joe (April, 1993). Genetic Algorithms and Database Indexing. In Dr. Dobb’s Journal p.30 • Ditlea, Steve (November, 1994). Magazine p.48 Imitation of Life. In Upside • Gordon, Michael (June, 1991). User-based Document Clustering by Redescribing Subject Descriptions with a Genetic Algorithm. In Journal of the American Society for Information Science v42 p.311 • Hedberg, Sara (September, 1994). AI Expert, p. 25-29. 186 Emerging Genetic Algorithms. In 参考文献 • Hinton, G.E., & Nowlan, S.J. (1987). How Learning Can Guide Evolution. In Complex Systems 1: p.495-502. * Kennedy, Scott (June, 1995). Genetic Algorithms: Digital Darwinism. In Hitchhicker’s Guide to Artificial Intelligence Miller Freeman Publishers • Kennedy, Scott (December, 1993). Expert, p. 35-38 • Lane, A (June, 1995). p.11 Five Ways to a Better GA. In AI The GA Edge in Analyzing Data. In AI Expert • Lee, Y.C. (Ed.). (1988). In World Scientific. Evolution, learning, and cognition. • Levitin, G and Rubinovitz, J (August, 1993). Genetic Algorithm for Linear and Cyclic Assignment Problem. In Computers & Operations Research v20 p.575 • Marler, P., & H.S. Terrace. (Eds.). Learning. Springer-Verlag. (1984). The Biology of • Mendelsohn, L. (December, 1994) Evolver Review In Technical Analysis of Stocks and Commodities. p.33 • Maynard Smith, J. (1987). Nature 329: p.761-762. When Learning Guides Evolution. In • Murray, Dan (June, 1994). Tuning Neural Networks with Genetic Algorithms. In AI Expert p.27 • Wayner, Peter (January, 1991). Genetic Algorithms: Programming Takes a Valuable Tip from Nature. In Byte Magazine v16 p.361 雑誌・ニュースレター • Advanced Technology for Developers (monthly newsletter). Jane Klimasauskas, Ed., High-Tech Communications, 103 Buckskin Court, Sewickley, PA 15143 (412) 741-7699 • AI Expert (monthly magazine). Larry O’Brien, Ed., 600 Harrison St., San Francisco, CA 94107 (415) 905-2234.*Although AI Expert ceased publishing in the spring of 1995, its back issues contain many useful articles.Miller-Freeman, San Francisco. • Applied Intelligent Systems (bimonthly newsletter). New Science Associates, Inc. 167 Old Post Rd., Southport, CT 06490 (203) 259-1661 • Intelligence (monthly newsletter). Edward Rosenfeld, Ed., PO Box 20008, New York, NY 10025-1510 (212) 222-1123 付録 C: 参考文献 187 • PC AI Magazine (monthly magazine). Joseph Schmuller, Ed., 3310 West Bell Rd., Suite 119, Phoenix, AZ 85023 (602) 971-1869 • Release 1.0 (monthly newsletter). Esther Dyson, Ed., 375 Park Avenue, New York, NY 10152 (212) 758-3434 • Sixth Generation Systems (monthly newsletter). Derek Stubbs, Ed., PO Box 155, Vicksburg, MI, 49097 (616) 649-3592 シミュレーションの基礎知識 シミュレーションについての知識があまりない場合、またはシミュレ ーション手法に関する基礎を学ぶには、以下の書籍や文献を参考にし てください。 * Baird, Bruce F. Managerial Decisions Under Uncertainty: John Wiley & Sons, Inc. 1989. * Clemen, Robert T. Making Hard Decisions: Duxbury Press, 1990. • Hertz, D.B. "Risk Analysis in Capital Investment": HBR Classic, Harvard Business Review, September/October 1979, pp. 169-182. • Hertz, D.B. and Thomas, H. Risk Analysis and Its Applications: John Wiley and Sons, New York, NY, 1983. • Megill, R.E. (Editor). Evaluating and Managing Risk: PennWell Books, Tulsa, OK, 1984. • Megill, R.E. An Introduction to Risk Analysis, 2nd Ed.: PennWell Books, Tulsa, OK, 1985. • Morgan, M. Granger and Henrion, Max, with a chapter by Mitchell Small, Uncertainty: Cambridge University Press, 1990. • Newendorp, P.D. Decision Analysis for Petroleum Exploration: Petroleum Publishing Company, Tulsa, Okla., 1975. • Raiffa, H. Decision Analysis: Addison-Wesley, Reading, Mass., 1968. 188 参考文献 シミュレーションとモンテカルロ抽出法に関する技 術文献 シミュレーション、抽出法、統計理論に関する詳細については、以下 の書籍や文献を参考にしてください。 • Iman, R. L., Conover, W.J. "A Distribution-Free Approach To Inducing Rank Correlation Among Input Variables": Commun. Statist.-Simula. Computa.(1982) 11(3), 311-334 * Law, A.M. and Kelton, W.D. Simulation Modeling and Analysis: McGraw-Hill, New York, NY, 1991,1982. Rubinstein, R.Y. Simulation and the Monte Carlo Method: John Wiley and Sons, New York, NY, 1981. ラテン方格抽出法に関する技術文献 比較的新しい手法であるラテン方格抽出法に興味がある場合は、以下 の文献を参考にしてください。 • Iman, R.L., Davenport, J.M., and Zeigler, D.K. "Latin Hypercube Sampling (A Program Users Guide)": Technical Report SAND79-1473, Sandia Laboratories, Albuquerque (1980). • Iman, R.L. and Conover, W.J. "Risk Methodology for Geologic Displosal of Radioactive Waste: A Distribution - Free Approach to Inducing Correlations Among Input Variables for Simulation Studies": Technical Report NUREG CR 0390, Sandia Laboratories, Albuquerque (1980). • McKay, M.D, Conover, W.J., and Beckman, R.J. "A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code": Technometrics (1979) 211, 239-245. • Startzman, R. A. and Wattenbarger, R.A. "An Improved Computation Procedure for Risk Analysis Problems With Unusual Probability Functions": SPE Hydrocarbon Economics and Evaluation Symposium Proceedings, Dallas (1985). 付録 C: 参考文献 189 シミュレーションを使用したサンプルや活用事例 シミュレーションの実用例に関しては、以下の文献を参考にしてくだ さい。 Hertz, D.B. and Thomas, H. Practical Risk Analysis - An Approach Through Case Histories: John Wiley and Sons, New York, NY, 1984. * Murtha, James A. Decisions Involving Uncertainty, An @RISK Tutorial for the Petroleum Industry: James A. Murtha, Houston, Texas, 1993 • Newendorp, P.D. Decision Analysis for Petroleum Exploration: Petroleum Publishing Company, Tulsa, Okla., 1975. • Pouliquen, L.Y. Risk Analysis in Project Appraisal: World Bank Staff Occasional Papers Number Eleven. John Hopkins Press, Baltimore, MD, 1970. * Trippi, Robert R. and Truban, Efraim, Neural Networks: In Finance and Investing: Probus Publishing Co., 1993 190 参考文献 用語集 用語に関する詳細については、このマニュアルの索引を参照してくだ さい。 アルゴリズム 特定の種類の問題を解決するための方法を、順を追って数学的に指定 したもの。すべてのコンピュータ プログラムは、多くのアルゴリズ ムの組み合わせで構築されています。 遺伝子型 生物学における遺伝子型とは、個体の遺伝子構造のことです。一般に この用語は個体の遺伝子を総体したものを指します。遺伝的アルゴリ ズムの分野においては、問題の 1 つな可能な解として評価される人 工「染色体」のことを意味します。 遺伝的アルゴリ ズム いくつかの可能な解を繰り返し試行して、より良い解の構成要素を複 製したり混合することにより、操作の結果を改善するための手順。こ の処理は、適者生存の法則により生殖が行われる、生物界の進化の過 程に基づいています。 解 すべてのモデルに、1 つの出力を生成する多くの変数が含まれていま す。Evolver で言う「解」とは通常、変数の唯一の最適な組み合わせ ではなく、起こりうる変数の組み合わせのうちの 1 つを指します。 解法 Evolver には 6 つの解法が用意されています。各解法には、特定の 種類の問題を解決するためにカスタムのアルゴリズムが使われます。 問題で選択された変数の各セットについて、ユーザーがその処理に使 用する解法を指定する必要があります。利用できる解法には、グルー ピング、順序、レシピ、予算、プロジェクト、スケジュールがありま す。 確率 確率は、どれくらいの可能性で値または事象が発生するかを示す尺度 です。値または事象の発生数を合計発生数で除算した頻度として、シ ミュレーション データから測定することができます。この計算は 0 ～ 1 の値を返すため、100 を乗算することで百分率に変換できます。 →「度数分布」、「確率分布」を参照 確率性 不確実性やリスク性の類義語です。 →「リスク」、「決定性」を参照 用語集 191 確率分布 確率分布または確率密度関数とは、クラス サイズが無限小である、 無限大のセットの値から構成された度数分布のことを指す統計学用語 です。 →「度数分布」を参照 関数 Excel の関数はあらかじめ定義された数式で、入力された値に対して 操作を行い、その結果を返します。Excel には、式の操作に必要な時 間とスペースを節約できる、「SUM」などの数百の数式が組み込まれ ています。例えば、「A1+ A2+ A3+ A4+ A5+ A6」と入力する代わりに、 「SUM(A1:A6)」と入力するだけで同じ結果を得られます。 極大値 特定の値の範囲内において、特定の関数が取りうる最大値。極大値は、 変数の一部またはすべての値をわずかに変更することで、関数の結果 がそれより少ない量だけ変化する場合に、関数内の変数の一連の値に 対して存在します。 →「大局的な最大値」も参照 決定性 決定性という用語は、与えられた値または変数に不確実性が伴わない ことを示します。 交差 遺伝子学における交差とは、分裂中に同種の染色分体間で行われる同 等な遺伝物質の交換のことです。Evolver で言う交差とは、これに相 当する計算処理のことを意味します。変数間の交換により新しいシナ リオの組み合わせが生成されます。 高次モーメント 高次モーメントとは、確率分布の統計です。一般にこの用語は、歪度 と尖度 (つまり 3 次モーメントと 4 次モーメント) のことを指しま す。1 次モーメントは平均値、2 次モーメントは標準偏差のことをそ れぞれ表します。 →「歪度」、「尖度」、「平均値」、「標準偏差」を参照 個体 一連の変数値 (シナリオ) が保管された、個体群内のメモリ ブロッ ク。 個体群 Evolver がメモリに保管する、シナリオのセット全体を指します。こ の個体群から新しいシナリオが生成されます。Evolver は、モデルの 調整可能セル グループそれぞれにつき、起こりうる解の個体群を 1 つ維持します。 最適化 関数の出力が最大化または最小化されるような変数の値を見つける処 理。方程式を解くタイプの最適化は、変数が少なく変動の滑らかな関 数では簡単に行えますが、実世界の問題を処理するのは非常に困難で す。一般に、困難な問題を解くには検索機構が必要となります。 Evolver は、遺伝的アルゴリズムに基づく最適化検索機構を用いてい ます。 192 最頻値 最頻値またはモードは、一連の値で最も多く発生する値を指します。 ヒストグラムや結果分布では、確率が最も高いクラスやバーの中央値 に相当します。 試行 Evolver で問題の各変数の値を生成し、シナリオを再計算して評価を 行う処理のことです。 シナリオ スプレッドシート モデル内の変数の一連の値を指します。通常の場 合、各シナリオが 1 つの可能な解を表します。 シミュレーショ ン シミュレーションとは、ある不確実な状況において発生しうるすべて の可能なシナリオを取得するために、Excel ワークシートなどのモデ ルを異なる入力値を使って繰り返し計算する手法を意味します。 従属変数 従属変数は、考察するモデルのその他の変数の値に何らかの方法で依 存する変数です。ある形式では、不確実な従属変数の値は、その他の 不確実なモデル変数の関数の方程式から計算することができます。そ の他、従属変数は、独立変数の標本を抽出するのに使用される乱数と 相関する乱数に基づく分布から抽出されることがあります。 →「独立変数」を参照 ステータス バー ステータス バーは Excel ウィンドウの下部にあり、Evolver の現在 の状況が表示されます。 制限 制限は、シナリオを有効とみなすために、満たすことが好ましい条件 (ソフト制限)、または満たす必要のある条件 (ハード制限) です。 世代 遺伝的アルゴリズムの分野では、まったく新しい「子孫」の解からな る個体群のことを、新しい「世代」と呼びます。一部の遺伝的アルゴ リズム ルーチンでは、個体群の全メンバーを 1 度に掛け合わせ、ま ったく新しい世代の子孫を生成して前世代の個体群を置き換えます。 Evolver では、1 度に 1 つの個体を評価し置き換える (順位置換) ので、「世代」という用語は使われません。この定常状態法は、世代 置換と同等の効果があります。 セル セルは、スプレッドシートにデータを保管するための基本単位です。 Excel ワークシートでは最大 256 列、16,000 行のセル、つまり合計 400 万以上のセルが使用できます。 尖度 尖度とは、分布形状の尺度です。尖度によって、分布がどの程度平ら であるか、または尖っているかが示されます。尖度が高いほど、より 尖り気味の分布が得られます。 →「歪度」を参照 ソフト制限 制限を必ずしも満たす必要がない場合には、ハード制限の代わりにソ フト制限として設定することができます。ソフト制限を設定するには、 Evolver でペナルティ関数を指定するか、ターゲット セルの適応度 関数にペナルティ関数を追加します。 Error! Style not defined. 193 一般に、できるだけソフト制限を使用する方が適しています。その理 由は、1) Evolver ではソフト制限の課された問題の方が迅速に解決 できること、そして 2) ソフト制限のあるモデルでは、その制限をほ ぼ満たしている優れた解を見つけられること (これはハード制限を満 たす質の悪い解よりも有用です)、の 2 点にあります。 ソルバー (俗語) 線形プログラミング手法の組み合わせか、基本的な山登り法 アルゴリズムを使って、目的の出力を生成するような入力を見つける ためのシンプルなソフトウェア プログラム。ソルバーでは、推測を 行った上で解答を調整しますが、最終的な答えが「大局的」な解では なく「局所的」な解となることがよくあります。 ターゲット セル 最小化または最大化する必要のある値が入っている、スプレッドシー ト セル。このセルは [Evolver - モデル] ダイアログで設定します (Evolver の [モデルの定義] コマンドか、[モデル] アイコンを選択 します)。 ダイアログ ユーザーからの入力を求めるためにコンピュータ画面に表示されるウ ィンドウのことを指します。「ダイアログ ボックス」とも呼ばれま す。Evolver には [Evolver - モデル] と [調整可能セル] の 2 つ の主要なダイアログがあります。 大局的な最大値 特定の関数の、起こりうる最大値。複雑な関数やモデルでは多くの極 大値が存在しても、大局的な最大値は 1 つしか存在しないことがあ ります。 調整可能セル ターゲット セルの値を最適化するために、Evolver によって値を調 整できるスプレッドシート セル。調整可能セルは可変の値であり、 式ではなく数値を指定する必要があります。 調整可能セルの グループ 一連の変数とその処理方法をまとめて、1 つの調整可能セル グルー プにします。Evolver では、[モデル] ダイアログの変数セクション にすべての調整可能セル グループが表示されます。このアーキテク チャにより、複雑な問題を構築して複数の調整可能セル グループと して表すことが可能になります。 適応度関数 特定の問題に対する、提示された解の適応度を求める数式です。遺伝 的アルゴリズムの分野では、生物界の選択における「適応度」に相当 する用語として使われます。遺伝的アルゴリズムを使って問題を解決 する場合、正確な適応度関数を設定することが不可欠です。この適応 度関数によるシミュレーションの結果が、最適化が必要なゴール、つ まりターゲット値となります。 適者生存 適者生存とは、環境への適応度の高い個体ほど生存期間が長くなり、 生殖により個体群の次世代に遺伝子を受け渡す可能性が高い、という 理論のことです。 194 独立変数 独立変数は、考察するモデルのその他の変数の値にまったく依存しな い変数です。不確実な独立変数の値は、適切な確率分布から標本を抽 出することにより決定されます。この標本は、モデルのその他の変数 に抽出されたほかのランダム標本とは関係なく、独立した方法で抽出 されます。 →「従属変数」を参照 度数分布 度数分布は、Evolver の出力確率分布および、入力ヒストグラム (HISTOGRAM) 分布を表す正当な用語です。度数分布は、値をクラスに 分類し、柱高によってクラス内の発生度数を表わした分布です。この 発生頻度は確率に相当します。 突然変異 生物界では遺伝子の突然変異によって、効果的な自然淘汰に必要とさ れる多様性が生まれます。遺伝的アルゴリズムでもこれと同様、突然 変異を使って可能なシナリオの個体群中の多様性を維持します。 パーセンタイル パーセンタイルとは、データ セット内の変数の増加量を意味します。 パーセンタイルによって 100 等分される各データ範囲に、合計値の 1 パーセントが含まれます。例えば、60 パーセンタイルは、データ セット内で 60% の値がこれを下回り、40% がこれを上回る位置を示 す値です。 ハード制限 常に満たさなければならない制限。例えば、レシピ解法の変数の範囲 にハード制限を適用する場合、10 ～ 20 に範囲が設定された変数に は、10 未満の値や 20 より大きい値は決して使用できません。 →「ソフト制限」も参照 範囲 Evolver における定義: Evolver で特定の変数を調整する際に許可される範囲、つまり最大値 と最小値は、ユーザーが設定します。範囲を設定する理由は必ずしも 問題を解決するためではなく、可能な値を制限して Evolver の検索 対象を絞り込むためです。 Excel における定義: ワークシート内の連続したセルのブロック。範囲を定義するには、左 上隅のセルと右下隅のセルを指定します (例えば、「A5:C9」の範囲 には 15 個のセルが含まれます)。 反復試行 反復試行は、シミュレーション中にユーザーのモデルを再計算するこ とを意味します。1 回のシミュレーションは、数々の再計算、または 反復試行から構成されています。それぞれの反復試行中、すべての不 確実変数が各確率分布によりいったんサンプリングされ、これらの標 本値を使用してモデルの再計算が行われます。 →反復試行は「シミュレーション試行」とも呼ばれます。 表現型 生物学では、遺伝子間および遺伝子と環境との間の相互作用により、 目に見える形で現れる個体の特質のことを表現型と呼びます。遺伝的 Error! Style not defined. 195 アルゴリズムの分野においては、表現型は完全な解 (または「染色 体」) を構成する個々の変数 (または「遺伝子」) のことを指します。 →「遺伝子型」を参照 標準偏差 標準偏差とは、分布内の値の分散度を図る尺度で、分散の平方根に等 しくなります。 →「分散」を参照 フィールド データを入力するための基本単位。フィールドには、その種類によっ てテキスト、画像、数値などのアイテムが含まれます。Evolver のダ イアログの大半のフィールドは、ユーザーがスプレッドシート セル の位置または Evolver の動作を指定するオプションを入力するため に表示されます。 平均値 一連の値の平均値とは、これらすべての値の合計値を、そのセットに 含まれる変数の合計数で割った値です。 →「期待値」と同義 ペナルティ関数 特定の条件を満たさないシナリオにペナルティを課すために Evolver が使用することのできるスプレッドシート方程式。ペナルティ関数を 使用すると、シナリオの副作用を最小化したり、複数のゴールを達成 するのに役立ちます。ハード制限と異なり、ペナルティ関数は無効な 解の検討を許可しますが、個体群がこれらの解とは離れた方向に進化 するように、そのような解の評価を下げる役割を果たします。ブール 演算子によるペナルティはオンかオフのどちらかになり、無効な解の すべてに同量のペナルティを適用します。スケーリング ペナルティ はこれより柔軟性があり、制限の違反の度合いに比例する量のペナル ティを適用します。 モデル このマニュアルで言うモデルとは、実世界の状況を Excel で数値に より表したものを指します。 モンテカルロ法 モンテカルロ法は、シミュレーション モデリングにおけるランダム 変数の従来の抽出法です。標本は、分布の範囲内で完全に無作為に選 択されるため、非常に歪んだ、または裾の長い分布の収束には、大量 の標本が必要になります。 →「ラテン方格法」を参照 山登り法アルゴ リズム 特定のシナリオから開始して、解を改善する方向に繰り返し少しずつ 進めていく最適化の手法。山登り法アルゴリズムはシンプルで処理も 高速ですが、欠点が 2 つあります。まず、改善度が最も大きい方向 を見つけるために多大な処理が必要となる可能性があります。さらに、 一般に山登り法では一番近くの山頂、つまり「極大値」が見つかりま す。そのため、問題が難しい場合、大局的な最大値が見つからないこ とがあります。 196 ラテン方格法 ラテン方格法は、シミュレーション モデリングで使用される比較的 新しい層化抽出法です。モンテカルロ抽出法とは対照的に、層化抽出 法は、少数の標本で標本分布の収束を行える傾向にあります。 →「モンテカルロ法」を参照 乱数ジェネレー タ 乱数ジェネレータとは、通常 0 から 1 の範囲で乱数を選択するアル ゴリズムです。これらの乱数は、最小値 0 と最大値 1 の一様分布か ら抽出された標本と同等であり、これを特定の分布タイプから抽出さ れた標本へ変換するその他のルーチンの基盤となります。 →「ランダム標本」、「シード」を参照 ランダム標本 ランダム標本とは、ランダム変数を表す確率分布から選択された 1 つの値です。これらの標本は、サンプリングの「アルゴリズム」に従 って無作為に抽出されます。このアルゴリズムで抽出された大量のラ ンダム標本から構成される度数分布によって、そのアルゴリズムのゴ ールである確率分布の近似値が求められます。 離散型分布 最小値と最大値の間で有限数の離散値のみが可能値である確率分布。 →「連続型分布」を参照 累積度数分布 累積度数分布は、Evolver の出入力累積分布を表す用語です。累積分 布は、度数分布の範囲の度数を累積して (つまり柱高を徐々に追加し て) 表示されます。累積分布は、変数値に等しいかそれ以下の確率を 表す場合は「上向きの傾斜曲線」となります。また、変数値に等しい かそれ以上の確率を表す累積分布の場合は「下向きの傾斜曲線」とな ります。 →「累積分布」を参照 累積分布 累積分布 (累積分布関数) は最大値からランダム変数の所定の値まで の範囲における、確率分布の積分に等しい点から構成された、一連の 点です。 →「累積度数分布」、「確率分布」を参照 連続型分布 最小値と最大値の間のすべての値が可能な確率分布 (確率は有限)。 →「離散型分布」を参照 歪度 歪度とは、分布形状の尺度です。歪度によって、分布の非対称度が示 されます。歪んだ分布はピークまたは最頻値の片方により多くの値を 含み、一方の裾がもう片方の裾よりも長くなります。歪度 0 は対称 的な分布を示します。また、負の歪度は分布が左側に歪んでいること を意味し、正の歪度は分布が右側に歪んでいることを示します。 →「尖度」を参照 Error! Style not defined. 197 198 索引 Ｅ Evolver Microsoft ソルバーとの違い 概要 機能 チュートリアル 適用ケース 利点 Evolver ウオッチャー Evolver のコンピュータからの削除 Evolver の自己学習 Excel ソルバー(「ソルバー」を参照) 144 13 137 10 145 16 36, 125 7 10 143 Ｇ GRG ルーチン 143 Ｐ Palisade 社 5 あ アルゴリズムの定義 値 92 アプリケーション設定コマンド アルファベット順並べ替えの例 137 121 47 い 遺伝演算子 遺伝子プール Error! Style not defined. 105 161 199 遺伝的アルゴリズム コンピュータの例 生物の例 利点 161 158 16 う ウオッチャー 36, 125 え 演算子 105 お 「お読みください」(README) ファイル 10 か 解の地形 解法 グルーピング 例 59, 69 順序 例 49, 65, 77 スケジュール 例 57 制限としての解法 プロジェクト 例 63 予算 例 45, 53, 71, 73 レシピ 例 47, 51, 55, 67, 75, 79, 81, 83, 85 化学平衡の例 画面の再描画 画像 138 97 100 166 98 95 55 34 き 技術仕様 200 176 局所的な解 ～と大局的な解 143 く グラフ グラフの進行状況 画像 グルーピング解法 説明 例 59, 69 36, 126 34 97 け 経路の例 63 こ 広告ミックスの例 交差率 機能 実装方法 購入判断の例 コードのセグメント化の例 ゴールが複数ある問題 45 103, 128, 160 103 177 75 59 174 さ 最適化 概要 手法 例 141 最適化ゴール 最適化実行詳細オプション 15 137 25, 90 115 し 時間 授業のスケジュールの例 巡回セールスマンの問題の例 巡回セールスマンの例 順序解法 Error! Style not defined. 115 57 77 77 201 例 49, 65, 77 順列組み合わせの問題 証券トレーダーの例 処理速度、改善 進行状況ウィンドウ シンプレックス手法 137 81 175 119 147 す スケジュール解法 説明 例 57 ステータス バー スペースシャトルの例 100 125, 193 79 せ 制限 実装 製作工場の例 整数 制約ソルバー コマンド 世代置換 使用しない理由 線形の問題 選択ルーチン 164– 65 178 65 92 122 176 147 176 そ ソフト制限 ソルバー Evolver との違い 28, 108, 109, 168 143 144 た ターゲット セル 大局的な解 ～と局所的な解 タスク割り当ての例 202 25, 90, 194 143 49 ち 置換方法 チュートリアル 調整可能セル 178 10 25, 91 つ 追加 - 制限の追加 107 て 停止条件 概要 データベース テーブルベースの問題 適応度関数 115 32 149 149 21, 90 と 突然変異率 機能 実装方法 128 104 178 は パーセンタイル ハード制限 バックトラック 195 28, 108 178 ふ プロジェクト解法 例 63 へ ベーカリーの例 ペナルティ関数 使用 Error! Style not defined. 51 173 203 説明 例 172 変圧器の例 169 83 ほ ポートフォリオ配分の例 ポートフォリオ分散の例 71 69 も モデル ダイアログ 問題 順列組み合わせ 線形 テーブルベース 24, 89 150 147 149 や 山登り法 ソルバーでの使用 例 148 139 143 ゆ 輸送費の例 85 よ 予算解法 説明 例 45, 53, 71, 73 予算配分の例 98 53 ら ラジオ送信機の例 ラジオ塔の配置の例 204 73 67 れ レシピ解法 説明 例 47, 51, 55, 67, 75, 79, 81, 83, 85 連続型モデル Error! Style not defined. 95 143 205 206