1

問題

私は粒子群最適化について少し調べていたので、テストしてみようと言いました。

私が解決しようとしている問題は、バランス パーティション問題です。または、単純にサブセット合計問題 (合計がすべての数値の半分になる) に縮小されます。

粒子の速度を更新するための一般的な式は

ここに画像の説明を入力

しかし、この質問についてはあまり詳しく説明しません。

サブセット合計問題に対するオンラインでの PSO の試みがないため、代わりに巡回セールスマン問題を調べました。

それらは、訪問した町のセットを取得し、ある町を別の町から減算し、それに対して何らかの操作を行うことを含む、速度を更新するためのアプローチです。

それと上記の式との間に関係は見られませんでした。

私のアプローチ

そこで私は公式を破棄し、部分和問題への独自のアプローチを試みました。

私は基本的にgbestandを使用しpbestて、特定の要素をサブセットから削除または追加する確率を決定しました。

つまり、問題空間が[1,2,3,4,5](ターゲットが7または8) で、現在の[1,None,3,None,None]粒子(サブセット)gbestが[None,2,3,None,None]321gbest

私はコードを投稿できますが、それが必要だとは思わないので、アイデアを得ることができます (私は python を使用しています - したがってNone)。

基本的に、これはある程度機能し、まともな解決策を得ましたが、より大きなデータセットと値では非常に遅くなりました.

私の質問

問題をエンコードして、粒子の「速度」をスマートな方法で更新していますか?

これが正しく収束するかどうかを判断する方法はありますか?

特定の問題空間に対して収束する「更新」式を作成する方法を学ぶために使用できるリソースはありますか?

よろしくお願いします！

4

1 に答える 1

1

エンコーディング

はい、これを正しくエンコードしています。各ビットマップ (事実上、5 要素のリストです) は粒子です。

概念

方程式の概念的な問題は、問題空間が離散格子グラフであり、更新ステップにすぐに役立たないためです。たとえば、学習率を調整してより細かい粒度を得たい場合は、通常、学習率をわずかな係数 (たとえば 3) だけ減らします。この空間で、わずか 1/3 のステップを踏むことは何を意味するのでしょうか? それがあなたが問題を抱えている理由です。

私が見る主な可能性は、3 倍の数の粒子を作成することですが、遷移確率をすべて 3 で割ることです。これでも十分には満足できませんが、プロセスを適切にシミュレートします。

離散ステップ

非常に大きなグラフがあり、速度が速いと 1 ステップで数十回の遷移が発生する可能性がある場合は、よりスムーズな距離 (損失またはエラー) 関数を使用してモデルを導くことができます。2 つの位置の間に 5 ステップしかないこのような小さなものでは、そのような概念を扱うのは困難です。

代わりに、解までの推定距離に基づく誤差関数を利用します。簡単なのは、粒子の合計を 7 または 8 の近い方から引くことです。難しいのは、その差と「作用している」粒子要素に基づいて距離を推定することです。

収束の証明

はい、それを行う方法はありますが、機能分析が必要です。一般に、誤差関数が粒子空間で凸であることを実証する必要があります。言い換えれば、少なくとも相対的な配置に関しては、誤差関数が信頼できる距離メトリックであることを証明する必要があります (つまり、誤差が小さいほど、解に近づいていることを意味することを証明する必要があります)。

更新式の作成

いいえ、これはヒューリスティック フィールドであり、粒子座標、誤差関数、および移動特性によって定義される問題空間の形状に基づいています。

余分な推薦

現在許可されているトランジションは、「追加」要素と「削除」要素です。これに「スワップ要素」を含めます。現在のメンバーを不在のメンバーと交換します。これにより、自明なエラー関数が凸空間を定義できるようになり、非常に短時間で収束します。

于 2016-11-08T01:17:44.660 に答える