Добрый день. В последнее время решил заняться самообразованием. Решено было начать с генетических алгоритмов.

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.

Поэтому я решил, что было бы неплохо написать класс-каркас для любого ГА. Об это и будет данная статья. Предполагается, что вы уже знакомы с основами генетических алгоритмов.

Кому интресно, прошу под кат.


Код будет написан на Java.

Несмотря на то, что мы пишем каркас, нам нобходимо его тестировать. Для этого я взял классическую NP-полную задачу — задачу коммивояжёра.

Немного об архитектуре приложения:

Для представления Генома(Индивида) будем использовать long[]. Мне почему-то показался этот вариант лучше чем boolean[].

Так же нам необходим интерфейс:

public interface FitnessFunction {
	int getArity(); //Кол-во битов в геноме
	long run(long[] genom); //Собственно сама ФитнессФункция от генома. 
}


Разрабатываемый нами класс:
public class GeneticEngine{
	public GeneticEngine(FitnessFunction fitnessFunction) {...} //Конструктор
	public long[] run() {...} //Основное тело
	private void generateFirstGeneration() {...} //генерация первого поколения
	private void selection(){...} //Процедура селекци
	private void crossing() {...} //Процедура скрещивания
	private void mutation() {...} //Процедура мутации
}


Так как мы пишем «универсальный» класс, необходимо, чтобы он поддреживал разные варианты скрещивания и селекции, поэтому были добавлены 2 перечисления (Enum):
public enum SelectionType {
	TOURNEY, ROULETTE_WHEEL
}

public enum CrossingType {
	ONE_POINT_RECOMBINATION, TWO_POINT_RECOMBINATION, ELEMENTWISE_RECOMBINATION, ONE_ELEMENT_EXCHANGE
}


… и некоторые приватные поля:

private int genomLength; //Длина генома в битах
private long generationCount; //Кол-во поколений
private int individualCount; //Кол-во Геномов(Индивидов,Особей) в поколении
private SelectionType selectionType; //Тип Селекции
private CrossingType crossingType; //Тип Скрещивания
private boolean useMutation; //Использовать мутацю
private double mutationPercent; //Как часто происходит мутация

Для них есть сеттеры и геттеры.

А теперь о всем по порядку…

Генерация первого поколения.


Все очень просто: рандомом генерируем лонги, из лонгов составляем геномы и кладем их в массив. Код приводить не буду.

Селекция.

Я нашел 2 вида селекции:
  • Рулетка
  • Турнир

Процедура селекции создает новый массив Геномов.

