抄録

◎久我元士・髙橋良英（八戸工大）

巡回セールスマン問題（TSP）を解く枝組み立て交叉(EAX)の並列処理方式として，集中多段交叉（CMX）の有効性を実験により定量的に検証する。CMXは，島間の多様性を確保するために、島間で移民をしない遺伝的アルゴリズムの並列処理方式としている。そこでは，各島で生成した優れた個体を併合し，併合した個体群の中から個体の選択・遺伝子交叉を行ない，更に優れた個体を生成している。本論文では，CMXと島間で移民を行う島モデルによる並列処理方式(Family併合法)を集団の多様性制御の観点から定量的に比較評価した。集団の多様性を熱力学的遺伝アルゴリズム（TDGA)のエントロピーで定量的に測定した。そして,最適解探索率と集団の多様性の関係を小規模プログラム実験で明らかにしたので報告する。