Генетический алгоритм - это эвристика поиска, основанная на теории естественной эволюции Чарльза Дарвина. Этот алгоритм отражает процесс естественного отбора, при котором наиболее подходящие особи отбираются для размножения, чтобы произвести потомство следующего поколения.
Понятие естественного отбора
Процесс естественного отбора начинается с отбора наиболее приспособленных особей из популяции. Они производят потомство, которое наследует характеристики родителей и будет добавлено к следующему поколению. Если родители лучше приспособлены, их дети будут лучше родителей и имеют больше шансов выжить. Этот процесс продолжает повторяться, и в конце, будет найдено поколение с самыми подходящими особями.
Это понятие может быть применено к проблеме поиска. Мы рассматриваем набор решений для проблемы и выбираем из них набор лучших.
В генетическом алгоритме рассматриваются пять фаз.
- Начальная популяция (Initial population)
- Функция пригодности (Fitness function)
- Отбор (Selection)
- Скрещивание (Crossover)
- Мутация (Mutation)
Начальная популяция
Процесс начинается с набора особей, который называется населением. Каждая особь - это решение проблемы, которую вы хотите решить.
Особь характеризуется набором параметров (переменных), известных как гены. Гены объединяются в цепочку, образуя хромосому (решение).
В генетическом алгоритме набор генов индивида представлен строкой в алфавитном порядке. Обычно используются двоичные значения (строка из 1 и 0). Мы говорим, что кодируем гены в хромосоме.
Популяция, хромосомы и гены
Функция пригодности
Функция пригодности определяет, насколько индивид подходит к решению (способность индивида конкурировать с другими индивидами). Это дает оценку пригодности для каждого индивида. Вероятность того, что индивид будет выбран для размножения, основана на его оценке пригодности.
Отбор
Идея фазы отбора состоит в том, чтобы отобрать наиболее подходящих индивидов и позволить им передать свои гены следующему поколению.
Две пары индивидуумов (родители) выбираются на основе их показателей пригодности. Индивиды с высокой пригодностью имеют больше шансов быть выбранными для размножения.
Скрещивание
Скрещивание является наиболее значимой фазой в генетическом алгоритме. Для каждой пары родителей, которые должны быть спарены, точка скрещивания выбирается из генов случайным образом.
Например, точка скрещивания может быть равна 3, как показано ниже.
Точка скрещивания
Потомки создаются путем обмена генами родителей между собой, пока не будет достигнута точка скрещивания.
Обмен генами среди родителей
Новое потомство добавляется к населению.
Новое потомство
Мутация
У определенных новых потомков некоторые из их генов могут подвергаться мутации с низкой вероятностью. Это подразумевает, что некоторые биты в битовой строке могут быть перевернуты.
Мутация: до и после
Мутация происходит для поддержания разнообразия в популяции и предотвращения преждевременной конвергенции.
Завершение
Алгоритм заканчивается, если популяция сошлась (не производит потомство, которое значительно отличается от предыдущего поколения). Далее говорят, что генетический алгоритм предоставил множество решений нашей проблемы.
Комментарии
Население имеет фиксированный размер. Когда формируются новые поколения, индивиды с наименьшей пригодностью умирают, предоставляя место для нового потомства.
Последовательность этапов повторяется, чтобы произвести индивидов в каждом новом поколении, которые лучше, чем в предыдущем поколении.
Псевдокод:
START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP
Пример реализации в Java
Ниже приведен пример реализации генетического алгоритма на Java. Не стесняйтесь поиграть с кодом.
Дан набор из 5 генов, каждый ген может содержать одно из двоичных значений 0 и 1.
Значение пригодности рассчитывается как число единиц, присутствующих в геноме. Если есть пять единиц, то он имеет максимальную пригодность. Если нет единиц, то у него минимальная пригодность.
Этот генетический алгоритм пытается максимизировать функцию пригодности, чтобы обеспечить популяцию, состоящую из наиболее приспособленных индивидуумов, то есть индивидуумов с пятью единицами.
Примечание. В этом примере после скрещивания и мутации наименее приспособленная особь заменяется на новое наиболее приспособленное потомство.
import java.util.Random;
/**
*
* @author Vijini
*/
//Main class
public class SimpleDemoGA {
Population population = new Population();
Individual fittest;
Individual secondFittest;
int generationCount = 0;
public static void main(String[] args) {
Random rn = new Random();
SimpleDemoGA demo = new SimpleDemoGA();
//Initialize population
demo.population.initializePopulation(10);
//Calculate fitness of each individual
demo.population.calculateFitness();
System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
//While population gets an individual with maximum fitness
while (demo.population.fittest < 5) {
++demo.generationCount;
//Do selection
demo.selection();
//Do crossover
demo.crossover();
//Do mutation under a random probability
if (rn.nextInt()%7 < 5) {
demo.mutation();
}
//Add fittest offspring to population
demo.addFittestOffspring();
//Calculate new fitness value
demo.population.calculateFitness();
System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
}
System.out.println("\nSolution found in generation " + demo.generationCount);
System.out.println("Fitness: "+demo.population.getFittest().fitness);
System.out.print("Genes: ");
for (int i = 0; i < 5; i++) {
System.out.print(demo.population.getFittest().genes[i]);
}
System.out.println("");
}
//Selection
void selection() {
//Select the most fittest individual
fittest = population.getFittest();
//Select the second most fittest individual
secondFittest = population.getSecondFittest();
}
//Crossover
void crossover() {
Random rn = new Random();
//Select a random crossover point
int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);
//Swap values among parents
for (int i = 0; i < crossOverPoint; i++) {
int temp = fittest.genes[i];
fittest.genes[i] = secondFittest.genes[i];
secondFittest.genes[i] = temp;
}
}
//Mutation
void mutation() {
Random rn = new Random();
//Select a random mutation point
int mutationPoint = rn.nextInt(population.individuals[0].geneLength);
//Flip values at the mutation point
if (fittest.genes[mutationPoint] == 0) {
fittest.genes[mutationPoint] = 1;
} else {
fittest.genes[mutationPoint] = 0;
}
mutationPoint = rn.nextInt(population.individuals[0].geneLength);
if (secondFittest.genes[mutationPoint] == 0) {
secondFittest.genes[mutationPoint] = 1;
} else {
secondFittest.genes[mutationPoint] = 0;
}
}
//Get fittest offspring
Individual getFittestOffspring() {
if (fittest.fitness > secondFittest.fitness) {
return fittest;
}
return secondFittest;
}
//Replace least fittest individual from most fittest offspring
void addFittestOffspring() {
//Update fitness values of offspring
fittest.calcFitness();
secondFittest.calcFitness();
//Get index of least fit individual
int leastFittestIndex = population.getLeastFittestIndex();
//Replace least fittest individual from most fittest offspring
population.individuals[leastFittestIndex] = getFittestOffspring();
}
}
//Individual class
class Individual {
int fitness = 0;
int[] genes = new int[5];
int geneLength = 5;
public Individual() {
Random rn = new Random();
//Set genes randomly for each individual
for (int i = 0; i < genes.length; i++) {
genes[i] = Math.abs(rn.nextInt() % 2);
}
fitness = 0;
}
//Calculate fitness
public void calcFitness() {
fitness = 0;
for (int i = 0; i < 5; i++) {
if (genes[i] == 1) {
++fitness;
}
}
}
}
//Population class
class Population {
int popSize = 10;
Individual[] individuals = new Individual[10];
int fittest = 0;
//Initialize population
public void initializePopulation(int size) {
for (int i = 0; i < individuals.length; i++) {
individuals[i] = new Individual();
}
}
//Get the fittest individual
public Individual getFittest() {
int maxFit = Integer.MIN_VALUE;
int maxFitIndex = 0;
for (int i = 0; i < individuals.length; i++) {
if (maxFit <= individuals[i].fitness) {
maxFit = individuals[i].fitness;
maxFitIndex = i;
}
}
fittest = individuals[maxFitIndex].fitness;
return individuals[maxFitIndex];
}
//Get the second most fittest individual
public Individual getSecondFittest() {
int maxFit1 = 0;
int maxFit2 = 0;
for (int i = 0; i < individuals.length; i++) {
if (individuals[i].fitness > individuals[maxFit1].fitness) {
maxFit2 = maxFit1;
maxFit1 = i;
} else if (individuals[i].fitness > individuals[maxFit2].fitness) {
maxFit2 = i;
}
}
return individuals[maxFit2];
}
//Get index of least fittest individual
public int getLeastFittestIndex() {
int minFitVal = Integer.MAX_VALUE;
int minFitIndex = 0;
for (int i = 0; i < individuals.length; i++) {
if (minFitVal >= individuals[i].fitness) {
minFitVal = individuals[i].fitness;
minFitIndex = i;
}
}
return minFitIndex;
}
//Calculate fitness of each individual
public void calculateFitness() {
for (int i = 0; i < individuals.length; i++) {
individuals[i].calcFitness();
}
getFittest();
}
}
Пример вывода, где наиболее подходящее решение найдено в 32-м поколении:
Комментариев нет:
Отправить комментарий