Rehberli Yerel Arama (Guided Local Search, GLS) eniyileme problemlerini çözmek için kullanılan metaheuristik bir algoritmadır. Temelde, yerel arama yöntemleriyle birlikte kısıtlamalar ekleyerek arama alanını daraltır ve çözümün daha hızlı bulunmasını sağlar.

GLS, birçok optimizasyon probleminde çok etkili olan yerel arama yöntemlerini genişletmek ve çeşitlendirmek için tasarlanmıştır. Yerel arama metodolojileri genellikle en iyi çözümü bulma konusunda etkilidirler ancak genellikle yerel optimumlarda sıkışıp kalırlar, bu da gerçekten en iyi çözümü bulmalarını engeller. GLS, bu sorunu çözmek için arama sürecini çeşitlendirerek ve çözüm uzayında farklı bölgeleri ziyaret etmeye teşvik ederek yerel arama metodolojilerini geliştirir.

GLS'nin temel fikri, arama alanını belli bir çözüm yoluna "rehberlik" etmek ve ardından bu yol boyunca daha derinlemesine araştırma yapmaktır. Bu, çözüm alanında daha etkili bir şekilde gezinmeyi ve potansiyel olarak daha iyi çözümleri daha hızlı bir şekilde bulmayı sağlar.

GLS, aşağıdaki genel adımları içerir:

1. Yerel arama yöntemi ile bir çözüm bulunur (bu genellikle rastgele bir başlangıç noktasından başlar ve ardından bir çözüm bulana kadar yerel arama adımlarını uygular).
2. Çözümdeki özellikler belirlenir (örneğin, bir gezgin satıcı probleminde her bir kenar bir özellik olabilir).
3. Her özelliğin ne kadar kullanıldığını ölçen bir kullanım maliyeti belirlenir.
4. Yüksek maliyetli özellikler için bir ceza faktörü uygulanır, böylece gelecekteki aramalar bu özelliklerden kaçınır.
5. Adım 1'den 4'e kadar olan adımlar belirli bir durdurma kriteri karşılanana kadar tekrarlanır.

Bu yöntem genellikle seyahat eden satıcı problemları gibi çok zor optimizasyon problemları için kullanılır. GLS'nin etkinliği, kullanılan yerel arama yöntemi, özellik belirleme stratejisi ve ceza faktörünün nasıl belirlendiğine bağlıdır.

from numpy import argmax
from numpy.random import rand
from numpy.random import randint

# Büyük değerli şehirlerin seçilimini azaltmak için cezalandırıcı bir hedef fonksiyonu.
def objective(city, penalty, cities):
    return sum(cities) - penalty[city]

# Şehirler listesini kullanarak rastgele bir çözüm oluşturun.
def random_solution(cities, penalty):
    return randint(len(cities))

# Şu anki çözümden başka bir çözüm oluşturun.
def local_search(current, cities, penalty):
    best = current
    best_eval = objective(best, penalty, cities)
    for city in [i for i in range(len(cities)) if i != current]:
        # yeni bir çözüm değeri hesaplayın.
        solution_eval = objective(city, penalty, cities)
        # yeni çözüm değeri, en iyi çözüm değerinden daha büyükse, yeni çözümü en iyi çözüm olarak kabul edin.
        if solution_eval > best_eval:
            best, best_eval = city, solution_eval
    return best

# Rehberli Yerel Arama algoritmasını başlatın.
def guided_local_search(cities, max_iter, max_no_improv):
    # başlangıç çözümünü oluşturun.
    current = {'vector': random_solution(cities, [0]*len(cities))}
    current['cost'] = objective(current['vector'], [0]*len(cities), cities)
    # ceza faktörlerini başlatın.
    penalty = [0 for i in range(len(cities))]
    # en iyi çözümü başlangıç çözümü olarak belirleyin.
    best = current
    # her bir iterasyon için döngü oluşturun.
    for iter_ in range(max_iter):
        # yerel bir arama yaparak mevcut çözümü geliştirin.
        current['vector'] = local_search(current['vector'], cities, penalty)
        current['cost'] = objective(current['vector'], penalty, cities)
        # en iyi çözümü güncelleyin.
        if current['cost'] > best['cost']:
            best = current
        # ceza faktörlerini güncelleyin.
        for i in range(len(penalty)):
            if i == current['vector']:
                penalty[i] += 1
    return best['vector']

