0

目標は、99 個の要素のリストを作成することです。すべての要素は 1 または 0 でなければなりません。最初の要素は 1 でなければなりません。合計で 7 つの 1 が必要です。

import random
import math
import time

# constants determined through testing                                                                                                       

generation_constant = 0.96

def generate_candidate():
    coin_vector = []
    coin_vector.append(1)
    for i in range(0, 99):
        random_value = random.random()
        if (random_value > generation_constant):
            coin_vector.append(1)
        else:
            coin_vector.append(0)
    return coin_vector

def validate_candidate(vector):
    vector_sum = sum(vector)
    sum_test = False
    if (vector_sum == 7):
        sum_test = True
    first_slot = vector[0]
    first_test = False
    if (first_slot == 1):
        first_test = True
    return (sum_test and first_test)

vector1 = generate_candidate()
while (validate_candidate(vector1) == False):
    vector1 = generate_candidate()
print vector1, sum(vector1), validate_candidate(vector1)

ほとんどの場合、出力は正しく、次のようになります。

[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ] 7 真

ただし、出力が次のようになる場合もあります。

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 2 偽

私は正確に何を間違っていますか?

4

4 に答える 4

1

あなたが与えたアルゴリズムは動作しますが、遅いです。理想generation_constantは実際には二項分布を使用して計算できることに注意してください。最適値は ≈0.928571429 で、1.104% の確率で条件に適合します。最初の要素を手動で 1 に設定すると、最適値generation_constantは約 0.93877551 となり、16.58% の確率で条件に適合します。

上記は二項分布に基づいており、各試行の確率がpである合計N回の試行のうち、正確にk回の「成功」イベントが発生する確率はP ( k | N , p ) = N ! * p ^ k * (1 - p ) ^ ( N - k ) / ( n ! * ( N - k ))。それをExcel、Mathematica、またはグラフ電卓に貼り付けて、Pを最大化してください。

または:

最初と 6 つの追加項目が 1 で残りの要素が 0 である 99 個の数字のリストを生成するには、random.randomそれほど多くの呼び出しを行う必要はありません。疑似乱数の生成には非常にコストがかかります。randomあまり電話しないようにする方法は 2 つあります。

最もプロセッサ効率の良い方法は、挿入する必要がある 6 回に対して、ランダムに 6 回だけ呼び出すことです。

import random

# create vector of 99 0's
vector = [0 for i in range(99)]

# set first element to 1
vector[0] = 1

# list of locations of all 0's
indexes = range(1, 99)

# only need to loop 6 times for remaining 6 ones
for i in range(6):
    # select one of the 0 locations at random
    # "pop" it from the list so it can't be selected again
    # and set it's coresponding element in vector to 1.
    vector[indexes.pop(random.randint(0, len(indexes) - 1))] = 1

または、メモリを節約するために、新しいインデックスをそれぞれテストして、実際に何かが設定されることを確認することもできます。

import random

# create vector of 99 0's
vector = [0 for i in range(99)]

# only need to loop 7 times
for i in range(7):
    index = 0                          # first element is set to 1 first
    while vector[index] == 1:          # keep calling random until a 0 is found
        index = random.randint(0, 98)  # random index to check/set
    vector[index] = 1                  # set the random (or first) element to 1

2 つ目は常に最初の要素を最初に 1 に設定します。index = random.randint(0, 98)これは、 if のみが呼び出されるためですvector[0] == 1

于 2013-11-08T20:31:40.950 に答える
0

遺伝的プログラミングでは、無効な構成が可能な限り排除されるようにドメインを制御する必要があります。適合度は、無効な構成を排除するのではなく、有効な構成を評価することを想定しています。正直なところ、この問題は遺伝的プログラミングにはあまり適していないようです。ドメインの概要を説明しました。しかし、フィットネスの説明はどこにもありません。

とにかく、そうは言っても、ドメインに入力する方法は次のようになります。最初の要素は常に 1 であるため、無視します。残りの 98 個には 6 個しかないため、6 個の 1 を 92 個のゼロにシャッフルします。または、ドメインがそれほど大きくないため、可能性を列挙することもできます.

于 2013-11-08T19:56:10.850 に答える
0

sum() の使い方だと思います。これにより、リストが適切に変更されると思います。

>>> mylist = [1,2,3,4]
>>> sum(mylist)
10
>>> mylist
[]

これは(やや)Pythonicの再帰バージョンです

def generate_vector():
    generation_constant = .96
    myvector = [1]+[ 1 if random.random() > generation_constant else 0 for i in range(0,99)]

    mysum = 0
    for a in myvector:
        mysum = (mysum + a) 

    if mysum == 7 and myvector[0]==1:
        return myvector
    return generate_vector()

そしておまけに

def generate_test():
    for i in range(0,10000):
        vector = generate_vector()
        sum = 0
        for a in vector:
            sum = sum + a
        if sum != 7 or vector[0]!=1:
            print vector

出力:

>>> generate_test()
>>> 
于 2013-11-08T20:12:58.733 に答える