SMSを使用せずにオンラインで遺伝的アルゴリズムを使用してルービックキューブを構築する

昼食を食べに行ったとき、同僚のデイブが私に声をかけました。「アレックス、プログラミングスキルを向上させたいですか？」 私はそれについて考えました。 興味深いオファーでしたが、私は拒否する傾向がありました。 いいでしょう冗談です 朝は、私が郵便局に着き、アリで誤って注文されたペニーチャイニーズキューブを手に入れたという事実から始まりました。 昼食までに組み立てマニュアルを勉強し、筋肉の記憶を更新しましたが、夕方には十分な演奏ができていることに気付きました。 キューブの未来は明確でした。週に1、2回、棚にほこりがたまります。考えを整理したり、気を散らしたりするために、たぶんそれを集めます。 機械的な組み立て速度の競争？ 非慈悲、それは巣箱をする方が良い...



いつものように、状況は自動化についての考えによって救われました。 短い研究の後、私は偵察を認識しました。 そもそも、神の数は20に相当する長い数が発見されています。確かに、これからの集会の仕事は単純化されていません。 考えられるすべてのキューブ構成に最短パスのグラフを使用することは、スポーティではなく、リソースの面で少しオーバーヘッドがあります。 神のアルゴリズムは、使用される特定の合理的な量のメモリを意味し、同時に最小限の変更を提供する義務があります。 したがって、そのようなアルゴリズムはまだありません。 従来のテンプレート手法と比較してアセンブリを大幅に高速化できるアルゴリズムは多数ありますが、既に誰かが（数学的に）敷設したパスを繰り返すのは退屈に思えました。 誰かが興味を持っているなら、ここに良い分析があります。 ここでのアイデアは、式を使用して下から上に階層化されたアセンブリにあります。 フォーミュラは、そのようなターゲットを絞った修正、およびそのようなセカンダリ修正をもたらす一連のキューブ修正です。 したがって、担保の変更は、ほとんどの場合、まだ収集されていないレイヤーに当てはまります。 テンプレートメソッドは、テンプレートの詳細レベルが異なります。 あらゆる種類のスピードキューブは、多数の特別なケースについて考えられるすべてのパターンを知っているため、競技の各修正から0.1秒余分にプレイすることができます。 他に何を人生に費やすことができるかの例。



だから、私は次第に自分のための仕事を作りました。 その結果、次のように定式化されます。 最短のリアルタイムで、ルービックキューブのソルバーを記述する必要があります。



キューブについて何を知っていますか？ その状態の数は

（8！×3 ^ 7）×（12！×2 ^ 11）/ 2 = 43252003274274489856 000

。

最短パスのグラフの使用に制限を課しているのはこの数値です。 彼のルールについて何を知っていますか？ 各特定の要素（側面または角）がその場所に正確に立つ必要があるという事実。 正確な場所は何ですか？ サイド要素の場合、これは両方の色と中央要素の色の対応、コーナー要素の場合、3つの中央要素とこのコーナー要素の3色の対応です。







したがって、いつでも、「この要素はその位置にあるのか？」という質問に簡単に答えることができます。 私たちが知っている2番目の側面は、Cubeを複数の層に組み立てることができ、各層が徐々に組み立てられることです。 そして、それは... pa-para-param！ 勾配ヒューリスティックが必要です。 実装方法を選択するだけです。 私は代数的方法を考慮しませんでした、なぜなら 私は、同様のクラスの問題に簡単に一般化できる解決策を求めていました。 （たとえば、最大11 * 11 * 11までの出来事を一般化することはそれほど難しくありません。）別のオプションがありました。Googleの「ルービックキューブアセンブリ」の記事を自動化するだけで、マスクマスクの詳細と公式を打ち込むことができました。 しかし、明らかな理由で、憧れ以外に、このオプションは何ももたらしませんでした。



バストがありました。 可能な限りの数の状態にもかかわらず、列挙は最も単純な解決策のように思えました。 実装の詳細を確認するために残った。 直感は、可能なオプションの特定の競争環境が必要になると私に言ったので、提示されたオプションから次のビルドレベルへの移行を見つけることはより速くなるでしょう。 一般に、遺伝的アルゴリズムのバリアントはそれ自体で支配的になり始めました。



