データ分析基礎知識

“分析力をコアとするデータソリューションカンパニー”
株式会社ALBERTが、データ分析にまつわる基礎知識をわかりやすく解説します。

最適化問題とは

最適化問題(Optimization Problem)とは、「与えられた制約条件の下で、ある目的関数を大または最小にする解を求めること」をいいます。最適化問題は、数理計画問題ともいわれるように、制約条件や目的関数などを、数理モデル(数式)にしなくては解けません。先に述べた乗り換え案内なども経路の最適化であり、最適化のアルゴリズムに従ってコンピュータが最適解を出すわけです。

ナップサック問題

数理計画分野では有名な「ナップサック問題(Knapsack problem)」を例に挙げて説明をしてみましょう。ナップサック問題とは、「何個かの価値や容量、重量などがわかっている品物があります。ナップサックには容量や強度の制限があり、それを超えないように品物を詰めなくてはなりません。ナップサックに入れた品物の価値の和が最大になるようにするにはどの品物を選べばよいでしょうか」という問題です。

泥棒が盗む最適なアイテム
図5.泥棒が盗む最適なアイテム

具体的には、泥棒に入った家に以下のようなものがあったとします。なるべくトータルの価値が大きくなるように盗みたいのですが、ナップサックには3,000しか入れられません。あなたなら、何をナップサックに入れますか?まずは、価値が一番高い金塊に目がいくと思います。しかし、金塊は重量が重いので、これを先に入れてしまうと、後に入れるものが制限されてしまいます。このように、価値が一番高いものから順に採用する方法を「どん欲法」といい、必ずしも最適化はされません。欲張りは結局は損をするということでしょうか。

表1.商品の価値と重量
商品の価値と重量

これを最適化問題として解いてみましょう。制約条件は重量の合計が3,000以下、変化させるのは採択の有無で、採用なら1、採用しなければ0です。この価値の合計を最大化する組み合わせを計算してみてください。組み合せは2の8乗=256通りあります。これほど単純なモデルでもこれだけの計算をしてみなくてはいけないので、とても大変です。

実際に最適化ツールを使って計算してみたものが以下の表です。ナップサックに3,000しか入らないときには、「置物」と「絵画を」盗むのがよいようです。しかし、3,200入るナップサックだったとすれば、置物も絵画も採用せず、「金塊」「指輪」「ネックレス」「現金」を盗むのが、価値の最大化になるわけです。

表2.重量制限と最適な組み合せ
重量制限と最適な組み合せ

このように、組み合せが多すぎて自分では計算できないときに、最適な組み合せを導出するのが最適化問題です。

食事の最適化

ダイエットをしている人も多いと思いますが、極端な食事制限はせず1日3食きちんと食べ、栄養バランスを取った上でカロリーコントロールをしなくてはいけないといわれます。もし以下のような食品があったとします。一般的な成人の1日の摂取エネルギーを1,800kcalとすると、栄養バランスを考慮したうえでこのエネルギーを摂るとしたら、以下の食品のどれを選べばよいでしょうか。

様々な食品
図6.様々な食品

これはまさに最適化問題です。栄養バランスという制約条件があるなかで、カロリーを1,800kcal以内で最大化するという問題です。栄養バランスの最適化に活用できるのが「四群点数法」 ※です。食品を栄養的な特徴で以下のような4つの食品群に分類し、80kcalを1点とする単位で表します。一日に必ず摂らなくてはいけない点数は、1〜3群は3点、4群は11点といわれています。合計20点になりますので、成人の場合は最低でも1,600kcalは必要になるというわけです。各食品群からまんべんなく食品を選び、摂取する事で、栄養バランスの良い食事を摂ることができます。

※四群点数法は、女子栄養大学の創立者・香川綾がバランスのよい食事法として考案した

四群点数法
図7.四群点数法

上記に挙げた食品のエネルギー量(kcal)と各群の点数を示したものが以下の表です。これらの中から、栄養バランスを摂りながら目標とするエネルギー量に最も近い食品の組合せを決めることを考えます。

表3.各メニューのエネルギー量と各栄養素の点数
各メニューのエネルギー量と各栄養素の点数

上記に挙げた食品のエネルギー量(kcal)と各群の点数を示したものが以下の表です。これらの中から、栄養バランスを摂りながら目標とするエネルギー量に最も近いメニューの組合せを決めることを考えます。性別、年代別にエネルギー量の目標が異なるので、それぞれの最適化問題を解いてみました。その結果が以下の通りです。

表4.性・年代別最適化の結果表
性・年代別最適化の結果表

すべて目標となるエネルギー量と各群の目標点数をクリアしていることがわかると思います。これらをまとめると以下のようになり、目標とするエネルギー量が少し異なるだけでも、食べる食品が大きく変わることが見てとれます。この程度の単純な最適化問題でも、自分で解こうと思うと非常に大変だと思いますが、最適化のソフトを用いることで瞬時に結果を出すことができます。

最適化した1日のメニュー
図8. 最適化した1日のメニュー
このページをシェアする

About

ALBERTについて