Harmoni Arama Algoritması

03 Eylül 2023

1. Giriş

Harmoni arama, biyolojik algoritmalardan ilham alan bir optimizasyon algoritmasıdır. Harmoni arayışı fikri, müzisyenlerin iyi bir uyum elde etmek için sürekli olarak enstrümanlarını ayarlamalarından kaynaklanmaktadır. Algoritma Zong Woo Geem ve diğerleri tarafından 2001 yılında geliştirilmiş olup, kolay uygulanması ve optimum çözüme hızlı yakınlaşması nedeniyle yaygın olarak kullanılmaktadır.

Algoritmanın fikri bir grubun birlikte çalmasına dayanıyor. Gruptaki bir müzisyen belli bir uyum sağlanana kadar enstrümanı akort eder. Başlangıçta kötü bir uyumla çalan orkestra, belli bir iyi uyum düzeyine ulaşana kadar enstrüman akortunu ayarlar. Ortaya çıkan her uyum, sorunun çözümüdür. Harmoni algoritması, orkestra gibi önceki çözümlerde rastgele değişiklikler yaparak yinelemeli olarak iyileşen yeni çözümler üretir.

2. Algoritma

                     Initialize the parameters of harmony memory size, number of improvisations,\n\tharmony memory considering rate, pitch adjusting rate.\nInitialize the harmony memory.\nEvaluate all solutions using the fitness function.\nFor number of improvisations do\n\tnew harmony = ∅\n\tif random < harmony memory considering rate then\n\t\tmemory consideration\n\t\tif random < pitch adjustment rate then\n\t\t\tpitch adjustment\n\t\tend if\n\telse\n\t\trandom consideration\n\tend if\n\tevaluate the fitness function of the new solution.\n\tReplace the worst solution in harmony memory by the new solution.\nEnd loop                 

3. Harmoni Arama Kullanım Alanları

Kolay uygulanabilirliği ve verimliliği nedeniyle harmoni arayışı birçok alanda kullanılmaktadır. Örneğin herhangi bir akademik kurumda oldukça zorlu bir görev olan ders çizelgelemede kullanılabilir. Su dağıtım ağının tasarımı HSA'nın başka bir kullanımıdır. Şebekenin düşük maliyetle sorunsuz bir su temini sağlaması için boru çapı, yükseklik ve ayrım farklılıkları dikkate alınarak inşa edilmesi gerekir. HSA ayrıca mümkün olan en düşük maliyetle çok fazla elektrik sağlamayı içeren güç kaynağı optimizasyonu için de kullanılır. Sonuç olarak harmoni arama algoritması planlama, inşaat mühendisliği, elektrik mühendisliği gibi birçok alanda kullanılmaktadır.

4. Örnek Problem

4.1 Problem Tanımı

Hedefe en yakın noktayı bulmak için harmoni arama algoritmasını kullanacağız. Hedef 100x100 koordinat sisteminin 1. bölgesindeki rastgele bir noktadır.

4.2 Uygunluk Fonksiyonu

Uygunluk fonksiyonu iki nokta arasındaki mesafenin formülüdür. Amaç, fonksiyonu en aza indirmektir.

                         def fitness_function(first_point, second_point=TARGET_POINT):\n\treturn math.sqrt((first_point[0] - second_point[0]) ** 2 +\n\t\t\t\t\t(first_point[1] - second_point[1]) ** 2)                     

4.3 Parametreleri Tanımlama

Harmony memory en iyi harmonileri saklar. Harmony history her nesildeki harmonileri saklar. Problem tanımıyla tanımlanan hedef nokta, x ve y koordinatlarından oluşan bir tuple'dır. Harmony memory size, harmoni hafızasının maksimum uzunluğudur. Number of improvisations, harmonileri geliştirmek için yapılan yinelemelerin sayısıdır. Harmony memory considering rate, mevcut bir harmoniyi hafızadan seçme olasılığıdır. Pitch adjusting rate, hafızadan seçilen harmonide küçük değişiklikler yapma olasılığıdır. Maksimum x ve maksimum y koordinat sisteminin sınırıdır.

                         harmony_memory = []  # stores best harmonies\nharmony_history = []  # stores all harmonies on every generation\nTARGET_POINT = (50, 50)\nHARMONY_MEMORY_SIZE = 1000\nNUM_OF_IMPROVISATIONS = 10000\nHARMONY_MEMORY_CONSIDERING_RATE = 0.4\nPITCH_ADJUSTING_RATE = 0.4\nMAX_X = 100\nMAX_Y = 100                     

4.4 İlk Harmonileri Yaratma

