Harmony Search Algorithm

03 September 2023

1. Introduction

Harmony search is an optimization algorithm inspired by biological algorithms. The idea of harmony search comes from musicians constantly tuning their instruments to achieve a good harmony. The algorithm is developed by Zong Woo Geem et al. in 2001, and it has been widely used because of its easy application and fast convergence to the optimum solution.

The idea of the algorithm is based on a band playing together. A musician in the band tunes the instrument until a certain harmony is achieved. The orchestra, which plays in a bad harmony at first, adjusts the instrument tuning until they achieve a certain degree of good harmony. Every harmony that arises is a solution to the problem. The Harmony algorithm generates new solutions that are iteratively improving by making random changes to previous solutions, such as an orchestra.

2. The Algorithm

                     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. Applications of Harmony Search

Due to its easy applicability and efficiency, harmony search is used in many areas. For example, it can be used in course timetabling which is a very challenging task in any academic institution. The design of a water distribution network is another use for HSA. For the network to provide a smooth water supply at a low cost, it must be constructed with consideration for differences in pipe diameter, elevation, and separation. HSA is also used for power supply optimization, which involves supplying a lot of electricity at the lowest possible cost. All in all, Harmony search algorithm is used in many areas such as scheduling, civil engineering, electrical engineering.

4. Sample Problem

4.1 Problem Definition

We will use harmony search algorithm to find the nearest point to the target. The target is a random point in the 1st region of the 100x100 coordinate system.

4.2 Fitness Function

The fitness function is the formula of the distance between two points. The goal is to minimize the function.

                         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 Defining Parameters

Harmony memory stores the best harmonies. Harmony history stores the harmonies on every generation. Target point which is defined by problem definition is a tuple consisting of x and y coordinates. Harmony memory size is the maximum length of the harmony memory. Number of improvisations is the number of iterations to improve harmonies. Harmony memory considering rate is the probability of choosing an existing harmony from the memory. Pitch adjusting rate is the probability of making small changes to the selected harmony from the memory. Maximum x and maximum y are the boundary of the coordinate system.

                         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 Creating Initial Harmonies

Initial harmonies are randomly generated at the beginning of the algorithm. Fitness function is evaluated for each generated harmony.

                         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 function randomly selects a harmony from the harmony memory.

                         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 function slightly changes the harmony. It checks the boundary limits of the coordinate system and increases or decreases the coordinates by one, depending on chance.

                         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 function randomly creates a new harmony.

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

4.8 Update Harmony Memory

Update harmony memory function replaces the worst harmony in the memory to the new harmony if the new harmony is a better solution than the worst harmony.

                         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 The Driver Function

The algorithm is executed with this main function. First, the harmony memory is randomly initialized. Then, either a new harmony is created or randomly selected from memory. If the harmony is randomly selected from the harmony memory it can be slightly changed by the pitch adjustment function. After that, harmony memory is updated. The worst harmony is replaced by the current harmony if the current harmony is a better solution. As the last step of the loop, harmony history is updated if the current iteration is a new generation. Finally, the best harmony and the fitness is printed to the screen.

                         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 Results

The algorithm continuously improves the worst solution, ensuring that all solutions are close to the best and that all solutions are in harmony. As seen in the Figure 4.1, in the first iteration the solutions are distributed and inharmonious, but in the Figure 4.2 all the solutions are close to the target and overall harmony is provided.