2017年度 知能情報学科 知能情報処理演習2
Cによる最適化プログラミング補足資料
担当 : D3,D4(月5限、6限),D1,D2(月7限,8限)
演習テキスト
C言語ソースコード
ナップサック問題
拡張ナップサック問題 問題を選んでチャレンジしてみよう
- 2つの制約条件がある場合 (テキスト 4.4.1 参照)
- 2つのナップサックがある場合 (テキスト 4.4.2 参照)
- 2種類の価値があり,それぞれの和をできるだけ大きくしたい場合 (テキスト 4.4.3 参照)
- 各荷物が2つずつある場合 (テキスト 4.4.4 参照)
レポートを書くにあたっての一般的な注意:
- 表紙の次に、目次を付ける。
- 各章には、適切な章題(章の題目、タイトル)を付ける。
- 図には図番号と図題(図題は図の下に)、表には表番号と表題(表題は表の上に)を付ける。
- 図の縦軸・横軸には、タイトルを付ける。
- 表は、各行・各列が何を表すのか、表中に明記する。
- 図や表は、何を表すためにそれを用いるのかをよく考えた上で、適切な形式(折れ線グラフが適当なのか、棒グラフで表すべきか等)を選ぶ。
- 実験で用いたパラメータ値などは、本文に明記する。
- 誤字は、極力なくす。
- 「です」「ます」文体は、用いない。
- レポート冊子は、左綴じに(左側に縦2箇所、あるいは、左上1箇所)。
確率的探索法の実験に対しての注意:
- 確率的手法であるから、1試行の実験結果のみでは、十分に信頼性のある結果、それに基づく考察とはならない。
- 「色々やってみたけど、これだけを見せます」といった記述だけでは、不明なので、実行した実験は具体的に示し、結果もできるだけ具体的に報告する。
- パラメータ依存性や、交叉方法による違いなどを考察するには、N=8の小規模な問題のみの結果では無理がある。極端なはなし、N=8なら全探索で最適解を十分短時間で求められるレベルの問題規模であり、これで探索手法の性能を議論するのは適当ではない。
- 得られた解が実行不能解ならば、最終的には採用できない。よって、ペナルティ法などで、一時的に実行不能解も許して探索する場合には、必ず、最終的な最良解が実行可能解であることを確認する必要がある。
- サンプルプログラム(のまま、変更を加えていない部分)は、印刷して提出するレポート中のソースリストには、特に全て含める必要はない。(ファイルで提出するプログラムファイルは、そのまま実行できる必要があるの で、全文含めること)