Генетический алгоритм является поиск эвристическим , который вдохновлен теорией Чарльза Дарвина естественной эволюции. Этот алгоритм отражает процесс естественного отбора, в котором наиболее приспособленные лица выбираются для воспроизведения, чтобы произвести потомство следующего поколения.
Понятие естественного отбора
Процесс естественного отбора начинается с отбора наиболее приспособленных людей из популяции. Они производят потомство, которое наследует характеристики родителей и будет добавлено к следующему поколению. Если у родителей лучше фитнес, их дети будут лучше родителей и имеют больше шансов на выживание. Этот процесс продолжает повторяться, и в конце будет найдено поколение с наиболее приспособленными людьми.
Это понятие может быть применено для поиска. Мы рассмотрим набор решений для задачи и выберем из них множество лучших.
Пять фаз рассматриваются в генетическом алгоритме.
- Первоначальное население
- Фитнес-функция
- выбор
- Кроссовер
- перегласовка
Начальное население
Процесс начинается с набора людей, который называется населением . Каждый человек является решением проблемы, которую вы хотите решить.
Индивидуум характеризуется набором параметров (переменных), известных как Гены . Гены объединяются в цепочку, образуя хромосому (решение).
В генетическом алгоритме множество генов индивида представляется с использованием строки в терминах алфавита. Обычно используются двоичные значения (строка из 1s и 0s). Мы говорим, что мы кодируем гены в хромосоме.
Фитнес-функция
Функция фитнеса определяет, насколько подходит человек (способность человека конкурировать с другими людьми). Это дает каждому человеку индивидуальную оценку . Вероятность того, что человек будет выбран для воспроизведения, основывается на его счете пригодности.
выбор
Идея фазы выбора состоит в том, чтобы выбрать наиболее приспособленных людей и позволить им передавать свои гены следующему поколению.
Две пары индивидуумов ( родителей ) выбираются на основе их оценок пригодности. Лица с высокой степенью пригодности имеют больше шансов быть выбранными для воспроизведения.
Кроссовер
Кроссовер — наиболее значимая фаза генетического алгоритма. Для каждой пары родителей, которые должны быть сопряжены, точка кроссовера выбирается случайным образом изнутри генов.
Например, рассмотрите точку кроссовера как 3, как показано ниже.
Потомство создается путем обмена генами родителей между собой, пока точка пересечения не будет достигнута.
Новое потомство добавляется к населению.
перегласовка
У некоторых новых потомков некоторые из их генов могут быть подвергнуты мутации с низкой случайной вероятностью. Это означает, что некоторые биты в битовой строке могут быть перевернуты.
Мутация происходит для сохранения разнообразия внутри населения и предотвращения преждевременной конвергенции.
прекращение
Алгоритм завершается, если совокупность сходится (не производит потомство, существенно отличающееся от предыдущего поколения). Затем говорится, что генетический алгоритм предоставил множество решений нашей проблемы.
Комментарии
Население имеет фиксированный размер. По мере формирования новых поколений люди с наименьшей пригодностью умирают, обеспечивая пространство для нового потомства.
Последовательность фаз повторяется, чтобы произвести людей в каждом новом поколении, которые лучше, чем предыдущее поколение.
Psuedocode
СТАРТ Генерировать начальное население. Вычислить фитнес. ПОВТОР. Выбор. Кроссовер. Мутация. Вычислить фитнес. UNTIL население сходится. STOP.
Пример внедрения в Java
Ниже приведен пример реализации генетического алгоритма в Java. Не стесняйтесь играть с кодом.
Учитывая набор из 5 генов, каждый ген может содержать одно из двоичных значений 0 и 1.
Значение пригодности рассчитывается как количество 1s, присутствующих в геноме. Если есть пять 1 с, то он имеет максимальную пригодность. Если нет 1s, то он имеет минимальную пригодность.
Этот генетический алгоритм пытается максимизировать функцию фитнеса, чтобы обеспечить население, состоящее из наиболее приспособленного человека, т.е. людей с пятью 1 сек.
Примечание. В этом примере, после кроссовера и мутации, наименее подходящий индивидуум заменяется на новое наиболее приспособленное потомство.
| import java.util.Random ; | |
| / ** | |
| * | |
| * @author Vijini | |
| * / | |
| // Основной класс | |
| открытый класс SimpleDemoGA { | |
| Население населения = новое Население (); | |
| Индивидуальные приспособления; | |
| Индивидуальный secondFittest; | |
| int generationCount = 0 ; | |
| public static void main ( String [] args ) { | |
| Случайный rn = новый Random (); | |
| SimpleDemoGA demo = новый SimpleDemoGA (); | |
| // Инициализация населения | |
| демо . населения . initializePopulation ( 10 ); | |
| // Рассчитайте пригодность каждого человека | |
| демо . населения . calculateFitness (); | |
| Система . из . Println ( « Поколение: « + демо . generationCount + « Fittest: « + демо . населения . приспособленного); | |
| // В то время как население получает человека с максимальной пригодностью | |
| в то время как (demo . population . fittest < 5 ) { | |
| ++ demo . generationCount; | |
| // Делаем выбор | |
| демо . выбор (); | |
| // Делаем кроссовер | |
| демо . кроссовер (); | |
| // Делаем мутацию при случайной вероятности | |
| if (rn . nextInt () % 7 < 5 ) { | |
| демо . Мутация (); | |
| } | |
| // Добавить наиболее приспособленное потомство к популяции | |
| демо . addFittestOffspring (); | |
| // Вычисление нового значения пригодности | |
| демо . населения . calculateFitness (); | |
| Система . из . Println ( « Поколение: « + демо . generationCount + « Fittest: « + демо . населения . приспособленного); | |
| } | |
| Система . из . println ( » \ n Решение найдено в генерации « + demo . generationCount); | |
| Система . из . Println ( « Фитнес: « + демо . населения . getFittest () . фитнес); | |
| Система . из . print ( « Гены: » ); | |
| for ( int i = 0 ; i < 5 ; i ++ ) { | |
| Система . из . print (demo . population . getFittest () . гены [i]); | |
| } | |
| Система . из . println ( » « ); | |
| } | |
| // Выбор | |
| void selection () { | |
| // Выберите наиболее подходящего человека | |
| fittest = население . getFittest (); | |
| // Выбор второго наиболее приспособленного человека | |
| secondFittest = население . getSecondFittest (); | |
| } | |
| // Кроссовер | |
| void crossover () { | |
| Случайный rn = новый Random (); | |
| // Выбор случайной точки пересечения | |
| int crossOverPoint = rn . nextInt (население . лица [ 0 ] . geneLength); | |
| // Обмен значениями среди родителей | |
| for ( int i = 0 ; i < crossOverPoint; i ++ ) { | |
| int temp = сильнейший . гены [I]; | |
| сильнейший . гены [i] = secondFittest . гены [I]; | |
| secondFittest . гены [i] = temp; | |
| } | |
| } | |
| // Мутация | |
| void mutation () { | |
| Случайный rn = новый Random (); | |
| // Выберите случайную точку мутации | |
| int mutationPoint = rn . nextInt (население . лица [ 0 ] . geneLength); | |
| // Отбрасываем значения в точке мутации | |
| если (сильнейшие . гены [mutationPoint] == 0 ) { | |
| сильнейший . гены [mutationPoint] = 1 ; | |
| } else { | |
| сильнейший . гены [mutationPoint] = 0 ; | |
| } | |
| mutationPoint = rn . nextInt (население . лица [ 0 ] . geneLength); | |
| if (secondFittest . genes [mutationPoint] == 0 ) { | |
| secondFittest . гены [mutationPoint] = 1 ; | |
| } else { | |
| secondFittest . гены [mutationPoint] = 0 ; | |
| } | |
| } | |
| // Получите самое сильное потомство | |
| Индивидуальный getFittestOffspring () { | |
| если (сильнейший . fitness > secondFittest . fitness) { | |
| возвращение наиболее приспособлено; | |
| } | |
| return secondFittest; | |
| } | |
| // Замените наименее приспособленного человека из наиболее подходящего потомства | |
| void addFittestOffspring () { | |
| // Обновляем значения пригодности потомства | |
| сильнейший . calcFitness (); | |
| secondFittest . calcFitness (); | |
| // Получить индекс наименее подходящего индивидуального | |
| int minimumFittestIndex = совокупность . getLeastFittestIndex (); | |
| // Замените наименее приспособленного человека из наиболее подходящего потомства | |
| населения . индивидуумы [наименьшее FittestIndex] = getFittestOffspring (); | |
| } | |
| } | |
| // Индивидуальный класс | |
| class Individual { | |
| int fitness = 0 ; | |
| int [] genes = new int [ 5 ]; | |
| int geneLength = 5 ; | |
| public Individual () { | |
| Случайный rn = новый Random (); | |
| // Устанавливаем гены случайным образом для каждого человека | |
| для ( Int я = 0 ; я < гены . длины; я ++ ) { | |
| гены [i] = Math . abs (rn . nextInt () % 2 ); | |
| } | |
| фитнес = 0 ; | |
| } | |
| // Вычислить пригодность | |
| public void calcFitness () { | |
| фитнес = 0 ; | |
| for ( int i = 0 ; i < 5 ; i ++ ) { | |
| if (гены [i] == 1 ) { | |
| ++ фитнес; | |
| } | |
| } | |
| } | |
| } | |
| // Класс популяции | |
| класс Население { | |
| int popSize = 10 ; | |
| Индивидуальные [] индивидуалы = новые лица [ 10 ]; | |
| int fittest = 0 ; | |
| // Инициализация населения | |
| public void initializePopulation ( int size ) { | |
| for ( int i = 0 ; i < индивиды . length; i ++ ) { | |
| индивиды [i] = new Individual (); | |
| } | |
| } | |
| // Получите наиболее подходящего человека | |
| public Individual getFittest () { | |
| int maxFit = Целое число . MIN_VALUE ; | |
| int maxFitIndex = 0 ; | |
| for ( int i = 0 ; i < индивиды . length; i ++ ) { | |
| if (maxFit <= индивиды [i] . фитнес) { | |
| maxFit = индивиды [i] . фитнес; | |
| maxFitIndex = i; | |
| } | |
| } | |
| fittest = индивидуумы [maxFitIndex] . фитнес; | |
| возвращение лиц [maxFitIndex]; | |
| } | |
| // Получите второго наиболее приспособленного человека | |
| public Individual getSecondFittest () { | |
| int maxFit1 = 0 ; | |
| int maxFit2 = 0 ; | |
| for ( int i = 0 ; i < индивиды . length; i ++ ) { | |
| если (индивидуумы [i] . fitness > индивидуумы [maxFit1] . fitness) { | |
| maxFit2 = maxFit1; | |
| maxFit1 = i; | |
| } else if (индивиды [i] . fitness > индивидуумы [maxFit2] . fitness) { | |
| maxFit2 = i; | |
| } | |
| } | |
| возвращение лиц [maxFit2]; | |
| } | |
| // Получить индекс наименее приспособленных | |
| public int getLeastFittestIndex () { | |
| int minFitVal = Целое число . MAX_VALUE ; | |
| int minFitIndex = 0 ; | |
| for ( int i = 0 ; i < индивиды . length; i ++ ) { | |
| if (minFitVal > = индивидуалы [i] . fitness) { | |
| minFitVal = индивиды [i] . фитнес; | |
| minFitIndex = i; | |
| } | |
| } | |
| return minFitIndex; | |
| } | |
| // Рассчитайте пригодность каждого человека | |
| public void calculateFitness () { | |
| for ( int i = 0 ; i < индивиды . length; i ++ ) { | |
| лиц [i] . calcFitness (); | |
| } | |
| getFittest (); | |
| } | |
| } | |
