超大規模問題に対する遺伝的アルゴリズムの開発 Development of Genetic Algorithms for Large-Scale Optimization Problems

解くべき最適化問題（特に組合せ最適化問題）の規模が大きくなってくると，最適化に必要な計算時間も膨大なものとなってしまう．そこで，並列計算を用いて短時間で最適化を行うための並列計算法を開発する．例えば，200万都市規模の巡回セールスマン問題（有名なベンチマーク問題で，200万個の地球上の都市を最短経路で一周する経路を見つける）の既知最良解を更新するための並列遺伝的アルゴリズムを構築する．このような研究を通して，さまざまな問題に対して適用可能な並列遺伝的アルゴリズムの基礎的な枠組みを構築することを目指します．

    さらに，一部の問題では，解空間の次元数が数千から数万にも及ぶ場合があり，こうした高次元問題に対しても有効なメタヒューリスティクスの開発が求められます．

As the size of combinatorial optimization problems increases, the required computation time grows rapidly. This research focuses on developing parallel genetic algorithms to solve such large-scale problems efficiently using parallel computing. For example, we aim to construct a parallel genetic algorithm capable of improving the best-known solution to the 2-million-city Traveling Salesman Problem—a well-known benchmark involving the shortest route through 2 million cities on Earth. Through this work, we aim to establish a foundational framework for parallel genetic algorithms applicable to a wide range of large-scale problems.

In addition, some problems have extremely high-dimensional solution spaces, with thousands or even tens of thousands of dimensions. To address such challenges, it is necessary to develop metaheuristic algorithms specifically designed for high-dimensional optimization.

Reference:

1. Yang, Y., Li, H., Lei, Z., Yang, H., & Wang, J. (2025). A Nonlinear Dimensionality Reduction Search Improved Differential Evolution for large-scale optimization. Swarm and Evolutionary Computation, 92, 101832. https://doi.org/10.1016/j.swevo.2024.101832

2. 永田 裕一 :巡回セールスマン問題に対する最強遺伝的アルゴリズムの設計思想, 日本オペレーションズ・リサーチ学会 春季研究発表会&シンポジウム, 2023年3月.

3. 山越 幸太, 永田 裕一, 小野 功: TSPのためのGA-EAXにおける探索ステージ切換条件とマルチスタート戦略の提案, 計測自動制御学会論文集, Vol.52, No.4, 242-248, 2016年. (DOI: 10.9746/sicetr.52.242, CiNii: 1390282679485961088)

4. 永田 裕一 :可変長マルコフモデルに基づく巡回セールスマン問題に対する GA の多様性指標の提案, 進化計算学会 進化計算シンポジウム2016, 2016年12月.

5. 寺尾 圭一郎, 小野 典彦, 永田 裕一 :差分データを用いた巡回セールスマン問題のための GA-EAX の効率的並列化, 進化計算学会 進化計算シンポジウム2016, 2016年12月.  

6. 寺尾 圭一郎, 小野 典彦, 永田 裕一 :大規模巡回セールスマン問題に対する交叉EAXを用いた遺伝的アルゴリズムの並列化, 計測自動制御学会 システム・情報部門学術講演会2015, 2015年11月.    

7. 山越 幸太, 永田 裕一, 小野 功 :TSP のためのGA-EAX における探索ステージ切換条件に関する一検討, 計測自動制御学会 システム・情報部門学術講演会2014, 2014年11月.    

8. Kazuma Honda, Yuichi Nagata and Isao Ono: A Parallel Genetic Algorithm with Edge Assembly Crossover for 100,000-City Scale TSPs, Proceedings of the 2013 Congress on Evolutionary Computation (CEC 2013), 1278-1285, Jun. 2013.

9. 永田 裕一 : 局所的な交叉EAXを用いたGAの高速化とTSPへの適用, 人工知能学会論文誌, Vol.22, No.5, 524-552, 2007年. (DOI: 10.1527/tjsai.22.542, CiNii: 1390001205108326656)

10. 永田 裕一 : 局所的多様性の損失を考慮した評価関数を用いたGAのTSPへの適用, 人工知能学会論文誌, Vol.21, No.2, 195-204, 2006年. (DOI: 10.1527/tjsai.21.195, CiNii: 1390282680083497216, Elsevier: Scopus)

11. 永田 裕一, 小林 重信 : 巡回セールスマン問題に対する交叉:枝組み立て交叉の提案と評価, 人工知能学会誌(-2013), Vol.14, No.5, 848-859, 1999年.

Code:

1. https://github.com/louiseklocky/NDRDE