На самом деле есть один, который является общим и существует с .net 2.0. Это называется KeyedCollection
. Тем не менее, существует ограничение, заключающееся в том, что он создает ключи из значений , поэтому он не является общей коллекцией пар ключ / значение. (Хотя вы, конечно, можете использовать его как KeyedCollection
в качестве обходного пути).
Если вам нужно это как IDictionary
, у него есть свойство .Dictionary
.
Несколько более незначительная проблема, с которой я столкнулся, заключается в том, что это абстрактный класс, и вы должны создать его подкласс и реализовать:
protected abstract TKey GetKeyForItem(TItem item)
Я бы предпочел просто передать лямбду в конструктор для этого цель, но опять же, я думаю, что виртуальный метод немного быстрее, чем лямбда (любые комментарии по этому поводу приветствуются).
Редактировать Поскольку вопрос возник в комментариях: KeyedCollection
сохраняет порядок, как он наследует от Collection
, что делает (это происходит из IList
. См. также документация метода Add: Добавляет объект в конец Коллекции. ).
Ниже приводится полный обзор ГА. Я старался быть очень подробным, чтобы его можно было легко закодировать на C / Java / Python / ..
/* 1. Init population */
POP_SIZE = number of individuals in the population
pop = newPop = []
for i=1 to POP_SIZE {
pop.add( getRandomIndividual() )
}
/* 2. evaluate current population */
totalFitness = 0
for i=1 to POP_SIZE {
fitness = pop[i].evaluate()
totalFitness += fitness
}
while not end_condition (best fitness, #iterations, no improvement...)
{
// build new population
// optional: Elitism: copy best K from current pop to newPop
while newPop.size()<POP_SIZE
{
/* 3. roulette wheel selection */
// select 1st individual
rnd = getRandomDouble([0,1]) * totalFitness
for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
rnd -= pop[idx].fitness
}
indiv1 = pop[idx-1]
// select 2nd individual
rnd = getRandomDouble([0,1]) * totalFitness
for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
rnd -= pop[idx].fitness
}
indiv2 = pop[idx-1]
/* 4. crossover */
indiv1, indiv2 = crossover(indiv1, indiv2)
/* 5. mutation */
indiv1.mutate()
indiv2.mutate()
// add to new population
newPop.add(indiv1)
newPop.add(indiv2)
}
pop = newPop
newPop = []
/* re-evaluate current population */
totalFitness = 0
for i=1 to POP_SIZE {
fitness = pop[i].evaluate()
totalFitness += fitness
}
}
// return best genome
bestIndividual = pop.bestIndiv() // max/min fitness indiv
Обратите внимание, что в настоящее время вам не хватает фитнес-функции (зависит от домена). Кроссовер будет простым одноточечным кроссовером (поскольку вы используете двоичное представление). Мутация может быть простым изменением бита наугад.
РЕДАКТИРОВАТЬ : Я реализовал указанный выше псевдокод на Java с учетом вашей текущей структуры кода и обозначений (имейте в виду, что я больше сторонник ac / c ++, чем java). Обратите внимание, что это ни в коем случае не самая эффективная или полная реализация, я признаю, что написал ее довольно быстро:
Individual.java
import java.util.Random;
public class Individual
{
public static final int SIZE = 500;
private int[] genes = new int[SIZE];
private int fitnessValue;
public Individual() {}
public int getFitnessValue() {
return fitnessValue;
}
public void setFitnessValue(int fitnessValue) {
this.fitnessValue = fitnessValue;
}
public int getGene(int index) {
return genes[index];
}
public void setGene(int index, int gene) {
this.genes[index] = gene;
}
public void randGenes() {
Random rand = new Random();
for(int i=0; i<SIZE; ++i) {
this.setGene(i, rand.nextInt(2));
}
}
public void mutate() {
Random rand = new Random();
int index = rand.nextInt(SIZE);
this.setGene(index, 1-this.getGene(index)); // flip
}
public int evaluate() {
int fitness = 0;
for(int i=0; i<SIZE; ++i) {
fitness += this.getGene(i);
}
this.setFitnessValue(fitness);
return fitness;
}
}
Population.java
import java.util.Random;
public class Population
{
final static int ELITISM_K = 5;
final static int POP_SIZE = 200 + ELITISM_K; // population size
final static int MAX_ITER = 2000; // max number of iterations
final static double MUTATION_RATE = 0.05; // probability of mutation
final static double CROSSOVER_RATE = 0.7; // probability of crossover
private static Random m_rand = new Random(); // random-number generator
private Individual[] m_population;
private double totalFitness;
public Population() {
m_population = new Individual[POP_SIZE];
// init population
for (int i = 0; i < POP_SIZE; i++) {
m_population[i] = new Individual();
m_population[i].randGenes();
}
// evaluate current population
this.evaluate();
}
public void setPopulation(Individual[] newPop) {
// this.m_population = newPop;
System.arraycopy(newPop, 0, this.m_population, 0, POP_SIZE);
}
public Individual[] getPopulation() {
return this.m_population;
}
public double evaluate() {
this.totalFitness = 0.0;
for (int i = 0; i < POP_SIZE; i++) {
this.totalFitness += m_population[i].evaluate();
}
return this.totalFitness;
}
public Individual rouletteWheelSelection() {
double randNum = m_rand.nextDouble() * this.totalFitness;
int idx;
for (idx=0; idx<POP_SIZE && randNum>0; ++idx) {
randNum -= m_population[idx].getFitnessValue();
}
return m_population[idx-1];
}
public Individual findBestIndividual() {
int idxMax = 0, idxMin = 0;
double currentMax = 0.0;
double currentMin = 1.0;
double currentVal;
for (int idx=0; idx<POP_SIZE; ++idx) {
currentVal = m_population[idx].getFitnessValue();
if (currentMax < currentMin) {
currentMax = currentMin = currentVal;
idxMax = idxMin = idx;
}
if (currentVal > currentMax) {
currentMax = currentVal;
idxMax = idx;
}
if (currentVal < currentMin) {
currentMin = currentVal;
idxMin = idx;
}
}
//return m_population[idxMin]; // minimization
return m_population[idxMax]; // maximization
}
public static Individual[] crossover(Individual indiv1,Individual indiv2) {
Individual[] newIndiv = new Individual[2];
newIndiv[0] = new Individual();
newIndiv[1] = new Individual();
int randPoint = m_rand.nextInt(Individual.SIZE);
int i;
for (i=0; i<randPoint; ++i) {
newIndiv[0].setGene(i, indiv1.getGene(i));
newIndiv[1].setGene(i, indiv2.getGene(i));
}
for (; i<Individual.SIZE; ++i) {
newIndiv[0].setGene(i, indiv2.getGene(i));
newIndiv[1].setGene(i, indiv1.getGene(i));
}
return newIndiv;
}
public static void main(String[] args) {
Population pop = new Population();
Individual[] newPop = new Individual[POP_SIZE];
Individual[] indiv = new Individual[2];
// current population
System.out.print("Total Fitness = " + pop.totalFitness);
System.out.println(" ; Best Fitness = " +
pop.findBestIndividual().getFitnessValue());
// main loop
int count;
for (int iter = 0; iter < MAX_ITER; iter++) {
count = 0;
// Elitism
for (int i=0; i<ELITISM_K; ++i) {
newPop[count] = pop.findBestIndividual();
count++;
}
// build new Population
while (count < POP_SIZE) {
// Selection
indiv[0] = pop.rouletteWheelSelection();
indiv[1] = pop.rouletteWheelSelection();
// Crossover
if ( m_rand.nextDouble() < CROSSOVER_RATE ) {
indiv = crossover(indiv[0], indiv[1]);
}
// Mutation
if ( m_rand.nextDouble() < MUTATION_RATE ) {
indiv[0].mutate();
}
if ( m_rand.nextDouble() < MUTATION_RATE ) {
indiv[1].mutate();
}
// add to new population
newPop[count] = indiv[0];
newPop[count+1] = indiv[1];
count += 2;
}
pop.setPopulation(newPop);
// reevaluate current population
pop.evaluate();
System.out.print("Total Fitness = " + pop.totalFitness);
System.out.println(" ; Best Fitness = " +
pop.findBestIndividual().getFitnessValue());
}
// best indiv
Individual bestIndiv = pop.findBestIndividual();
}
}
Обратите внимание, что в некоторых случаях вы можете сделать что-то вроде с лямбда-выражениями, скомпилировав их в дерево Expression
, а не в делегат ( что является обманом, но может быть достаточно, чтобы помочь):
Expression<Func<char, int, string>> func
= (c, i) => new string(c, i);
Console.WriteLine(func); // writes: (c, i) => new String(c, i)
var del = func.Compile();
string s = del('a', 5);
Console.WriteLine(s); // writes: aaaaa
Обратите внимание, что деревья выражений .NET 4.0 могут инкапсулировать тела операторов в соответствии с исходным вопросом (обсуждаемым в конце этой статьи ), но Компилятор C # не поддерживает компиляцию кода C # в такие выражения (вам нужно делать это сложным способом).
и затем можно повторно использовать его несколько раз для выполнения выбора за O (log N) времени.Кроме того, обратите внимание, что выбор турнира намного проще реализовать!
Эти другие вопросы о выборе колеса рулетки должны помочь:
В первом, I ' Я пытался объяснить , как работает колесо рулетки. Во втором, Джарод Эллиотт предоставил некоторый псевдокод . В сочетании с описанием эффективной реализации Адамски , этого должно быть достаточно, чтобы что-то заработало.
Идея, которую вы ищете, называется «выбор колеса рулетки». У вас еще нет установленной функции приспособленности (вы можете иметь в виду, что приспособленность каждого человека является интегральной ценностью его хромосомы), но когда вы составляете общий план, просуммируйте приспособленность всей популяции.
Существуют и другие эквивалентные реализации, но общая идея состоит в том, чтобы выбрать элементы с вероятностью, пропорциональной их пригодность.
Править: Несколько замечаний по фитнес-функциям. Представление хромосомы (в вашем случае как 32-битное целое число) не зависит от функции пригодности, используемой для ее оценки. Например, при двоичном кодировании хромосома обычно рассматривается как набор битовых полей, упакованных в целое значение соответствующего размера. Затем кроссовер и мутация могут быть выполнены соответствующими операциями битовой маскировки. Если вам интересно, я могу опубликовать простой код GA, который у меня есть (на C и Python), который использует побитовые операции для реализации этих функций. Я не уверен, насколько вы комфортно владеете этими языками.
Просто момент, который стоит упомянуть. Выбор колеса рулетки (как указано в псевдокоде) не будет работать для задач минимизации - однако, он действителен для задач максимизации.
Из-за способа, которым выбирается наиболее подходящий индивидуум, случай минимизации не работает. Подробности приведены в: Вычислительный интеллект: 2-е издание
Почему бы не использовать фреймворк с открытым исходным кодом, например JGAP: http://jgap.sf.net