# Rehberli Yerel Arama algoritmasını çalıştırın.
max_iter = 50
max_no_improv = 30
cities = [randint(1, 10) for i in range(5)]

best = guided_local_search(cities, max_iter, max_no_improv)
print('En iyi bulunan şehir: %s' % best)

Yukarıdaki kodda, bir şehirler listesi üzerinde Rehberli Yerel Arama algoritmasını uyguluyoruz. Şehirler listesi, her şehrin değerini içerir ve bu değerler rastgele olarak atanır. Bu durumda, her bir şehir bir çözümü temsil eder ve amacımız bu çözümler arasından en iyisini bulmaktır.

Bu algoritmanın hedef fonksiyonu, bir ceza faktörü içerir, bu da büyük değerli çözümlerin seçilme olasılığını azaltır. Bu ceza faktörü, bir çözüm seçildiğinde her seferinde artar, bu da büyük değerli çözümlerin tekrar seçilme olasılığını daha da azaltır.

Bu algoritma, mevcut çözümün etrafında yerel bir arama yapar ve mevcut çözümden daha iyi bir çözüm bulursa, bu çözümü yeni mevcut çözüm olarak kabul eder. Bu yerel arama süreci, belirli bir sayıda yineleme veya belirli bir sayıda geliştirme olmadan sonra durur.

1. Hedef Fonksiyonu: Bu, optimizasyon probleminin çözümünün kalitesini değerlendiren bir fonksiyondur. Bu durumda, hedef fonksiyonu, bir şehirdeki toplam değeri belirler ve aynı zamanda bir ceza faktörü ekler. Bu ceza faktörü, bir şehrin daha önce seçilme sayısına dayanır. Yani, bir şehir ne kadar çok seçilirse, o şehrin seçilme olasılığı o kadar azalır. Bu, algoritmanın sürekli olarak aynı "iyi" çözümleri seçmesini ve diğer olası çözümleri araştırmamasını önlemeye yardımcı olur.

2. Rastgele Çözüm: Bu, şehirler listesi üzerinden rastgele bir şehir seçerek bir başlangıç çözümü oluşturur. Bu başlangıç çözümü, algoritmanın ilk 'mevcut' çözümü olacaktır.

3. Yerel Arama: Bu, mevcut çözümün etrafında bir arama yapar, yani mevcut çözümden farklı olan diğer tüm şehirler üzerinde bir döngü çalıştırır. Her bir şehir için, hedef fonksiyonunu hesaplar ve eğer bu değer en iyi şu anki değerden daha iyiyse, bu şehiri yeni 'en iyi' çözüm olarak kabul eder. Yani, yerel arama, mevcut çözümün "komşu" çözümlerini araştırarak daha iyi bir çözüm bulmayı dener.

4. Rehberli Yerel Arama: Bu, yerel aramanın bir uzantısıdır. Yerel aramadan farklı olarak, rehberli yerel arama, her iterasyonda mevcut çözümü ve ceza faktörlerini günceller. Bu, algoritmanın daha önce ziyaret ettiği çözümleri 'hatırlamasını' ve bu çözümleri tekrar seçme olasılığını azaltmasını sağlar. Bu şekilde, algoritma daha fazla çözüm alanını keşfedebilir.

5. Cezaların Güncellenmesi: Her iterasyonda, algoritma, mevcut çözüm için ceza faktörünü bir artırır. Bu, algoritmanın aynı çözümü tekrar tekrar seçmesini zorlaştırır ve daha fazla çözüm alanını keşfetmesini teşvik eder.

6. En İyi Çözüm: Bu, algoritmanın bulduğu en iyi çözümdür. Her iterasyonda, algoritma mevcut çözümün kalitesini (hedef fonksiyonu değerini) kontrol eder ve bu değer daha önce bulunan en iyi değerden daha iyiyse, mevcut çözümü yeni 'en iyi' çözüm olarak kabul eder. Bu 'en iyi' çözüm, algoritmanın sonucu olarak döndürülür.