Başlangıç harmonileri algoritmanın başlangıcında rastgele oluşturulur. Üretilen her harmoni için uygunluk fonksiyonu çalıştırılır.

                         def init_memories():\n    initial_harmonies = []\n    for i in range(HARMONY_MEMORY_SIZE):\n        harmony = (random.randint(0, MAX_X), random.randint(0, MAX_Y))\n        fitness = fitness_function(harmony)\n        initial_harmonies.append((harmony, fitness))\n    return initial_harmonies                     

4.5 Memory Consideration

Memory consideration fonksiyonu, harmoni belleğinden rastgele bir harmoni seçer.

                         def memory_consideration(harmony):\n    memory_index = random.randint(0, HARMONY_MEMORY_SIZE - 1)\n    harmony.extend(harmony_memory[memory_index][0])                     

4.6 Pitch Adjustment

Pitch adjustment fonksiyonu harmoniyi biraz değiştirir. Koordinat sisteminin sınırlarını kontrol ederek koordinatları şansa bağlı olarak birer birer artırır veya azaltır.

                         def pitch_adjustment(harmony):\n    is_pitch_up_allowed = (harmony[0] + 1) <= MAX_X and (harmony[1] + 1) <= MAX_Y\n    is_pitch_down_allowed = (harmony[0] - 1) >= 0 and (harmony[1] - 1) > 0\n    if random.random() < 0.5 and is_pitch_up_allowed:\n        harmony[0] += 1\n        harmony[1] += 1\n    elif is_pitch_down_allowed:\n        harmony[0] -= 1\n        harmony[1] -= 1                     

4.7 Random Selection

Random selection fonksiyonu rastgele yeni bir uyum yaratır.

                         def random_selection(harmony):\n    harmony.extend((random.randint(0, MAX_X), random.randint(0, MAX_Y)))                     

4.8 Harmoni Belleğini Güncelle

Update harmony memory fonksiyonu, eğer yeni uyum en kötü uyumdan daha iyi bir çözüm ise, hafızadaki en kötü uyumu yeni uyumla değiştirir.

                         def update_harmony_memory(harmony, fitness):\n    if (harmony, fitness) not in harmony_memory:\n        worst_index = None\n        worst_fitness = float('-inf')\n        for i, (harmony, fitness) in enumerate(harmony_memory):\n            if fitness > worst_fitness:\n                worst_index = i\n                worst_fitness = fitness\n        if fitness < worst_fitness:\n            harmony_memory[worst_index] = (harmony, fitness)                     

4.9 Ana Fonksiyon

Algoritma bu ana fonksiyonla yürütülür. İlk olarak harmony memory rastgele kurulur. Daha sonra ya yeni bir harmoni yaratılır ya da hafızadan rastgele seçilir. Eğer harmoni harmoni memory'den rastgele seçilirse pitch adjustment function ile biraz değiştirilebilir. Bundan sonra harmoni hafızası güncellenir. Mevcut harmoni daha iyi bir çözüm ise, en kötü harmoni mevcut harmoniyle değiştirilir. Döngünün son adımı olarak, mevcut yinelemenin yeni nesil olması durumunda harmony history güncellenir. Son olarak en iyi harmoni ve uygunluk fonksiyonu değeri ekrana yazdırılır.

                         def main():\n    harmony_memory.extend(init_memories())\n    harmony_history.append(copy.deepcopy(harmony_memory))\n    generation = 0\n    for i in range(NUM_OF_IMPROVISATIONS):\n        harmony = []\n        if random.random() < HARMONY_MEMORY_CONSIDERING_RATE:\n            memory_consideration(harmony)\n            if random.random() < PITCH_ADJUSTING_RATE:\n                pitch_adjustment(harmony)\n        else:\n            random_selection(harmony)\n        fitness = fitness_function(harmony)\n        update_harmony_memory(harmony, fitness)\n\n        if i % HARMONY_MEMORY_SIZE == 0:\n            generation += 1\n            harmony_history.append(copy.deepcopy(harmony_memory))\n\n    best_harmony = None\n    best_fitness = float('+inf')\n    for harmony, fitness in harmony_memory:\n        if fitness < best_fitness:\n            best_harmony = harmony\n            best_fitness = fitness\n    print("Best harmony", best_harmony)\n    print("Best fitness", best_fitness)                     

5 Sonuçlar

Algoritma sürekli olarak en kötü çözümü iyileştirerek tüm çözümlerin en iyiye yakın olmasını ve tüm çözümlerin uyum içinde olmasını sağlar. Şekil 4.1'de görüldüğü gibi ilk iterasyonda çözümler dağınık ve uyumsuzdur ancak Şekil 4.2'de tüm çözümler hedefe yakın olup genel uyum sağlanmaktadır.