Shonwiler [34] は完全に独立したサブ集団から構成される孤立島型並 列GAモデル (IIP: independent and identical processing) をマルコフチェーンで解 析し, 単純GAと比較してプロセッサ台数以上の超線形高速化が達成できることを証明し た.
を
とする. 
は集団の全集合とする. 遺伝的アルゴリズム
を集団の状態遷移と考えると, 状態遷移行列 
を持つマルコフチェーンとみなせる.
最適個体を含む集団の集合を 
とすると, 
となる最初の時
刻 
の平均 
が最適解への平均到達時間である. は,
で与えられる. 
を P から 
であるすべての集団の行と列を
除いた行列とすると, 確率 
は
で与えられる. ここで, 
は要素がすべて 1 の列ベクトル, 
は初期集団となる確率のベクトルである.
Perron-Frobeniusの定理から は最大固有値 
を持つ.
は次の1世代で最適解が見つかる確率である. 
と 
を
に対する右および左固有ベクトルで, 各要素が正かつ和が1となる確率ベク
トルとする.
加速係数 s を 
と定義すると,
が成り立ち, 平均到達時間 が近似的に次のように計算できる.
完全に独立な単純GAを m 個のプロセッサで並列に動作させるとする. 
を各GAの最適解への平均到達時間とすると, 並列GAの
最適解への平均到達時間は
と定義される. 
は 
と等価なので, 確率 
は
で与えられ,
となる. 以上から, m 並列GAによる高速化を最適解への平均到達時間の比とすると,
のように計算できる.
したがって, s>0 の場合にはプロセッサ台数以上の高速化が望めることになる.
パスワード問題とは, M 種類のアルファベットが J 文字からなるパスワードを発見す
る問題で, 真のパスワードのみ適応度が1で他の文字列はすべて0となる関数である.
Mt.Sandia問題は, 
の整数 x に対し, 関数
の最大値を求める一種のだまし問題である.
これらの問題は十分に小さいので理論値が計算できる. プロセッサ数 m=1,2,4,8 の場 合の高速化比率を, 理論値と数値実験により得た値を比較してよく一致することを示し た. いずれも s>1 であり超線形 (superlinear) に高速化される.
また, サイズの大きな問題の例として逆フラクタル問題を取り上げ, LAN間接続した SPARC Workstation により超線形な高速化を確認した.