Покрытие вершины с использованием генетического алгоритма
Генетический алгоритм - это эволюционная вычислительная техника, основанная на концепциях Генетики и Естественного отбора. Он в основном используется для поиска почти оптимального решения для многих оптимизаций и более сложных задач, где детерминированное полиномиальное решение невозможно.
Генетический алгоритм также можно использовать в пространстве поиска, чтобы найти нужные функции и параметры модели для прогнозирования целевой переменной. Другим важным преимуществом генетического алгоритма является то, что помимо стандартных задач оптимизации они также полезны, когда целевая функция является недифференцируемой, прерывистой, стохастической или нелинейной.
Я начну этот блог с краткого описания Генетического алгоритма и Вершинного покрытия. Затем я покажу, как мы можем использовать генетический алгоритм для получения почти оптимального решения проблемы вершинного покрытия, которое намного лучше, чем алгоритмы приближения. В этом блоге я также хочу, чтобы читатели ощутили силу генетического алгоритма. Полный исходный код решения можно найти здесь.
Генетический алгоритм
Генетические алгоритмы делятся на 5 этапов:
- Инициализация: исходные решения (первые поколения) инициализируются случайным образом.
- Оценка пригодности. Основная идея заключается в том, что может быть сложно найти оптимальное решение, но как только у нас есть какое-то решение, к нему легко привязать оценку качества или пригодности.
- Выбор: наиболее приспособленный член (решение) популяции выживает и переходит к следующему поколению.
- Кроссовер: наиболее подходящий член (решения) популяции объединяется в пары для создания новых членов (возможное решение).
- Мутация: новые участники (возможные новые решения) незначительно меняются, чтобы стать еще лучше.
Как только начальная популяция сгенерирована, цикл отбора, кроссовера и мутации продолжается в течение многих поколений, пока алгоритм не сойдется или не будет достигнута максимальная итерация. Эти концепции подробно описаны в этом блоге.
Проблема с вершинным покрытием
Вершинное покрытие - это такое подмножество вершин в Графе, что для каждого ребра (u, v) графа либо u, либо v находится в вершинном покрытии. Это типичная NP-трудная задача оптимизации, имеющая алгоритм аппроксимации, но не имеющая детерминированного полиномиального решения.
График 1 имеет вершинное покрытие 3, как и в случае трех красных узлов все ребра покрываются таким образом, что для каждого ребра (u, v) графа либо ‘u’, либо ‘v’ находится в вершинном покрытии. Точно так же Graph-2 имеет вершинное покрытие 4.
Граф 3 имеет покрытие вершин 2, а Граф 4 имеет покрытие вершин 3.
Vertex-Cover - это типичная NP-Hard проблема, не имеющая детерминированного решения за полиномиальное время. У нас есть приближенный алгоритм, который работает за полиномиальное время и дает неоптимальное решение. Подробности алгоритма аппроксимации можно найти по ссылке ниже.
Также имеется доказательство того, что приближенное решение никогда не может превышать наиболее оптимальное решение в 2 раза. Подробности можно найти здесь.
Создание данных графика
Я создал график с 250 узлами. Основная идея, используемая для создания этого графика, состоит в том, чтобы нарисовать случайное число в диапазоне [0,1] и создать границу между узлами «u» и «v», только если вероятность меньше порогового значения.
#Graph Library
import networkx as nx
edge_probability = .0085
adjacency_matrix = np.zeros((nodes,nodes),dtype = np.int)
edges = []
edges_cnt = 0
for i in range(nodes):
for j in range(i):
prob = random.random()
if prob < edge_probability:
adjacency_matrix[i,j] = 1
edges.append((i,j))
edges_cnt += 1
G=nx.Graph()
G.add_nodes_from(list(range(0,nodes)))
G.add_edges_from(edges)
nx.draw(G,node_color='r', node_size=18, alpha=0.8)
График имеет 256 ребер.
Алгоритм аппроксимации для нахождения вершинного покрытия на графе "G"
Алгоритм аппроксимации вершинного покрытия - это жадный алгоритм, который может не дать наиболее оптимального решения. Работу алгоритма аппроксимации можно объяснить следующим образом:
1) Initialize the solution-set as {}
2) Loop through all the E (Edges).
3) For an arbitrary edge (u, v) from set of E (Edges).
a) Add 'u' and 'v' to solution-set if none of the vertices 'u' or 'v' present in the set already
b) If any of the vertex 'u' or 'v' present already in the solution-set, skip the edge and move to the next one.
3) Return solution-set.
Более подробную информацию о решении можно найти в этом блоге.
Запуская алгоритм аппроксимации на нашем Графе «G», имеющем 250 узлов и 256 ребер, мы получаем вершинное покрытие из 178 узлов.
#Vertex Cover Greedy Algorithm
visited = np.zeros(nodes)
cnt = 0
for e in edges:
(u,v) = e
# print(u,v)
if ((visited[u]==0) & (visited[v]==0)):
visited[u] = 1
visited[v] = 1
cnt+=2
print("Vertex cover consists of {} nodes".format(cnt))
Выход: Вершинная крышка состоит из 178 узлов.
Генетический алгоритм поиска вершинного покрытия на графике "G"
Подход к решению
Возможных подходов к решению Vertex-Cover с использованием генетического алгоритма может быть довольно много.
Один из подходов может заключаться в определении оценки пригодности как функции покрытых ребер и количества используемых вершин. Когда решение покрывает все ребра, штраф равен 0, и штраф учитывается, если некоторые ребра пропущены. Кроме того, существует стоимость, связанная с количеством узлов, используемых для этого. Это потребует тщательного определения фитнес-ядра.
Я не хотел, чтобы у меня была проблема с оценкой пригодности как функцией перекрытых ребер и количества вершин. Я хотел, чтобы это было функцией одного из них. Итак, я зафиксировал количество вершин и определил оценку пригодности как функцию только покрытых ребер. Вот как это было сделано:
1. Is it possible to cover all the edges with exactly 'k' number of vertices. Genetic Algorithm tries to find such solution, if possible. 2. Binary Search for the minimum value for 'k'.
Инициализация
Нам нужно выяснить, можно ли покрыть все ребра, используя некоторые «k» вершин. Итак, мы случайным образом инициализируем популяцию с некоторыми «k» вершинами как часть вершинного покрытия.
n = 250
#----------Hyperparameters can be tuned--------------------
pop_total = 1500 # max population allowed in the environment
pop_init = 1000 # Initial Population
max_iterate = 500 # Max Iterations or Generations allowed
#----------------------------------------------------------
def chromosomes_gen(n,k,pop_init):
lst = []
for i in range(pop_init):
chromosome = np.zeros(n,dtype= int)
samples = random.sample(range(0,n), k = k)
for j in range(k):
chromosome[samples[j]] = 1
lst.append(chromosome)
return lst
Оценка фитнеса
Здесь я проверяю, используя данное решение для ровно «k» вершин, сколько ребер пропущено. Я добавляю для него счетчик штрафов / препятствий.
def cost(soln,n,edges):
obstacles = 0
for e in edges:
(u,v) = e
if ((soln[u]==0) & (soln[v]==0)):
obstacles += 1
return obstacles
Выбор
Возможны различные подходы к отбору. В этой задаче я просто беру решения с лучшими результатами, передаю их следующему поколению и убиваю остальные. Переменная pop_total определяет максимальную популяцию, которую можно передать следующему поколению.
def selection(lst,pop_total,n,edges):
score = []
output_lst = []
len_lst = len(lst)
for i in range(len_lst):
score.append(cost(lst[i],n,edges))
sorted_index = np.argsort(score)
cnt = 0
for i in range(len_lst):
output_lst.append(lst[sorted_index[i]])
if((i+1) == pop_total):
break
lst = output_lst
# Return truncated-population and best score of this Generation
return lst,score[sorted_index[0]]
Кроссовер
В кроссовере мы объединяем два решения в надежде получить еще лучшее решение. В этой задаче я беру два решения, нахожу вершины в первом решении, которых нет во втором решении, и аналогичным образом беру вершины во втором решении, которых нет в первом решении, и меняю местами 50% из них.
#Crossover
cross_over_prob = 0.50
for i in range(len_lst):
# First solution
tmp = lst[i].copy()
# Second solution
mate_with = lst[int(random.uniform(0,len_lst))]
tmp_unique = []
mate_with_unique = []
# Store all vertices of Solution-1 and Solution-2
for j in range(n):
if(tmp[j]==1):
tmp_unique.append(j)
if(mate_with[j]==1):
mate_with_unique.append(j)
#Filter vertices from Solution-1 which is in Solution-2 and shuffle
tmp_unique = np.setdiff1d(tmp,mate_with)
random.shuffle(tmp_unique)
#Filter vertices from Solution-2 which is in Solution-1 and shuffle
mate_with_unique = np.setdiff1d(mate_with,tmp)
random.shuffle(mate_with_unique)
#Swap 50% unique vertices from Solution2 into Solution1 ~ New Soln
swap = math.ceil(cross_over_prob * min(len(tmp_unique),len(mate_with_unique)))
for j in range(swap):
tmp[mate_with_unique[j]] = 1
tmp[tmp_unique[j]] = 0
new_solution = tmp
Мутация
На этом этапе новые решения, выходящие из состояния кроссовера, немного меняются или, альтернативно, видоизменяются в надежде стать еще лучше. В этой задаче я выполняю два типа мутаций, меняя 5% раствора. Я подбрасываю монету, и если выпадает голова, я выполняю Мутацию-1, иначе выполняю Мутацию-2, изменяя 5% раствора по-разному.
В Мутации-1 я беру случайные 5% вершин из решения и заменяю их некоторыми другими случайными 5% вершин, которых раньше не было в решении.
В Мутации-2 я беру случайные 5% вершин из решения и заменяю их некоторыми другими 5% вершин, которые могут покрывать некоторые из ребер, которые текущее решение не может покрыть.
# Mutation
mutat_prob = 0.05
zeroes = []
ones = []
for j in range(n):
if soln[j]==1:
ones.append(j)
else:
zeroes.append(j)
random.shuffle(ones)
random.shuffle(zeroes)
coin_toss = random.random()
if(coin_toss <= 0.5):
# Mutation-1
swaps = min(len(ones),len(zeroes))
for j in range(swaps):
coin_toss2 = random.random()
if(coin_toss2 < mutat_prob):
soln[ones[j]] = 0
soln[zeroes[j]] = 1
#Swapping logic
dummy = ones[j]
ones[j] = zeroes[j]
zeroes[j] = dummy
else:
# Mutation-2
mutate_lst = []
for e in edges:
(u,v) = e
if((soln[u] == 0) & (soln[v] == 0)):
coin_toss2 = random.random()
if(coin_toss2 < mutat_prob):
coin_toss3 = random.random()
if(coin_toss3 <= 0.5):
if(u not in mutate_lst):
mutate_lst.append(u)
else:
if(v not in mutate_lst):
mutate_lst.append(v)
random.shuffle(mutate_lst)
sz = min(len(ones),len(mutate_lst))
for j in range(sz):
soln[ones[j]] = 0
soln[mutate_lst[j]] = 1
#Swapping logic
dummy = ones[j]
ones[j] = mutate_lst[j]
mutate_lst[j] = dummy
soln_lst.append(soln)
Производительность генетического алгоритма во многом зависит от того, насколько хорошо построены функции кроссовера и мутации. Эти функции должны быть тщательно спроектированы и настроены / изменены для достижения наилучшей производительности.
Двоичный поиск для поиска минимального "k"
Я выполняю двоичный поиск, чтобы найти наименьшее значение k, такое, что вершинное покрытие k вершин покрывает все ребра графа.
# Environment to perform Initialisation-Selection-Crossover-Mutation
def environ(n,k,mut_prob,pop_init,pop_totl,max_iterate,edges)
soln = chromosomes_gen(n,k,pop_init)
for it in range(max_iterate):
soln = cross_over_mutate(soln,n,k,mut_prob,pop_total,edges)
soln,cost_value = selection(soln,pop_total,n,edges)
if cost_value==0:
break
return cost_value,result
# Binary Search function
def mfind(n,mut_prob,pop_init,pop_total,max_iterate,edges,start,end)
result_dict = {}
l = start
h = end
ans = 0
while(l<=h):
m = int((l+h)/2.0)
cv,res = environ(n,m,mut_prob,pop_init,pop_total,max_iterate,edges)
if(cv==0):
result_dict[m] = res
h = m-1
else:
l = m + 1
return result_dict
# Main-function Call
res = mfind(n,mutat_prob,pop_init,pop_total,max_iterate,edges,1,n)
Полученные результаты
Используя генетический алгоритм, вершинное покрытие графа G с 250 узлами и 256 ребрами оказывается 104 узлами, что намного меньше и лучше, чем решение алгоритма приближения из 178 узлов. Полный исходный код решения можно найти здесь.
Заключение
В этом сообщении в блоге мы поняли концепцию генетического алгоритма, а также его варианты использования и свойства. Затем мы использовали генетический алгоритм для решения проблемы вершинного покрытия и получили гораздо лучшее решение, чем его аналог алгоритма приближения.
Если у вас есть какие-либо сомнения или вопросы, свяжитесь со мной. Мне будет интересно узнать, есть ли у вас интересная постановка проблемы или идея, и можно ли для этого использовать генетический алгоритм.
Мой канал Youtube для получения дополнительной информации:
Об авторе:
Абхишек Мунголи - опытный специалист по анализу данных с опытом работы в области машинного обучения и компьютерных наук, охватывающий различные области и способ решения проблем. Отлично разбирался в различных задачах машинного обучения и оптимизации, характерных для розничной торговли. С энтузиазмом относятся к масштабному внедрению моделей машинного обучения и обмену знаниями через блоги, выступления, встречи, публикации и т. Д.
Мой мотив всегда состоит в том, чтобы упростить самые сложные вещи до их наиболее упрощенной версии. Я люблю решение проблем, науку о данных, разработку продуктов и масштабируемые решения. Я люблю исследовать новые места и заниматься спортом в свободное время. Следуйте за мной в Medium, Linkedin или Instagram и просматривайте мои предыдущие сообщения. Приветствую отзывы и конструктивную критику. Некоторые из моих блогов -
- 5 ошибок, которых должен избегать каждый специалист по анализу данных
- Разложение временных рядов простым и интуитивно понятным способом
- Как вычисления на GPU буквально спасли меня на работе?
- Теория информации и расхождение KL Часть I и Часть II
- Обработка Википедии с помощью Apache Spark для создания горячих наборов данных
- Нечеткая кластеризация на основе полууправляемого вложения
- Сравните, какая модель машинного обучения работает лучше
- Анализ данных Fitbit для демистификации изменений телесного паттерна в условиях пандемической изоляции
- Мифы и реальность вокруг корреляции
- Руководство для того, чтобы стать специалистом по анализу данных, ориентированным на бизнес
