平成  年  月  日

九州大学工学部地球環境工学科船舶海洋システム工学コース

平成  年度システム設計工学 定期試験問題
問題１
以下は  年代の日本車の主要目と燃費（  モード 走行）のデータである。
車名重量  ） 減速比 幅×高さ 出力 トルク 圧縮比

燃費 



クラウン
マーク 
カムリ
ソアラ
セド リックローレル
レパード
カペラ
ギャランΣ

  
 
         
ルーチェ ？

【問１１】表の最下段の車種「ルーチェ」の燃費不明なので 、表のデータより多重回帰によって（  点）推定したい。上記の表データの数字を用いて具体的な式を示し 、計算手順を説明せよ。
【 問１２】多重回帰による推定をより精度良く行うためには 、説明変数（ 特徴量）の取捨選択が必要であり、多重共線性に陥るような説明変数の組み合わせは避けるべきである。このとき、（  点）
多重共線性とは何か、説明せよ。

問題２次元平面におけるド ロネー図の生成方法の概略を述べよ。
（  点）

問題３点 ½    および ¾    を通り、点 ½ での接線方向ベクトルが ½    、点 ¾ での接線方向ベクトルが ¾    で与えられる  次多項式曲線の係数ベクトルを全て求めよ。

  ただし   ¼ 点間 ½ ¾ において媒介変数  は ½

¾

¿ 


 の値をとるものとする。
（  点）

問題４
パラメータベクトル  の値を探索してコスト関数   の最小化を行うための共役勾配法について、以下の説明を読んで問に答えよ：

 番目の方向転換をする点の座標ベクトル：  点 における勾配ベクトル：  点 からラインサーチを行う方向ベクトル： 

以上の記法を用いると、共役勾配法の手順は以下のとおりである：

 まず最初に勾配の反対方向へラインサーチを行う：¼  ¼  の次の点  ·½ はラインサーチで見つけた最小点： ·½    ! ただし  は係数
 次の点  ·½ での新しい探索方向  ·½ は、前の探索方向  と共役であるようにするため、点 ·½ の勾配と前の探索方向  を結合： ·½     ! ただし   は重み係数
   を  としてステップ２より繰り返す

【問４１】共役勾配法では重み係数   はどんな式で与えられるか？
いて示せ。
（  点）

勾配  および  ·½ を用【問４２】ラインサーチとは何か説明せよ。また代表的なラインサーチを挙げよ。
（  点）【問４３】共役勾配法は、有限要素法などにおいて大規模な連立１次方程式    （ただし は実対称正定値行列で表された係数行列、 は求める未知変数行列、 は係数行列）を解くのにも利用される。どのようにして共役勾配法により解くのか 、解法を説明せよ。またそれが効率良く解ける理由を説明せよ。
（  点）

問題５
組合せ最適化について、以下の問いに答えよ。
【問５１】ある最適化問題を解くアルゴ リズムの計算量

となる場合、この計算量

 "#が 、問題の大きさをで与えたときを $% &' 記法で表せ。
（  点）【問５２】組合せ最適化問題に対する強力な解法の一つである「分枝限定法」とは、どのようなアルゴ リズムか説明せよ。またその特徴を述べよ。
（  点）【問５３】解答用紙上のグラフはＡからＪの各ノード 間で移動が可能な場合のコストを表す。Ａから各ノード へ最小コストで移動する場合の Ａからの総コスト および 経路 をダ イクストラ法で計算し 、計算過程を解答用紙上の図へ記入せよ。経路は矢印で示せ。
（  点）問題６
パラメータベクトル  の値を探索してコスト関数   の最小化を行う最適化手法の１つに生物の進化の仕組みを模倣した遺伝的アルゴ リズムがある。これについて、以下の問いに答えよ。
【問６１】個体集団の世代交代方法として ()) がある。具体的な処理手順を説明せよ。
（  点）【問６２】遺伝的アルゴ リズムによる多目的最適化を行う場合、集団の個体同士の交叉オペレ ーション等で増加した個体数を一定に保つため、)* と呼ばれる淘汰戦略が +,$ らにより提案されている。この )* の処理手順の概要を説明せよ。説明には図などを用いても良い。
（  点）

