我目前正在尝试实现 java 轮盘赌选择（请参阅http://en.wikipedia.org/wiki/Fitness_proportionate_selection）。
我的问题是在找到我的人口中每个人的相对适应度之后出现的。
例如，假设我创建了一个概率轮盘赌，例如：
个人 a : 0 - 0.3 个人 b : 0.3 - 0.5 个人 c : 0.5 - 1
而个人 a 有 30% 的被选中变化，b 有 20% 和 c 有 50% 的被选中是我旋转这个轮盘赌。
我的问题是，维基百科文章提到“注意性能提升可以通过使用二分搜索而不是线性搜索来找到合适的口袋来实现。” 这意味着在生成我的随机数之后，我必须对我的口袋进行一次线性或二分搜索，以找到选择了哪一个。
问题是，从性能的角度来看，这种在每个回合找到正确口袋的二进制搜索似乎是不必要的，难道不可能简单地拥有某种 HashMap 而表中的每个条目都链接到如图所示的范围上面并使用该范围内的键进行拉取将在线性时间内拉出相关联的个体，而不是需要二进制搜索。
我查看了树形图，但树形图必须对口袋进行初始排序，这是不行的，没有排序。
使用 n=1.000 个人并选择其中 k=100，您可以
只有测试才能知道什么更快，性能取决于 n、k 和实现。
HashMap 仅允许通过键的确切值查找元素。您的算法需要按范围查找值。因此，使用二分搜索或 TreeMap 会给你 O(log(n)) 复杂度。我认为不可能有更好的复杂性。
而且我不明白你在说什么。看起来您是在说线性搜索比 TreeMap 或二进制搜索具有更好的性能。这是错的。
好吧，也许这个 java 中的轮盘选择代码可以让你开始在这里得到所有你可以得到的 Chromosome 类
import java.util.*; // Random, Arrays, Vector, List
import java.io.*; // BufferedWriter, FileWriter
/**
* <code>Evolution</code> implements the genetic algorithm.
*
* This is an executable class that uses the <code>Chromosome<code>
* class to implement the genetic algorithm. It can be run with the
* following command line calls:
* <UL>
* <LI>java Evolution ones population_size chromosome_size generations crossover_rate mutation_rate logfile
* <LI>java Evolution binary population_size chromosome_size generations crossover_rate mutation_rate logfile binary_number
* </UL>
* <P>
* Where the parameters are:
* <UL>
* <LI><B>ones</B>: use the number of ones in the gene sequence as the
* fitness function
* <LI><B>binary</B>: measure the closeness of the gene sequence to a binary
* number for the fitness function
* <LI><B>chromosome_size</B>: an int number of genes in each chromosome
* <LI><B>generations</B>: an int number of generations to produce
* <LI><B>crossover_rate</B>: a double gene crossover rate between 0 and 1
* <LI><B>mutation_rate</B>: a double gene mutation rate between 0 and 1
* <LI><B>logfile</B>: a String name for the log file
* <LI><B>binary_number</B>: an int to be used as the binary number for
* the binary number fitness function
* </UL>
* <P>
* Some example command line calls:
* <UL>
* <LI>java Evolution ones 100 20 100 0.7 0.001 ones.log
* <LI>java Evolution binary 100 20 100 0.7 0.001 binary.log 3755865
* </UL>
* <P>
* This class implements a "roulette wheel" selection method, based on each
* chromosome's fitness value. The genetic operators are single-point
* crossover and point-mutation. To boost the selectiveness of each
* generation, the <code>threshold</code> value in the <code>selection</code>
* method can be set to an arbitrary fitness value, or to the average
* fitness value, etc.
* <P>
*/
public class Evolution
{
/**
* holds the best fitness value of a population for a particular
* generation
*/
private int best_fit = 0;
/**
* holds the sum of the fitness values of the population for a particular
* generation
*/
private int total_fit = 0;
/**
* holds the population
*/
private Vector population = null;
/**
* holds the "roulette odds" for each individual in a generation. Each
* index corresponds to an individual in the population, and each value
* represents the sum of the fitness values for that individual and all
* the prior ones in the population. The "roulette wheel" algorithm is
* performed by choosing a random number between zero and
* <code>total_fit</code> (inclusive). This number is then searched for
* in the <code>roulette</code> array. The index which contains the
* random number or the next higher number is the individual chosen for
* that "spin of the roulette wheel."
*
* @see #selection(double)
*/
private int roulette[] = null;
/**
* holds onto a <code>Random</code> object
*
* @see java.util.Random
*/
private Random rand = null;
/**
* a double between 0 and 1 (inclusive) that represents the rate at which
* crossover occurs in selected individuals
*/
private double crossover_rate = 0;
/**
* a double between 0 and 1 (inclusive) that represents the rate at which
* mutation occurs in selected individuals
*/
private double mutation_rate = 0;
/**
* Constructor for <code>Evolution</code> that use the total number of
* ones in a <code>Chromosome</code>'s gene sequence as its fitness
* function.
*
* @param pop_size a positive <code>int</code> number of
* chromosomes in the population for each generation
* @param chrom_size a positive <code>int</code> number of genes in each
* <code>Chromosome</code> object's gene sequence
* @param pc the crossover rate; this should be a
* <code>double</code> value between zero and one
* (inclusive)
* @param pc the mutation rate; this should be a
* <code>double</code> value between zero and one
* (inclusive)
*
* @see #crossover_rate
* @see #mutation_rate
* @see Chromosome#Chromosome(int, java.util.Random)
*/
public Evolution(int pop_size, int chrom_size, double pc, double pm)
{
Chromosome c = null;
total_fit = 0;
best_fit = 0;
crossover_rate = pc;
mutation_rate = pm;
// make population and roulette mapping
population = new Vector(pop_size);
roulette = new int[pop_size];
// seed the random number generator
rand = new Random(System.currentTimeMillis());
// make population
for (int i = 0; i < pop_size; i++)
{
c = new Chromosome(chrom_size, rand);
// update fitness information
total_fit = total_fit + c.get_fit();
best_fit = Math.max(best_fit, c.get_fit());
// add chromosome to population and roulette wheel
population.add(c);
roulette[i] = total_fit;
}
}
/**
* Constructor for <code>Evolution</code> that use the proximity of
* a <code>Chromosome</code>'s gene sequence to a <code>target</code>
* sequence as the fitness function.
*
* The <code>Chromosome</code>s made in this <code>Evolution</code> have
* gene sequences equal to <code>target.length</code>. The fitness
* function walks through the indexes of <code>target</code> and the
* given chromosome's gene sequence, and adds one to that chromosome's
* fitness for each gene that has the same value as <code>target</code>.
*
* @param pop_size a positive <code>int</code> number of
* chromosomes in the population for each generation
* @param target a <code>boolean</code> array whose length will be
* used as the length for all <code>Chromosome</code>s
* made by this <code>Evolution</code>; this parameter's
* value will be used by the <code>Chromosome</code>s'
* fitness functions
* @param pc the crossover rate; this should be a
* <code>double</code> value between zero and one
* (inclusive)
* @param pc the mutation rate; this should be a
* <code>double</code> value between zero and one
* (inclusive)
*
* @see #crossover_rate
* @see #mutation_rate
* @see Chromosome#Chromosome(boolean[], java.util.Random)
*/
public Evolution(int pop_size, boolean[] target, double pc, double pm)
{
Chromosome c = null;
total_fit = 0;
best_fit = 0;
crossover_rate = pc;
mutation_rate = pm;
// make population
population = new Vector(pop_size);
roulette = new int[pop_size];
// seed the random number generator
rand = new Random(System.currentTimeMillis());
// make population
for (int i = 0; i < pop_size; i++)
{
c = new Chromosome(target, rand);
// update fitness information
total_fit = total_fit + c.get_fit();
best_fit = Math.max(best_fit, c.get_fit());
// add chromosome to population and roulette wheel
population.add(c);
roulette[i] = total_fit;
}
}
/**
* Probablistically selects <code>Chromosome</code>s from this
* <code>Evolution</code>'s <code>population</code> using the
* code "roulette wheel" algorithm.
*
* This method returns a new <code>List</code> of individuals from the
* previous population who have been probabalistically selected based
* on their fitness. To do this, this method randomly picks a value
* between zero and <code>total_fit</code> (inclusive). It then
* searches for this value in <code>roulette</code>, which is an
* <code>int</code> array the same length as the number of individuals
* in <code>population</code>. Each index in <code>roulette</code>
* corresponds to an individual in the population, and each value in
* the array is the sum of the the fitness values of all the
* individuals before it, plus the fitness value of the current
* individual. A search is done on <code>roulette</code> for the
* randomly generated number. If the number is equal to or less than a
* value in the array, but greater than the value in the previous index,
* that index is selected, and the individual that corresponds to that
* index is added to the selected population.
* <P>
* Often, this function is not "selective" enough. For that reason, one
* can set the <code>threshold</code> parameter. No individual with a
* fitness function less than the threshold will be added to the new
* population. For the simple roulette behavior described above, the
* <code>threshold</code> should be set to zero. Else, it could be
* set to the average fitness, or any other arbitrary value. If it is
* set higher than the fitness of the most fit individual in this
* population, the method will enter an infinite loop.
*
* @param threshold a <code>double</code> fitness value; individuals
* fitness values below this value are guaranteed not
* to added to the <code>List</code> of selected
* individuals. This value must be less than or equal
* to the fitness of the most fit individual in the
* population, or this method will enter an infinite
* loop.
*
* @return a <code>List</code> of length equal to the size of
* the current <code>population</code> composed of
* individuals probabalistically selected from the
* current <code>population</code>
*/
public List selection(double threshold)
{
int index = 0;
int random_int = 0;
int size = population.size();
Vector selected_pop = new Vector(size);
Chromosome selected = null;
// make population
for (int i = 0; i < size; i++)
{
// roulette wheel selection
random_int = rand.nextInt(total_fit + 1);
index = Arrays.binarySearch(roulette, random_int);
if (index < 0)
{
index = Math.abs(index + 1);
}
// get selected chromosome
selected = (Chromosome)(population.get(index));
// ignore if chromosome doesn't meet fitness threshold
if (selected.get_fit() < threshold)
{
i--;
}
// else add chromosome to new selected population
else
{
selected_pop.add(selected.getCopy());
}
}
return selected_pop;
}
/**
* Accepts a <code>List</code> of <code>Chromosomes</code>, performs
* crossover and mutation operations on them with some probability,
* recomputes each <code>Chromosome</code>'s fitness value,
* recomputes the <code>total_fit</code>, <code>best_fit</code>, and
* </code>roulette</code>, and then sets the <code>population</code>
* to this <code>List</code> of new <code>Chromosome</code>.
*
* This method performs two basic functions: crossover and mutation.
* It first clears <code>total_fit</code> and <code>best_fit</code>.
* In the crossover step, the first and second <code>Chromosome</code>
* are selected for crossover, the third and fourth, etc. If there is
* an odd number in the list, the last <code>Chromosome</code> is not
* crossed. Crossover occurs only with the probability given by the
* <code>crossover_rate</code>. This method assumes that the
* elements in the input <code>List</code> were already selected
* randomly, and thus makes no effort to randomly select individuals
* from the input <code>List</code> for crossover.
* <P>
* Mutation occurs after crossover. Each element is examined and
* has a chance of being point-mutated with a probability given by
* the <code>mutation_rate</code>. After the<code>Chromosome</code>
* is or is not mutated, its fitness is recomputed and
* <code>total_fit</code>, <code>best_fit</code> and
* <code>roulette</code> are updated accordingly.
* <P>
* After the mutation step, the <code>population</code> is given the
* value of the <code>List</code> of mutated and crossed
* <code>Chromosome</code>s.
*
* @param threshold a <code>List</code> of <code>Chromosome</code>s to
* be crossed and mutated
*
* @see #crossover_rate
* @see #mutation_rate
* @see Chromosome#crossover(Chromosome, Chromosome, java.util.Random)
* @see Chromosome#mutate(Chromosome, java.util.Random)
*/
public void reproduction(List selected_pop)
{
int size = selected_pop.size();
int half_size = ((size + 1) / 2);
Chromosome parent1 = null;
Chromosome parent2 = null;
// reset fitness statistics
best_fit = 0;
total_fit = 0;
// crossover
for (int i = 1; i < half_size; i++)
{
if (rand.nextDouble() <= crossover_rate)
{
parent1 = (Chromosome)(selected_pop.get(i * 2));
parent2 = (Chromosome)(selected_pop.get((i * 2) - 1));
Chromosome.crossover(parent1, parent2, rand);
}
}
// mutation, and update fitness and roulette
for (int i = 0; i < size; i++)
{
parent1 = (Chromosome)(selected_pop.get(i));
if (rand.nextDouble() <= mutation_rate)
{
Chromosome.mutate(parent1, rand);
}
// update fitness information
total_fit = total_fit + parent1.get_fit();
best_fit = Math.max(best_fit, parent1.get_fit());
// update roulette
roulette[i] = total_fit;
}
// set the population to this new population
population = new Vector(selected_pop);
}
/**
* Creates a binary representation <code>boolean</code> array of
* an input <code>int</code>.
*
* This method makes a <code>boolean</code> array of a length
* specified by the <code>length</code> parameter, with the binary
* representation of the <code>number</code> parameter, where
* <code>true</code> represents one, and <code>false</code>
* represents zero. The least signifiant bits are at the start of
* the array, and if the number ends before the end of the array,
* subsequent bits are zero. If the length of the array is less
* than the number of bits needed to represent the input digit,
* the most significant bits past the length of the array are
* truncated.
*
* @param number an <code>int</code> to be encoded into binary
* @param length the length of the binary array
*
* @return a <code>boolean</code> array representation of
* the <code>number</code> parameter in binary
*/
public static boolean[] toBinary(int number, int length)
{
boolean result[] = new boolean[length];
for (int i = (length - 1); i >= 0; i--)
{
if ((number % 2) == 1)
{
result[i] = true;
}
else
{
result[i] = false;
}
number = (number / 2);
}
return result;
}
/**
* Evolves this evolution object through the given number of generations,
* printing the results of each generation to stdout and to a log file.
*
* This method is basically a glorified loop, with a lot of string
* manipulation for the print statements. Note that you can set the
* threshold parameter for the <code>selection</code> method in this
* method. It will loop and print out the results for the number of
* generations specifed by the parameter <code>generations</code>.
*
* @param generations an <code>int</code> number of generations to
* print results for
* @param log a <code>BufferedWriter</code> attached to a
* log file, for writing results to a log
*
* @throws IOException thrown if there is an error writing to
* the log file
*
* @see java.io.BufferedWriter
* @see #selection(double)
* @see #reproduction(java.util.List)
*/
public void evolve(int generations, BufferedWriter log) throws IOException
{
StringBuffer buffer = null;
double average = 0;
double threshold = 0;
// print header info to screen and file
buffer = new StringBuffer();
buffer.append("Generations: ");
buffer.append(generations);
buffer.append("\tPopulation Size: ");
buffer.append(population.size());
buffer.append("\tCrossover Rate: ");
buffer.append(crossover_rate);
buffer.append("\tMutation Rate: ");
buffer.append(mutation_rate);
System.out.println(buffer.toString());
log.write(buffer.toString() + "\n");
// make new generations
for (int i = 0; i <= generations; i++)
{
average = total_fit / (double)(population.size());
// print to screen
buffer = new StringBuffer();
buffer.append("Generation: ");
buffer.append(i);
buffer.append("\tBest Fitness: ");
buffer.append(best_fit);
buffer.append("\tAverage Fitness: ");
buffer.append(average);
System.out.println(buffer.toString());
// log to file
buffer = new StringBuffer();
buffer.append(i);
buffer.append("\t");
buffer.append(best_fit);
buffer.append("\t");
buffer.append(average);
buffer.append("\n");
log.write(buffer.toString());
// create new generation
threshold = 0;
reproduction(selection(threshold));
}
}
/**
* Execute method for <code>Evolution</code>.
*
* The syntax for running this method at the command line is included in
* the class comments for <code>Evolution</code>. This method takes an
* array of <code>String</code> arguments and, depending on the
* arguments, makes a new <code>Evolution</code> that uses either the
* number-of-ones or the binary number fitness function. It creates
* a log file, and then calls <code>evolve</code> to do the work. Any
* exception that is thrown in this process is caught, a stack trace is
* printed, and the program exits.
*
* @param args an array of <code>String</code> parameters from the
* command line
*
* @see #Evolution
*/
public static void main(String args[])
{
Evolution evolution = null;
int pop_size = 0;
int chromosome_size = 0;
int generations = 0;
double crossover_rate = 0;
double mutation_rate = 0;
BufferedWriter log = null;
int number = 0;
boolean[] binary = null;
try
{
// get command line parameters
pop_size = Integer.parseInt(args[1]);
chromosome_size = Integer.parseInt(args[2]);
generations = Integer.parseInt(args[3]);
crossover_rate = Double.parseDouble(args[4]);
mutation_rate = Double.parseDouble(args[5]);
log = new BufferedWriter(new FileWriter(args[6]));
if (args[0].equals("ones") && (args.length == 7))
{
evolution = new Evolution(pop_size, chromosome_size, crossover_rate, mutation_rate);
}
else if (args[0].equals("binary") && (args.length == 8))
{
number = Integer.parseInt(args[7]);
binary = Evolution.toBinary(number, chromosome_size);
evolution = new Evolution(pop_size, binary, crossover_rate, mutation_rate);
}
else
{
System.err.println("Usage: java Evolution ones <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile>");
System.err.println("Usage: java Evolution binary <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile> <binary_number>");
System.exit(1);
}
evolution.evolve(generations, log);
log.flush();
log.close();
}
catch (Exception e)
{
e.printStackTrace();
System.err.println("Usage: java Evolution ones <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile>");
System.err.println("Usage: java Evolution binary <population_size> <chromosome_size> <generations> <crossover_rate> <mutation_rate> <logfile> <binary_number>");
System.exit(1);
}
}
}
染色体.java
import java.util.*; // Random
/**
* <code>Chromosome</code> is a wrapper class for a bit vectory representing
* an individual in a population for a genetic algorithm.
*
* This class has three main functions: First, it holds the "genetic"
* information for an individual in a genetic algorithm population. This
* information takes the form of a bit vector, represented as a boolean
* array. Second, it computes and holds the fitness value for the
* individual represented by a particular instantiation of this class.
* Currently, there are two fitness functions available, which are described
* later. Finally, it provides static functions for the recombination of
* gene sequences.
*/
public class Chromosome implements Cloneable
{
/**
* the target gene sequence, if the fitness function is
* <code>binary_number</code>
*/
private boolean target[];
/**
* the bit vector representing the gene sequence
*/
private boolean genes[];
/**
* the fitness value for this <code>Chromosome</code>
*/
private int fit = 0;
/**
* Constructor for <code>Chromosomes</code> that use the
* <code>number_of_ones</code> fitness function.
*
* @param length the length of the gene sequence this
* <code>Chromosome</code> will contain
* @param rand a <code>Random</code> object
*
* @see #no_of_ones()
* @see java.util.Random
*/
public Chromosome(int length, Random rand)
{
genes = new boolean[length];
rand_sequence(rand);
// fitness = the number of ones
target = null;
fitness();
}
/**
* Constructor for <code>Chromosomes</code> that use the
* <code>binary_number</code> fitness function.
*
* @param in_target the length of the gene sequence this
* <code>Chromosome</code> will contain
* @param rand a <code>Random</code> object
*
* @see #binary_number()
* @see java.util.Random
*/
public Chromosome(boolean[] in_target, Random rand)
{
genes = new boolean[in_target.length];
rand_sequence(rand);
// fitness = closeness to a binary number
target = in_target;
fitness();
}
/**
* Returns a copy of this <code>Chromosome</code> obtained from the
* <code>clone</code> method in <code>java.lang.Object</code>.
*
* @return a new <code>Chromosome</code> object with exactly the same
* values as this <code>Chromosome</code> object
*
* @see java.lang.Object#clone()
*/
public Chromosome getCopy()
{
Chromosome copy = null;
try
{
copy = (Chromosome)(this.clone());
}
catch (Exception e)
{
e.printStackTrace();
}
return copy;
}
/**
* Returns the fitness value for this <code>Chromosome</code>.
*
* @return a non-negative <code>int</code> representing the fitness of
* this <code>Chromosome</code> object
*
* @see #fit
*/
public int get_fit()
{
return fit;
}
/**
* Prints the fitness and gene sequence of this <code>Chromosome</code>
* to stdout.
*/
public void print()
{
StringBuffer buffer = new StringBuffer();
// print fitness
buffer.append("fitness: ");
buffer.append(fit);
buffer.append("\t");
// print gene genes
buffer.append("[");
for (int i = 0; i < genes.length; i++)
{
if (genes[i])
{
buffer.append(1);
}
else
{
buffer.append(0);
}
if (i < (genes.length - 1))
{
buffer.append(" ");
}
}
buffer.append("]");
System.out.println(buffer.toString());
}
public static void crossover(Chromosome parent1, Chromosome parent2, Random rand)
{
int cross_point = rand.nextInt(parent1.genes.length);
boolean swap_buff = true;
for (int i = 0; i <= cross_point; i++)
{
swap_buff = parent1.get(i);
parent1.set(i, parent2.get(i));
parent2.set(i, swap_buff);
}
// update fitness
parent1.fitness();
parent2.fitness();
}
public static void mutate(Chromosome parent, Random rand)
{
int index = rand.nextInt(parent.genes.length);
// mutate at index
parent.set(index, !parent.get(index));
// update fitness
parent.fitness();
}
/**
* Returns the gene at <code>index</code> in <code>genes</code>.
*
* @return the <code>boolean</code> value of the gene at
* <code>index</code> in the <code>genes</code> array.
*
* @see #genes
*/
private boolean get(int index)
{
return genes[index];
}
/**
* Sets the gene at <code>index</code> in <code>genes</code>.
*
* @see #genes
*/
private void set(int index, boolean value)
{
genes[index] = value;
}
private void fitness()
{
// choose proper fitness function
if (target == null)
{
no_of_ones();
}
else
{
binary_number();
}
}
private void rand_sequence(Random rand)
{
for (int i = 0; i < genes.length; i++)
{
genes[i] = rand.nextBoolean();
}
}
private void binary_number()
{
int count = 0;
// count genes that are the same as the target
for (int i = 0; i < genes.length; i++)
{
if (genes[i] == target[i])
{
count++;
}
}
// set fitness
fit = count;
}
private void no_of_ones()
{
int count = 0;
// count genes that are true
for (int i = 0; i < genes.length; i++)
{
if (genes[i])
{
count++;
}
}
// set fitness
fit = count;
}
}