資料ダウンロード|分野別ソリューション
ナップサック問題への適用例
代表的なナップサック問題の場合、各アイテムをナップサックに詰める（=1）か/詰めない(=0)かを変数とし、アイテムの数をnとすると、全組み合わせは2^n となります。アイテムが増加するに従って指数的に組み合わせの数が増加し、問題を困難にします。
本資料では、車載用の回路である過電圧保護回路の全素子（電源を除く）を対象に、オープン/ショート時の解析を「Optimus」の自動化機能で実施し、工数削減の可能性を評価した事例をご紹介します。
ナップサック問題
それぞれ異なる重さと利得を持つ複数のアイテムを、最大容量が決まっているナップサックに入れる問題です。ナップサックに入れるアイテムの総重量がナップサックの最大容量内であるという制約条件を満たしながら、アイテムの総利得が最大となるようなアイテムの組合せを求めます。最適解は、アイテム３、アイテム４、アイテム５、アイテム６、アイテム８を選択した場合で、その際の総利得は９＋４＋９＋７＋５＝３４、総重量は５＋１＋７＋３＋３＝１９になります。
定式化
前述の問題を左のように定式化します。
Optimusの解析シーケンス
まず、設計変数を定義します（アイテム1〜アイテム8共通）。タイプは整数で、下限は０、上限は１です。次に、出力値グループ「各アイテムの利得と重量算出」を定義します（グループ1〜グループ8共通）。たとえば、グループ1を設定する場合、利得の名前を「利得1」、関数を「7＊$アイテム1$」とし、重量の名前を「重量1」、関数を「10＊$アイテム1$」とします。 最後に、出力値グループ「全アイテムの総利得と総重量」を定義します。利得の名前を「総利得」、関数を「$利得1$＋$利得2$＋・・・＋$利得8$」とし、重量の名前を「総重量」、関数を「$重量1$＋ $重量2$＋・・・＋ $重量8$」とします。
Optimusの最適解
アルゴリズムSelf-Adaptive Evolutionの使用により、計算回数69回（全組み合わせは256通り）で最適解を探索できました。オプションは、以下2点を除きデフォルト設定としました。
- 乱数発生パターン：「1」内部的に使用する乱数表の番号
- 最大反復回数：「6」本問題の全組み合わせは2^8＝256のため、これを超えない反復回数としました。
全組み合わせ256通りと比較すると、少ない計算量で最適解を得ることができました。
＊続きはダウンロードしてお読みください。