問題７
パラメータベクトル  に依存し た非線形コスト関数   を、等式制約条件    ただし  のもとで最小化する場合、ラグランジュの未定乗数法による解法を用いるのが定石である。ラグランジュの未定乗数法について説明せよ。説明にはパラメータベクトル  、コスト関数   、等式制約条件    、未定乗数 などの記法を用いよ。
（  点）

問題８あるクレーンを単位時間毎に観測したところ「稼働」と「待機」の２状態が存在する。
●クレーンが「稼働」状態にあるとき、次のステップも「稼働」状態である確率は  、「待機」状態へ遷移する確率は  である。
●クレーンが「 待機」状態にあるとき、次のステップに「稼働」状態へ遷移する確率は  、「待機」
状態のままである確率は である。
このときクレーンの平均稼働率を計算せよ。
（  点）問題９
ある工場で製造されている製品は、前工程から始まり後工程をへて完成品となるが 、各工程においてたびたび不具合により作業のやり直しが発生する。
●「前工程」にいる場合、やり直し作業が発生して次のステップにおいても「前工程」にとど まる確率は  、次のステップで後工程へ移る確率は  である。
●「後工程」にいる場合、やり直し作業が発生して次のステップにおいても「後工程」にとど まる確率は  、次のステップで「 完成」する確率は  である。
●「完成」したら作業は終了で、その状態からは動かないものとする。
「後工程」の状態を  、「完成」状態を  とする。
●「前工程」の状態を  、
このとき「前工程」からスタートして「完成」に至るまでの平均ステップ数を計算せよ。
（  点）平成  年度システム設計工学定期試験 解答
問題１【問１１】（  点）全車種の説明変数（ 特徴量） 重量! 減速比! 幅×高さ! 出力! トルク! 圧縮比を以下の変数       で表し 、燃費  を以下の多重回帰によって説明する：
       

ただし        は回帰係数、 は確率変動（ 誤差）である。
 を求める。行と列を間違えないよう注意しここで、表のデータを用いて、回帰係数  ながら表のデータを行列に変換すると、以下のようになる：           
                                                と表す。ここで 、
 行列 の最初の列の要素は  とする
 行列 には推定しようとする車種（ここではルーチェ）のデータを含めない以上の点に注意する。このとき     とした場合の誤差ベクトル の平方和を最小にする
回帰係数  は以下の式で与えられる：    

ルーチェの説明変数 重量! 減速比! 幅×高さ! 出力! トルク! 圧縮比 の値を     
 を使って              へ代入し 、上で求めた回帰係数  --

 - - -

 -

 -

 

よりルーチェの燃費の推定値  を得る。この推定の式では誤差  の項は考えない。



【問１２】（  点）説明変数   について、任意の定数   を用いて関係式       に近い関係が成り立つとき、データは強い多重共線関係（ 多重共線性）があるという。このとき回帰係数ベクトルを求める逆行列計算が不安定になり、無意味な解が出やすいという問題がある。

問題２ド ロネー図の生成方法：全ての点の中から  点を選び 、その外接円を描く。このとき、円内にその 点以外の点が含まれなければ 、それらを  角形として結ぶ。この作業を全ての  点の組合せにつ（  点）いて行ったとき、最終的に得られる  角形分割はド ロネー分割になっている。

問題３
成分について      点 ½ を通る条件より
点 ¾ を通る条件より
      点 ½ の傾きについての条件より
    点 ¾ の傾きについての条件より
     !
      !
    



成分について       点 ½ を通る条件より
点 ¾ を通る条件より
       
点 ½ の傾きについての条件より
    点 ¾ の傾きについての条件より
      !

 


   !
    

以上の連立方程式を   についてそれぞれ解いてまとめると、
¼   ! ½   ! ¾   ! ¿    （  点）曲線の形状は図のようになる：

