유전자 알고리즘의 룰렛 선택
https://stackoverflow.com/questions/177271
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
누구든지 룰렛 선택 기능에 대한 의사 코드를 제공 할 수 있습니까? 이것을 어떻게 구현합니까 :
이 수학 표기법을 읽는 방법을 정말로 이해하지 못합니다. 나는 확률이나 통계를받지 못했습니다.
해결책
내가 직접 해본 지 몇 년이 지났지 만 Google에서 다음 의사 코드가 쉽게 발견되었습니다.
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
또한 FS를 축적하면보다 효율적인 솔루션을 생성 할 수 있습니다.
cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]
def select(cfs):
return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))
이것은 더 빠르며 매우 간결한 코드입니다. C ++의 STL에는 사용중인 언어 인 경우 유사한 이등분 알고리즘이 있습니다.
게시 된 의사 코드에는 불분명 한 요소가 포함되어 있으며 생성의 복잡성을 추가합니다. 자식 순수한 선택을 수행하는 대신. 다음은 해당 의사 코드의 간단한 파이썬 구현입니다.
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)
- 에프맥스 인구의 최대 체력입니다
- AVG (F)는 평균 체력입니다
τ는 모집단 (N)의 개인 수에 명시 적으로 의존하지 않지만 비율은 N에 따라 변경 될 수 있습니다.
그러나 많은 응용 분야에서 (체력이 남아 있고 평균 체력이 N을 증가시키기 위해 0으로 줄어들지 않는 경우) τ는 n과 함께 무동력으로 증가하지 않습니다. 이 알고리즘의 전형적인 복잡성은 O (1)입니다. (검색 알고리즘을 사용한 룰렛 휠 선택에는 O (N) 또는 O (LOG N) 복잡성이 있습니다).
이 절차의 확률 분포는 실제로 고전적인 룰렛 휠 선택과 동일합니다.
자세한 내용은 다음을 참조하십시오.
- 확률 적 수용을 통한 룰렛 휠 선택 (Adam Liposki, Dorota Lipowska -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**
위의 답변에서, 나는 다음을 얻었고, 그것은 답 자체보다 나에게 더 분명했습니다.
예를 들어 보려면 :
random (sum) :: random (12) 인구를 통한 반복, 우리는 다음을 확인합니다 : random <sum
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;
}
}
Stanford AI Lab의 Thrun 교수는 또한 Udacity의 CS373 동안 Python에서 빠른 (ER?) 재 샘플링 코드를 제시했습니다. Google 검색 결과는 다음 링크로 이어졌습니다.
http://www.udacity-forums.com/cs373/questions/20194/fast-resampling-algorithm
도움이 되었기를 바랍니다
다음은 최근 룰렛 선택을 위해 쓴 소형 Java 구현입니다.
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://naturefcode.com/book/book/book-9the-evolution-of-code - 유전자 알고리즘에 대한 초보자 친화적이고 명확한 장. 설명합니다 룰렛 휠 선택 나무 편지 양동이로서 보통의 연산).
https://en.wikipedia.org/wiki/fitness_proportion_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
이 답변은 기본적으로 Andrew Mao의 답변과 동일합니다.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;
}