private void selection(){	
		switch (selectionType) {
		case ROULETTE_WHEEL:{		
			float[] wheel = new float[this.individualCount];
			wheel[0] = //Значение ФитнессФункции для 1-ого генома 
			for (int i=1;i<this.individualCount;i++){
				wheel[i] = wheel[i-1] + //Значение ФитнессФункции для i-ого генома
			}
			float all = wheel[this.individualCount-1];
		
			for (int i=0;i<this.individualCount;i++){
				float index = Math.abs(this.random.nextFloat())*all;
				
				int l = 0;
				int r = individualCount-1;
				int c = 0;
				while (l < r){
				c = (l+r) >> 1;
				if (index <= while[c]){
				        r = c;
				    }else{
				        l = c + 1;
				    }
				}
				this.genomListOffsprings[i] = this.genomListParents[l].clone();
			}
			break;
		}
		case TOURNEY:{
			for (int i=0;i<this.individualCount;i++){
				int index1 = random.nextInt(individualCount);
				int index2 = random.nextInt(individualCount);
		
				long fr1 = //Значение ФитнессФункции для index1 Генома
				long fr2 = //Значение ФитнессФункции для index2 Генома

				this.genomListOffsprings[i] = fr1 > fr2 ? this.genomListParents[index1].clone() : this.genomListParents[index2].clone();
			}
			break;
		}
	}


Несколько замечаний «от себя»:

  • В процессе тестов оказалось, что большую часть выполняется ФитнессФункция (около 90% времени).
  • Применив кэширование результатов ФинессФункции на каждом поколении удалось увеличить производительность всего алгоритма в 3-4 раза.
  • В силу прдыдущих двух пунктов, Рулетка оказалась в разы худшим алгоритмом, чем Турнир.


Скрещивание.


Скрещивание бывает:
  • Одноточечная рекомбинация.
  • Двуточечная рекомбинация.
  • Поэлементное скрещивание.
  • Обмен одним геном.


Несколько замечаний «от себя»:

  • Во время тестов выяснилось, что лучше всего работает Поэлементное скрещивание. В то время как Остальные 3 алгоритма имеют одинаковую «полезность».
  • (очевидное) Обмен одним геном работает за O(1), остальные алгоритмы работают за O(L), где l — длина генома.
  • Не смотря на предыдущий пункт ВСЕ 4 алгоритма работают за примерно одинаковое время(именно время). Точнее: 90 % времени работы всего ГА занимает ФитнессФункция, на ее фоне O(1) и O(L) для скрещивания равнозначны.
  • В силу предыдущих трех пунктов наилучшим алгоритмом скрещивания считаю (я считаю) Поэлементное скрещивание.


*Для функция скрещивания и мутации я использовал бинарные операции. Поэтому пришлось объявить несколько статических перменных.

public static final int OCTET_LENGTH = 64; // Кол-во битов в лонге
public static final int MASK_FOR_MOD = OCTET_LENGTH - 1; // вместо "x%64" я использую "x & MASK_FOR_MOD"  
public static final int SHIFT_FOR_DIVISION; // вместо "x/64" - "x >> SHIFT_FOR_DIVISION"


Функция для скрещивания двух геномов:
(Приведн код только для Поэлементное Скрещивание)
private void cross(long[] genom1, long[] genom2) {
	switch (crossingType) {
	...
	case ELEMENTWISE_RECOMBINATION:{
		for (int outerOffset = 0; outerOffset < this.sizeOfArray; outerOffset++) {
			long mask = this.random.nextLong(); // какие биты менять, а какие нет (1-обмениваем битами, 0-оставляем)
			long swapMask = (genom1[outerOffset] ^ genom2[outerOffset]) & mask;

			genom1[outerOffset] ^= swapMask;
			genom2[outerOffset] ^= swapMask;
		}
		break;
	}
}


Пояснения:
Чтобы обменять между собой числа a и b необходимо:
swapMask = a xor b;
a = a xor swapMask;
b = b xor swapMask;

А если на swapMask мы наложим (and) mask, то у a и b поменяются только те биты, которые == 1 в числе mask.

swapMask = (a xor b) and mask;
a = a xor swapMask;
b = b xor swapMask;

Мутация.

private void mutation() {
	for (long[] genom : this.genomListOffsprings) {
		if (random.nextDouble() <= mutationPercent) {
			mutate(genom);
		}
	}
}

private void mutate(long[] genom) {
	int index = this.random.nextInt(this.genomLength);
	int outerOffset = index >> SHIFT_FOR_DIVISION;
	int innerOffset = (index & MASK_FOR_MOD);
	long mask = 1L << innerOffset;
	genom[outerOffset] ^= mask;
}


Чтобы инвертировать бит необходимо:
bit = bit xor 1;
Следовательно, чтобы инвертировать любой бит в числе необходимо сдвинуть единицу на нужную позицию.

«Тело».

И основная функция, которая связывает все предыдущие:

public long[] run() {
	generateFirstGeneration();
		
	while (currentGeneration < generationCount) {

		selection();
		this.crossing();
		if (useMutation) {
			mutation();
		}
			
		currentGeneration++;
	}

	return ВыбратьЛучшийГеномВТекущемПоколении.
}


Применение.

Использовать это все достаточно просто:
Сначала нужно описать класс ФитнессФункции.
А дальше…

MyFitnessFunction ff = new MyFitnessFunction();
GeneticEngine ge = new GeneticEngine(ff);
ge.setIndividualCount(1000); //устанавливаем кол-во особей в поколении
ge.setGenerationCount(10000); //устанвливаем кол-во поколений
ge.setSelectionType(SelectionType.TOURNEY); //тип селекции
ge.setCrossingType(CrossingType.ELEMENTWISE_RECOMBINATION); //тип скрещивания
ge.setUseMutation(true); //наши геномы могут мутировать
ge.setMutationPercent(0.02d); //нсколько часто мутируют геномы

long[] better = ge.run(); //запускаем


Вернемся к задаче коммивояжёра.

Так как растояние между городами заполнялось рандомом «random.nextInt(256)». То смею предположить, что среднее расстояние между 2 городами = 128. => Средняя длина маршрута по всем городам = 128*256=32768. (! могу ошибаться).

При 
IndividualCount = 100;
GenerationCount = 10000;
SelectionType = SelectionType;
CrossingType = ELEMENTWISE_RECOMBINATION;
UseMutation = true;
MutationPercent = 0.02d;

ГА находит путь = 10000-12000 за 6-7 сек. Что в 3 раза лучше Среднего.

При
IndividualCount = 1000;
GenerationCount = 10000;

5500-7000 за минуту.

При 
IndividualCount = 10000;
GenerationCount = 100000;

Код работает около 15 часов. и находит маршрут = 3500-4000.

Куда расти дальше.

  • Надеюсь, знающие люди подскажут как лучше реализовать Рулетку.
  • Можно сделать останов ГА не по кол-ву поколений, а по достижении какого-то значения ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.
  • Можно, хранить индивид с лучшей ФитнессФункцией за все поколения. Или не за все поколения, а только из тех индивидов, для которых ФитнессФункция рассчитывалась — это не будет затратно.


Ссылка на GitHub. Буду рад если кому-то пригодиться.

UPD:Код написан на Java, но я старался его писать без использования java.util, и таким образом чтобы он был похож на Си.
Чем обусловлен данный аспект:
  • Не будет оверхеда при хранении данных.
  • Код становиться легкопереносимым на Си/Си++/php/любой Си-подобный язык.
  • Быстродействию это не повредит (возможно даже немного повысит).
  • Код не станет сложнее читаться.

(в комментариях код спутали с С-шным, поэтому данную задачу считаю выполненной)

UPD2:LeoCcoder нашел ошибку в Рулетке(в бинарном поиске). Исправлено.