ランタイムとして通常の最新のブラウザーを選択することにしました。 このことは、迅速な実装の要件を完全に満たしました。 私はその瞬間にベラルーシでガチョウを放牧していた友人とそのアイデアを共有しました。 ディマは提案を取り上げ、私たちは努力を並行して組み合わせる方法を検討し始めました。 Collabedit.comはすぐに見つかり、同時に複数の人にJavaScriptコードを書くことができました。 包括的なホスティングにhtmlを配置しました

<script src = " collabedit.com/download?id=svxve "> </ script>

<script src = " collabedit.com/download?id=s8xkv "> </ script>

そして始めました。 物理オブジェクトの記述としてキューブを保存することは、9つの要素の配列で構成される個々の6つのプレーンを保存して束ねるよりも、無意味ではるかに複雑なプロセスのように思えました。 UIを記述してキューブをレンダリングするために座って、Dimaはキューブオブジェクトとその変更を説明するために座った。 キューブ上で一連のアクションを完全に実行するには、3つの操作を実行できる必要があります。

1.左への立方体の回転

2.キューブを上に回転させます

3.前頭面の時計回りの回転



声明を証明することは意味がないと思う、それは非常に直感的です。



たとえば、立方体を上向きに回転させる場合、4つの平面の配列を周期的に交換し、左側と右側をそれぞれ反時計回りと時計回りに回転させ、水平軸に沿って背面を反映させる必要があります。 翌朝、私は最後の事実を理解するためにほぼ2時間を殺し、仮想キューブと実際のキューブを回転させた後、対称性に違いが生じました。 Kubikは、標準の数式表記（右、左、上、 D自分、前）からのコマンドを、.modify（シンボル）メソッドを介してサポートすることと、アポストロフィを使用したアンチアワー修正をサポートすることを学びました。 次に、特定のキューブで数式全体を実行できるようにするrunSequence関数を作成しました。 通訳者の準備の一部はほぼ完了しました。 最後の仕上げとして、新しいランダムキューブシャッフル式を導出してシャッフル関数を作成しました。念のため、インタープリターと実際のキューブの結果を確認しました。 これですべて、ルーチン部分は終了しました。

色の区別がないキューバの社会には目的がありません。

思った。 キューバ人口の各メンバー、それぞれ小さなキュービックは、彼が人としてハイヤーキューバにどれだけ近いかを表さなければなりません。 そうでなければ、この社会的グループは明らかに混乱と修正の過剰に行き詰まります。 まず第一に、フィットネス関数の説明のために座った。 各プレーンの同一色の数を数え、正方形に直立させて追加したいだけなのは明らかでした-必要ですが、できません。 そうでない場合、キューブの人口は、最も近いローカル最大値から選択されることはありません。 希望の光線はより狭く焦点を合わせられるべきです。 層の古典的なアセンブリ方法に従って機能を説明しました。 さらに、次の各レイヤー、および現在のレイヤーの各次の要素は、フィットネスの顕著な増加をもたらし、それにより、より適応したCubobodsがすぐに人口を支配するようになりました。

