Blog「株式会社LIFULL(ライフル)」の社員によるブログです。2017-03-02班分けAIこんにちは、MAM開発グループの椎橋です。MAMとはマーケティングオートメーションの略で、マーケティングに関する機械学習アルゴリズムを作ったり、データ分析をして改善につなげたりしています。今回は社内制度のクリエイターの日を2日間利用して、社員旅行の班分けの最適化モデルを作りました。以前はこの制度を利用してサーバ・ミドルウェアの勉強をしました。nextdeveloper.hatenablog.com弊社の社員旅行は多くの社員が参加し、最高に盛り上がる大イベントです。そのスケジュールの中にアクティビティと呼ばれるイベントがあります。これは班に分かれて観光やスポーツなどを楽しむというもので、私は昨年そば打ちを体験しました。複数あるアクティビティのうち参加できるのは一つだけな上に、人数の上限が設定されているために希望したアクティビティに参加できるかどうかは分かりません。昨年は社員旅行委員が抽選と手動調整によって班分けを行いましたが、数時間かかったらしいので最適化モデルを作ることにしました。データ抽出まずは、計算に用いるデータを準備します。フォームで社員の希望調査を行い、集計結果を以下のように変換します。-1性別カラムは男性なら1,女性なら-1を取るようにし、各アクティビティの希望順位をgroupカラムに記します。希望していないアクティビティには-1を割り当てました。次にこの問題を数式に変換します。定数まずは定数を以下のように定めます。$s_i$$h_{ij}$は希望順位から算出した定数で、算出方法は割愛します。添え字集合を以下のように定義しておきます。次に、問題を解くための変数を以下のように設定します。対して定めることで班分けを一意に決定できます。モデリング上記を用いてモデリングします。$$という式を作れます。これは以下のような行列形式で考えるとわかりやすいです。なり、それを上記の式で表しています。対して制約が設定されています。ついての制約で行列形式のデータを列で見るとわかりやすいです。上限人数以下になるようにします。目的は希望度を最大化しつつ班の男女の人数の比率をできるだけ等しくすることで、以下のようにします。I}{s_ix_{ij}}}{g_j}\right|}\right)$$第一項は希望度の総和、第二項は疑似男女比差を表しています。以下の制約を加えれば実現できます。以上をまとめますと、以下のモデルで書けました。設計ができたので、Pythonで実装します。実数変数(Continuous)にしていることです。整数になることが保証されているためです。組み合わせ問題は変数を増やすと爆発的に計算量が増加しますが、この緩和を適用できると変数が増えても比較的容易に最適解を求められます。最後に最適化と抽選式で結果を比較します。抽選式は、希望人数を加えても班の上限に達しないならば抽選せずに確定させ、そうでなければ抽選によって班に加えるメンバーを選出する決め方です。抽選式では希望外の班に割り当てられた社員がいるので、この後手動で調整する必要があります。一方で最適化の結果ではその現象は起きていません。16秒この規模になると最適化の効果が顕著になりますね。まとめクリエイターの日を利用して社員旅行の班分け最適化モデルを作りました。整数条件を不要としたモデルにすることで変数が増えても比較的容易に計算できるのが特徴でした。エンジニア支援制度が充実したネクストでは鋭意エンジニア採用中です!新卒・中途問わず、ご興味を持たれた方は是非下記ページを御覧ください。L...2019-12-16LIFULLが主要サービスの(ほぼ)全てをKubernetesに移行するまで技術開発部の相原です。ServiceTopol...2018-12-10GoogleAppsScript(GAS)でGoogleフォームを魔改造したこんにちは。(@ki...2018-06-21RubyKaigi2018の聴講した講演を三行でまとめてみました初めまして。流通事業部UXU開発2Gの吉田です。株式会社LIFULL「LIFULL」とは、世界中の人々の人生やくらし(LIFE)を満たす(FULL)企業へと成長していきたいという想いをこめた造語です。LIFULLはてなブログをはじめよう!nextdeveloperさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。