組合せ最適化問題では, 初期の頃は巡回セールスマン問題(TSP: Traveling Salesman Problem) を対象とした研究が多かったが, 特殊なコーディングと遺伝オペレータを必 要とするために, 最近では0/1ビットで表現できる. グラフ分割問題(GPP: Graph Partitioning Problem)や二次割当問題(QAP: Quadratic Assignment Problem), 0/1ナ ップザック問題(zero-one knapsack problem)が使われることが多い.
グラフ分割問題はグラフを等しい頂点数を持つ二つのグラフに最小のカットで分割する 問題であり, 頂点数のビット列でコーディングし, 0/1がそれぞれどちらの部分グラフ に属するかを表す. 適応度関数には, カット数に部分グラフの頂点数の差の二乗のペナ ルティを加えた,
の式を使用する. 分割対象にはマルチレベルグラフ(同一の強連結グラフが二つ存在 するので最適の適応度はゼロであるようなグラフ)と呼ばれる図5.6のグラフが良く使われる.
図5.6 64頂点のマルチレベルグラフの例
二次割当問題はLSIの回路配置等で現れる問題で TSP を包含する問題表現である.
行列 A, B が与えられたとき, 順列を表す 
を
と表す. QAP は次式を最小化する を求める問題として定義される.
行列 A は構造行列またはコスト行列と呼ばれ, 行列 B は要素間の距離を表す.