اختيار الروليت في الخوارزميات الجينية
https://stackoverflow.com/questions/177271
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل يمكن لأي شخص تقديم بعض الرموز الزائفة لوظيفة اختيار الروليت؟كيف يمكنني تنفيذ هذا:
لا أفهم حقًا كيفية قراءة تدوين الرياضيات هذا.لم أتخذ أي احتمالات أو إحصاءات.
المحلول
ولقد كان بضع سنوات منذ أن كنت قد فعلت ذلك بنفسي، ولكن تم العثور على رمز زائف التالية بسهولة بما فيه الكفاية على جوجل.
for all members of population
sum += fitness of this individual
end for
for all members of population
probability = sum of probabilities + (fitness / sum)
sum of probabilities += probability
end for
loop until new population is full
do this twice
number = Random between 0 and 1
for all members of population
if number > probability but less than next probability
then you have been selected
end for
end
create offspring
end loop
ويمكن الاطلاع على الموقع حيث جاء ذلك من هنا اذا كنت بحاجة الى مزيد من التفاصيل.
نصائح أخرى
والكثير من الحلول الصحيحة بالفعل، ولكن أعتقد أن هذا الرمز هو أكثر وضوحا.
def select(fs):
p = random.uniform(0, sum(fs))
for i, f in enumerate(fs):
if p <= 0:
break
p -= f
return i
وبالإضافة إلى ذلك، إذا كنت تتراكم على خ، أنت يمكن أن تنتج حلا أكثر كفاءة.
cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]
def select(cfs):
return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))
وهذا هو كل أسرع وانها متاحة موجزة للغاية. STL في C ++ لديه خوارزمية التنصيف مماثلة المتاحة إذا كان هذا هو اللغة التي تستخدمها.
ووشبة الكود نشر يحتوي على بعض العناصر غير واضحة، ويضيف تعقيد توليد <م> ذرية بدلا من أداء اختيار نقية. هنا هو تطبيق بيثون بسيط من أن شبة الكود:
def roulette_select(population, fitnesses, num):
""" Roulette selection, implemented according to:
<http://stackoverflow.com/questions/177271/roulette
-selection-in-genetic-algorithms/177278#177278>
"""
total_fitness = float(sum(fitnesses))
rel_fitness = [f/total_fitness for f in fitnesses]
# Generate probability intervals for each individual
probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
# Draw new population
new_population = []
for n in xrange(num):
r = rand()
for (i, individual) in enumerate(population):
if r <= probs[i]:
new_population.append(individual)
break
return new_population
وهذا ما يسمى اختيار عجلة الروليت عبر القبول العشوائي:
/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.
unsigned rw_selection(double f_max)
{
for (;;)
{
// Select randomly one of the individuals
unsigned i(random_individual());
// The selection is accepted with probability fitness(i) / f_max
if (uniform_random_01() < fitness(i) / f_max)
return i;
}
}
متوسط عدد المحاولات المطلوبة لتحديد واحد هو:
τ = والأعلى / المتوسط (و)
- Fالأعلى هو أقصى قدر من اللياقة البدنية للسكان
- avg(f) هو متوسط اللياقة البدنية
τ لا تعتمد بشكل صريح على عدد الأفراد في السكان (N)، ولكن يمكن أن تتغير النسبة مع N.
ومع ذلك، في العديد من التطبيقات (حيث تظل اللياقة البدنية محدودة ولا يتناقص متوسط اللياقة البدنية إلى 0 لزيادة N) τ لا تزيد بشكل غير محدود مع N وبالتالي التعقيد النموذجي لهذه الخوارزمية هو O(1) (اختيار عجلة الروليت باستخدام خوارزميات البحث له تعقيد O(N) أو O(log N)).
التوزيع الاحتمالي لهذا الإجراء هو في الواقع نفس التوزيع في اختيار عجلة الروليت الكلاسيكية.
لمزيد من التفاصيل انظر:
- اختيار عجلة الروليت عبر القبول العشوائي (آدم ليبوسكي، دوروتا ليبوسكا - 2011)
وهنا بعض التعليمات البرمجية في C:
// Find the sum of fitnesses. The function fitness(i) should
//return the fitness value for member i**
float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
sumFitness += fitness(i);
// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;
// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;
while (randomNumber > partialSum)
{
partialSum += fitness(memberID);
memberID++;
}
**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**
ومن الجواب أعلاه، وحصلت على ما يلي، الذي كان أكثر وضوحا بالنسبة لي من الإجابة نفسها.
لإعطاء مثال على ذلك:
وعشوائية (مجموع) :: عشوائية (12) بالتكرار عبر السكان، ونحن تحقق ما يلي: عشوائي <مبلغ
ودعونا اختار 7 كرقم عشوائي.
Index | Fitness | Sum | 7 < Sum
0 | 2 | 2 | false
1 | 3 | 5 | false
2 | 1 | 6 | false
3 | 4 | 10 | true
4 | 2 | 12 | ...
وخلال هذا المثال، معظم مناسبا (مؤشر 3) لديها أعلى نسبة من اختياره (33٪)؛ حيث وصل عدد عشوائي ليس لديها سوى على الأرض داخل 6-> 10، وسيتم اختيارها.
for (unsigned int i=0;i<sets.size();i++) {
sum += sets[i].eval();
}
double rand = (((double)rand() / (double)RAND_MAX) * sum);
sum = 0;
for (unsigned int i=0;i<sets.size();i++) {
sum += sets[i].eval();
if (rand < sum) {
//breed i
break;
}
}
أ. عرض Thrun من مختبر ستانفورد AI أيضا (إيه؟) رمز إعادة أخذ العينات بسرعة في الثعبان أثناء CS373 له من دورة Udacity. نتائج بحث Google أدت إلى الرابط التالي:
http://www.udacity-forums.com/ cs373 / الأسئلة / 20194 / سريعة اختزال خوارزمية
ويساعد هذا الأمل
إليك تطبيق جافا المدمجة كتبت مؤخرا لاختيار الروليت، ونأمل من الاستخدام.
public static gene rouletteSelection()
{
float totalScore = 0;
float runningScore = 0;
for (gene g : genes)
{
totalScore += g.score;
}
float rnd = (float) (Math.random() * totalScore);
for (gene g : genes)
{
if ( rnd>=runningScore &&
rnd<=runningScore+g.score)
{
return g;
}
runningScore+=g.score;
}
return null;
}
اختيار عجلة الروليت في MatLab:
TotalFitness=sum(Fitness);
ProbSelection=zeros(PopLength,1);
CumProb=zeros(PopLength,1);
for i=1:PopLength
ProbSelection(i)=Fitness(i)/TotalFitness;
if i==1
CumProb(i)=ProbSelection(i);
else
CumProb(i)=CumProb(i-1)+ProbSelection(i);
end
end
SelectInd=rand(PopLength,1);
for i=1:PopLength
flag=0;
for j=1:PopLength
if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
flag=1;
break;
end
end
if(flag==0)
SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
end
end
Based on my research ,Here is another implementation in C# if there is a need for it:
//those with higher fitness get selected wit a large probability
//return-->individuals with highest fitness
private int RouletteSelection()
{
double randomFitness = m_random.NextDouble() * m_totalFitness;
int idx = -1;
int mid;
int first = 0;
int last = m_populationSize -1;
mid = (last - first)/2;
// ArrayList's BinarySearch is for exact values only
// so do this by hand.
while (idx == -1 && first <= last)
{
if (randomFitness < (double)m_fitnessTable[mid])
{
last = mid;
}
else if (randomFitness > (double)m_fitnessTable[mid])
{
first = mid;
}
mid = (first + last)/2;
// lies between i and i+1
if ((last - first) == 1)
idx = last;
}
return idx;
}
حسنًا، هناك طريقتان لذلك اختيار عجلة الروليت تطبيق: معتاد و القبول العشوائي واحد.
معتاد الخوارزمية:
# there will be some amount of repeating organisms here.
mating_pool = []
all_organisms_in_population.each do |organism|
organism.fitness.times { mating_pool.push(organism) }
end
# [very_fit_organism, very_fit_organism, very_fit_organism, not_so_fit_organism]
return mating_pool.sample #=> random, likely fit, parent!
القبول العشوائي الخوارزمية:
max_fitness_in_population = all_organisms_in_population.sort_by(:fitness)[0]
loop do
random_parent = all_organisms_in_population.sample
probability = random_parent.fitness/max_fitness_in_population * 100
# if random_parent's fitness is 90%,
# it's very likely that rand(100) is smaller than it.
if rand(100) < probability
return random_parent #=> random, likely fit, parent!
else
next #=> or let's keep on searching for one.
end
end
يمكنك اختيار أي منهما، وسوف يعودون بنتائج متطابقة.
موارد مفيدة:
http://natureofcode.com/book/chapter-9-the-evolution-of-code - فصل سهل للمبتدئين وواضح عن الخوارزميات الجينية.يشرح اختيار عجلة الروليت مثل دلو من الحروف الخشبية (كلما أدخلت المزيد - زادت فرصة اختيار الحرف A، معتاد خوارزمية).
https://en.wikipedia.org/wiki/Fitness_proportionate_selection - يصف القبول العشوائي خوارزمية.
هذا سويفت 4 ينفذ ملحق المصفوفة الاختيار العشوائي الموزون، ويعرف أيضًا باسم اختيار الروليت من عناصره:
public extension Array where Element == Double {
/// Consider the elements as weight values and return a weighted random selection by index.
/// a.k.a Roulette wheel selection.
func weightedRandomIndex() -> Int {
var selected: Int = 0
var total: Double = self[0]
for i in 1..<self.count { // start at 1
total += self[i]
if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
}
return selected
}
}
على سبيل المثال بالنظر إلى مجموعة العناصر المكونة من عنصرين:
[0.9, 0.1]
weightedRandomIndex() سيعود صفرًا في 90% من الوقت وواحدًا في 10% من الوقت.
هنا اختبار أكثر اكتمالا:
let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
let index = weights.weightedRandomIndex()
results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
print(weights[key], Double(val)/Double(n))
}
انتاج:
0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092
هذه الإجابة هي في الأساس نفس إجابة أندرو ماو هنا:https://stackoverflow.com/a/15582983/74975
وكتبت النسخة في C # و أتطلع حقا للتأكيد أنه من الصحيح فعلا:
و(roulette_selector هو رقم عشوائي التي ستكون في نطاق 0،0-1،0)
private Individual Select_Roulette(double sum_fitness)
{
Individual ret = new Individual();
bool loop = true;
while (loop)
{
//this will give us a double within the range 0.0 to total fitness
double slice = roulette_selector.NextDouble() * sum_fitness;
double curFitness = 0.0;
foreach (Individual ind in _generation)
{
curFitness += ind.Fitness;
if (curFitness >= slice)
{
loop = false;
ret = ind;
break;
}
}
}
return ret;
}
