Comments
Description
Transcript
九州大学海洋システム工学専攻 システム設計特論 (木村) 水曜2限(10
2008年10月1日 九州大学 海洋システム工学専攻 システム設計特論 (木村) 水曜2限(10:30~12:00) 場所:船2講義室 1 システム設計特論 全体の授業内容: 様々なタイプの最適化問題とその解法について述べる ・問題のモデル化について ・数値最適化問題およびその最適化手法 (勾配法、滑降シンプレックス法、遺伝的手法) ・組合せ最適化問題およびその最適化手法 (PERT、ランダムサーチ、分枝限定法、焼きなまし法) ・多目的最適化問題とその解法 (遺伝的アルゴリズム) ・知識発見、学習システムの設計 (関数近似、ニューラルネットワーク、決定木、クラスタリング手法) 試験成績評価方法: ・テーマの区切り毎にレポート (計40点) ・授業日程の最終日程3回は、学生のプレゼンテーション形式のゼミ(1人10分程度) 発表内容は投票によって評価し、優秀者は成績評価に加点+α ただし、内容に明らかな誤りがある場合は失格(0点)とする 60点満点で評価 2 講義日程 10月 1日 概要説明 確率シミュレーション 10月 8日 連続関数の最適化1(ラインサーチ/勾配法) 10月15日 連続関数の最適化2(シンプレックス法) 10月22日 連続関数の最適化3(SA・遺伝的手法) 10月29日 組合せ最適化 11月 5日 多目的最適化・遺伝的多目的最適化手法 11月12日 関数近似(線形回帰) 11月19日 データの補間による関数近似・計算幾何学 11月26日 非線形関数近似(ニューラルネット) 12月 3日 パターン学習と最適化 12月10日 確率ネットワーク 12月17日 最適化の実例紹介 1月7,14,21日 学生によるプレゼンテーション 3 計算機環境について 本講義のレポート課題では、最適化アルゴリズムを計算機上にプログラミングして 実行することが必要となるので、各自で用意しておくこと。 【推薦するプログラミング言語・環境】 1)Excel上でVBA(高度なマクロのようなもの)を使う → ◎お手軽/初心者向け/将来的に即戦力 × 最新のオブジェクト指向言語であり、Fortranとのギャップ大 × マイクロソフト社の環境に特化 2)Java言語を使う → ◎最も洗練されたオブジェクト指向言語/タダで使える/ ◎ WindowsだけでなくLinuxでも使える/携帯アプリのプログラムも作れる × 上級者向け/ Fortranとのギャップ大 3)C言語/C++言語を使う → ◎プログラミング言語としてはスタンダード ×Windowsで無料のパッケージ入手困難/上級者向け 4)Fortran言語を使う → 流体・構造計算に強いが、新しいプログラムの開発効率 が悪いため将来的に消滅していく可能性高 (木村の私見) 4 システム設計の概要 1) 「モデル化」: 問題の本質を正しく捉えて、うまく表現する 2) 「最適化」: モデルを用いて、何らかの設計指標の意味で 最も好ましい設計パラメータを見つける 扱うシステム: 機械/物流/通信/人工知能など どのような設計問題でも、「モデル化」と「最適化」を適切に行う ことにより、同様に扱うことが可能 5 【最適化とは?】 「最も良い状態になるように、手段や方法を考えて行動すること」 最適化以前に、 その目的である 「評価」を定義 することが重要 解候補---評価値 例) 製品のデザイン---売上げ高 船の形状---推進抵抗 モデル化に関連 一般的な最適化のプロセス: 新しい 解候補の生成 解候補の評価 以前の解候補の評価値を参考にして、より有望な解候補を生成することで 解候補を改善していく 6 【最適化とは?】 1)連続関数最適化問題 例: 石油を汲み上げるための油井を掘る 油を含む地層が最も地上に近い部分を掘ると利益が最大になる 予算の都合で、試掘の回数が制限される → 限られた試掘回数(6回)の範囲内で、最も地上に近い油層を探索する 解候補4 解候補5 解候補6 解候補2 解候補3 解候補1 x 真の最適解 利益関数 f(x) 探索で発見 した最良解 実際のxはn次元空間上を探索 7 Excel上のマクロを利用してプログラムを組む Visual Basic for Applications (VBA)のテクニック ●Excelのマクロとは? 一連の操作を自動的に行う機能 例) セル(マス目)に数字を1から順番に埋めていく ●Excelのマクロでどんなプログラムが作れるのか? 任意のセルに書き込まれている数字や文字を読み込んで処理したり、 指定した番地のセルへ計算結果を書き込んだりできる 上達すれば、ポップアップウインドウを出して数値やメッセージの入力や表示をしたり、 図形描画・画像表示やファイル操作など、様々な操作が可能 8 マクロの作成 1) Excel のメニューバー中の[ツール(T)]の[マクロ(M)]から [VisualBasicEditor(V)]を選択 2) VisualBasicEditor上のメニューバー中の[挿入(I)]から [標準モジュール(M)]を選択 3) <コード>ウインドウにモジュールのコード(プログラム)が白紙状態で 表示されるので、ここへプログラムを書き込むべし! マクロの実行 1) Excel のメニューバー中の[ツール(T)]の[マクロ(M)]から [マクロ(M)]を選択 2) 作成したマクロを含めて使用可能なマクロ一覧が表示されるので、 選択して実行する 9 VBAプログラム言語の仕様 プロシージャABCD Sub ABCD() Dim x As Double x = 100 EFGH x End Sub 変数の宣言 他のプロシージャEFGHを 呼び出し プロシージャEFGH Sub EFGH( z ) MsgBox z End Sub 10 VBAプログラム言語の仕様 【データ型】 ・整数型 Integer -1, 0, 1, 2, …など ・浮動小数点型 double 0.12, -4.56 など ・論理(ブーリアン)型 boolean true またはfalse 宣言例) Dim loop As Integer 宣言例) Dim alpha As Double 宣言例) Dim b As boolean 【演算】 ・代入 a = 10 変数aに10を代入 a = a + 10 変数aの値に10を加えたものを、aに代入 ・2項演算 a = b + c a = b-c a=b*c a=b/c; それぞれ加算・減算・乗算・除算 条件を満たさなければfalseが代入される ・関係演算(演算結果がブーリアン型になる) b = (a = c) a と c が等しいときブーリアン型変数bにtrueが代入 b = (a < c) a < c のときブーリアン型変数bにtrueが代入 b = (a <= c) a が c の値以下のときブーリアン型変数bにtrueが代入 変数a,b,c全てブーリアン型変数のとき c = a And c AND演算子: aとc 両方ともtrueのとき変数cにtrueが代入 c = a Or c OR演算子: aとc どちらかがtrueのとき変数cにtrueが代入 【配列】 同じデータ型を持つ要素に番号をつけて扱う 宣言例) Dim x(10) As Double 11 使い方: y = x(1) x(3)=z w = x(loop) など VBAプログラム言語の仕様 【セルのデータを読み書きする】 Cells( 1, 2 ) = 100 x = Cells(3, 4) Cells( 1, 1 ).Clear 【関数を使う】 x = Rnd() x = Sqr(y) 1行目の2列目(1-B)のセルに数値100を書き込む 3行目の4列目(3-D)のセルの数字を変数 x へ代入 1行目の1列目(1-A)のセルの中身を消去して空に Double型の変数 x に0~1の乱数を代入 Double型の変数 x にyの平方根を代入 【ダイヤログを表示する】 MsgBox “メッセージダイアログ” などなど 詳細は解説書などを参照のこと 12 流れ制御文(1) 【連接】 b = a + 10 c=a+b b=a+10 上に書かれた文(ステートメント) から順番に実行される c=a+b 条件部には Boolean型の値がくる 【判断】 If ( a < b ) Then c=b Else c=a End If a<b false true c=b c=a 13 流れ制御文(2) 【多方向分岐】 a=0 if ( a = 0 ) Then b=b+2 ElseIf( a = 1 ) Then b=b+4 ElseIf( a = 3 ) Then b=b+1 Else b=0 End If true false b = b+2 a=1 true b=b+4 false a=3 true false b=b+1 b=0 14 流れ制御文(3) 【前判定反復】 Do While( a < 0 ) a=a+1 Loop a<0 false true a=a+1 【後判断反復】 Do a=a+1 Loop While( a < 10 ) a=a+1 a < 10 true false 15 流れ制御文(4) 【所定回数反復】 i = 1 (初期化) For i = 1 to 8 a=a+1 Next i <> 8 ? false true a=a+1 For文では自動的に この処理が行われる i = i+1 16 複数プロシージャ間で同じ変数を共有する:グローバル変数 例)シンプレックス法のモジュール Dim XL, XH, XS,XI, XG,XR,XE As Double Sub Optimization() GetXG Reflect Extend … End Sub Sub GetXG() XG=(XL+XH+XS+XI)/4 End Sub Sub Reflect() XR=2*XG-XH End Sub Sub Extend() XE=2*XR-XG End Sub モジュールの先頭 (プロシージャの前) で定義された変数は、 全プロシージャで共有される → グローバル変数 各プロシージャの中で 定義された変数は、 そのプロシージャ内だけで 通用する → ローカル変数 17