関数calcTargetStickers（キューブ、サイド、セル）{
     var target = cube.get（side、4）;
    セル=セル||  [0、1、2、3、4、5、6、7、8];
     var count = 0;
     for（i = 0; i <cells.length; i ++）{
         count + = cube.get（side、cells [i]）== target？  1-0;
     }
    戻りカウント;
 }

 ...
         var crossCoincidence = 0;
         / * [side1、cell_side1、front_cell] * /
         $ .map（[[[1、5、3]、[0、7、1]、[3、3、5]、[4、1、7]]、function（el、i）{
             var p = calcTargetStickers（cube、el [0]、[el [1]]）;
             if（p && calcTargetStickers（cube、2、[el [2]]））{
                 crossCoincidence ++;
             }
         }）;        
        ポイント+ = crossCoincidence * crossCoincidence * 50;
        
         var angleCoincidence = 0;
         / * [side1、cell_side1、side2、cell_side2、front_cell] * /
         if（crossCoincidence == 4）
         $ .map（[[[1、2、0、6、0]、[0、8、3、0、2]、[3、6、4、2、8]、[4、0、1、8、 6]]、関数（el、i）{
             if（calcTargetStickers（cube、el [0]、[el [1]]）&& calcTargetStickers（cube、el [2]、[el [3]]）&& calcTargetStickers（cube、2、[el [4]]）） {
                角度一致++;
             }
         }）;
        ポイント+ =角度一致*角度一致* 100;        
       
        
         var layer2Coincidence = 0;
         / * [side1、cell_side1、side2、cell_side2] * /
         if（anglesCoincidence == 4 && crossCoincidence == 4）
         $ .map（[[[1、1、0、3]、[0、5、3、1]、[3、7、4、5]、[4、3、1、7]]、function（el、 i）{
             if（calcTargetStickers（cube、el [0]、[el [1]]）&& calcTargetStickers（cube、el [2]、[el [3]]））{
                 layer2Coincidence ++;
             }
         }）;
        ポイント+ = layer2Coincidence * layer2Coincidence * 200;
        
        
         var layer3Coincidence = 0;
         / * [side1、cell_side1] * /
         if（layer2Coincidence == 4）
         $ .map（[[[1、3]、[0、1]、[3、5]、[4、7]]、function（el、i）{
             if（calcTargetStickers（cube、el [0]、[el [1]]））{
                 layer3Coincidence ++;
             }
         }）;
        ポイント+ = layer3Coincidence * layer3Coincidence * 300;
        
        
          var layer3Angles = 0;
         / * [side1、cell_side1、side2、cell_side2] * /
         if（layer3Coincidence == 4）
         $ .map（[[[1、0、0、0]、[0、2、3、2]、[3、8、4、8]、[4、6、1、6]]、function（el、 i）{
             if（calcTargetStickers（cube、el [0]、[el [1]]）&& calcTargetStickers（cube、el [2]、[el [3]]））{
                 layer3Angles ++;
             }
         }）;
        ポイント+ = layer3Angles * layer3Angles * 400;
         if（layer3Angles == 4）
            解決済み= true; 

各レベルには、これらの要素が所定の位置にあるかどうかに関係なく、側面または角度の4つの要素のチェックが含まれます。 4つの要素がすべて揃ったら、次のレベルに進むことができます。 これにより、母集団全体がスムーズに分離されます。



次に、遺伝的アルゴリズム自体が来ていました。 明らかに、ゲノムはCubeの特定のテンプレート変更です。 ゲノム-現在の状態に至った一連の変更全体。 キューブを横断した結果は何ですか？ 何も、彼らはすべて同性であり、出芽によって増加します。 進化の各ラウンドでは、既存のゲノムに遺伝子を追加することにより、すべてのゲノムの突然変異が発生します。 突然変異のもう1つのパラメーターはgeneMaxAppendCount値です。これは、次の突然変異中に追加される遺伝子の最大可能数です。 これは、キューブが一度に生成できる複雑な修正の量を規制する重要な数値です。 突然変異後、キューバはその適合性と見なされ、他のすべてのキューブと見なされます。 次に、病院の平均気温が考慮され、それに基づいて、特定のキューバの遺伝子型が人口にどの程度広く分布しているのかがわかります。

             var poluttionCount = Math.floor（（1）*（curFitness / averageTemperature-1））;
             poluttionCount * = poluttionCount;
             poluttionCount--;

さらに、このより強いキューブは、人口のいくつかのより弱いキューブを取り除き、進化の次のラウンドが始まります。







やった！ 動作します。

私が遭遇した主な問題は、アセンブリの最後の段階でした：2つのレベルが完全に組み立てられ、側壁が3番目のレベルにあり、コーナーさえその場所にあります-それはいくつかのコーナーを時計回りまたは反時計回りに回転させるだけです完全に完成したキューブ...しかし、このステージにはトリックが含まれています：コーナーの最終回転中、それらは常に0または2以上であり、キューブの下部の2つのレイヤーはすべて、上部のコーナーがすべて正しい位置に回転するまで破壊されます、さらにはすべての変更 水平面全3完全に組み立てられたキューブの層に沿って適切に整列することに加えて、一つの同じ平面が、最終的に用いて行わなければなりません。 そして、2歳の子供でさえ最新のアクションに直観的に対処するという事実にもかかわらず、私はフィットネス機能にいくつかの特別なケースを入れたくありませんでした。 進化アルゴリズムの手段は、最終手段の中間アセンブリに必要な穴をジャンプすることです。 このために、2つのことを行いました。



1.式のセットで、角度回転式を2xと4xの繰り返しで追加し、1つの遺伝子についてそれぞれ角度が反時計回りまたは時計回りに回転するようにしました。 これにより、1回の突然変異でほとんどの操作を実行する可能性が高まります。

2.値geneMaxAppendCountを入力し、フィットネス関数に含めました。 ポイント+ = cube.geneMaxAppendCount * 30; 。 実際、通常、キューバは最大値4または5から始まります。キューバを改善するのが簡単な最初の段階では、1つまたは2つの遺伝子で発生し、遺伝的遷移の短いキューブが人口を支配し始めます。 最後の段階では、そのような戦略はもはや失敗しません。より複雑な解決策を見つけようとしている個人を奨励する必要があります。そのため、geneMaxAppendCountの成長は母集団の終わりにはなりません。



これらの2つのトリックにより、平均300の操作（キューブ全体の回転を除く）でルービックキューブを解くことが保証されました。 ランダムな突然変異がキューブを一時的に破壊する穴を生き残るまで、最終段階でプロセスが遅れることがあります。 手動で、最も原始的なアルゴリズムに従って、私は平均170の操作でキューブを収集します。 しかし、これは網羅的アルゴリズムにとって非常に合理的な数値であり、さらに、人口は遺伝子型の長さを削減する必要があり、操作の必要数が大幅に削減されると思います。



次に、低レベルのソリューション。



考えられる遺伝子のように、プログラムはインターネット上のランダムな記事からコピーした式のセットを使用します。

 var formulHigh = [
     「U」、「D」、「<」、「^」、「>」、「v」、「<」、「^」、「>」、「v」、 
     「R 'D' R D」、  
     「U 'L' ULUFU 'F'」、「FRUR 'U' F '」、 
     「RUR 'URUU R'」、「URU 'L' UR 'U' L」、「U 'L' URU 'LU R'」、
     「R 'D' RDR 'D' R D」、「R 'D' RDR 'D' RDR 'D' RDR 'D' R D」
 ]; 

回転演算子と基本的な修正のみを使用して、問題を完全に完全に解決することは可能だと思いましたか？

  var formulLow = [
     「U」、「F」、「<」、「^」、「>」、「v」、「R」、「L」、「D」、
     「R 'D' RDR 'D' R D」、「R 'D' RDR 'D' RDR 'D' RDR 'D' R D」
 ]; 

角度の回転式は私には明白に必要であるように思われました、さもなければ、プレファイナルホールは合理的な期間にわたって克服できないように思われます。



私は次の問題に出くわしました。小さな穴でさえ、克服するのはすでに困難でした。 有用な修正への道順が複雑であるため、キューバは一時的な破壊の期間を生き延びるのが非常に困難でした。 より良い形を求めて行った大胆なキューブの愛顧をどうにかして確保する必要がありました。 私は、人口に対する譲許的融資政策を導入することにしました。 過去100ラウンドの進化で大幅なフィットネスの改善がなかった場合、ランダムキューブは30ラウンドの追加のフィットネスで無利子にクレジットされました。 しかし、彼らは全人口を上回って、それを犠牲にしてのみ増加するために彼らの信用を使うことができませんでした。 次の勝利の構成に到達する可能性を高めるために、彼らは現在、より高度なキューブから一時的な保護を受けています。



私の意見では、この考えは悪くはありませんが、どうやら設定を微調整しなかったため、効率が大幅に向上することはありませんでした。







おそらく、「クリーンな」ソリューションには、利用可能なオプションのスペースが劇的に拡大する大規模な人口が数桁必要です。 ところで、Chromeでは、コードは私のFFよりもはるかに高速に動作します。



要約できますか。 これは遺伝的アルゴリズムの最初のアプリケーションであり、幸いなことに成功しています。 目標は、最小の抵抗で達成されました。 私はあなたにバトンを渡します、ハブロフスクの居住者、多分あなたは人口を「きれいな」決定に導くことができます。



オンラインデモ： http : //misc.motogipsy.ru/cube/

コードでアーカイブ： http : //misc.motogipsy.ru/cube/cube.zip

collabeditを使用したコード： http ://misc.motogipsy.ru/cube/index_net.html