[PYTHON] We will implement the optimization algorithm (harmony search)

Introduction

A series of optimization algorithm implementations. First, look at Overview.

The code can be found on github.

Harmony search

Overview

Harmony Search is an algorithm created by focusing on the thoughts of musicians when improvising. I think the musician has decided the original phrase of the following idea.

• Play frequently used phrases as they are
• Adjust and play frequently used phrases
• Create and play a new phrase

reference ・ Introduction to Evolutionary Computation Algorithms Optimal Solutions Derived from Behavioral Sciences of Organisms

algorithm

• Algorithm flow

• Term correspondence

• Regarding hyperparameters

Duplicate chords

Use the target chord as it is.

x^{new}_i = x^r_i

Adjust and use chords

Adjust with the following formula.

$ B $ is the bandwidth, a user-specified variable.

Bandwidth improvement

This article is original.

In the above formula, the value of $ B $ is highly dependent on the lower and upper limits of the one element in question. So instead of using $ B $ directly, I chose a percentage.

Whole code

import math
import random

class Harmony():
    def __init__(self, 
        harmony_max,
        bandwidth=0.1,
        enable_bandwidth_rate=False,  #Whether bandwidth is a percentage or a value
        select_rate=0.8,
        change_rate=0.3,
    ):
        self.harmony_max = harmony_max
        self.bandwidth = bandwidth
        self.enable_bandwidth_rate = enable_bandwidth_rate
        self.select_rate = select_rate
        self.change_rate = change_rate

    def init(self, problem):
        self.problem = problem

        self.harmonys = []
        for _ in range(self.harmony_max):
            self.harmonys.append(problem.create())


    def step(self):

        #Create a new harmony
        arr = []
        for i in range(self.problem.size):
            
            if random.random() < self.select_rate:
                #Generate new chords
                arr.append(self.problem.randomVal())
                continue

            #Select one harmony
            h_arr = self.harmonys[random.randint(0, self.harmony_max-1)].getArray()

            if random.random() < self.change_rate:
                #Change chords
                if self.enable_bandwidth_rate:
                    #Specify bandwidth as a percentage
                    bandwidth = self.bandwidth * (self.problem.MAX_VAL - self.problem.MIN_VAL)
                else:
                    bandwidth = self.bandwidth
                n = h_arr[i] + bandwidth * (random.random()*2-1)
                arr.append(n)
            else:
                #Duplicate chords
                arr.append(h_arr[i])

        harmony = self.problem.create(arr)

        #Replace if the new harmony has a higher rating than the worst harmony
        self.harmonys.sort(key=lambda x: x.getScore())
        if self.harmonys[0].getScore() < harmony.getScore():
            self.harmonys[0] = harmony

Hyperparameter example

It is the result of optimizing hyperparameters with optuna for each problem. One optimization trial yields results with a search time of 5 seconds. I did this 100 times and asked optuna to find the best hyperparameters.

Visualization of actual movement

The 1st dimension is 6 individuals, and the 2nd dimension is 20 individuals, which is the result of 50 steps. The red circle is the individual with the highest score in that step.

The parameters were executed below.

Harmony(N, bandwidth=1.0, enable_bandwidth_rate=True, select_rate=0.4, change_rate=0.9)

function_Ackley

• 1D

• 2D

function_Rastrigin

• 1D

• 2D

function_Schwefel

• 1D

• 2D

function_StyblinskiTang

• 1D

• 2D

function_XinSheYang

• 1D

• 2D

Afterword

Replacing the individual with the lowest evaluation value is a feature not found in other algorithms. The reason why learning seems slow in the image is that only one individual is evaluated in one step. (Cuckoo search is similar, 1 step ≒ 1 individual evaluation)