シフトスケジュール問題のＧＡによる解法

公開日: 2021-06-18

投稿者：
お気に入り件数：0
閲覧数：251

[ PDFファイル ]

2020seedsP4.pdf

キーワード：ＧＡ、組み合わせ最適化、進化的計算
研究・地域連携活動の背景・目的
「24時間体制で業務に当たらなければならない職場における勤務シフトスケジューリング
作成」や「都市部の電車のダイヤグラム作成」といった「組み合わせ最適化問題」と呼ば
れている問題は、解くのが困難な「NP困難性を有する問題」として知られています。
研究・地域連携活動の概要紹介
●ジェネティックアルゴリズムによる組み合わせ最適化問題の解法の研究
ジェネティックアルゴリズムとは「遺伝子型」と「表現型」という２つの属性を持つ個
体を「解候補」として多数用意し、それらを「遺伝子の交差」「遺伝子の突然変異」と
いった操作を繰り返し行いながら、設定した環境に最も適する個体を見出す、という
「最適解探索手法」です。実際にこれが適用される問題としては「スケジューリング問
題」「配送計画問題」など、我々のごく身近で発生する問題があります。このような問
題は一般に「組み合わせ最適化問題」と呼ばれますが、これは通常の解探索手法で用い
られる「初期解を修正しながら、より評価値の高い方向に解を移動させる」という手法
では解けないのが一般的です。ジェネティックアルゴリズムでは問題に合わせた「遺伝
子型」をまず乱数を用いて多数生成し、「多点探索」の手法で最適解を求めます。個々
の問題に対して、どのような「遺伝子型」そして「交差」及び「突然変異」のやり方を
させれば良いのかを研究しています。
●技術系ベンチャー企業による「ディスラクティブ・イノベーション」の研究
現在技術者によって設立されたさまざまな企業が「技術系ベンチャー企業」として活動
しているが、残念ながら日本においてはその成功事例は非常に少ないのが現状である。
一方海外に目をやるとアメリカのＧＡＦＡを始めとして、単に成功しているだけでなく、
世界経済を牽引する存在まで昇りつめる事例が多くある。このような企業は単にある技
術を「発明」しているだけでなく、その技術によって「既存の価値体系（世界）が破壊さ
れている（ディスラクティブ・イノベーション）」のが特徴である。どのような要素（仕
組み、方法、システム　etc.）がそれを成し遂げさせているかを研究しています。
期待される効果などアピールポイント
ＧＡは「組み合わせ最適化問題」を効果的に解く手法として知られていまが、応用に際し
ては「遺伝子」構造の決定や、「遺伝子」の「交差」「突然変異」に関して、個々の問題
の特性に応じた工夫が必要とされます。そういった工夫の部分を「アルゴリズム」として
プログラムに組み込み、具体的な問題に対応するソフトウェアを開発することを目指して
います。

カテゴリ　：　シーズ（得意な技術・サービス等）

対象エリア：　選択なし

有効期限　：　無期限

（ご注意）

◯ コメントは公開されます。秘密情報の取り扱いには十分お気をつけください。
◯ 非公開で投稿者と連絡を取るには、右の［個別メッセージ］機能を利用して下さい。

個別メッセージ

ニーズ・シーズ投稿者と個別のメッセージ交換を行えます。

ログインすれば投稿者と個別メッセージ（非公開）のやりとりができます。

企業や地域自治体・公共機関、大学等の産学官連携による「ニーズ・シーズのマッチングプラットフォーム KuRiPS」

シフトスケジュール問題のＧＡによる解法

（ご注意）

個別メッセージ

ニーズ・シーズ投稿者と個別のメッセージ交換を行えます。

関連するニーズ・シーズ

理論物理学、データサイエンス

ハイブリッドロケットエンジンの研究開発

航空機関連の研究及び地域連携活動

企業や地域自治体・公共機関、大学等の産学官連携による「ニーズ・シーズのマッチングプラットフォーム KuRiPS」

シフトスケジュール問題のＧＡによる解法

（ご注意）

個別メッセージ ニーズ・シーズ投稿者と個別のメッセージ交換を行えます。

関連するニーズ・シーズ

理論物理学、データサイエンス

ハイブリッドロケットエンジンの研究開発

航空機関連の研究及び地域連携活動

個別メッセージ

ニーズ・シーズ投稿者と個別のメッセージ交換を行えます。