Добрый день. В последнее время решил заняться самообразованием. Решено было начать с генетических алгоритмов.
Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрешивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.
Поэтому я решил, что было бы неплохо написать класс-каркас для любого ГА. Об это и будет данная статья. Предполагается, что вы уже знакомы с основами генетических алгоритмов.
Кому интресно, прошу под кат.
Несмотря на то, что мы пишем каркас, нам нобходимо его тестировать. Для этого я взял классическую 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> 1;
if (wheel[c]<index){
l=c;
}else{
r=c;
}
}
this.genomListOffsprings[i] = this.genomListParents[l].clone();
}
break;
}
case TOURNEY:{
for (int i=0;i 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() > 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 Средняя длина маршрута по всем городам = 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.
Куда расти дальше.
Надеюсь, знающие люди подскажут как лучше реализовать Рулетку.
Можно сделать останов ГА не по кол-ву поколений, а по достижении какого-то значения ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.
Можно, хранить индивид с лучшей ФитнессФункцией за все поколения. Или не за все поколения, а только из тех индивидов, для которых ФитнессФункция рассчитывалась — это не будет затратно.
Код. Буду рад если кому-то пригодиться.
