文書 / 歴史

歴史的:論文(2026年)

野球シーズン計画における遺伝的プログラミング。実現可能性と最適化問題。コンピュータ工学論文、ITAM。指導教員:アンドレス・ゴメス・デ・シルバ・ガルサ博士。2026年7月23日承認。

問題点

MLBは約180日間で30チームで2,430試合をスケジュールしています。各チームは都市間で移動し、その距離はチームごとに大きく異なります。2016年にはシアトルが76,683km、シカゴ・カブスが39,015kmを移動しました。

総距離が最も短いスケジュールを見つけることはトーナメント交通問題(PTT)と呼ばれます。これはNP難易度の問題で、可能なスケジュールの数が非常に速く増えてすべてを確認できないのです。

方法

遺伝子プログラミング(PG)は、1992年にジョン・コザによって提案され、進化を模倣します。それは解決策の集団を作り、最良のものを取り出し、それらを組み合わせて新しい世代を形成します。

表現: 各カレンダーは木構造です。そのノードは crear_juego (日付、ホームチーム、アウェイチーム)や obtener_calendarioなどの操作で、2つの試合リストに加わります。
生存可能性(C1): 各チームはトーナメントで求められる正確な試合数をプレイしなければなりません。0の値はスケジュールが有効であることを示します。
距離(C2): 各スタジアムの座標にハヴェルサインの式で計算された移送の合計。
ソフトウェア: 3つのモジュール(プランナー、計算機、遺伝子プログラム)で、DEAPライブラリを用い、Djangoのウェブアプリケーションとは別です。

結果

30チーム、1チーム163試合、5試合シリーズ、20世代を試してみてください。

ランダムサーチと遺伝的プログラミングの比較
方法	おそらく。渡りの	おそらく。突然変異の	実現可能性(C1)	総距離(C2)	時間
ランダムサーチ	0.0	0.0	0(有効)	2,663,470.70 km 短距離	200.25 s
遺伝的プログラミング	0.8	0.2	0(有効)	3,182,738.33 km	3,337.81 s

主な発見

遺伝子プログラミングはランダム検索を上回ることはありませんでした。 19.5%長く距離を得て、ほぼ17倍の時間がかかりました。最良のカレンダーは常にランダムな初期世代から得られます。

論文は以下の原因を特定しました。

一般的なクロスオーバーや突然変異演算子は問題を知らずにノードを変えます。ほとんどの場合、無効なカレンダーを生成します。
適応度関数は距離よりも生存可能性にはるかに大きな重みを与えます。無効な子は常に有効な親に負けます。
アルゴリズムはすぐに局所最適解に収束し、初期解のみを保持しました。

否定の結果も結果です。これは、表現や演算子がアルゴリズムと同じくらい重要であることを示しています。

今後の活動

論文は文脈演算子を提案しました:ノードをランダムに変える代わりに、カレンダーを有効に保つ一連のやブロック全体を交換するというものです。また、多くの構成を同時に探求するために量子コンピューティングにも言及しました。

論文の後に何が行われたか見てみましょう

タイムライン

2026年5月 · 論文文書の公式版です。
2026年7月23日 · メキシコシティでの防衛。論文承認。

資料と引用

論文文書、公式以前のバージョン (PDF, 4.8 MB, スペイン語で)
弁護側の提示 (PDF, 2.9 MB, スペイン語で)

APA形式での引用:

Brenes Valencia, L. P. (2026). Programación genética en la planificación de temporadas de béisbol (Tesis de Ingeniería en Computación). Instituto Tecnológico Autónomo de México (ITAM), Ciudad de México, México.