遺伝的アルゴリズムを使用して数独ソルバーを作成するタスクを引き受けました。
初期化: 指定された値を各染色体に格納し、各行が値 1 ～ 9 の有効な順列になるように値をランダムに生成します。
適合度 : 各行、列、正方形のグリッドの「場違い」な値の数を合計して決定されます。
フィットネス機能: 典型的なルーレット盤の選択
選択: ランダムですが、ルーレット ホイールを使用して加重します。
Crossover : 2 つの親からさまざまな行をランダムに選択して、1 つの子を作成します。(適切なミニグリッドを維持するために、2 つの親から一度に 3 つの行をランダムに選択するクロスオーバーも実装しました)。以下は、各クロスオーバー メソッドから 1 つずつ、2 つの子の例です。
Parent 1 row 1
Parent 2 row 2
Parent 1 row 3
Parent 2 row 4
Parent 1 row 5
Parent 2 row 6
Parent 2 row 7
Parent 1 row 8
Parent 1 row 9
Parent 1 row 1
Parent 1 row 2
Parent 1 row 3
Parent 2 row 4
Parent 2 row 5
Parent 2 row 6
Parent 1 row 7
Parent 1 row 8
Parent 1 row 9
突然変異: 最初は 2 つのランダムな場所で値を交換しただけでしたが、有効な順列であった行に重複が発生したため、実際にはアルゴリズムがさらに悪化しました。そこで、突然変異 (突然変異の可能性が 25% から 50% の範囲にある場合に最適に機能するように思われる) を変更して、行をランダムに選択し、その行の順序をランダム化しました (指定された値を正しい場所に残します)。 .
また、ランダムな行を選択し、行内の 2 つのランダムな (指定されていない) 位置を選択して交換するミューテーションも試しましたが、これによりパフォーマンスも大幅に低下しました。(2 つのランダムな場所の交換とは異なり、なぜこのミューテーションがパフォーマンスを大幅に低下させるのか理解できませんが、行全体をランダム化するミューテーションはパフォーマンスを向上させます)
私のアルゴリズムは、まだ難解なパズルを解いていません。多くの場合、(わずか 6 ～ 10 の競合の範囲で) 近づくことはありますが、決して解決策に到達することはできません (おそらく極小値を見つけて行き詰まっていると思われます)。
アルゴリズムを改善するために、母集団の大部分 (パフォーマンスが最も悪い染色体) を完全にランダム化されたボードに置き換える機能を追加しましたが、これによる影響は最小限に抑えられているようです。
私のアプローチの弱点は何ですか？どうすればパフォーマンスを向上させることができますか?
数独は、クロスオーバーとは対照的に、突然変異によるパフォーマンスの向上に役立つようです。