В этой статье я постараюсь дать вам представление о том, как работает генетический алгоритм, и мы реализуем генетический алгоритм для оптимизации функций. Итак, начнем.
Генетический алгоритм - это метод оптимизации на основе поиска. Его часто используют для поиска оптимального или ближайшего оптимального решения. Его представил Джон Холланд. Он основан на теории естественного отбора Дарвина. Прежде чем объяснять, как работает генетический алгоритм, позвольте мне сначала объяснить теорию Дарвина о естественном отборе. В своей теории он определил естественный отбор как принцип, по которому каждое небольшое изменение [признака], если оно полезно, сохраняется. Идея была проста, но действенна: люди, лучше всего адаптированные к окружающей среде, имеют больше шансов выжить и размножаться. [Википедия] Иногда эту теорию описывают как выживание наиболее приспособленных. У тех, кто лучше других, есть шанс выжить в этой эволюции. Все дело в генетическом алгоритме. Он имитирует процесс естественного отбора, чтобы найти лучшее решение.
В генетике мы будем использовать некоторые биологические термины, такие как популяция, хромосома, ген, отбор, кроссовер, мутация. Теперь, прежде всего, давайте попробуем понять, что означают эти термины.
Население, Хромосома, Ген
В начале этого процесса нам нужно инициализировать некоторые возможные решения этой проблемы. Население - это подмножество всех возможных решений данной проблемы. По-другому можно сказать, что популяция - это набор хромосом. Хромосома - одно из решений текущей проблемы. И каждая хромосома - это набор генов.
Для простоты мы можем описать хромосому как строку. Итак, мы можем сказать, что совокупность - это набор некоторой строки (каждый символ - это двоичное значение, 0 или 1). И каждый символ строки - это ген.
Чтобы запустить процесс генетического алгоритма, нам сначала нужно инициализировать популяцию. Мы можем инициализировать популяцию двумя способами. Первый случайный, а второй эвристический. Всегда лучше начинать алгоритм с некоторой случайной совокупности.
Фитнес-функция
После инициализации популяции нам нужно рассчитать значение приспособленности этих хромосом. Теперь вопрос в том, что это за функция пригодности и как она вычисляет значение приспособленности.
В качестве примера предположим, что у нас есть уравнение f (x) = -x² + 5. Нам нужно решение, для которого оно имеет максимальное значение и ограничение 0≤x≤31.
Теперь давайте представим, что у нас есть случайная популяция из четырех хромосом, как показано ниже. Длина нашей хромосомы равна 5, так как 2⁵ = 32 и 0≤x≤31.
Наша фитнес-функция рассчитает функциональную ценность каждой хромосомы, как указано в формулировке задачи:
Для 1-й хромосомы 01110 означает 14 в целом числе. Итак, f (x) = - (14 * 14) + 5 = -191.
Для 2-й хромосомы 10101 означает 21 целое число. Итак, f (x) = - (21 * 21) + 5 = -436.
Для 3-й хромосомы 00011 означает целое число 3. Итак, f (x) = - (3 * 3) + 5 = -4.
Для 4-й хромосомы 10111 означает 23 целым числом. Итак, f (x) = - (23 * 23) + 5 = -524.
Родительский выбор
Отбор родителей осуществляется с использованием значений пригодности хромосом, рассчитанных функцией приспособленности. На основе этих значений пригодности нам нужно выбрать пару хромосом с наивысшим значением приспособленности.
Есть много способов расчета пригодности, например, выбор колеса рулетки, выбор ранга.
При выборе колеса рулетки хромосома с наивысшим значением пригодности имеет максимальную вероятность быть выбранной в качестве родительской. Но в этом процессе выбора можно выбрать более низкую.
При ранжировании хромосомы ранжируются в зависимости от их пригодности от более высокого к низкому. Например, в соответствии со значениями пригодности, рассчитанными выше, мы можем расположить эти хромосомы в порядке от более высокого к более низкому, например, 3-я ›1-я› 2-я ›4-я. Таким образом, на этапе выбора 3-я и 1-я хромосомы будут выбраны на основе оценки пригодности, рассчитанной на основе функции приспособленности.
Кроссовер
Кроссовер используется для изменения программирования хромосом от поколения к поколению путем создания детей или потомков. Родительские хромосомы используются для создания этих потомков (сгенерированных хромосом).
Для создания потомков есть несколько способов, например одноточечный кроссовер, двухточечный или многоточечный кроссовер.
Для одноточечного кроссовера нам сначала нужно выбрать точку, а затем обменять эти части, разделенные этой точкой, между родительскими хромосомами, чтобы создать потомство. Вы можете использовать цветовую комбинацию для облегчения понимания.
Для двухточечного кроссовера нам нужно выбрать две точки и затем поменять биты.
Наконец, эти новые потомки добавляются к популяции.
Мутация
Мутация вносит разнообразие в население. Существуют разные виды мутаций, такие как мутация Bit Flip, мутация Swap, мутация инверсии и т. Д. Все они настолько просты.
В мутации Bit Flip просто выберите один или несколько битов, а затем переверните их. Если выбранный бит равен 0, установите его на 1, а если выбранный бит равен 1, установите его на 0.
В Мутации Swap Bit выберите два бита и просто поменяйте их местами.
При обратной мутации просто инвертируйте биты.
Реализация генетического алгоритма на Python
Попробуем реализовать генетический алгоритм на Python для оптимизации функций.
Заявление о проблеме
Предположим, что у нас есть уравнение f (x) = -x² + 5. Нам нужно решение, для которого оно имеет максимальное значение и ограничение 0≤x≤31. Чтобы выбрать начальную популяцию, используйте вероятность 0,2.
Вы можете найти полный код здесь.
Исходное население
Случайная инициализация лучше, чем эвристическая инициализация. Поэтому здесь для инициализации популяции используется случайная инициализация.
#initialize population import random best=-100000 populations =([[random.randint(0,1) for x in range(6)] for i in range(4)]) print(type(populations)) parents=[] new_populations = [] print(populations)
Фитнес-функция
Функция пригодности вычисляет значение пригодности хромосом. Функциональность фитнес-функции зависит от требований проблемы.
#fitness score calculation ............
def fitness_score() :
global populations,best
fit_value = []
fit_score=[]
for i in range(4) :
chromosome_value=0
for j in range(5,0,-1) :
chromosome_value += populations[i][j]*(2**(5-j))
chromosome_value = -1*chromosome_value if populations[i][0]==1 else chromosome_value
print(chromosome_value)
fit_value.append(-(chromosome_value**2) + 5 )
print(fit_value)
fit_value, populations = zip(*sorted(zip(fit_value, populations) , reverse = True))
best= fit_value[0]
fitness_score()
Выбор
Наиболее подходящие хромосомы выбираются на основе оценок пригодности. Здесь используется процесс выбора ранга.
def selectparent():
global parents
#global populations , parents
parents=populations[0:2]
print(type(parents))
print(parents)
selectparent()
Кроссовер
После выбора наиболее подходящих родителей требуется кроссовер для создания потомства. Здесь используется одноточечный кроссовер.
def crossover() :
global parents
cross_point = random.randint(0,5)
parents=parents + tuple([(parents[0][0:cross_point +1] +parents[1][cross_point+1:6])])
parents =parents+ tuple([(parents[1][0:cross_point +1] +parents[0][cross_point+1:6])])
print(parents)
Мутация
После того, как кроссовер выполнен, выполняется мутация для сохранения разнообразия от одного поколения к другому. Здесь мы рассмотрим одноточечную мутацию с переворотом битов.
def mutation() :
global populations, parents
mute = random.randint(0,49)
if mute == 20 :
x=random.randint(0,3)
y = random.randint(0,5)
parents[x][y] = 1-parents[x][y]
populations = parents
print(populations)
Нам нужно повторить весь процесс несколько раз, пока мы не найдем лучшее решение.
Вы найдете полный код на Kaggle.
использованная литература
- Генетический алгоритм - мутация
- Генетический алгоритм - кроссовер
- Генетический алгоритм - родительский отбор
- Генетический алгоритм - инициализация популяции
