0

私は最適化問題のためのJavaフレームワークに取り組んでいます。これまで、lp_solveとGLPKを実装してきたので、線形問題（LP）と整数線形問題（ILP）を処理できます。ここで、非線形制約または非線形目的関数の問題を処理できるようにするために、ソルバーとして進化的アルゴリズムを使用する可能性を提供したいと思います。一般に、制約最適化問題（COS）を処理します。遺伝的アルゴリズム用のApachecommons遺伝的パッケージを見つけ、遺伝的アルゴリズムの実装を開始しました。

私のアルゴリズムの染色体は、最適化問題の解決策を表しています。つまり、マップで構成されていますVariable -> Number。さて、最初の母集団では、ランダムにソリューションを作成し、そこから進化を始めたいと思います。したがって、変数のランダムな値を見つける必要があります。変数の下限と上限にアクセスでき、その定義域が整数であるかどうかは実数です。したがって、次の方法で変数を開始します。

//Create a Random Number generator
Random generator = new Random();

//Create a new Map to store the variables and their assigned values
Map<String,Number> newRepresentation = new HashMap<String,Number>();

//Iterate over all variables from the problem
for (Entry<String,Variable> entry : problem.getVariables().entrySet()) {
    Variable variable = entry.getValue();
    Number uB = variable.getUpperBound();
    Number lB = variable.getLowerBound();
    //Create a random value for this variable
    Number randomValue = (generator.nextDouble() * (uB.doubleValue() - lB.doubleValue())) + lB.doubleValue();
    //If the variable has Integers as its domain, make the random value an Integer
    if (variable.getType() == OptVarType.INTEGER) randomValue = randomValue.intValue();
    newRepresentation.put(variable.getName(), randomValue);
}

newRepresentationこれにより、すべての変数が乱数に割り当てられたマップが得られるはずです。ただし、変数が制限されていない場合、つまり下限がに等しく0、上限がに等しい場合Integer.MAX_VALUE、下限に近い値を取得することはありません。たとえば、私は問題を抱えています

max 3x+4y
s.t.
x+2y <= 14
3x-y >= 0
x-y <= 2
x in {0,...,2147483647}
y in {0,...,2147483647}

次に、最適なソリューションはx=6, y=4です。しかし、変数は私のEAによって次のように初期化されます。

A new Population has been initiated: {y=1430866067, x=1616622921}
A new Population has been initiated: {y=1483081480, x=1389387196}
A new Population has been initiated: {y=242558338, x=376547119}
A new Population has been initiated: {y=1861689859, x=959676986}
...

値は、最適なソリューションが配置されている下限に近づくことはありません。したがって、私のEAは、数分間検索した後でも、少なくとも最適なソリューションに近いソリューションを見つけられません。

質問：値が検索空間全体に均等に分散されるように、染色体の開始を変更するにはどうすればよいですか？

4

1 に答える 1

1

まず、変換後も整数値が均等に分散されているかどうかを考えました。

例：

5から10までの整数を作成したいので、その間隔で均一に分散されたdoubleを作成し（これはコードで正常に機能します）、[5,5.5）にある可能性は、 [5.5,6）、[6,6.5]、...、[9.5,10）。ここで、整数に変換するために、値をフロア化し、説明した2つの間隔をそれぞれの可能な整数値にマッピングします。だから、これは私には問題ないようです。

私も簡単なテストを実行しました、そしてそれは私にとってうまくいきます。だから私はあなたの問題の2つの考えられる理由だけを見ます：

  1. 乱数ジェネレーターが壊れています。（標準のJDKを使用している場合はほとんどありません）
  2. 実行する試行回数が少なすぎるため、開始値も低くなります。間隔は非常に大きくなります。

編集：Numberクラスのドキュメントを見てきました。整数への変換は、切り捨てまたは丸めのいずれかを自由に使用できます。丸めを使用する場合、ランダムな整数値は均一に分散されなくなるため、double値を明示的にフロア化する必要があります。

于 2012-08-23T08:25:11.487 に答える