この投稿では、チームが計画した方法で新しい魔術師を作成するために、Yandexのほぼすべてで解決しなければならなかった色理論への没入を必要とする興味深いアルゴリズム上の問題についてお話したいと思います。
花の魔術師は、2008年にYandexの検索結果に登場しました。 それが考案されたとき、私たちはそれが人に怖がっているニンフの太ももの色を明らかにするおもちゃになるだけでなく、式によって色を知り、色による表記を学び、ある色空間から別の色空間にコードを翻訳するのに役立つことを望んでいました。 ソーサラーの古いバージョンは、ドラム、カラーピッカー、入力、および234の名前付きカラーで構成されていました。
最初は、更新された引き渡しで数週間でそれを復活させることが可能であるように思われました。 このタスクの最初の部分は、新しいスタイルの検索結果ページに魔術師の外観を取り入れることでした。
標準の要素では組み立てられないことがすぐに明らかになりました。 さらに、古いページの検索結果用に描かれた魔術師は新しいバージョンに適合せず、デザイナーによると、3次元のドラムを作ることはもはや流行ではありません。 したがって、フラットなデザインが生まれました。 新しいバージョンでサポートしたい主なことは、以前はなかったが、名前のないカスタムカラーを表示することでした。 古いバージョンでは、魔術師はすべての問い合わせに最も近い名前の付いた色で答え、人々を迷わせる可能性がありました。 現在、任意の色が最も近い名前の隣人に囲まれているか、異なる明るさで表示されます。
主な検索デザイナーkovchiyは、個人アーカイブから数千の名前付きの花を含むファイルをチームに提示しました。 その結果、1010色があり、その名前と座標は標準の色リスト（HTML色名、X11色名など）で部分的に固定され、部分的に独立して発明されています。 そして、彼らを魔術師に入れる方法を考え始めたとき、最も難しいことが始まりました。 それに取り組んだチームは、Yandex社内ソーシャルネットワークで花を最高に選別するためのコンテストを手配することさえ決定しました。 そこで問題について学び、解決策を提案しましたが、最終的に本番環境に入りました。 しかし、まず最初に。
そのため、次のように、ドラム上の色のセットを（線またはリング上に）配置することがタスクでした。
- 隣接する色の間の遷移は滑らかで、おそらくコントラストが低いため、隣接する色は似ていました。
- 近い色をグループ化して、類似した色を並べて配置しました。
順序が指定されていない元の色のセットのように見えた
しかし、すでにこれらの2つの基準は次のとおりです。
- 冗長 -類似色のグループ化はコントラストを高め、コントラストの低下はグループを分割します。
- 不十分 -これらの基準によれば、それらが等しい場合、多くの異なる決定を可能にします。いくつかは、全体としての場所の目に見える有意性など、定義されていない品質で目立っています。
- 未定義 -希望するソリューションがどのように見えるかを示しますが、どのソリューションが優れているかを区別することはできません。
その結果、判断を比較する際の審査員と参加者の両方は、基準の順守よりも味覚に依存していました。
手動で、アルゴリズムの助けがなければ、さらに少ない色の美しい順序を見つけるだけでなく、見つかった人を改善することもできません。 特定の場所がドラムの別の部分で同じ色を持っているように見える場合、それを再配置するとシャープなコントラストが明らかになります。色の知覚は背景に依存し、移動した色の新しい隣人は、近くの花の背景にとても似ているように見えますが、移動後に突然劇的に異なる色合いを示します。
アルゴリズムで色配置を選択する場合、問題の最適化問題を確認するのは自然であり、それを解決するための最初のステップは最適化目標を選択することです-これまたはその色配置がどれだけ良いか悪いかを伝える関数です。
この関数を作成するには、 ΔEと呼ばれる補助関数が必要です。これは、2つの色の違いまたは類似度に数値を設定します。 つまり、近い色の1つのペアの差が別のペアの差と等しい場合にのみ、各ペアの色が互いに等間隔にあるように見えるはずです。 ΔEは色彩科学の基本的な問題の1つですが、特定のフレームワーク内では完全に解決されています。 幸いなことに、色の違いの関数は色の科学で長い間研究されてきましたが、現在、必要に応じて、1976年の国際照明委員会がCIE L * a * b * （LAB）色空間とともに公開している公式が使用されています （色は単にそれらの間のユークリッド距離です）CIEΔEと呼ばれ、1994年と2000年に改良されました。 CIEΔEを知らなかった競技者は、通常、ΔE自体をRGBおよびHSVのユークリッド距離として定義しました。
ΔEを使用して、ドラム上の色の配置の品質を、ドラム上の隣接する色間の差の平方の合計として評価するための関数を構築できます。 参加者間の決定は、ソリューションの品質機能の選択とは異なり始めます。 すべての優れたソリューションはCIEΔEを使用しました。 それらの間で、ソリューションの品質関数の選択とその最適化のアルゴリズムが異なります。
CIEΔEの意味がいくらか異なるのはなぜですか？ CIE LABカラースペースは、色が等間隔になるように作成されました。 輝度を他の2つの色座標から分離します。これにより、他の座標が同じ単位で変化した場合に、いくつかの輝度単位の色の変化が差として認識されるように選択されます。 しかし、物理空間（ CIE XYZ ）のLABへの変換を表現する関数の数学的な単純さは、明らかに重要でした。 その後の実験では、知覚される色差は、非常に近いとはいえ、LABに固有のものとは完全に一致しないことが示されました。 つまり、LABは完全に均質ではありません。 しかし、CIEΔE1976の修正は新しい色空間に含めることはできません。つまり、CIE LABの古いCIEΔEのように、補正されたCIEΔEがユークリッド距離になる空間を持つことは不可能です。 したがって、CIE LAB 1967が引き続き使用されます。
色の空間を選択したら、ソリューションの品質の最も自然で最も単純な関数をさらに選択できます。これは、配置の隣接する色の間の平方和です。 この機能を最適化すると、隣接する色の間の移行が最もスムーズになり（CIEΔEを使用する場合）、このソリューションは現在、更新されたカラーソーサラーで使用されています。 ただし、その一部を使用し、他の色調にスムーズに切り替えて最初の色調に再び戻るよりも、隣接する色のグループを一列に並べた方がよい場合があることを特に考慮していません。 さらに、色を「一方向に」色に切り替えることが望ましい場合があります。これにより、暗い赤の後、少し明るい赤が暗い色合いではなくさらに明るくなります。 これらの要望を考慮に入れるために、参加者は単純な品質関数に、より離れた隣人への二乗差の合計、またはすべての最も近い隣人の平均色を追加しました。 これにより、アレンジメントの全体的な外観は改善されましたが、残念ながら、クローズアップビュー-魔術師が一度に表示する5色のセット-を不当に悪化させることがよくありました。
品質関数を選択したら、最適化方法を決定する必要があります。 この関数が隣同士の色の差の二乗の合計のように見える場合、それを最適化するタスクは、巡回セールスマンの経路（TSP）を最適化するタスクとほぼ同等で、すべての場所を一度訪れて、合計経路を最小化するように努めます。 TSPはNP複雑ですが、よく研究された問題であり、パブリックドメインにはおおよその解決策として主にLKHとConcordeの優れたソルバーがいくつかあります。 特殊なソルバーを使用すると、普遍的な最適化手法を使用した場合よりも最適かつ高速にソリューションを近づけることができます。
配置品質のより複雑な関数が選択された場合、最も近い隣同士の間だけでなく違いを考慮して、そのような普遍的な方法が必要です。
CIE94 メトリック用のZubchickの TSPソートオプション
2人の参加者がアニーリング法を使用しました。 一貫したソリューション最適化のこの方法。 まず、任意の解決策を採用してから、徐々に改善していきます。 各ステップで、以前のソリューションの単純な変換を選択します。 たとえば、いくつかのランダムな色や隣接する色を入れ替えたり、花を反転したり、別の場所に置いたりします。 ソリューションの品質関数によるこのような置換の後、前のソリューションと次のソリューションの品質が比較されます。
AOrazaevのいくつかのアニーリングソートオプション
これがアニーリング法ではなく、勾配降下法である場合、彼は常に低品質のソリューションから高品質のソリューションに移行します。 しかし、このような方法は、単純な変換を使用してソリューションを改善することが不可能な場合、局所的な最適化につながりますが、すべてが根本的に変更された場合、より良い結果を得ることができます。 したがって、アニーリング方法は、ソリューションを悪化させることがあります。 このため、グローバルな最適値の検索でローカルな最適値を取り除くことができます。 解決策は悪くありませんでしたが、近くでは十分ではありませんでした。
私たちの他の2人の同僚は遺伝的アルゴリズムを使用しましたが、良い結果が得られなかったか、品質関数が失敗しました。 XtremAlRavenのバージョンとは別に、独自に取得したTSPソリューションが出発点として採用されましたが、大幅に改善することはできませんでした。
遺伝的アルゴリズムを使用して、XtremAlRavenのCIE1994メトリックで変更されたTSPを改善する試み
これまで、結果はアルゴリズムでしか取得できないという事実について話しましたが、特定のアルゴリズムを選択することに加えて、いくつかの手動介入が可能でした。 第一に、一部の参加者は、最初にいくつかの選択したポイント（黒、赤、緑など）の周りの色をグループ化し、すべてのゾーンを個別に最適化してから、それらを結合しようとしました。
手動で選択したグループに色を配置して（類似の飽和色が互いに混ざらないように）、境界色を見つけて互いに滑らかになるようにし、各グループを境界色の間でソートしました。 この方法を使用すると、さまざまな場所で同じ色の斑点よりも少ないことが判明するため、遠くから見た目が良いソリューションを見つけることができますが、魔術師では、5色しか表示されない場合、少し悪く見えます。
実際、競争が発表される前に、魔術師の開発者が1か月半の間、色をうまく配置する方法の問題を未解決のままにしていたため、タスクは困難に思えました。 最終的に、彼ら自身が後で競争に参加した人々に匹敵する品質の良い解決策を見つけました。 また、色の理論のいくつかの要素を事前に知らない場合、この問題をうまく解決する方法を理解することは困難です。 私の決定は、コンテストの3日目、他のほとんどの日-最初の週に準備ができていました。
最終ソート
ここでは、魔術師に関係していたチームはすでに困難を抱えていました-彼らはほぼ40のいずれかを選択しなければなりませんでした。