Açgözlü Rastgele Uyarlanabilir Arama (Greedy Randomized Adaptive Search Procedure, GRASP) bir heuristik veya metaheuristik arama algoritmasıdır. Bu algoritma, karmaşık optimizasyon problemlerini çözmek için kullanılır. GRASP, genellikle NP-zor problemleri çözmede etkilidir. Algoritmanın genel yaklaşımı iki ana adımdan oluşur: 

1. Yapılandırma Fazı: Bu aşamada, GRASP, olası çözümler arasından rastgele birini seçer. Ancak bu tamamen rastgele bir seçim değildir: seçim, çözümün kalitesini artıracak şekilde "açgözlü" bir yöntemle yönlendirilir. Yani, algoritma her adımda çözümün kalitesini en çok artıracak olanı seçme eğilimindedir. Bu yöntem, genellikle bir RCL (Restricted Candidate List) adı verilen kısıtlı bir aday listesi kullanılarak uygulanır.

2. Yerel Arama Fazı: Bu aşamada, yapılandırma fazında bulunan çözümden yola çıkarak yerel bir arama yapılır. Yerel arama, genellikle "en iyi komşu" veya "ilk iyileştirme" stratejisi kullanarak gerçekleştirilir. Yani, mevcut çözümden "kısa bir mesafe" içinde bulunan diğer çözümler arasından en iyi olanı seçmeye çalışır.

Bu iki faz, belirli bir durma kriteri sağlanana kadar tekrarlanır. Durma kriteri genellikle belirli bir zaman sınırına ulaşılması, belirli bir sayıda iterasyon yapılması veya belirli bir çözüm kalitesine ulaşılması şeklinde olabilir.

GRASP, genellikle birden fazla başlangıç noktasından çözüm arama ve yerel arama ile çözümü rafine etme yeteneği sayesinde etkilidir. Bu, GRASP'ın hem global çözüm uzayını geniş bir şekilde keşfetmesine hem de bulunan her çözümü detaylı bir şekilde incelemesine olanak sağlar. Bu yaklaşım, GRASP'ın karmaşık optimizasyon problemlerinde genellikle iyi sonuçlar vermesini sağlar.

import numpy as np
from random import choice

# İki nokta arasındaki Öklidyen mesafe
def mesafe(nokta1, nokta2):
    return np.sqrt((nokta1[0]-nokta2[0])**2 + (nokta1[1]-nokta2[1])**2)

# Açgözlü inşa heuristiği
def açgözlü_inşa(sehirler, alpha):
    N = len(sehirler)
    kalanlar = list(range(1, N))
    çözüm = [0]
    while kalanlar:
        mesafeler = [mesafe(sehirler[çözüm[-1]], sehirler[j]) for j in kalanlar]
        max_mesafe = max(mesafeler)
        min_mesafe = min(mesafeler)
        esik_deger = min_mesafe + alpha * (max_mesafe - min_mesafe)
        adaylar = [j for j, mesafe in zip(kalanlar, mesafeler) if mesafe <= esik_deger]
        sonraki_sehir = choice(adaylar)
        kalanlar.remove(sonraki_sehir)
        çözüm.append(sonraki_sehir)
    return çözüm

# Yerel arama prosedürü
def yerel_arama(sehirler, çözüm):
    N = len(çözüm)
    for i in range(N-1):
        for j in range(i+2, N+1):
            komsu = çözüm[:i+1] + çözüm[i+1:j][::-1] + çözüm[j:]
            if tur_uzunluğu(sehirler, komsu) < tur_uzunluğu(sehirler, çözüm):
                return komsu
    return çözüm

# Turun toplam uzunluğu
def tur_uzunluğu(sehirler, çözüm):
    return sum(mesafe(sehirler[çözüm[i-1]], sehirler[çözüm[i]]) for i in range(len(çözüm)))

# Ana GRASP prosedürü
def grasp(sehirler, alpha, max_iter):
    en_iyi_çözüm = açgözlü_inşa(sehirler, alpha)
    en_iyi_uzunluk = tur_uzunluğu(sehirler, en_iyi_çözüm)
    for _ in range(max_iter):
        çözüm = açgözlü_inşa(sehirler, alpha)
        çözüm = yerel_arama(sehirler, çözüm)
        uzunluk = tur_uzunluğu(sehirler, çözüm)
        if uzunluk < en_iyi_uzunluk:
            en_iyi_uzunluk = uzunluk
            en_iyi_çözüm = çözüm
    return en_iyi_çözüm, en_iyi_uzunluk

Bu kodu çalıştırmak için öncelikle şehirlerin koordinatlarını belirleyen bir liste oluşturmanız gerekiyor. Ayrıca, alpha ve max_iter değerlerini belirtmeniz gerekiyor. İşte bir örnek:

# Rastgele şehirler oluşturalım
np.random.seed(0)  # Her seferinde aynı şehirlerin oluşması için seed değerini sabitledik
sehirler = [list(np.random.rand(2)) for _ in range(20)]  # 20 şehir için 2 boyutlu (x, y) rastgele koordinatlar oluşturulur

# Alfa ve max_iter değerlerini belirleyelim
alpha = 0.5  # Yarı yolda rastgele ve yarı yolda açgözlü strateji kullanılacak
max_iter = 100  # 100 iterasyon yapılacak

# Şimdi GRASP algoritmasını çağıralım
en_iyi_çözüm, en_iyi_uzunluk = grasp(sehirler, alpha, max_iter)

# Sonuçları yazdıralım
print("En iyi çözüm: ", en_iyi_çözüm)
print("En iyi tur uzunluğu: ", en_iyi_uzunluk)

Bu kodu çalıştırdığınızda, en iyi tur (yani gezgin satıcının ziyaret ettiği şehirlerin sırası) ve bu turun toplam uzunluğunu döndürecektir.