10.8

y0.6

0.4

0.2

000.2

0.4

0.60.81x問題４【問４１】（  点）.",/0,1&2,,3, 法： ·½ ·½  ·½     

または 4#"5 &2%$%,1, 法：
 



 ·½



   ·½
 

【問４２】（  点）
ラインサーチとは、 次元空間  において関数   の極小値または極大値となるパラメータ  の値を求めるアルゴ リズムである。代表的ラインサーチとして黄金分割法や逆放物線補間などがある。
【問４３】（  点）
連立一次方程式    の各行列を用いて以下の２次形式コスト関数   を考える：
    

このコスト関数   を最小化する  を共役勾配法で求める。このとき、最小点では     より    を満たすので 、求める連立１次方程式の解を得る。
共役勾配法は 次元の２次形式コスト関数に対して 回のラインサーチで効率良く最適化を得られるため、上記の方法で効率良く連立１次方程式の解を得ることができる。

問題５【問５１解答】
（  点）6% &' 表記では、

 定数係数を無視する
 問題の大きさ が大きくなった場合に影響する項だけを抽出する
  

よって【問５２】（  点）
分枝限定法は、解候補をツリー状の列挙図によって列挙・評価していく途中で、解の可能性の無い、あるいは可能性の低い枝を刈ることで探索空間を減らす探索方法である。この枝刈りを行う
際、解の可能性の無い枝だけを刈れば最適解を得ることができる。
（  点）解き方は第  回講義資料参照【問５３】

A210292C47D1011G413F1035E19I229B812

63316H622J

問題６【問６１】（  点）()) の処理手順： 個体集団より親個体 個をランダムに非復元抽出し 、この親個体群から交叉によって親個体よりも多い子個体群を生成したら 、親個体を捨て、子個体群の中から評価値の優れたものを 個選び 、もとの親個体群と入れ替えて個体集団へ戻す。
【問６２】（  点）)* の処理手順：

 まず個体集団の中からパレ ート集合を取り出し 、この集合を最高ランクの 257  とする。
この 257  の集合を取り除いた残りの集団でのパレート集合を取り出し 、この集合を 257とする。同様の手順により個体集団のランキングを行う。
 次世代に残す世代をランクの高い順に選択する。
 全ての個体を次世代に残せないランクについては 、そのランク内の各個体において隣接個体との距離から後述の「混雑度」を求め、この混雑度の値が小さい個体を間引く。
「混雑度」の計算方法：各ランク内の個体集合を目的関数別にソートし 、全個体それぞれの隣接する個体との距離を求め、全ての目的関数における距離の和をその個体の混雑度とする。また、ある目的関数において端にある個体は、その目的関数おける距離の最大値を与える。

問題７
まず以下のラグランジュ関数 を導入する：

  

この関数が 

 において極大値または極小値となるための必要条件は以下の式で与えられる：









   

この連立方程式を解いて求めた  の中に求める最小点のパラメータが含まれる。
（  点）

問題８「 稼働」を状態１、「待機」を状態２とすると、状態遷移確率行列は







ここで定常分布を    と表すと      

この連立方程式を解くと    !    となり、稼働率は「稼働」状態の割合である    である。
（  点）問題９（  点）状態遷移行列は以下のとおり： 
   

基本行列を  とすると、
   







よって吸収状態に陥るまでの平均ステップ 数は















状態  からスタートするので 、この行列の上の要素だけに注目する。よって答えは  ステップ。
【参考文献】［１］早川 毅 著：

回帰分析の基礎朝倉書店（  ．

本試験問題および 解答に疑問がある場合は， 月  日（ 金）正午までに，Ｗ２号館６階６３４号室の木村まで申し出ること。

8#91% 0  :% ;15

システム設計工学 解答用紙 学籍番号＿＿＿＿＿＿＿＿氏名＿＿＿＿＿＿＿＿＿＿＿
紙面が足りない場合は裏面も使用すること。

【問５３】

410A210222F
10CI

4B

98G

D33
612E

63HJ