Неконтролируемое обучение и алгоритмы случайной оптимизации
Алгоритм имитации отжига (SA) - один из многих алгоритмов случайной оптимизации. В отличие от таких алгоритмов, как алгоритм Hill Climbing, целью которых является только улучшение оптимизации, SA позволяет проводить больше исследований. Идея состоит в том, что с этим исследованием более вероятно достижение глобального оптимума, чем локального (для получения дополнительной информации о локальных оптимумах, глобальных оптимумах и алгоритме оптимизации восхождения на холм перейдите по этой ссылке).
Термин «отжиг» используется в металлургии, где целью является снижение и повышение температуры металла. Этот процесс позволяет молекулам повторно объединяться и каждый раз приближаться, так что металл становится тверже. Аналогия применяется к алгоритму SA путем приближения к решению, отхода от него путем исследования и снова приближения к еще лучшему решению.
Алгоритм имитации отжига
Алгоритм можно разложить на 4 простых шага:
- Начать со случайной точки x.
- Выберем новую точку xⱼ в окрестности N (x).
- Решите, переходить ли к новой точке xⱼ. Решение будет приниматься на основе функции вероятности P (x, xⱼ, T) (поясняется ниже).
- Уменьшить T
Как мы уже упоминали ранее, P (x, xⱼ, T) - это функция, которая будет указывать нам, перейдем ли мы к новой точке или нет:
Давайте посмотрим, что сообщает нам функция. F (x) - целевая функция (функция, для которой мы хотим найти оптимальную точку x). Если новая точка xⱼ улучшает результат целевой функции, мы переместимся в новую точку с вероятностью 1.
Когда новая точка не улучшает целевую функцию, мы переместимся к новой точке в зависимости от разницы F (xⱼ) -F (x) и переменной T.
Когда T высокое, вероятность перехода к новой точке также будет высокой, а когда T низкое, вероятность перехода к новой точке также низка. Вот почему сначала мы начнем с высокого T, чтобы провести больше исследований, и постепенно уменьшим значение T, чтобы достичь оптимальной точки.
Теперь, когда мы знаем, как работает алгоритм, пора выполнить пример с использованием Python, чтобы углубить наше понимание.
Проблема восьми королев
Задача восьми ферзей состоит в том, чтобы расположить 8 ферзей на доске 8 * 8, при этом ни одна из них не находится на линии атаки друг друга. Ферзи могут двигаться по горизонтали, диагонали и вертикали, как показано на Рисунке 1.1.
Найти решение проблемы непросто, поскольку существует множество комбинаций. Мы можем видеть некоторые решения на изображении 1.2, когда на доске были размещены только 6 и 7 ферзей.
Теперь, когда мы понимаем проблему, перейдем к коду Python и решим ее.
8 королев с использованием Python
В python существует библиотека под названием «mlrose», которая очень полезна для реализации алгоритмов случайной оптимизации, поэтому первые несколько строк кода будут использоваться для импорта этой библиотеки, а также библиотеки numpy, которая помогает нам обрабатывать массивы.
### Importing the necessary libraries import mlrose import numpy as np
Следующим шагом является определение целевой функции. Целевая функция будет подсчитывать количество ферзей, которые находятся в месте, где их нельзя атаковать. Учитывая, что ферзи движутся вертикально, разумно сказать, что ни один ферзь не должен располагаться в одной и той же вертикали, и, таким образом, мы можем представить положение каждого ферзя в виде простого массива из 8 позиций. Например, на шахматной доске массив A = [0,2,1,3,7,4,5,6] будет выглядеть как Изображение 2.1.
Пришло время закодировать целевую функцию:
###Defining the objective function
def queens_max(position):
# We start the count
no_attack_on_j = 0
queen_not_attacking=0
# Compare for each pair of queens
for i in range(len(position) - 1):
no_attack_on_j=0
for j in range(i + 1, len(position)):
### Check if there is any diagonal or horizontal attack.
###Iterative process for each column
if (position[j] != position[i]) and (position[j] != position[i] + (j - i)) and (position[j] != position[i] - (j - i)):
"""If there isn't any attack on the evaluated column.
The count is increased by one.
This counter is only used as a reference ."""
no_attack_on_j += 1
"""If there is no attack on all the columns.
The general counter is increased by one.
This counter indicates the number of queens that are correctly
positioned."""
if(no_attack_on_j==len(position)-1-i):
queen_not_attacking+=1
"""The return number is the number of queens not attacking each
other. If this number is 7 we add 1 cause it means the last
queen is also free of attack."""
if(queen_not_attacking==7):
queen_not_attacking+=1
return queen_not_attacking
Определенная ранее целевая функция назначается в качестве аргумента методу CustomFitness в mlrose. Вот так с этой библиотекой может работать любая целевая функция.
# Assign the objective function to "CustomFitness" method. objective= mlrose.CustomFitness(queens_max)
Теперь мы закончили сложную часть. Осталось только сказать mlrose, какую проблему нужно решить. Решаемая задача имеет дискретные числа (целые числа), поэтому воспользуемся методом DiscreteOpt. Этот метод будет содержать описание проблемы и имеет 4 аргумента:
- length - размер массива, с которым мы работаем (для задачи восьми ферзей это 8).
- fitness_fn - целевая функция, которую мы ранее определили с именем «цель».
- maximize - должно быть «Истина», если мы хотим максимизировать целевую функцию, и «Ложь» в противном случае.
- max_val - этот параметр указывает максимальное значение, которое может принимать функция. Он начинается с 0 и заканчивается max_val-1. В нашем случае ферзь может располагаться от 0 до 7, поэтому max_val = 8.
Строка кода:
#Description of the problem problem = mlrose.DiscreteOpt(length = 8, fitness_fn = objective, maximize = True, max_val = 8)
Наконец, пора рассказать mlrose, как решить проблему. Мы знаем, что собираемся использовать имитацию отжига (SA), и важно указать 5 параметров.
- проблема - этот параметр содержит информацию о проблеме. Мы определили это ранее под названием «проблема».
- schedule - этот параметр сообщает T, как уменьшаться на каждой итерации. Есть много способов уменьшить T, и их можно проверить на mlrose. На этот раз T будет экспоненциально уменьшаться с помощью ExpDecay ().
- max_attempts - важно определить количество попыток, с которыми алгоритм будет пытаться найти лучшее решение. Если количество попыток достигает максимума, он должен остановиться.
- max_iter - указывает максимальное количество новых точек, которые алгоритм может найти, или максимальное количество итераций, которые он выполняет.
- init_state - параметр «init_state» - это начальная позиция массива.
Последний кусок кода выглядит так:
# Define decay schedule
T = mlrose.ExpDecay()
# Define initial state
initial_position = np.array([4, 6, 1, 5, 2, 0, 3, 7])
# Solve problem using simulated annealing
best_position, best_objective = mlrose.simulated_annealing(problem=problem, schedule = T,
max_attempts = 500, max_iters = 5000,
init_state = initial_position)
print('The best position found is: ', best_position)
print('The number of queens that are not attacking each other is: ', best_objective)
Output:
The best position found is: [4 6 1 5 2 0 3 7]
The number of queens that are not attacking each other is: 8.0
Мы успешно решили проблему 8 ферзей, как показано на Рисунке 2.2.
Заключительные замечания и код
Надеюсь, вам понравилась статья, и вы поиграли с проблемой восьми ферзей. Я оставляю вам код в google colab и github. Можно запустить этот код и с помощью нескольких настроек даже решить проблему 9,10… n ферзя.
Библиография:
Машинное обучение, рандомизированная оптимизация и поиск¶. (нет данных). Получено 13 августа 2020 г. с сайта https://mlrose.readthedocs.io/en/stable/.
Тренировки мозга. (нет данных). Получено 13 августа 2020 г. с сайта http://www.brainmetrix.com/8-queens/.
Восемь королев. (нет данных). Получено 10 сентября 2020 г. с сайта http://www.datagenetics.com/blog/august42012/.
Первоначально опубликовано на https://www.estudiodedatos.com 25 августа 2020 г.
