Генетические алгоритмы. От теории к практике

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

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 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 нашел ошибку в Рулетке(в бинарном поиске). Исправлено.
Поделиться публикацией

Похожие публикации

Комментарии 36

    0
    Подсветку кода сделайте пожалуйста, читать трудно. :)
      +1
      Готово.
      0
      И поправьте в статье к какому языку вы привязываетесь, видно что к Си, но… всякое бывает…
        0
        Я тоже сначала подумал что Си, а потом в тегах увидел java… :))
      • НЛО прилетело и опубликовало эту надпись здесь
          +1
          Зачем изобретать велосипед? есть же библиотеки для этого…

          вот это место непойдет:
          while (l!=r){
          c = (l+r) >> 1;
          if (wheel[c]<index){
          l=c;
          }else{
          r=c;
          }
          }

          задача бинарным поиском найти максимальный индекс элемента в массиве wheel, значение которого меньше переменной index

          а вы находите непонятно что, вы смотрите только элементы в середине отрезков, и если значение элемента в середине предыдущего отрезка меньше, а в середине следующего отрезка больше index, вы считаете, что середина предыдущего отрезка это наш искомый элемент и берете его индекс… но это неправильно, это не рулетка.

          а еще эта штука иногда зацикливается, например если:
          wheel = [1; 1000];
          r = 1; l =0; index = 900; c =0;
          то из вашего while мы никогда не выйдем
            +1
            спасибо. Код должен быть таким:
            while (l < r){
            	c = (l+r) >> 1;
            	if (index <= while[c]){
            		r = c;
            	}else{
            		l = c + 1;
            	}
            }
            –1
            «ложим их в массив.»
            Неужели теперь так можно говорить/писать?
              +3
              Нельзя, но зачем «палить» автора в комментариях? Для этого вполне подойдут личные сообщения. Автор бы быстро всё исправил и никто бы больше не заметил эту ошибку.
                0
                Простите, я новичок здесь. В следующий раз именно так и сделаю.
              0
              Можете пояснить, какую роль в вашем коде играют переменные, которые вы называете innerOffset и outerOffset и во всех местах используете одинаковым способом? Почему они являются результатами операций от деления на длину лонга в битах и взятия остатка, но используются для сдвига маски и указания индекса в массиве лонгов, из которых состоит геном?
                0
                Биты в гене храняться в таком виде (в данном случае для простоты считаю, что кол-во бит, отведенных под long, равно 8):

                Если нам нужно получить доступ к 15 биту, то outerOffset будет указывать в каком long'е хранится бит, а innerOffset в какой позиции в long'e стоит этот бит.
                int index =  15;
                outerOffset = index / LENGTH_OF_LONG; //  == 15/8 == 1
                innerOffset = index % LENGTH_OF_LONG - 1; // == 15 % 8 - 1 == 7 - 1 == 6 (!)нумерация начинается с 0


                А бинарные сдвиги и && заменяют целочисленное деление и взятие остатка от деления, так как выполняются быстрее.
                  0
                  Понял, просто не вник сначала, что это подсчет номера бита. Про битовые операции я в курсе. Спасибо!
                    0
                    Из статьи неясно как Вы кодируете/декодируете последовательность обхода городов коммивояжером. Как нолики и единицы хромосомы становятся номерами городов?
                  0
                  Насколько я знаю, в генетических алгоритмах мутация необходима, иначе в общем случае алгоритм, хоть и сходится, но не факт, что к решению. Поэтому думаю, что нет необходимости в
                  private boolean useMutation; //Использовать мутацю


                  Поправьте меня, если не прав.
                    0
                    Да, без использования мутации невозможно 100% получить все возможные комбинации. Но «private boolean useMutation;» — не сильно влияет на производительность, и если вдруг нам захочется НЕ использовать мутацию, то это будет легко сделать, установив нужный флаг в false.
                    0
                    Насколько я помню в DE алгоритмах у нас 3 вероятности:
                    probability pi_1: z1[i] < — N(0, sigm1) else z1[i] < — 0
                    probability pi_2: z2[i] < — N(0, sigm2) else z2[i] < — 0
                    probability pi: NEW_POPULATION(p, i) = POPULATION(c1, i) + (F + z1) * (POPULATION(c2, i) — POPULATION(c3, i) + z2) else NEW_POPULATION(p, i) = POPULATION(c1, i)

                    тоесть с вероятностями pi_1, pi_2 генерируются вектора характеризающие мутацию, и с вероятностью pi мутация переносится в следующее поколение, собственно вопрос:

                    Подскажите, где у вас pi_1, pi_2 или я описываю нечто другое?
                      0
                      Я использую вариант проще: есть вероятность мутации, если random.nextDouble() > процентМутации, то один бит инвертируется.
                      Не могли бы вы подробно описать свой вариант? Или кинуть линку на описание?
                        0
                        Использовал алгоритм дифференциальной эволюции, только в качестве критерия остановки эволюции было задано число повторений. Идея в том что у нас есть некоторый вектор изменяя который нужно добиться оптимизации некоторой функции.
                        В процессе эволюции мы к имеющемуся вектору прибавляем еще 2 случайных вектора с некоторым потоянным смещением F
                          0
                          Из вики:
                          Дифференциа́льная эволю́ция — метод многомерной математической оптимизации, относящийся к классу стохастических алгоритмов оптимизации и использующий некоторые идеи генетических алгоритмов.

                          Я так понял диффернциальныя эволюция это немного другой алгоритм, хотя и очень похожий на ГА.
                      0
                      Я просто оставлю это здесь:
                      Ген репарации комплементарных повреждений ДНК в результате рентгеновского излучения у китайских хомячков
                      www.genepassport.ru/base?GenID=114
                        +2
                        1. Количество орфографических и грамматических ошибок зашкаливает. «Ложим в массив», блин. Курите учебники русского языка.
                        2. Хромосома — это абсолютно не обязательно вектор из нулей и единиц.
                        3. Из п. 2 — операции селекции, скрещивания и мутации сильно зависят от конкретной задачи и стандартизированы быть не могут.
                        4. Перечисления и свитчи по ним для изменения поведения класса — «эта пять». Курите «Рефакторинг» Фаулера и SOLID.
                        5. index1, index2, fr1, fr2 — вообще без комментариев. Использовать именования типа target, source и так далее не судьба?
                        6. Терминология — откуда вы ее взяли?

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

                            Например: первые три бита — число, следущие (14*8) бит представляют собой строку из 14 символов, и в конце еще 2 бита, которые трактуются как 2 boolean'а.

                            В моей реализации фитнесс функции. Каждые 8 бит составляют число, таким образом в одном лонге хранится 8 чисел.
                              0
                              И вот тут засада. В бинарном кодировании рекомендуют использовать такое кодирование, при котором изменение одного бита не приведет к радикальному изменению свойства гена (в терминах ГА — метрика хромосомы изменится незначительно). Поэтому рекомендуют при бинарном кодировании использовать код Грея, т.к. он более стабилен в этом отношении. И поэтому же кодирование битами вещественных параметров (float/double) вообще неприемлемо — эффект от мутаций да и от кроссовера будет слишком непредсказуемым/нестабильным. Представьте себе изменение показателя степени в два раза.

                              В ГА важна стабильность паттернов — близкие паттерны должны давать схожее поведение особи. А при двоичном кодировании флотов получится очень нестабильная эволюция.
                                0
                                кодирование битами вещественных параметров (float/double) вообще неприемлемо — эффект от мутаций да и от кроссовера будет слишком непредсказуемым/нестабильным.


                                очень ценное замечание. спасибо.

                                Хотя в принципе и любой float можно закодировать, использую код Грея. Или это будет очень ресурсоемко?
                                  0
                                  В литературе написано, что кодек Бин <-> Грей действительно снижает производительность. Но как я понял, это в отношении к просто бинарному кодированию. Тут главный недостаток Грея и в то же время может и достоинство — квантование значений. Т.е. кодом Грея мы по сути снижаем количество значений, снижаем разрядность вещественного числа. Если я ничего не путаю.
                                  С другой стороны при кодировании вещественными векторами разрядность ограничивается лишь выбранным представлением вещественного типа. Тут имеем у флотов/даблов плавающее квантование (из-за представления числа в виде целой части + дробной + мантиссы), либо меньший диапазон допустимых значений при использовании предстваления с фиксированной точкой. Таким образом пространсво поиска разрастается неимоверно. К тому же кросовер и мутация становятся арифметическими. Так что вещественное кодирование легче привязывается к задачам цифровой обработки сигналов, но более ресурсоемкая при прочих ваных условиях.
                                  Однако бывает (как в моем случае), что вещественное кодирование позволяет резко сократить количество параметров (длину хромосом), что может дать ощутимый профит.

                                  Мое словоблудство расценивайте как очередной довод о том, что универсальный фреймворк для ГА — слишком сложно и нецелесообразно. ИМХО.
                                    0
                                    Кодирование числа с плавающей точкой давно уже описано в литературе. Если коротко, то выбирается допустимый диапазон значений float, разбивается на N интервалов таким образом, чтобы два соседних интервала давали приблизительно одинаковое значение фитнес-функции. Тогда число с плавающей точкой однозначно отображается в номер интервала. И наоборот, по номеру интервала можно вернуться к значению с плавающей точкой. Теоретически N можно сделать бесконечно большим, чтобы дискретность числа с плавающей точкой была незаметна, но тогда увеличивается длина хромосомы, что увеличивает алгоритмическую сложность задачи. Поэтому N выбирается с умом.
                                    Теперь о практике. Я реализовывал генетический алгоритм применительно к дискретной задаче о рюкзаке. Но я его вдоль и поперек исследовал и для непрерывных функций. Результаты превзошли все мои ожидания. Для сложных целевых функций генетический алгоритм всегда выдавал абсолютный экстремум. Если попытаться решать ту же задачу градиентным спуском, то хотя и не будет потерь на кодировании/декодировании хромосомы, но гарантии нахождения абсолютного экстремума нет.
                            0
                            > Можно сделать останов ГА не по кол-ву поколений, а по достижении какого-то значения
                            > ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.

                            Критериев останова разных тоже много и они тоже сильно зависят от конкретных задач.
                              0
                              Привели бы парочку примеров, думаю никто б не отказался.
                                0
                                1. Кол-во поколений.
                                2. Истечение какого-либо реального времени.
                                3. Квадрат разности фитнесс-функций лучших особей двух последних поколений меньше заданного значения.
                                4. Все особи в поколении отличаются друг от друга в рамках заданной погрешности.
                                5. Фитнесс-функция достигла некоего заданного значения (не всегда нужно оптимальное решение, иногда хватает «достаточного»).
                                и т. д.
                              0
                              А где практика, если это решение стандартной абстрактной задачи ;).
                                0
                                Копипаста вам из вики:

                                Генетические алгоритмы применяются для решения следующих задач:
                                Оптимизация функций
                                Оптимизация запросов в базах данных
                                Составление расписаний
                                Игровые стратегии


                                Алгоритм крайне просто применить к этим практическим задачам, надо только задать параметры алгоритма и интерпретировать результат.
                                  0
                                  Вот как раз ради этого я и полез читать данную статью. Мне кажется, то, что описано тут — можно найти в других статьях/учебниках и закодить с минимальными усилиями. А вот собственно то, как генетический алгоритм помогает решить именно задачу коммивояжера (или любую другую задачу), как геном влияет на алгоритм решения — непонятно.
                                  Ясно, что какого-то общего влгоритма не существует, и для каждой задачи параметры будут обозначать что-то свое, но мне кажется, что как раз такая привязка ГА к конкретной задаче и есть самое интересное и полезное.
                                    0
                                    С вами согласен, тоже хотел бы прочесть про решение конкретной задачи с помощью этого метода на хабре
                                      0
                                      Вот пример моего использования ГА. Но там ГА с вещественным кодированием — сильно отличается от того что здесь изложено.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое