この記事は機械翻訳されたものです。
テストの実行
細菌の採餌最適化 (機械翻訳)
圧電細菌採餌の最適化 （エピ） は非常に困難または不可能の数値最大化または最小化問題の近似解を検索するために使用することができます魅力的な人工知能 （AI） 技術です。 私はこの記事で説明圧電エピのバージョン 2002年の紙では、「バイオミミ クリーの細菌採餌の分散最適化と制御、」博士によって基づいています。 ケビン Passino。 (このホワイト ペーパーはインターネット検索で見つけることができますが、サブスクリプションが必要です。)圧電エピはモデルの食品を求めると生殖行動 E. などの一般的な細菌の確率論的手法です。 大腸菌の数値最適化問題を解決するために効果的な決定論的なアプローチが存在します。 最良の方法を圧電エピものの感触をこの資料の内容を確認する調べることです図 1 と図 2。
.png)
図 1 Rastrigin 関数問題
.png)
図 2 の細菌の採餌の最適化を使用して
図 1 、標準ベンチマーク問題としてを使用して最適化アルゴリズムの有効性をテストするには多くの場合、Rastrigin 関数のグラフです。 目標は、x の値を見つけることですし、関数を最小限に抑える y。 ローカルミニマ ソリューションは多くの谷があることを見ることができます。 ただし、x には 1 つだけのグローバル ソリューションがある 0.0 と y = =、関数の値が 0.0 0.0 =。
図 2 圧電エピ Rastrigin 関数を解決しようとしてのスクリーン ショットです。 プログラムはシミュレートされた細菌 (この例では 100) の数など、いくつかのパラメーターを設定します。 各菌可能な解決策を表します位置しています。 最初に、すべての細菌はランダムな位置に設定されます。 各位置は、Rastrigin 関数の値を表す、関連するコストがあります。 メインの処理ループを実行すると、さまざまな細菌が連続してより良い解決策を見つけます。 処理の最後に、最善の解決策を見つけた 0.0002 だとき x-0.0010 と y = = 0.0005 — 非常には非常に最適なソリューションが閉じます。
この資料の残りの部分で私は、圧電エピ アルゴリズムの詳細に説明し、実行されているプログラムを歩く図 2。 私は、デモ ・ プログラムで c# の場合は、コードが、ここで Visual Basic など別の言語を示すコードを簡単に適応することができる必要があります。ネットまたは Windows PowerShell。 プログラムの完全なソース コードが入手可能です archive.msdn.microsoft.com/mag201203TestRun。 この資料には、中間または高度なスキルを現代の手続き型言語でコーディングしているが、何か圧電エピまたは関連の AI 技術について知っていると仮定しない前提としています。
細菌の実際の行動
E. など細菌 大腸菌、惑星の最も成功した生物の中で。 細菌べん毛と呼ばれる剛付属があります。 すべての鞭毛が反時計回りに回転して、プロペラ効果が作成されます細菌は以上または以下の垂直方向の泳ぐ。
細菌を傾向があるなどいくつかの意味を改善しているときに泳ぐことが増加の栄養グラデーションを例えば見つける。 すべての鞭毛、時計回りの方向に回転すると、細菌迅速に転落し、新しい方向にポイントします。 細菌は、有害物質が発生した場合、またはが、改善されない、グラデーションで転落する傾向があります。 細菌再現約 20 分間隔か無性に 2 つの同一の娘を分割します。 健康細菌よりも少ない健全な細菌を再現する傾向があります。
プログラムの全体的な構造
圧電エピ デモの全体的なプログラム構造に記載されている図 3。
図 3 圧電エピ プログラム構造
using System;
namespace BacterialForagingOptimization
{
class BacterialForagingOptimizationProgram
{
static Random random = null;
static void Main(string[] args)
{
try
{
int dim = 2;
double minValue = -5.12;
double maxValue = 5.12;
int S = 100;
int Nc = 20;
int Ns = 5;
int Nre = 8;
int Ned = 4;
double Ped = 0.25;
double Ci = 0.05;
random = new Random(0);
// Initialize bacteria colony
// Find best initial cost and position
int t = 0;
for (int l = 0; l < Ned; ++l) // Eliminate-disperse loop
{
for (int k = 0; k < Nre; ++k) // Reproduce-eliminate loop
{
for (int j = 0; j < Nc; ++j) // Chemotactic loop
{
// Reset the health of each bacterium to 0.0
for (int i = 0; i < S; ++i)
{
// Process each bacterium
}
++t;
}
// Reproduce healthiest bacteria, eliminate other half
}
// Eliminate-disperse
}
Console.WriteLine("\nBest cost found = " + bestCost.ToString("F4"));
Console.Write("Best position/solution = ");
ShowVector(bestPosition);
}
catch (Exception ex)
{
Console.WriteLine("Fatal: " + ex.Message);
}
} // Main
static double Cost(double[] position) { ...
}
}
public class Colony // Collection of Bacterium
{
// ...
public class Bacterium : IComparable<Bacterium>
{
// ...
}
}
} // ns
私は Visual Studio の BacterialForagingOptimization という c# コンソール アプリケーションを作成するのにために使用。 Program.cs ファイル BacterialForagingOptimizationProgram.cs に変更し、すべてのテンプレートは-ステートメントを除く System 名前空間への参照を使用して生成を削除します。
私はクラス スコープ ランダム オブジェクトをというランダム宣言; すぐわかる圧電エピ、確率的アルゴリズムです。 Main メソッド内私はいくつか主要な変数を宣言しました。 変数の dim 次元問題での数です。 この例の目的を見つけるには x と y は、Rastrigin 関数の 2 を dim で設定は。 MinValue と maxValue 変数 x と y の両方の制限を確立します。 変数 S 細菌の数です。 S と Nc はのでこれら研究資料より簡単にすることができますを使用する名前を参照としてその記事の使用など、少し nondescriptive 変数名を使用します。
変数の Nc いわゆる走化手順の数です。 これは各細菌の存続期間を表すカウンターとして考えることができます。 変数 Ns、細菌と同じ方向に泳ぐ最大回数です。 変数 Nre は再現手順の数です。 この細菌の世代の数として考えることができます。 変数のネッド分散ステップ数です。 すべての今して圧電エピ アルゴリズムでは新しい位置に実際の細菌に及ぼす外部環境のモデリング、ランダムにいくつかの細菌が分散します。 変数 Ped 分散されて、特定の細菌の確率です。 変数の Ci の基本的な水泳の長さ各細菌です。 泳ぐときは、細菌 Ci 以上、1 つのステップで移動しますありません。 変数 t 圧電エピの進行状況を追跡する時間カウンターです。 圧電エピは比較的新しいですので、非常に小さな圧電エピ パラメーターに異なる値を使用しての効果について知られています。
メインの圧電エピ アルゴリズム処理のいくつかの入れ子になったループで構成されています。 1 つのタイム カウンターで制御される遺伝のアルゴリズムなどのほとんどの AI アルゴリズムとは異なり、圧電エピ複数のループ カウンターによって制御されます。
プログラムは、静的関数を使用します。 これは、最小化または最大化しようとしている関数です。 この例では、コスト関数、Rastrigin 関数だけです。 入力は、double 値の配列に可能な解決策を表す細菌の位置を表すです。 この例では、コストの関数として定義されます。
double result = 0.0;
for (int i = 0; i < position.Length; ++i) {
double xi = position[i];
result += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
}
return result;
インターネット検索することによって Rastrigin 関数についての詳細を見つけることができますが、ポイント コスト関数は細菌の位置を受け入れるし、最小化または最大化しようとしている値を返します。
細菌と植民地のクラス
圧電エピ プログラムでは、細菌のコレクションを表す、植民地クラスは個々 の細菌を定義する入れ子になった菌クラスを定義します。 入れ子になった菌クラスに記載されている図 4。
図 4 菌クラス
public class Bacterium : IComparable<Bacterium>
{
public double[] position;
public double cost;
public double prevCost;
public double health;
static Random random = new Random(0);
public Bacterium(int dim, double minValue, double maxValue)
{
this.position = new double[dim];
for (int p = 0; p < dim; ++p) {
double x = (maxValue - minValue) * random.NextDouble() + minValue;
this.position[p] = x;
}
this.health = 0.0;
}
public override string ToString()
{
// See code download
}
public int CompareTo(Bacterium other)
{
if (this.health < other.health)
return -1;
else if (this.health > other.health)
return 1;
else
return 0;
}
}
細菌が、次の世代に存続するを決定するとき彼らの健康が菌の 2 つのオブジェクトを並べ替えることができますようにクラス菌、IComparable インターフェイスから派生します。
位置フィールド ソリューションを表します。 [コスト] フィールドの位置に関連付けられているコストです。 フィールド prevCost 細菌の前の位置に関連付けられているコストです。 これには、それは、改善されて、したがってかどうか、泳ぐ転落かかどうかを知って、細菌ことができます。 健康フィールド菌の累積コストの合計は、細菌の寿命中にです。 目標コストを最小限に抑えるには、健康の値が小さい大きい値よりも優れています。
細菌のコンス トラクターを菌オブジェクトにランダムな位置を初期化します。 [コスト] フィールドは、明示的にコンス トラクターによって設定されていません。 CompareTo メソッドは最小の健康から菌オブジェクト最大健康に注文します。
図 5 簡単な植民地クラスを示しています。
図 5 は、植民地のクラス
public class Colony
{
public Bacterium[] bacteria;
public Colony(int S, int dim, double minValue, double maxValue)
{
this.bacteria = new Bacterium[S];
for (int i = 0; i < S; ++i)
bacteria[i] = new Bacterium(dim, minValue, maxValue);
}
public override string ToString() { // See code download }
public class Bacterium : IComparable<Bacterium>
{
// ...
}
}
植民地クラスは基本的に細菌のオブジェクトのコレクションです。 植民地のコンス トラクターは菌の細菌のコンス トラクターを呼び出すことによって、各菌ランダムな位置割り当てられる場所のコレクションを作成します。
アルゴリズム
S と Nc、圧電エピ アルゴリズムなどの圧電エピ変数初期化セットアップ後、細菌のコロニーましょう。
Console.WriteLine("\nInitializing bacteria colony");
Colony colony = new Colony(S, dim, minValue, maxValue);
for (int i = 0; i < S; ++i) {
double cost = Cost(colony.bacteria[i].position);
colony.bacteria[i].cost = cost;
colony.bacteria[i].prevCost = cost;
}
...
コスト関数が、植民地の外部にあるため、菌の各オブジェクトのコスト コスト関数を使用して、植民地コンス トラクター以外に設定されます。
初期化後は、コストが Rastrigin 関数を最小限の場合より高いコストよりは念頭に置いて維持、植民地の最高の菌が決定されます。
double bestCost = colony.bacteria[0].cost;
int indexOfBest = 0;
for (int i = 0; i < S; ++i) {
if (colony.bacteria[i].cost < bestCost) {
bestCost = colony.bacteria[i].cost;
indexOfBest = i;
}
}
double[] bestPosition = new double[dim];
colony.bacteria[indexOfBest].position.CopyTo(bestPosition, 0);
Console.WriteLine("\nBest initial cost = " + bestCost.ToString("F4"));
...
次に、メインの圧電エピ処理の複数のループを設定されています。
Console.WriteLine("\nEntering main BFO algorithm loop\n");
int t = 0;
for (int l = 0; l < Ned; ++l)
{
for (int k = 0; k < Nre; ++k)
{
for (int j = 0; j < Nc; ++j)
{
for (int i = 0; i < S; ++i) { colony.bacteria[i].health = 0.0; }
for (int i = 0; i < S; ++i) // Each bacterium
{
...
外側のループ インデックス l 分散手順を処理します。 次のループ インデックス k を再現手順を処理します。 第 3 ループ インデックス j の各細菌の存続期間を表す走化手順を処理します。 各菌の健康を 0 にリセットされますので走ループ内で、新世代の細菌は、生成されています。 健康値走ループ内で、各菌、新しい方向性を決定するには、バッテリー装着時とし、新たな方向性で移動のリセット細菌のような後。
double[] tumble = new double[dim];
for (int p = 0; p < dim; ++p) {
tumble[p] = 2.0 * random.NextDouble() - 1.0;
}
double rootProduct = 0.0;
for (int p = 0; p < dim; ++p) {
rootProduct += (tumble[p] * tumble[p]);
}
for (int p = 0; p < dim; ++p) {
colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
}
...
最初に、現在の細菌の位置の各コンポーネントでは、-1.0 ～ +1.0 のランダムな値が生成されます。 [ルート製品の結果のベクトルが計算されます。 して、細菌の新しい位置、古い位置を撮影していくつかの Ci 変数値の一部を移動計算されます。
タンブリング後、現在の細菌を更新され、新しいグローバル最善の解決策を発見したかどうかを参照してくださいに菌がチェックされます。
colony.bacteria[i].prevCost = colony.bacteria[i].cost;
colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
colony.bacteria[i].health += colony.bacteria[i].cost;
if (colony.bacteria[i].cost < bestCost) {
Console.WriteLine("New best solution found by bacteria " + i.ToString()
+ " at time = " + t);
bestCost = colony.bacteria[i].cost;
colony.bacteria[i].position.CopyTo(bestPosition, 0);
}
...
次に、細菌はそれより良い位置を見つけることによって改善している限り、ここでそれが同じ方向に泳ぐ泳ぐループを入力します。
int m = 0;
while (m < Ns && colony.bacteria[i].cost < colony.bacteria[i].prevCost) {
++m;
for (int p = 0; p < dim; ++p) {
colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
}
colony.bacteria[i].prevCost = colony.bacteria[i].cost;
colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
if (colony.bacteria[i].cost < bestCost) {
Console.WriteLine("New best solution found by bacteria " +
i.ToString() + " at time = " + t);
bestCost = colony.bacteria[i].cost;
colony.bacteria[i].position.CopyTo(bestPosition, 0);
}
} // while improving
} // i, each bacterium
++t; // increment the time counter
} // j, chemotactic loop
...
変数 m 同じ方向で連続の泳ぐ Ns の変数の値の最大数を制限するには、泳ぐカウンターです。 スイミング、時間カウンターがインクリメントされ、走化性のループを終了します。
この時点で、Nc によって与えられたその寿命すべての細菌が住んでいる、健康的な半植民地住んでいるし、少なくとも健康の半分を死ぬこと。
Array.Sort(colony.bacteria);
for (int left = 0; left < S / 2; ++left) {
int right = left + S / 2;
colony.bacteria[left].position.CopyTo(colony.bacteria[right].position, 0);
colony.bacteria[right].cost = colony.bacteria[left].cost;
colony.bacteria[right].prevCost = colony.bacteria[left].prevCost;
colony.bacteria[right].health = colony.bacteria[left].health;
}
} // k, reproduction loop
...
IComparable から菌オブジェクトを派生するため、Array.Sort メソッドを自動的に最小の健康から並べ替えます (小さな良いです） ので、最高の細菌コロニー配列の左の S/2 セルの最大の健康に。 細菌のコロニーの右のセルの弱い半分は、効果的に細菌アレイの方の半分のデータには弱いの右半分にコピーして殺され。 つまり、細菌、S の合計数 2 で割り切れる数べきであることに注意してください。
圧電エピ アルゴリズムの分散フェーズに入り、この時点で、走化性と生殖のループ、終了します。
for (int i = 0; i < S; ++i) {
double prob = random.NextDouble();
if (prob < Ped) {
for (int p = 0; p < dim; ++p) {
double x = (maxValue - minValue) *
random.NextDouble() + minValue;
colony.bacteria[i].position[p] = x;
}
double cost = Cost(colony.bacteria[i].position);
colony.bacteria[i].cost = cost;
colony.bacteria[i].prevCost = cost;
colony.bacteria[i].health = 0.0;
if (colony.bacteria[i].cost < bestCost) {
Console.WriteLine("New best solution found by bacteria " +
i.ToString() + " at time = " + t);
bestCost = colony.bacteria[i].cost;
colony.bacteria[i].position.CopyTo(bestPosition, 0);
}
} // if (prob < Ped)
} // for
} // l, elimination-dispersal loop
...
各菌が調べられます。 ランダム値を生成、現在の細菌を任意の場所に移動するかどうかを決定する変数の小児科と比較します。 細菌実際に分散している場合は、世界最高の新しい位置を発見したかどうかを参照してくださいに純粋な偶然でしました。
この時点ですべてのループが実行されているし、圧電エピ アルゴリズム ShowVector という名前のヘルパー プログラム定義メソッドを使うことが最善の解決策が表示されます。
Console.WriteLine("\n\nAll BFO processing complete");
Console.WriteLine("\nBest cost (minimum function value) found = " +
bestCost.ToString("F4"));
Console.Write("Best position/solution = ");
ShowVector(bestPosition);
Console.WriteLine("\nEnd BFO demo\n");
}
catch (Exception ex)
{
Console.WriteLine("Fatal: " + ex.Message);
}
} // Main
...
ポイントは何ですか？
圧電エピ伝統的な数学的手法を使用して処理できない数値最適化問題の近似解を見つけることは比較的新しいアプローチです。 私の意見では、圧電エピ遺伝的アルゴリズムと粒子群最適化の代替です。 どれだけ効果的な圧電エピの質問に答えるに少しの研究の証拠かではないです。
圧電エピ使用方法がありますか？ ソフトウェアのテスト、および最適化に一般に関連する多くの可能性があります。 たとえば、何か非常に困難な短期的な変更のいくつかに、ニューヨーク証券取引所の価格などを予測しようとしています。 いくつかの履歴データを収集し、株価は、入力データに関連いくつか複雑な数学方程式を考え出すが、方程式のパラメーターを決定する必要があります。 可能性のある圧電エピ パラメーターの値を推定するのに、方程式をした間違った予測の割合のコスト関数が使用できます。
圧電エピです、型メタ意味あるだけに、概念的なフレームワークは、特定のアルゴリズムを設計するために使用することができます。 ここで紹介した圧電エピのバージョンは、多くの可能性を 1 つだけで、トピックの最終的な単語ではなく、実験のための出発点と見なされる必要があります。 実際には、この記事のサイズを管理できるようにするには、私は、元の圧電エピ研究資料に記載されて機能に群がって、細菌を削除しました。
Dr.James McCaffrey作品は Volt Information Sciences Inc.、ここで彼は、Microsoft レドモンド、ワシントン州で、キャンパス働くソフトウェア エンジニアの技術トレーニングを管理します。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。また、『.NET Test Automation Recipes: A Problem-Solution Approach』(Apress、2006 年) の著者でもあります。連絡先は jammc@microsoft.com (英語のみ) です。
この記事のレビュー、次技術専門家に感謝：Paul Koch、 Dan Liebling、 Anne Loomis Thompson と Shane Williams